1、PageRank算法介紹,李鵬飛 2013.4.28,Google服務(wù)器,Google工作電腦,Google爬蟲,網(wǎng)頁,Google存儲系統(tǒng),搜索引擎示意,目錄,Google的網(wǎng)頁排序 PageRank算法求解 PageRank算法的應(yīng)用 小結(jié),Google的網(wǎng)頁排序,在Google中搜索“體育新聞”,Google的網(wǎng)頁排序,在Google中搜索“體育新聞” 搜索引擎工作的簡要過程如下 針對查詢詞“體育新聞”進行分詞“體育”、“新聞” 根據(jù)建立的倒排索引，將同時包含“體育”和“新聞”的文檔返回，并根據(jù)相關(guān)性進行排序 這里的相關(guān)性主要是基于內(nèi)容的相關(guān)性 但是會有一些垃圾網(wǎng)頁，雖然也包含大量的查詢

2、詞，但卻并非滿足用戶需要的文檔，如下圖，一個網(wǎng)頁中雖然出現(xiàn)了四次“體育新聞”但卻不是用戶所需要的 因此，頁面本身的重要性在網(wǎng)頁排序中也起著很重要的作用,查詢詞和文檔的相關(guān)性,Google的網(wǎng)頁排序,在Google中搜索“體育新聞”,Google的網(wǎng)頁排序,如何度量網(wǎng)頁本身的重要性呢？ 互聯(lián)網(wǎng)上的每一篇html文檔除了包含文本、圖片、視頻等信息外，還包含了大量的鏈接關(guān)系，利用這些鏈接關(guān)系，能夠發(fā)現(xiàn)某些重要的網(wǎng)頁 直觀地看，某網(wǎng)頁A鏈向網(wǎng)頁B，則可以認為網(wǎng)頁A覺得網(wǎng)頁B有鏈接價值，是比較重要的網(wǎng)頁。 某網(wǎng)頁被指向的次數(shù)越多，則它的重要性越高；越是重要的網(wǎng)頁，所鏈接的網(wǎng)頁的重要性也越高。,A,B,網(wǎng)

3、頁是節(jié)點，網(wǎng)頁 間的鏈接關(guān)系是邊,Google的網(wǎng)頁排序,如何度量網(wǎng)頁本身的重要性呢？ 比如，新華網(wǎng)體育在其首頁中對新浪體育做了鏈接，人民網(wǎng)體育同樣在其首頁中對新浪體育做了鏈接 可見，新浪體育被鏈接的次數(shù)較多；同時，人民網(wǎng)體育和新華網(wǎng)體育也都是比較“重要”的網(wǎng)頁，因此新浪體育也應(yīng)該是比較“重要”的網(wǎng)頁。,新華網(wǎng)體育,人民網(wǎng)體育,Google的網(wǎng)頁排序,一個更加形象的圖,鏈向網(wǎng)頁E的鏈接遠遠大于鏈向網(wǎng)頁C的鏈接，但是網(wǎng)頁C的重要性卻大于網(wǎng)頁E。這是因為因為網(wǎng)頁C被網(wǎng)頁B所鏈接，而網(wǎng)頁B有很高的重要性。,Pagerank算法簡介,創(chuàng)始人：拉里佩奇(Larry Page ) Google創(chuàng)始人之一

4、應(yīng)用： 是Google用來衡量 一個網(wǎng)站的好壞的唯 一標(biāo)準(zhǔn)。,Google的網(wǎng)頁排序,PageRank的提出 Google的創(chuàng)始人之一Larry Page于1998年提出了PageRank，并應(yīng)用在Google搜索引擎的檢索結(jié)果排序上，該技術(shù)也是Google早期的核心技術(shù)之一 Larry Page是Google的創(chuàng)始首席執(zhí)行官，2001年4月轉(zhuǎn)任現(xiàn)職產(chǎn)品總裁。他目前仍與Eric Schmidt和Sergey Brin一起共同負責(zé) Google的日常運作。他在斯坦福大學(xué)攻讀計算機科學(xué)博士學(xué)位期間，遇到了Sergey Brin，他們于1998年合伙創(chuàng)立Google。,Pagerank算法原理：,G

