基于多目標(biāo)蟻群算法的主題爬蟲策略

東 熠,劉景發(fā),劉文杰

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

0 概述

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

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

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

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

1 主題描述

主題描述的任務(wù)是針對某個特定主題,根據(jù)一定的模型和方法將抽象的主題內(nèi)容轉(zhuǎn)變?yōu)榭闪炕嬎闩c對比的形式,并使用主題向量表達(dá)主題內(nèi)容。目前使用較多的相關(guān)性判斷方法的原理是比較目標(biāo)網(wǎng)頁與基準(zhǔn)之間的差異,該基準(zhǔn)即主題向量,因此,在計算網(wǎng)頁相關(guān)度前需獲取主題向量。傳統(tǒng)的主題描述方法主要基于特征詞[15],但是常忽略特征詞之間的語義關(guān)系,且特征詞分布過于稀疏,降低了對主題內(nèi)容的表達(dá)能力?？紤]到本體能夠在語義和知識層面上描述信息,因此,本文利用領(lǐng)域本體構(gòu)建主題向量進(jìn)行主題描述。

1.1 領(lǐng)域本體構(gòu)建

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

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

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

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

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

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

1.2 主題語義權(quán)重向量獲取

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

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

(1)

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

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

(2)

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

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

(3)

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

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

(4)

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

定義5(概念語義關(guān)系) 本文考慮同義關(guān)系(Synonym),被引發(fā)關(guān)系(Induced-By)和繼承關(guān)系(Is-a) 3種語義關(guān)系。根據(jù)領(lǐng)域?qū)＜乙庖姺謩e賦予這3種關(guān)系權(quán)值為1、1/2和1/3。C1和C2的概念語義關(guān)系影響因子IFRel的計算公式如下:

(5)

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

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

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

k4×IFCoi+k5×IFRel

(6)

其中,調(diào)節(jié)因子k1～k5根據(jù)專家經(jīng)驗獲取,且滿足k1+k2+k3+k4+k5=1。

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

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

sim(C,tn))

(7)

2 主題相關(guān)度計算

2.1 網(wǎng)頁文本內(nèi)容主題相關(guān)度計算

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

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

(8)

其中,tfi,l為第i個主題詞在網(wǎng)頁文本第l個位置規(guī)范化后的詞頻;fi,l為第i個主題詞在網(wǎng)頁文本第l個位置的詞頻;maxfi,l為第i個主題詞在網(wǎng)頁文本中所有出現(xiàn)位置中出現(xiàn)次數(shù)最多的詞頻;L為網(wǎng)頁文本被標(biāo)簽分段的組數(shù)(本文中L=5);Wl為第l組標(biāo)簽的權(quán)重。

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

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

(9)

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

2.2 鏈接主題相關(guān)度計算

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

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

(10)

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

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

(11)

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

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

R(Pu)=Sem(T,U)

(12)

根據(jù)上述分析,得到鏈接主題相關(guān)度計算公式如下:

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

(13)

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

3 種子鏈接的選取

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

1)設(shè)置候選種子鏈接數(shù)k=50,以主題詞為查詢項,通過傳統(tǒng)搜索引擎進(jìn)行搜索,并獲取網(wǎng)頁文本。

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

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

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

5)結(jié)合領(lǐng)域?qū)＜乙庖?對候選鏈接集合中k個鏈接進(jìn)行篩選,最終選出30個鏈接作為種子鏈接。

4 多目標(biāo)蟻群算法主題爬蟲策略

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

4.1 目標(biāo)函數(shù)

為評價待訪問鏈接l的主題相關(guān)度,綜合考慮鏈接的錨文本和網(wǎng)頁文本的主題相關(guān)度,給出選擇最優(yōu)鏈接l的3個目標(biāo)函數(shù)如下:

maxF1=R(al)

(14)

maxF2=R(Pl)

(15)

maxF3=R(Pu)

(16)

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

4.2 多目標(biāo)蟻群算法

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

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

1)路徑構(gòu)建

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

(17)

2)信息素更新

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

(18)

3)多目標(biāo)解的選擇

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

(19)

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

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

圖1 使用不同方法得到的最優(yōu)解集

4.3 基于多目標(biāo)蟻群算法的主題爬蟲策略設(shè)計

