第21章 PageRank算法

本文是李航老師的《統(tǒng)計(jì)學(xué)習(xí)方法》一書的代碼復(fù)現(xiàn)。作者：黃海廣

備注：代碼都可以在github中下載。我將陸續(xù)將代碼發(fā)布在公眾號(hào)“機(jī)器學(xué)習(xí)初學(xué)者”，可以在這個(gè)專輯在線閱讀。

PageRank是互聯(lián)網(wǎng)網(wǎng)頁重要度的計(jì)算方法，可以定義推廣到任意有向圖結(jié)點(diǎn)的重要度計(jì)算上。其基本思想是在有向圖上定義隨機(jī)游走模型，即一階馬爾可夫鏈，描述游走者沿著有向圖隨機(jī)訪問各個(gè)結(jié)點(diǎn)的行為，在一定條件下，極限情況訪問每個(gè)結(jié)點(diǎn)的概率收斂到平穩(wěn)分布，這時(shí)各個(gè)結(jié)點(diǎn)的概率值就是其 PageRank值，表示結(jié)點(diǎn)相對重要度。

有向圖上可以定義隨機(jī)游走模型，即一階馬爾可夫鏈，其中結(jié)點(diǎn)表示狀態(tài)，有向邊表示狀態(tài)之間的轉(zhuǎn)移，假設(shè)一個(gè)結(jié)點(diǎn)到連接出的所有結(jié)點(diǎn)的轉(zhuǎn)移概率相等。轉(zhuǎn)移概率由轉(zhuǎn)移矩陣表示

第行第列的元素表示從結(jié)點(diǎn)跳轉(zhuǎn)到結(jié)點(diǎn)的概率。

當(dāng)含有個(gè)結(jié)點(diǎn)的有向圖是強(qiáng)連通且非周期性的有向圖時(shí)，在其基礎(chǔ)上定義的隨機(jī)游走模型，即一階馬爾可夫鏈具有平穩(wěn)分布，平穩(wěn)分布向量稱為這個(gè)有向圖的 PageRank。若矩陣是馬爾可夫鏈的轉(zhuǎn)移矩陣，則向量R滿足

向量的各個(gè)分量稱 PageRank為各個(gè)結(jié)點(diǎn)的值。

其中，表示結(jié)點(diǎn)的 PageRank值。這是 PageRank的基本定義。

PageRank基本定義的條件現(xiàn)實(shí)中往往不能滿足，對其進(jìn)行擴(kuò)展得到 PageRank的一般定義。任意含有個(gè)結(jié)點(diǎn)的有向圖上，可以定義一個(gè)隨機(jī)游走模型，即一階馬爾可夫鏈，轉(zhuǎn)移矩陣由兩部分的線性組合組成，其中一部分按照轉(zhuǎn)移矩陣，從一個(gè)結(jié)點(diǎn)到連接出的所有結(jié)點(diǎn)的轉(zhuǎn)移概率相等，另一部分按照完全隨機(jī)轉(zhuǎn)移矩陣，從任一結(jié)點(diǎn)到任一結(jié)點(diǎn)的轉(zhuǎn)移概率都是。這個(gè)馬爾可夫鏈存在平穩(wěn)分布，平穩(wěn)分布向量R稱為這個(gè)有 PageRank向圖的一般，滿足

其中是阻尼因子，1是所有分量為1的維向量。

PageRank的計(jì)算方法包括迭代算法、冪法、代數(shù)算法。

冪法將 PageRank的等價(jià)式寫成

其中是阻尼因子，是所有元素為1的階方陣。

PageRank算法可以看出是一般轉(zhuǎn)移矩陣的主特征向量，即最大的特征值對應(yīng)的特征向量。 冪法就是一個(gè)計(jì)算矩陣的主特征值和主特征向量的方法。

步驟是：選擇初始向量；計(jì)算一般轉(zhuǎn)移矩陣；進(jìn)行迭代并規(guī)范化向量

直至收斂。

---

