pangrank算法

1、1. 前言這系列的文章主要講述2006年評出的數據挖掘10大算法（見圖1）。文章的重點將偏向于算法的來源以及算法的主要思想，不涉及具體的實現。如果發(fā)現文中有錯，希望各位指出來，一起討論。                                 

2、0;                     圖1 來自IDMer的文章    在這些算法中，最引人注目的自然是Google的核心技術之一PageRank。因此本系列就先來探索PageRank的誕生過程。 2. 核心思想    常言道，看一個人怎樣，看他有什么朋友就知道了。也就是說，一個人有著越多牛X朋友的人，他是牛X

3、的概率就越大。將這個知識遷移到網頁上就是“被越多優(yōu)質的網頁所指的網頁，它是優(yōu)質的概率就越大”。PageRank的核心思想就是上述簡單卻有效的觀點。由這個思想，可以得到一個直觀的公式：                                   

4、;                                                  

5、;          (1)R(x)表示x的PageRank，B(x)表示所有指向x的網頁。      公式(1)的意思是一個網頁的重要性等于指向它的所有網頁的重要性相加之和。粗看之下，公式(1)將核心思想準確地表達出來了。但仔細觀察就會發(fā)現，公式(1)有一個缺陷：無論J有多少個超鏈接，只要J指向I，I都將得到與J一樣的重要性。當J有多個超鏈接時，這個思想就會造成不合理的情況。例如：一個新開的網站N只有兩個指向它的超鏈接，一個來自著名并且歷史悠久的門戶網站

6、F，另一個來自不為人知的網站U。根據公式(1)，就會得到N比F更優(yōu)質的結論。這個結論顯然不符合人們的常識。彌補這個缺陷的一個簡單方法是當J有多個超鏈接（假設個數為N），每個鏈接得到的重要性為R(j)/N。于是公式(1)就變成：                                                     

7、;                                            (2)N(j)表示j頁面的超鏈接數                                  

8、0;                                          圖2 來自Lawrence Page的文章     從圖2可以看出，如果要得到N比F更優(yōu)質的結論，就要求N得到很多重要網站的超鏈接或者海量不知名網站的超鏈接。而這是可接受的。因此可以認為公式(2)將核心思想準確地表達出來了。為了得到標準化的計算結果，在

9、公式(2)的基礎上增加一個常數C，得到公式(3)：                                                                              &#

10、160;                     (3) 3. 計算由公式(3)可知，PageRank是遞歸定義的。換句話就是要得到一個頁面的PageRank，就要先知道另一些頁面的PageRank。因此需要設置合理的PageRank初始值。不過，如果有辦法得到合理的PageRank初始值，還需要這個算法嗎？或者說，這個嚴重依賴于初始值的算法有什么意義嗎？依賴于合理初始值的PageRank算法是沒意義的，那么不依賴于初始值的PageRank算法就是有意義的了。也就是

11、說，如果存在一種計算方法，使得無論怎樣設置初始值，最后都會收斂到同一個值就行了。要做到這樣，就要換一個角度看問題，從線性代數的角度看問題。將頁面看作節(jié)點，超鏈接看作有向邊，整個互聯網就變成一個有向圖了。此時，用鄰接矩陣M表示整個互聯網，若第I個頁面有存在到第J個頁面的超鏈接，那么矩陣元素mij=1，否則mij=0。對于圖3有矩形M= 0, 1, 1, 0,             0, 0, 0, 1,            1, 0, 0, 0,  &#

12、160;         1, 1, 1, 0                                                                        

13、            圖3觀察矩陣M可發(fā)現，M的第I行表示第I個網頁指向的網頁，M的第J列表示指向J的網頁。如果將M的每個元素都除于所在行的全部元素之和，然后再將M轉置（交換行和列），得到MT。MT的每一行的全部元素之和不就正好是公式(3)中的 嗎？例如圖3可以得到這樣的矩陣：MT= 0,   0,  1, 1/3,        1/2, 0,  0, 1/3,       1/2,  0,  

