基于多目标蚁群算法的主题爬虫策略

东 熠,刘景发,刘文杰

(1.南京信息工程大学 计算机与软件学院,南京 210044; 2.广东外语外贸大学 a.广州市非通用语种智能处理重点实验室; b.信息科学与技术学院,广州 510006)

0 概述

随着科技的飞速发展,信息已成为一种重要资源,而信息的有效获取对各领域都至关重要。在气象领域,气象灾害数量占到自然灾害总数量的70%以上[1],严重威胁到人民群众生命财产安全,也给社会经济发展带来不利影响,例如,2016年天津暴雨造成受灾人口达到14万,直接经济损失超过2.5亿元[2]。因此,及时获取气象灾害预警与应急处理信息极为重要。互联网由于拥有海量数据资源,因而成为获取大量气象灾害信息的重要渠道。然而目前互联网通用搜索引擎查询结果相关性不高,不能满足用户个性化查询需求。为解决该问题,研究人员提出主题爬虫方法并对其展开深入研究。

主题爬虫方法主要包括传统基于启发式策略的经典爬行方法、基于概念语义的主题爬行方法和基于智能优化算法的主题爬行方法。传统启发式主题爬虫方法包括超链接拓扑结构法和网页内容分析法。针对超链接拓扑结构法,文献[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算法,结合相似度度量方法对网页进行模糊主题相关性计算。基于超链接拓扑结构的主题爬虫方法注重超链接结构,侧重于抓取权威性强且质量高的网页,但较少考虑主题相关度。而基于网页内容分析的主题爬虫方法在链接价值预测方面存在不足,容易忽视链接结构对结果的影响。

传统主题爬虫方法主要采用关键词进行匹配检索,但由于该方法存在一词多义或一义多词情况,导致遗漏更多相关网页。针对该问题,研究人员提出基于语义分析的主题爬虫方法。例如,文献[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等方法爬准率更高。后续将在语义方面优化爬虫的主题描述,进一步提高爬虫抓取网页的准确率。