摘 要： HITS 算法是Web結構挖掘中一種經典的鏈接分析算法, 其主要問題是容易發生主題漂移。針對這一問題，提出了一種基于文本內容和鏈接分析相結合的改進算法。實驗證明改進后的算法提高了查詢結果的相關度, 降低了主題漂移的可能性。
關鍵詞： HITS算法；主題漂移；權威網頁；中心網頁
?
??? Internet是一個巨大、分布廣泛、全球性的信息服務中心，它提供了各種各樣的信息服務。但如何從Internet浩如煙海的信息中獲取所需信息或是從中提取有用知識，一直是相關專家探究的問題。將傳統的數據挖掘技術和Web結合起來，對Web進行數據挖掘成為解決這一問題的重要途徑。由于Web上的鏈接結構含有非常豐富和重要的信息，鏈接分析技術已經被成功地用于分析Web超鏈接數據來確定權威信息源。而在各種對網頁進行鏈接分析并提取主題的算法中，HITS算法是最典型的。
1 HITS算法
1.1? HITS算法的基本思想
HITS 算法[1]是一種Web結構挖掘算法[1], 該算法基于用戶的查詢, 根據給定的查詢通過分析Web的前向鏈接和后向鏈接來發現一組相關網頁，從而找出Web集合中的authority網頁(與給定查詢主題的上下文最為相關并具有權威性的網頁)和hub網頁(提供指向權威網頁鏈接集合的Web網頁)。為每個網頁定義兩個度量值:權威權重(authority weight)和中心權重(Hub weight)，通過這兩個權重來判定該網頁對特定主題的重要性。
1.2? HITS算法的具體過程
整個HITS算法主要可以分為以下幾個步驟:
(1)在搜索引擎上輸入給定的關鍵詞, 以此搜索到的最前面的r個等級最高的查詢結果網頁作為根集(root set)R，R需滿足如下3個條件： ①R中網頁數量相對較小.②R中網頁大多數是與查詢關鍵詞q相關的網頁。③R中網頁包含較多的權威網頁。
(2)通過向R中加入被R引用的網頁和引用R的網頁將R擴展成一個更大的基礎集合(base set)B。擴展規則為：將根集中的全部網頁加入進來, 并加入最多d個鏈接到根集R中的Web網頁。
(3)以B中的Hub網頁為頂點集Vl，以authority網頁為頂點集V2，Vl中的網頁到V2中的網頁的超鏈接為邊集E，形成一個二分有向圖G＝(V1，V2，E)。對V1中的任一個頂點v，用h(v)表示網頁v的hub值，對V2中的頂點u，用a(u)表示網頁的authority值。假設Web鏈接結構子圖G中包含n個節點(網頁)，對這n個節點加以編號：1，2，…，n，這樣就可以為Web鏈接結構子圖G定義一個n×n的鄰接矩陣A，如果頁面i指向頁面j，則矩陣中的項(i, j)為1，否則為0。同樣把所有節點的authority和hub值定義為向量形式，即：a=(a1,a2,...,an)和h=(h1,h2,...,hn)。
?
根據線性代數的理論，向量a和h經過展開計算后，會收斂至對稱矩陣ATA和AAT的主特征向量。ATA的主特征向量代表權威網頁，而其主特征向量中數值越高代表網頁的權威權重也越高；同樣，AAT的主特征向量代表中心網頁，而其主特征向量中數值越高代表網頁的中心權重也越高。通過以上過程可以看出，經過若干次迭代計算后, 即可得到每一頁面的authority 和hub。基集B中網頁的權威權重和中心權重從根本上說是由基集B中網頁的鏈接關系所決定的，更具體地說，是由對稱矩陣ATA和AAT所決定的。
2?HITS算法中存在的問題
HITS算法雖然在某些查詢主題下能夠較為準確地提取出權威網頁, 但在一些場合中仍會使得算法發生嚴重的“主題漂移”[2]的現象( authorities集中到一些鏈接稠密的非相關網頁的現象被稱為“主題漂移”) 。該現象的出現說明在傳統HITS算法中仍存在一些缺點, 這就要求對傳統HITS算法進行改進, 以使其具有更為廣泛的適用性, 提高權威頁面搜索的效率。
3?HITS算法的改進
HITS算法遇到的問題，多是因為HITS是純粹的基于鏈接分析的算法，沒有考慮文本內容。繼KLIINBERG J提出HITS算法以后，很多研究者對HITS進行了改進，提出了許多HITS的變種算法，主要有IBM Almaden研究中心Clever搜索引擎的ARC(Automatic Resource Compilation)算法[4]和由GEVREY J和RUGER S于2002年提出來的兩個基于超鏈接和內容的網頁排序算法[5]：Average算法和Sim算法等。
針對HITS算法發生的“主題漂移”的現象，本文在鏈接分析的基礎上引入了網頁內容信息[3]的判斷，提出了一種改進的HITS算法。
3.1? 改進思想
HITS 算法中, 構造一個基本集R集, 然后通過基本集擴展到B集, 形成整個Web 子圖。這樣做的原因是R集可能并不包含真正的用戶需要的頁面。例如搜索關鍵詞“搜索引擎”時, 文本搜索引擎返回的頁面通常不會包含Google、Yahoo等搜索引擎的頁面, 因為它們的頁面通常不會出現搜索引擎這樣的字眼。這使得原本很重要的頁面不能被包含在第一步得到的結果中。B集可以解決這個問題, 因為可以通過R集中網頁的鏈接來得到需要的網頁。但是也正是由于HITS 算法的這種特性使得它在構造B集時, 常常會引入過多與主題無關的頁面, 它們有些還由于擁有互相指向的鏈接而擁有較高的權威值。如果控制B集構造時的半徑, 可能得不到足夠的頁面,B集半徑足夠大可能會找到真正的合適頁面, 但是這時也已經引入了過多的無關頁面。
針對此，本文在鏈接分析的基礎上引入網頁內容信息[2]的判斷，通過計算B集中每一網頁與主題的相似度，設定閾值去掉相似度較低的頁面，然后將網頁的相似度用于最終的迭代計算，有效地去除“主題漂移”現象。
改進算法采用的模型和技術與當前Web檢索系統大多采用的向量空間模型(VSM)和技術有最大的兼容性，以便算法的有效實現以及與當前檢索系統的有效集成。改進后的算法主要包括3個過程：(1)有效地選取基集；(2)擴展基集時通過余弦公式對網頁內容信息進行判斷，使擴展后的網頁與查詢主題有最大的相關性，從而避免“主題漂移”；(3)迭代計算與返回結果[4-8]。
3.2? 算法詳細步驟
(1)合理地獲取基集，構造鏈接結構子圖G，對于圖G中的每一個節點V(網頁)有兩個值, 分別是hub值與authority 值, 用H(v),A(V)表示, 把所有節點的authority和hub值定義為向量形式，即：a=(a1,a2,...,an)和h=(h1,h2,...,hn)V=1,2,3..N;N為G中節點(網頁)數量。
(2)對H(v),A(v)進行初始化, 使得H(v) = 1，A(v) = 1。
(3)內容匹配：將B集中擴展得到的網頁看做一篇文檔，把文檔d和查詢式q表示成向量形式(d =(d 1,d2…dn)di代表第i篇文檔q=(q1,q2…qn)qi代表查詢主題中第i個關鍵詞)。文檔d(document)可看成是由相互獨立的若干詞條(term) ( t1,t2...tn)組成,對于每一詞條ti,根據詞條在文檔中隱含的語義及重要程度賦以一定的權值Wti , 則文檔的特征向量為(Wt1,Wt2...Wtn), 通過Similarity(di,Q) 余弦公式來表示第i篇文檔與查詢條件Q的相關度。
?
?
并以此作為權重賦予相應的節點(網頁)，Web節點的內容與查詢主題相關度越大，對應的權值也越大。這樣，鏈接結構圖就成了節點帶權的有向圖，使用這樣的權重來合理控制鏈接分析時節點對authority/hub值的影響，最終有效控制主題偏移現象。
4? 實驗結果與分析
在測試文檔集的選擇上，選用BORODIN A等人提供的Web文檔集[9](包括“Abortion”、 “Genetic”、 “Movies”、“Harvard”等關鍵詞依次對應的2 849，2 613，5 613,1 583個網頁)對改進的HITS算法和原HITS算法進行了實驗比較，實驗數據如表1所示。
?
通過實驗數據，對搜索出來的前30位的網頁進行相關率比較如圖1所示。在前30位網頁中發現原HITS算法將許多與查詢主題無關的網頁排了進來，使得網頁相關率較低；而改進后的HITS算法排在前30內的網頁相關率明顯高于原HITS算法。
?
?
再對獲取網頁的前10位進行權威度比較(這里網頁權威度是根據大多數人的評價得來的)，發現原HITS算法由于獲取相關網頁的準確率不高，使得獲取權威網頁的總體效果也不佳，而改進后的HITS算法明顯優于原HITS算法，如圖2所示。
?
?
以上結果說明，在原HITS算法中出現了TKC問題，排序較高的相關頁面中存在與查詢主題無關的網頁，而改進的算法則有效地控制了TKC問題，通過加入對文本內容的分析使排序權值較高的頁面與查詢主題緊密相關。
文章在深入研究了Web挖掘和Web鏈接結構分析的基礎上，重點分析了主題提取算法HITS的基本思想和算法步驟。針對HITS算法基于純鏈接，容易發生“主題偏移”現象，本文從網頁文本內容著手，提出一種將網頁文本內容和鏈接結構相結合的改進HITS算法，并通過實驗結果證明了改進后算法的有效性。
參考文獻
[1]?王曉宇,周傲英.萬維網的鏈接結構分析及其應用綜述[J].軟件學報, 2003, 14( 10) : 1768-1780.
[2]?倪現軍. 結構挖掘中web有向圖模型的改進算法[J].微計算機信息,2007,12-3:163-165.
[3]?黃麗雯, 錢微. 多文檔文本摘要的一種改進HITS算法[J].計算機應用,2006,26(11):2625-2627.
[4] ?CHAKRABARTI S,DOM B,RAGHAVAN P,et al.Automatic resource compilation by analyzing hyperlink structure and associated text[J].Computer Networks and ISDN Systems,1998,30(4):1-7.
[5] ?GEVREY J,RUGER S.Link-based approaches for text retrieval.Proceedings of TREC-10,NIST(Gaithersburg,MD,13-16Nov2001)[M].NIST Special Publication,2002.
[6] XINGW , GHORBANIA. Weighted pagerank algorithm[C].Proceedings of the Second Conference on Communication Networks and Services Research, 2004: 305- 314.
[7] ?KOSALA R, BLOCKEEL H. Web mining research: A Survey. ACMSIGKDD, 2000(07).
[8] ?MIZUUCHI Y. Finding Context Paths for web pages[J]. InProc. of ACM Hypertext, 1999,2(2)：13-22.
[9] ?BORODIN A, ROBERTS G O, Rosenthal J S, etal.Finding authorities and hubs form link structures on the World Wide Web[C].In Web,Hong Kong,China,May 2001.