14、;0, 1/3,        0,   1,   0,  0   將R看作是一個N行1列的矩陣，公式(3)變?yōu)镽 = C MT R  (4)在公式(4)中，R可以看作MT的特征向量，其對應的特征值為1 / C（看不明白這句話，可以回憶下線性代數中對特征向量的定義對于矩陣A，若存在著列向量X和一個數c，使得AX=cX，則X稱為A的特征向量，c稱為A的特征值）。冪法(power method）計算主特征向量與初始值無關，因此只要把R看作主特征向量計算，就可以解決初始值的合理設置問題。冪法得到的結果

15、與初始值無關，是因為最終都會收斂到某個值。因此使用冪法之前，要確保能夠收斂。但是，在互聯網的超鏈接結構中，一旦出現封閉的情況，就會使得冪法不能收斂。所謂的封閉是指若干個網頁互相指向對方，但不指向別的網頁，具體的例子如圖4所示：                                     圖4 來自Soumya Sanyal的PPT上圖4個綠色網頁就是封閉情況。這種情況會使得這些網頁的P

16、ageRank在計算的時候不斷地累加，從而使得結果不能收斂。仔細研究就會發(fā)現紅色網頁的PageRank給了綠色網頁后，綠色網頁就將這些PageRank吞掉了。Larry Page將這種情況稱為Rank Sink。如果沿著網頁的鏈接一直點下去，發(fā)現老是在同樣的幾個網頁中徘徊，怎么辦？沒錯，把當前頁面關掉，再開一個新的網頁。上述情況正好與Rank Sink類似，也就意味著可以借鑒這個思想解決Rank Sink。因此，在公式(3)中的基礎上加一個逃脫因子E，得到：                   

17、                                                                             (5)E(i)表示第i個網頁的逃脫因子 

18、60; 將(5)變成矩陣形式，可得：R = C MT R + CE = C( MT R + E )其中列向量R的1范數(即R的全部矩陣元素相加)為1將上式重寫為R = C( MT + E * 1 ) R (6)1是指一行N列的行向量，且每個元素都是1   在公式(6)中，只要將R看作(MT + E * 1)的特征向量，就可以同時解決初始值設置問題和封閉的情況。 4. 資料共享   找資料是簡單的事，但要找到好資料就不那么容易了。因此，這一小節(jié)是分享我找到的一些比較好的資料。1. PageRank

19、之父的文章: The PageRank Citation Ranking Bringing Order to the Web:8090/422/2. 一個對PageRank進行解釋的PPT，講解得很好: The PageRank Citation Ranking Redone3. 不錯的PageRank科普文: Google 的秘密- PageRank 徹底解說 中文版4. 本文所用到的線性代數相關知識/Books/LA/eigen/PageRank算法分類： 搜索引擎Search Engine&

20、#160;數據結構與算法2012-09-21 17:02 26967人閱讀 評論(10) 收藏 舉報目錄(?)+1. PageRank算法概述         PageRank,即網頁排名，又稱網頁級別、Google左側排名或佩奇排名。        是Google創(chuàng)始人拉里·佩奇和謝爾蓋·布林于1997年構建早期的搜索系統(tǒng)原型時提出的鏈接分析算法，自從Google在商業(yè)上獲得空前的成功

21、后，該算法也成為其他搜索引擎和學術界十分關注的計算模型。目前很多重要的鏈接分析算法都是在PageRank算法基礎上衍生出來的。PageRank是Google用于用來標識網頁的等級/重要性的一種方法，是Google用來衡量一個網站的好壞的唯一標準。在揉合了諸如Title標識和Keywords標識等所有其它因素之后，Google通過PageRank來調整結果，使那些更具“等級/重要性”的網頁在搜索結果中另網站排名獲得提升，從而提高搜索結果的相關性和質量。其級別從0到10級，10級為滿分。PR值越高說明該網頁越受歡迎（越重要）。例如：一個PR值為1的網站表明這個網站不太具有流行度，而PR值為7到10

22、則表明這個網站非常受歡迎（或者說極其重要）。一般PR值達到4，就算是一個不錯的網站了。Google把自己的網站的PR值定到10，這說明Google這個網站是非常受歡迎的，也可以說這個網站非常重要。 2. 從入鏈數量到 PageRank        在PageRank提出之前，已經有研究者提出利用網頁的入鏈數量來進行鏈接分析計算，這種入鏈方法假設一個網頁的入鏈越多，則該網頁越重要。早期的很多搜索引擎也采納了入鏈數量作為鏈接分析方法，對于搜索引擎效果提升也有較明顯的效果。 PageRank除了考慮到入鏈數量的影響，還

23、參考了網頁質量因素，兩者相結合獲得了更好的網頁重要性評價標準。對于某個互聯網網頁A來說，該網頁PageRank的計算基于以下兩個基本假設：     l 數量假設：在Web圖模型中，如果一個頁面節(jié)點接收到的其他網頁指向的入鏈數量越多，那么這個頁面越重要。    l 質量假設：指向頁面A的入鏈質量不同，質量高的頁面會通過鏈接向其他頁面?zhèn)鬟f更多的權重。所以越是質量高的頁面指向頁面A，則頁面A越重要。       利用以上兩個假設，P

