基于Ｗｅｂ結構挖掘的ＨＩＴＳ算法研究

摘要：隨著網絡與數據挖掘技術的發展，Web數據挖掘得到了較多的研究。本文從Web結構挖掘的角度出發，在分析了Web結構挖掘技術的基礎上，研究了HITS算法。針對HITS算法的多主題性、無關頁面、無關鏈接等問題，提出了HITS算法改進算法。

關鍵詞：Web結構挖掘；HITS算法；根集向量投影法；基本集縮減法

中圖分類號：TP312文獻標識碼：A文章編號：1009-3044(2008)20-30218-03

Research on the Algorithm of HITS Based on Web Structure Mining

LIU Jun，WANG Xiao-Ling，TANG Quan

(School of Information Science and Engineering，Central South University，Changsha 410083，China)

Abstract:With the development of the internet and the data mining，more and more research work are come out with the Web data mining.From the direction of Web structure mining and on the base of analyzing the technology of Web structure mining， this paper studies the algorithm of HITS．Comes up with the improvement algorithm of the HITS algorithm aim for the multi—subjects of the algorithm of HITS，unrelated pages，irrelevant links and so on．

Key words:Web structure mining;HITS algorithm;Root-set eigenvector projection method;Base-set downsizing method

1 引言

最近幾年，許多研究者發現，WWW上超鏈結構是個非常豐富和重要的資源，如果能夠充分利用的話，可以極大的提高檢索結果的質量。基于這種超鏈分析的思想，Sergey Brin和Lawrence Page在1998年提出了PageRank算法 ，同年J. Kleinberg提出了HITS算法，其它一些學者也相繼提出了另外的鏈接分析算法，如SALSA，PHITS，Bayesian等算法。這些算法有的已經在實際的系統中實現和使用，并且取得了良好的效果。

2 Web結構挖掘簡述

Web結構挖掘的目的是發現頁面的結構(文檔內部結構)和Web的結構(文檔間超鏈結構)，利用這些結構所蘊涵的信息可以幫助我們發現很多有用的模式或知識。如果兩篇文獻具有同被引(Co-citation)和耦合(Coupling)等關系，則這兩篇文獻具有相互關系或相互聯系。充分利用這些關系，能夠客觀地反映科學活動中許多隱蔽的和深層次的相關關系，顯示出有用的結構[1]。

M．R．Henzinger認為目前的Web超鏈接分析大多基于以下兩條基本假設[2]：

假設1：從Web網頁A指向網頁B的超鏈接是網頁A作者對網頁B的推薦。

假設2：如果一條超鏈接將網頁A和網頁B相互鏈接起來，則網頁A和網頁B可能有共同的主題(Topic)。

基于上面的兩個基本假設，我們還可以引申出以下幾個假設[2-4]：

假設3：一個頁面被多次引用，即很多頁面有指向它的鏈接，則這個頁面很重要。

假設4：一個頁面盡管沒有被多次引用，但被一個重要頁面引用，則這個頁面也可能很重要。

假設5：一個頁面的重要性被均勻分布并傳遞到它所引用的頁面。

假設6：如果頁面P和q同被引，則它們可能是相關的， 同被引度越大，相關度越大。

假設7：如果頁面P和q耦合，則它們可能是相關的，耦合度越大，相關度越大。

3 HITS算法簡述

J. Kleinberg提出的HITS算法中引入了Hub網頁，Hub網頁是提供指向權威網頁鏈接集合的WEB網頁。一般來說，好的Hub網頁指向許多好的權威網頁；好的權威網頁是有許多好的Hub網頁指向的WEB網頁。這種Hub與Authorities網頁之間的相互加強關系，可用于權威網頁的發現和WEB結構和資源的自動發現，這就是Hub/Authority方法的基本思想。

HITS（Hyperlink－Induced Topic Search）算法是利用Hub/Authority方法的搜索方法，算法如下：

(1)將查詢q提交給傳統的基于關鍵字匹配的搜索引擎．搜索引擎返回很多網頁，從中取前n個網頁作為根集(root set)，用S表示。

S滿足如下3個條件：

(1)S中網頁數量相對較小；

(2)S中網頁大多數是與查詢q相關的網頁；

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

(2)通過向S中加入被S引用的網頁和引用S的網頁將S擴展成一個更大的集合T．

(3)以T中的Hub網頁為頂點集Vl，以權威網頁為頂點集V2，Vl中的網頁到V2中的網頁的超鏈接為邊集E，形成一個二分有向圖SG＝(V1，V2，E)。對V1中的任一個頂點v，用h(v)表示網頁v的Hub值，對V2中的頂點u，用a(u)表示網頁的Authority值。開始時h(v)＝a(u)＝1，對u執行I操作修改它的a(u)，對v執行O操作修改它的h(v)：

如此不斷的重復計算下面的操作I，O，直到a（u），h（v）收斂。

