一种基于时间序列预测的重采策略

史存会，孟 剑，俞晓明，刘 悦，靳小龙，程学旗

(1. 中国科学院 计算技术研究所 中国科学院网络数据科学与技术重点实验室，北京 100190；2. 中国科学院大学，北京 100049)

0 引言

近年来，随着互联网的发展，从传统的新闻、论坛、博客到新兴的社交媒体、自媒体，如微信、微博等，互联网每天产生的信息量呈现爆炸式增长。及时地获取到这些新产生的内容，无论是对搜索引擎，舆情监测等应用都具有非常重要的意义。网络爬虫的一个重要目标，就是能够快速地获取这些新增的页面。通过研究发现，基于对链向新内容页面的研究，能够通过监控很少的一些预先选择好的页面，就能够发现90%新的内容[1]。针对新闻、论坛、博客、微信、微博等网站的分析，我们发现存在一类页面，专门用于链向新增内容，我们称之为版块页；另外一类页面主要展示信息内容，我们称之为内容页。图1(a)给出了版块页的样例，图1(b)给出了内容页的样例。基于这种版块页—内容页的组织形式，可以通过定期重访版块页的策略来检测是否有新增内容。如果存在新增内容，则获取内容链接，并进一步采集相应页面。这种策略对于针对特定新闻门户的不同频道，论坛的不同版面或博客、微博、微信公众号的不同用户新增信息的及时获取都非常有效。

图1 版块页、内容页样例图

随着互联网内容的重要性日益增强，网站也越来越注重对于网站内容的保护，要求网络爬虫对网站进行友好访问。对于恶意访问网站的行为，越来越多的网站会采取反爬取的保护策略。大量网站对IP或访问者在一定时间窗口内访问量进行统计，根据设定阈值进行访问限制，如提示访问频繁，弹出验证码，交互验证等。

针对上述情况，本文提出对于版块页—内容页设计的网络采集器，重采策略需要同时考虑采集实时性和对网站访问友好性的需求。一方面，能够对新增内容及时感知获取，另一方面，降低对于受访网站的访问频次，提升对采集网站的友好性。传统的重采策略通常基于刷新采集的方式，难以兼顾采集实时性和对网站访问的友好性: 提升访问频次，采集实时性得到提升，但会导致对网站访问的过于频繁，友好性变差；反之，降低访问频次，友好性提升，但采集实时性无法保证。

针对上述问题，本文将版块页在不同时间点是否增加新内容建模为一个时间序列，提出了一种预测的思路，通过预测未来某一时刻是否更新来指导传统的重采策略。在理想状态下，当版块页未更新时，网络爬虫通过预测，不进行采集，当版块更新时，网络爬虫通过预测进行采集。这样既保证了对新增内容的及时获取，又降低了采集的频次，从而有效兼顾了采集实时性和对网站访问友好性的需求。图2给出了一个兼顾实时性和友好性的重采策略示意图。其中有“+”号页表示版块页有更新。

图2 兼顾实时性和友好性的重采策略

传统的时间序列分析方法，包括基于随机过程理论和数理统计学的分析方法，虽然在对时间序列的统计特征分析上取得了一定的效果，但对于大规模的、存在噪音的实际数据进行预测、分类和知识发现时，效果并不理想。这类方法通常需要特定的模型结构，且对数据的转换可能会造成数据转换出错导致分析结果失真或错误，大大降低了处理速度，难以满足应用领域要求的时效性[2]。深度学习或神经网络等技术，以数据为基础，利用算法自动从数据提取特征，不受限于固定的模型结构，其中递归神经网络 (recurrent neural network，RNN)[3-4]作为一种循环反馈的神经网络框架，能够考虑时间序列的时序相关性，理论上能够利用任意长度的历史信息，因此可以更加全面完整地对时间序列进行建模。作为一种特殊的 RNN 模型，长短期记忆(long short-term memory，LSTM)[5]网络通过自身特殊的结构设计，有效地规避了常规RNN 训练过程中的梯度消失和梯度爆炸问题[6]，能够比较有效地被训练，从而真正有效地利用历史序列信息。目前， LSTM 已经在声音识别[7]、视频分类[8]、语音理解[9]等诸多前沿领域中得到了广泛研究和应用。

