統(tǒng)計學(xué)習(xí)方法：第21章 PageRank算法

第二十一章

PageRank算法PageRank算法在實際應(yīng)用中許多數(shù)據(jù)都以圖（graph)的形式存在，比如，互聯(lián)網(wǎng)、社交網(wǎng)絡(luò)都可以看作是一個圖圖數(shù)據(jù)上的機(jī)器學(xué)習(xí)具有理論與應(yīng)用上的重要意義PageRank算法是圖的鏈接分析（linkanalysis）的代表性算法，屬于圖數(shù)據(jù)上的無監(jiān)督學(xué)習(xí)方法。PageRank可以定義在任意有向圖上，后來被應(yīng)用到社會影響力分析、文本摘要等多個問題。PageRank算法PageRank算法的基本想法是在有向圖上定義一個隨機(jī)游走模型，即一階馬爾可夫鏈，描述隨機(jī)游走者沿著有向圖隨機(jī)訪問各個結(jié)點的行為在一定條件下，極限情況訪問每個結(jié)點的概率收斂到平穩(wěn)分布，這時各個結(jié)點的平穩(wěn)概率值就是其PageRank值，表示結(jié)點的重要度。PageRank是遞歸定義的，PageRank的計算可以通過迭代算法進(jìn)行。PageRank的定義基本想法歷史上，PageRank算法作為計算互聯(lián)網(wǎng)網(wǎng)頁重要度的算法被提出PageRank是定義在網(wǎng)頁集合上的一個函數(shù)，它對每個網(wǎng)頁給出一個正實數(shù)，表示網(wǎng)頁的重要程度，整體構(gòu)成一個向量PageRank值越高，網(wǎng)頁就越重要，在互聯(lián)網(wǎng)搜索的排序中可能就被排在前面基本想法假設(shè)互聯(lián)網(wǎng)是一個有向圖，在其基礎(chǔ)上定義隨機(jī)游走模型，即一階馬爾可夫鏈，表示網(wǎng)頁瀏覽者在互聯(lián)網(wǎng)上隨機(jī)瀏覽網(wǎng)頁的過程假設(shè)瀏覽者在每個網(wǎng)頁依照連接出去的超鏈接以等概率跳轉(zhuǎn)到下一個網(wǎng)頁，并在網(wǎng)上持續(xù)不斷進(jìn)行這樣的隨機(jī)跳轉(zhuǎn)，這個過程形成一階馬爾可夫鏈PageRank表示這個馬爾可夫鏈的平穩(wěn)分布每個網(wǎng)頁的PageRank值就是平穩(wěn)概率。基本想法下圖表示一個有向圖，假設(shè)是簡化的互聯(lián)網(wǎng)例，結(jié)點A,B,C和D表示網(wǎng)頁，結(jié)點之間的有向邊表示網(wǎng)頁之間的超鏈接，邊上的權(quán)值表示網(wǎng)頁之間隨機(jī)跳轉(zhuǎn)的概率基本想法假設(shè)有一個瀏覽者，在網(wǎng)上隨機(jī)游走如果瀏覽者在網(wǎng)頁A，則下一步以1/3的概率轉(zhuǎn)移到網(wǎng)頁B,C和D如果瀏覽者在網(wǎng)頁B，則下一步以1/2的概率轉(zhuǎn)移到網(wǎng)頁A和D如果瀏覽者在網(wǎng)頁C，則下一步以概率1轉(zhuǎn)移到網(wǎng)頁A如果瀏覽者在網(wǎng)頁D，則下一步以1/2的概率轉(zhuǎn)移到網(wǎng)頁B和C基本想法直觀上，一個網(wǎng)頁，如果指向該網(wǎng)頁的超鏈接越多，隨機(jī)跳轉(zhuǎn)到該網(wǎng)頁的概率也就越高，該網(wǎng)頁的PageRank值就越高，這個網(wǎng)頁也就越重要一個網(wǎng)頁，如果指向該網(wǎng)頁的PageRank值越高，隨機(jī)跳轉(zhuǎn)到該網(wǎng)頁的概率也就越高，該網(wǎng)頁的PageRank值就越高，這個網(wǎng)頁也就越重要PageRank值依賴于網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，一旦網(wǎng)絡(luò)的拓?fù)洌ㄟB接關(guān)系）確定，PageRank值就確定基本想法PageRank的計算可以在互聯(lián)網(wǎng)的有向圖上進(jìn)行，通常是一個迭代過程先假設(shè)一個初始分布，通過迭代，不斷計算所有網(wǎng)頁的PageRank值，直到收斂為止有向圖從一個結(jié)點出發(fā)到達(dá)另一個結(jié)點，所經(jīng)過的邊的一個序列稱為一條路徑（(path),路徑上邊的個數(shù)稱為路徑的長度如果一個有向圖從其中任何一個結(jié)點出發(fā)可以到達(dá)其他任何一個結(jié)點，就稱這個有向圖是強(qiáng)連通圖（stronglyconnectedgraph)有向圖假設(shè)k是一個大于1的自然數(shù)如果從有向圖的一個結(jié)點出發(fā)返回到這個結(jié)點的路徑的長度都是k的倍數(shù)，那么稱這個結(jié)點為周期性結(jié)點如果一個有向圖不含有周期性結(jié)點，則稱這個有向圖為非周期性圖（aperiodicgraph)，否則為周期性圖有向圖下圖是一個周期性有向圖的例子從結(jié)點A出發(fā)返回到A，必須經(jīng)過路徑A一B一C一A，所有可能的路徑的長度都是3的倍數(shù)，所以結(jié)點A是周期性結(jié)點。這個有向圖是周期性圖隨機(jī)游走模型隨機(jī)游走模型注意轉(zhuǎn)移矩陣具有性質(zhì)即每個元素非負(fù)，每列元素之和為1，即矩陣M為隨機(jī)矩陣（stochasticmatrix)。隨機(jī)游走模型在有向圖上的隨機(jī)游走形成馬爾可夫鏈。也就是說，隨機(jī)游走者每經(jīng)一個單位時間轉(zhuǎn)移一個狀態(tài)如果當(dāng)前時刻在第j個結(jié)點（狀態(tài)），那么下一個時刻在第i個結(jié)點（狀態(tài)）的概率是mij這一概率只依賴于當(dāng)前的狀態(tài)，與過去無關(guān)，具有馬爾可夫性。隨機(jī)游走模型在下圖的有向圖上可以定義隨機(jī)游走模型結(jié)點A到結(jié)點B,C和D存在有向邊，可以以概率1/3從A分別轉(zhuǎn)移到B,C和D，并以概率0轉(zhuǎn)移到A，于是可以寫出轉(zhuǎn)移矩陣的第1列結(jié)點B到結(jié)點A和D存在有向邊，可以以概率1/2從B分別轉(zhuǎn)移到A和D，并以概率0分別轉(zhuǎn)移到B和C，于是可以寫出矩陣的第2列隨機(jī)游走模型于是得到轉(zhuǎn)移矩陣隨機(jī)游走在某個時刻t訪問各個結(jié)點的概率分布就是馬爾可夫鏈在時刻t的狀態(tài)分布，可以用一個n維列向量

