王月琦

[摘 要]HITS算法是基于鏈接分析的一種權(quán)威資源提取算法。相對(duì)于其他Web結(jié)構(gòu)挖掘算法來說，HITS算法優(yōu)勢(shì)非常明顯。針對(duì)HITS算法的缺陷，可以使用基本集縮減法對(duì)HITS算法進(jìn)行改進(jìn)。

[關(guān)鍵詞]Web結(jié)構(gòu)挖掘；HITS算法；數(shù)據(jù)挖掘

[中圖分類號(hào)] G633.67 [文獻(xiàn)標(biāo)識(shí)碼] A [文章編號(hào)] 1674-6058（2018）15-0036-02

Web擁有海量的信息，為人們提供豐富多樣的信息服務(wù)。隨著信息技術(shù)的發(fā)展和Web信息量的指數(shù)級(jí)增長(zhǎng)，快速準(zhǔn)確地從Web網(wǎng)絡(luò)中獲取信息變得愈發(fā)重要。因此，如何從Web網(wǎng)絡(luò)中尋找信息，提取出有價(jià)值的內(nèi)容，已成為當(dāng)前Web結(jié)構(gòu)挖掘的重要研究課題。用戶不但需要獲取Web頁面，還希望查找的頁面質(zhì)量高，即為權(quán)威頁面。HITS算法是基于鏈接分析的一種權(quán)威資源提取算法。而作為Web數(shù)據(jù)挖掘的重要內(nèi)容，Web結(jié)構(gòu)挖掘的關(guān)鍵在于信息檢索。在Web結(jié)構(gòu)挖掘領(lǐng)域中，鏈接分析的作用非常重要，主要用于分析超鏈接以確定權(quán)威信息源。本文研究HITS算法，分析了傳統(tǒng)HITS算法存在的問題，并在此基礎(chǔ)上運(yùn)用基本集縮減法優(yōu)化HITS算法，從而實(shí)現(xiàn)更有效率的權(quán)威網(wǎng)頁檢索。

一、HITS算法基本原理

作為數(shù)據(jù)提取的典型算法之一，HITS算法的應(yīng)用和需要檢索的主題有直接關(guān)系。HITS算法的基本思想是先提取出Web鏈接結(jié)構(gòu)中用戶需要檢索的相關(guān)頁面，組成Web鏈接結(jié)構(gòu)子圖，再運(yùn)用HITS算法分析計(jì)算這個(gè)鏈接結(jié)構(gòu)子圖。而Web鏈接主要有以下幾點(diǎn)特征：（1）有些鏈接的作用是廣告或?qū)Ш?，只有具有注釋性的鏈接才能用于判斷?quán)威性。（2）由于商業(yè)競(jìng)爭(zhēng)，指向Web網(wǎng)頁競(jìng)爭(zhēng)領(lǐng)域的權(quán)威網(wǎng)頁的情況很少。（3）一般來說，權(quán)威網(wǎng)頁都缺少明顯的描述，如百度搜索主頁不會(huì)給出明確的有關(guān)Web搜索引擎的描述信息。

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

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

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

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

在HITS算法的基本集中含有很多互相之間毫無關(guān)聯(lián)的網(wǎng)頁，因此，需要對(duì)基本集進(jìn)行精簡(jiǎn)。可以通過剔除與根集沒什么關(guān)系的網(wǎng)頁，從而有效抑制主題偏移問題，同時(shí)大大減少運(yùn)算量。為了實(shí)現(xiàn)這個(gè)目的，可以對(duì)HITS算法進(jìn)行優(yōu)化，以優(yōu)化基本集的獲取方式，從而獲得新的HITS算法優(yōu)化方法——基本集縮減法。所謂基本集縮減法，是指通過考慮指向或來自根集中網(wǎng)頁的鏈接數(shù)目縮減基本集，再?gòu)闹刑崛∵m當(dāng)?shù)腤eb Communities。基本集縮減法的優(yōu)化對(duì)象是傳統(tǒng)HITS算法的第二個(gè)步驟：通過向S中加入被S引用的網(wǎng)頁和引用S的網(wǎng)頁，將S擴(kuò)展成一個(gè)更大的集合T。改進(jìn)的HITS算法第二步驟是：首先加入所有的根集網(wǎng)頁指向的網(wǎng)頁以及最多d個(gè)指向根集R中網(wǎng)頁的Web網(wǎng)頁，將根集R的規(guī)模擴(kuò)展至n，構(gòu)建基本集S，再篩選已建立的基本集S，只選擇指向至少k個(gè)根集網(wǎng)頁以及被至少k個(gè)根集網(wǎng)頁所鏈向的網(wǎng)頁，從而實(shí)現(xiàn)基本集的縮減。由此，可以總結(jié)出運(yùn)用基本集縮減算法提取Authoritiy網(wǎng)頁的基本步驟：（1）在搜索引擎中輸入特定關(guān)鍵詞，檢索到的r個(gè)等級(jí)的結(jié)果網(wǎng)頁構(gòu)成根集Rσ。（2）擴(kuò)展根集R的規(guī)模至n，構(gòu)建基本集Sσ，加入所有的根集網(wǎng)頁指向的網(wǎng)頁以及最多d個(gè)指向根集R中網(wǎng)頁的Web網(wǎng)頁，將根集R的規(guī)模擴(kuò)展至n，構(gòu)建基本集S，再篩選已建立的基本集S，只選擇指向至少k個(gè)根集網(wǎng)頁以及被至少k個(gè)根集網(wǎng)頁所鏈向的網(wǎng)頁，從而實(shí)現(xiàn)基本集的縮減。（3）用G（Sσ）表示根據(jù)基本集Sσ中的網(wǎng)頁鏈接關(guān)系推導(dǎo)而來的結(jié)構(gòu)子圖，則G（Sσ）中包含內(nèi)鏈、外鏈兩種鏈接。所謂外鏈，是指域名不同的Web網(wǎng)頁之間的鏈接，內(nèi)鏈?zhǔn)侵赣蛎嗤木W(wǎng)頁之間的鏈接，在實(shí)際情況下，只考慮外鏈，而忽略基本集Sσ中的所有內(nèi)鏈。（4）結(jié)合基本集Sσ構(gòu)造鄰接矩陣矩陣A和轉(zhuǎn)置矩陣AT，計(jì)算其每個(gè)特征值及所對(duì)應(yīng)的特征向量，并歸一化。（5）歸一化后的特征向量中將絕對(duì)值較大的元素作為authorities返回?；炯目s減，使得鄰接矩陣階數(shù)大為減少，因此，基本集縮減法能夠有效降低特征值的計(jì)算量。

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

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

[ 參 考 文 獻(xiàn) ]

[1] 劉軍.基于Web結(jié)構(gòu)挖掘的HITS算法研究[D].長(zhǎng)沙：中南大學(xué)， 2008.

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

[3] 范聰賢，徐汀榮，范強(qiáng)賢.Web結(jié)構(gòu)挖掘中HITS算法改進(jìn)的研究[J]. 微計(jì)算機(jī)信息， 2010（3）.

（責(zé)任編輯 周侯辰）