pageRank 詳細(xì)解析具體例子

1、PageRank解釋方法一1. PageRank的核心思想                                             &

2、#160;                                                (1) R(x)表示x的

3、PageRank，B(x)表示所有指向x的網(wǎng)頁(yè)。      公式(1)的意思是一個(gè)網(wǎng)頁(yè)的重要性等于指向它的所有網(wǎng)頁(yè)的重要性相加之和。粗看之下，公式(1)將核心思想準(zhǔn)確地表達(dá)出來了。但仔細(xì)觀察就會(huì)發(fā)現(xiàn)，公式(1)有一個(gè)缺陷：無論J有多少個(gè)超鏈接，只要J指向I，I都將得到與J一樣的重要性。當(dāng)J有多個(gè)超鏈接時(shí)，這個(gè)思想就會(huì)造成不合理的情況。例如：一個(gè)新開的網(wǎng)站N只有兩個(gè)指向它的超鏈接，一個(gè)來自著名并且歷史悠久的門戶網(wǎng)站F，另一個(gè)來自不為人知的網(wǎng)站U。根據(jù)公式(1)，就會(huì)得到N比F更優(yōu)質(zhì)的結(jié)論。這個(gè)結(jié)論顯然不符合人們的常識(shí)。彌補(bǔ)這個(gè)缺陷的一個(gè)簡(jiǎn)單方法是

4、當(dāng)J有多個(gè)超鏈接（假設(shè)個(gè)數(shù)為N），每個(gè)鏈接得到的重要性為R(j)/N。于是公式(1)就變成公式（2）：                                                                      

5、0;                          （2） N(j)表示j頁(yè)面的超鏈接數(shù) 圖2 來自Lawrence Page的文章     從圖2可以看出，如果要得到N比F更優(yōu)質(zhì)的結(jié)論，就要求N得到很多重要網(wǎng)站的超鏈接或者海量不知名網(wǎng)站的超鏈接。而這是可接受的。因此可以認(rèn)為公式(2)將核心思想準(zhǔn)確地表達(dá)出來了。為了得到標(biāo)準(zhǔn)化的計(jì)算結(jié)果，在公式(2)的基礎(chǔ)上增加一個(gè)常數(shù)C，得到公式(3)：   

6、;                                                                                     

7、0;           (3) 2.  計(jì)算，實(shí)例由公式(3)可知，PageRank是遞歸定義的。換句話就是要得到一個(gè)頁(yè)面的PageRank，就要先知道另一些頁(yè)面的PageRank。因此需要設(shè)置合理的PageRank初始值。不過，如果有辦法得到合理的PageRank初始值，還需要這個(gè)算法嗎？或者說，這個(gè)嚴(yán)重依賴于初始值的算法有什么意義嗎？依賴于合理初始值的PageRank算法是沒意義的，那么不依賴于初始值的PageRank算法就是有意義的了。也就是說，如果存在一種計(jì)算方法，使得無論怎樣設(shè)置初始值，最后都會(huì)收斂到同

8、一個(gè)值就行了。要做到這樣，就要換一個(gè)角度看問題，從線性代數(shù)的角度看問題。將頁(yè)面看作節(jié)點(diǎn)，超鏈接看作有向邊，整個(gè)互聯(lián)網(wǎng)就變成一個(gè)有向圖了。此時(shí)，用鄰接矩陣M表示整個(gè)互聯(lián)網(wǎng)，若第I個(gè)頁(yè)面有存在到第J個(gè)頁(yè)面的超鏈接，那么矩陣元素mij=1，否則mij=0。對(duì)于圖3有矩形M= 0, 1, 1, 0,             0, 0, 0, 1,            1, 0, 0, 0,           

9、1, 1, 1, 0                                                                                 

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

11、0; 0,   1,   0,  0   將R看作是一個(gè)N行1列的矩陣，公式(3)變?yōu)楣剑?）R = C MT R  (4)在公式(4)中，R可以看作MT的特征向量，其對(duì)應(yīng)的特征值為1 / C（看不明白這句話，可以回憶下線性代數(shù)中對(duì)特征向量的定義對(duì)于矩陣A，若存在著列向量X和一個(gè)數(shù)c，使得AX=cX，則X稱為A的特征向量，c稱為A的特征值）。冪法(power method）計(jì)算主特征向量與初始值無關(guān)，因此只要把R看作主特征向量計(jì)算，就可以解決初始值的合理設(shè)置問題。冪法得到的結(jié)果與初始值無關(guān)，是因?yàn)樽罱K都會(huì)收斂到某個(gè)值。因此使用冪法之

12、前，要確保能夠收斂。但是，在互聯(lián)網(wǎng)的超鏈接結(jié)構(gòu)中，一旦出現(xiàn)封閉的情況，就會(huì)使得冪法不能收斂。所謂的封閉是指若干個(gè)網(wǎng)頁(yè)互相指向?qū)Ψ?，但不指向別的網(wǎng)頁(yè)，具體的例子如圖4所示：                                     圖4 來自Soumya Sanyal的PPT上圖4個(gè)綠色網(wǎng)頁(yè)就是封閉情況。這種情況會(huì)使得這些網(wǎng)頁(yè)的PageRank在計(jì)算的時(shí)候不斷地累加，從而使得結(jié)果不能收

