基于超鏈接分析的排序算法課件

1、基于超鏈接分析的排序算法洪賽2015.1.42022/10/41WME小組:洪賽小組:洪賽搜索引擎排序算法概述超鏈接分析排序算法概述PageRank算法PageRank算法概述從入鏈數(shù)量到 PageRankPageRank算法原理PageRank冪法計算PageRank優(yōu)缺點CONTENTHITS算法Hub頁面與Authority頁面算法基本思想：相互增強關(guān)系HITS算法HITS算法存在的問題HITS算法與PageRank算法比較2022/10/42WME小組:洪賽小組:洪賽搜索引擎排序算法，主要經(jīng)歷了三個階段的發(fā)展歷程：第一階段，主要考慮關(guān)鍵詞因素，統(tǒng)計關(guān)鍵詞在文檔中出現(xiàn)的頻率和關(guān)鍵詞在文檔

2、中出現(xiàn)的位置信息。詞頻位置加權(quán)算法應(yīng)用廣泛，發(fā)展也相對比較成熟，目前這種算法仍然是許多搜索引擎的核心排序算法。這類算法的代表為TF-IDF。第二階段，考慮網(wǎng)頁權(quán)重因素，網(wǎng)頁本身的級別越高，在檢索結(jié)果排序中越靠前。利用超鏈接分析，有效地計算網(wǎng)頁的相關(guān)度與重要度，代表的算法有 PageRank ，HITS等。第三階段，有效利用用戶日志數(shù)據(jù)與統(tǒng)計學(xué)習(xí)方法，使網(wǎng)頁相關(guān)度與重要度計算的精度有了進一步的提升，代表的方法包括排序?qū)W習(xí)、網(wǎng)頁重要度學(xué)習(xí)、匹配學(xué)習(xí)、話題模型學(xué)習(xí)、查詢語句轉(zhuǎn)化學(xué)習(xí)。搜索引擎排序算法概述2022/10/43WME小組:洪賽小組:洪賽超鏈接分析排序算法的思想起源于文獻(xiàn)引文索引機制：一篇

3、文章若被其他文章引用的次數(shù)越多或者被權(quán)威的論文引用，則該文章被認(rèn)為很有價值。超鏈接分析的思想與上述思想極為相似，一個網(wǎng)頁被其他網(wǎng)頁引用的次數(shù)越多，或者被某一權(quán)威的網(wǎng)頁所引用，該網(wǎng)頁就顯得越重要。超鏈接分析排序算法概述2022/10/44WME小組:洪賽小組:洪賽大部分鏈接分析算法建立在兩個概念模型上：隨機漫游模型：針對瀏覽網(wǎng)頁用戶行為建立的抽象概念模型，用戶上網(wǎng)過程中會不斷打開鏈接，在相互有鏈接指向的網(wǎng)頁之間跳轉(zhuǎn)，這是直接跳轉(zhuǎn)，如果某個頁面包含的所有鏈接用戶都不感興趣則可能會在瀏覽器中輸入另外的網(wǎng)址，這是遠(yuǎn)程跳轉(zhuǎn)。該模型就是對一個直接跳轉(zhuǎn)和遠(yuǎn)程跳轉(zhuǎn)兩種用戶瀏覽行為進行抽象的概念模型；典型的使用

4、該模型的算法是PageRank；子集傳播模型：基本思想是把互聯(lián)網(wǎng)網(wǎng)頁按照一定規(guī)則劃分，分為兩個甚至是多個子集合。其中某個子集合具有特殊性質(zhì)，很多算法從這個具有特殊性質(zhì)的子集合出發(fā)，給予子集合內(nèi)網(wǎng)頁初始權(quán)值，之后根據(jù)這個特殊子集合內(nèi)網(wǎng)頁和其他網(wǎng)頁的鏈接關(guān)系，按照一定方式將權(quán)值傳遞到其他網(wǎng)頁。典型的使用該模型的算法有HITS和Hilltop算法。2022/10/45WME小組:洪賽小組:洪賽PageRank，即網(wǎng)頁排名，又稱網(wǎng)頁級別、Google左側(cè)排名或佩奇排名。Google創(chuàng)始人拉里佩奇和謝爾蓋布林于1997年構(gòu)建早期搜索系統(tǒng)原型時提出的鏈接分析算法。目前很多重要的鏈接分析算法都是在PageR

