PageRank算法解析.ppt

《PageRank算法解析.ppt》由会员分享，可在线阅读，更多相关《PageRank算法解析.ppt（54页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第六章 排序（PageRank）,王海,目錄,背景介紹Google的網頁排序PageRank簡化模型PageRank的計算PageRank存在的問題,Google查詢過程,Google 查詢的全過程通常不超過半秒時間，但在這短短的時間內需要完成多個步驟，然後才能將搜索結果交付給搜索資訊的使用者。,PageRank?,PageRank的提出Google的創始人之一Larry Page於1998年提出了PageRank，並應用在Google搜尋引擎的檢索結果排序上，該技術也是Google早期的核心技術之一Larry Page是Google的創始首席執行官，2001年4月轉任現職產品總裁。他目前仍與

2、Eric Schmidt和Sergey Brin一起共同負責 Google的日常運作。他在斯坦福大學攻讀計算機科學博士學位期間，遇到了Sergey Brin，他們於1998年合夥創立Google。,目錄,背景介紹Google的網頁排序PageRank簡化模型PageRank的計算PageRank存在的問題,Google的網頁排序,在Google中搜索“體育新聞”,Google的網頁排序,在Google中搜索“體育新聞”搜尋引擎工作的簡要過程如下針對查詢詞“體育新聞”進行分詞“體育”、“新聞”根據建立的倒排索引，將同時包含“體育”和“新聞”的文檔返回，並根據相關性進行排序這裡的相關性主要是基於內

3、容的相關性但是會有一些垃圾網頁，雖然也包含大量的查詢詞，但卻並非滿足使用者需要的文檔，如下圖，一個網頁中雖然出現了四次“體育新聞”但卻不是使用者所需要的因此，頁面本身的重要性在網頁排序中也起著很重要的作用,查詢詞和文檔的相關性,Google的網頁排序,在Google中搜索“體育新聞”,Google的網頁排序,如何度量網頁本身的重要性呢？ 互聯網上的每一篇HTML文檔除了包含文本、圖片、視頻等資訊外，還包含了大量的鏈接關係，利用這些鏈接關係，能夠發現某些重要的網頁直觀地看，某網頁A鏈向網頁B，則可以認為網頁A覺得網頁B有鏈接價值，是比較重要的網頁。 某網頁被指向的次數越多，則它的重要性越高；越是

4、重要的網頁，所鏈接的網頁的重要性也越高。,A,B,網頁是節點，網頁間的鏈接關係是邊,Google的網頁排序,如何度量網頁本身的重要性呢？比如，新華網體育在其首頁中對新浪體育做了鏈接，人民網體育同樣在其首頁中對新浪體育做了鏈接可見，新浪體育被鏈接的次數較多；同時，人民網體育和新華網體育也都是比較“重要”的網頁，因此新浪體育也應該是比較“重要”的網頁。,新華網體育,人民網體育,Google的網頁排序,一個更加形象的圖,鏈向網頁E的鏈接遠遠多於鏈向網頁C的鏈接，但是網頁C的重要性卻大於網頁E。這是因為因為網頁C被網頁B所鏈接，而網頁B有很高的重要性。,HTTP網頁鏈接示意圖,目錄,背景介紹Googl

5、e的網頁排序PageRank簡化模型PageRank的計算PageRank存在的問題,什麼是PageRankPageRank是一種在搜尋引擎中根據網頁之間相互的鏈接關係計算網頁排名的技術。 PageRank是Google用來標識網頁的等級或重要性的一種方法。其級別從1到10級，PR值越高說明該網頁越受歡迎（越重要）。 PageRank近似於一個用戶，是指在Internet上隨機地按一下鏈接將會到達特定網頁的可能性。通常，能夠從更多地方到達的網頁更為重要，因此具有更高的PageRank。如果要查看此網站PageRank值，請安裝GOOGLE工具條並啟用PageRank特性，或者在Firefox安

6、裝SearchStatus外掛程式。,PageRank演算法原理：,PageRank 的核心思想,PageRank 是基於從許多優質的網頁鏈接過來的網頁，必定還是優質網頁的回歸關係，來判定所有網頁的重要性。,鏈入鏈接數 (單純的意義上的受歡迎度指標) 鏈入鏈接是否來自推薦度高的頁面 (有根據的受歡迎指標) 鏈入鏈接源頁面的鏈接數 (被選中的幾率指標),因此，如果從類似於 Yahoo! 那樣的 PageRank 非常高的網站被鏈接的話，僅此網頁的 PageRank 也會一下子上升；相反地，無論有少鏈入鏈接數，如果全都是從那些沒有多大意義的頁面鏈接過來的話，PageRank 也不會輕易上升。,Pa

