基于时效性的爬虫调度

摘 要：搜索引擎作为互联网信息获取的入口，实现高效、准确的信息获取非常重要，爬虫作为搜索引擎的上游，其重要性不言而喻，特别是大数据时代信息更新频繁，如何在第一时间获取新闻是实现爬虫时效性的重要因素。为了充分利用有限资源，提升带宽利用率，设计一种基于历史数据预测的爬虫调度算法。该算法通过抓取网站历史，更新频次积累数据，使用随机森林回归建立模型，并在系统中实现爬虫调度。实验结果表明，该策略在抓取新链的命中率上提升了46%，平均成本降低了11%，平均抓取延时降低了14%。

关键词：搜索引擎;爬虫调度;回归预测;随机森林

DOI：10. 11907/rjdk.191420

开放科学（资源服务）标识码（OSID）：

中图分类号：TP301

文献标识码：A

文章编号：1672-7800（2020）001-0108-05

0 引言

在过去20年里，网络数据规模增长非常迅速，现已全面进入大数据时代，从基础行业到尖端行业，大数据无处不在[1]。搜索引擎作为互联网的一大入口，其重要性尤为凸显，搜索引擎需要从外部网络获取数据进行加工处理，通常由网络爬虫作为其上游抓取全网数据[2-4]。互联网上每天都有大量新网页产生，如何高效、准确地抓取到最新数据成为一项挑战。如果爬虫不能及时抓到突发事件或者相关内容抓取不全，则搜索引擎无法建库和收录，导致用户无法及时搜索到目标内容，则该技术将面临淘汰。

搜索引擎的4个评价指标为“快、准、新、全”[5-6]。“快”指搜索速度快，用户等待时间越短越好;“准”指搜索相关性高，返回的结果大部分应是用户需要的;“新”指时效性，返回的结果需尽快收录最新文章;“全”指网页覆盖率，应当尽可能多地覆盖全網数据。爬虫第一时间抓取到页面才能让搜索引擎第一时间索引并展示相应内容，因此本文主要针对时效性进行研究。

1 通用爬虫技术

爬虫指按照一定规则，自动抓取互联网信息的程序[7]。爬虫通常分为通用爬虫和垂直爬虫，通用型爬虫设置好抓取的范围和目标，达到目标就停止爬取，一般信息较多，覆盖点比较全但需要清除一些垃圾站点;垂直型爬虫只关注与特定主题相关的内容或者属于特定行业的数据，这样减少了不必要的资源浪费，而且还缩短了网页抓取时间[8]。两者根据使用场景的不同各有优缺点，架构区别主要表现在选择链接上。爬虫从预先设置好的种子页面开始抓取，之后抽取链接扩展链接库，然后根据广度或者深度优先深入抓取，尽可能多地覆盖网页[9-10]。

1.1 基本爬虫框架

通常爬虫架构主要模块为调度模块、抓取模块、下载模块、页面分析模块、链接选择模块、存储模块，所有模块组合起来形成一个闭环，流程架构如图1所示。

调度模块（ Scheduler）从链接选择模块（Selector）接受链接并将它们分散到一天均匀抓取，交给抓取模块（ Fetch-er）处理抓取参数和控制抓取策略，下载模块（Downloader）获取链接后从互联网下载网页回传给分发模块进行处理，然后交给页面分析模块（ Extractor）抽取相关信息，如页面摘要、时间因子、垃圾信息、链接信息等，再根据策略写入网页库（Pages），新链接去重后写入链接库（Linkbase），链接选择模块根据链接深度决定是否选择相关链接，至此整个流程形成一个持续抓取的闭环[11-13]。

1.2 时效性

爬虫主要从抓取种子页面获取新网页，新闻列表页是最典型的种子页面，搜索引擎时效性主要体现在新闻类网页上，第一时间抓取到最新的新闻是搜索引擎最重要的功能，所以对一些更新频繁的页面，爬虫也会频繁抓取，但高频次的抓取会让对方网站承受比较大的压力，导致对方封禁爬虫，而且这种做法对自身带宽要求比较高，网页并不是随时会更新，若大量访问却提取不出新链接，则浪费带宽资源。因此提出时效性问题，对抓取频次进行精细化控制，需在压力和时间上作出平衡决策[14-16]。

