基于多目標蟻群算法的主題爬蟲策略

東 熠,劉景發,劉文杰

(1.南京信息工程大學 計算機與軟件學院,南京 210044; 2.廣東外語外貿大學 a.廣州市非通用語種智能處理重點實驗室; b.信息科學與技術學院,廣州 510006)

0 概述

隨著科技的飛速發展,信息已成為一種重要資源,而信息的有效獲取對各領域都至關重要。在氣象領域,氣象災害數量占到自然災害總數量的70%以上[1],嚴重威脅到人民群眾生命財產安全,也給社會經濟發展帶來不利影響,例如,2016年天津暴雨造成受災人口達到14萬,直接經濟損失超過2.5億元[2]。因此,及時獲取氣象災害預警與應急處理信息極為重要?；ヂ摼W由于擁有海量數據資源,因而成為獲取大量氣象災害信息的重要渠道。然而目前互聯網通用搜索引擎查詢結果相關性不高,不能滿足用戶個性化查詢需求。為解決該問題,研究人員提出主題爬蟲方法并對其展開深入研究。

主題爬蟲方法主要包括傳統基于啟發式策略的經典爬行方法、基于概念語義的主題爬行方法和基于智能優化算法的主題爬行方法。傳統啟發式主題爬蟲方法包括超鏈接拓撲結構法和網頁內容分析法。針對超鏈接拓撲結構法,文獻[3]提出基于超鏈接來源多樣性分析的網頁排名算法Drank,對超鏈接的數量、質量以及多樣性進行綜合分析。文獻[4]提出超鏈接誘導主題搜索 (Hyperlink Induced Topic Search,HITS)算法,將網頁分為權威型和目錄型。文獻[5]提出一種基于路徑信任知識圖的方法。在網頁內容分析法中,寬度優先搜索(Breadth First Search,BFS)[6]和最佳優先搜索(Optimum Prior Search,OPS)[7]是常用的2種主題爬行算法。BFS算法利用先進先出隊列輔助搜索網頁,但其忽視了鏈接的優先權。OPS算法在計算鏈接的優先權值后會先訪問優先權最高的鏈接,然而其容易陷入局部最優的困境,遺漏更多與主題相關的網頁。此外,文獻[8]提出基于語義相似度向量空間模型的主題爬蟲方法,通過整合術語TF-IDF值和術語之間的語義相似度來計算網頁文本主題相關度。文獻[9]提出一種Shark Search算法,結合相似度度量方法對網頁進行模糊主題相關性計算?；诔溄油負浣Y構的主題爬蟲方法注重超鏈接結構,側重于抓取權威性強且質量高的網頁,但較少考慮主題相關度。而基于網頁內容分析的主題爬蟲方法在鏈接價值預測方面存在不足,容易忽視鏈接結構對結果的影響。

傳統主題爬蟲方法主要采用關鍵詞進行匹配檢索,但由于該方法存在一詞多義或一義多詞情況,導致遺漏更多相關網頁。針對該問題,研究人員提出基于語義分析的主題爬蟲方法。例如,文獻[10]提出一種基于領域本體的應急計劃主題爬蟲策略,通過構建領域本體來定義主題,并采用URL模式庫對爬行鏈接的相關度進行預測。文獻[11]提出利用概念背景圖指導主題爬蟲檢索與用戶主題高度相關的網頁,將被抓取網頁的知識背景和語義應用于主題爬蟲。另外,針對OPS算法不考慮全局最優解決方案的問題,研究人員提出基于智能優化算法的主題爬蟲策略。文獻[12]在用戶瀏覽行為優化遺傳操作的基礎上,提出基于改進遺傳算法的主題爬蟲方法。文獻[13]提出使用貪婪啟發式策略和遺傳算法相結合的主題爬蟲方法,通過使用不同的重組算子改善爬行性能。文獻[14]針對爬行過程易陷入局部最優的問題,設計出結合爬蟲記憶歷史主機信息和模擬退火的主題爬蟲策略。

