搜索引擎鏈接分析算法之：hilltop算法

1、<p>　　Hilltop外鏈算法是由Krishna Baharat 在2000年左右研究的，于2001年申請(qǐng)專利，但是有很多人以為Hilltop算法是由谷歌研究的。只不過是Krishna Baharat 后來加入了Google成為了一名核心工程師，然后授權(quán)給Google使用的。 </p><p>　　在與PageRank算法相比之下，Google意識(shí)到這個(gè)算法的進(jìn)步會(huì)為他們的搜索排名帶來非常

2、重要的功能。Google的HillTop算法現(xiàn)在已經(jīng)能更好的與舊的算法(PR算法)聯(lián)合起來工作。根據(jù)觀察HillTop算法比起它在2000年剛設(shè)計(jì)的時(shí)候已經(jīng)有了很大的進(jìn)步。顯然這也是2003年11月16日“佛羅里達(dá)”更新中影響的一個(gè)最主要的算法。     </p><p>　　1. Hilltop算法基本思想</p><p>　　Hilltop融合了HITS和

3、PageRank兩個(gè)算法的基本思想：</p><p>　　一方面，Hilltop是與用戶查詢請(qǐng)求相關(guān)的鏈接分析算法，吸收了HITS算法根據(jù)用戶查詢獲得高質(zhì)量相關(guān)網(wǎng)頁子集的思想，即主題相關(guān)網(wǎng)頁之間的鏈接對(duì)于權(quán)重計(jì)算的貢獻(xiàn)比主題不相關(guān)的鏈接價(jià)值要更高.符合“子集傳播模型”，是該模型的一個(gè)具體實(shí)例；</p><p>　　另一方面，在權(quán)值傳播過程中，Hilltop也采納了PageRank的基本指導(dǎo)

4、思想，即通過頁面入鏈的數(shù)量和質(zhì)量來確定搜索結(jié)果的排序權(quán)重。</p><p>　　2. Hilltop算法的一些基本定義</p><p>　　非從屬組織頁面：   </p><p>　　“非從屬組織頁面”（Non-affiliated Pages）是Hilltop算法的一個(gè)很重要的定義。要了解什么是非從屬組織頁面，先要搞明白什么是“從屬組織網(wǎng)站”，

5、所謂“從屬組織網(wǎng)站”，即不同的網(wǎng)站屬于同一機(jī)構(gòu)或者其擁有者有密切關(guān)聯(lián)。具體而言，滿足如下任意一條判斷規(guī)則的網(wǎng)站會(huì)被認(rèn)為是從屬網(wǎng)站：</p><p>　　條件1：主機(jī)IP地址的前三個(gè)子網(wǎng)段相同，比如：IP地址分別為159.226.138.127和159.226.138.234的兩個(gè)網(wǎng)站會(huì)被認(rèn)為是從屬網(wǎng)站。</p><p>　　條件2：如果網(wǎng)站域名中的主域名相同，比如:www.ibm.com和

6、www.ibm.com.cn會(huì)被認(rèn)為是從屬組織網(wǎng)站。 </p><p>　　“非從屬組織頁面”的含義是：如果兩個(gè)頁面不屬于從屬網(wǎng)站，則為非從屬組織頁面。圖6-22是相關(guān)示意圖，從圖中可以看出，頁面2和頁面3同屬于IBM的網(wǎng)頁，所以是“從屬組織頁面”，而頁面1和頁面5、頁面3和頁面6都是“非從屬組織頁面”。由此也可看出，“非從屬組織頁面”代表的是頁面的一種關(guān)系，單個(gè)一個(gè)頁面是無所謂從屬或者非從屬組織頁面的

7、。</p><p>　　圖6-22 “從屬組織頁面”與“非從屬組織頁面”</p><p><b>　　專家頁面：</b></p><p>　　“專家頁面”(Export Sources)是Hilltop算法的另外一個(gè)重要定義。所謂“專家頁面”，即與某個(gè)主題相關(guān)的高質(zhì)量頁面，同時(shí)需要滿足以下要求：這些頁面的鏈接所指向的頁面相互之間都是“非從屬組織

