2012年3月30日 星期五

HITS演算法詳解


HITS演算法詳解

HITSHyper-link-induced topic search)是由kleinberg提出來的基於連接分析的網頁排名演算法,描述2種類型的網頁:“權威性(authority)的網頁”:對於一個特定的的檢索,該網頁提供最好的相關資訊;“目錄型(hub)網頁”:該網頁提供很多指向其他高品質權威型的網頁鏈結。由此,我們可以在每個網頁上定義“目錄型權值”和“權威型權值2個參數。
1HITS演算法基本思想:
 1、好的hub型網頁指向好的authority型網頁
 2、好的authority型網頁是由好的hub型網頁所指向的網頁
2Hits演算法

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)表示網頁vHubh(v)收斂V2中的頂點u,a(u) 表示網頁的Authority值。
開始時h ( v) = a ( u) = 1,u 執行I 操作修改它的a ( u) ,v執行O操作修改它的h ( v),然後規範化a ( u)Ph ( v),如此不斷的重複計算下面的I操作和O操作直到a ( u)
其中I操作:a ( u) = Σh ( v);O 操作:h ( v) = Σa ( u) 。每次迭代對a ( u) h ( v) 進行規範化處理:a ( u) = a ( u)PΣ[ a ( q) ]2;h ( v) = h ( v)PΣ[ h ( q) ]2

HITS演算法可以獲得比較好的查全率輸出一組具有較大Hub值的網頁和具有較大權威值的網頁但在實際應用中HITS演算法有以下幾個問題

S 生成T 的時間開銷是很昂貴的T 生成有向圖也很耗時需要分別計算網頁的APH計算量大;網頁中廣告等無關鏈結影響AH值的計算降低HITS演算法的精度;HITS演算法只計算主特徵向量處理不好主題漂移問題;進行窄主題查詢時可能產生主題泛化問題。

相關分析演算法大體可以分為4
基於隨機漫遊模型的演算法比如PageRank、Repution演算法基於HubAuthority 相互加強模型的演算法HITS 及其變種基於概率模型的演算法SALSA、PHITS;基於貝葉斯模型的演算法如貝葉斯演算法

所有的演算法在實際應用中都結合傳統的內容分析技術進行優化。Allan Borodin 也指出沒有一種演算法是完美的在某些查詢下結果可能很好在另外的查詢下結果可能很差
S擴展為基本集合(base set) TT包含由S指出或指向S的網頁。可以設定一個上限如 1000—5000個網頁。
開始權重傳播。在集合T中計算每個網頁的目錄型權值和權威型權值。Clever的做法是採用目錄型網頁和權威型網頁相互評價的辦法進行遞迴計算。對於一個網頁p,用xp來表示網頁p的權威型權值,用yp來表示它的目錄型權值,並且用如下公式進行計算:
1.計算各節點的HubAuthority
2.賦予每個節點的hub值和authority值都為1
3.運行Authority更新規則。
4.運行Hub更新規則。
5.Normalize數值,即每個節點的Hub值除所有Hub值之和,每個Authority值除所有Authority值之和。
6.必要時從第二步開始重複。

引用自《Chczz.com

1 則留言:

  1. 您好 請問有hits的計算實例嗎? 難理解二個分值的計算,謝謝

    回覆刪除