針對目前主題爬蟲方法容易偏離主題和陷入局部最優的問題,本文提出一種基于多目標蟻群優化 (Multi-Objective Ant Colony Optimization,MOACO) 算法的主題爬蟲方法。采用鏈接錨文本主題相關度、鏈接指向網頁主題相關度以及鏈接所在網頁主題相關度建立鏈接的多目標優化模型,利用MOACO中智能體的信息素交互行為和正反饋機制,從全局角度尋找Pareto最優鏈接來確定智能體搜索方向,以獲取主題相關度高的網頁。

1 主題描述

主題描述的任務是針對某個特定主題,根據一定的模型和方法將抽象的主題內容轉變為可量化計算與對比的形式,并使用主題向量表達主題內容。目前使用較多的相關性判斷方法的原理是比較目標網頁與基準之間的差異,該基準即主題向量,因此,在計算網頁相關度前需獲取主題向量。傳統的主題描述方法主要基于特征詞[15],但是常忽略特征詞之間的語義關系,且特征詞分布過于稀疏,降低了對主題內容的表達能力?？紤]到本體能夠在語義和知識層面上描述信息,因此,本文利用領域本體構建主題向量進行主題描述。

1.1 領域本體構建

領域本體的構建方法主要包括人工構建方法、半自動構建方法和全自動構建方法。在人工構建方法中,概念和概念之間的關系由具備相關領域知識的專家確定,該方法耗費時間較長,且本體質量會受到領域專家知識儲備及個人主觀性的影響。全自動構建方法較少,不僅難以實現,而且構建的本體質量不高。因此,本文采用一種基于形式概念分析(Formal Concept Analysis,FCA)的半自動方法構建領域本體。FCA是一種數據分析方法,其主要的數據結構——概念格是由多個概念節點組成的圖模型,概念節點由外延和內涵組成。FCA方法生成概念格的過程實質上是一種概念聚類,即將數據中隱含的概念及其關系形式化。由于FCA方法具有自動獲取概念之間層次關系并挖掘隱藏關系的能力,因此其作為有效的半自動領域本體構建方法受到研究人員的關注。本文構建領域本體方法的具體步驟如下:

1)確定主題。選出5個主題特征詞作為查詢項,輸入到Google、百度、必應等搜索引擎,從這些搜索引擎返回的結果中選取排名前50個網頁,使用開源的分詞工具IK-Analyzer從上述網頁的文本中選出能描述主題的特征詞組成文檔集合與術語集合。

2)“文檔-術語”矩陣構建。采用上述文檔集合和術語集合,建立“文檔-術語”矩陣,該矩陣即形式化背景,用三元組F=(UrlSet,Terminology,Relation)來表示,其中,UrlSet為網頁文檔集合,Terminology為術語集合,Relation為文檔與術語之間的關系。

3)將形式化背景輸入開發工具ConExp中,自動構建概念格,并用Hasse圖表示。概念格中1個概念節點代表1個概念Node=(Obj,Att),外延Obj是UrlSet中的文檔,內涵Att是Terminology中的術語。

4)利用本體Web語言和所構建概念格對概念之間的語義關系進行形式化描述,并采用Protégé本體開發工具對構建的本體進行可視化處理。

從領域本體中提取所有概念,構建主題向量T={t1,t2,…,tn},tn為第n個主題詞,n為主題詞數量。采用基于本體概念語義相似度的方法為主題向量的每個主題詞賦予主題語義權重。

1.2 主題語義權重向量獲取

參考文獻[16],利用領域本體計算概念之間的語義相似度,綜合考慮語義距離、概念密度、概念深度、概念重合度和概念語義關系等概念之間相似度的影響因素。

定義1(語義距離) 概念C1和概念C2之間的語義距離Dis(C1,C2)用其在本體樹最短路徑上的數量表示。C1和C2的語義距離影響因子IFDis計算公式如下:

(1)

其中:τ為調節因子,且τ為大于0的實數;若C1和C2之間的最短路徑語義距離Dis(C1,C2)越大,則語義距離影響因子IFDis越小,其相似度也越小。