24、ageRank算法剛開始賦予每個網頁相同的重要性得分，通過迭代遞歸計算來更新每個頁面節(jié)點的PageRank得分，直到得分穩(wěn)定為止。 PageRank計算得出的結果是網頁的重要性評價，這和用戶輸入的查詢是沒有任何關系的，即算法是主題無關的。假設有一個搜索引擎，其相似度計算函數不考慮內容相似因素，完全采用PageRank來進行排序，那么這個搜索引擎的表現是什么樣子的呢？這個搜索引擎對于任意不同的查詢請求，返回的結果都是相同的，即返回PageRank值最高的頁面。 3. PageRank算法原理      PageRank的計算充分利用了兩

25、個假設：數量假設和質量假設。步驟如下：      1）在初始階段：網頁通過鏈接關系構建起Web圖，每個頁面設置相同的PageRank值，通過若干輪的計算，會得到每個頁面所獲得的最終PageRank值。隨著每一輪的計算進行，網頁當前的PageRank值會不斷得到更新。      2）在一輪中更新頁面PageRank得分的計算方法：在一輪更新頁面PageRank得分的計算中，每個頁面將其當前的PageRank值平均分配到本頁面包含的出鏈上，這樣每個鏈接即獲得了相應的權值。而每個頁

26、面將所有指向本頁面的入鏈所傳入的權值求和，即可得到新的PageRank得分。當每個頁面都獲得了更新后的PageRank值，就完成了一輪PageRank計算。  3.2 基本思想：       如果網頁T存在一個指向網頁A的連接，則表明T的所有者認為A比較重要，從而把T的一部分重要性得分賦予A。這個重要性得分值為：PR（T）/L(T)    其中PR（T）為T的PageRank值，L(T)為T的出鏈數        則

27、A的PageRank值為一系列類似于T的頁面重要性得分值的累加。        即一個頁面的得票數由所有鏈向它的頁面的重要性來決定，到一個頁面的超鏈接相當于對該頁投一票。一個頁面的PageRank是由所有鏈向它的頁面（鏈入頁面）的重要性經過遞歸算法得到的。一個有較多鏈入的頁面會有較高的等級，相反如果一個頁面沒有任何鏈入頁面，那么它沒有等級。3.3 PageRank簡單計算：       假設一個由只有4個頁面組成的集合：A，B，C和D。如果所有頁面都鏈向A

28、，那么A的PR（PageRank）值將是B，C及D的和。              繼續(xù)假設B也有鏈接到C，并且D也有鏈接到包括A的3個頁面。一個頁面不能投票2次。所以B給每個頁面半票。以同樣的邏輯，D投出的票只有三分之一算到了A的PageRank上。             換句話說，根據鏈出總數平分一個頁面的PR值。  &#

29、160;    例子：        如圖1 所示的例子來說明PageRank的具體計算過程。                                &

30、#160;    3.4  修正PageRank計算公式：         由于存在一些出鏈為0，也就是那些不鏈接任何其他網頁的網， 也稱為孤立網頁，使得很多網頁能被訪問到。因此需要對 PageRank公式進行修正，即在簡單公式的基礎上增加了阻尼系數（damping factor）q， q一般取值q=0.85。      其意義是，在任意時刻，用戶到達某頁面后并繼續(xù)向后瀏覽的概率。 1-

