一種有效的專題信息集中和檢索策略

摘 要:Internet上專題資源網頁匯聚和檢索是垂直搜索引擎中的核心問題，HITS算法是早期解決這個問題的經典算法，很多文獻對它進行了改進，但無論索引的主題相關率還是引擎的查準率都有提高的余地。提出一種基于錨文本和標題信息過濾并結合網頁內容相關度判斷的HITS專題檢索策略，利用專題訓練集判斷主題相關度，很好地解決了只依靠查詢字符串判斷的弊端。實驗表明，此策略能很好地提高專題信息匯聚精確度和檢索的準確率，并且減少了非相關URL的下載量。

關鍵詞:HITS算法; 錨文本; 網頁標題; 專題相關度; 向量模型; 專題訓練集

中圖分類號:TP301.6文獻標志碼:A

文章編號:1001-3695(2010)06-2106-03

doi:10.3969/j.issn.1001-3695.2010.06.032

Effective strategy of topic distillation and retrieval

WANG Yuxina， LIU Haifenga， GUO Heb， CHEN Xinb

(a.School of Electronic Information Engineering， b.School of Software， Dalian University of Technology， Dalian Liaoning 116023， China)

Abstract:The strategy of topic distillation and retrieval on Internet is the key work in research of vertical search engine. HITS algorithm is a classical method for this problem at an earlier time， and some improvements are made by other researchers afterwards. Nevertheless， no matter the theme relation rate or accuracy grade of engine still have room to be improved. This paper proposed a strategy of topic distillation and retrieval by filtering Web pages based on anchor texts and titles combining relation grade of Web pages. Using the topic training collection to judge relation grade could overcome the shortcomings of depending on inquiring strings. The experiment results prove that this strategy can improve the accuracy of topic distillation and retrieval， and reduce the downloaded information of unrelated URLs.

Key words:HITS algorithm; anchor text; Web page title; relation grade of topic; vector model; topic training collection

0 引言

隨著Internet資源的高速增長，數據量已經遠遠超出搜索引擎能覆蓋的范圍，截至2008年全球因特網資源網頁已數以億計，即使是最著名的Google也只能覆蓋全部信息的30%~40%。于是人們越來越難以從通用搜索引擎獲取自己需要的某一專題領域的信息，在返回的數千個網頁中找到自己需要的那一方面的信息非常困難[1，2]。專題搜索策略的目的就是實現人們對于某一專題領域相關信息的準確定位。

垂直搜索引擎是近幾年來展開研究的一個檢索模型，它的核心就是專題內容的集中和檢索，這種策略又稱為專題網絡蜘蛛。網絡蜘蛛是抓取下載網頁連接的程序模型，專題網絡蜘蛛則對網頁進行預測，賦予不同的優先值，按照與專題領域相關的優先級策略進行抓取下載，以便集中處理相關領域的網頁。一個好的專題信息檢索策略，既能讓最終的檢索列表按照網頁與主題相關度高低排列等待檢索，又能避免非相關網頁的下載和計算。Pagerank算法和HITSC(hyperlink induced topic search)算法是抓取下載策略中的兩種經典算法[3]，基于HITS算法的網絡蜘蛛策略在專題領域應用更加廣泛，但是它容易產生主題漂移。針對這個缺點很多文獻提出了改進方案[4~6]，它們大多是基于網頁內容相關性判斷的，或者利用超鏈接文字信息和結構判斷網頁性質[7，8]，諸如ARC算法、average和sim算法[5];但也存在各自的缺點，無論是最終索引列表中內容與主題相關度的比率還是對于特定關鍵詞檢索的查準率，都有提高的余地。本文提出了一種基于錨文本和標題信息與專題訓練集比較而過濾網頁并結合網頁內容相關度判斷的HITS專題檢索策略，新的策略能很好地解決判斷條件單薄、無關網頁下載并參與計算的問題，改善主題漂移現象，進一步提高主題檢索的精度。

1 HITS算法及其主要改進

