摘 要： HITS 算法是Web結(jié)構(gòu)挖掘中一種經(jīng)典的鏈接分析算法, 其主要問題是容易發(fā)生主題漂移。針對(duì)這一問題,，提出了一種基于文本內(nèi)容和鏈接分析相結(jié)合的改進(jìn)算法。實(shí)驗(yàn)證明改進(jìn)后的算法提高了查詢結(jié)果的相關(guān)度, 降低了主題漂移的可能性,。
關(guān)鍵詞： HITS算法；主題漂移；權(quán)威網(wǎng)頁；中心網(wǎng)頁
?
??? Internet是一個(gè)巨大,、分布廣泛、全球性的信息服務(wù)中心,，它提供了各種各樣的信息服務(wù),。但如何從Internet浩如煙海的信息中獲取所需信息或是從中提取有用知識(shí)，一直是相關(guān)專家探究的問題,。將傳統(tǒng)的數(shù)據(jù)挖掘技術(shù)和Web結(jié)合起來，對(duì)Web進(jìn)行數(shù)據(jù)挖掘成為解決這一問題的重要途徑,。由于Web上的鏈接結(jié)構(gòu)含有非常豐富和重要的信息,，鏈接分析技術(shù)已經(jīng)被成功地用于分析Web超鏈接數(shù)據(jù)來確定權(quán)威信息源。而在各種對(duì)網(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)頁),。為每個(gè)網(wǎng)頁定義兩個(gè)度量值:權(quán)威權(quán)重(authority weight)和中心權(quán)重(Hub weight),，通過這兩個(gè)權(quán)重來判定該網(wǎng)頁對(duì)特定主題的重要性。
1.2? HITS算法的具體過程
整個(gè)HITS算法主要可以分為以下幾個(gè)步驟:
(1)在搜索引擎上輸入給定的關(guān)鍵詞, 以此搜索到的最前面的r個(gè)等級(jí)最高的查詢結(jié)果網(wǎng)頁作為根集(root set)R,，R需滿足如下3個(gè)條件： ①R中網(wǎng)頁數(shù)量相對(duì)較小.②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ò)展成一個(gè)更大的基礎(chǔ)集合(base set)B,。擴(kuò)展規(guī)則為：將根集中的全部網(wǎng)頁加入進(jìn)來, 并加入最多d個(gè)鏈接到根集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è)二分有向圖G＝(V1，V2,，E),。對(duì)V1中的任一個(gè)頂點(diǎn)v，用h(v)表示網(wǎng)頁v的hub值，對(duì)V2中的頂點(diǎn)u,，用a(u)表示網(wǎng)頁的authority值,。假設(shè)Web鏈接結(jié)構(gòu)子圖G中包含n個(gè)節(jié)點(diǎn)(網(wǎng)頁)，對(duì)這n個(gè)節(jié)點(diǎn)加以編號(hào)：1,，2,，…，n,，這樣就可以為Web鏈接結(jié)構(gòu)子圖G定義一個(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ì)算后，會(huì)收斂至對(duì)稱矩陣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,。基集B中網(wǎng)頁的權(quán)威權(quán)重和中心權(quán)重從根本上說是由基集B中網(wǎng)頁的鏈接關(guān)系所決定的,，更具體地說,，是由對(duì)稱矩陣ATA和AAT所決定的。
2?HITS算法中存在的問題
HITS算法雖然在某些查詢主題下能夠較為準(zhǔn)確地提取出權(quán)威網(wǎng)頁, 但在一些場(chǎng)合中仍會(huì)使得算法發(fā)生嚴(yán)重的“主題漂移”[2]的現(xiàn)象( authorities集中到一些鏈接稠密的非相關(guān)網(wǎng)頁的現(xiàn)象被稱為“主題漂移”) ,。該現(xiàn)象的出現(xiàn)說明在傳統(tǒng)HITS算法中仍存在一些缺點(diǎn), 這就要求對(duì)傳統(tǒng)HITS算法進(jìn)行改進(jìn), 以使其具有更為廣泛的適用性, 提高權(quán)威頁面搜索的效率,。
3?HITS算法的改進(jìn)
HITS算法遇到的問題，多是因?yàn)镠ITS是純粹的基于鏈接分析的算法,，沒有考慮文本內(nèi)容,。繼KLIINBERG J提出HITS算法以后，很多研究者對(duì)HITS進(jìn)行了改進(jìn),，提出了許多HITS的變種算法,，主要有IBM Almaden研究中心Clever搜索引擎的ARC(Automatic Resource Compilation)算法[4]和由GEVREY J和RUGER S于2002年提出來的兩個(gè)基于超鏈接和內(nèi)容的網(wǎng)頁排序算法[5]：Average算法和Sim算法等。
針對(duì)HITS算法發(fā)生的“主題漂移”的現(xiàn)象,，本文在鏈接分析的基礎(chǔ)上引入了網(wǎng)頁內(nèi)容信息[3]的判斷,，提出了一種改進(jìn)的HITS算法,。
3.1? 改進(jìn)思想
HITS 算法中, 構(gòu)造一個(gè)基本集R集, 然后通過基本集擴(kuò)展到B集, 形成整個(gè)Web 子圖。這樣做的原因是R集可能并不包含真正的用戶需要的頁面,。例如搜索關(guān)鍵詞“搜索引擎”時(shí), 文本搜索引擎返回的頁面通常不會(huì)包含Google,、Yahoo等搜索引擎的頁面, 因?yàn)樗鼈兊捻撁嫱ǔ２粫?huì)出現(xiàn)搜索引擎這樣的字眼。這使得原本很重要的頁面不能被包含在第一步得到的結(jié)果中,。B集可以解決這個(gè)問題, 因?yàn)榭梢酝ㄟ^R集中網(wǎng)頁的鏈接來得到需要的網(wǎng)頁,。但是也正是由于HITS 算法的這種特性使得它在構(gòu)造B集時(shí), 常常會(huì)引入過多與主題無關(guān)的頁面, 它們有些還由于擁有互相指向的鏈接而擁有較高的權(quán)威值。如果控制B集構(gòu)造時(shí)的半徑, 可能得不到足夠的頁面,B集半徑足夠大可能會(huì)找到真正的合適頁面, 但是這時(shí)也已經(jīng)引入了過多的無關(guān)頁面,。
針對(duì)此,，本文在鏈接分析的基礎(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個(gè)過程：(1)有效地選取基集,；(2)擴(kuò)展基集時(shí)通過余弦公式對(duì)網(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,，對(duì)于圖G中的每一個(gè)節(jié)點(diǎn)V(網(wǎng)頁)有兩個(gè)值, 分別是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)對(duì)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個(gè)關(guān)鍵詞),。文檔d(document)可看成是由相互獨(dú)立的若干詞條(term) ( t1,t2...tn)組成,對(duì)于每一詞條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)度越大,，對(duì)應(yīng)的權(quán)值也越大。這樣,，鏈接結(jié)構(gòu)圖就成了節(jié)點(diǎn)帶權(quán)的有向圖,，使用這樣的權(quán)重來合理控制鏈接分析時(shí)節(jié)點(diǎn)對(duì)authority/hub值的影響，最終有效控制主題偏移現(xiàn)象,。
4? 實(shí)驗(yàn)結(jié)果與分析
在測(cè)試文檔集的選擇上,，選用BORODIN A等人提供的Web文檔集[9](包括“Abortion”,、 “Genetic”、 “Movies”,、“Harvard”等關(guān)鍵詞依次對(duì)應(yīng)的2 849,，2 613，5 613,1 583個(gè)網(wǎng)頁)對(duì)改進(jìn)的HITS算法和原HITS算法進(jìn)行了實(shí)驗(yàn)比較,，實(shí)驗(yàn)數(shù)據(jù)如表1所示,。
?
通過實(shí)驗(yàn)數(shù)據(jù)，對(duì)搜索出來的前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算法,。
?
?
再對(duì)獲取網(wǎng)頁的前10位進(jìn)行權(quán)威度比較(這里網(wǎng)頁權(quán)威度是根據(jù)大多數(shù)人的評(píng)價(jià)得來的),，發(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問題,，通過加入對(duì)文本內(nèi)容的分析使排序權(quán)值較高的頁面與查詢主題緊密相關(guān),。
文章在深入研究了Web挖掘和Web鏈接結(jié)構(gòu)分析的基礎(chǔ)上，重點(diǎn)分析了主題提取算法HITS的基本思想和算法步驟,。針對(duì)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.