基于Web結構挖掘中HITS算法的研究

王月琦

[摘 要]HITS算法是基于鏈接分析的一種權威資源提取算法。相對于其他Web結構挖掘算法來說，HITS算法優勢非常明顯。針對HITS算法的缺陷，可以使用基本集縮減法對HITS算法進行改進。

[關鍵詞]Web結構挖掘；HITS算法；數據挖掘

[中圖分類號] G633.67 [文獻標識碼] A [文章編號] 1674-6058（2018）15-0036-02

Web擁有海量的信息，為人們提供豐富多樣的信息服務。隨著信息技術的發展和Web信息量的指數級增長，快速準確地從Web網絡中獲取信息變得愈發重要。因此，如何從Web網絡中尋找信息，提取出有價值的內容，已成為當前Web結構挖掘的重要研究課題。用戶不但需要獲取Web頁面，還希望查找的頁面質量高，即為權威頁面。HITS算法是基于鏈接分析的一種權威資源提取算法。而作為Web數據挖掘的重要內容，Web結構挖掘的關鍵在于信息檢索。在Web結構挖掘領域中，鏈接分析的作用非常重要，主要用于分析超鏈接以確定權威信息源。本文研究HITS算法，分析了傳統HITS算法存在的問題，并在此基礎上運用基本集縮減法優化HITS算法，從而實現更有效率的權威網頁檢索。

一、HITS算法基本原理

作為數據提取的典型算法之一，HITS算法的應用和需要檢索的主題有直接關系。HITS算法的基本思想是先提取出Web鏈接結構中用戶需要檢索的相關頁面，組成Web鏈接結構子圖，再運用HITS算法分析計算這個鏈接結構子圖。而Web鏈接主要有以下幾點特征：（1）有些鏈接的作用是廣告或導航，只有具有注釋性的鏈接才能用于判斷權威性。（2）由于商業競爭，指向Web網頁競爭領域的權威網頁的情況很少。（3）一般來說，權威網頁都缺少明顯的描述，如百度搜索主頁不會給出明確的有關Web搜索引擎的描述信息。

由此可見，Web鏈接的實際情況與平均分配權值不相符。因此，HITS算法中加入了網頁的另一種類型，即Hub網頁。指向權威網頁的鏈接都集中在Hub網頁，雖然Hub網頁本身并沒有什么網頁指向它，但Hub網頁提供了指向權威網頁的鏈接集合。如，課程主頁上的參考文獻列表。通常情況下，一個優秀的Hub網頁會同時指向數量眾多的權威網頁，同時一個優秀的權威網頁會有很多Hub網頁指向它，而頁面的Authority就等于指向該頁面的所有Hub的和；頁面的Hub等于它指向的頁面的Authority之和。Hub和Authority網頁之間的關系，可用來自動查找權威網頁和Web結構和資源。這就是HITS算法的基本原理。

二、傳統HITS算法存在的問題

傳統的HITS算法主要存在以下幾個問題：第一，下載、分析網頁包含的鏈接并且排除重復的鏈接需要耗費大量的時間，計算量比PageRank算法大。第二，某些情況下，大量主機A上的網頁會指向另一臺主機B上的某一個特定網頁，從而使主機A上的網頁Hub值和主機B上網頁的Authority增加，反之也一樣。HITS算法假設不同的組織或個人決定某個網頁的權威值，上述的情況對主機A和B上網頁的Hub和Authority值造成影響。第三，網頁中包含的無關鏈接網頁中一些無關的鏈接對Hub和Authority值的計算造成影響。網頁在制作的過程中往往會被加入一些無關鏈接，如廣告、友情鏈接，這些都對HITS算法的精確度有影響。第四，主題漂移是HITS算法存在的最大問題。Web鏈接結構的自組織性，使WWW中主題一樣或相關的頁面通過超鏈接形成一個個緊密鏈接區域。當用戶查詢范圍較寬的定義主題或者多個主題時，鏈接結構子圖會因為多個子主題對應多個信息形成多個相對緊密鏈接區域。而HITS算法屬于迭代算法，因此，緊密鏈接區域的頁面權值必然會增大，從而干擾檢索的精確度，使用戶獲得的結果發生漂移，這種現象叫作主題漂移。第五，運用HITS算法查詢主題時，可能會出現主題泛化的現象，也就是說結果中出現了新的與查詢無關的主題。