定義2(概念密度) 概念C1和概念C2之間的概念密度用C1和C2在本體樹上最近共同祖先所包含的直接子節點個數表示。C1和C2的概念密度影響因子IFDen計算公式如下:

(2)

其中,CS為C1和C2的最近公共祖先概念節點,Density(CS)為CS的直接子概念節點數,Density(O)為整個本體樹上所有概念節點擁有子概念節點最多的概念節點子概念節點數。若最近公共祖先概念節點包含的直接子節點數越多,則概念密度影響因子越大,其語義相似度越大。

定義3(概念深度) 概念C的概念深度通過概念節點與本體樹根節點之間最短路徑上的數量表示。C1和C2的概念深度影響因子IFDep計算公式如下:

(3)

其中:Depth(C)為概念C在本體樹的層次深度,即概念C到本體樹根節點最短路徑的長度;Depth(O)為在整個本體樹中所有概念的最大層次深度;Depth(CS)為C1和C2的最近公共祖先概念節點CS在本體樹中層次深度。由于在本體樹中層次深度越大的概念越具體,因此在語義距離相同的情況下,距離本體樹根節點較遠的2個概念節點相似度比距離根節點較近的2個概念節點相似度大。

定義4(概念重合度) 概念C1和概念C2之間的概念重合度用C1和C2包含的本體樹中公共祖先節點數量來表示。C1和C2的概念重合度影響因子IFCoi的計算公式如下:

(4)

其中,count(Up(C1)∩(Up(C2))為概念C1和C2包含的公共祖先節點數,max(Depth(C1),Depth(C2))表示概念C1和C2中層次深度最大值。若2個概念節點的公共節點數量越多,則其概念重合度越高,相似度也越大。

定義5(概念語義關系) 本文考慮同義關系(Synonym),被引發關系(Induced-By)和繼承關系(Is-a) 3種語義關系。根據領域專家意見分別賦予這3種關系權值為1、1/2和1/3。C1和C2的概念語義關系影響因子IFRel的計算公式如下:

(5)

其中,NS為C1和C2之間最短路徑上的邊數;Ci為最短路徑上的第i個概念節點,Fi為Ci的父概念,Value(Ci,Fi)為概念節點Ci與其父概念節點Fi之間的有向邊權重。

綜合以上5種影響因素,C1和C2之間的概念語義相似度sim(C1,C2)計算公式如下:

sim(C1,C2)=k1×IFDis+k2×IFDen+k3×IFDep+

k4×IFCoi+k5×IFRel

(6)

其中,調節因子k1～k5根據專家經驗獲取,且滿足k1+k2+k3+k4+k5=1。

為獲取主題語義權重向量,首先確定1個主題概念C,然后根據1.1節獲取的主題向量T={t1,t2,…,ti,…,tn},根據式(6)計算主題向量T中每個主題詞與主題概念C之間的概念語義相似度,最終得到主題語義權重向量WT= {wt1,wt2,…,wti,…,wtn},其中,wti為主題向量中第i個主題詞的主題語義權重,即主題概念C和主題詞ti之間的語義相似度值。WT計算公式如下:

WT=(sim(C,t1),sim(C,t2),…,sim(C,ti),…,

sim(C,tn))

(7)

2 主題相關度計算

2.1 網頁文本內容主題相關度計算

超文本標記語言(Hyper Text Markup Language,HTML)網頁由于具有簡易性、可擴展性、平臺無關性和通用性等特點,因此在萬維網上被廣泛應用。HTML通過標記符號來標記所需要顯示網頁中各部分內容,且標記符號通常成對出現。將選取的主要標簽分為5組:G1=(標題、關鍵詞、描述、一級標題);G2=(二級標題、三級標題);G3=(四級標題、五級標題、六級標題、加粗文字);G4=(正文信息);G5=(非正文信息)。由于從不同標簽內容提取的主題詞對整個網頁主題相關性的影響不同,因此本文經多次實驗并參考國內外研究成果,給予不同標簽不同的權重值Wl=(2,1.5,1.2,1.0,0.2)。

將網頁文本映射為1個特征向量D={d1,d2,…,di,…,dn},得到相對應的特征權重向量WD={wd1,wd2,…,wdi,…,wdn}。網頁文本特征權重向量的取值采用改進的詞頻-逆文檔頻率(TF-IDF)模型如下:

(8)

其中,tfi,l為第i個主題詞在網頁文本第l個位置規范化后的詞頻;fi,l為第i個主題詞在網頁文本第l個位置的詞頻;maxfi,l為第i個主題詞在網頁文本中所有出現位置中出現次數最多的詞頻;L為網頁文本被標簽分段的組數(本文中L=5);Wl為第l組標簽的權重。

通過上述方法獲得主題詞語義向量WT和網頁文本特征權重向量WD,通過計算主題詞語義權重向量和網頁文本特征權重向量的余弦(即采用向量空間模型(VSM))來確定網頁文本內容主題相關度。網頁P的主題相關度計算公式如下:

R(P)=Sem(T,D)=

(9)

R(P)的值域為[0,1],如果主題詞語義權重向量和網頁文本特征權重向量的夾角越小,則網頁內容主題相關度R(P)越大;反之,R(P)越小。設置閾值σ,若R(P)≥σ,則認為網頁P與預先選定的主題相關。

2.2 鏈接主題相關度計算

在主題爬蟲不斷獲取鏈接的過程中,難以避免會抓取到與主題相關度較低或者不相關的鏈接,因此,需要對鏈接進行相關度計算。通過過濾相關度較低的鏈接,保證爬蟲能夠篩選出高質量的網頁。本文以鏈接的錨文本主題相關度、鏈接所在網頁的主題相關度以及鏈接指向網頁的主題相關度作為判斷鏈接是否與主題相關的3個指標。

1)由于錨文本內容直指主題,篇幅較短,因此鏈接的錨文本主題相關度為鑒別鏈接是否與主題相關的1個重要評價指標。對于鏈接l的錨文本al,計算鏈接錨文本主題相關度的前提是計算鏈接錨文本的特征權重,本文使用改進TF-IDF模型[17]計算鏈接的錨文本特征權重,計算公式如下:

(10)

本文使用VSM方法,通過計算主題詞的語義權重向量WT和錨文本權重向量WA=(wa1,wa2,…,wai,…,wan)的余弦來獲取錨文本al的主題相關度,計算公式如下:

R(al)=Sem(T,al)=

(11)

其中,R(al)取值范圍為0～1,其越接近1,說明鏈接l的錨文本主題相關度越高。

2)由于鏈接指向網頁的內容通常與鏈接所在網頁的內容相關聯,前者可能是后者的具體說明或闡述,因此鏈接指向網頁的主題相關度和鏈接所在網頁的主題相關度均為判斷鏈接是否與主題相關的重要指標。對于鏈接l所指向的網頁Pu,用U={u1,u2,…,ui,…,un}表示其文本特征向量,利用式(8)中的TF-IDF模型計算相應的文本特征權重向量Wu=(wu1,wu2,…,wui,…,wun)。其中,wui為第i個主題詞在網頁文本Pu中的權重。根據式(9),鏈接l指向網頁主題相關度的表達式為:

R(Pu)=Sem(T,U)

(12)

根據上述分析,得到鏈接主題相關度計算公式如下:

R(l)=t1×R(al)+t2×R(Pl)+t3×R(Pu)

(13)

其中:t1、t2、t3分別為鏈接l的錨文本主題相關度、鏈接所在網頁主題相關度以及鏈接指向網頁主題相關度的權重系數,且滿足t1+t2+t3=1;R(Pl)為鏈接l所在網頁P的主題相關度,可由式(9)計算得到。設置鏈接相關度閾值為η,若R(l)≥η,則表示鏈接l與主題相關。

3 種子鏈接的選取

在主題爬行的過程中,如果所選取種子鏈接指向的網頁中包含描述主題的多樣化術語,則不僅可加快網絡爬蟲的工作效率,還能擴大爬蟲覆蓋率。在選取種子鏈接的過程中,應篩選與主題相關的多樣化術語作為查詢項,以獲取多樣化的鏈接,具體流程如下:

1)設置候選種子鏈接數k=50,以主題詞為查詢項,通過傳統搜索引擎進行搜索,并獲取網頁文本。

2)對獲取的網頁文本進行解析和分詞,利用VSM方法和構建好的領域本體計算網頁文本的主題相關度。設置閾值v,若某網頁文本的主題相關度大于閾值v,則將該網頁文本分類到主題相關的文檔集合,否則分類到與主題不相關的文檔集合。同時將與主題相關網頁文本所對應的URL鏈接加入到候選鏈接集合IQ中。本文利用結巴分詞工具從與主題相關的網頁文檔中提取新特征詞[18]。

3)將新特征詞依次作為查詢項來搜索新網頁。

4)若IQ中鏈接的數量大于或等于k,則轉到步驟5,否則轉到步驟2。

5)結合領域專家意見,對候選鏈接集合中k個鏈接進行篩選,最終選出30個鏈接作為種子鏈接。

4 多目標蟻群算法主題爬蟲策略

由于鏈接主題相關度受網頁內容和錨文本等多種因素影響,因此傳統主題爬蟲方法通常將各因素的主題相關度進行線性加權求和作為待訪問鏈接的主題相關度,并采用單目標優化方法確定爬蟲的搜索方向。盡管該方法通常能有效指導主題爬蟲跳出局部最優的困境,然而由于線性加權求和方法存在難以合理確定最優權重系數和規范化目標函數的問題,因此即使各因素的主題相關度計算非常準確,得到的待爬行鏈接的主題相關度仍可能存在較大偏差,從而使爬行偏離主題,爬回大量與主題不相關的網頁。本文基于鏈接的錨文本主題相關度、鏈接指向網頁的主題相關度以及鏈接所在網頁的主題相關度建立鏈接多目標優化模型,提出一種基于多目標蟻群優化算法的主題爬蟲方法。采用MOACO算法能得到1組Pareto最優的鏈接以引導主題爬蟲方向,從而解決基于單目標優化的傳統主題爬蟲方法難以合理確定各因素主題相關度最優權重因子的問題。

4.1 目標函數

為評價待訪問鏈接l的主題相關度,綜合考慮鏈接的錨文本和網頁文本的主題相關度,給出選擇最優鏈接l的3個目標函數如下:

maxF1=R(al)

(14)

maxF2=R(Pl)

(15)

maxF3=R(Pu)

(16)

其中,R(al)、R(Pl)和R(Pu)分別為鏈接l的錨文本al主題相關度、鏈接l所在網頁Pl的主題相關度以及鏈接l指向網頁Pu的主題相關度。

4.2 多目標蟻群算法

蟻群優化(Ant Colony Optimization,ACO)算法是研究人員受蟻群覓食行為啟發而提出的全局優化算法。ACO算法使用一定數量的智能體(螞蟻)反復構建優化問題的可行解,并在每輪構建可行解的過程中留下信息素,可行解質量越好,留下的信息素濃度就越高。在不斷積累的過程中,螞蟻會在正反饋機制作用下集中到最優路徑,即得到問題的最優解。在單目標ACO算法中,在正反饋機制作用下,螞蟻會向信息素濃度高的地方聚集。然而在多目標優化問題中,這種行為會使解匯聚在某個區域,從而破壞群體的多樣性。因此,利用多目標蟻群優化MOACO算法求解多目標函數優化問題不同于單目標蟻群算法。

對于多目標優化問題,由于MOACO算法最終將得到1組Pareto最優解,因此要求所得解在收斂到Pareto前沿的同時還要保持多樣性。在MOACO算法中,如果1條路徑上通過的智能體越多,則留在路徑上的信息素濃度越高,該路徑被其他智能體選擇的概率就越高。同時,算法在執行過程中,會保存當前得到的非支配解,并利用其指導智能體的搜索方向。因此,MOACO算法中智能體搜索過程不僅受到路徑留下的信息素影響,也會受到所有智能體最優經驗的影響。在多目標蟻群優化算法中,智能體爬行路徑構建、信息素更新和多目標解的選擇是影響該算法的3個重要因素。