5、oogle的網(wǎng)頁排序,網(wǎng)頁的PageRank值 PR值：取值0-10 Google工具欄 9 8 ,Pagerank算法相關(guān)概念,PR值：用來評價網(wǎng)頁的重要性，PR值越大越重要，其級別從0到10級。一般PR值達到4，就算是一個不錯的網(wǎng)站了。Google把自己的網(wǎng)站的PR值定到10，這說明Google這個網(wǎng)站是非常受歡迎的，也可以說這個網(wǎng)站非常重要。 阻尼因數(shù)：(damping factor)其值為0.85 阻尼系數(shù)d定義為用戶不斷隨機點擊鏈接的概率，所以，它取決于點擊的次數(shù)，被設(shè)定為0-1之間。d的值越高，繼續(xù)點擊鏈接的概率就越大。因此，用戶停止點擊并隨機沖浪至另一頁面的概率在式子中用常數(shù)(1

6、-d)表示。無論入站鏈接如何，隨機沖浪至一個頁面的概率總是(1-d)。(1-d)本身也就是頁面本身所具有的PageRank值。,Pagerank核心思想,PageRank通過網(wǎng)絡(luò)浩瀚的超鏈接關(guān)系來確定一個頁面的等級。Google把從A頁面到B頁面的鏈接解釋為A頁面給B頁面投票，Google根據(jù)投票來源（甚至來源的來源，即鏈接到A頁面的頁面）和投票目標(biāo)的等級來決定新的等級。這樣，PageRank會根據(jù)網(wǎng)頁B所收到的投票數(shù)量來評估該網(wǎng)頁的重要性。此外，PageRank還會評估每個投票網(wǎng)頁的重要性，因為某些重要網(wǎng)頁的投票被認為具有較高的價值，這樣，它所鏈接的網(wǎng)頁就能獲得較高的價值。這就是PageRa