4 對HITS算法的改進研究

4.1 利用根集向量投影法對HITS算法進行改進

Authorities集中到一些鏈接稠密的非相關網頁的現象被稱為主題偏移問題，為了弄清楚HITS算法中存在的這個問題，本文對Kleinberg的算法進行了細致的分析，圖1是對該問題的一個形象化的描述。

在圖1中，●和★均表示網頁，連線表示網頁之間存在鏈接。可見，正是因為由★所表示的那組內部鏈接稠密的網頁的存在，使得該組網頁的權值會在HITS算法的運算過程中不公平的迅速增加，從而使得運算結果不可避免的向該組網頁集中，這時，就很容易出現HITS算法提取結果與原始主題嚴重偏移的情況了。

圖1 HITS算法中存在的問題

主題偏移問題頻繁出現在信息回收領域中。為了解決這一問題，Saeko等[5]提出了一種基于鏈接分析的改進手段:根集向量投影法。

根集向量投影法對HITS算法的改進是在特征值計算的階段進行的。

首先對矩陣ATA進行分析，在該矩陣中，(i，j)元素的計算過程可以由以下算式表示：

由于（A）ij表示的是有網頁i對網頁j的引用狀況，因此（ATA）ij就表示了到網頁i和j的鏈接數目。

假定V表示對應基本集的n維歐幾里德空間，w表示對應根集的r維子空間，我們將后者稱為根集子空間。

將所有的特征值按降序排列為λ1，λ2， λ3，…，λn。其對應的特征向量經歸一化后分別為е1，е2，е3，…，еn，于是，矩陣ATA可以被表示為（假定所有的特征值都不同）：

圖2所顯示的情形是authorities并沒有如期望的那樣向原始查詢主題集中。(雖然在圖2中為了清晰簡明的說明問題，將e1， e2作為二維向量處理，但在實際中，它們顯然應該是多維的)。

在圖2中，雖然λ1>λ2，但是凡所對應的特征向量e1中的大部分元素都在W的垂直方向，這實際上意味著與e2比較，el中更多的元素都是在將根集向基本集的擴展過程中添加進來的，這些網頁所擁有的大量鏈接都不是來自根集的(該組網頁在圖1中由x 表示);另一方面，e2與根集子空間的關系更為密切，這說明e2中有著更多的來自根集中的鏈接。

從主特征向量中所提取的是基本集中鏈接關系最為稠密的權威網頁組，事實上，也可以在非主特征向量中選擇具有較大絕對值的元素，從而獲取不同的權威網頁組，這樣就會獲得不同的結果。只是這樣一來所獲得的權威網頁組，其內部鏈接關系的稠密程度就不如主特征向量的結果了。主題偏移現象的發生，就是因為傳統HITS算法從主特征向量中所提取的權威網頁組，雖然其內部鏈接關系最為稠密，但是該組網頁與根集的關系卻很小，即和原查詢主題的關聯程度非常小.為了避免這種情形的發生，就應該考慮從其它非主特征向量中提取不同的、雖然內部鏈接并不是最為稠密、但與根集關系卻更為密切的權威網頁組。因此，當出現了如圖2所描繪的情況時，應選擇從e2中提取權威網頁。

根據以上分析，可以對原來HITS算法的第四步進行如下改動，從而得到根集向量投影法:

(1)根據S構造n×n的鄰接矩陣A及其轉置矩陣AT，計算其每個特征值，所對應的特征向量el，e2 ， еn，并將它們歸一化;

(2)將每一個特征向量的各項元素均取其絕對值，然后在根集子空間W上進行投影P，然后進行比較，從中找到使‖Pλiеi‖的值達到最大的特征向量е*;

文獻[6]中曾指出，在特征向量中具有較大絕對值的負元素和非負元素都應該作為權威網頁被提取出來，只不過兩者分別屬于不同的具有稠密鏈接關系的權威網頁組。因此，在根集向量投影法的第四步(b)操作中，首先將特征向里中的各項元素均取其絕對值，然后再在根集子空間上進行投影。

顯然，使用根集向量投影法對HITS算法進行改進之后，權威網頁的提取效果要大大優于使用傳統HITS算法的效果。

從中可以得到這樣一個結論:利用根集向量投影法可以有效的抑制與查詢主題無關的內部鏈接稠密網頁組的提取，使提取結果更為向根集靠近，從而避免了傳統 HITS算法中主題偏移現象的產生。

4.2 利用基本集縮減法對HITS算法進行改進

基本集中包含了大量的互不相關的網頁。由于被提取出來的Web Communities應該具有很多鏈向/來自根集網頁的鏈接，因此對基本集還可以進行進一步精簡，一方面，剔除掉與根集關系不大的網頁可以對主題偏移問題加以抑制;另一方面，這樣做還可以大大減少運算量。