在實(shí)際應(yīng)用中許多數(shù)據(jù)都以圖(graph)的形式存在，比如，互聯(lián)網(wǎng)、社交網(wǎng)絡(luò)都可以看作是一個(gè)圖。圖數(shù)據(jù)上的機(jī)器學(xué)習(xí)具有理論與應(yīng)用上的重要意義。pageRank算法是圖的鏈接分析 (link analysis)的代表性算法，屬于圖數(shù)據(jù)上的無監(jiān)督學(xué)習(xí)方法。

pageRank算法最初作為互聯(lián)網(wǎng)網(wǎng)頁重要度的計(jì)算方法，1996年由page和Brin提出，并用于谷歌搜索引擎的網(wǎng)頁排序。事實(shí)上，pageRank可以定義在任意有向圖上，后來被應(yīng)用到社會(huì)影響力分析、文本摘要等多個(gè)問題。

pageRank算法的基本想法是在有向圖上定義一個(gè)隨機(jī)游走模型，即一階馬爾可夫鏈，描述隨機(jī)游走者沿著有向圖隨機(jī)訪問各個(gè)結(jié)點(diǎn)的行為。在一定條件下，極限情況訪問每個(gè)結(jié)點(diǎn)的概率收斂到平穩(wěn)分布， 這時(shí)各個(gè)結(jié)點(diǎn)的平穩(wěn)概率值就是其 pageRank值，表示結(jié)點(diǎn)的重要度。 pageRank是遞歸定義的，pageRank的計(jì)算可以通過迭代算法進(jìn)行。

#https://gist.github.com/diogojc/1338222/84d767a68da711a154778fb1d00e772d65322187import numpy as np from scipy.sparse import csc_matrixdef pageRank(G, s=.85, maxerr=.0001):"""Computes the pagerank for each of the n statesParameters----------G: matrix representing state transitionsGij is a binary value representing a transition from state i to j.s: probability of following a transition. 1-s probability of teleportingto another state.maxerr: if the sum of pageranks between iterations is bellow this we willhave converged."""n = G.shape[0]# transform G into markov matrix AA = csc_matrix(G, dtype=np.float)rsums = np.array(A.sum(1))[:, 0]ri, ci = A.nonzero()A.data /= rsums[ri]# bool array of sink statessink = rsums == 0# Compute pagerank r until we convergero, r = np.zeros(n), np.ones(n)while np.sum(np.abs(r - ro)) > maxerr:ro = r.copy()# calculate each pagerank at a timefor i in range(0, n):# inlinks of state iAi = np.array(A[:, i].todense())[:, 0]# account for sink statesDi = sink / float(n)# account for teleportation to state iEi = np.ones(n) / float(n)r[i] = ro.dot(Ai * s + Di * s + Ei * (1 - s))# return normalized pagerankreturn r / float(sum(r)) # Example extracted from 'Introduction to Information Retrieval' G = np.array([[0,0,1,0,0,0,0],[0,1,1,0,0,0,0],[1,0,1,1,0,0,0],[0,0,0,1,1,0,0],[0,0,0,0,0,0,1],[0,0,0,0,0,1,1],[0,0,0,1,1,0,1]]) print(pageRank(G,s=.86)) [0.12727557 0.03616954 0.12221594 0.22608452 0.28934412 0.036169540.16274076]

---

本章代碼來源：https://github.com/hktxt/Learn-Statistical-Learning-Method

下載地址

https://github.com/fengdu78/lihang-code

參考資料：

[1] 《統(tǒng)計(jì)學(xué)習(xí)方法》: https://baike.baidu.com/item/統(tǒng)計(jì)學(xué)習(xí)方法/10430179

[2] 黃海廣: https://github.com/fengdu78

[3] ?github: https://github.com/fengdu78/lihang-code

[4] ?wzyonggege: https://github.com/wzyonggege/statistical-learning-method

[5] ?WenDesi: https://github.com/WenDesi/lihang_book_algorithm

[6] ?火燙火燙的: https://blog.csdn.net/tudaodiaozhale

[7] ?hktxt: https://github.com/hktxt/Learn-Statistical-Learning-Method

總結(jié)

以上是生活随笔為你收集整理的复现经典：《统计学习方法》第21章 PageRank算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。