基于維基百科和網頁相似度分析的主題爬行策略

欒霞+趙曉楠

摘 要： 針對當前常用爬蟲爬行策略的不足，提出結合維基百科和網頁相似度分析的主題爬行策略。利用維基百科分類樹的結構對主題進行描述；下載網頁后對網頁進行相應處理，結合文本相關性和Web鏈接分析來計算候選鏈接的優先級。實驗表明，該爬蟲搜索結果與主題相關度明顯高于傳統爬蟲，爬蟲爬全率有一定提高。該主題爬蟲主題描述方法和爬行策略有一定的推廣價值，尤其在轉基因生物領域中，該爬蟲中有一定的創新性。

關鍵詞： 維基百科； 文本相關性； 鏈接分析； 相似度計算

中圖分類號： TN911?34； TP391.4 文獻標識碼： A 文章編號： 1004?373X（2014）20?0035?03

Topic crawling strategies based on Wikipedia and analysis of web?page similarity

LUAN Xia1， ZHAO Xiao?nan2

（1. The Network Center， 323rd Hospital of Chinese Peoples Liberation Army， Xian 710054， China； 2. Unit 68303 of PLA， Wuwei 733000， China）

Abstract： To overcome the weakness existing in the present topic crawling strategies， a topic crawling strategy based on Wikipedia and web?page similarity analysis is put forward in this paper. The Wikipedia classification tree structure is utilized to describe the topics， and then the downloaded webs are properly handled. Finally， the priorities of the candidate links are calculated in combination with text relativity and analysis of Web links. The experimental result indicates that this new method is better than the traditional crawler in terms of searching results and topic relativity， and its climb rate has been increased. The theme description method and the crawl strategy have a certain promotion value， especially in the field of genetically modified organisms， the crawler has certain innovativeness.

Keywords： topic crawling； Wikipedia； text relativity； link analysis； similarity calculation

0 引 言

近年來隨著因特網技術的發展與普及，網絡上的信息量越來越大，如何高效地從網絡上獲得有用的資源變得至關重要。主題爬行器是解決這一問題的技術之一，它是在預定主題的指引下，在網絡上選擇與主題相關的網頁進行爬取，并避免了非相關的網頁[1]。傳統的爬行策略大多都是通過與關鍵詞機械的匹配，Ehrig等人把本體引入到主題爬行中[2]，利用本體代替了關鍵詞，利用本體中的詞匯層次關系計算出網頁的主題相關度，但本體的描述方法過于復雜，直接影響了使用效率。在計算網頁相關性上，傳統主題爬行策略主要有兩類：基于網頁內容的搜索策略、基于Web鏈接評價的搜索策略。基于網頁內容的搜索策略是對文本中的相似度進行計算，根據相似度確定URL優先級；基于Web鏈接評價的搜索策略是根據Web頁面之間的相互引用關系來確定網頁的相似度，從而確定URL優先級隊列。基于網頁內容的搜索策略雖然簡單但忽略了鏈接結構信息，所以不能很好的預測鏈接價值；而基于Web鏈接評價的搜索策略只考慮了網頁之間的相互引用，但忽略了頁面與主題的相關性，容易出現“出題漂移”的問題[3]，因此不適合挖掘主題資源。本文在綜合考慮以上問題的基礎上，設計了一種新的主題爬行策略，首先通過維基百科對主題進行描述；對下載的網頁進行處理后，綜合基于網頁內容和Web鏈接分析來確定URL的優先級。

1 主題爬行策略設計

本文綜合維基百科、網頁內容和Web鏈接的方法來設計主題爬行策略，新策略的處理流程圖如圖1所示。

1.1 基于維基百科的主題描述

在主題爬蟲中如果對主題描述太為廣泛就會導致搜索的網頁量大而相關性就小；如果太具體就會限制爬行范圍，雖然搜索的網頁相關度高，但是會減少數量[4]。而維基百科[5]是一個動態的、可自由訪問和編輯的全球最大的Web知識庫。維基百科對其中的每個概念都給出了對應的描述文檔，并以分類樹[6]的形式組織在一起。分類樹中上層為較泛化的概念，下層為較細化的概念。