Rt

表示，那么在時刻t+1訪問各個結(jié)點的概率分布Rt+1滿足PageRank的基本定義給定一個包含n個結(jié)點的強(qiáng)連通且非周期性的有向圖，在其基礎(chǔ)上定義隨機(jī)游走模型假設(shè)轉(zhuǎn)移矩陣為M，在時刻0,1,2,...,t,…訪問各個結(jié)點的概率分布為則極限

存在極限向量R表示馬爾可夫鏈的平穩(wěn)分布，滿足PageRank的基本定義PageRank的基本定義顯然有M(vi)表示指向結(jié)點vi的結(jié)點集合L(vj)表示結(jié)點vj連出的有向邊的個數(shù)PageRank的基本定義是理想化的，在這中情況下，PageRank存在，而且可以通過不斷迭代求得PageRank值PageRank的基本定義例求下圖的PageRank例轉(zhuǎn)移矩陣取初始分布向量

R0

為例以轉(zhuǎn)移矩陣M連乘初始向量

R0

得到向量序列最后得到極限向量

即有向圖的PageRank值一般的有向圖未必滿足強(qiáng)連通且非周期性的條件。所以PageRank的基本定義不適用。例下圖的有向圖的轉(zhuǎn)移矩陣M是例這時M不是一個隨機(jī)矩陣，因為隨機(jī)矩陣要求每一列的元素之和是1，這里第3列的和是0，不是1如果仍然計算在各個時刻的各個結(jié)點的概率分布，就會得到如下結(jié)果可以看到，隨著時間推移，訪問各個結(jié)點的概率皆變?yōu)?PageRank的一般定義PageRank一般定義的想法是在基本定義的基礎(chǔ)上導(dǎo)入平滑項給定一個含有n個結(jié)點vi,i=1,2,…,n，的任意有向圖假設(shè)考慮一個在圖上隨機(jī)游走模型，即一階馬爾可夫鏈，其轉(zhuǎn)移矩陣是M，從一個結(jié)點到其連出的所有結(jié)點的轉(zhuǎn)移概率相等。PageRank的一般定義這個馬爾可夫鏈未必具有平穩(wěn)分布假設(shè)考慮另一個完全隨機(jī)游走的模型，其轉(zhuǎn)移矩陣的元素全部為1/n，也就是說從任意一個結(jié)點到任意一個結(jié)點的轉(zhuǎn)移概率都是1/n兩個轉(zhuǎn)移矩陣的線性組合又構(gòu)成一個新的轉(zhuǎn)移矩陣，在其上可以定義一個新的馬爾可夫鏈。PageRank的一般定義容易證明這個馬爾可夫鏈一定具有平穩(wěn)分布，且平穩(wěn)分布滿足式中d(0≤d≤1）是系數(shù)，稱為阻尼因子（dampingfactor)R是n維向量