1)路徑構建

對于第k個智能體,假設在t時刻,其所在網頁為Pi,如果Pi中有1個鏈接指向網頁Pj,那么處于Pi的智能體將根據一定條件決定是否從Pi移動到Pj。假設V為Pi中所有鏈接指向新頁面的集合,利用偽隨機比例選擇規則計算出第k個智能體從當前網頁Pi到達網頁Pj的概率。偽隨機比例選擇規則公式如下:

(17)

2)信息素更新

在MOACO算法中,智能體每經過1個周期就會更新所有路徑的信息素,各路徑信息素濃度會隨著時間t的增長而降低。從頁面Pi到頁面Pj的鏈接l(i,j)上的信息素更新公式如下:

(18)

3)多目標解的選擇

對于MOACO算法獲得的1組p個Pareto最優鏈接,利用快速非支配排序方法[19]和最近最遠候選解(Nearest and Farthest Candidate Solution,NFCS)方法[20],從中選擇q(q≤p)個鏈接加入到最優鏈接集BP中,以引導爬蟲的搜索方向。采用NFCS方法計算任意2個解(網頁)XS和XY之間的目標函數距離Dis(XS,XY),計算公式如下:

(19)

其中:Fi(XS)和Fi(XY)分別為XS和XY的第i個目標函數值;m為目標函數的個數,本文中m=3。

本文利用1個隊列CQ存放通過快速非支配排序法獲取的所有非支配解,使用NFCS方法從隊列CQ中選取1組鏈接,這些鏈接指向的網頁將作為多目標蟻群算法下個周期的初始爬行節點。圖1為從12個基于目標F1和F2的Pareto最優解中使用不同方法挑選出5個最優解組成的最優解集,其中,圖1(a)中實心圓是使用NFCS方法選出的最優解集,圖1(b)中實心圓是使用NSGA-Ⅱ中擁擠度方法[19]選出的最優解集,數字表示解選擇的次序,空心圓為未被上述2種方法選中的最優解。可以看出,NFCS方法相較擁擠度方法能得到更均勻的Pareto前沿,且獲得的Pareto最優解更具多樣性。

圖1 使用不同方法得到的最優解集

4.3 基于多目標蟻群算法的主題爬蟲策略設計

在多目標蟻群優化算法主題爬行過程中,設置m個智能體(螞蟻),每個智能體從當前網頁的子鏈接中利用偽隨機比例選擇規則和輪盤賭方法選出下個爬取的網頁,并將當前網頁中所有子鏈接放入等待隊列。對于新加入等待隊列中的每個鏈接,根據式(13)計算其主題相關度,若主題相關度大于預先設置的閾值η,則將該鏈接指向的網頁放入下載網頁集合中;若放入下載網頁集合中網頁的主題相關度大于閾值σ,則將該網頁同時放入保存網頁集合中。智能體在經過的路徑留下信息素,并到達新的網頁節點。重復此構建智能體爬行路徑的過程,直到每個智能體都達到最大爬行深度,然后通過式(18)更新所有爬行路徑上的信息素濃度。對于等待隊列中所有鏈接進行非支配排序,并采用NFCS方法選出1組Pareto最優鏈接作為爬蟲新一輪爬行的初始鏈接(即智能體爬行路徑的起點),再繼續下一輪爬行?；诙嗄繕讼伻簝灮惴ǖ闹黝}爬蟲策略具體步驟如下:

1)通過1.1節所述方法構建的領域本體獲取主題向量;根據種子鏈接的選取方法獲取30個種子鏈接,并放入起始鏈接隊列(LinkInit);初始化控制參數α和β以及信息素衰減因子ρ,智能體數量m=30,最大深度MaxDepth=7,頁面相關度閾值為σ,鏈接優先度評價閾值為η,保存頁面集合(PageSave),下載頁面集合(PageDown),等待鏈接隊列(LinkWait)和子鏈接集合(LinkChild)。