圖1 爬行策略流程圖

本文通過維基百科的主題向量來描述主題，約束爬取范圍，具體方法為：

（1） 完善分類樹。維基百科中對屬于某概念的部分下層概念并不收錄進分類樹中，而出現在描述文檔中，這樣就導致了分類樹不完整，從而影響相關度計算。本文將這些概念提取出來，并加入到分類樹中。例如，將出現在“轉基因”描述文檔中的“遺傳工程”加入到“轉基因”的分類樹中。

（2） 從分類樹中提取概念p向上一層的概念集合[Cup]和向下N層概念的集合[Cdown]，組成p的相關概念集合（Relevant Concept Mass，RCM），即[RCMp=Cup?Cdown? p] 。

（3） 對概念p的相關概念集合 中的每個概念[RCMp={c1，c2，…，ci，…，cm}m>0]計算權重 （0

（4） 將主題描述文檔經過分詞和去除排除詞匯后映射到 [VSp]上，即將詞語映射到[RCMp]中存在并且在分類樹中距離主題概念p最近的概念上，然后統計[VSp]中每個概念在主題描述文檔中出現的頻率（f），最終計算主題向量T：

[T=wi×fi]

式中：[fi]等于屬于[ci]的詞的頻率之和。

1.2 網頁主題相關性計算

主題相關性的計算準確與否直接影響了主題爬行器的性能。本文將下載的網頁進行分塊后，利用改進的Shark[7]啟發式搜索算法，根據爬行過的網頁內容和Web鏈接信息來計算待爬行網頁隊列中的URL優先級。

1.2.1 網頁內容評價

本文設計兩個隊列來存放待爬行的URL，分別為相關度高的優先隊列PQ（Prior Queue）和相關度低的普通隊列NQ（Normal Queue）；設計三類閾值來決定待爬行URL屬于哪個隊列，分別為頁面內容閾值上限pageMaxLimit、頁面閾值下限pageMinLimit，節點閾值上限nodeMaxLimit、節點閾值下限nodeMinLimit，錨文本的相關度閾值anchorLimit。其中，節點閾值上限即是PQ的最低相關度值，節點閾值下限即是NQ的最低相關度值。而網頁和關鍵詞的相似度計算仍采用向量空間模型，計算公式如下：

[simp，k=cosp，k=i=1nwij*wiqi=1nw2ij*i=1nw2iq]

式中：p指當前頁面；k指主題；頁面內容向量[p=w1q，w2q，…，wnq]；主題向量[k=w1j，w2j，…，wnj]；[w1j]指關鍵詞i在頁面j中的權值；[wiq]指關鍵詞i的權值。

根據相關度可以將待爬URL放入相應的隊列中，若一個頁面的主題相關度大于pageMaxLimit，則將該頁面的子頁面放入PQ隊列中；若一個頁面的主題相關度值介于pageMaxLimit和pageMinLimit之間，則根據該頁面的子頁面的錨文字或URL字符串是否包含關鍵詞向量中的關鍵詞來決定是否將其加入到PQ中，如果滿足任何一個條件，則將其加入到PQ中；否則由子節點的相關度值來決定加入隊列的類型。

1.2.2 Web鏈接評價

本文采用Hits[8]算法思想來進行Web鏈接評價。Hits算法由Kleinberg首先提出，用來判斷網頁重要性，目前主要用于搜索結果排序。該算法思想是如果一個網頁被其他多個網頁鏈接，則比其他鏈接少的頁面重要。因此引入權威（Authority）頁面和中心（Hub）頁面的概念。即好的Hub頁面總是指向許多好的Authority頁面；反之，好的Authotirty頁面總是被許多好的Hub頁面所鏈接。因此，這種相互加強的關系可以用于發現Authority頁面。算法首先利用爬蟲從Web上獲取與用戶查詢相關的部分網頁構成網絡子圖G（V，E）（V為網絡子圖的節點集，E為網絡子圖的邊集），然后通過迭代計算出每個網頁的權威值和中心值，迭代步驟如下：

（1） 確定與主題最相關的K（200）個頁面，稱為root集。