网页内容大部分都是人为编辑发布的信息，因此规律和不确定性同时存在。白天信息更新比较频繁，夜间更新较少;一个栏目的编辑者可能是不同的人，发文时间每天可能不同;突发事件会导致信息更新频繁，节假日会导致信息更新较少。频次控制最先实现的是使每个种子页面用固定的间隔进行抓取，这样爬虫能开始初步工作，但是上述问题不能得到解决，这就需要动态地进行频次控制，对于网页更新的变化规律，相关学者经过研究发现，泊松过程是描述这种变化规律的最佳模式[17-18]。

泊松过程（ Poisson Process）是一种在实践中常被使用的计数随机过程，描述特定现象发生次数随时间变化的规律。如果计算在某一段时间内出现的随机点数目，该数目也是随机的，且随着这段时间延伸的不断变化，该变化过程为伴随着随机点过程的计数过程[19]。

泊松过程有3个特点：时间（或空间）上的均匀性、未来变化与过去变化没有关系（即独立增量性）、普遍性。

称去非负整数的随机过程[t，t+r]为强度（或速率）为入的泊松过程，如果满足：①N（0）=0;②N（t）为平稳独立增量过程;③对任意的0≤s

在区间[t，t+r]内发生时间的数目概率分布为：

在式（1）中，参数A是一个正数和固定参数，称作抵达率（或强度）。所以给定在区间[t，t+r]内发生时间的数目，则随机变数N（T+）-N（T）呈现泊松过程，参数为λτ。

2 基于时效性的调度算法

本部分主要介绍基于时效性的调度算法，通过挖掘网页历史数据建模，并提出算法评价方法。

2.1 时效性调度算法

互联网信息更新很频繁，对于网页更新的变化规律，可以通过历史数据挖掘得来。该算法流程如图2所示。

整个算法分为4个部分：①历史数据积累;②抽取发布时间;③对历史数据建模;④应用调度模块。详细过程如下：

（1）历史数据积累。首先爬虫系统正常运行一段时间，网页调度算法按默认的间隔抓取，记录下调度时间和首次抓取时间，保存到网页库。

（2）抽取网页发布时间。爬虫系统在运行一定时间后，会累积下大量网页数据，其中正文页面通常会有文章发布时间，即使没有，也能通过算法计算出大概文章时间。设正文页面的父页面上次调度时间为Tlast，本次调度时间为T now，页面发布时间T page，可以得出结论Tlast

（3）历史数据建模。网页包含发布时间后，即可把同一个种子页面扩散出去的页面聚类在一起，根据每个聚类的组，通过随机森林回归进行建模，得到种子页面时效性模型。其中未能抽取出发布时间的页面和数量过小，不进行模型构建。

（4）应用调度模块。时效性模型建立好后，在调度时先查询是否包含有模型，若有則根据模型计算出调度频率，按照频率抓取种子页面。

2.2 随机森林回归

随机森林（ Random Forest，RF）是一种基于集成学习（ Ensemble Learning）的算法，属于Bagging类型，通过组合多个弱分类器，并经过投票或者取平均值，使最终模型结果有比较好的精度，并具有良好的泛化性能。随机森林采用的弱分类器是分类与回归树（ Classification and Regres-sionrree，CART），既可以用于分类，也可以用于回归，本文采用随机森林回归算法[20]，算法描述如下：

（1）为每颗决策树产生训练集，使用Bagging抽样方法生产让训练数据有一定的差异性。一般使用无权重抽样算法，每次抽取过程随机，之后把结果放还至原样本里，则抽出来的子集会有重复，能解决局部最优解的问题。

（2）设训练样本有N个特征，从样本中随机选取其中M个特征，从单颗决策树开始，从M个特征中最优的特征进行分裂，直到所有训练样本在该节点上均为同一类为止。

（3）重复以上两个步骤，建立K棵决策树，此时将待预测的样本输入决策树，把所有预测结果进行加权后作为最终结果。因为这些决策树之间并没有耦合关系，通常采取并行方式进行处理，所以随机森林算法速度大幅提高。

2.3 历史数据建模

