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