13、斂。仔細(xì)研究就會(huì)發(fā)現(xiàn)紅色網(wǎng)頁(yè)的PageRank給了綠色網(wǎng)頁(yè)后，綠色網(wǎng)頁(yè)就將這些PageRank吞掉了。Larry Page將這種情況稱為Rank Sink。如果沿著網(wǎng)頁(yè)的鏈接一直點(diǎn)下去，發(fā)現(xiàn)老是在同樣的幾個(gè)網(wǎng)頁(yè)中徘徊，怎么辦？沒錯(cuò)，把當(dāng)前頁(yè)面關(guān)掉，再開一個(gè)新的網(wǎng)頁(yè)。上述情況正好與Rank Sink類似，也就意味著可以借鑒這個(gè)思想解決Rank Sink。因此，在公式(3)中的基礎(chǔ)上加一個(gè)逃脫因子E，得到：                           

14、                                                                     (5)E(i)表示第i個(gè)網(wǎng)頁(yè)的逃脫因子   將(5)變成矩陣形式，可得：R = C MT&#

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

16、n Ranking Bringing Order to the Web:8090/422/2. 一個(gè)對(duì)PageRank進(jìn)行解釋的PPT，講解得很好: The PageRank Citation Ranking Redone3. 不錯(cuò)的PageRank科普文: Google 的秘密- PageRank 徹底解說 中文版4. 本文所用到的線性代數(shù)相關(guān)知識(shí)pageRank二1 基本思想：       如果網(wǎng)頁(yè)T存在一個(gè)指向網(wǎng)頁(yè)A的連接，則表明T的所有者認(rèn)為A比較重要，從而把T的一部分重要性得

17、分賦予A。這個(gè)重要性得分值為：PR（T）/L(T)    其中PR（T）為T的PageRank值，L(T)為T的出鏈數(shù)        則A的PageRank值為一系列類似于T的頁(yè)面重要性得分值的累加。        即一個(gè)頁(yè)面的得票數(shù)由所有鏈向它的頁(yè)面的重要性來決定，到一個(gè)頁(yè)面的超鏈接相當(dāng)于對(duì)該頁(yè)投一票。一個(gè)頁(yè)面的PageRank是由所有鏈向它的頁(yè)面（鏈入頁(yè)面）的重要性經(jīng)過遞歸算法得到的。一個(gè)有較多鏈入的頁(yè)面會(huì)有較高

18、的等級(jí)，相反如果一個(gè)頁(yè)面沒有任何鏈入頁(yè)面，那么它沒有等級(jí)。2 PageRank簡(jiǎn)單計(jì)算：       假設(shè)一個(gè)由只有4個(gè)頁(yè)面組成的集合：A，B，C和D。如果所有頁(yè)面都鏈向A，那么A的PR（PageRank）值將是B，C及D的和。              繼續(xù)假設(shè)B也有鏈接到C，并且D也有鏈接到包括A的3個(gè)頁(yè)面。一個(gè)頁(yè)面不能投票2次。所以B給每個(gè)頁(yè)面半票。以同樣的邏輯，D投出的票只有三分之一算到了A的Pag

19、eRank上。             換句話說，根據(jù)鏈出總數(shù)平分一個(gè)頁(yè)面的PR值。       例子：        如圖1 所示的例子來說明PageRank的具體計(jì)算過程。             

20、;                        3  修正PageRank計(jì)算公式：         由于存在一些出鏈為0，也就是那些不鏈接任何其他網(wǎng)頁(yè)的網(wǎng)， 也稱為孤立網(wǎng)頁(yè)，使得很多網(wǎng)頁(yè)能被訪問到。因此需要對(duì) PageRank公式進(jìn)行修正，即在簡(jiǎn)單公式的基

21、礎(chǔ)上增加了阻尼系數(shù)（damping factor）q， q一般取值q=0.85。      其意義是，在任意時(shí)刻，用戶到達(dá)某頁(yè)面后并繼續(xù)向后瀏覽的概率。 1- q= 0.15就是用戶停止點(diǎn)擊，隨機(jī)跳到新URL的概率）的算法被用到了所有頁(yè)面上，估算頁(yè)面可能被上網(wǎng)者放入書簽的概率。      最后，即所有這些被換算為一個(gè)百分比再乘上一個(gè)系數(shù)q。由于下面的算法，沒有頁(yè)面的PageRank會(huì)是0。所以，Google通過數(shù)學(xué)系統(tǒng)給了每個(gè)頁(yè)面一個(gè)最小值。  

