趙炎

摘要：信息技術的發(fā)展催生了更多更先進的數(shù)據(jù)挖掘技術，其中基于Web結(jié)構的數(shù)據(jù)挖掘技術獲得業(yè)界普遍關注。文章從Web結(jié)構挖掘深入研究運用Hyperlink-Induced Topic Search（HITS）算法挖掘web數(shù)據(jù)，從而準確判斷web鏈接頁面的重要性，分析了HITS算法的基本思想和存在的問題，并提出了HITS算法的改進方案。

關鍵詞：Web結(jié)構挖掘；HITS算法；數(shù)據(jù)挖掘

Web擁有海量的信息，為人們提供豐富多樣的信息服務。隨著信息技術的發(fā)展和Web信息量的指數(shù)級增長，快速準確地從Web網(wǎng)絡中獲取信息變得愈發(fā)重要。因此，如何從海量的Web網(wǎng)絡中尋找有價值的數(shù)據(jù)信息已然是現(xiàn)階段Web結(jié)構挖掘的一個非常重要的研究課題。在實際應用場景中，用戶往往需要在獲得Web頁面的基礎上快速找到高質(zhì)量的所謂權威頁面。在Web結(jié)構挖掘中鏈接分析的作用非常重要，而以鏈接分析為基礎建立的HITS算法能夠高效地篩選出Web頁面中的權威資源。常常用于分析超鏈接以確定權威信息源。本文研究HITS算法，分析了傳統(tǒng)HITS算法存在的問題，并在此基礎上運用基本集縮減法優(yōu)化HITS算法，從而實現(xiàn)更有效率的權威網(wǎng)頁檢索，提高提高算法的效率和靈活性。

一、HITS算法基本原理

作為數(shù)據(jù)提起算法的典型算法之一，HITS算法的應用和需要檢索的主題有直接關系。HITS算法的基本思想是先提取出Web鏈接結(jié)構中用戶需要檢索的相關頁面，組成Web鏈接結(jié)構子圖，再運用HITS算法分析計算這個連接結(jié)構子圖。而Web鏈接主要有以下幾點特征。

其一，有些鏈接的作用是廣告或?qū)Ш?，只有具有注釋性的鏈接才能用于權威性的評判。

其二，商業(yè)競爭因素的影響下，權威網(wǎng)頁鏈接至Web網(wǎng)頁競爭領域的情況很少。

其三，一般來說，權威網(wǎng)頁都缺少明顯的描述，如百度搜索主頁并不會將與Web信息檢索引擎有關的具體描述信息呈現(xiàn)給用戶。

可見，Web鏈接的實際情況與平均分配權值不相符。因此，在HITS算法中新增了一種新的網(wǎng)頁類型，也就是Hub網(wǎng)頁。Hub網(wǎng)頁集中了鏈接至權威網(wǎng)頁的鏈接。實際上，很少有網(wǎng)頁指向Hub網(wǎng)頁，但是Hub網(wǎng)頁中集中了鏈接至權威網(wǎng)頁的鏈接。如，排列在課本主頁上的一列參考文獻。在常規(guī)情況下，高質(zhì)量的Hub網(wǎng)頁指向了大量的權威網(wǎng)頁，而一個高質(zhì)量的權威網(wǎng)頁擁有許多指向它的Hub網(wǎng)頁，但是一個頁面的authority等于鏈接至這個頁面的全部hub的和；一個頁面的hub等于它指向的頁面的全部authority的和。而Hub和Authority網(wǎng)頁之間的關系是自動查詢權威網(wǎng)頁和Web結(jié)構和資源的重要工具。這就是HITS算法的基本原理。

二、傳統(tǒng)HITS算法存在的問題

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

三、利用基本集縮減法優(yōu)化HITS算法

在HITS算法的基本集中含有很多互相之間毫無關聯(lián)的網(wǎng)頁，因此，需要對基本集進行精簡?？梢酝ㄟ^剔除與根集沒什么關系的網(wǎng)頁，從而有效抑制主題偏移問題，同時大大降低運算量。為了實現(xiàn)這個目的，可以對HITS算法進行優(yōu)化，以優(yōu)化獲取基本集的方式，產(chǎn)生新的HITS算法改進方案——基本集縮減法。所謂基本集縮減法，是指通過考慮指向或來自根集中網(wǎng)頁的鏈接數(shù)目縮減基本集，再從提取適當?shù)腤eb Communities?；炯s減法向S中加入被S引用的網(wǎng)頁和引用S的網(wǎng)頁將S擴展成一個更大的集合T。HITS算法改進：首先加入所有的根集網(wǎng)頁指向的網(wǎng)頁以及最多d個指向根集R中網(wǎng)頁的Web網(wǎng)頁，將根集R的規(guī)模擴展至n，構建基本集S，再篩選已建立的基本集S，只選擇指向至少k個根集網(wǎng)頁以及被至少k個根集網(wǎng)頁鏈向的網(wǎng)頁，從而實現(xiàn)基本集的縮減。由此，可以總結(jié)出采用基本集縮減算法提取authorities網(wǎng)頁的步驟。

