鏈接分析算法之：HillTop算法

   Hilltop算法是由Krishna Baharat 在2000年左右研究的，于2001年申請專利，但是有很多人以為Hilltop算法是由谷歌研究的。只不過是Krishna Baharat 后來加入了Google成為了一名核心工程師，然后授權給Google使用的。 

        在與PageRank算法相比之下，Google意識到這個算法的進步會為他們的搜索排名帶來非常重要的功能。Google的HillTop算法現在已經能更好的與舊的算法(PR算法)聯合起來工作。根據觀察HillTop算法比起它在2000年剛設計的時候已經有了很大的進步。顯然這也是2003年11月16日“佛羅里達”更新中影響的一個最主要的算法。     

1. Hilltop算法基本思想

       Hilltop融合了HITS和PageRank兩個算法的基本思想：

       一方面，Hilltop是與用戶查詢請求相關的鏈接分析算法，吸收了HITS算法根據用戶查詢獲得高質量相關網頁子集的思想，即主題相關網頁之間的鏈接對于權重計算的貢獻比主題不相關的鏈接價值要更高.符合“子集傳播模型”，是該模型的一個具體實例；

      另一方面，在權值傳播過程中，Hilltop也采納了PageRank的基本指導思想，即通過頁面入鏈的數量和質量來確定搜索結果的排序權重。

2. Hilltop算法的一些基本定義

  非從屬組織頁面：   

    “非從屬組織頁面”（Non-affiliated Pages）是Hilltop算法的一個很重要的定義。要了解什么是非從屬組織頁面，先要搞明白什么是“從屬組織網站”，所謂“從屬組織網站”，即不同的網站屬于同一機構或者其擁有者有密切關聯。具體而言，滿足如下任意一條判斷規則的網站會被認為是從屬網站：

      條件1：主機IP地址的前三個子網段相同，比如：IP地址分別為159.226.138.127和159.226.138.234的兩個網站會被認為是從屬網站。

      條件2：如果網站域名中的主域名相同，比如:www.ibm.com和www.ibm.com.cn會被認為是從屬組織網站。 

     “非從屬組織頁面”的含義是：如果兩個頁面不屬于從屬網站，則為非從屬組織頁面。圖6-22是相關示意圖，從圖中可以看出，頁面2和頁面3同屬于IBM的網頁，所以是“從屬組織頁面”，而頁面1和頁面5、頁面3和頁面6都是“非從屬組織頁面”。由此也可看出，“非從屬組織頁面”代表的是頁面的一種關系，單個一個頁面是無所謂從屬或者非從屬組織頁面的。

                           圖6-22 “從屬組織頁面”與“非從屬組織頁面”

專家頁面：

      “專家頁面”(Export Sources)是Hilltop算法的另外一個重要定義。所謂“專家頁面”，即與某個主題相關的高質量頁面，同時需要滿足以下要求：這些頁面的鏈接所指向的頁面相互之間都是“非從屬組織頁面”，且這些被指向的頁面大多數是與“專家頁面”主題相近的。

目標頁面集合：

     Hilltop算法將互聯網頁面劃分為兩類子集合，最重要的子集合是由專家頁面構成的互聯網頁面子集，不在這個子集里的剩下的互聯網頁面作為另外一個集合，這個集合稱作“目標頁面集合”（Target Web Servers）。

3. Hilltop算法

     圖6-23是Hilltop算法的整體流程示意。

     1) 建立專家頁面索引：首先從海量的互聯網網頁中通過一定規則篩選出“專家頁面”子集合，并單獨為這個頁面集合建立索引。

     2）用戶查詢: Hilltop在接收到用戶發出的某個查詢請求時:

      首先) 根據用戶查詢的主題，從“專家頁面”子集合中找出部分相關性最強的“專家頁面”，并對每個專家頁面計算相關性得分，

       然后)根據“目標頁面”和這些“專家頁面”的鏈接關系來對目標頁面進行排序。基本思路遵循PageRank算法的鏈接數量假設和質量原則，將專家頁面的得分通過鏈接關系傳遞給目標頁面，并以此分數作為目標頁面與用戶查詢相關性的排序得分。

       最后) 系統整合相關專家頁面和得分較高的目標頁面作為搜索結果返回給用戶。

                                                            圖6-23 Hilltop算法流程

      若在上述過程中，Hilltop無法得到一個足夠大的專家頁面集合，則返回搜索結果為空。由此可以看出，Hilltop算法更注重搜索結果的精度和準確性，不太考慮搜索結果是否足夠多或者對大多數用戶查詢是否都有相應的搜索結果，所以很多用戶發出的查詢的搜索結果為空。這意味著Hilltop可以與某個排序算法相結合，以提高排序準確性，但并不適合作為一個獨立的網頁排序算法來使用。