版块页的内容更新，除了与当前时刻的输入有关，而且还可能与历史的输入相关。为了抓住版块页更新的时序特性，本文提出了一种基于LSTM网络的时间序列预测模型，用于改进传统的重采策略，在获取新增内容的同时，兼顾时效性和友好性。

1 相关工作

1.1 WEB时序动态演化

对Web内容的时序动态和演化，主要集中在对整个互联网发展演化的研究。

Ntoulas等[10]发现web页面创建和老化非常快。 Olston 和 Pandey[11]研究 web页面中信息的寿命，提出重采策略。允许爬虫对准持久的内容，替代临时内容，能够更快的覆盖子序列的变化。 Adar[12]研究了web正文的变化，包括时间间隔(小时级和低于小时级的爬取)和实际的变化(页面级变化，DOM树变化，和词级变化)。Bar-Yossef[13]研究了Web的消亡，发现不仅很多页面存在快速消亡，很多Web的子图也会快速消亡。

Barbosa[14]首次利用从文本中抽取的静态特征预测页面的变化行为。基于这种想法，Tan 和 Mitra[15]提出用户动态特征，及其他从web链接结构和web搜索日志中抽取的特征，对具有相似变化行为的页面分组。Radinsky和Bennett[16]更近一步，提出一个变化预测框架，使用内容的特征和与观察到变化页面的度和关系，与其他页面的关联，以及与之前遇到的各类变化的相似度。

Li等[17]为了克服在盲采样下传统采集方法对估计页面更新存在的偏差，提出了四种不同层级的采样算法。

本文的工作不是对整个互联网进行研究，而是针对特定的具有版块页-内容页结构的版块进行重采。此外，上述工作的重点在于维持搜索引擎或数据库中数据的新鲜度，而本文的关注重点在于获取新增内容的同时考虑对网站访问的友好性。

1.2 WEB新增内容发现

Dasgupta[1]研究了爬虫能够有效发现新页面的程序。他们提出了利用历史统计的算法来估计哪些页面最可能链向新内容。他们发现，基于对链向新内容页面的研究，能够通过监控很小的一些选择好的页面，发现90%的新增内容，另外10%则需要付出额外的努力。

Santos等[18]提出了不仅要维护已采集页面的新鲜度，还要确定新的相关内容，并扩展该集合的观点。同时，在分析构建的话题相关数据集上发现大部分页面有非常高或非常低的变化率。

李魁等[19]提出了基于一种“版面—主题关联判断”(BTCJ)算法,采用一种基于版面扩展的采集策略，这种策略在论坛采集准确率和覆盖率方面显著优于广度优先策略，并具有良好的泛化能力。

Prieto等[20]提出了一种基于推的策略，通过设计网站管理者主动推送更新的协作系统，实现对页面变化的快速感知。这种方法虽然有效，但需要网站管理者的授权。

上述工作在一定程度上说明了基于版块页-内容页这种架构的采集器能够高效地获取到新增的内容。本文要优化的采集策略也是基于在此架构上。但上述工作的关注点在于及时地获取新增内容，本文在考虑实时性的同时，还考虑对网站访问的友好性。

1.3 时间序列预测

时间序列预测分析就是利用过去一段时间内某事件时间的特征，来预测未来一段时间内该事件的特征，一些典型的场景包括汇率预测，网站访问量预测等。随着深度学习的发展，神经网络在时间序列预测上取得了较好的效果。

循环神经网络(RNN)是目前常用的一种网络结构。传统的神经网络假设数据输入之间是相互独立的，之间没有依赖关系，但是，许多任务上，这种假设与实际情况差别较大。如在自然语言处理中，对于句子来讲，句子中的词出现的概率不是独立的，而是受到其前面词的影响。在语音识别中，连续的语音之间同样存在依赖关系，而RNN的出现可以捕获到这些输入序列中存在的特征模式[3-4]，因为，RNN的结构决定了其特别适合用来处理序列数据，其结构如图3所示。

图3 循环神经网络示意图

图3的左半部分展示了循环神经网络的示意图。与其他类型的神经网络最显著的区别是其存在回路，即当前时间步骤的输出作为下一个时间步骤的输入。理论上，当前时间步骤的计算可以利用之前所有步骤输入的信息，就犹如RNN能够记住之前数据输入的状态，利用之前输入的信息，计算当前的输出，这是RNN网络结构的巨大优势。