31、 q= 0.15就是用戶停止點擊，隨機跳到新URL的概率）的算法被用到了所有頁面上，估算頁面可能被上網者放入書簽的概率。      最后，即所有這些被換算為一個百分比再乘上一個系數q。由于下面的算法，沒有頁面的PageRank會是0。所以，Google通過數學系統(tǒng)給了每個頁面一個最小值。           這個公式就是.S Brin 和 L. Page 在The Anatomy of a Large- scale Hypertextu

32、al Web Search Engine Computer Networks and ISDN Systems 定義的公式。     所以一個頁面的PageRank是由其他頁面的PageRank計算得到。Google不斷的重復計算每個頁面的PageRank。如果給每個頁面一個隨機PageRank值（非0），那么經過不斷的重復計算，這些頁面的PR值會趨向于正常和穩(wěn)定。這就是搜索引擎使用它的原因。 4. PageRank冪法計算(線性代數應用)4.1 完整公式：關于這節(jié)內容，可以查閱：谷歌背后的數學首先求完整的公式：Arvind Arasu 在Ju

33、nghoo Cho Hector Garcia - Molina, Andreas Paepcke, Sriram Raghavan. Searching the Web 更加準確的表達為： 是被研究的頁面，是鏈入頁面的數量，是鏈出頁面的數量，而N是所有頁面的數量。PageRank值是一個特殊矩陣中的特征向量。這個特征向量為： R是如下等式的一個解：如果網頁i有指向網頁j的一個鏈接，則否則0。4.2 使用冪法求PageRank      那我們PageRank 公式可以轉換為求解的值，   &#

34、160;  其中矩陣為 A = q  × P + ( 1 一 q) *  /N 。 P 為概率轉移矩陣，為 n  維的全 1 行. 則 =           冪法計算過程如下：      X  設任意一個初始向量, 即設置初始每個網頁的 PageRank值均。一般為1.    

35、 R = AX;     while  (1 )(            if ( l X - R I  <  ) /如果最后兩次的結果近似或者相同，返回R                  return R;&#

36、160;              else                   X =R;               R = AX;   

37、;          4.3 求解步驟：一、 P概率轉移矩陣的計算過程:        先建立一個網頁間的鏈接關系的模型,即我們需要合適的數據結構表示頁面間的連接關系。      1) 首先我們使用圖的形式來表述網頁之間關系：       現在假設只有四張網頁集合：A、B、C，其抽象結構如下圖1：   

38、60;                                         圖1 網頁間的鏈接關系      顯然這個

39、圖是強連通的（從任一節(jié)點出發(fā)都可以到達另外任何一個節(jié)點）。      2）我們用矩陣表示連通圖：       用鄰接矩陣 P表示這個圖中頂點關系 ，如果頂（頁面）i向頂點（頁面）j有鏈接情況 ，則pij   =   1 ，否則pij   =   0 。如圖2所示。如果網頁文件總數為N ， 那么這個網頁鏈接矩陣就是一個N x N  的矩 陣 。   

40、    3）網頁鏈接概率矩陣       然后將每一行除以該行非零數字之和，即（每行非0數之和就是鏈接網個數）則得到新矩陣P，如圖3所示。 這個矩陣記錄了 每個網頁跳轉到其他網頁的概率，即其中i行j列的值表示用戶從頁面i 轉到頁面j的概率。圖1 中A頁面鏈向B、C，所以一個用戶從A跳轉到B、C的概率各為1/2。      4）概率轉移矩陣P       采用P 的轉置

41、矩 陣進行計算， 也就是上面提到的概率轉移矩陣P 。  如圖4所示：                         圖2  網頁鏈接矩陣：               

42、                       圖3  網頁鏈接概率矩陣：                         

43、;    圖4  P 的轉置矩 陣 二、 A矩陣計算過程。      1）P概率轉移矩陣  :             2）/N 為：           3）A矩陣為：q  × P + ( 1 一 q) *