第一步，輸入特定的關鍵詞，檢索到的r個等級的結(jié)果網(wǎng)頁構成根集Rσ。

第二步，擴展根集R的規(guī)模至n，構建基本集Sσ，加入所有的根集網(wǎng)頁指向的網(wǎng)頁以及最多d個指向根集R中網(wǎng)頁的Web網(wǎng)頁，將根集R的規(guī)模擴展至n，構建基本集S，再篩選已建立的基本集S，只選擇指向至少k個根集網(wǎng)頁以及被至少k個根集網(wǎng)頁鏈向的網(wǎng)頁，從而實現(xiàn)基本集的縮減。

第三步，用G（Sσ）表示根據(jù)基本集Sσ中的網(wǎng)頁鏈接關系推導而來的結(jié)構子圖，則G（Sσ）中包含內(nèi)鏈、外鏈兩種鏈接。所謂外鏈是指域名不同的Web網(wǎng)頁之間的鏈接，內(nèi)鏈是指相同域名的網(wǎng)頁之間的鏈接，在實際情況下，只考慮了外鏈，而忽略基本集Sσ中的所有內(nèi)鏈。

第四步，結(jié)合基本集Sσ構造鄰接矩陣矩陣A和轉(zhuǎn)置矩陣AT，計算其每個特征值及所對應的特征向量。

第五步，特征向量歸一化后會以authorities值返回具有較大絕對值的元素。縮減基本集可以減少鄰接矩陣階數(shù)，降低特征值的計算量。

縮減基本集方法中的計算量的預估方法如下：從與基本集S對應的一個n*n鄰接矩陣中選取出鏈接至根集R中元素的多個網(wǎng)頁，從鄰接矩陣中從第n-r行中選擇前r個元素之和≥2的行，可預估其計算量為r（n—r）。與之類似，選取多個根集網(wǎng)頁鏈接的網(wǎng)頁所需計算量一樣。運用該方法可以將基本集縮減為原先的一半，考慮到計算與Web數(shù)據(jù)挖掘中HITS算法有關的特征向量的計算量為n3，計算是加上2r（n—r）的額外計算量，運用基本集縮減法還可以有效減少計算量，同時基本集縮減法能夠有效抑制主題偏移問題。

四、結(jié)語

綜上所述，HITS算法雖然存在一些問題，但是相對于其他Web結(jié)構挖掘算法來說，優(yōu)勢非常明顯。HITS算法的基本思想以頁面之間的鏈接關系為基礎。從Web結(jié)構挖掘的本質(zhì)入手，分析了HITS 算法的基本思想，探討了HITS算法的基本原理。但是由于篇幅限制無法進一步深入研究其算法，通過分析HITS算法的缺陷，找到相應的改進方案，進而提高HITS算法的使用效果，促進其在信息檢索領域的運用。在研究改進HITS算法的過程中，應該先深入研究傳統(tǒng)的HITS算法中存在的不足，針對主題偏移現(xiàn)象和減少基本集鄰接矩陣特征值和特征向量的計算量，提出使用基本集縮減法對HITS算法進行改進，根據(jù)網(wǎng)頁與根集元素之間的鏈接數(shù)量進一步提取基本集，使基本集規(guī)模進一步縮減，從而使搜索結(jié)果更加集中于根集，有效降低計算開銷，從而有效提升HITS算法的計算效率和精確度。

參考文獻：

[1]劉軍. 基于Web結(jié)構挖掘的HITS算法研究[D]. 中南大學， 2008.

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

[3]范聰賢， 徐汀榮， 范強賢. Web結(jié)構挖掘中HITS算法改進的研究[J]. 微計算機信息， 2010， 26（3）：160-162.

[4]馬潔. web結(jié)構挖掘中HITS算法的研究[J]. 軟件：電子版， 2013（5）.