2)初始化起始鏈接隊列中每個鏈接的信息素濃度C0;將m個智能體的初始位置(LinkInit中的鏈接指向的網頁)放入禁忌表Tabu中;設置爬行深度t=1。

3)依次對第m個智能體進行爬蟲操作,即Fork:=1 tomdo。

(1)獲取第k個智能體當前所在網頁Pi的所有子鏈接,并進行過濾操作(刪除重復出現的鏈接),將過濾后的子鏈接放入集合LinkChild中。

(2)根據式(9)計算網頁Pi的主題相關度。

(3)根據式(12)計算集合LinkChild中每個鏈接指向網頁的主題相關度,并根據式(11)計算所有子鏈接的錨文本主題相關度。

(5)對于LinkChild中每個鏈接l,根據式(13)將鏈接l所指向網頁的主題相關度、鏈接l的錨文本相關度和鏈接l所在網頁的主題相關度進行線性加權求和,從而得到鏈接l的主題相關度R(l)。

(6)對于LinkChild中每個鏈接l,若鏈接l的主題相關度R(l)大于閾值η,則將該鏈接l指向的網頁Pk加入下載頁面集合PageDown,并將網頁Pk對應的鏈接l放入等待鏈接隊列LinkWait,此時若網頁Pk的主題相關度R(Pk)大于閾值σ,則也將該網頁Pk加入保存頁面集合PageSave;否則將鏈接l舍棄。當LinkChild中所有鏈接都遍歷后,清空集合LinkChild。

4)若下載頁面集合PageDown中網頁數量大于15 000,則算法結束;否則轉到步驟5。

5)若爬行深度t達到最大深度MaxDepth,則清空禁忌表Tabu和起始鏈接隊列LinkInit,轉到步驟6;否則,令t=t+1,轉到步驟3。

6)按照信息素更新式(18),以更新所有路徑上的信息素濃度。

7)對于LinkWait中的所有鏈接,計算每個鏈接所在頁面的主題相關度、鏈接錨文本的主題相關度、鏈接指向頁面的主題相關度3個目標函數值,并利用快速非支配排序方法和最近最遠候選解方法,選取m個鏈接放入起始鏈接隊列LinkInit,作為新一輪的初始鏈接,清空LinkWait和LinkChild,轉到步驟2。

5 實驗與結果分析

本文實驗采用聯想90DSCTO1WW臺式機,實驗環境為:Intel?CoreTMi5-6500處理器,3.20 GHz CPU,Windows10操作系統。開發工具為Eclipse2019_03和JDK1.8.0。

5.1 算法評價指標

評價主題爬蟲性能的常用指標為爬準率(Accuracy)和爬全率(Recall)。爬準率是主題爬蟲爬取到與主題相關的網頁數量占總網頁數量的比例。爬全率是主題爬蟲爬取到與主題相關網頁數量占整個網絡中與主題相關網頁數量的比例。爬準率和爬全率的表達式如下:

(20)

(21)

其中,N為爬蟲爬取到與主題相關網頁數量,W為整個網絡中與主題相關網頁數量,T為爬蟲爬取到的總網頁數量。由于在整個網絡中與主題相關的網頁資源龐大且更新太快,爬全率很難計算,因此本文不采用爬全率作為爬蟲性能的評價指標。

由于當前沒有主題爬蟲性能評價標準,因此為進一步對主題爬蟲的結果進行分析,本文采用所有被爬取網頁的平均主題相關度和標準差來分析算法性能。爬取到所有網頁集合平均主題相關度RT和標準差SDT的表達式如下:

(22)

(23)

其中,R(Pi)為網頁Pi的主題相關度,T為爬取到的總網頁數量。

5.2 結果分析