7、geRank簡單計算：,假設一個由只有4個頁面組成的集合：A，B，C和D。如果所有頁面都鏈向A，那麼A的PR（PageRank）值將是B，C及D的和。 繼續假設B也有鏈接到C，並且D也有鏈接到包括A的3個頁面。一個頁面不能投票2次。所以B給每個頁面半票。以同樣的邏輯，D投出的票只有三分之一算到了A的PageRank上。 換句話說，根據鏈出總數平分一個頁面的PR值。,PageRank的簡單計算過程,PR：0.1,PR：0.09,PR：0.08,PR：0.08,PR：0.03,0.05,0.05,0.03,0.03,0.03,PageRank的簡化模型,可以把互聯網上的各網頁之間的鏈接關係看成一個

8、有向圖。假設衝浪者瀏覽的下一個網頁鏈接來自於當前網頁。建立簡化模型：對於任意網頁Pi，它的PageRank值可表示為如下：其中Bi為所有鏈接到網頁i的網頁集合，Lj為網頁j的對外鏈接數（出度）。,PRi：網頁i的PageRank值PRj：網頁j的PageRank值Lj：網頁j鏈出的連接數Bi：鏈接到網頁i的網頁集合,目錄,背景介紹Google的網頁排序PageRank簡化模型PageRank的計算PageRank存在的問題,PageRank的計算,互聯網是一個有向圖;每一個網頁是圖的一個頂點;網頁間的每一個超鏈接是圖的一個有向邊;用鄰接矩陣來表示圖，即：定義鄰接矩陣為G，若網頁j到網頁i有超鏈

9、接，則gij=1；反之gij=0;顯然，如果網頁有N個，則矩陣為NN 的0、1方陣。,矩陣化PageRank問題,多個網頁相互鏈接的圖對應的鄰接矩陣G（這裡將0,1值用二值圖像顯示，黑色代表0，白色代表1）,PageRank的計算,定義鄰接矩陣為G，若網頁j到網頁i有超鏈接，則 ；反之， 。記矩陣G的列和、行和分別是cj，ri分別給出了頁面j的鏈出鏈接數目和鏈入鏈接數目,PageRank的計算,假設我們在上網的時侯瀏覽頁面並選擇下一個頁面，這個過程與過去瀏覽過哪些頁面無關，而僅依賴於當前所在的頁面，那麼這一選擇過程可以認為是一個有限狀態、離散時間的隨機過程，其狀態轉移規律用Markov鏈描述。

10、定義轉移概率矩陣,PageRank的計算,根據Markov鏈的基本性質，對於正則Markov鏈，存在平穩分佈 ，滿足 x表示在極限狀態（轉移次數趨於無限）下各網頁被訪問的概率分佈。x定義為網頁的PageRank向量，xi表示第i個網頁的PageRank值,求矩陣A的特徵值1對應的特徵向量x,PageRank的計算：具體方法,x定義為網頁的PageRank向量，xi表示第i個網頁的PageRank值 直接求解：求矩陣A的特徵值1對應的特徵向量冪迭代法：給定x0，xk+1=Axk,例：假設世界上只有七張網頁，依次編號為ID=17，其抽象結構如下圖：,網頁鏈接圖的鄰接矩陣,0 1 1 0 1 1 0

11、 1 0 1 1 0 0 0 1 0 0 1 1 0 0 1 0 0 0 1 0 0 1 0 0 1 0 1 1 0 0 0 0 1 0 0 1 0 0 0 0 0 0,G =,狀態轉移概率矩陣A,0 11/20 1/41/2 01/501/2 1/3 0 0 01/50 0 1/3 1/4 0 01/50 0 0 1/4 0 01/50 0 1/3 0 1/21 0 0 0 0 1/4 0 01/50 0 0 0 0 0,A =,PageRank的計算-直接求解,0.6994565338373890.3828604185215180.3239588156720540.242969111754

12、0400.4123112199462510.1030778049865630.139891306767478,0.3035143769968050.1661341853035140.1405750798722040.1054313099041530.1789137380191690.04472843450479230.0607028753993610,求矩陣A特徵值1對應的特徵向量x,歸一化,PageRank的計算-冪迭代求解,1/71/71/71/71/71/7 1/7,0.321428570.147619050.111904760.064285710.290476190.035714290

13、.02857143,0.303310470.166277790.140563450.105344470.179159360.044610650.06073381,0.303514570.166134160.140575020.105431220.178913820.044728450.06070277,x0,x1,x10,x20,0.3035143769968050.1661341853035140.1405750798722040.1054313099041530.1789137380191690.0447284345047920.060702875399361,直接法 x =,7個網頁的P

