您好,登錄后才能下訂單哦!
pagerank算法怎么理解,相信很多沒有經(jīng)驗(yàn)的人對(duì)此束手無策,為此本文總結(jié)了問題出現(xiàn)的原因和解決方法,通過這篇文章希望你能解決這個(gè)問題。
1. PageRank算法概述
PageRank,即網(wǎng)頁(yè)排名,又稱網(wǎng)頁(yè)級(jí)別、Google左側(cè)排名或佩奇排名。
是Google創(chuàng)始人拉里·佩奇和謝爾蓋·布林于1997年構(gòu)建早期的搜索系統(tǒng)原型時(shí)提出的鏈接分析算法,自從Google在商業(yè)上獲得空前的成功后,該算法也成為其他搜索引擎和學(xué)術(shù)界十分關(guān)注的計(jì)算模型。目前很多重要的鏈接分析算法都是在PageRank算法基礎(chǔ)上衍生出來的。PageRank是Google用于用來標(biāo)識(shí)網(wǎng)頁(yè)的等級(jí)/重要性的一種方法,是Google用來衡量一個(gè)網(wǎng)站的好壞的唯一標(biāo)準(zhǔn)。在揉合了諸如Title標(biāo)識(shí)和Keywords標(biāo)識(shí)等所有其它因素之后,Google通過PageRank來調(diào)整結(jié)果,使那些更具“等級(jí)/重要性”的網(wǎng)頁(yè)在搜索結(jié)果中另網(wǎng)站排名獲得提升,從而提高搜索結(jié)果的相關(guān)性和質(zhì)量。其級(jí)別從0到10級(jí),10級(jí)為滿分。PR值越高說明該網(wǎng)頁(yè)越受歡迎(越重要)。例如:一個(gè)PR值為1的網(wǎng)站表明這個(gè)網(wǎng)站不太具有流行度,而PR值為7到10則表明這個(gè)網(wǎng)站非常受歡迎(或者說極其重要)。一般PR值達(dá)到4,就算是一個(gè)不錯(cuò)的網(wǎng)站了。Google把自己的網(wǎng)站的PR值定到10,這說明Google這個(gè)網(wǎng)站是非常受歡迎的,也可以說這個(gè)網(wǎng)站非常重要。
在PageRank提出之前,已經(jīng)有研究者提出利用網(wǎng)頁(yè)的入鏈數(shù)量來進(jìn)行鏈接分析計(jì)算,這種入鏈方法假設(shè)一個(gè)網(wǎng)頁(yè)的入鏈越多,則該網(wǎng)頁(yè)越重要。早期的很多搜索引擎也采納了入鏈數(shù)量作為鏈接分析方法,對(duì)于搜索引擎效果提升也有較明顯的效果。 PageRank除了考慮到入鏈數(shù)量的影響,還參考了網(wǎng)頁(yè)質(zhì)量因素,兩者相結(jié)合獲得了更好的網(wǎng)頁(yè)重要性評(píng)價(jià)標(biāo)準(zhǔn)。
對(duì)于某個(gè)互聯(lián)網(wǎng)網(wǎng)頁(yè)A來說,該網(wǎng)頁(yè)P(yáng)ageRank的計(jì)算基于以下兩個(gè)基本假設(shè):
? 數(shù)量假設(shè):在Web圖模型中,如果一個(gè)頁(yè)面節(jié)點(diǎn)接收到的其他網(wǎng)頁(yè)指向的入鏈數(shù)量越多,那么這個(gè)頁(yè)面越重要。
? 質(zhì)量假設(shè):指向頁(yè)面A的入鏈質(zhì)量不同,質(zhì)量高的頁(yè)面會(huì)通過鏈接向其他頁(yè)面?zhèn)鬟f更多的權(quán)重。所以越是質(zhì)量高的頁(yè)面指向頁(yè)面A,則頁(yè)面A越重要。
利用以上兩個(gè)假設(shè),PageRank算法剛開始賦予每個(gè)網(wǎng)頁(yè)相同的重要性得分,通過迭代遞歸計(jì)算來更新每個(gè)頁(yè)面節(jié)點(diǎn)的PageRank得分,直到得分穩(wěn)定為止。 PageRank計(jì)算得出的結(jié)果是網(wǎng)頁(yè)的重要性評(píng)價(jià),這和用戶輸入的查詢是沒有任何關(guān)系的,即算法是主題無關(guān)的。假設(shè)有一個(gè)搜索引擎,其相似度計(jì)算函數(shù)不考慮內(nèi)容相似因素,完全采用PageRank來進(jìn)行排序,那么這個(gè)搜索引擎的表現(xiàn)是什么樣子的呢?這個(gè)搜索引擎對(duì)于任意不同的查詢請(qǐng)求,返回的結(jié)果都是相同的,即返回PageRank值最高的頁(yè)面。
PageRank的計(jì)算充分利用了兩個(gè)假設(shè):數(shù)量假設(shè)和質(zhì)量假設(shè)。步驟如下:
1)在初始階段:網(wǎng)頁(yè)通過鏈接關(guān)系構(gòu)建起Web圖,每個(gè)頁(yè)面設(shè)置相同的PageRank值,通過若干輪的計(jì)算,會(huì)得到每個(gè)頁(yè)面所獲得的最終PageRank值。隨著每一輪的計(jì)算進(jìn)行,網(wǎng)頁(yè)當(dāng)前的PageRank值會(huì)不斷得到更新。
2)在一輪中更新頁(yè)面PageRank得分的計(jì)算方法:在一輪更新頁(yè)面PageRank得分的計(jì)算中,每個(gè)頁(yè)面將其當(dāng)前的PageRank值平均分配到本頁(yè)面包含的出鏈上,這樣每個(gè)鏈接即獲得了相應(yīng)的權(quán)值。而每個(gè)頁(yè)面將所有指向本頁(yè)面的入鏈所傳入的權(quán)值求和,即可得到新的PageRank得分。當(dāng)每個(gè)頁(yè)面都獲得了更新后的PageRank值,就完成了一輪PageRank計(jì)算。
3.2 基本思想:
如果網(wǎng)頁(yè)T存在一個(gè)指向網(wǎng)頁(yè)A的連接,則表明T的所有者認(rèn)為A比較重要,從而把T的一部分重要性得分賦予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ì)有較高的等級(jí),相反如果一個(gè)頁(yè)面沒有任何鏈入頁(yè)面,那么它沒有等級(jí)。
3.3 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的PageRank上。
例子:
如圖1 所示的例子來說明PageRank的具體計(jì)算過程。
這個(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ì)算,這些頁(yè)面的PR值會(huì)趨向于正常和穩(wěn)定。這就是搜索引擎使用它的原因。
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è)特征向量為:
如果網(wǎng)頁(yè)i有指向網(wǎng)頁(yè)j的一個(gè)鏈接,則
=0。
4.2 使用冪法求PageRank
那我們PageRank 公式可以轉(zhuǎn)換為求解 /N 。 P 為概率轉(zhuǎn)移矩陣,=
) { //如果最后兩次的結(jié)果近似或者相同,返回R
return R;
} else {
X =R;
R = AX;
}
}
4.3 求解步驟:
一、 P概率轉(zhuǎn)移矩陣的計(jì)算過程:
先建立一個(gè)網(wǎng)頁(yè)間的鏈接關(guān)系的模型,即我們需要合適的數(shù)據(jù)結(jié)構(gòu)表示頁(yè)面間的連接關(guān)系。
1) 首先我們使用圖的形式來表述網(wǎng)頁(yè)之間關(guān)系:
現(xiàn)在假設(shè)只有四張網(wǎng)頁(yè)集合:A、B、C,其抽象結(jié)構(gòu)如下圖1:
圖2 網(wǎng)頁(yè)鏈接矩陣: 圖3 網(wǎng)頁(yè)鏈接概率矩陣:
圖4 P’ 的轉(zhuǎn)置矩 陣
二、 A矩陣計(jì)算過程。
1)P概率轉(zhuǎn)移矩陣 :
/N 為:
/N = 0.85 × P + 0.15 *
初始每個(gè)網(wǎng)頁(yè)的 PageRank值均為1 , 即X~t = ( 1 , 1 , 1 ) 。
三、 循環(huán)迭代計(jì)算PageRank的過程
第一步:
繼續(xù)迭代這個(gè)過程...
直到最后兩次的結(jié)果近似或者相同,即R最終收斂,R 約等于X,此時(shí)計(jì)算停止。最終的R 就是各個(gè)頁(yè)面的 PageRank 值。
用冪法計(jì)算PageRank 值總是收斂的,即計(jì)算的次數(shù)是有限的。
Larry Page和Sergey Brin 兩人從理論上證明了不論初始值如何選取,這種算法都保證了網(wǎng)頁(yè)排名的估計(jì)值能收斂到他們的真實(shí)值。
由于互聯(lián)網(wǎng)上網(wǎng)頁(yè)的數(shù)量是巨大的,上面提到的二維矩陣從理論上講有網(wǎng)頁(yè)數(shù)目平方之多個(gè)元素。如果我們假定有十億個(gè)網(wǎng)頁(yè),那么這個(gè)矩陣 就有一百億億個(gè)元素。這樣大的矩陣相乘,計(jì)算量是非常大的。Larry Page和Sergey Brin兩人利用稀疏矩陣計(jì)算的技巧,大大的簡(jiǎn)化了計(jì)算量。
優(yōu)點(diǎn):
是一個(gè)與查詢無關(guān)的靜態(tài)算法,所有網(wǎng)頁(yè)的PageRank值通過離線計(jì)算獲得;有效減少在線查詢時(shí)的計(jì)算量,極大降低了查詢響應(yīng)時(shí)間。
缺點(diǎn):
1)人們的查詢具有主題特征,PageRank忽略了主題相關(guān)性,導(dǎo)致結(jié)果的相關(guān)性和主題性降低
2)舊的頁(yè)面等級(jí)會(huì)比新頁(yè)面高。因?yàn)榧词故欠浅:玫男马?yè)面也不會(huì)有很多上游鏈接,除非它是某個(gè)站點(diǎn)的子站點(diǎn)。
看完上述內(nèi)容,你們掌握pagerank算法怎么理解的方法了嗎?如果還想學(xué)到更多技能或想了解更多相關(guān)內(nèi)容,歡迎關(guān)注億速云行業(yè)資訊頻道,感謝各位的閱讀!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。