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

欒霞+趙曉楠

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

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

中圖分類號： TN911?34； TP391.4 文獻標(biāo)識碼： 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 引 言

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

1 主題爬行策略設(shè)計

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

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

在主題爬蟲中如果對主題描述太為廣泛就會導(dǎo)致搜索的網(wǎng)頁量大而相關(guān)性就?。蝗绻唧w就會限制爬行范圍，雖然搜索的網(wǎng)頁相關(guān)度高，但是會減少數(shù)量[4]。而維基百科[5]是一個動態(tài)的、可自由訪問和編輯的全球最大的Web知識庫。維基百科對其中的每個概念都給出了對應(yīng)的描述文檔，并以分類樹[6]的形式組織在一起。分類樹中上層為較泛化的概念，下層為較細化的概念。

圖1 爬行策略流程圖

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

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

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

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

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

[T=wi×fi]

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

1.2 網(wǎng)頁主題相關(guān)性計算

主題相關(guān)性的計算準(zhǔn)確與否直接影響了主題爬行器的性能。本文將下載的網(wǎng)頁進行分塊后，利用改進的Shark[7]啟發(fā)式搜索算法，根據(jù)爬行過的網(wǎng)頁內(nèi)容和Web鏈接信息來計算待爬行網(wǎng)頁隊列中的URL優(yōu)先級。

1.2.1 網(wǎng)頁內(nèi)容評價

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

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

式中：p指當(dāng)前頁面；k指主題；頁面內(nèi)容向量[p=w1q，w2q，…，wnq]；主題向量[k=w1j，w2j，…，wnj]；[w1j]指關(guān)鍵詞i在頁面j中的權(quán)值；[wiq]指關(guān)鍵詞i的權(quán)值。

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

1.2.2 Web鏈接評價

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

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

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

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

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

1.2.3 改進的優(yōu)先級計算

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

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

式中：[ti]指網(wǎng)頁i的主題相關(guān)度；thr為相似度閾值；[Pi]指網(wǎng)頁i的鏈接個數(shù)；[oi-1k]指網(wǎng)頁i-1的第k個鏈接所指的網(wǎng)頁編號。

2 實驗與分析

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

圖2 結(jié)果對比

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

3 結(jié) 語

本文研究了主題爬蟲中爬蟲策略的選取，主要包括對關(guān)鍵字向量的描述、網(wǎng)頁優(yōu)先級計算，設(shè)計并實現(xiàn)了一個通用的主題爬蟲爬行策略，實驗表明本文的方法取得了良好的效果，具有較大的應(yīng)用價值。

參考文獻

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

[2] 戴智利，王鑫昱.一種基于動態(tài)時間閾值的會話識別方法[J].計算機應(yīng)用與軟件，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].電子科技大學(xué)學(xué)報，2010，39（3）：321?334.

[7] 陳竹敏.面向垂直搜索引擎的主題爬行技術(shù)研究[D].濟南：山東大學(xué)，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 結(jié)果對比

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

3 結(jié) 語

本文研究了主題爬蟲中爬蟲策略的選取，主要包括對關(guān)鍵字向量的描述、網(wǎng)頁優(yōu)先級計算，設(shè)計并實現(xiàn)了一個通用的主題爬蟲爬行策略，實驗表明本文的方法取得了良好的效果，具有較大的應(yīng)用價值。

參考文獻

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

[2] 戴智利，王鑫昱.一種基于動態(tài)時間閾值的會話識別方法[J].計算機應(yīng)用與軟件，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].電子科技大學(xué)學(xué)報，2010，39（3）：321?334.

[7] 陳竹敏.面向垂直搜索引擎的主題爬行技術(shù)研究[D].濟南：山東大學(xué)，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 結(jié)果對比

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

3 結(jié) 語

本文研究了主題爬蟲中爬蟲策略的選取，主要包括對關(guān)鍵字向量的描述、網(wǎng)頁優(yōu)先級計算，設(shè)計并實現(xiàn)了一個通用的主題爬蟲爬行策略，實驗表明本文的方法取得了良好的效果，具有較大的應(yīng)用價值。

參考文獻

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

[2] 戴智利，王鑫昱.一種基于動態(tài)時間閾值的會話識別方法[J].計算機應(yīng)用與軟件，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].電子科技大學(xué)學(xué)報，2010，39（3）：321?334.

[7] 陳竹敏.面向垂直搜索引擎的主題爬行技術(shù)研究[D].濟南：山東大學(xué)，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.