在多目標(biāo)蟻群優(yōu)化算法主題爬行過程中,設(shè)置m個智能體(螞蟻),每個智能體從當(dāng)前網(wǎng)頁的子鏈接中利用偽隨機比例選擇規(guī)則和輪盤賭方法選出下個爬取的網(wǎng)頁,并將當(dāng)前網(wǎng)頁中所有子鏈接放入等待隊列。對于新加入等待隊列中的每個鏈接,根據(jù)式(13)計算其主題相關(guān)度,若主題相關(guān)度大于預(yù)先設(shè)置的閾值η,則將該鏈接指向的網(wǎng)頁放入下載網(wǎng)頁集合中;若放入下載網(wǎng)頁集合中網(wǎng)頁的主題相關(guān)度大于閾值σ,則將該網(wǎng)頁同時放入保存網(wǎng)頁集合中。智能體在經(jīng)過的路徑留下信息素,并到達(dá)新的網(wǎng)頁節(jié)點。重復(fù)此構(gòu)建智能體爬行路徑的過程,直到每個智能體都達(dá)到最大爬行深度,然后通過式(18)更新所有爬行路徑上的信息素濃度。對于等待隊列中所有鏈接進(jìn)行非支配排序,并采用NFCS方法選出1組Pareto最優(yōu)鏈接作為爬蟲新一輪爬行的初始鏈接(即智能體爬行路徑的起點),再繼續(xù)下一輪爬行。基于多目標(biāo)蟻群優(yōu)化算法的主題爬蟲策略具體步驟如下:

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

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

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

(1)獲取第k個智能體當(dāng)前所在網(wǎng)頁Pi的所有子鏈接,并進(jìn)行過濾操作(刪除重復(fù)出現(xiàn)的鏈接),將過濾后的子鏈接放入集合LinkChild中。

(2)根據(jù)式(9)計算網(wǎng)頁Pi的主題相關(guān)度。

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

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

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

4)若下載頁面集合PageDown中網(wǎng)頁數(shù)量大于15 000,則算法結(jié)束;否則轉(zhuǎn)到步驟5。

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

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

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

5 實驗與結(jié)果分析

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

5.1 算法評價指標(biāo)

評價主題爬蟲性能的常用指標(biāo)為爬準(zhǔn)率(Accuracy)和爬全率(Recall)。爬準(zhǔn)率是主題爬蟲爬取到與主題相關(guān)的網(wǎng)頁數(shù)量占總網(wǎng)頁數(shù)量的比例。爬全率是主題爬蟲爬取到與主題相關(guān)網(wǎng)頁數(shù)量占整個網(wǎng)絡(luò)中與主題相關(guān)網(wǎng)頁數(shù)量的比例。爬準(zhǔn)率和爬全率的表達(dá)式如下:

(20)

(21)

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

由于當(dāng)前沒有主題爬蟲性能評價標(biāo)準(zhǔn),因此為進(jìn)一步對主題爬蟲的結(jié)果進(jìn)行分析,本文采用所有被爬取網(wǎng)頁的平均主題相關(guān)度和標(biāo)準(zhǔn)差來分析算法性能。爬取到所有網(wǎng)頁集合平均主題相關(guān)度RT和標(biāo)準(zhǔn)差SDT的表達(dá)式如下:

(22)

(23)

其中,R(Pi)為網(wǎng)頁Pi的主題相關(guān)度,T為爬取到的總網(wǎng)頁數(shù)量。

5.2 結(jié)果分析

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

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

圖2 5種算法的爬準(zhǔn)率對比

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

圖3 5種算法爬取的主題相關(guān)網(wǎng)頁數(shù)量對比

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

圖4 5種算法對于爬取網(wǎng)頁的平均主題相關(guān)度對比

圖5為5種算法在爬取網(wǎng)頁主題相關(guān)度的標(biāo)準(zhǔn)差對比,算法的標(biāo)準(zhǔn)差越低,說明算法越穩(wěn)定。雖然MOACO算法標(biāo)準(zhǔn)差在運行初期很高,但是其整體呈現(xiàn)不斷下降趨勢,且在爬取網(wǎng)頁總數(shù)達(dá)15 000時,標(biāo)準(zhǔn)差約為0.17,該值僅高于WSE算法,但是低于其他3種算法,這說明MOACO算法的爬行性能較穩(wěn)定。由上述可知,MOACO算法在5種主題爬蟲算法中性能最優(yōu)。

圖5 5種算法對于爬取網(wǎng)頁主題相關(guān)度的標(biāo)準(zhǔn)差對比

6 結(jié)束語

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