4. Hilltop算法流程

      從上述整體流程描述可看出，Hilltop算法主要包含兩個步驟：專家頁面搜索及目標頁面排序。

步驟一：專家頁面搜索

         Hilltop算法從1億4千萬網頁中，通過計算篩選出250萬規模的互聯網頁面作為“專家頁面”集合?！皩＜翼撁妗钡倪x擇標準相對寬松，同時滿足以下兩個條件的頁面即可進入“專家頁面”集合:

         條件1：頁面至少包含k個出鏈，這里的數量k可人為指定；

         條件2：k個出鏈指向的所有頁面相互之間的關系都符合“非從屬組織頁面”的要求；

       當然，在此基礎上，可以設定更嚴格的篩選條件，比如要求這些“專家頁面”所包含鏈接指向的頁面中，大部分所涉及的主題和專家頁面的主題必須是一致或近似的。

       根據以上條件篩選出“專家頁面”后，即可對“專家頁面”單獨建索引，在此過程中，索引系統只對頁面中的“關鍵片段”（Key Phrase）進行索引。所謂“關鍵片段”，在Hilltop算法里包含了網頁的三類信息：網頁標題、H1標簽內文字和URL錨文字。

       網頁的“關鍵片段”可以支配（Qualify）某個區域內包含的所有鏈接，“支配”關系代表了一種管轄范圍，不同的“關鍵片段”支配鏈接的區域范圍不同，具體而言：

       頁面標題可以支配頁面內所有出現的鏈接，

       H1標簽可以支配包圍在<H1>和</H1>內的所有鏈接，

       URL錨文字只能支配本身唯一的鏈接。

       圖6-24給出了“關鍵片段”對鏈接支配關系的示意圖，在以“奧巴馬訪問中國”為標題的網頁頁面中，標題支配了所有這個頁面出現的鏈接，而H1標簽的管轄范圍僅限于標簽范圍內出現的2個鏈接，對于錨文字“中國領導人”來說，其唯一能夠支配的就是本身的這個鏈接。之所以定義這種支配關系，對于第二階段將“專家頁面”的分值傳遞到“目標頁面”時候會起作用。

                                 圖6-24 “關鍵片段”鏈接支配關系

        系統接收到用戶查詢Q，假設用戶查詢包含了多個單詞，Hilltop如何對“專家頁面”進行打分呢？對“專家頁面”進行打分主要參考以下三類信息：

         1)“關鍵片段”包含了多少查詢詞，包含查詢詞越多，則分值越高，如果不包含任何查詢詞，則該“關鍵片段”不計分；

         2)“關鍵片段”本身的類型信息，網頁標題權值最高，H1標簽次之，再次是鏈接錨文字；

         3)用戶查詢和“關鍵片段”的失配率，即“關鍵片段”中不屬于查詢詞的單詞個數占“關鍵片段”總單詞個數，這個值越小越好，越大則得分衰減越多；

       Hilltop綜合考慮以上三類因素，擬合出打分函數來對“專家頁面”是否與用戶查詢相關進行打分，選出相關性分值足夠高的“專家頁面”，以進行下一步驟操作，即對“目標頁面”進行相關性計算。