Kleinberg提出的HITS算法的基本思想是[9]:a)利用通用搜索引擎得到一個網頁的初始子集I，I內的頁面和用戶查詢專題有很大的相關性。b)把I指向的網頁和指向I的網頁都包含進來，形成基礎集合E，E中的每個頁面都具有一個authority權值(表示網頁與查詢條件相關度的高低)和hub權值(反映該頁面鏈出相關度高頁面的多少情況)[6]。a=(a1，a2，…，an)和h=(h1，h2，…，hn)代表E中所有網頁的authority和hub向量，初始時把所有的ai和hi都設置為1，然后利用下面的公式進行計算:

ai=∑j∈B(i)hj，hi=∑j∈F(i)aj(1)

其中:B(i)和F(i)分別表示指向該網頁的和該網頁指向的網頁鏈接集合。用n×n的矩陣A表示集合E的網頁節點間的連接，如果節點i和j之間有連接，則A[i，j]=1，否則A[i，j]=0。因此式(1)可以表示為

a=ATh=ATAa， h=Aa=AATh(2)

迭代計算a和h，直至收斂。集中求ATA和AAT，最后按照authority和hub值排序，將a和h值大于閾值M的網頁挑出來。

HITS算法雖然可以提高一定的專題查準率，但也存在一些缺點:a)忽略了網頁內容的差異，對于每個鏈接網頁賦予相同的加權常數，這樣非相關網頁和相關網頁同等對待，會產生主題漂移現象。b)形成集合E時，初始集合I中網頁的一些非相關鏈接也加入進來，增加了無謂的下載量，也使后續更多的無關網頁參與計算，對準確率存在一定的影響。

基于網頁內容相關度的HITS算法是一種普遍的HITS算法改進策略，它的主要不同之處在于計算網頁權值的公式中對于每個網頁的加權常數不全部賦1，而是利用空間向量計算網頁內容與查詢關鍵詞的相似度，再依據相似度給網頁賦予不同的加權常數，計算式為

ai=∑j∈B(i)hj×F， hi=∑j∈F(i)aj×F(3)

這種方法能解決一定的主題漂移現象，但也存在著缺點:對于下載沒有過濾，那些非相關性的網頁還是下載并參與了計算，不但多做了很多下載工作，也多少會造成對最后結果的影響。

還有一些改進方法單純依靠超鏈接信息和查詢關鍵詞相似度作為加權依據，這樣會造成更不準確的判斷。而且上述無論基于網頁內容還是基于鏈接的改進，都是依據與查詢關鍵詞相似度來判斷的，這樣的條件太過單薄，容易忽略掉很多主題相關的信息。

2 專題集中和檢索策略

對于特定專題來說，網頁之間的超鏈接價值是不同的，錨文本信息和文檔網頁標題信息能較好地反映該鏈接網頁的主題內容，是對網頁主題內容判斷的重要參考。針對原始HITS算法以及結合網頁相關度的改進算法的缺點，本文在加入URLs形成集合E之前利用錨文本和標題信息先進行一次判斷，過濾掉大量與主題訓練集向量相似度很低的無關網頁，再采用基于網頁內容和專題訓練集相關度結合HITS公式進行計算。這樣進行一層過濾，一層權值排序不但能大大減少計算量，而且相比單純的權值排序更能提高專題信息的查準率。圖1是本文策略流程圖。

2.1 專題訓練集

專題訓練集是事先練習得出的一個專題領域關鍵文檔內容的集合。首先利用通用搜索引擎對專題關鍵詞進行查詢，挑選出結果中一些權威網站，對其進行一定深度的抓取，抓取的網頁文檔分詞后的內容放在本地文件夾里，形成訓練集合。編寫詞頻統計函數把文檔中的詞的頻率輸出，并按詞頻大小排列，利用改進TFIDF計算公式[10]對詞的權值進行計算:

Wik=tiklogN/nk+0.1∑nk=1(tik)2×log2N/nk+0.1(4)

其中:tik表示特征詞Tk在文檔Di中出現的次數;N表示全部文檔的總數;nk表示所有文檔中含有此特征詞Tk的文檔數。計算得到的詞頻和詞權輸出在本地文件中，再依據詞權信息統計出一定數量的相關專題關鍵詞，形成專題訓練集空間向量。例如，統計了100個與領域相關的專題關鍵詞及其權值，那么訓練集空間就是一個100維的向量，每一維的大小就是該詞的權值。后文用到的錨文本和標題信息空間向量以及網頁內容空間向量也同樣采用TFIDF計算權值式的方法統計形成。