在实际应用中，原始的RNN建模长距离依赖的能力并没有人们期待的那样好，原因在于梯度消失的问题。为了解决RNN在训练过程中梯度消失的问题，主要采用基于门的循环单元来缓解梯度消失问题。目前常用的是LSTM[5]和GRU(Gated Recurrent Unit )[21]。

LSTM的提出较好解决了RNN训练过程中的梯度消失问题[6]，近年来，又得益于计算机计算速度的提升和GPU等加速硬件的普及，LSTM在许多应用领域取得了成功。原始的LSTM由Hochreiter等[5]提出，Gers等[22]在原始LSTM模型的基础上进行了若干的改进。LSTM利用门机制来解决梯度消失的问题，其内部结构如图4所示。它由3个控制门(gate)和一个内部存储单元(cell)组成，gate是一种让信息选择性通过的机制，全0表示不让任何信息通过，全1表示让所有信息通过，cell则起到了保持和传递信息的作用。三个控制门依次是输入门(input gate，it)，遗忘门(forget gate，ft)和输出门(output gate，ot)，g，h为tanh(·)激活函数，σ为sigmoid(·)激活函数，xt，ct和st分别是LSTM单元步骤t时的输入向量，内部状态向量和输出向量，zt就是标准RNN中的输出。

图4 LSTM单元结构

与LSTM相比，GRU单元只有两个门，重置门(reset gate)和更新门(update gate)，如图5所示。重置门决定了新的输入信息如何与之前的信息交互，更新门决定了如何保留之前的信息。另外，GRU没有内部记忆单元cell。Chung等[23]的研究表明，两者的性能相近，关键在于参数的调节和训练数据。目前， LSTM 已经在声音识别[7]、视频分类[8]、语音理解[9]等诸多前沿领域中得到了广泛研究和应用。

图5 GRU单元结构

本文借鉴LSTM网络能够较好地学习序列依赖的特性，用于构建时间序列预测模型。

2 本文工作

重采策略无法兼顾采集的实时性和对网站访问的友好性，我们考虑采用预测的方法对重采策略进行改进，通过预测版块页是否更新来指导采集行为，从而达到兼顾采集时效性和对网站访问友好性的目的。本文首先形式化地定义了预测版块页更新的问题，通过时间序列预测建模该问题，模型通过学习版块页的更新规律，改进重采策略。

2.1 问题定义

对于任意给定的版块页，其具有较丰富的历史更新信息，我们希望预测其在未来时刻是否更新。

该问题可以形式化为给定版块B和其更新的历史信息C=[(t0,y0),(t0+ΔT,y1),…,(t0+iΔT,yi),…,(t0+nΔT,yn)], 其中，(t0+iΔT,yi)表示t0+iΔT时刻页面的更新状态yi，yi∈{0,1}。预测其在未来时刻Tf更新的概率，如式(1)所示。

yf:P(Y|B,C,Tf)

(1)

2.2 时间序列预测模型TSP

我们将该问题建模为一个时间序列预测问题。对于每个时间点，模型输出为一个二分类的值。