5、ank算法基礎(chǔ)上衍生出來的。PageRank是Google用于用來標(biāo)識網(wǎng)頁的等級/重要性的一種方法。PageRank算法概述2022/10/47WME小組:洪賽小組:洪賽PageRank的級別從0到10級，10級為滿分。PR值越高說明該網(wǎng)頁越受歡迎（越重要）。PR值為7到10則表明這個網(wǎng)站非常受歡迎（或者說極其重要）。一般PR值達(dá)到4，就算是一個不錯的網(wǎng)站了。Google把自己的網(wǎng)站的PR值定到10。2022/10/48WME小組:洪賽小組:洪賽對于某個互聯(lián)網(wǎng)網(wǎng)頁A來說，該網(wǎng)頁PageRank的計算基于以下兩個基本假設(shè)：數(shù)量假設(shè)：在Web圖模型中，如果一個頁面節(jié)點接收到的其他網(wǎng)頁指向的入鏈數(shù)量

6、越多，那么這個頁面越重要。質(zhì)量假設(shè)：指向頁面A的入鏈質(zhì)量不同，質(zhì)量高的頁面會通過鏈接向其他頁面?zhèn)鬟f更多的權(quán)重。所以越是質(zhì)量高的頁面指向頁面A，則頁面A越重要。從入鏈數(shù)量到 PageRank2022/10/410WME小組:洪賽小組:洪賽PageRank的計算充分利用了數(shù)量假設(shè)和質(zhì)量假設(shè)。步驟如下：1）在初始階段：網(wǎng)頁通過鏈接關(guān)系構(gòu)建起Web圖，每個頁面設(shè)置相同的PageRank值，通過若干輪的計算，會得到每個頁面所獲得的最終PageRank值。隨著每一輪的計算進行，網(wǎng)頁當(dāng)前的PageRank值會不斷得到更新。2）在一輪中更新頁面PageRank得分的計算方法：在一輪更新頁面PageRank得分

7、的計算中，每個頁面將其當(dāng)前的PageRank值平均分配到本頁面包含的出鏈上，這樣每個鏈接即獲得了相應(yīng)的權(quán)值。而每個頁面將所有指向本頁面的入鏈所傳入的權(quán)值求和，即可得到新的PageRank得分。當(dāng)每個頁面都獲得了更新后的PageRank值，就完成了一輪PageRank計算。 PageRank算法原理2022/10/411WME小組:洪賽小組:洪賽基本思想：如果網(wǎng)頁T存在一個指向網(wǎng)頁A的連接，則表明T的所有者認(rèn)為A比較重要，從而把T的一部分重要性得分賦予A。這個重要性得分值為：PR（T）/L(T)其中PR（T）為T的PageRank值，L(T)為T的出鏈數(shù);則A的PageRank值為一系列類似于T

8、的頁面重要性得分值的累加。 即一個頁面的得票數(shù)由所有鏈向它的頁面的重要性來決定，到一個頁面的超鏈接相當(dāng)于對該頁投一票。一個頁面的PageRank是由所有鏈向它的頁面（鏈入頁面）的重要性經(jīng)過遞歸算法得到的。一個有較多鏈入的頁面會有較高的等級，相反如果一個頁面沒有任何鏈入頁面，那么它沒有等級。PageRank算法原理2022/10/412WME小組:洪賽小組:洪賽例子：如圖所示的例子來說明PageRank的具體計算過程。PageRank算法原理2022/10/414WME小組:洪賽小組:洪賽修正PageRank計算公式:由于存在一些出鏈為0，也就是那些不鏈接任何其他網(wǎng)頁的網(wǎng)， 也稱為孤立網(wǎng)頁，使得

9、很多網(wǎng)頁能被訪問到。對 PageRank公式進行修正，即在簡單公式的基礎(chǔ)上增加了阻尼系數(shù)（damping factor）q， q一般取值q=0.85。其意義是，在任意時刻，用戶到達(dá)某頁面后并繼續(xù)向后瀏覽的概率。1-q=0.15就是用戶停止點擊，隨機跳到新URL的概率的。 PageRank算法原理2022/10/415WME小組:洪賽小組:洪賽一個頁面的PageRank是由其他頁面的PageRank計算得到。Google不斷的重復(fù)計算每個頁面的PageRank。如果給每個頁面一個隨機PageRank值（非0），那么經(jīng)過不斷的重復(fù)計算，這些頁面的PR值會趨向于正常和穩(wěn)定。要得到一個頁面的PageR

10、ank，得先知道另一些頁面的PageRank。因此需要設(shè)置合理的PageRank初始值。不過，如果有辦法得到合理的PageRank初始值，還需要這個算法嗎？那么有沒有不依賴于初始值的PageRank算法？也就是說，如果存在一種計算方法，使得無論怎樣設(shè)置初始值，最后都會收斂到同一個值就行了。要做到這樣，就要換一個角度看問題，從線性代數(shù)的角度看問題。PageRank算法原理2022/10/417WME小組:洪賽小組:洪賽PageRank冪法計算2022/10/418WME小組:洪賽小組:洪賽PageRank冪法計算2022/10/419WME小組:洪賽小組:洪賽PageRank值是一個PT中的特征