8、頁面”，且這些被指向的頁面大多數(shù)是與“專家頁面”主題相近的。</p><p><b>　　目標(biāo)頁面集合：</b></p><p>　　Hilltop算法將互聯(lián)網(wǎng)頁面劃分為兩類子集合，最重要的子集合是由專家頁面構(gòu)成的互聯(lián)網(wǎng)頁面子集，不在這個(gè)子集里的剩下的互聯(lián)網(wǎng)頁面作為另外一個(gè)集合，這個(gè)集合稱作“目標(biāo)頁面集合”（Target Web Servers）。</p>

9、<p>　　3. Hilltop算法</p><p>　　圖6-23是Hilltop算法的整體流程示意。</p><p>　　1) 建立專家頁面索引：首先從海量的互聯(lián)網(wǎng)網(wǎng)頁中通過一定規(guī)則篩選出“專家頁面”子集合，并單獨(dú)為這個(gè)頁面集合建立索引。</p><p>　　2）用戶查詢: Hilltop在接收到用戶發(fā)出的某個(gè)查詢請(qǐng)求時(shí):</p>&

10、lt;p>　　首先) 根據(jù)用戶查詢的主題，從“專家頁面”子集合中找出部分相關(guān)性最強(qiáng)的“專家頁面”，并對(duì)每個(gè)專家頁面計(jì)算相關(guān)性得分，</p><p>　　然后)根據(jù)“目標(biāo)頁面”和這些“專家頁面”的鏈接關(guān)系來對(duì)目標(biāo)頁面進(jìn)行排序。基本思路遵循PageRank算法的鏈接數(shù)量假設(shè)和質(zhì)量原則，將專家頁面的得分通過鏈接關(guān)系傳遞給目標(biāo)頁面，并以此分?jǐn)?shù)作為目標(biāo)頁面與用戶查詢相關(guān)性的排序得分。</p><p

11、>　　最后) 系統(tǒng)整合相關(guān)專家頁面和得分較高的目標(biāo)頁面作為搜索結(jié)果返回給用戶。</p><p>　　圖6-23 Hilltop算法流程</p><p>　　若在上述過程中，Hilltop無法得到一個(gè)足夠大的專家頁面集合，則返回搜索結(jié)果為空。由此可以看出，Hilltop算法更注重搜索結(jié)果的精度和準(zhǔn)確性，不太考慮搜索結(jié)果是否足夠多或者對(duì)大多數(shù)用戶查詢是否都有相應(yīng)的搜索結(jié)果，所以很多用戶發(fā)

12、出的查詢的搜索結(jié)果為空。這意味著Hilltop可以與某個(gè)排序算法相結(jié)合，以提高排序準(zhǔn)確性，但并不適合作為一個(gè)獨(dú)立的網(wǎng)頁排序算法來使用。</p><p>　　4. Hilltop算法流程</p><p>　　從上述整體流程描述可看出，Hilltop算法主要包含兩個(gè)步驟：專家頁面搜索及目標(biāo)頁面排序。</p><p>　　步驟一：專家頁面搜索</p><

13、;p>　　Hilltop算法從1億4千萬網(wǎng)頁中，通過計(jì)算篩選出250萬規(guī)模的互聯(lián)網(wǎng)頁面作為“專家頁面”集合?！皩＜翼撁妗钡倪x擇標(biāo)準(zhǔn)相對(duì)寬松，同時(shí)滿足以下兩個(gè)條件的頁面即可進(jìn)入“專家頁面”集合:</p><p>　　條件1：頁面至少包含k個(gè)出鏈，這里的數(shù)量k可人為指定；</p><p>　　條件2：k個(gè)出鏈指向的所有頁面相互之間的關(guān)系都符合“非從屬組織頁面”的要求；</p>