用專題訓練集相比用查詢字符串判斷主題相關度能更廣泛全面地判斷用戶意圖，使用戶需要的主題相關信息不會被忽略掉。例如，輸入的查詢字符串是“石油”，而某網頁的錨文本信息為“我國各種主要能源資料”，依據查詢字符串判斷的話，此網頁與主題的相似度會很低，容易被忽略，而專題訓練集則不會。

2.2 錨文本和標題信息過濾URLs形成集合E

首先利用主題權威關鍵詞在通用搜索引擎上取出查詢結果的前若干條鏈接地址網頁，形成初始集合I;針對I中網頁的所有鏈入和鏈出鏈接，采用空間向量模型計算專題訓練集向量和錨文本與標題信息向量之間的相似度，若相似度很低就不予抓取和下載。

設S=(s1，s2，…，sm)為專題訓練集向量，Rj=(rj1，rj2，…，rjm)為錨文本和標題信息向量，m為向量維數。采用式(5)計算網頁的所有鏈接與專題訓練集的相似度:

F(S，Rj)=∑mi=1si×rji∑mi=1si21/2∑mi=1rji21/2(5)

為了避免過濾掉過多網頁而影響查全率，只對相似度為0和接近0，即基本不相關的鏈接不予抓取和下載。這樣做的好處在于在開始時就排除了很明顯的非相關網頁，如廣告鏈接、導航鏈接等，可以避免不必要的下載流量和存儲空間，而且后續計算量會減少，計算的專題精度也會提高。

2.3 E中authority值和hub值的計算和網頁排序

經過錨文本和標題信息與專題訓練集信息相似度判斷過濾后的網頁集合E中就不含與主題無關的一部分網頁，然后計算集合E中網頁的authority值和hub值。集合E的網頁都是相連的，可以形成一個有向圖，鏈接的結構和數量能代表一定程度的網頁價值。單純依靠計算網頁內容的主題相關度來決定最后的排序會對網頁的判斷產生誤差，采用HITS算法中計算網頁權值的思想，利用網頁內容的主題相關度[5]結合HITS計算式:

ai=∑j∈B(i)hjF(S，Rj)， hi=∑j∈F(i)ajF(S，Rj)(6)

其中:F(S，Rj)表示專題訓練集向量與Rj所代表的網頁內容的向量之間的相似度，相似度的計算依然采用上面計算向量相似度的公式。最后依據a和h值取出前若干網頁作為后面的檢索庫列表。

此時網頁已經下載下來，可以直接解析網頁，網頁的內容對于判斷主題相關度更加精確，并且網頁形成的有向圖中很多無關網頁節點并不真實存在，這些值全為0，計算比較方便。所以這里用網頁內容而不是錨文字和標題信息判斷主題相關度。

2.4 算法策略整體描述

算法策略過程描述如下(抓取深度為2層):

a)將權威主題查詢條件提交給通用搜索引擎，返回通用搜索引擎的前N條結果，合并去重，得到集合I。

b)用向量相似度公式計算集合I中網頁的每個鏈接網頁的錨文字和標題信息向量與專題訓練集向量的相似度F(S，Rj)。對于相似度值為0和接近0的鏈接不予抓取下載，剩下的下載，依次擴展，形成集合E。

c)把集合E看成一個網頁節點的有向圖，每個節點代表一個網頁，對于每個節點，賦予兩個值authority和hub，表示為a和h，初始值均為1。

d)將專題訓練集向量與每個節點網頁的內容向量進行相似度計算(式(5))。計算出的每個相似度作為每個節點網頁的加權常數值F。

e)式(6)為改進的HITS計算權值公式，計算所有節點的a和h值，并進行標準化。

f)設定閾值M，將所有a和h值大于M的節點網頁取出。

g)按照權值大小順序，輸出取出的網頁的排序結果加入檢索列表。

3 實驗數據分析