11、向量。這個特征向量為：R是如下等式的一個解：如果網(wǎng)頁i有指向網(wǎng)頁j的一個鏈接，則否則PageRank冪法計算2022/10/420WME小組:洪賽小組:洪賽PageRank冪法計算冪法計算過程如下： X設(shè)任意一個初始向量,即設(shè)置初始每個網(wǎng)頁的PageRank值均。一般為1.R = AX;while (1 )if( lX -R I ) /如果最后兩次的結(jié)果近似或者相同，返回Rreturn R; else X =R;R = AX;2022/10/421WME小組:洪賽小組:洪賽用冪法計算PageRank 值總是收斂的，即計算的次數(shù)是有限的。不論初始值如何選取，這種算法都保證了網(wǎng)頁排名的估計值能收斂

12、到他們的真實值。PageRank冪法計算2022/10/422WME小組:洪賽小組:洪賽HITS(Hyperlink - Induced Topic Search)算法是由康奈爾大學(xué)( Cornell University ) 的Jon Kleinberg 博士于1997 年首先提出的,為IBM 公司阿爾馬登研究中心( IBM Almaden Research Center) 的名為“CLEVER”的研究項目中的一部分。HITS算法是鏈接分析中非?；A(chǔ)且重要的算法，目前已被Teoma搜索引擎（）作為鏈接分析算法在實際中使用。HITS算法2022/10/424WME小組:洪賽小組:洪賽Hub頁面

13、（樞紐頁面）和Authority頁面（權(quán)威頁面）是HITS算法最基本的兩個定義。所謂“Authority”頁面，是指與某個領(lǐng)域或者某個話題相關(guān)的高質(zhì)量網(wǎng)頁，比如搜索引擎領(lǐng)域，Google和百度首頁即該領(lǐng)域的高質(zhì)量網(wǎng)頁，比如視頻領(lǐng)域，優(yōu)酷和土豆首頁即該領(lǐng)域的高質(zhì)量網(wǎng)頁。所謂“Hub”頁面，指的是包含了很多指向高質(zhì)量“Authority”頁面鏈接的網(wǎng)頁，比如hao123首頁可以認(rèn)為是一個典型的高質(zhì)量“Hub”網(wǎng)頁。 HITS算法的目的即是通過一定的技術(shù)手段，在海量網(wǎng)頁中找到與用戶查詢主題相關(guān)的高質(zhì)量“Authority”頁面和“Hub”頁面，尤其是“Authority”頁面，因為這些頁面代表了能夠

14、滿足用戶查詢的高質(zhì)量內(nèi)容，搜索引擎以此作為搜索結(jié)果返回給用戶。Hub頁面與Authority頁面2022/10/425WME小組:洪賽小組:洪賽根集合將查詢q提交給基于關(guān)鍵字查詢的檢索系統(tǒng)，從返回結(jié)果頁面的集合總?cè)∏皀個網(wǎng)頁(如n=200)，作為根集合(root set)，記為root，則root滿足：1).root中的網(wǎng)頁數(shù)量較少2).root中的網(wǎng)頁是與查詢q相關(guān)的網(wǎng)頁3).root中的網(wǎng)頁包含較多的權(quán)威(Authority)網(wǎng)頁HITS算法2022/10/427WME小組:洪賽小組:洪賽擴展集合base在根集root的基礎(chǔ)上，HITS算法對網(wǎng)頁集合進行擴充（參考右圖）集合base擴充原則

15、是：凡是與根集內(nèi)網(wǎng)頁有直接鏈接指向關(guān)系的網(wǎng)頁都被擴充到集合base，無論是有鏈接指向根集內(nèi)頁面，或者是根集頁面有鏈接指向的頁面，都被擴充進入擴展網(wǎng)頁集合base。HITS算法在這個擴充網(wǎng)頁集合內(nèi)尋找好的“Hub”頁面與好的“Authority”頁面。HITS算法2022/10/428WME小組:洪賽小組:洪賽對于“擴充網(wǎng)頁集合”來說，我們并不知道哪些頁面是好的“Hub”或者好的“Authority”頁面，每個網(wǎng)頁都有潛在的可能，所以對于每個頁面都設(shè)立兩個權(quán)值，分別來記載這個頁面是好的Hub或者Authority頁面的可能性。在初始情況下，在沒有更多可利用信息前，每個頁面的這兩個權(quán)值都是相同的，