14、<p>　　當(dāng)然，在此基礎(chǔ)上，可以設(shè)定更嚴(yán)格的篩選條件，比如要求這些“專家頁面”所包含鏈接指向的頁面中，大部分所涉及的主題和專家頁面的主題必須是一致或近似的。</p><p>　　根據(jù)以上條件篩選出“專家頁面”后，即可對(duì)“專家頁面”單獨(dú)建索引，在此過程中，索引系統(tǒng)只對(duì)頁面中的“關(guān)鍵片段”（Key Phrase）進(jìn)行索引。所謂“關(guān)鍵片段”，在Hilltop算法里包含了網(wǎng)頁的三類信息：網(wǎng)頁標(biāo)題、H1標(biāo)簽

15、內(nèi)文字和URL錨文字。</p><p>　　網(wǎng)頁的“關(guān)鍵片段”可以支配（Qualify）某個(gè)區(qū)域內(nèi)包含的所有鏈接，“支配”關(guān)系代表了一種管轄范圍，不同的“關(guān)鍵片段”支配鏈接的區(qū)域范圍不同，具體而言：</p><p>　　頁面標(biāo)題可以支配頁面內(nèi)所有出現(xiàn)的鏈接，</p><p>　　H1標(biāo)簽可以支配包圍在<H1>和</H1>內(nèi)的所有鏈接，<

16、/p><p>　　URL錨文字只能支配本身唯一的鏈接。</p><p>　　圖6-24給出了“關(guān)鍵片段”對(duì)鏈接支配關(guān)系的示意圖，在以“奧巴馬訪問中國”為標(biāo)題的網(wǎng)頁頁面中，標(biāo)題支配了所有這個(gè)頁面出現(xiàn)的鏈接，而H1標(biāo)簽的管轄范圍僅限于標(biāo)簽范圍內(nèi)出現(xiàn)的2個(gè)鏈接，對(duì)于錨文字“中國領(lǐng)導(dǎo)人”來說，其唯一能夠支配的就是本身的這個(gè)鏈接。之所以定義這種支配關(guān)系，對(duì)于第二階段將“專家頁面”的分值傳遞到“目標(biāo)頁面”

17、時(shí)候會(huì)起作用。</p><p>　　圖6-24 “關(guān)鍵片段”鏈接支配關(guān)系</p><p>　　系統(tǒng)接收到用戶查詢Q，假設(shè)用戶查詢包含了多個(gè)單詞，Hilltop如何對(duì)“專家頁面”進(jìn)行打分呢？對(duì)“專家頁面”進(jìn)行打分主要參考以下三類信息：</p><p>　　1)“關(guān)鍵片段”包含了多少查詢?cè)~，包含查詢?cè)~越多，則分值越高，如果不包含任何查詢?cè)~，則該“關(guān)鍵片段”不計(jì)分；<

18、;/p><p>　　2)“關(guān)鍵片段”本身的類型信息，網(wǎng)頁標(biāo)題權(quán)值最高，H1標(biāo)簽次之，再次是鏈接錨文字；</p><p>　　3)用戶查詢和“關(guān)鍵片段”的失配率，即“關(guān)鍵片段”中不屬于查詢?cè)~的單詞個(gè)數(shù)占“關(guān)鍵片段”總單詞個(gè)數(shù)，這個(gè)值越小越好，越大則得分衰減越多；</p><p>　　Hilltop綜合考慮以上三類因素，擬合出打分函數(shù)來對(duì)“專家頁面”是否與用戶查詢相關(guān)進(jìn)行打

19、分，選出相關(guān)性分值足夠高的“專家頁面”，以進(jìn)行下一步驟操作，即對(duì)“目標(biāo)頁面”進(jìn)行相關(guān)性計(jì)算。</p><p>　　步驟二：目標(biāo)頁面排序</p><p>　　Hilltop算法包含一個(gè)基本假設(shè)，即認(rèn)為一個(gè)“目標(biāo)頁面”如果是滿足用戶查詢的高質(zhì)量搜索結(jié)果，其充分必要條件是該“目標(biāo)頁面”有高質(zhì)量“專家頁面”鏈接指向。然而，這個(gè)假設(shè)并不總是成立，比如有的“專家頁面”的鏈接所指向的“目標(biāo)頁面”可能與用