步驟二：目標頁面排序

       Hilltop算法包含一個基本假設，即認為一個“目標頁面”如果是滿足用戶查詢的高質量搜索結果，其充分必要條件是該“目標頁面”有高質量“專家頁面”鏈接指向。然而，這個假設并不總是成立，比如有的“專家頁面”的鏈接所指向的“目標頁面”可能與用戶查詢并非密切相關。所以，Hilltop算法在這個階段需要對“專家頁面”的出鏈仔細進行甄別，以保證選出那些和查詢密切相關的目標頁面。

      Hilltop在本階段是基于“專家頁面”和“目標頁面”之間的鏈接關系來進行的，在此基礎上，將“專家頁面”的得分傳遞給有鏈接關系的“目標頁面”。傳遞分值之前，首先需要對鏈接關系進行整理，能夠獲得“專家頁面”分值的“目標頁面”需要滿足以下兩點要求：

     條件1：至少需要兩個“專家頁面”有鏈接指向“目標頁面”，而且這兩個專家頁面不能是“從屬組織頁面”，即不能來自同一網站或相關網站。如果是“從屬組織頁面”，則只能保留一個鏈接，拋棄權值低的那個鏈接；

     條件2：“專家頁面”和所指向的“目標頁面”也需要符合一定要求，即這兩個頁面也不能是“從屬組織頁面”；

      在步驟一，給定用戶查詢，Hilltop算法已經獲得相關的“專家頁面”及其與查詢的相關度得分，在此基礎上，如何對“目標頁面”的相關性打分？上面列出的條件1指出，能夠獲得傳遞分值的“目標頁面”一定有多個“專家頁面”鏈接指向，所以“目標頁面”所獲得的總傳播分值是每個有鏈接指向的“專家頁面”所傳遞分值之和。而計算其中某個“專家頁面”傳遞給“目標頁面”權值的時候是這么計算的：

        a. 找到“專家頁面” 中那些能夠支配目標頁面的“關鍵片段”集合S；

        b. 統計S中包含用戶查詢詞的“關鍵片段”個數T，T越大傳遞的權值越大；

        c.“專家頁面”傳遞給“目標頁面”的分值為：E*T，E為專家頁面本身在第一階段計算得到的相關得分，T為b步驟計算的分值，

     我們以圖6-25的具體例子來說明。假設“專家頁面”集合內存在一個網頁P，其標題為：“奧巴馬訪問中國”，網頁內容由一段<H1>標簽文字和另外一個單獨的鏈接錨文字組成。該頁面包含三個出鏈，其中兩個指向“目標頁面集合”中的網頁www.china.org,另外一個指向網頁www.obama.org。出鏈對應的錨文字分別為：“奧巴馬”，“中國”和“中國領導人”。

                                                          圖6-25 Hilltop算法分值傳遞

       從圖示的鏈接關系可以看出，網頁P中能夠支配www.china.org這個目標頁面的“關鍵片段”集合包括：{中國領導人，中國，<H1>奧巴馬訪問中國</H1>,標題：奧巴馬訪問中國}。而能夠支配www.obamba.org目標頁面的“關鍵片段”集合包括：{奧巴馬，<H1>奧巴馬訪問中國</H1>,標題：奧巴馬訪問中國}。

      接下來我們分析“專家頁面”P在接收到查詢時，是怎樣將分值傳遞給與其有鏈接關系的“目標頁面”的。假設系統接收到的查詢請求為“奧巴馬”,在接收到查詢后，系統首先根據上述章節所述,找出“專家頁面”并給予分值，而網頁P是作為“專家頁面”其中一個頁面，并獲得了相應的分值S，我們重點關注分值傳播步驟。

     對于查詢“奧巴馬”來說，網頁P中包含這個查詢詞的“關鍵片段”集合為：{奧巴馬，<H1>奧巴馬訪問中國</H1>,標題：奧巴馬訪問中國}，如上所述，這三個“關鍵片段”都能夠支配www.obama.org頁面，所以網頁P傳遞給www.obamba.org的分值為S*3。而對于目標頁面www.china.org來說，這三個“關鍵片段”中只有{<H1>奧巴馬訪問中國</H1>,標題：奧巴馬訪問中國}這兩個能夠支配目標頁面，所以網頁P傳遞給www.china.org的分值為S*2。

    對于包含多個查詢詞的用戶請求，則每個查詢詞單獨如上計算，將多個查詢詞的傳遞分值累加即可。

5. Hilltop在應用中不足

      專家頁面的搜索和確定對算法起關鍵作用，專家頁面的質量決定了算法的準確性；而專家頁面的質量和公平性在一定程度上難以保證。 Hiltop忽略了大多數非專家頁面的影響。

       在Hilltop的原型系統中，專家頁面只占到整個頁面的1．79%，不能全面反映民意。

       Hilltop算法在無法得到足夠的專家頁面子集時(少于兩個專家頁面)，返回為空，即Hilltop適合于對查詢排序進行求精，而不能覆蓋。這意味著Hilltop可以與某個頁面排序算法結合，提高精度，而不適合作為一個獨立的頁面排序算法。

       Hilltop存在與HITS算法類似的計算效率問題，因為根據查詢主題從“專家頁面”集合中選取主題相關的頁面子集也是在線運行的，這與前面提到的HITS算法一樣會影響查詢響應時間。隨著“專家頁面”集合的增大，算法的可擴展性存在不足之處。

轉自：http://blog.csdn.net/hguisu/article/details/8021036