7、nk的核心思想，當(dāng)然PageRank算法的實際實現(xiàn)上要復(fù)雜很多。,PageRank簡單計算：,假設(shè)一個由只有4個頁面組成的集合：A，B，C和D。如果所有頁面都鏈向A，那么A的PR（PageRank）值將是B，C及D的和。 繼續(xù)假設(shè)B也有鏈接到C，并且D也有鏈接到包括A的3個頁面。一個頁面不能投票2次。所以B給每個頁面半票。以同樣的邏輯，D投出的票只有三分之一算到了A的PageRank上。 換句話說，根據(jù)鏈出總數(shù)平分一個頁面的PR值。,如圖1 所示的例子來說明PageRank的具體計算過程。,PR值計算公式：,PR(A)= (1-d)/N+d(PR(t1)/C(t1)+.+PR(tn)/C(tn

8、) N: 網(wǎng)絡(luò)中網(wǎng)頁總數(shù) d: 阻尼因數(shù) PR(x):網(wǎng)頁x的PR值 C(tn)：網(wǎng)頁tn的鏈出網(wǎng)頁數(shù) 一個頁面的PageRank是由其他頁面的PageRank計算得到。Google不斷的重復(fù)計算每個頁面的PageRank。如果給每個頁面一個隨機PageRank值（非0），那么經(jīng)過不斷的重復(fù)計算，這些頁面的PR值會趨向于正常和穩(wěn)定。這就是搜索引擎使用它的原因。,PR值的取決因素：,鏈入網(wǎng)頁數(shù) 鏈入網(wǎng)頁的質(zhì)量 鏈入網(wǎng)頁的鏈出網(wǎng)頁數(shù),PageRank值是一個特殊矩陣中的特征向量。這個特征向量為：,PR值的計算（1）,PR(A)= (1-d)/n+d(PR(t1)/C(t1)+.+PR(tn)/C(

9、tn),PR值的計算（2）,(1-d)/n+d(PR(t1)/C(t1)+.+PR(tn)/C(tn),2.2 使用冪法求PageRank,冪法計算過程如下：X 設(shè)任意一個初始向量, 即設(shè)置初始每個網(wǎng)頁的 PageRank值均。一般為1. R = AX; while (1 )( if ( l X - R I e) /如果最后兩次的結(jié)果近似或者相同，返回R return R; else X =R; R = AX; ,一、 P概率轉(zhuǎn)移矩陣的計算過程: 先建立一個網(wǎng)頁間的鏈接關(guān)系的模型,即我們需要合適的數(shù)據(jù)結(jié)構(gòu)表示頁面間的連接關(guān)系。 1) 首先我們使用圖的形式來表述網(wǎng)頁之間關(guān)系： 現(xiàn)在假設(shè)只有四張網(wǎng)

10、頁集合：A、B、C，其抽象結(jié)構(gòu)如下圖1：,2.3 求解步驟：,2）我們用矩陣表示連通圖： 用鄰接矩陣 P表示這個圖中頂點關(guān)系 ，如果頂（頁面）i向頂點（頁面）j有鏈接情況 ，則pij = 1 ，否則pij = 0 。如圖2所示。如果網(wǎng)頁文件總數(shù)為N ， 那么這個網(wǎng)頁鏈接矩陣就是一個N x N 的矩 陣 。 3）網(wǎng)頁鏈接概率矩陣 然后將每一行除以該行非零數(shù)字之和，即（每行非0數(shù)之和就是鏈接網(wǎng)個數(shù)）則得到新矩陣P，如圖3所示。 這個矩陣記錄了 每個網(wǎng)頁跳轉(zhuǎn)到其他網(wǎng)頁的概率，即其中i行j列的值表示用戶從頁面i 轉(zhuǎn)到頁面j的概率。圖1 中A頁面鏈向B、C，所以一個用戶從A跳轉(zhuǎn)到B、C的概率各為1/2。

11、 4）概率轉(zhuǎn)移矩陣P 采用P 的轉(zhuǎn)置矩 陣進行計算， 也就是上面提到的概率轉(zhuǎn)移矩陣P 。 如圖4所示：,2.3 求解步驟：,2.4 A矩陣計算過程。,2.5 循環(huán)迭代計算PageRank的過程,2.6 改 進,Larry Page和Sergey Brin 兩人從理論上證明了不論初始值如何選取，這種算法都保證了網(wǎng)頁排名的估計值能收斂到他們的真實值。 由于互聯(lián)網(wǎng)上網(wǎng)頁的數(shù)量是巨大的，上面提到的二維矩陣從理論上講有網(wǎng)頁數(shù)目平方之多個元素。如果我們假定有十億個網(wǎng)頁，那么這個矩陣 就有一百億億個元素。這樣大的矩陣相乘，計算量是非常大的。Larry Page和Sergey Brin兩人利用稀疏矩陣計算的技

12、巧，大大的簡化了計算量。,PageRank的計算舉例,鏈接源I D 鏈接目標(biāo) ID 1 2,3 ,4,5, 7 2 1 3 1,2 4 2,3,5 5 1,3,4,6 6 1,5 7 5,3 PageRank算法的應(yīng)用,學(xué)術(shù)論文的重要性排序 學(xué)術(shù)論文的作者的重要性排序 某作者引用了其它作者的文獻，則該作者認為其它作者是“重要”的。 網(wǎng)絡(luò)爬蟲(Web Crawler) 可以利用PR值，決定某個URL，所需要抓取的網(wǎng)頁數(shù)量和深度 重要性高的網(wǎng)頁抓取的頁面數(shù)量相對多一些，反之，則少一些 關(guān)鍵詞與句子的抽?。ü?jié)點與邊）,小結(jié),優(yōu)點： 是一個與查詢無關(guān)的靜態(tài)算法，所有網(wǎng)頁的PageRank值通過離線計算獲得；有效減少在線查詢時的計算量，極大降低了查詢響應(yīng)時間。 PageRank的缺點 過分相信鏈接關(guān)系 一些權(quán)威網(wǎng)頁往往是相互不鏈接的，比