20、戶查詢并非密切相關(guān)。所以，Hilltop算法在這個(gè)階段需要對(duì)“專家頁面”的出鏈仔細(xì)進(jìn)行甄別，以保證選出那些和查詢密切相關(guān)的目標(biāo)頁面。</p><p>　　Hilltop在本階段是基于“專家頁面”和“目標(biāo)頁面”之間的鏈接關(guān)系來進(jìn)行的，在此基礎(chǔ)上，將“專家頁面”的得分傳遞給有鏈接關(guān)系的“目標(biāo)頁面”。傳遞分值之前，首先需要對(duì)鏈接關(guān)系進(jìn)行整理，能夠獲得“專家頁面”分值的“目標(biāo)頁面”需要滿足以下兩點(diǎn)要求：</p>

21、;<p>　　條件1：至少需要兩個(gè)“專家頁面”有鏈接指向“目標(biāo)頁面”，而且這兩個(gè)專家頁面不能是“從屬組織頁面”，即不能來自同一網(wǎng)站或相關(guān)網(wǎng)站。如果是“從屬組織頁面”，則只能保留一個(gè)鏈接，拋棄權(quán)值低的那個(gè)鏈接；</p><p>　　條件2：“專家頁面”和所指向的“目標(biāo)頁面”也需要符合一定要求，即這兩個(gè)頁面也不能是“從屬組織頁面”；</p><p>　　在步驟一，給定用戶查詢，H

22、illtop算法已經(jīng)獲得相關(guān)的“專家頁面”及其與查詢的相關(guān)度得分，在此基礎(chǔ)上，如何對(duì)“目標(biāo)頁面”的相關(guān)性打分？上面列出的條件1指出，能夠獲得傳遞分值的“目標(biāo)頁面”一定有多個(gè)“專家頁面”鏈接指向，所以“目標(biāo)頁面”所獲得的總傳播分值是每個(gè)有鏈接指向的“專家頁面”所傳遞分值之和。而計(jì)算其中某個(gè)“專家頁面”傳遞給“目標(biāo)頁面”權(quán)值的時(shí)候是這么計(jì)算的：</p><p>　　a. 找到“專家頁面” 中那些能夠支配目標(biāo)頁面的“關(guān)

23、鍵片段”集合S；</p><p>　　b. 統(tǒng)計(jì)S中包含用戶查詢?cè)~的“關(guān)鍵片段”個(gè)數(shù)T，T越大傳遞的權(quán)值越大；</p><p>　　c.“專家頁面”傳遞給“目標(biāo)頁面”的分值為：E*T，E為專家頁面本身在第一階段計(jì)算得到的相關(guān)得分，T為b步驟計(jì)算的分值，</p><p>　　我們以圖6-25的具體例子來說明。假設(shè)“專家頁面”集合內(nèi)存在一個(gè)網(wǎng)頁P(yáng)，其標(biāo)題為：“奧巴馬訪問

24、中國”，網(wǎng)頁內(nèi)容由一段<H1>標(biāo)簽文字和另外一個(gè)單獨(dú)的鏈接錨文字組成。該頁面包含三個(gè)出鏈，其中兩個(gè)指向“目標(biāo)頁面集合”中的網(wǎng)頁www.china.org,另外一個(gè)指向網(wǎng)頁www.obama.org。出鏈對(duì)應(yīng)的錨文字分別為：“奧巴馬”，“中國”和“中國領(lǐng)導(dǎo)人”。</p><p>　　圖6-25 Hilltop算法分值傳遞</p><p>　　從圖示的鏈接關(guān)系可以看出，網(wǎng)頁P(yáng)中能夠