（2） 對于root集中的任一網頁p，將p中所包含的鏈接加入到root集中，最多不超過d（50）個，擴展后稱為base集。

（3） 計算base集中每個頁面的中心值和權威值，計算方法如下：如果G中有n個節點，則有n維向量a，h，[ai]指節點i的權威值、[hi]指節點i的中心值，設[a0=1]，[h0=1]，然后進行迭代運算：

[ai=i∈Vhi-1， hi=i∈Vai-1]

1.2.3 改進的優先級計算

由于基于內容評價的策略忽略了鏈接結構信息，在預測鏈接價值方面存在不足；而Hits算法只考慮了Web頁面之間的引用關系，忽略了頁面的主題相關性，容易造成主題漂移現象。為了克服二者的不足，本文設計了基于主題敏感的鏈接分析方法，稱為主題Hits。對于中心Hub頁面只有當所指網頁為主題相關時才能獲得相應值，該值由所指頁面的Authority值和其主題相關度決定；而Hub值由其鏈接到的頁面的主題相關度決定。因此迭代公式如下：

[ai=i，k∈VPi-1tik=1Pjtoi-1khi-1hi=i∈V&ti-1≥thrai-1×ti-1]

式中：[ti]指網頁i的主題相關度；thr為相似度閾值；[Pi]指網頁i的鏈接個數；[oi-1k]指網頁i-1的第k個鏈接所指的網頁編號。

2 實驗與分析

系統選用Java語言在Eclipse平臺下開發。實驗環境為微機1臺，CPU為Intel Core 2，內存1 GB。軟件環境為Windows XP和JDK1.6，選IIS 6.0為Internet為信息服務，數據庫選用MySQL。系統選用轉基因生物為主題，運行時初始種子網頁包括烏有之鄉，天涯網：天涯雜談、經濟論壇，鳳凰網：辯論會、鏗鏘雜談，新華網：發展論壇，人民網：強國論壇，百度貼吧，中華網論壇，騰訊論壇，網易論壇，新浪論壇，搜狐論壇；主要門戶網站新聞及相關轉載情況，主要門戶網站：雅虎、搜狐、新浪、網易、騰訊等。關注人物包括： 金薇（國際先驅報）、張宏良、蔣高明、顧秀林、 郎咸平。根據上述內容，設計了一個主題爬蟲，將三種爬行策略進行對比，圖2是對比結果，其中，查準率=主題相關的網頁數/總網頁數。

圖2 結果對比

上面的分析可知，新的爬行策略在查詢特定主題信息方面比傳統的爬行技術有著明顯的優勢，隨著網頁數量的增大，新的策略在總體上也存在優勢。算法中各種參數的設置和閾值的選擇對爬行結果有重要的影響，因此如何確定最有利的參數和閾值有待于進一步研究。

3 結 語

本文研究了主題爬蟲中爬蟲策略的選取，主要包括對關鍵字向量的描述、網頁優先級計算，設計并實現了一個通用的主題爬蟲爬行策略，實驗表明本文的方法取得了良好的效果，具有較大的應用價值。

參考文獻

[1] 蔡號，賈于波，黃成偉，等.Web日志挖掘中的會話識別算法[J].計算機工程與設計，2009，30（6）：1321?1324.

[2] 戴智利，王鑫昱.一種基于動態時間閾值的會話識別方法[J].計算機應用與軟件，2010，27（2）：244?246.

[3] AGGARWAL C C， AL?GARAWI， YU P S. Intelligent crawling on the world wide Web with arbitrary predicates [C]// Proceedings of the 10th International Conference on World Wide Web. New York： ACM， 2001： 89?113.

[4] 史天藝，李明祿.基于維基百科的自動詞義消歧方法[J].計算機工程，2009，35（18）：62?65.

[5] Anon. Wikipedia [EB/OL]. [2011?02?16]. http：//wikipedia.jaylee.cn.

[6] 趙飛，周濤，張良，等.維基百科研究綜述[J].電子科技大學學報，2010，39（3）：321?334.

[7] 陳竹敏.面向垂直搜索引擎的主題爬行技術研究[D].濟南：山東大學，2008.