本文設置爬蟲主題為暴雨災害,采用本文所提基于FCA的半自動方法構建暴雨災害領域本體。由于當前對蟻群算法中參數研究未有嚴格的理論基礎,因此式(17)、式(18)中信息素蒸發率ρ、信息素重要性參數α、啟發式信息重要性參數β等均為多次實驗的經驗值。通過大量實驗,確定ρ=0.7、α=0.3、β=6.0、η=0.1以及MaxDepth=7。主題爬蟲中頁面相關度閾值σ的設置對爬蟲的結果至關重要,若閾值設置過低,則爬取到的網頁與主題相關性不大;若閾值設置過高,則爬取到的網頁數量大幅減少,將遺漏與主題相關的網頁。本文設置頁面相關度閾值σ=0.62,爬蟲算法結束條件為下載網頁數量達到15 000。

在相同的實驗條件下,分別測試寬度優先搜索(BFS)算法[6]、最佳優先搜索(OPS)算法[7]、網頁空間進化(WSE)算法[20]、基于模擬退火的主題爬蟲策略(FCSA)算法[14]和多目標蟻群優化算法(MOACO)算法的爬準率,結果如圖2所示。可以看出:MOACO算法的爬準率除了在運行初期有起伏之外,其他階段均為平穩增長,且當爬取的網頁數量達到6 500時,MOACO算法的爬準率高于其他4種算法,最終爬準率穩定在89%;在整個搜索網頁過程中,BFS算法的爬準率變化起伏很大,最終穩定在30%;OPS算法的爬準率在運行初期有明顯增長,但當爬取網頁總數量達到5 000時,其爬準率快速下降,最終穩定在50%;FCSA算法的爬準率在爬取網頁過程中穩定在70%;WSE算法的爬準率在初期出現下降,但整體呈現穩定增長趨勢,最終穩定在76%。

圖2 5種算法的爬準率對比

圖3為5種算法在爬取與主題相關網頁數量的對比?？梢钥闯?MOACO算法爬取到與主題相關網頁的數量較另外4種算法更多。結合圖2可知,FCSA、WSE和MOACO這3種智能優化算法的爬準率和搜索相關網頁能力高于另外2種算法,且在搜索策略上更具有全局性,能盡量避免爬蟲陷入局部最優的困境,從而抓取到更多與主題相關的網頁。MOACO算法由于其自身的正反饋機制,因此能較快找到相關度高的網頁。此外,MOACO算法通過多目標優化選取1組Pareto最優鏈接確定智能體搜索網頁的方向,解決了單目標算法難以合理確定目標權重和標準化目標函數值的問題,提高了爬蟲搜索相關網頁的能力。

圖3 5種算法爬取的主題相關網頁數量對比

圖4為5種算法在爬取網頁平均主題相關度的對比。在整個爬蟲爬行過程中,MOACO算法的平均主題相關度不斷上升,當網頁數量達到15 000時,其平均主題相關度約為0.79,高于另外4種算法。

圖4 5種算法對于爬取網頁的平均主題相關度對比

圖5為5種算法在爬取網頁主題相關度的標準差對比,算法的標準差越低,說明算法越穩定。雖然MOACO算法標準差在運行初期很高,但是其整體呈現不斷下降趨勢,且在爬取網頁總數達15 000時,標準差約為0.17,該值僅高于WSE算法,但是低于其他3種算法,這說明MOACO算法的爬行性能較穩定。由上述可知,MOACO算法在5種主題爬蟲算法中性能最優。

圖5 5種算法對于爬取網頁主題相關度的標準差對比

6 結束語

本文提出一種采用多目標蟻群優化算法的主題爬蟲方法。對螞蟻覓食的行為進行模擬,通過正反饋機制并利用智能體之間信息素的交互引導爬行方向,將基于改進TF-IDF的錨文本相關度、基于位置加權方法計算的網頁主題相關度以及鏈接指向網頁主題相關度為目標函數建立鏈接主題相關度模型,以選取Pareto最優鏈接并作為智能體的尋優方向,從而獲取更多與主題相關的網頁。實驗結果表明,該方法較FCSA、WSE等方法爬準率更高。后續將在語義方面優化爬蟲的主題描述,進一步提高爬蟲抓取網頁的準確率。