25、支配www.china.org這個(gè)目標(biāo)頁面的“關(guān)鍵片段”集合包括：{中國領(lǐng)導(dǎo)人，中國，<H1>奧巴馬訪問中國</H1>,標(biāo)題：奧巴馬訪問中國}。而能夠支配www.obamba.org目標(biāo)頁面的“關(guān)鍵片段”集合包括：{奧巴馬，<H1>奧巴馬訪問中國</H1>,標(biāo)題：奧巴馬訪問中國}。</p><p>　　接下來我們分析“專家頁面”P在接收到查詢時(shí)，是怎樣將分值傳遞給與

26、其有鏈接關(guān)系的“目標(biāo)頁面”的。假設(shè)系統(tǒng)接收到的查詢請(qǐng)求為“奧巴馬”,在接收到查詢后，系統(tǒng)首先根據(jù)上述章節(jié)所述,找出“專家頁面”并給予分值，而網(wǎng)頁P(yáng)是作為“專家頁面”其中一個(gè)頁面，并獲得了相應(yīng)的分值S，我們重點(diǎn)關(guān)注分值傳播步驟。</p><p>　　對(duì)于查詢“奧巴馬”來說，網(wǎng)頁P(yáng)中包含這個(gè)查詢?cè)~的“關(guān)鍵片段”集合為：{奧巴馬，<H1>奧巴馬訪問中國</H1>,標(biāo)題：奧巴馬訪問中國}，如上所述

27、，這三個(gè)“關(guān)鍵片段”都能夠支配www.obama.org頁面，所以網(wǎng)頁P(yáng)傳遞給www.obamba.org的分值為S*3。而對(duì)于目標(biāo)頁面www.china.org來說，這三個(gè)“關(guān)鍵片段”中只有{<H1>奧巴馬訪問中國</H1>,標(biāo)題：奧巴馬訪問中國}這兩個(gè)能夠支配目標(biāo)頁面，所以網(wǎng)頁P(yáng)傳遞給www.china.org的分值為S*2。</p><p>　　對(duì)于包含多個(gè)查詢?cè)~的用戶請(qǐng)求，則每個(gè)查

28、詢?cè)~單獨(dú)如上計(jì)算，將多個(gè)查詢?cè)~的傳遞分值累加即可。</p><p>　　5. Hilltop在應(yīng)用中不足</p><p>　　專家頁面的搜索和確定對(duì)算法起關(guān)鍵作用，專家頁面的質(zhì)量決定了算法的準(zhǔn)確性；而專家頁面的質(zhì)量和公平性在一定程度上難以保證。 Hiltop忽略了大多數(shù)非專家頁面的影響。</p><p>　　在Hilltop的原型系統(tǒng)中，專家頁面只占到整個(gè)頁面的1．

29、79%，不能全面反映民意。</p><p>　　Hilltop算法在無法得到足夠的專家頁面子集時(shí)(少于兩個(gè)專家頁面)，返回為空，即Hilltop適合于對(duì)查詢排序進(jìn)行求精，而不能覆蓋。這意味著Hilltop可以與某個(gè)頁面排序算法結(jié)合，提高精度，而不適合作為一個(gè)獨(dú)立的頁面排序算法。</p><p>　　Hilltop存在與HITS算法類似的計(jì)算效率問題，因?yàn)楦鶕?jù)查詢主題從“專家頁面”集合中選取

30、主題相關(guān)的頁面子集也是在線運(yùn)行的，這與前面提到的HITS算法一樣會(huì)影響查詢響應(yīng)時(shí)間。隨著“專家頁面”集合的增大，算法的可擴(kuò)展性存在不足之處。</p><p>　　--------------------- </p><p><b>　　作者：規(guī)速 </b></p><p><b>　　來源：CSDN &l

31、t;/b></p><p>　　原文：https://blog.csdn.net/hguisu/article/details/8021036 </p><p>　　版權(quán)聲明：本文為博主原創(chuàng)文章，轉(zhuǎn)載請(qǐng)附上博文鏈接！</p><p>　　網(wǎng)站部分內(nèi)容來自網(wǎng)絡(luò)，僅作分享之用，文章版權(quán)屬于原作者。如果分享內(nèi)容侵犯您的版權(quán)或者所標(biāo)來源非第一原創(chuàng)，請(qǐng)聯(lián)系我們