三、利用基本集縮減法優化HITS算法

在HITS算法的基本集中含有很多互相之間毫無關聯的網頁，因此，需要對基本集進行精簡。可以通過剔除與根集沒什么關系的網頁，從而有效抑制主題偏移問題，同時大大減少運算量。為了實現這個目的，可以對HITS算法進行優化，以優化基本集的獲取方式，從而獲得新的HITS算法優化方法——基本集縮減法。所謂基本集縮減法，是指通過考慮指向或來自根集中網頁的鏈接數目縮減基本集，再從中提取適當的Web Communities。基本集縮減法的優化對象是傳統HITS算法的第二個步驟：通過向S中加入被S引用的網頁和引用S的網頁，將S擴展成一個更大的集合T。改進的HITS算法第二步驟是：首先加入所有的根集網頁指向的網頁以及最多d個指向根集R中網頁的Web網頁，將根集R的規模擴展至n，構建基本集S，再篩選已建立的基本集S，只選擇指向至少k個根集網頁以及被至少k個根集網頁所鏈向的網頁，從而實現基本集的縮減。由此，可以總結出運用基本集縮減算法提取Authoritiy網頁的基本步驟：（1）在搜索引擎中輸入特定關鍵詞，檢索到的r個等級的結果網頁構成根集Rσ。（2）擴展根集R的規模至n，構建基本集Sσ，加入所有的根集網頁指向的網頁以及最多d個指向根集R中網頁的Web網頁，將根集R的規模擴展至n，構建基本集S，再篩選已建立的基本集S，只選擇指向至少k個根集網頁以及被至少k個根集網頁所鏈向的網頁，從而實現基本集的縮減。（3）用G（Sσ）表示根據基本集Sσ中的網頁鏈接關系推導而來的結構子圖，則G（Sσ）中包含內鏈、外鏈兩種鏈接。所謂外鏈，是指域名不同的Web網頁之間的鏈接，內鏈是指域名相同的網頁之間的鏈接，在實際情況下，只考慮外鏈，而忽略基本集Sσ中的所有內鏈。（4）結合基本集Sσ構造鄰接矩陣矩陣A和轉置矩陣AT，計算其每個特征值及所對應的特征向量，并歸一化。（5）歸一化后的特征向量中將絕對值較大的元素作為authorities返回。基本集的縮減，使得鄰接矩陣階數大為減少，因此，基本集縮減法能夠有效降低特征值的計算量。

基本集縮減下的計算量可以采用以下方式進行預估：從與基本集S對應的一個n*n鄰接矩陣選擇指向多個根集R中元素的網頁，表示從n—r行中選取前r個元素之和大于或等于2的行。因此，可預估其計算量為r（n-r）。同樣的道理，選擇被多個根集網頁指向的網頁需要的計算量是一樣的。運用該方法可以將基本集縮減為原先的一半。考慮到計算關于Web數據挖掘中HITS算法的研究特征向量的計算量為n3，即便加上2r（n-r）的額外計算量，運用基本集縮減法還是可以有效減少計算量。同時基本集縮減法能夠有效抑制主題偏移問題。

綜上所述，HITS算法雖然存在一些問題，但是相對于其他Web結構挖掘算法來說，優勢非常明顯。HITS算法的基本思想以頁面之間的鏈接關系為基礎。本文從Web結構挖掘的本質入手，分析了HITS 算法的基本思想，探討了HITS算法的基本原理。但是由于篇幅限制，無法進一步深入研究其算法，在對HITS算法的研究改進過程中，首先分析傳統HITS算法容易出現的問題，針對主題偏移現象和減少基本集鄰接矩陣特征值和特征向量的計算量，提出使用基本集縮減法對HITS算法進行改進，根據網頁與根集元素之間的鏈接數量進一步提取基本集，使基本集規模進一步縮減，從而使搜索結果更加集中于根集，有效減小計算開銷，從而有效提升HITS算法的計算效率和精確度。

[ 參 考 文 獻 ]

[1] 劉軍.基于Web結構挖掘的HITS算法研究[D].長沙：中南大學， 2008.

[2] 盧虹宇.Web結構挖掘中HITS算法的研究[D].成都：西南交通大學， 2008.

[3] 范聰賢，徐汀榮，范強賢.Web結構挖掘中HITS算法改進的研究[J]. 微計算機信息， 2010（3）.

（責任編輯 周侯辰）