-
当今,有效信息变得越来越重要,而网络爬虫正是穿梭于互联网中帮助人们自动获取信息的一把利器。据中国互联网络信息中心第49次调查报告显示[1],截至2021年12月,仅中国网页的数量就已经达到3 350亿个,全球互联网的网页数量更是难以估计,这使得传统搜索引擎很难满足特定用户的需求。因此,如何利用主题爬虫[2]抓取特定领域的数据,从而为特定人群提供个性化推荐已经成为许多学者研究的热点。
主题爬虫是一种旨在搜集某一领域数据的网络爬虫,它将使用某种策略和网页分析算法来降低传统网络爬虫因大量网页遍历而带来的代价,从而更有效地获取主题相关的信息。目前,主题爬虫的研究主要集中在链接的评价和搜索策略上。链接评价是指对链接相关性和重要性的评价。链接评价方法主要有基于网页内容分析的方法和基于链接结构分析的方法。前者的代表主要有Fish Search[3]和Shark Search[4];后者的代表主要有PageRank算法[5]与HITS(hyperlink−induced topic search)[6]算法。由于基于网页内容分析的主题爬虫方法仅考虑网页、锚文本等文本信息,缺乏对网页链接结构的考虑,所以容易导致爬虫陷入局部最优。基于链接结构分析的主题爬虫应用较为广泛,近年来一些学者进行了深入研究。文献[7]通过在Shark Search算法的基础上引入相关链接块的概念来解决链接的锚文本较为短小、不能准确表明链接指向主题相关性的缺陷。文献[8]以主机目标网站中若干相同目录路径中的页面聚合相关性作为领域相关性特征,提出一种拥有“领域功能”的主题爬虫方法。但该类方法由于未考虑链接的主题相关性,所以爬虫容易产生主题漂移现象[6]。鉴于此,一些学者尝试综合这两类方法来提高链接评价的准确性[9]。另外,搜索策略决定不同价值链接被访问的次序。传统的纯粹基于链接相关性高低的爬行策略难以使爬虫通过具有潜在价值的链接进行网页有效搜索。为提升主题爬虫的隧道穿越能力[10],引导主题爬虫以最小的代价从相关度低的区域跳转到相关度高的区域,文献[11-14]采用智能优化方法来改进爬虫的全局寻优能力。文献[11]为提取和揭示网络犯罪,使用基于蚁群优化的主题爬虫,为Web犯罪挖掘开发一种基于本体的优化方法。文献[12]将多目标优化算法引入主题爬虫,提出了一种基于网页空间进化(WSE)算法的主题爬虫方法。文献[13]进一步将WSE算法和领域本体相结合,提出了一种新的基于WSE的主题爬虫算法(focused crawler combining Web space evolution and ontology, FCWSEO)。在该算法中,通过构建领域本体建立主题模型,使用一种最近最远候选解法挑选Pareto最优链接。文献[14]为克服人工构建本体过程中构建者知识储备和主观意识的限制,提出了一种结合潜狄利克雷分布和Apriori算法的领域本体半自动构建方法。他们基于链接评估的多目标优化模型和改进的多目标蚁群优化算法来指导爬虫的搜索方向。文献[15]通过加入时间因子,动态调节适应度函数和遗传算子,在一定程度上避免了爬虫陷入循环爬行的陷阱。文献[16]结合爬虫记忆历史主机信息和模拟退火算法设计了暴雨灾害主题爬虫。文献[17]应用多目标蚁群算法来选择主题爬虫过程中的Pareto最优链接,进而引导爬虫搜索更多主题相关的页面。本质上,基于智能优化算法的主题爬虫以一定规则或概率接收主题相关度低的页面,具有全局优化的优点。但上述算法在链接搜索次序选择上缺乏对已爬取网页的统计,导致历史经验难以指导后续的网页搜索。特别是当爬虫距离主题相关页面较远时,常常出现主题偏移现象。
针对上述问题,本文提出一种基于Wang-Landau(WL)抽样的主题爬虫方法。该方法采用一组带有语义权重的向量来描述主题,并使用向量空间模型(vector space model, VSM)[18]分别计算链接对应的锚文本和链接指向网页文本的主题相关度;再利用PageRank算法从链接结构角度评价链接的重要性,进而选定具有潜在价值的链接。基于WL算法,将能量状态密度函数和直方图函数应用于主题爬行策略,通过统计状态密度的变化,决定主题爬虫是否接受目标链接,进而指导爬虫寻找一条合适的主题爬行路径。此外,为防止爬虫接受无关链接而导致主题搜索方向偏移,引入区域竞争策略挑选目标链接,以获得更好的爬行效果。
-
在主题爬虫过程中,本文综合考虑链接指向网页的主题相关度和链接锚文本主题相关度,并根据链接所在页面的重要性选择具有潜在价值的页面。
-
在主题爬虫中,一般采用一组特定术语组成的主题词向量TK来描述用户选定的特定主题,假设TK定义如下:
$$ {\bf{TK}}={{\rm{tk}}_{1}, {\rm{tk}}_{2}, \cdots, {\rm{tk}}_{n}} $$ (1) 式中,tki(i=1,2,···,n)表示第i个主题词;n为主题词集TK中元素的个数。本文以暴雨灾害和台风灾害为主题,根据领域专家经验和多次对比实验,设置描述暴雨灾害的主题词组分别为暴雨、气象、天气、灾害和预防,描述台风灾害的主题词组分别为台风、风暴潮、暴雨、气压和风力。令wtki为主题词tki的权重,其值主要基于特征提取的主题词权重计算方法和领域专家结合经验设定[12]。在主题词向量确定以后,为计算网页主题相关度,需要确定网页文本特征向量。本文采用IK-Analyzer对网页文本进行分词、去停用词等预处理。将处理之后的网页文本Pj用向量DKj表示:
$$ {\bf{DK}}_{j}={{\rm{dk}}_{j,1,}, {\rm{dk}}_{j,2}, \cdots, {\rm{dk}}_{j,i}, \cdots, {\rm{dk}}_{j,n}} $$ (2) 式中,dkj,i表示网页文本Pj中的第i个特征词。对于文本中的某个特征词,它的权重采用词频−逆文档频率(term frequency–inverse document frequency, TF-IDF) [19]方法计算:
$$ {w_{{\rm{d}}{{\rm{k}}_{j{\text{,}}i}}}} = \frac{{{n_{j,i}}}}{{\displaystyle\sum\limits_k {{n_{j,k}}} }} {{\rm{lg}} }\frac{{{D}}}{{1 + {{{D}}_i}}} $$ (3) 式中,nj,i表示在网页文本Pj中第i个特征词出现的次数;分母表示文本Pj中所有特征词出现的次数之和;D为当前爬取网页文本总数;Di为包含第i个特征词的网页文本数。某个词的权重越大,说明该词越能代表文档的特征。当词权重为0时,说明该词不出现于该网页。
对于链接l所在网页Pl,本文采用VSM计算主题向量TK和网页文本特征向量DKl的主题相关度R(Pl):
$$\begin{split} & R({P_l}) = {\rm{sim}}({\bf{TK}},{\bf{D}}{{\bf{K}}_l}) = \cos < {{\boldsymbol{W}}_{{\bf{TK}}}},{{\boldsymbol{W}}_{{\bf{D}}{{\bf{K}}_l}}} > = \\ &\qquad\qquad \frac{{\displaystyle\sum\limits_{i = 1}^n {{w_{{\rm{t}}{{\rm{k}}_i}}}{w_{{\rm{d}}{{\rm{k}}_{l,i}}}}} }}{{\sqrt {\displaystyle\sum\limits_{i = 1}^n {w_{_{{\rm{t}}{{\rm{k}}_i}}}^2} \displaystyle\sum\limits_{i = 1}^n {w_{_{{\rm{d}}{{\rm{k}}_{l,i}}}}^2} } }} \end{split}$$ (4) 式中,WTK为用户所指定主题词的权重向量;
$ {{\boldsymbol{W}}_{{\bf{D}}{{\bf{K}}_l}}} $ 为网页文本Pl(或锚文本)的特征权重向量。本文由式(4)分别计算待访问链接l所指向网页的主题相关度和其锚文本的主题相关度,再进行线性加权求和得到链接l的综合主题相关度:$$ R(l)= \partial R({\rm{anchor}}_{l})+(1-\partial ) R(P_{l}) $$ (5) 式中,R(l)表示链接l的综合主题相关度;R(anchorl)和R(Pl)分别为链接l的锚文本anchorl和链接l指向网页Pl的主题相关度;∂为权重系数。
由于基于网页文本内容和链接结构分析的主题爬虫方法在各自单独使用时其爬准率往往受限,因此通常相互结合使用,实现互补,进而提高爬虫抓取网页的准确率。此外,上述策略在计算链接优先度后,大多采取最佳优先机制进行网页抓取,该贪心策略往往容易使爬虫陷入局部最优。
-
从有潜在价值的网页出发,抓取更多主题相关页面,还可以从重要性的角度综合评价网页。一般地,网页的重要性主要由网页链接关系来衡量,本文采用PageRank算法来计算网页的重要性。PageRank算法的思想是通过网页的引用关系来判断网页是否重要,即若某网页被其他网页引用次数越多,就认为该网页越重要,而当某网页被这些重要的网页引用时,该网页也被认为是重要的。本文采用的PageRank计算公式为:
$$ {\rm{PR}}({P_j}) = (1 - \alpha ) + \alpha \sum\limits_{{P_i} \in {B_j}} {\frac{{{\rm{PR}}({P_i})}}{{|{C_i}|}}} $$ (6) 式中,PR(Pj)代表网页Pj的PR值;Bj为网页Pj的所有入链页面集;Ci为Pj的入链页面Pi的出链集合;
$ \alpha $ = 0.85为跳转因子,主要用于表示Web用户有多大概率通过其他网页的出链来访问当前页面,1−$ \alpha $ 表示用户通过键入URL等方式来直接访问该网页的概率。通过式(6)可给网页赋予一个重要性的量化值。本文将从主题相关度较低的网页中选取重要性值PR≥2的网页作为具有潜在价值的网页,这些网页将有机会在爬行过程中被选中,从而辅助爬虫跳出局部最优,以搜寻更多主题相关的页面。 -
实验环境:处理器Intel(R)为Core(TM)i7-7700 HQ,CPU为2.80 GHz,RAM为8 GB;开发工具为MyEclipse+JDK1.7+Java语言;分词工具为IK-Analyzer;HTML解析器为Jsoup。
爬行主题:暴雨灾害和台风灾害。
实验数据:暴雨灾害的主题词组为暴雨、气象、天气、灾害和预防,权重依次设为0.8、0.1、0.1、0.5和0.3;台风灾害的主题词组为台风、风暴潮、暴雨、气压和风力,权重依次设为0.8、0.5、0.3、0.2和0.2;对暴雨灾害和台风灾害,使用百度进行主题词搜索,对得到的搜索结果结合人工经验分别筛选18个和30个URL作为初始种子链接。
实验参数:令调节因子∂=0.3;对暴雨灾害,设置主题相关度阈值β=0.62,对台风灾害,设置主题相关度阈值β=0.67;最大爬取网页数DP=15 000,其余参数均已在前文给出。
上述这些实验数据和实验参数的设置对爬虫算法的效果有一定影响,其值是参考文献[12, 14]以及通过多次对比实验使爬虫算法达到最好结果而确定的。
-
为评价爬虫方法的效果,通常使用爬准率(Accuracy)和爬全率(Recall)作为评价指标。因爬全率一般难以计算,本文选用爬准率作为评价主题爬虫效果的主要指标:
$$ {\text{Accuracy = LP/DP}} $$ (8) 式中,LP表示下载的主题相关网页数量;DP表示下载的总网页数。本文还使用平均主题相关度(average relevance, AR)和标准差 (standard deviation, SD)来测试爬虫的性能,包括所有下载网页的平均主题相关度(average relevance of all downloaded pages, ARDP)、所有下载网页主题相关度的标准差(standard deviation of topic relevance of all downloaded pages, SDDP)、所有下载主题相关网页的平均主题相关度(average relevance of all downloaded topic-relevant pages, ARLP)和所有下载主题相关网页主题相关度的标准差(standard deviation of topic relevance of all downloaded topic-relevant pages, SDLP):
$$ \text{A}{\text{R}}_{\text{DP}}=\frac{1}{\text{DP}} \sum _{l=1}^{\text{DP}}R\left({P}_{l}\right) $$ (9) $$ \text{S}{\text{D}}_{\text{DP}}=\sqrt{\frac{1}{\text{DP}} \sum _{l=1}^{\text{DP}}\left(R\right({P}_{l})-\text{A}{\text{R}}_{\text{DP}}{)}^{2}} $$ (10) $$ \text{A}{\text{R}}_{\text{LP}}=\frac{1}{\text{LP}} \sum _{l=1}^{\text{LP}}R\left({P}_{l}\right) $$ (11) $$ \text{S}{\text{D}}_{\text{LP}}=\sqrt{\frac{1}{\text{LP}} \sum _{l=1}^{\text{LP}}\left(R\right({P}_{l})-\text{A}{\text{R}}_{\text{LP}}{)}^{2}} $$ (12) 式中,R(Pl)表示网页Pl的主题相关度。
-
针对暴雨灾害主题,本文实现了基于WL抽样的主题爬虫算法,并与文献中的广度优先搜索(breadth first search, BFS)[25]、最佳优先搜索(best first search, OPS)[24]、多目标蚁群优化(multi-objective ant colony optimization, MOACO)[17]、记忆历史主机信息退火爬虫算法(focused crawler based on simulated annealing with host information, FCSA-host)[16]及结合本体的网页空间进化主题爬虫算法(focused crawler combining webpage space evolution and ontology, FCWSEO)[13]进行了对比,如表1所示。评价指标包括爬准率(Accuracy)、下载的主题相关网页数(LP)、所有下载网页的平均主题相关度(ARDP)及其标准差(SDDP)、所有下载相关网页的平均主题相关度(ARLP)及其标准差(SDLP),以及算法运行时间(Time)。由于文献中MOACO和FCWSEO两个算法没有测试ARLP和SDLP两个评价指标,故在表1中未给出相应的结果。
由表1可知,在爬虫初始阶段(DP=1 000),因采用区域竞争策略对种子链接附近中的高度相关区域进行了访问,故WL方法在Accuracy、LP和SDDP上均取得最优结果。OPS算法因每次均接受相关度最高的链接,所以具有最高的ARDP和ARLP,且在Accuracy和LP上的表现仅次于WL方法,而FCSA−host算法获得最优的SDLP。当DP=5 000时,FCSA−host方法在Accuracy、LP和SDLP这3个指标上取得最优结果,在ARDP上MOACO方法对OPS算法实现反超。此后,OPS获取相关页面的能力逐渐降低,并因贪心策略而陷入搜索局部最优。当DP=10 000时,WL方法在Accuracy和LP两个指标上再次反超FCSA−host,同时高于其余对比方法。此时,FCWSEO方法结合本体的优势逐渐显现,在ARDP指标上取得最优效果。随着爬行的深入,当DP=15 000时,WL方法在Accuracy、LP和SDDP这3项指标上均高于其他方法。这是因为,WL方法的随机抽样能力使其始终能稳定地穿越一些潜在价值较高的链接并获取更多的主题相关网页。FCWSEO算法通过最近最远候选解法选择一组Pareto最优链接来更新种子链接库中的链接,这使其在Accuracy和LP两项指标上超过了除WL外的所有方法,且在ARDP上表现最优。MOACO策略通过选择主题爬虫过程中的Pareto最优链接,从而使更多可能指向主题相关页面的链接被接受,这使得它在ARDP和SDDP指标上分别取得了仅次于FCWSEO和WL方法的结果。FCSA−host方法给予了次优链接优先访问的机会,且具有历史记忆能力,这使得它的6项指标值均取得了较好的结果,且在ARLP指标上取得最优结果。当DP=15 000时,本文WL方法的Accuracy值分别比BFS、OPS、FCSA-host、 MOACO和FCWSEO的结果高出335.09%、44.56%、17.72%、11.58%及6.1%。表1显示,本文所提方法在爬准率Accuracy、下载相关网页的数量LP和下载网页主题相关度的标准差SDDP这3个指标上效果最好。不过,在ARDP、ARLP和SDLP指标上,WL方法表现一般,这主要是因为WL方法采用修改的状态密度函数和直方图策略(即每访问一次链接就给予该链接状态密度函数一个惩罚,并将其能量区间直方图函数+1)引导爬虫访问态密度低的区域,有利于爬虫扩大搜索范围,抓取更多主题相关网页,但并不能确保每次都只接受主题相关度高的链接。另外,在运行时间方面,WL方法跟文献中的其他方法相比也具有明显优势或相当。
表 1 β=0.62时,暴雨灾害主题下各种主题爬虫算法在不同爬行阶段的实验结果比较
DP 算法 Accuracy LP ARDP SDDP ARLP SDLP Time/h 1000 BFS 0.3200 320 0.4977 0.2290 0.7551 0.0780 — OPS 0.8230 823 0.7143 0.1575 0.7722 0.0642 — FCSA-host 0.7010 701 0.6720 0.1509 0.7492 0.0478 — MOACO 0.6291 629 0.6957 0.2810 — — — FCWSEO 0.4542 454 0.7109 0.1643 — — — WL 0.8520 852 0.6613 0.0716 0.6827 0.0835 — 5000 BFS 0.2690 1345 0.4363 0.2378 0.7421 0.0572 — OPS 0.7704 3852 0.6802 0.1610 0.7494 0.0586 — FCSA-host 0.8030 4015 0.6953 0.1199 0.7422 0.0452 — MOACO 0.7042 3521 0.7801 0.1865 — — — FCWSEO 0.6572 3286 0.7590 0.1767 — — — WL 0.7796 3898 0.6779 0.0929 0.6791 0.0802 — 10000 BFS 0.1345 1345 0.2966 0.2226 0.7421 0.0572 — OPS 0.6533 6533 0.6269 0.2175 0.7589 0.0622 — FCSA-host 0.7628 7628 0.7004 0.1371 0.7640 0.0595 — MOACO 0.7872 7872 0.7756 0.1537 — — — FCWSEO 0.8070 8070 0.7904 0.1612 — — — WL 0.8504 8504 0.6749 0.0821 0.6862 0.0774 — 15000 BFS 0.2029 3043 0.3705 0.2438 0.7471 0.0637 8.6 OPS 0.6107 9160 0.6169 0.2339 0.7650 0.0633 9.0 FCSA-host 0.7499 11248 0.7003 0.1471 0.7712 0.0665 11.8 MOACO 0.7912 11868 0.7780 0.1377 — — 15.8 FCWSEO 0.8322 12483 0.8201 0.1558 — — 12.2 WL 0.8828 13242 0.6917 0.0784 0.7122 0.0820 8.1 为综合考察6种算法在暴雨灾害主题下的实验效果,表2给出了6种算法在DP=15 000时对4个典型指标Accuracy、LP、ARDP和SDDP应用Friedman测试[13]的结果,用Ranks值表示。其中,Ranks值为1表示对应方法为该指标的最佳结果,6为最差结果。从表2可看出,WL方法除ARDP指标排在第4位外,在Accuracy、LP和SDDP指标上均排在第1位。综合来看,WL方法具有最小的平均Ranks值(Average=1.75),是所有对比方法中性能最好的方法。BFS在各阶段的Ranks值始终最高,故其性能最差。
表 2 β=0.62时,暴雨灾害主题下各种主题爬虫算法的Friedman ranks比较
算法 Accuracy LP ARDP SDDP Average BFS 6 6 6 6 6 OPS 5 5 5 5 5 FCSA−host 4 4 3 3 3.5 MOACO 3 3 2 2 2.5 FCWSEO 2 2 1 4 2.25 WL 1 1 4 1 1.75 为进一步测试WL方法的性能,在暴雨灾害主题下,设置网页主题相关度阈值β=0.70,最大爬取网页数DP=15 000,运行本文提出的基于WL抽样的主题爬虫算法,并给出各项评价指标Accuracy、LP、ARDP、SDDP、ARLP、SDLP以及运行时间(Time)的结果,与文献中的网页空间进化算法(WSE)[12]、融合本体和改进禁忌搜索策略的主题爬虫方法(On-ITS)[26]、基于全局与局部本体和模拟退火策略的主题爬虫算法(FCOSA_LG)[27]、结合本体学习和多目标蚁群优化方法(OLMOACO)的主题爬虫方法[14]以及融合本体的网页空间进化主题爬虫算法(FCWSEO)[13]的结果对比如表3所示。由于文献中WSE、On-ITS、OLMOACO和FCWSEO这4种算法没有测试ARLP和SDLP这两个评价指标,故在表3中未给出相应的结果。在6种基于智能优化算法的先进主题爬虫方法中,WL方法在Accuracy、LP和SDDP这3个度量指标上均获得最优结果;而FCWSEO在ARDP指标上,FCOSA_LG在ARLP和SDLP两个指标上得到最好结果。在运行时间上,本文WL方法比文献中的算法运行时间明减少或相当,这主要是因为WL方法采用修改的状态密度函数和直方图函数策略更有利于算法爬取主题相关网页,同时WL方法不需要通过本体构造得到主题向量。
表 3 β=0.70时,暴雨灾害主题下各种先进主题爬虫方法的实验结果比较
算法 Accuracy LP ARDP SDDP ARLP SDLP Time/h WSE(2019) 0.7334 11002 0.7290 0.1600 — — 12.2 On-ITS(2020) 0.7340 11010 0.7295 0.1619 — — 13.2 FCOSA_LG(2022) 0.7653 11479 0.7511 0.1462 0.8095 0.0581 13.1 OLMOACO(2022) 0.7417 11126 0.7781 0.1375 — — 16.0 FCWSEO(2022) 0.8108 12162 0.8219 0.1566 — — 11.6 WL(本文) 0.8489 12734 0.6822 0.0897 0.7002 0.0891 8.4 为综合考察各种算法效果,表4给出了6种先进爬虫方法在DP=15 000时对4个典型指标Accuracy、LP、ARDP和SDDP应用Friedman测试[13]的结果。表4显示,WL和FCWSEO在所有对比方法中性能最好,FCOSA_LG和OLMOACO两个算法并列排在第三,WSE算法排在最后。
表 4 当β=0.70,时暴雨灾害主题下各种主题爬虫方法的Friedman ranks比较
算法 Accuracy LP ARDP SDDP Average WSE 6 6 5 5 5.5 On-ITS 5 5 4 6 5.0 FCOSA_LG 3 3 3 3 3.0 OLMOACO 4 4 2 2 3.0 FCWSEO 2 2 1 4 2.25 WL 1 1 6 1 2.25 针对台风灾害主题,设置网页主题相关度阈值β=0.67,本文实现了基于WL抽样的主题爬虫算法,并与文献中的BFS[25]、OPS[24]、模拟退火算法(simulated annealing, SA)[28]、网页空间进化算法(WSE)[12]、结合本体和改进禁忌搜索策略的主题爬虫方法(On-ITS)[26]以及结合本体学习和多目标蚁群优化方法(OLMOACO) [14]进行了结果对比,评价指标包括Accuracy、LP、ARDP、SDDP、ARLP、SDLP和Time,如表5所示。由于文献中其他算法没有测试ARLP和SDLP两个评价指标,故在表中未给出相应的结果。本文给出这两个指标的结果供将来其他算法进行比较。
由表5可知,当DP=1 000和5 000时,WL方法在Accuracy、LP和SDDP上均取得最优结果,在ARDP上其结果略低于On-ITS。由于BFS不对链接进行相关性判断,所以其爬准率始终都很低;而OPS因仅接受相关度最高的链接,易使爬虫陷入局部最优,爬准率逐渐降低;SA根据一定的概率选择主题不相关的网页,从而避免了陷入局部最优,在Accuracy、LP、ARDP、SDDP这4个评价指标上,其结果均优于BFS和OPS方法,但由于该算法主题描述不够准确,其结果劣于其他几种算法。当DP=10 000时,WL方法在Accuracy、LP上取得最优结果,在ARDP上略低于On-ITS方法,在SDDP上低于OLMOACO和On-ITS两种方法。当DP=15 000时,WL方法在Accuracy、LP上的优势继续保持,最终爬准率稳定在87%左右,而BFS、OPS、SA、WSE、On-ITS和OLMOACO方法的爬准率分别为4.7%、8.3%、35.8%、70.4%、82.0%和75.0%。在ARDP指标上,On-ITS的优势保持,而在SDDP指标上,OLMOACO的优势也继续保持。在运行时间上,当下载15 000个网页时,本文WL方法比BFS、OPS、SA、WSE、On-ITS和OLMOACO算法的运行时间明显减少或相当。为综合考察各种算法在台风灾害主题的爬虫效果,表6给出了7种方法在DP=15 000时应用Friedman测试[13]4个典型指标的结果。表6显示,WL方法在Accuracy、LP指标上均排在第一位,在ARDP和SDDP指标上均排在第二位。综合来看,WL方法具有最小的平均Ranks值(Average=1.5),是所有对比方法中性能最好的方法,其余6种算法按平均Ranks值从高到低排序依次是On-ITS、OLMOACO、WSE、SA、OPS和BFS。
表 5 台风灾害主题下各种主题爬虫算法在不同爬行阶段实验结果比较
DP 算法 Accuracy LP ARDP SDDP ARLP SDLP Time/h 1000 BFS 0.092 92 0.231 0.221 — — — OPS 0.391 391 0.432 0.283 — — — SA 0.414 414 0.551 0.212 — — — WSE 0.571 571 0.672 0.123 — — — On-ITS 0.707 707 0.811 0.152 — — — OLMOACO 0.625 625 0.681 0.212 — — — WL 0.714 714 0.701 0.121 0.747 0.112 — 5000 BFS 0.071 355 0.249 0.222 — — — OPS 0.248 1240 0.442 0.241 — — — SA 0.492 2460 0.591 0.181 — — — WSE 0.606 3030 0.664 0.134 — — — On-ITS 0.807 4035 0.852 0.128 — — — OLMOACO 0.767 3835 0.701 0.126 — — — WL 0.868 4338 0.703 0.108 0.721 0.104 — 10000 BFS 0.045 448 0.212 0.174 — — — OPS 0.124 1240 0.431 0.172 — — — SA 0.422 4215 0.552 0.169 — — — WSE 0.707 7069 0.687 0.124 — — — On-ITS 0.812 8120 0.781 0.112 — — — OLMOACO 0.737 7370 0.700 0.088 — — — WL 0.893 8927 0.701 0.121 0.723 0.098 — 15000 BFS 0.047 705 0.211 0.184 — — 8.5 OPS 0.083 1244 0.436 0.144 — — 9.1 SA 0.358 5370 0.533 0.160 — — 11.1 WSE 0.704 10560 0.684 0.127 — — 12.2 On-ITS 0.820 12300 0.792 0.123 — — 13.2 OLMOACO 0.750 11250 0.700 0.075 — — 15.0 WL 0.873 13095 0.702 0.099 0.712 0.095 8.2 表 6 台风灾害主题下7种主题爬虫算法的Friedman ranks比较
算法 Accuracy LP ARDP SDDP Average BFS 7 7 7 7 7 OPS 6 6 6 5 5.75 SA 5 5 5 6 5.25 WSE 4 4 4 4 4.0 On-ITS 2 2 1 3 2.0 OLMOACO 3 3 3 1 2.5 WL 1 1 2 2 1.5
Focused Crawler Method Based on Wang−Landau Sampling
-
摘要: 针对传统爬虫方法存在搜索易陷入局部最优,且很少考虑结合历史爬行经验对爬行路径进行修正的缺陷,提出一种基于WL抽样的主题爬行方法。该方法分别使用向量空间模型(VSM)和PageRank算法对链接的相关性和重要性进行评价,采用区域竞争策略从具有主题相关或潜在价值的链接集合中选出目标链接。基于概率密度函数,WL抽样算法对侯选集中选出的目标链接进行抽样判断,根据历史统计经验指导爬虫的后续爬行,从而优化搜索路径。实验结果表明,提出的基于WL抽样的主题爬虫方法比其他主题爬虫方法能搜索到更多主题相关的网页,其爬准率和所有下载网页主题相关度的标准差具有明显优势。
-
关键词:
- 网络爬虫 /
- 信息检索 /
- 暴雨灾害 /
- 台风灾害 /
- Wang-Landau抽样
Abstract: Aiming at the problem that the traditional crawler methods are easy to fall into local optima of the search and rarely consider modifying the crawling path based on historical crawling experience, a focused crawler method based on Wang−Landau (WL) sampling is proposed. This method uses the vector space model (VSM) and PageRank algorithm to evaluate the relevance and importance of links, respectively. Regional competition strategy is used to select the target link from the link set containing the topic−related links and links with potential value. Based on probability density function, the WL algorithm is used to sample the selected target links in the set, and guides the subsequent crawling of the crawler according to the historical statistical experience, so as to optimize the search path. The experimental results show that the WL-based focused crawling method can search more topic-relevant webpages than other methods in the literature, and the climbing accuracy and standard deviation of topic relevance of all downloaded pages are also significantly improved.-
Key words:
- focused crawler /
- information retrieval /
- rainstorm disaster /
- typhoon disaster /
- Wang-Landau sampling
-
表 1 β=0.62时,暴雨灾害主题下各种主题爬虫算法在不同爬行阶段的实验结果比较
DP 算法 Accuracy LP ARDP SDDP ARLP SDLP Time/h 1000 BFS 0.3200 320 0.4977 0.2290 0.7551 0.0780 — OPS 0.8230 823 0.7143 0.1575 0.7722 0.0642 — FCSA-host 0.7010 701 0.6720 0.1509 0.7492 0.0478 — MOACO 0.6291 629 0.6957 0.2810 — — — FCWSEO 0.4542 454 0.7109 0.1643 — — — WL 0.8520 852 0.6613 0.0716 0.6827 0.0835 — 5000 BFS 0.2690 1345 0.4363 0.2378 0.7421 0.0572 — OPS 0.7704 3852 0.6802 0.1610 0.7494 0.0586 — FCSA-host 0.8030 4015 0.6953 0.1199 0.7422 0.0452 — MOACO 0.7042 3521 0.7801 0.1865 — — — FCWSEO 0.6572 3286 0.7590 0.1767 — — — WL 0.7796 3898 0.6779 0.0929 0.6791 0.0802 — 10000 BFS 0.1345 1345 0.2966 0.2226 0.7421 0.0572 — OPS 0.6533 6533 0.6269 0.2175 0.7589 0.0622 — FCSA-host 0.7628 7628 0.7004 0.1371 0.7640 0.0595 — MOACO 0.7872 7872 0.7756 0.1537 — — — FCWSEO 0.8070 8070 0.7904 0.1612 — — — WL 0.8504 8504 0.6749 0.0821 0.6862 0.0774 — 15000 BFS 0.2029 3043 0.3705 0.2438 0.7471 0.0637 8.6 OPS 0.6107 9160 0.6169 0.2339 0.7650 0.0633 9.0 FCSA-host 0.7499 11248 0.7003 0.1471 0.7712 0.0665 11.8 MOACO 0.7912 11868 0.7780 0.1377 — — 15.8 FCWSEO 0.8322 12483 0.8201 0.1558 — — 12.2 WL 0.8828 13242 0.6917 0.0784 0.7122 0.0820 8.1 表 2 β=0.62时,暴雨灾害主题下各种主题爬虫算法的Friedman ranks比较
算法 Accuracy LP ARDP SDDP Average BFS 6 6 6 6 6 OPS 5 5 5 5 5 FCSA−host 4 4 3 3 3.5 MOACO 3 3 2 2 2.5 FCWSEO 2 2 1 4 2.25 WL 1 1 4 1 1.75 表 3 β=0.70时,暴雨灾害主题下各种先进主题爬虫方法的实验结果比较
算法 Accuracy LP ARDP SDDP ARLP SDLP Time/h WSE(2019) 0.7334 11002 0.7290 0.1600 — — 12.2 On-ITS(2020) 0.7340 11010 0.7295 0.1619 — — 13.2 FCOSA_LG(2022) 0.7653 11479 0.7511 0.1462 0.8095 0.0581 13.1 OLMOACO(2022) 0.7417 11126 0.7781 0.1375 — — 16.0 FCWSEO(2022) 0.8108 12162 0.8219 0.1566 — — 11.6 WL(本文) 0.8489 12734 0.6822 0.0897 0.7002 0.0891 8.4 表 4 当β=0.70,时暴雨灾害主题下各种主题爬虫方法的Friedman ranks比较
算法 Accuracy LP ARDP SDDP Average WSE 6 6 5 5 5.5 On-ITS 5 5 4 6 5.0 FCOSA_LG 3 3 3 3 3.0 OLMOACO 4 4 2 2 3.0 FCWSEO 2 2 1 4 2.25 WL 1 1 6 1 2.25 表 5 台风灾害主题下各种主题爬虫算法在不同爬行阶段实验结果比较
DP 算法 Accuracy LP ARDP SDDP ARLP SDLP Time/h 1000 BFS 0.092 92 0.231 0.221 — — — OPS 0.391 391 0.432 0.283 — — — SA 0.414 414 0.551 0.212 — — — WSE 0.571 571 0.672 0.123 — — — On-ITS 0.707 707 0.811 0.152 — — — OLMOACO 0.625 625 0.681 0.212 — — — WL 0.714 714 0.701 0.121 0.747 0.112 — 5000 BFS 0.071 355 0.249 0.222 — — — OPS 0.248 1240 0.442 0.241 — — — SA 0.492 2460 0.591 0.181 — — — WSE 0.606 3030 0.664 0.134 — — — On-ITS 0.807 4035 0.852 0.128 — — — OLMOACO 0.767 3835 0.701 0.126 — — — WL 0.868 4338 0.703 0.108 0.721 0.104 — 10000 BFS 0.045 448 0.212 0.174 — — — OPS 0.124 1240 0.431 0.172 — — — SA 0.422 4215 0.552 0.169 — — — WSE 0.707 7069 0.687 0.124 — — — On-ITS 0.812 8120 0.781 0.112 — — — OLMOACO 0.737 7370 0.700 0.088 — — — WL 0.893 8927 0.701 0.121 0.723 0.098 — 15000 BFS 0.047 705 0.211 0.184 — — 8.5 OPS 0.083 1244 0.436 0.144 — — 9.1 SA 0.358 5370 0.533 0.160 — — 11.1 WSE 0.704 10560 0.684 0.127 — — 12.2 On-ITS 0.820 12300 0.792 0.123 — — 13.2 OLMOACO 0.750 11250 0.700 0.075 — — 15.0 WL 0.873 13095 0.702 0.099 0.712 0.095 8.2 表 6 台风灾害主题下7种主题爬虫算法的Friedman ranks比较
算法 Accuracy LP ARDP SDDP Average BFS 7 7 7 7 7 OPS 6 6 6 5 5.75 SA 5 5 5 6 5.25 WSE 4 4 4 4 4.0 On-ITS 2 2 1 3 2.0 OLMOACO 3 3 3 1 2.5 WL 1 1 2 2 1.5 -
[1] 中国互联网络信息中心. 中国互联网络发展状况统计报告[EB/OL]. [2022-01-21]. http://www.cnnic.net.cn/NMediaFile/old_attach/P020220721404263787858.pdf. China Internet Network Information Center. Statistical report on the development of Internet in China[EB/OL]. [2022-01-21]. http://www.cnnic.net.cn/NMediaFile/old_attach/P020220721404263787858.pdf. [2] RAWAT A, BANSAL M. Review paper on focused crawler for categorization[J]. International Journal of Computer Trends & Technology, 2014, 12(3): 141-143. [3] DE BRA P M E, POST R D J. Searching for arbitrary information in the WWW: The fish−search for mosaic[C]// World Wide Web Conference. Geneva: [s.n.], 1994: 1-11. [4] 程元堃, 廖闻剑, 程光. 词向量聚类加权shark−search的主题爬虫策略研究[J]. 计算机与数字工程, 2018, 46(1): 144-148. doi: 10.3969/j.issn.1672-9722.2018.01.031 CHENG Y K, LIAO W J, CHENG G. Research on the theme crawler strategy of shark-search weighted by word vector clustering[J]. Computer and Digital Engineering, 2018, 46(1): 144-148. doi: 10.3969/j.issn.1672-9722.2018.01.031 [5] BRIN S, PAGE L. The anatomy of a large-scale hypertextual web search engine[J]. Computer Networks and ISDN Systems, 1998, 30(1-7): 107-117. doi: 10.1016/S0169-7552(98)00110-X [6] GAO Q, ZHANG Y P. Study on theme-drift of hyperlink-induced topic search algorithm[J]. Journal of Computer Applications, 2009, 29(11): 3100-3102. doi: 10.3724/SP.J.1087.2009.03100 [7] 周雪, 刘乃文. 引入主题链接块因子的候选链接搜索策略研究[J]. 计算机与数字工程, 2018, 46(5): 874-878. doi: 10.3969/j.issn.1672-9722.2018.05.006 ZHOU X, LIU N W. Research on candidate link search strategy with Topic link block factor[J]. Computer and Digital Engineering, 2018, 46(5): 874-878. doi: 10.3969/j.issn.1672-9722.2018.05.006 [8] SUEBCHUA T, MANASKASEMSAK B, RUNGSAWANG A, et al. Efficient topical focused crawling through neighborhood feature[J]. New Generation Computing, 2018, 36(2): 95-118. doi: 10.1007/s00354-017-0029-8 [9] 库珊, 刘钊. 基于PageRank与HITS的改进算法的网页排名优化[J]. 武汉科技大学学报, 2019, 42(2): 155-160. KU S, LIU Z. Webpage ranking optimization based on the improved algorithm of PageRank and HITS[J]. Journal of Wuhan University of Science and Technology, 2019, 42(2): 155-160. [10] 姜琨, 朱磊, 王一川. 基于动态隧道技术的主题爬行策略[J]. 计算机系统应用, 2020, 29(3): 253-260. JIANG K, ZHU L, WANG Y C. Topic crawling strategy based on dynamic tunneling technology[J]. Computer System Applications, 2020, 29(3): 253-260. [11] HOSSEINKHANI J, TAHERDOOST H, KEIKHAEE S. Anton framework based on semantic focused crawler to support web crime mining using SVM[J]. Annals of Data Science, 2021, 8(2): 227-240. doi: 10.1007/s40745-019-00208-5 [12] 刘景发, 李新, 蒋盛益. 基于网页空间进化算法的暴雨灾害主题爬虫策略[J]. 计算机工程, 2019, 45(2): 184-190. doi: 10.19678/j.issn.1000-3428.0052035 LIU J F, LI X, JIANG S Y. Crawler strategy for rainstorm disaster theme based on webpage space evolution algorithm[J]. Computer Engineering, 2019, 45(2): 184-190. doi: 10.19678/j.issn.1000-3428.0052035 [13] LIU J F, LI X, ZHANG Q S, et al. A novel focused crawler combining Web space evolution and domain ontology[J]. Knowledge-Based Systems, 2022, 243: 108495. doi: 10.1016/j.knosys.2022.108495 [14] LIU J F, DONG Y, LIU Z X, et al. Applying ontology learning and multi-objective ant colony optimization method for focused crawling to meteorological disasters domain knowledge[J]. Expert Systems with Applications, 2022, 198: 116741. doi: 10.1016/j.eswa.2022.116741 [15] 荆文鹏, 王育坚, 董伟伟. 自适应遗传算法在主题爬虫搜索策略中的应用研究[J]. 计算机科学, 2016, 43(8): 254-257. doi: 10.11896/j.issn.1002-137X.2016.08.051 JING W P, WANG Y J, DONG W W. Application research of adaptive genetic algorithm in topic crawler search strategy[J]. Computer Science, 2016, 43(8): 254-257. doi: 10.11896/j.issn.1002-137X.2016.08.051 [16] 刘景发, 李帆, 蒋盛益. 基于综合优先度和主机信息的暴雨灾害主题退火爬虫算法[J]. 计算机科学, 2019, 46(2): 215-222. doi: 10.11896/j.issn.1002-137X.2019.02.033 LIU J F, LI F, JIANG S Y. Annealing crawler algorithm for rainstorm disaster theme based on comprehensive priority and host information[J]. Computer Science, 2019, 46(2): 215-222. doi: 10.11896/j.issn.1002-137X.2019.02.033 [17] 东熠, 刘景发, 刘文杰. 基于多目标蚁群算法的主题爬虫策略[J]. 计算机工程, 2020, 46(9): 274-282. doi: 10.19678/j.issn.1000-3428.0055967 DONG Y, LIU J F, LIU W J. Focused crawler strategy based on multi−objective ant colony algorithm[J]. Computer Engineering, 2020, 46(9): 274-282. doi: 10.19678/j.issn.1000-3428.0055967 [18] DU Y J, LIU W J, LV X J, et al. An improved focused crawler based on semantic similarity vector space model[J]. Applied Soft Computing, 2015, 36: 392-407. doi: 10.1016/j.asoc.2015.07.026 [19] CHEN K W, ZHANG Z P, LONG J, et al. Turning from TF-IDF to TF-IGM for term weighting in text classification[J]. Expert Systems with Applications, 2016, 66: 245-260. doi: 10.1016/j.eswa.2016.09.009 [20] WANG F, LANDAU D P. Efficient, multiple-range random walk algorithm to calculate the density of states[J]. Physical Review Letters, 2001, 86(10): 2050. doi: 10.1103/PhysRevLett.86.2050 [21] WANG B W, ZHAO P. An adaptive image watermarking method combining SVD and Wang-Landau sampling in DWT domain[J]. Mathematics, 2020, 8(5): 1-20. [22] 曹红英, 田华, 侯杰, 等. 使用王朗道蒙特卡罗算法和机器学习研究伊辛模型相变[J]. 山西大学学报(自然科学版), 2022, 12: 1-9. CAO H Y, TIAN H, HOU J, et al. Studying the phase transitions for Ising model through Wang-Landau monte carlo algorithm and machine learning[J]. Journal of Shanxi University (Natural Science Edition), 2022, 12: 1-9. [23] LIPOWSKI A, LIPOWSKA D. Roulette-Wheel selection via stochastic acceptance[J]. Physica A: Statistical Mechanics and its Applications, 2012, 391(6): 2193-2196. doi: 10.1016/j.physa.2011.12.004 [24] RAWAT S, PATIL D R. Efficient focused crawling based on best−first search[C]//2013 3rd IEEE International Advance Computing Conference (IACC). [S.l.]: IEEE, 2013: 908-911. [25] 王桦. 基于广度优先的主题爬虫的设计与实现[D]. 上海: 复旦大学, 2011. WANG H. Design and implementation of theme crawler based on breadth first[D]. Shanghai: Fudan University, 2011. [26] 刘景发, 顾瑶平, 刘文杰. 融合本体和改进禁忌搜索策略的气象灾害主题爬虫方[J]. 计算机应用, 2020, 40(8): 2255-2261. LIU J F, GU Y P, LIU W J. Focused crawler method combining ontology and improved tabu search for meteorological disaster[J]. Journal of Computer Applications, 2020, 40(8): 2255-2261. [27] LIU J F, LI F, DING R Y, et al. Focused crawling strategies based on ontologies and simulated annealing algorithm for rainstorm disaster domain knowledge[J]. Frontiers of Information Technology & Electronic Engineering, 2022, 23(8): 1189-1205. [28] 贺晟, 程家兴, 蔡欣宝. 基于模拟退火算法的主题爬虫[J]. 计算机技术与发展, 2009, 19(12): 55-58. doi: 10.3969/j.issn.1673-629X.2009.12.015 HE S, CHENG J X, CAI X B. Focused crawler based on simulated anneal algorithm[J]. Computer Technology and Development, 2009, 19(12): 55-58. doi: 10.3969/j.issn.1673-629X.2009.12.015