对于任意一个版面页,在时间序列[t0+ΔT,t0+2ΔT,……，t0+iΔT,t0+nΔT]中观察到版块页的变化序列，需要预测在tr(ti

(2)

其中,N为观测的时间序列数量，i为每个时间序列的长度。

图6给出了TSP预测模型的架构。按照网络的功能可分为两个部分: 循环层和输出层。

图6 TSP模型架构

TSP模型的底部为一个标准的LSTM网络，用来捕获输入时间序列内的特征模式。上文分析提到，LSTM的计算方式可以不用对序列依赖的特征做过强的假设，并且，LSTM的结构特点使LSTM在理论上可以学习任意时间长度和多时间尺度的时间序列特征信息。而现有LSTM的训练方法也非常成熟，模型可以很快地收敛。因此，TSP采用LSTM来建模消息传播时间序列中的序列特征模式。TSP输出层是一个标准的前馈网络，利用softmax输出来对不同时刻版块页的状态进行预测。

如图6所示，其中xt是输入Xi中的第t个元素，输入序列长度为T，模型的输入仅包含时间信息。Wl是循环参数矩阵，st是LSTM的隐藏层状态，用来保持版块页的更新状态，可以看成是版块页到第t个时间点时的表达，该表达包含了之前版块更新的动态信息。Ws是输出层的参数矩阵。yt是第t个时间点经过softmax对版块页更新状态的预测值。

2.3 改进的重采策略TSP-RC

我们通过训练得到预测模型后，可以通过预测未来时刻版块页是否更新来指导采集。该算法的具体步骤在算法1中具体描述。

算法1 TSP-RC输入:采集间隔,初次采集时间t0,采集周期ΔT,预测模型M,版块页bi输出:1.while(true):2. tc:当前时间3. if((tc-t0)%ΔT==0):4. isUpdate=Prediction(M,tc)5. if(isUpdate):6. crawl(bi)7. crawl(新增内容页面)8. else:9. sleep(ΔT)

3 实验与分析

本节通过微信公众号、新闻门户、微博三类数据对本文所提模型进行验证。首先，详细介绍所采用数据集的格式，抽取方法及训练、测试集的设定。接着引入两种评价方法对预测结果进行评价。最后，与未优化的重采策略进行比较，验证TSP-RC策略的有效性。

3.1 数据集

DataSet-1: 微信公众号数据

实验数据集来自微信公众号，该数据集抓取了1 000个活跃公众号从2018年2月1日至2018年4月30日的所有发布文章记录。每个微信公众号的文章列表页可以看作是一个独立的版块页。我们将每个公众号发布记录按天进行切分，形成89个等长的片段，每个片段包含24个小时的版块页更新状态。实验为每一个公众号单独训练一个模型，使用每个公众号前76天的数据作为训练集，后13天的数据作为测试集。

DataSet-2: 新闻门户数据

实验数据集来自新浪网，该数据集抓取了10个活跃频道(国内、社会、财经等)从2018年6月1日至2018年8月31日的所有发布文章记录。每个频道可以看作是一个独立的版块页。我们将每个频道发布新闻的记录按天进行切分，形成92个等长的片段，每个片段包含24个小时的版块页更新状态。实验为每一个频道单独训练一个模型，使用频道前76天的数据作为训练集，后16天的数据作为测试集。

DataSet-3: 微博数据

实验数据集来自新浪微博，该数据集抓取了1 000个活跃微博主从2018年6月1日至2018年8月31日的所有发布微博记录。每个微博主的微博列表页可以看作是一个独立的版块页。我们将每个微博主的发布记录按天进行切分，形成92个等长的片段，每个片段包含24个小时的版块页更新状态。实验为每一个微博主单独训练一个模型，使用每个微博主前76天的数据作为训练集，后16天的数据作为测试集。

针对上述三个数据集，我们对时间点进行了转换。每个数据转换为一个四元组，其中，dayOfMonth表示一月中的第几天，取值为[1,31],dayOfWeek表示一星期中的第几天,取值为[1,7]的整数，hour表示24小时中的第几个小时,取值为[0,23]的整数，label表示为是否发表新内容，取值为[0,1]的整数，0表示未更新，1表示更新。使用作为模型输入的时间向量。表1给出了实验数据的一个样例。

表1 实验数据样例

3.2 评价标准

本文引入两种评价标准用于判断重采策略的效果。

时效性: 时效性度量用于判断重采策略是否及时地发现了版块页的更新内容。其形式如式(3)所示。

(3)

重采策略在时效性上的值越大，则采集新增内容的时效性越好。

友好性: 友好性度量用于判断重采策略对网站访问的频繁程度。其形式如式(4)所示。

(4)

重采策略在友好性上的值越大，则采集器对网站的无效访问频度越低，友好性越强。

传统的重采策略不存在预测算法，在时效性和友好性计算式(3)和式(4)中的正确预测可以理解为某时刻是否进行定周期采集即为做出了预测。

3.3 参数设置

在TSP-RC模型中我们设置初次采集时间t0为0,采集周期ΔT为1h。为了能让TSP-RC模型取得较好的效果，本文设计了一系列实验对TSP-RC模型的模型参数进行调整。TSP-RC模型的激活函数使用sigmoid函数，隐含层节点数为128，时间窗口选为10。此外模型所需要调整的主要参数包括正负样例的权重和算法最大迭代步数。

迭代步数: 模型训练使用改进的Adam[24]算法，学习率设置为0.03。在抽样样本的实验中，我们发现模型在150步达到较为良好的收敛效果。为保证模型收敛，本文在模型中选取最大迭代步为300。

3.4 比较方法

为了评价TSP-RC策略的有效性，我们与未做改进的重采策略进行对比。

重采策略(Re-Crawling Strategy): 重采策略是一种有效的感知新增内容的爬虫策略。通过按照固定的时间间隔重新访问版块页面，能够及时地发现版块页的更新，并进一步获取新增的内容。在本实验中，由于数据是按照小时检测版块页的更新，为了能及时地检测到更新，我们设定重采策略的时间间隔为1h、2h、3h,分别记为RC(1h)，RC(2h)，RC(3h)。

3.5 实验结果

根据前述的实验方法，本文首先说明重采策略在不同时间间隔上时效性和友好性的表现。我们选取了从1h～23h的时间间隔，分别计算了其在三个数据集上的时效性和友好性，图7给出了其效果的折线图。从图上可以看出，随着时间间隔的扩大，RC策略的时效性逐步降低，友好性逐步提高。

之后本文将TSP-RC策略与RC(1h)、RC(2h)、RC(3h)策略在三个真实数据集上进行比较，并通过两种评价指标进行了结果展示，实验结果列于表2中。其中，时效性和友好性均为对所有预测结果的平均值。

图7 重采策略在1h～23h上时效性和友好性的效果

表2 TSP-RC策略与比较方法在评价标准上的表现

从表2中可以显见，较之对比方法RC(1h)，本文所提的TSP-RC策略在保证时效性的前提下，大幅降低了对网站的访问频率，提升了友好性；而相较RC(2h)和RC(3h)，TSP-RC既能保证很高的时效性，又能获得大体相当的友好性。另外，RC策略在1h、2h、3h上的结果也说明该方法无法同时兼顾时效性和友好性。为了说明本文方法的效果，我们选取了两个样例对TSP-RC进行说明。

表3 TSP-RC对公众号A的预测结果

在公众号A上，按照式(3)和式(4)计算可以得到，TSP-RC的时效性为1，友好性为0.63。在实时性和友好性方面都有比较好的兼顾。通过查看公众号A的版块页更新情况，该公众号更新内容的频率较低，且较为规律，此时，TSP-RC较好地学习到了A的更新习惯。

在公众号B上，TSP-RC则退化为RC(1h)。通过查看公众号B的版块页更新情况，该公众号更新内容的频率非常高，并且无规律，此时，TSP-RC的预测结果保证了采集的时效性，但没有兼顾友好性。

表4 TSP-RC对公众号B的预测结果

针对在三个数据集上的不同表现，我们分别计算了不同数据集上的发文频率(发文数据占总数据的比值)，列于表5。通过表2中友好性结果及表5中发文频率的结果，可以看到，新闻数据集上的发文频率最高，其友好性在三组结果中最低；微博数据的发文频率居中，取得最佳友好性；微信的发文频率最低，友好性居中。此外，我们还注意到微信公众号中包含了两类不同的公众号，一类有发文次数限制，而另一类没有限制。而微博和新闻上没有此种限制。由此可以看到，友好性与发文频率有一定关联，但并非直接线性相关，对于友好性的优化还存在较大空间。

表5 三个数据集的发文频率

通过在不同数据集上的实验可以看到，TSP-RC模型在对不同类型的数据上均能够较好地兼顾时效性和友好性，具有较强的泛化能力。在实时性方面，模型在不同类型的版块上均保证了较高的实时性。在友好性方面，通过对样例的分析可以看出，模型在对相对低频更新的版块表现更好；对高频更新的版块，模型为了保证采集的时效性，友好性会有所下降。

4 总结与展望

本文指出了采集过程中为保证时效性而导致的对网站高频访问的问题，将这一问题形式化，并提出了一种基于时间序列预测的改进重采策略，用于兼顾采集的时效性和对网站访问的友好性。该模型仅利用网站版块页的历史更新记录，在采集的时效性和网站访问的友好性方面取得了较好的折中。通过在真实的微信公众号、新闻门户和微博三类数据上进行实验，与未改进的重采策略比较，本文所提出的TSP-RC策略在保证较高的实时性的基础上，很大程度上保证了友好性。但对友好性的优化方面，还存在较大空间，未来可考虑结合其他网站信息进行预测。