[8] STRUBE M， PONZETTO S P. Wiki related computing semantic relatedness using Wikipedia [C]//Proceedings of the National Conference on Artificial Intelligence. Cambridge： AAAI Press， 2006： 1419?1424.

圖2 結果對比

上面的分析可知，新的爬行策略在查詢特定主題信息方面比傳統的爬行技術有著明顯的優勢，隨著網頁數量的增大，新的策略在總體上也存在優勢。算法中各種參數的設置和閾值的選擇對爬行結果有重要的影響，因此如何確定最有利的參數和閾值有待于進一步研究。

3 結 語

本文研究了主題爬蟲中爬蟲策略的選取，主要包括對關鍵字向量的描述、網頁優先級計算，設計并實現了一個通用的主題爬蟲爬行策略，實驗表明本文的方法取得了良好的效果，具有較大的應用價值。

參考文獻

[1] 蔡號，賈于波，黃成偉，等.Web日志挖掘中的會話識別算法[J].計算機工程與設計，2009，30（6）：1321?1324.

[2] 戴智利，王鑫昱.一種基于動態時間閾值的會話識別方法[J].計算機應用與軟件，2010，27（2）：244?246.

[3] AGGARWAL C C， AL?GARAWI， YU P S. Intelligent crawling on the world wide Web with arbitrary predicates [C]// Proceedings of the 10th International Conference on World Wide Web. New York： ACM， 2001： 89?113.

[4] 史天藝，李明祿.基于維基百科的自動詞義消歧方法[J].計算機工程，2009，35（18）：62?65.

[5] Anon. Wikipedia [EB/OL]. [2011?02?16]. http：//wikipedia.jaylee.cn.

[6] 趙飛，周濤，張良，等.維基百科研究綜述[J].電子科技大學學報，2010，39（3）：321?334.

[7] 陳竹敏.面向垂直搜索引擎的主題爬行技術研究[D].濟南：山東大學，2008.

[8] STRUBE M， PONZETTO S P. Wiki related computing semantic relatedness using Wikipedia [C]//Proceedings of the National Conference on Artificial Intelligence. Cambridge： AAAI Press， 2006： 1419?1424.

圖2 結果對比

上面的分析可知，新的爬行策略在查詢特定主題信息方面比傳統的爬行技術有著明顯的優勢，隨著網頁數量的增大，新的策略在總體上也存在優勢。算法中各種參數的設置和閾值的選擇對爬行結果有重要的影響，因此如何確定最有利的參數和閾值有待于進一步研究。

3 結 語

本文研究了主題爬蟲中爬蟲策略的選取，主要包括對關鍵字向量的描述、網頁優先級計算，設計并實現了一個通用的主題爬蟲爬行策略，實驗表明本文的方法取得了良好的效果，具有較大的應用價值。

參考文獻

[1] 蔡號，賈于波，黃成偉，等.Web日志挖掘中的會話識別算法[J].計算機工程與設計，2009，30（6）：1321?1324.

[2] 戴智利，王鑫昱.一種基于動態時間閾值的會話識別方法[J].計算機應用與軟件，2010，27（2）：244?246.

[3] AGGARWAL C C， AL?GARAWI， YU P S. Intelligent crawling on the world wide Web with arbitrary predicates [C]// Proceedings of the 10th International Conference on World Wide Web. New York： ACM， 2001： 89?113.

[4] 史天藝，李明祿.基于維基百科的自動詞義消歧方法[J].計算機工程，2009，35（18）：62?65.

[5] Anon. Wikipedia [EB/OL]. [2011?02?16]. http：//wikipedia.jaylee.cn.

[6] 趙飛，周濤，張良，等.維基百科研究綜述[J].電子科技大學學報，2010，39（3）：321?334.

[7] 陳竹敏.面向垂直搜索引擎的主題爬行技術研究[D].濟南：山東大學，2008.

[8] STRUBE M， PONZETTO S P. Wiki related computing semantic relatedness using Wikipedia [C]//Proceedings of the National Conference on Artificial Intelligence. Cambridge： AAAI Press， 2006： 1419?1424.