16、可以都設(shè)置為1。 之后，即可利用上面提到的兩個基本假設(shè)，以及相互增強關(guān)系等原則進行多輪迭代計算，每輪迭代計算更新每個頁面的兩個權(quán)值，直到權(quán)值穩(wěn)定不再發(fā)生明顯的變化為止。HITS算法2022/10/429WME小組:洪賽小組:洪賽右圖給出了迭代計算過程中，某個頁面的Hub權(quán)值和Authority權(quán)值的更新方式。HITS算法假設(shè)以A(i)代表網(wǎng)頁i的Authority權(quán)值，以H(i)代表網(wǎng)頁i的Hub權(quán)值。在右圖所示例子中，“擴充網(wǎng)頁集合”有3個網(wǎng)頁有鏈接指向頁面1，同時頁面1有3個鏈接指向其它頁面。那么，網(wǎng)頁1在此輪迭代中的Authority權(quán)值即為所有指向網(wǎng)頁1頁面的Hub權(quán)值之和；類似的，網(wǎng)

17、頁1的Hub分值即為所指向的頁面的Authority權(quán)值之和。2022/10/430WME小組:洪賽小組:洪賽“擴充網(wǎng)頁集合”內(nèi)其它頁面也以類似的方式對兩個權(quán)值進行更新，當(dāng)每個頁面的權(quán)值都獲得了更新，則完成了一輪迭代計算，此時HITS算法會評估上一輪迭代計算中的權(quán)值和本輪迭代之后權(quán)值的差異，如果發(fā)現(xiàn)總體來說權(quán)值沒有明顯變化，說明系統(tǒng)已進入穩(wěn)定狀態(tài)，則可以結(jié)束計算。將頁面根據(jù)Authority權(quán)值得分由高到低排序，取權(quán)值最高的若干頁面作為響應(yīng)用戶查詢的搜索結(jié)果輸出。如果比較發(fā)現(xiàn)兩輪計算總體權(quán)值差異較大，則繼續(xù)進入下一輪迭代計算，直到整個系統(tǒng)權(quán)值穩(wěn)定為止。HITS算法2022/10/431WME小

18、組:洪賽小組:洪賽HITS算法2022/10/432WME小組:洪賽小組:洪賽 HITS算法整體而言是個效果很好的算法，目前不僅應(yīng)用在搜索引擎領(lǐng)域，而且被“自然語言處理”以及“社交分析”等很多其它計算機領(lǐng)域借鑒使用，并取得了很好的應(yīng)用效果。盡管如此，最初版本的HITS算法仍然存在一些問題，而后續(xù)很多基于HITS算法的鏈接分析方法，也是立足于改進HITS算法存在的這些問題而提出的。HITS算法存在的問題2022/10/433WME小組:洪賽小組:洪賽歸納起來，HITS算法主要在以下幾個方面存在不足：1.計算效率較低：HITS算法是與查詢相關(guān)的算法，必須在接收到用戶查詢后進行計算，并且HITS算法

19、本身需要進行很多輪迭代計算才能獲得最終結(jié)果2.主題漂移問題:如果在擴展網(wǎng)頁集合里包含部分與查詢主題無關(guān)的頁面，且這些頁面之間有較多的相互鏈接指向，那么HITS算法很可能會給予這些無關(guān)網(wǎng)頁很高的排名，導(dǎo)致搜索結(jié)果發(fā)生主題漂移，這種現(xiàn)象被稱為“緊密鏈接社區(qū)現(xiàn)象”（Tightly-Knit Community Effect）。3.易被作弊者操縱結(jié)果:比如作弊者可以建立一個網(wǎng)頁，頁面內(nèi)容增加很多指向高質(zhì)量網(wǎng)頁或者著名網(wǎng)站的網(wǎng)址，這就是一個很好的Hub頁面，之后作弊者再將這個網(wǎng)頁鏈接指向作弊網(wǎng)頁，于是可以提升作弊網(wǎng)頁的Authority得分。4.結(jié)構(gòu)不穩(wěn)定:在原有的“擴充網(wǎng)頁集合”內(nèi)，若添加刪除個別網(wǎng)頁或者改變少數(shù)鏈接關(guān)系，HITS算法的排名結(jié)果就會有非常大的改變。HITS算法存在的問題2022/10/434WME小組:洪賽小組:洪賽 HITS算法和PageRank算法可以說是搜索引擎鏈接分析的兩個最基礎(chǔ)且最重要的算法。然而兩者在基本概念模型、計算思路以及技術(shù)實現(xiàn)細(xì)節(jié)都有很大的不同，下面對兩者之間的差異進行逐一說明。 1.HITS算法是與用戶輸入的查詢請求密切相關(guān)的，而PageRank與查詢請求無關(guān)。所以，HITS算法可以單獨作為相似性計算評價標(biāo)準(zhǔn)，而PageRank必須結(jié)合內(nèi)容相似性計算才可以用來對網(wǎng)頁相關(guān)性進行