流行排序和佩奇排序簡述（manifold rank & Page rank）
最近看了一篇文章，其中用到了流行排序（manifold ranking），于是就重新補查了一下流行排序，又因為流行排序中的收斂性用到了佩奇排序（page rank），是以這裡就簡單的叙述一下page rank和manifold rank。希望大家能有所收獲。由于manifold rank中用到了page rank的思想，是以此部落格就先叙述page rank，再進而叙述manifold rank。
佩奇排序（Page rank）
佩奇排序因其英文名字是page rank，并且最早應用于搜尋網頁的排序，是以佩奇排序也被叫做頁排序。
實際上Page rank之是以得名是因為google創始人之一的拉裡佩奇（Lawrence Page）有關，他也是page rank的提出者，這一算法被用于解決網頁排序的問題。如下圖所示，我們使用不同的搜尋引擎，往往會得到不同的結果。那麼google最初是如何實作網頁的排序的呢？那就是page rank啦。
page rank的基本思想是利用馬爾科夫過程中的馬爾科夫穩定性（markoff stability），其算法步驟也是十分的簡單：
（1）假設我們正在上網，我們會随便的選一個網頁待上一會兒，然後再随機的跳轉到該網頁連接配接的另外的網頁，通過上述的方式，我們就能得到狀态轉移矩陣。
（2）然後一直重複上次操作，直到收斂（其收斂是由于馬爾科夫的穩定性）。
（3）最後通過比較上網者浏覽所有網頁的機率分布，對網頁進行排序。機率越大的網頁，排序越靠前。
--》
--》
如上圖所述，首先作為一個随機的上網者，我們通路ABCD四個網站的機率都是1/4，網站A有分别以1/3的機率跳轉到BCD，以此類推，我們就可以得到狀态狀态轉移矩陣M，其中第1列就表示網站A跳轉到BCD的機率，又因為先假設A不能夠自己跳轉到自己是以A到A的跳轉機率是0。是以經過一次跳轉的結果便是V1,以此類推，我們繼續用M*V1便可以得到第二部跳轉的狀态轉移矩陣。我們就這樣一直在網頁間進行跳轉，由于馬爾科夫的穩定性，我們知道這樣的跳轉最終會導緻收斂，最後的使用者浏覽A,B,C,D的機率分布就為3/9,2/9,2/9,2/9，最後我們按照這個機率分布的大小對網頁進行排序，這就是page rank啦！
但是這個原始的page ranking是存在bug的，也就是會有一些先驗假設:如，1.不能存在某個網頁不跳轉到任何的網頁，也就是上面的terminal point的問題，這會使得最後A,B,C,D的機率分布都為0。2.也不能存在某個網頁自己跳轉到自己，也就是上面的 trap problem的問題，這會使得A,B,C,D的機率在有自己跳轉的網頁上的機率為1，而其他的機率為0。
有沒有什麼方法解決這一問題呢？答案是肯定的。
那就是在狀态轉移方程中加入擾動項，即紅框中的内容。這樣我們就能使浏覽者以一定的機率跳出terminal point和trap problem的問題使得狀态轉移能夠收斂。
流行排序（Manifold ranking）
流行排序出處是Dengyong Zhou的“Ranking on Data Manifolds” NIPS(2003)，其要解決的問題是如何實作如下資料的排序：
其中紅色十字被稱為是問詢點（query），我們想通過問詢問詢點實作對資料的排序，使得資料的排序像(c)圖中展現的那樣，如果我們隻是單純的使用歐氏距離對這些資料點進行排序則會得到圖(b)所示的結果，但是我們希望得到的排序是像圖(c)一樣的排序。這時我們該如何處理呢？
Dengyong Zhou的做法是：
（1）先衡量資料點和問詢點之間，以及這些資料點之間的距離，并将這些點兩兩之間的距離按照升序進行排列，同時将這兩點進行連接配接，重複實作這兩點之間的連接配接直到生成一個連接配接圖。（連接配接圖在下面的圖中會有所展示）。
（2）根據生成的連接配接圖和邊的長度（兩點之間的距離）設定邊的權重，權重的公式是采用的e指數的形式，如上圖2步所示。如果沒有連接配接，即沒有邊，則權重為零。這樣我們就得到了一個權重矩陣W。
（3）用一個對角矩陣D對W進行歸一化處理，D的對角線上的元素是W中所對應的行的元素的加和。
（4）與前面将的改進的page ranking相似，令“浏覽者”在這個圖上進行随機浏覽，也可稱之為疊代傳播，直至收斂。
（5）最後使用收斂後的排序值的大小f*最為最後排序的依據。
可贊的是，作者還給出了收斂性的證明，以及收斂的值。
如上圖3中的結果就是最後收斂的值，但是最後作者還給出了建議，由于直接計算最後收斂的結果在資料很多的情況下是不可行的，是以還是建議大家使用疊代的方式進行計算。
最後給出流行排序的疊代步驟和結果圖。
如上圖1中所示的就是，所生成的連接配接圖。
關于流行排序我就寫到這裡了，僅為了記錄一下我看過的東西，備忘一下，也希望能夠對大家有所幫助。