爬虫系统在运行一定时间后，会累积大量网页数据，其中正文页面通常会有文章发布时间，即使没有，也能通过算法计算出大概文章时间。设正文页面的父页面上次调度时间为Tlast，本次调度时间为T now，页面发布时间T page，可以得出结论Tlast< Tpage≤T now。如果Tlast不存在，说明页面的父页面是首次调度，不能确认该页面出现时间。如果T now一T last<1h，则可以把文章发布时间约等于两次调度的中间值。

本文根据新增数据量每一小时计算一次，每个页面一天有24个时段的数据，共统计了30天的数据，得到720项数据，每项都为时段内的新增页面数，抽取部分数据，算法步骤如下：

Input：网页库Pages的源数据，Output：网站标识与时间戳集合S

for page in Pages

//提取page的链接和发布时间

url，

publish_time←extract（ page）

//如果publish_time不存在或者超过30天就跳过

if publish_time not exist or publish_time+ 30days< now then

coniinue

end if

//分离出域名和路径

host，

path← splitHostAndPath（url）

//分离第一级path

patho ←splitFirstPath（ path）

//组合出主键

key←host+“一”+path0

//在S集合中S[key]中加入新的发布时间

appendTimeToData（S，key， publish_time）

end for

//遍历S集合

for key，value in S

//如果网站的新增数据小于阈值不进行后续分析

if size of value< 1000 then

if“一”in key then

//如果包含第一级path，尝试去掉重新加入S集合

host←splitHostFromKey（ key）

appendTimesToData（S，host， value）

end if

//从S集合中删除网站

deIKeyFromData（S，key）

continue

end if

//对S集合的发布时间集合进行排序

sort（ value）

end for

//产出网站标识一发布时间集合的数据集

return S

把上述数据绘制成时间一新增数据量图（见图4），可以观察到每天更新频率。

为了更清晰地观察到数据整体趋势，把时间数据的y轴累加，可以得到图5，对比上下两个图可以观察到很明显的新增趋势，并且有一定的周期性，每天白天为数据更新高发时段，并且在这些图中有4段更新平缓的区域，对应这30天的4周周末，于是把每天的小时数和每周的周数当作回归模型自变量。

每個种子页面均可生成如表1的数据，该数据为模型的训练数据。其中，hO-h23为每天的时段，w0-w6为每周的周数，均为自变量，value为新增数据量，是模型数据的因变量。

2.4 调度算法评价方法

本文采取多种验证方法进行评估，一是对预测结果进行随机交叉验证，其次是对顺序新数据的验证，最后是应用本文算法预测调度的对比分析。前两种验证使用R2Score进行判断，其公式如式（2）所示，可以衡量模型预测能力优劣。

第二种验证方法是选择数据尾部的数据再次计算R2的值，即可判断预测模型误差。

常规调度算法是间隔性抓取，不同需求选取不同的抓取间隔，本文把间隔分为10s、20s、30s、1 m、2m，5m、10m、30m、1h、2h几种情况计算，可按3个维度评判：①每次抓取记为一次成本，统计总成本;②抓取时间与网页真实出现的差值，最后算出方差;③准确度，单次抓取得到新链接标记为抓取准确，总结后可算出最后的准确度。

经过改进的算法仅关注成本，但命中率或延迟不是最优，因为在定间隔抓取中，高频次会导致成本高、命中率与延迟低。而低频次的抓取通常可以实现低成本、高命中率与高延迟。新算法的3项指标并不能看出明显优势，因此本文把3项指标量化后加权得到公式（4），其中设抓取成本为cost，命中次数为hit，总延迟为delay，加权结果为W。

3 实验结果及分析

实验使用Python开发的一套爬虫框架，主要在链接选择模块和调度模块进行时效性验证，其它模块仅保留基础功能。实验环境为单实例1CIC的Docker集群，出口带宽保证抓取在lOs内返回。

通过随机森林进行预测后，分别使用交叉验证和新数据验证，得到表2的结果。

R2-Score的准确度不太稳定，但是集中在0.6-0.9左右，交叉验证后可以看到趋势基本吻合，如图6所示。

把预测结果经过动态调度算法处理后应用于调度模块，经过几种固定间隔和动态调度算法的对比，得到表3所示数据，成本上中间数为2 160，动态调度算法为1 701，减少了11%的成本;命中率上中间数为43%，动态调度算法为63%，提升了46%;平均延迟中间数为41，动态调度算法为35，降低了14%的延迟。可以看到，这些指标均超过平均水平，并且加权后的结果优于其它方法。