本文進行關于能源和基金股票兩個相關領域的測試，選取Google查詢“能源”和“基金股票”關鍵詞得到的前10個查詢結果作為初始入口URL集合抓取鏈接網頁，形成集合。在Nutch結合Eclipse環境基礎上對比作三種策略的實驗比較，即原始HITS算法策略、結合網頁相關度的HITS算法策略和本文算法策略。抓取深度取2、3、4層，對應取權值排序的前50、100、200個結果，表1和2是主題相關內容所占比率對比。

表1 能源領域相關內容比率對比%

策略

層深

234

原始HITS策略404944

網頁相關度HITS策略486260

本文算法策略647674

表2 基金股票領域相關內容比率對比%

策略

層深

234

原始HITS策略384541

網頁相關度HITS策略546259

本文算法策略607169

從表1和2可以看出，本文策略對于相關內容比例的提高有顯著的作用，更不容易產生主題漂移現象。

表3和4列出了兩個領域對于特定關鍵詞的查準率數據對比和層深為2、3、4層分別取前30、50、80項的檢索結果。

表3 能源領域關鍵詞查準率對比%

層深算法策略 石油天然氣煤

2

HITS策略36.740.043.3

網頁相關度HITS策略43.346.753.3

本文策略53.360.063.3

3

HITS策略30.032.040.0

網頁相關度HITS策略40.044.052.0

本文策略52.058.064.0

4

HITS策略26.330.036.3

網頁相關度HITS策略37.542.547.5

本文策略48.856.362.5

表4 基金股票領域關鍵詞查準率對比%

層深算法策略 大盤信息走勢圖滬市信息

2

HITS策略33.356.740.0

網頁相關度HITS策略46.763.356.3

本文策略54.073.366.7

3

HITS策略28.046.038.0

網頁相關度HITS策略42.060.050.0

本文策略52.066.060.0

4

HITS策略25.040.032.5

網頁相關度HITS策略38.853.846.3

本文策略46.360.055.0

從表3和4可以看出，本文策略也明顯提高了特定關鍵詞查詢的準確率。

4 結束語

HITS算法及一些改進的專題信息集中和檢索策略，各自均存在一定的缺陷，檢索列表的相關內容比例、關鍵詞的查準率和相關度判斷的準確率都有提高空間。本文利用錨文本和標題信息結合專題訓練集合過濾網頁，并基于網頁內容和專題訓練集的相似度計算權值，這種二層判斷策略能很好地提高專題信息匯聚精確度和檢索的準確率，并減少非相關的下載流量和計算量。

參考文獻:

[1]AWEKAR A， KANG J. Selective approach to handing topic oriented tasks on the world wide Web[C]//Proc of IEEE Symposium on Computational Intelligence and Data Mining.2007:343-348.

[2]FLAKE G， LAWRENCE S， GILES C L. Efficient identification of Web communities[C]//Proc of the 7th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM Press，2000:150-160.

[3]CHAU M， CHEN H. Comparison of three vertical search spiders[J]. Computer， 2003，36(5):56-62.

[4]LV Lintao， CHEN Liping， ZHOU Hongfang. An improved topic relevance algorithm for vertical search engines[C]//Proc of International Conference on Wavelet Analysis and Pattern Recognition.2008:753-757.

[5]肖明君，黃劉生，羅永龍. SHITS:一種基于超鏈接和內容的網頁排序方法[J]. 小型微型計算機系統， 2006，27(12):2177-2182.

[6]BHARAT K， HENZINGER M. Improved algorithms for topic distillation in a hyperlinked environment[C]//Proc of the 21st International ACM SIGIR Conference on Research and Development in Information Retrieval. New York: ACM Press，1998:104-111.

[7]ALAMPANIDIS G， KOTROPOULOS C， PITAS I. Combining text and link analysis for focused crawling

: an application for vertical search engines[J]. Information Systems，2007，32(6):886-908.

[8]劉金紅，陸余良. 主題網絡爬行蟲研究綜述[J]. 計算機應用研究， 2007，24(10):26-29.

[9]KLEINBERG J. Authoritative sources in a hyperlinked environment[C]//Proc of the 9th Annual ACMSIAM Symposium on Discrete Algorithms Table of Contents. New York: ACM Press，1998:668-677.

[10]張博，蔡皖東. 面向主題的網絡蜘蛛技術研究與系統實現[J]. 微電子學與計算機，2009， 27(5):52-55.