HITS算法:英文全稱,算法由來,具體解釋,Hits算法,描述,偽代碼,拓展研究,

HITS 算法是由康奈爾大學( Cornell University ) 的Jon Kleinberg 博士於1997 年首先提出的,為IBM 公司阿爾馬登研究中心( IBM Almaden Research Center) 的名為“CLEVER”的研究項目中的一部分。

基本介紹

中文名：超文本敏感標題搜尋
外文名：Hyperlink-Induced Topic Search
所屬領域：網際網路技術

英文全稱,算法由來,具體解釋,Hits算法,描述,偽代碼,拓展研究,

英文全稱

Hyperlink-Induced Topic Search

算法由來

具體解釋

按照HITS算法，用戶輸入關鍵字後，算法對返回的匹配頁面計算兩種值，一種是樞紐值（Hub Scores），另一種是權威值(Authority Scores),這兩種值是互相依存、互相影響的。所謂樞紐值，指的是頁面上所有導出連結指向頁面的權威值之和。權威值是指所有導入連結所在的頁面中樞紐之和。

一個網頁重要性的分析的算法。

通常HITS算法是作用在一定範圍的，比如一個以程式開發為主題網頁，指向另一個以程式開發為主題的網頁，則另一個網頁的重要性就可能比較高，但是指向另一個購物類的網頁則不一定。

在限定範圍之後根據網頁的出度和入度建立一個矩陣，通過矩陣的疊代運算和定義收斂的閾值不斷對兩個向量Authority和Hub值進行更新直至收斂。

Hits算法

描述

HITS(Hyperlink – Induced Topic Search) 算法是利用HubPAuthority的搜尋方法,

具體算法如下:

將查詢q提交給基於關鍵字查詢的檢索系統，從返回結果頁面的集合中取前n個網頁(如n=200)，作為根集合(root set)，記為S，則S滿足：

1.S中的網頁數量較少

2.S中的網頁是與查詢q相關的網頁

3.S中的網頁包含較多的權威(Authority)網頁

通過向S 中加入被S 引用的網頁和引用S 的網頁,將S 擴展成一個更大的集合T. 以T 中的Hub 網頁為頂點集V1 ,以權威網頁為頂點集V2 。

V1 中的網頁到V2 中的網頁的超連結為邊集E ,形成一個二分有向圖. 對V1 中的任一個頂點v ,用h ( v) 表示網頁v 的Hub 值,且h ( v)收斂;對V2 中的頂點u ,用a ( u) 表示網頁的Authority 值。

開始時h ( v) = a ( u) = 1 ,對u 執行I 操作,修改它的a ( u) ,對v執行O操作,修改它的h ( v) ,然後規範化a ( u),h ( v) ,如此不斷的重複計算下面的I操作和O操作,直到a ( u),h(v)收斂。

其中I操作:a ( u) = Σh ( v) ;O 操作: h ( v) = Σa ( u) 。每次疊代對a ( u) 、h ( v) 進行規範化處理: a ( u) = a ( u)/Σ[ a ( q) ]2 ; h ( v) = h ( v)/Σ[ h ( q) ]2 。

偽代碼

HITS算法偽代碼如下：

1G:= set of pages

2for eachpagepinGdo

3p.auth = 1 //p.auth is the authority score of the pagep

4p.hub = 1 //p.hub is the hub score of the pagep

5functionHubsAndAuthorities(G)

6forstepfrom1tokdo// run the algorithm for k steps

7 norm = 0

8for eachpagepinGdo// update all authority values first

9p.auth = 0

10for eachpageqinp.incomingNeighborsdo//p.incomingNeighborsis the set of pages that link top

11p.auth +=q.hub

12 norm += square(p.auth) // calculate the sum of the squared auth values to normalise

13 norm = sqrt(norm)

14for eachpagepinGdo// update the auth scores

15p.auth =p.auth / norm // normalise the auth values

16 norm = 0

17for eachpagepinGdo// then update all hub values

18p.hub =

019for eachpagerinp.outgoingNeighborsdo//p.outgoingNeighborsis the set of pages thatplinks to

20p.hub +=r.auth

21 norm += square(p.hub) // calculate the sum of the squared hub values to normalise

22 norm = sqrt(norm)

23for eachpagepinGdo// then update all hub values

24p.hub =p.hub / norm // normalise the hub values

拓展研究

理解HITS算法是Web結構挖掘中最具有權威性和使用最廣泛的算法。HITS(Hypertext-InducedTopic Search)算法是利用Web的連結結構進行挖掘典型算法，其核心思想是建立在頁面連結關係的基礎上，對連結結構的改進算法。HITS算法通過兩個評價權值——內容權威度（Authority）和連結權威度（Hub）來對網頁質量進行評估。其基本思想是利用頁面之間的引用鏈來挖掘隱含在其中的有用信息（如權威性），具有計算簡單且效率高的特點。HITS算法認為對每一個網頁應該將其內容權威度和連結權威度分開來考慮，在對網頁內容權威度做出評價的基礎上再對頁面的連結權威度進行評價，然後給出該頁面的綜合評價。內容權威度與網頁自身直接提供內容信息的質量相關，被越多網頁所引用的網頁，其內容權威度越高；連結權威度與網頁提供的超連結頁面的質量相關，引用越多高質量頁面的網頁，其連結權威度越高。

首先，它完全將網頁的內容或文本排除在外，僅考慮網頁之間的連結結構來分析頁面的權威性，這與現實網路中的權威頁面相比，其不科學性顯而易見。然而HITS算法也有其明顯的不足。因為權威頁面必須針對某一主題或關鍵字而言。例如某一頁面對一確定主題具有較大權威性，但這並不意味在其他與其無關的主題方面同樣具有權威性。其次一個頁面對另一頁面的引用有多種情況，其中包含了一頁面對另一頁面的認可，但除此之外也有其他目的連結，如為了導航或為了付費廣告。就HITS算法的思想與實現過程做了細緻的研究與概括。而HITS算法在實現過程中均沒有考慮以上情況．導致了結果與目標的差距。

對HITS算法的第二個不足，即非正常目的的引用．在HITS算法看來，也誤認為是正常引用，導致實際結果與目標的出入。針對前面第一種不足，就有相關的學者提出了一種利用超鏈文字及其周圍文字與關鍵字相匹配而計算超鏈權值的方法，並引入係數對周圍文字和超鏈文字進行權值的相對控制，很好地將頁面文本信息引入到HITS算法，提高了算法的可靠性，並在現實中取得了很好的效果。

後來，經過不斷的改進。HITS算法又引入了時間參數，即利用對一連結引用的時間長短來評價是否為正常引用。因為非正常連結其引用時間肯定不會很長（如交換連結、廣告連結），相反，如果一頁面對另一頁面的連結時間較長，則必然反映此頁面就是用戶的尋找頁面。即目標頁面或至少是正常引用。

如設定訪問時間少於1分鐘者為非正常引用。如果設定時間閥值，則可以將非正常引用的連結在HITS算法的實現過程中篩選出來。另外可構造時間訪問函式，控制權威頁面的相對大小。如隨訪問時間的增大而其權威性也逐漸非線性增大．這樣可為HITS算法的權威頁面提供更合理、更科學的解釋。

HITS算法