為了達到這一目的，可以對HITS算法中的第二步加以改進，從而改進基本集的獲取方式，由此便得到了一種新的改進手段:基本集縮減法。

基本集縮減法通過對鏈向/來自根集中網頁的鏈接數目加以考慮來對基本集進行縮減，其對傳統HITS算法的第二步改進如下:

(1)將根集R的規模擴展至n，形成基本集S，擴展規則為：將根集中網頁所鏈接的全部網頁加入進來，并加入最多d個鏈接到根集R中網頁的Web網頁;

(2)對已獲取的基本集進行進一步篩選，只選取那些鏈向不少于k個根集網頁和被不少于k 個根集網頁所鏈向的網頁，由此獲取縮減后的基本集。

隨著基本集規模的縮減，鄰接矩陣的階數也大大減小，因此該方法可以有效的降低特征值的計算開銷。

縮減基本集時的計算開銷可以按如下方式估算：考慮一個對應S的n×n鄰接矩陣，選取那些鏈向多個根集R中元素的網頁意味著從n-r行中選取那些前r個元素之和大于或等于2的行，因此，所需的計算開銷為r(n-r)。同理，選取那些被多個根集網頁所鏈向的網頁也需要相同的計算開銷。

事實上，使用這個方法一般可以使基本集減小為原來的二分之一以下，考慮到計算關于Web數據挖捆中HITS算法的研究特征向量的開銷為n3，即使加上2r(n-r)的額外開銷，使用基本集縮減法仍然可以大大減少計算開銷。

基本集縮減法也可以在很大程度上抑制主題偏移現象的產生，但是效果不如根集向量投影法，在某些場合下，采用基本集縮減法仍有可能將少t的與主題不相關的網頁作為權威頁面提取出來。但是，無論如何，采用基本集縮減法可以大大減少特征值計算時的運算量，這也是該算法的最大優點。

4.3 將根集向量投影法與基本集縮減法相結合

基本集縮減法剔除了那些具有少于k個鏈向/來自根集網頁的鏈接的網頁。一般來說，k設的越小，解決主題偏移問題的效果就越差;但是如果k設的過大，則可能會誤剔除那些本該包含進Web communities的網頁。怎樣設定一個合理的k值是基本集縮減法的一大難點。

為了盡可能的解決這一難點，可以在應用基本集縮減法(k=2)之后的基礎上再使用根集向量投影法。這相當于:第一步首先剔除基本集中那些與根集明顯不相關的網頁，然后再使用投影法從對應縮減后的基本集Y'的歐幾里德空間向根集子空間W進行投影。

由于將根集向量投影法和基本集縮減法相結合后，首先對基本集進行了縮減，然后又使用投影法對各個特征向量在根集子空間上進行投影比較來提取權威網頁，關于Web數據挖掘中HITS算法的研究因此該算法不僅可以像根集向量投影法一樣有效抑制不相關內部鏈接稠密網頁組的提取，而且也具備基本集縮減法大大縮小運算量的特點，同時還避免了基本集縮減法中因為k值取得過小而造成的主題偏移現象。

5 結束語

本文在對HITS算法進行改進的過程中，首先分析了傳統算法容易出現主題偏移現象的原因是由于與查詢主題不相關的內部鏈接稠密網頁組被選中用以提取authorities，接著針對這一問題，采用根集向量投影法對HITS算法進行改進，使搜索結果向根集集中;然后為了減少基本集鄰接矩陣特征值和特征向量的運算量，使用基本集縮減法，根據各網頁與根集元素之間的鏈接數量對基本集進行了進一步提取，使其規模大大縮小，從而減少了運算量。針對基本集縮減法系數較難確定，對主題偏移現象的抑制不如根集向量投影法有效的特點，將這兩種算法結合起來進行權威網頁搜索，取得了良好的效果。

參考文獻：

[1] Adamic L A， Huberman B A．The Web's Hidden Order.Communication of the ACM，2001，44 (9):55-59.

[2] Herzinger M R.Hyperlink Analysis for the Web.IEEE Internet Computing，2001，5(1):5-50.

[3] Brin S，Page L.The Anatomy of a Large-Scale Hypersexual Web Search Engine. Http://www7.scu.edu.au/programme/fullpapers/1921/com1921.htm.

[4] Kleinberg J M.Authoritative Source In a Hyperlinked Environment.Journal of the ACM，1999，46 (5):6O4-632.

[5] Saeko Nomura，Satoshi Oyama，Toru Ishida，Tetsuo Hayamizu.Analysis and Improvement of HITS Algorithm for Detecting Web Communities. Proceedings of the 2002 Symposium on Applications and the Internet (SAINT' 02)，2002.

[6] Carriisre J， Kazman R. WebQuery: searching and visualizing the Web through connectivity [0L]. http://www.cgl.uwaterloo.ca/Projects/Vanish/Webquery-l.html，1997.