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

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

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

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

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

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

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

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

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

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

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

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

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

13、（樞紐頁面）和Authority頁面（權(quán)威頁面）是HITS算法最基本的兩個(gè)定義。所謂“Authority”頁面，是指與某個(gè)領(lǐng)域或者某個(gè)話題相關(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)為是一個(gè)典型的高質(zhì)量“Hub”網(wǎng)頁。 HITS算法的目的即是通過一定的技術(shù)手段，在海量網(wǎng)頁中找到與用戶查詢主題相關(guān)的高質(zhì)量“Authority”頁面和“Hub”頁面，尤其是“Authority”頁面，因?yàn)檫@些頁面代表了能夠

14、滿足用戶查詢的高質(zhì)量內(nèi)容，搜索引擎以此作為搜索結(jié)果返回給用戶。Hub頁面與Authority頁面2022/10/425WME小組:洪賽小組:洪賽根集合將查詢q提交給基于關(guān)鍵字查詢的檢索系統(tǒng)，從返回結(jié)果頁面的集合總?cè)∏皀個(gè)網(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小組:洪賽小組:洪賽擴(kuò)展集合base在根集root的基礎(chǔ)上，HITS算法對(duì)網(wǎng)頁集合進(jìn)行擴(kuò)充（參考右圖）集合base擴(kuò)充原則

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

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

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

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

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