22、         這個(gè)公式就是.S Brin 和 L. Page 在The Anatomy of a Large- scale Hypertextual Web Search Engine Computer Networks and ISDN Systems 定義的公式。     所以一個(gè)頁(yè)面的PageRank是由其他頁(yè)面的PageRank計(jì)算得到。Google不斷的重復(fù)計(jì)算每個(gè)頁(yè)面的PageRank。如果給每個(gè)頁(yè)面一個(gè)隨機(jī)PageRank值（非0），那么經(jīng)過不斷的重復(fù)計(jì)算，

23、這些頁(yè)面的PR值會(huì)趨向于正常和穩(wěn)定。這就是搜索引擎使用它的原因。 4. PageRank冪法計(jì)算(線性代數(shù)應(yīng)用)4.1 完整公式：關(guān)于這節(jié)內(nèi)容，可以查閱：谷歌背后的數(shù)學(xué)首先求完整的公式：Arvind Arasu 在Junghoo Cho Hector Garcia - Molina, Andreas Paepcke, Sriram Raghavan. Searching the Web 更加準(zhǔn)確的表達(dá)為： 是被研究的頁(yè)面，是鏈入頁(yè)面的數(shù)量，是鏈出頁(yè)面的數(shù)量，而N是所有頁(yè)面的數(shù)量。PageRank值是一個(gè)特殊矩陣中的特征向量。這個(gè)特征向量為： R是如下等式的一個(gè)解：

24、如果網(wǎng)頁(yè)i有指向網(wǎng)頁(yè)j的一個(gè)鏈接，則否則0。4.2 使用冪法求PageRank      那我們PageRank 公式可以轉(zhuǎn)換為求解的值，      其中矩陣為 A = q  × P + ( 1 一 q) *  /N 。 P 為概率轉(zhuǎn)移矩陣，為 n  維的全 1 行. 則 =           冪法計(jì)算過程

25、如下：      X  設(shè)任意一個(gè)初始向量, 即設(shè)置初始每個(gè)網(wǎng)頁(yè)的 PageRank值均。一般為1.     R = AX;     while  (1 )(            if ( l X - R I  <  ) /如果最后兩次的結(jié)果近似或者相

26、同，返回R                  return R;               else                  

27、X =R;               R = AX;             4.3 求解步驟：一、 P概率轉(zhuǎn)移矩陣的計(jì)算過程:        先建立一個(gè)網(wǎng)頁(yè)間的鏈接關(guān)系的模型,即我們需要合適的數(shù)據(jù)結(jié)構(gòu)表示頁(yè)面間的連接關(guān)系。    

28、60; 1) 首先我們使用圖的形式來表述網(wǎng)頁(yè)之間關(guān)系：       現(xiàn)在假設(shè)只有四張網(wǎng)頁(yè)集合：A、B、C，其抽象結(jié)構(gòu)如下圖1：                                  

29、60;  圖1 網(wǎng)頁(yè)間的鏈接關(guān)系      顯然這個(gè)圖是強(qiáng)連通的（從任一節(jié)點(diǎn)出發(fā)都可以到達(dá)另外任何一個(gè)節(jié)點(diǎn)）。      2）我們用矩陣表示連通圖：       用鄰接矩陣 P表示這個(gè)圖中頂點(diǎn)關(guān)系 ，如果頂（頁(yè)面）i向頂點(diǎn)（頁(yè)面）j有鏈接情況 ，則pij   =   1 ，否則pij   =   0 。如圖2所示。如果

30、網(wǎng)頁(yè)文件總數(shù)為N ， 那么這個(gè)網(wǎng)頁(yè)鏈接矩陣就是一個(gè)N x N  的矩 陣 。       3）網(wǎng)頁(yè)鏈接概率矩陣       然后將每一行除以該行非零數(shù)字之和，即（每行非0數(shù)之和就是鏈接網(wǎng)個(gè)數(shù)）則得到新矩陣P，如圖3所示。 這個(gè)矩陣記錄了 每個(gè)網(wǎng)頁(yè)跳轉(zhuǎn)到其他網(wǎng)頁(yè)的概率，即其中i行j列的值表示用戶從頁(yè)面i 轉(zhuǎn)到頁(yè)面j的概率。圖1 中A頁(yè)面鏈向B、C，所以一個(gè)用戶從A跳轉(zhuǎn)到B、C的概率各為1/2。    

31、;  4）概率轉(zhuǎn)移矩陣P       采用P 的轉(zhuǎn)置矩 陣進(jìn)行計(jì)算， 也就是上面提到的概率轉(zhuǎn)移矩陣P 。  如圖4所示：                    圖2  網(wǎng)頁(yè)鏈接矩陣：         

32、                             圖3  網(wǎng)頁(yè)鏈接概率矩陣：                   

33、;          圖4  P 的轉(zhuǎn)置矩 陣 二、 A矩陣計(jì)算過程。      1）P概率轉(zhuǎn)移矩陣  :             2）/N 為：           3）A矩陣為：q  × P + ( 1 一 q) *  /N = 0.85  × P + 0.15  * /N           初始每個(gè)網(wǎng)頁(yè)的 PageRank值均