是所有分量為1的n維向量R表示的就是有向圖的一般PageRank

表示結(jié)點vi的PageRank值PageRank的一般定義式（21.10）中第一項表示（狀態(tài)分布是平穩(wěn)分布時）依照轉(zhuǎn)移矩陣M訪問各個結(jié)點的概率，第二項表示完全隨機(jī)訪問各個結(jié)點的概率阻尼因子d取值由經(jīng)驗決定例如d=0.85。當(dāng)d接近1時，隨機(jī)游走主要依照轉(zhuǎn)移矩陣M進(jìn)行當(dāng)d接近0時，隨機(jī)游走主要以等概率隨機(jī)訪問各個結(jié)點。PageRank的一般定義可以由式（21.10)寫出每個結(jié)點的PageRank，這是一般PageRank的定義第二項稱為平滑項，由于采用平滑項，所有結(jié)點的PageRank值都不會為0，具有以下性質(zhì)：PageRank的一般定義PageRank的一般定義一般PageRank的定義意味著互聯(lián)網(wǎng)瀏覽者，按照以下方法在網(wǎng)上隨機(jī)游走：在任意一個網(wǎng)頁上，瀏覽者或者以概率d決定按照超鏈接隨機(jī)跳轉(zhuǎn)，這時以等概率從連接出去的超鏈接跳轉(zhuǎn)到下一個網(wǎng)頁或者以概率（1-d)決定完全隨機(jī)跳轉(zhuǎn)，這時以等概率1/n跳轉(zhuǎn)到任意一個網(wǎng)頁第二個機(jī)制保證從沒有連接出去的超鏈接的網(wǎng)頁也可以跳轉(zhuǎn)出。這樣可以保證平穩(wěn)分布，即一般PageRank的存在，因而一般PageRank適用于任何結(jié)構(gòu)的網(wǎng)絡(luò)。PageRank的計算迭代算法給定一個含有n個結(jié)點的有向圖，轉(zhuǎn)移矩陣為M，有向圖的一般PageRank由迭代公式的極限向量R確定PageRank的迭代算法，就是按照這個一般定義進(jìn)行迭代，直至收斂PageRank的迭代算法例圖中所示的有向圖，取d=0.8，求圖的PageRank例可得轉(zhuǎn)移矩陣為

按照式（21.15）計算例迭代公式為令初始向量例進(jìn)行迭代……例最后得到計算結(jié)果表明，結(jié)點C的PageRank值超過一半，其他結(jié)點也有相應(yīng)的PageRank值。冪法冪法（(powermethod)是一個常用的PageRank計算方法，通過近似計算矩陣的主特征值和主特征向量求得有向圖的一般PageRank冪法主要用于近似計算矩陣的主特征值（dominanteigenvalue）和主特征向量（dominanteigenvector)主特征值是指絕對值最大的特征值主特征向量是其對應(yīng)的特征向量注意特征向量不是唯一的，只是其方向是確定的，乘上任意系數(shù)還是特征向量冪法假設(shè)要求n階矩陣A的主特征值和主特征向量，采用下面的步驟。首先，任取一個初始。維向量xo，構(gòu)造如下的一個n維向量序列然后，假設(shè)矩陣A有n個特征值，按照絕對值大小排列對應(yīng)的n個線性無關(guān)的特征向量為這n個特征向量構(gòu)成n維空間的一組基。冪法于是，可以將初始向量

x0

表示為

的線性組合得到冪法接著，假設(shè)矩陣A的主特征值

是特征方程的單根，由上式得由于

，當(dāng)k充分大時有這里

是當(dāng)

時的無窮小量，

。即冪法說明當(dāng)k充分大時向量

xk

與特征向量

v1

只相差一個系數(shù)。由式（21.18)知，于是主特征值

可表示為其中xk,j和xk+1,j分別是xk和xk+1的第j個分量冪法在實際計算時，為了避免出現(xiàn)絕對值過大或過小的情況，通常在每步迭代后即進(jìn)行規(guī)范化，將向量除以其范數(shù)，即這里的范數(shù)是向量的無窮范數(shù)，即向量各分量的絕對值的最大值冪法現(xiàn)在回到計算一般PageRank。轉(zhuǎn)移矩陣可以寫作其中d是阻尼因子E是所有元素為1的n階方陣根據(jù)Perron-Frobenius定理，一般PageRank的向量R是矩陣A的主特征向量，主特征值是1所以可以使用冪法近似計算一般PageRank計算一般PageRank的冪法例給定一個如圖所示的有向圖，取d=0.85，求有向圖的一般PageRank。