4 结语

本文针对爬虫调度的时效性问题，提出一种根据历史数据指导新数据调度抓取的算法。与传统定间隔抓取相比，该算法在成本、命中率、平均延迟上均高于平均水平，很好地提高了实际抓取过程中的抓取效率，并且算法运行速度较快，由于采用比较基础的回归算法，所以针对实际抓取场景可在相对低成本下引入，使网络开销大幅降低。但是，该算法在应对突发性增长时还不够灵活，需进一步改进。

参考文献：

[1]程学旗，靳小龙，王元卓，等.大数据系统和分析技术综述[J].软件学报，2014，25（09）：1889-1908.

[2] 周德懋，李舟军.高性能网络爬虫：研究综述[J].计算机科学，2009，（8）：26-29+53.

[3] BRIN S，PACE L.The anatomy of a large-scale hypertextual wehsearch engine [Jl. Computer networks and ISDN systems， 1998. 30 （ 1-7）：107-117.

[4]ARASU A， CHO J，GARCIA-MOLINA H， et al. Searching the web[Jl. ACM Transactions on Internet Technology， 2001，1（1）：2-43.

[5]张兴华.搜索引擎技术及研究[J].现代情报，2004（4）：142-145.

[6] 马志杰.国外搜索引擎评价研究综述[J].图书馆学研究，2013（2）：2—6.

[7]KAUSAR M A， DHAKA V， SINGH S K.Web crawler：a review[J].International Journal of Computer Applications， 2013， 63（2）：3 1-36.

[8] 周立柱，林玲.聚焦爬虫技术研究综述[J].计算机应用，2005（9）：1965-1969.

[9]姜杉彪，黄凯林，卢昱江，等.基于Python的专业网络爬虫的设计与实现[J].企业科技与发展，2016（8）：17-19.

[10] 李应.基于Hadoop的分布式主题网络爬虫研究[J].软件导刊，2016. 15（3）：24-26.

[11] YU J，LI M，ZHANG D.A distributed web crawler model hased oncloud computing[C].Dalian： The 2nd Information Technology andMechatronics Engineering Conference， 2016.

[12]YE F，JINC Z， HUANC Q， et al. The research and implementationof a distributed crawler svstem based on Apache flink [C]. Interna-tional Conference on Algorithms and Architectures for Parallel Pro-cessing， 2018：90-98.

[13]YE F， JING Z， HUANC Q， et al. The research of a lightweight dis-tributed crawling system[C].2018 IEEE 16th International Confer-ence on Software Engineering Research， Management and Applica-tions（ SERA）， 2018： 200-204.

[14]孟涛，王继民，闫宏飞.网页变化与增量搜集技术[J].软件学报，2006（5）：1051-1067.

[15]LIU C，WANG W， ZHANG Y， et al. Predicting the popularity of on-line news based on multivariate analysis[C].2017 IEEE Internation-al Conference on Computer and Information Technology （CIT），2017：9-15.

[16]SHI Z， SHI M， LIN W. The implementation of crawling news pagebased on incremental web cra，vler[C].2016 4th International Confer-ence on Applied Computing and Information Technology/3rd Interna-tional Conference on Computational Science/lntelligence and Ap-plied Informatics/lst International Conference on Big Data， CloudComputing， Data Science & Engineering （ACIT-CSII-BCD） ，2016： 348-351.

[17]CHO J， CARCIA-MOLINA H. The evolution of the web and implica-tions for an incremental crawler[ R]. Stanford， 1999.

[18]徐尚瑜.基于泊松過程的爬虫调度策略分析[J].现代计算机：专业版，2009，（ 12）：68-71.

[19] FISCHER W，MEIER-HELLSTERN K.The Markov-modulated Poisson process （MMPP） cookbook [J]. Performance evaluation，1993，18（2）：149-171.

[20]BREIMAN L Random forests[ J]. Machine learning， 2001， 45（1）： 5-32.

（责任编辑：江艳）

作者简介：韩瑞昕（1994-），男，北京工业大学信息学部硕士研究生，研究方向为软件工程与理论。.