基于在线自学习的页面更新频率预测算法

摘要

近年来,互联网的整体规模越来越大,作为搜索引擎采集模块的爬虫的工作压力与日俱增,即使最专业的搜索引擎服务提供商,如谷歌、百度,也无法保证所有页面的时效性。而就单个页面而言,只有部分页面的变化频率较快。因而,通过页面更新频率预测算法使爬虫只下载那些变化了的网页,对减轻爬虫的工作压力有着重要的意义。
　　本文围绕着如何在实际环境中有效预测网页变化的需要,在深入研究了网页变化规律的基础上,基于在线抽样检测的算法思想,研究了网页不同特征集对基于聚类的抽样检测算法的影响,特征集包括词向量特征、文本特征、URL特征、动态特征等。在此基础上创新性的提出了遗传基因特征的概念,利用遗传基因特征实现了自学习的优化算法。为了确定实验效果、评价我们的算法,我们搜集了一个真实网页集合的真实变化情况,建立了实验数据集。
　　本文研究的内容和成果归结为以下方面:
　　首先,建立了评价网页更新频率预测效果的实验数据集。实验数据集来源于不同类型网站的不同类型网页,保证网页集合的多样性与代表性,使得其他研究人员可以在此数据集上进行网页更新的预测的相关研究。数据集网页数量约为30万,分布在不同的122个网站上。
　　然后,提取了网页的词向量特征、文本特征、URL特征、动态特征等,研究了不同特征集对基于聚类的在线抽样检测算法的影响,并利用预测命中率评价指标量化了不同特征集对聚类算法实验效果的影响,进而分析了聚类算法的有效性与性能上限。
　　最后,本文提出了利用遗传基因特征自动优化下一轮的特征,进而实现了在线自学习的页面更新预测算法。遗传基因特征根据上一轮预测结果生成惩罚或奖励因子,从而优化下一轮的网页特征,实现了算法的在线自学习过程。本文提出利用格雷码代替二进制字符串实现遗传基因特征,达到了利用普通的加减法实现奖励或惩罚的目的。
　　结果表明,基于在线自学习的页面更新预测算法,有效地预测了页面的变化规律,预测命中率比随机算法提高了约43个百分点,比基于网站的抽样检测算法提高了约20个百分点,因而能够有效的节省爬虫网络带宽。

目录

封面

中文摘要

英文摘要

目录

第1章 绪 论

1.1 研究的背景和意义

1.2 国内外研究进展与发展现状

1.3 本文的主要研究内容

1.4 文章的结构安排

第2章 页面更新预测相关基础知识

2.1 爬虫基本概念

2.2 增量爬虫基本概述

2.3 页面更新频率预测算法概述

2.4 本章小结

第3章 基于抽样检测的页面更新频率在线预测算法

3.1 在线预测算法概述，实验数据及评价指标

3.2 基于词向量特征聚类的抽样检测算法

3.3 基于静态特征聚类的抽样检测算法

3.4 基于静态特征以及动态特征聚类的抽样检测算法

3.5 基于聚类的抽样检测算法有效性分析

3.6 本章小结

第4章 自学习的优化算法

4.1 基于在线自学习的页面更新频率预测算法

4.2 采用二进制字符串实现的遗传基因特征集

4.3 格雷码

4.4 采用格雷码实现的遗传基因特征集

4.5 本章小结

结论

参考文献

攻读硕士学位期间发表的论文及其它成果

声明

致谢