摘 要： HITS 算法是Web結(jié)構(gòu)挖掘中一種經(jīng)典的鏈接分析算法, 其主要問題是容易發(fā)生主題漂移,。針對這一問題,，提出了一種基于文本內(nèi)容和鏈接分析相結(jié)合的改進(jìn)算法。實(shí)驗(yàn)證明改進(jìn)后的算法提高了查詢結(jié)果的相關(guān)度, 降低了主題漂移的可能性,。
關(guān)鍵詞： HITS算法；主題漂移；權(quán)威網(wǎng)頁,；中心網(wǎng)頁
?
??? Internet是一個巨大、分布廣泛,、全球性的信息服務(wù)中心,，它提供了各種各樣的信息服務(wù)。但如何從Internet浩如煙海的信息中獲取所需信息或是從中提取有用知識,，一直是相關(guān)專家探究的問題,。將傳統(tǒng)的數(shù)據(jù)挖掘技術(shù)和Web結(jié)合起來，對Web進(jìn)行數(shù)據(jù)挖掘成為解決這一問題的重要途徑,。由于Web上的鏈接結(jié)構(gòu)含有非常豐富和重要的信息,，鏈接分析技術(shù)已經(jīng)被成功地用于分析Web超鏈接數(shù)據(jù)來確定權(quán)威信息源。而在各種對網(wǎng)頁進(jìn)行鏈接分析并提取主題的算法中,，HITS算法是最典型的,。
1 HITS算法
1.1? HITS算法的基本思想
HITS 算法[1]是一種Web結(jié)構(gòu)挖掘算法[1], 該算法基于用戶的查詢, 根據(jù)給定的查詢通過分析Web的前向鏈接和后向鏈接來發(fā)現(xiàn)一組相關(guān)網(wǎng)頁，從而找出Web集合中的authority網(wǎng)頁(與給定查詢主題的上下文最為相關(guān)并具有權(quán)威性的網(wǎng)頁)和hub網(wǎng)頁(提供指向權(quán)威網(wǎng)頁鏈接集合的Web網(wǎng)頁),。為每個網(wǎng)頁定義兩個度量值:權(quán)威權(quán)重(authority weight)和中心權(quán)重(Hub weight),，通過這兩個權(quán)重來判定該網(wǎng)頁對特定主題的重要性。
1.2? HITS算法的具體過程
整個HITS算法主要可以分為以下幾個步驟:
(1)在搜索引擎上輸入給定的關(guān)鍵詞, 以此搜索到的最前面的r個等級最高的查詢結(jié)果網(wǎng)頁作為根集(root set)R，R需滿足如下3個條件： ①R中網(wǎng)頁數(shù)量相對較小.②R中網(wǎng)頁大多數(shù)是與查詢關(guān)鍵詞q相關(guān)的網(wǎng)頁,。③R中網(wǎng)頁包含較多的權(quán)威網(wǎng)頁,。
(2)通過向R中加入被R引用的網(wǎng)頁和引用R的網(wǎng)頁將R擴(kuò)展成一個更大的基礎(chǔ)集合(base set)B。擴(kuò)展規(guī)則為：將根集中的全部網(wǎng)頁加入進(jìn)來, 并加入最多d個鏈接到根集R中的Web網(wǎng)頁,。
(3)以B中的Hub網(wǎng)頁為頂點(diǎn)集Vl,，以authority網(wǎng)頁為頂點(diǎn)集V2，Vl中的網(wǎng)頁到V2中的網(wǎng)頁的超鏈接為邊集E,，形成一個二分有向圖G＝(V1,，V2，E),。對V1中的任一個頂點(diǎn)v,，用h(v)表示網(wǎng)頁v的hub值，對V2中的頂點(diǎn)u,，用a(u)表示網(wǎng)頁的authority值,。假設(shè)Web鏈接結(jié)構(gòu)子圖G中包含n個節(jié)點(diǎn)(網(wǎng)頁)，對這n個節(jié)點(diǎn)加以編號：1,，2,，…，n,，這樣就可以為Web鏈接結(jié)構(gòu)子圖G定義一個n×n的鄰接矩陣A,，如果頁面i指向頁面j，則矩陣中的項(xiàng)(i, j)為1,，否則為0,。同樣把所有節(jié)點(diǎn)的authority和hub值定義為向量形式,，即：a=(a1,a2,...,an)和h=(h1,h2,...,hn),。
?
根據(jù)線性代數(shù)的理論，向量a和h經(jīng)過展開計(jì)算后,，會收斂至對稱矩陣ATA和AAT的主特征向量,。ATA的主特征向量代表權(quán)威網(wǎng)頁，而其主特征向量中數(shù)值越高代表網(wǎng)頁的權(quán)威權(quán)重也越高,；同樣,，AAT的主特征向量代表中心網(wǎng)頁，而其主特征向量中數(shù)值越高代表網(wǎng)頁的中心權(quán)重也越高,。通過以上過程可以看出,，經(jīng)過若干次迭代計(jì)算后, 即可得到每一頁面的authority 和hub?；疊中網(wǎng)頁的權(quán)威權(quán)重和中心權(quán)重從根本上說是由基集B中網(wǎng)頁的鏈接關(guān)系所決定的,，更具體地說，是由對稱矩陣ATA和AAT所決定的。
2?HITS算法中存在的問題
HITS算法雖然在某些查詢主題下能夠較為準(zhǔn)確地提取出權(quán)威網(wǎng)頁, 但在一些場合中仍會使得算法發(fā)生嚴(yán)重的“主題漂移”[2]的現(xiàn)象( authorities集中到一些鏈接稠密的非相關(guān)網(wǎng)頁的現(xiàn)象被稱為“主題漂移”) ,。該現(xiàn)象的出現(xiàn)說明在傳統(tǒng)HITS算法中仍存在一些缺點(diǎn), 這就要求對傳統(tǒng)HITS算法進(jìn)行改進(jìn), 以使其具有更為廣泛的適用性, 提高權(quán)威頁面搜索的效率,。
3?HITS算法的改進(jìn)
HITS算法遇到的問題，多是因?yàn)镠ITS是純粹的基于鏈接分析的算法,，沒有考慮文本內(nèi)容,。繼KLIINBERG J提出HITS算法以后，很多研究者對HITS進(jìn)行了改進(jìn),，提出了許多HITS的變種算法,，主要有IBM Almaden研究中心Clever搜索引擎的ARC(Automatic Resource Compilation)算法[4]和由GEVREY J和RUGER S于2002年提出來的兩個基于超鏈接和內(nèi)容的網(wǎng)頁排序算法[5]：Average算法和Sim算法等。
針對HITS算法發(fā)生的“主題漂移”的現(xiàn)象,，本文在鏈接分析的基礎(chǔ)上引入了網(wǎng)頁內(nèi)容信息[3]的判斷,，提出了一種改進(jìn)的HITS算法。
3.1? 改進(jìn)思想
HITS 算法中, 構(gòu)造一個基本集R集, 然后通過基本集擴(kuò)展到B集, 形成整個Web 子圖,。這樣做的原因是R集可能并不包含真正的用戶需要的頁面,。例如搜索關(guān)鍵詞“搜索引擎”時, 文本搜索引擎返回的頁面通常不會包含Google、Yahoo等搜索引擎的頁面, 因?yàn)樗鼈兊捻撁嫱ǔ２粫霈F(xiàn)搜索引擎這樣的字眼,。這使得原本很重要的頁面不能被包含在第一步得到的結(jié)果中,。B集可以解決這個問題, 因?yàn)榭梢酝ㄟ^R集中網(wǎng)頁的鏈接來得到需要的網(wǎng)頁。但是也正是由于HITS 算法的這種特性使得它在構(gòu)造B集時, 常常會引入過多與主題無關(guān)的頁面, 它們有些還由于擁有互相指向的鏈接而擁有較高的權(quán)威值,。如果控制B集構(gòu)造時的半徑, 可能得不到足夠的頁面,B集半徑足夠大可能會找到真正的合適頁面, 但是這時也已經(jīng)引入了過多的無關(guān)頁面,。
針對此，本文在鏈接分析的基礎(chǔ)上引入網(wǎng)頁內(nèi)容信息[2]的判斷,，通過計(jì)算B集中每一網(wǎng)頁與主題的相似度,，設(shè)定閾值去掉相似度較低的頁面，然后將網(wǎng)頁的相似度用于最終的迭代計(jì)算,，有效地去除“主題漂移”現(xiàn)象,。
改進(jìn)算法采用的模型和技術(shù)與當(dāng)前Web檢索系統(tǒng)大多采用的向量空間模型(VSM)和技術(shù)有最大的兼容性，以便算法的有效實(shí)現(xiàn)以及與當(dāng)前檢索系統(tǒng)的有效集成,。改進(jìn)后的算法主要包括3個過程：(1)有效地選取基集,；(2)擴(kuò)展基集時通過余弦公式對網(wǎng)頁內(nèi)容信息進(jìn)行判斷，使擴(kuò)展后的網(wǎng)頁與查詢主題有最大的相關(guān)性,，從而避免“主題漂移”,；(3)迭代計(jì)算與返回結(jié)果[4-8]。
3.2? 算法詳細(xì)步驟
(1)合理地獲取基集,，構(gòu)造鏈接結(jié)構(gòu)子圖G,，對于圖G中的每一個節(jié)點(diǎn)V(網(wǎng)頁)有兩個值, 分別是hub值與authority 值, 用H(v),A(V)表示, 把所有節(jié)點(diǎn)的authority和hub值定義為向量形式，即：a=(a1,a2,...,an)和h=(h1,h2,...,hn)V=1,2,3..N;N為G中節(jié)點(diǎn)(網(wǎng)頁)數(shù)量,。
(2)對H(v),A(v)進(jìn)行初始化, 使得H(v) = 1,，A(v) = 1。
(3)內(nèi)容匹配：將B集中擴(kuò)展得到的網(wǎng)頁看做一篇文檔，把文檔d和查詢式q表示成向量形式(d =(d 1,d2…dn)di代表第i篇文檔q=(q1,q2…qn)qi代表查詢主題中第i個關(guān)鍵詞),。文檔d(document)可看成是由相互獨(dú)立的若干詞條(term) ( t1,t2...tn)組成,對于每一詞條ti,根據(jù)詞條在文檔中隱含的語義及重要程度賦以一定的權(quán)值Wti , 則文檔的特征向量為(Wt1,Wt2...Wtn), 通過Similarity(di,Q) 余弦公式來表示第i篇文檔與查詢條件Q的相關(guān)度,。
?
?
并以此作為權(quán)重賦予相應(yīng)的節(jié)點(diǎn)(網(wǎng)頁)，Web節(jié)點(diǎn)的內(nèi)容與查詢主題相關(guān)度越大,，對應(yīng)的權(quán)值也越大,。這樣，鏈接結(jié)構(gòu)圖就成了節(jié)點(diǎn)帶權(quán)的有向圖,，使用這樣的權(quán)重來合理控制鏈接分析時節(jié)點(diǎn)對authority/hub值的影響,，最終有效控制主題偏移現(xiàn)象。
4? 實(shí)驗(yàn)結(jié)果與分析
在測試文檔集的選擇上,，選用BORODIN A等人提供的Web文檔集[9](包括“Abortion”,、 “Genetic”、 “Movies”,、“Harvard”等關(guān)鍵詞依次對應(yīng)的2 849,，2 613，5 613,1 583個網(wǎng)頁)對改進(jìn)的HITS算法和原HITS算法進(jìn)行了實(shí)驗(yàn)比較,，實(shí)驗(yàn)數(shù)據(jù)如表1所示,。
?
通過實(shí)驗(yàn)數(shù)據(jù)，對搜索出來的前30位的網(wǎng)頁進(jìn)行相關(guān)率比較如圖1所示,。在前30位網(wǎng)頁中發(fā)現(xiàn)原HITS算法將許多與查詢主題無關(guān)的網(wǎng)頁排了進(jìn)來,，使得網(wǎng)頁相關(guān)率較低；而改進(jìn)后的HITS算法排在前30內(nèi)的網(wǎng)頁相關(guān)率明顯高于原HITS算法,。
?
?
再對獲取網(wǎng)頁的前10位進(jìn)行權(quán)威度比較(這里網(wǎng)頁權(quán)威度是根據(jù)大多數(shù)人的評價得來的),，發(fā)現(xiàn)原HITS算法由于獲取相關(guān)網(wǎng)頁的準(zhǔn)確率不高，使得獲取權(quán)威網(wǎng)頁的總體效果也不佳,，而改進(jìn)后的HITS算法明顯優(yōu)于原HITS算法,，如圖2所示。
?
?
以上結(jié)果說明,，在原HITS算法中出現(xiàn)了TKC問題,，排序較高的相關(guān)頁面中存在與查詢主題無關(guān)的網(wǎng)頁,，而改進(jìn)的算法則有效地控制了TKC問題,，通過加入對文本內(nèi)容的分析使排序權(quán)值較高的頁面與查詢主題緊密相關(guān)。
文章在深入研究了Web挖掘和Web鏈接結(jié)構(gòu)分析的基礎(chǔ)上,，重點(diǎn)分析了主題提取算法HITS的基本思想和算法步驟,。針對HITS算法基于純鏈接，容易發(fā)生“主題偏移”現(xiàn)象,，本文從網(wǎng)頁文本內(nèi)容著手,，提出一種將網(wǎng)頁文本內(nèi)容和鏈接結(jié)構(gòu)相結(jié)合的改進(jìn)HITS算法，并通過實(shí)驗(yàn)結(jié)果證明了改進(jìn)后算法的有效性。
參考文獻(xiàn)
[1]?王曉宇,周傲英.萬維網(wǎng)的鏈接結(jié)構(gòu)分析及其應(yīng)用綜述[J].軟件學(xué)報(bào), 2003, 14( 10) : 1768-1780.
[2]?倪現(xiàn)軍. 結(jié)構(gòu)挖掘中web有向圖模型的改進(jìn)算法[J].微計(jì)算機(jī)信息,2007,12-3:163-165.
[3]?黃麗雯, 錢微. 多文檔文本摘要的一種改進(jìn)HITS算法[J].計(jì)算機(jī)應(yīng)用,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.