14、ageRank值,PageRank結果的評價,將 PageRank 的評價按順序排列(PageRank小數點3位四捨五入):,頁面之間相互關係及狀態轉移圖,R實戰-PageRank,#構建鄰接矩陣adjacencyMatrix-function(pages) n-max(apply(pages,2,max) A - matrix(0,n,n) for(i in 1:nrow(pages) Apagesi,$dist,pagesi,$src-1 A#變換概率矩陣probabilityMatrix-function(G) cs - colSums(G) cscs=0 - 1 n - nrow(G)

15、 A - matrix(0,nrow(G),ncol(G) for (i in 1:n) Ai, - Ai, + Gi,/cs A,#遞迴計算矩陣特徵值eigenMatrix-function(G,iter=100) iter-10 n-nrow(G) x - rep(1,n) for (i in 1:iter) x - G %*% x x/sum(x)src=c(1,1,1,1,1,2,3,3,4,4,4,5,5,5,5,6,6,7)dist=c(2,3,4,5,7,1,1,2,2,3,5,1,3,4,6,1,5,5)pages=data.frame(src,dist)A-adjacency

16、Matrix(pages)G-probabilityMatrix(A)q-eigenMatrix(G,100),PageRank結果的評價,讓我們詳細地看一下。ID=1 的頁面的PageRank 是0.304，佔據全體的三分之一，成為了第1位。特別需要說明的是，起到相當大效果的是從排在第3位的 ID=2 頁面中得到了所有的PageRank (0.166) 數。ID=2頁面有從3個地方過來的鏈入鏈接，而只有面向 ID=1頁面的一個鏈接，因此(面向ID=1頁面的)鏈接就得到ID=2的所有的PageRank數。不過，就因為ID=1頁面是鏈出鏈接和鏈入鏈接最多的頁面，也可以理解它是最受歡迎的頁面。,P

17、ageRank結果的評價,反過來，最後一名的 ID=6 頁面只有 ID=1 的15的微弱評價。 總之，即使有同樣的鏈入鏈接的數目，鏈接源頁面評價的高低也影響 PageRank 的高低。,目錄,背景介紹Google的網頁排序PageRank簡化模型PageRank的計算PageRank存在的問題,簡化模型面臨的缺陷 實際的網路超鏈接環境沒有這麼理想化，PageRank會面臨兩個問題：Rank LeakRank Sink,Rank Leak（表重新計算）,Rank Leak：一個獨立的網頁如果沒有外出的鏈接就產生等級洩漏,處理Rank Leak的方法一,迭代拿掉圖中的Dead Ends節點及Dea

18、d Ends節點相關的邊（之所以迭代拿掉是因為當目前的Dead Ends被拿掉後，可能會出現一批新的Dead Ends），直到圖中沒有Dead Ends。對剩下部分計算PageRank，然後以拿掉Dead Ends逆向順序反推Dead Ends的PageRank。,以左圖為例，首先拿到D和D相關的邊，D被拿到後，C就變成了一個新的Dead Ends，於是拿掉C，最終只剩A、B。此時可很容易算出A、B的PageRank均為1/2。然後我們需要反推Dead Ends的PageRank，最後被拿掉的是C，可以看到C前置節點有A和B，而A和B的出度分別為3和2，因此C的PageRank為：1/2 *

19、1/3 + 1/2 * 1/2 = 5/12；最後，D的PageRank為：1/2 * 1/3 + 5/12 * 1 = 7/12。所以最終的PageRank為（1/2, 1/2, 5/12, 7/12）。,Rank Sink,Rank Sink：整個網頁圖中的一組緊密鏈接成環的網頁如果沒有外出的鏈接就產生Rank Sink。如果對這個圖進行計算，會發現D的PageRank越來越大（趨近於1），而其他節點PageRank）值越來越小（趨近於零）。,1,0,0,0,n次迭代,PageRank的隨機瀏覽模型,假定一個上網者從一個隨機的網頁開始瀏覽，上網者不中斷點擊當前網頁的鏈接開始下一次瀏覽。但是

20、，上網者最終厭倦了，開始了一個隨機的網頁。隨機上網者用以上方式訪問一個新網頁的概率就等於這個網頁PageRank值。 這種隨機模型更加接近於使用者的瀏覽行為； 一定程度上解決了Rank Leak和Rank Sink的問題； 保證PageRank具有唯一值。,隨機瀏覽模型的圖表示,設定任意兩個頂點之間都有直接通路，在每個頂點處以概率按原來藍色方向轉移，以概率1-按紅色方向轉移。,隨機瀏覽模型的鄰接表表示,由於網頁數目巨大，網頁之間的連接關係的鄰接矩陣是一個很大的疏鬆陣列,採用鄰接表來表示網頁之間的連接關係.隨機瀏覽模型的PageRank公式： N: 網路中網頁總數 : 阻尼因數，通常設為0.85

21、，即按照超鏈接進行瀏覽的概率； 1-：隨機跳轉一個新網頁的概率 e：N維單位向量 一個頁面的PageRank是由其他頁面的PageRank計算到。Google不斷的重複計算每個頁面的PageRank。如果給每個頁面一個隨機PageRank值（非0），由於等式PR=A*PR滿足瑪律可夫鏈的性質，如果瑪律可夫鏈收斂，則PR存在唯一解.通過迭代計算得到所有節點的PageRank值。那麼經過不斷的重複計算，這些頁面的PR值會趨向於正常和穩定。,瑪律可夫鏈收斂定理,例：,如果按這個公式迭代算下去，會發現Rank Sink的效應被抑制了，從而每個頁面都擁有一個合理的PageRank。,同樣方法是否可以解決

22、Rank Leak問題？,R實戰-PageRank,#構建鄰接矩陣adjacencyMatrix-function(pages) n-max(apply(pages,2,max) A - matrix(0,n,n) for(i in 1:nrow(pages) Apagesi,$dist,pagesi,$src-1 A#變換概率矩陣,考慮d的情況dProbabilityMatrix-function(G,d=0.85) cs - colSums(G) cscs=0 - 1 n - nrow(G) delta - (1-d)/n A - matrix(delta,nrow(G),ncol(G)

23、for (i in 1:n) Ai, - Ai, + d*Gi,/cs A,#遞迴計算矩陣特徵值eigenMatrix-function(G,iter=100) iter-10 n-nrow(G) x - rep(1,n) for (i in 1:iter) x - G %*% x x/sum(x)src=c(1,1,1,1,1,2,3,3,4,4,4,5,5,5,5,6,6,7)dist=c(2,3,4,5,7,1,1,2,2,3,5,1,3,4,6,1,5,5)pages=data.frame(src,dist)A-adjacencyMatrix(pages)G-probabilityMa

24、trix(A)q-eigenMatrix(G,100),改進,Larry Page和Sergey Brin 兩人從理論上證明了不論初始值如何選取，這種演算法都保證了網頁排名的估計值能收斂到他們的真實值。由於互聯網上網頁的數量是巨大的，上面提到的二維矩陣從理論上講有網頁數目平方之多個元素。如果我們假定有十億個網頁，那麼這個矩陣 就有一百億億個元素。這樣大的矩陣相乘，計算量是非常大的。Larry Page和Sergey Brin兩人利用疏鬆陣列計算的技巧，大大的簡化了計算量。,PageRank數值計算難點（一）,電腦容量限制 假設 N 是 104的 order。通常，數值計算程式內部行列和向量是用

25、雙精度記錄的，N 次正方行列 A 的記憶領域為 sizeof(double)* N * N =8 *104* 104800MB。N 如果變成 105或106的話，就變成80GB, 8TB。這樣的話不用說記憶體就連硬碟也已經很困難了。目前，Google處理著80億以上的頁面，很顯然，已知的這種做法已經完全不適用了。,PageRank數值計算難點（二）,收斂問題特徵向量的求解，就是求解方程Ax=x，是 N 元一次方程組，一般地不能得到分析解，所以只能解其數值。然而，常用的迭代求解方法會導致收斂速度很慢。,PageRank演算法的應用,學術論文的重要性排序學術論文的作者的重要性排序某作者引用了其他作

26、者的文獻，則該作者認為其他作者是“重要”的。網路爬蟲(Web Crawler)可以利用PR值，決定某個URL，所需要抓取的網頁數量和深度重要性高的網頁抓取的頁面數量相對多一些，反之，則少一些關鍵字與句子的抽取（節點與邊）,PageRank小結,優點： 是一個與查詢無關的靜態演算法，所有網頁的PageRank值通過離線計算獲得；有效減少線上查詢時的計算量，極大降低了查詢回應時間。PageRank的缺點過分相信鏈接關係一些權威網頁往往是相互不鏈接的，比如新浪、搜狐、網易以及騰訊這些大的門戶之間，基本是不相互鏈接的，學術領域也是這樣。1）人們的查詢具有主題特徵，PageRank忽略了主題相關性，導致結果的相關性和主題性降低 2）舊的頁面等級會比新頁面高。因為即使是非常好的新頁面也不會有很多上游鏈接，除非它是某個網站的子網站。排序技術是搜尋引擎的絕密Google目前所使用的排序技術，已經不再是簡單的PageRank,謝謝大家!,