基于关系子群发现算法的聚焦爬行技术

论文摘要

“聚焦爬虫(Focused Crawling)”在万维网上爬行的时候,尽可能地下载与某(些)主题相关的网页,同时尽可能避免无关网页的下载。聚焦爬行的一个基本技术难点在于爬虫能否在实际下载网页之前即对该网页的主题相关度进行尽可能准确的预测。然而,这种预测所惟一能够依据的各种间接、微妙的相关度线索无处不在但却充满了嗓音,通过传统的机器学习方法利用这些信息将异常困难。这些信息往往由网页上该链接出现的的“上下文环境”提供,也叫“链接上下文信息”。本论文提出一种基于“自然语言处理技术”中的“解析”技术的从网页中自动提取精确的“链接上下文信息”的方法,该方法在webKB数据集上取得了较好的初步实验结果。虽然通过精确提取“链接上下文信息”能够有助于提高对链接指向网页的主题分类精度,但很多情况下这些链接上下文信息或者充满嗓音,或者仍然过于稀少,依赖于这些不完备的信息进行准确的分类还是非常困难的。为此,本论文提出一种新颖的基于“关系子群发现”技术的聚焦爬行算法,它主要的贡献是两方面的:第一,它采用具有更强知识表示能力的一阶谓词逻辑来表示链接的背景知识,从而避免了精确提取“链接上下文信息”本身带来的技术挑战;第二,使用“子群发现(Subgroup Discovery)”的技术从以一阶逻辑表示的背景知识“归纳”出“聚焦爬行规则”。我们通过利用DMOZ人工网页分类数据集进行了多个类别实验,实验结果表明这种基于“关系子群发现”的“聚焦爬行”思路是切实可行的。一旦累积到足够多的在线训练数据集,我们的算法就能够发现大量的具有高“支持度”和“置信度”的用一阶逻辑表示的“聚焦爬行规则”。这些规则将指导以后的“聚焦爬行”过程,期间下载的不相关网页数量明显大幅度减少,同时能够维持“聚焦爬行”过程的正常运行。我们同时与现有的几种相关算法进行了详尽的比较,实验结果表明我们的算法在“收获比”方面明显优于其他方法。

论文目录

• 提要
• 第一章 绪论
• 1.1 什么是聚焦爬行
• 1.1.1 网络爬虫简介
• 1.1.2 聚焦爬行简介
• 1.2 聚焦爬行技术研究现状
• 1.2.1 聚焦爬行的两个研究方向
• 1.2.2 第一个研究问题：超链接相关性的鉴别
• 1.2.2.1 FishSearch算法
• 1.2.2.2 SharkSearch算法
• 1.2.2.3 Cho等的实验
• 1.2.2.4 第一代聚焦爬虫
• 1.2.2.5 WTMS系统
• 1.2.2.6 三种主题爬行策略的比较实验
• 1.2.2.7 智能爬行
• 1.2.2.8 加速聚焦爬虫
• 1.2.3 第二个研究问题：tunnelling难题
• 1.2.3.1 基于Context Graph的爬行策略
• 1.2.3.2 基于增强学习的爬行策略
• 1.2.4 总结
• 1.3 本文的组织
• 第二章 背景知识介绍
• 2.1 HTML和DOM简介
• 2.1.1 HTML语言
• 2.1.2 DOM模型
• 2.2 自然语言处理技术简介
• 2.2.1 自然语言处理技术
• 2.2.2 语法解析技术
• 2.3 关系机器学习
• 2.4 子群发现技术
• 2.5 小结
• 第三章 本文技术贡献一：精确抽取链接上下文相关文本
• 3.1 链接上下文相关文本及其作用
• 3.2 提取链接上下文相关文本带来的技术挑战
• 3.3 链接上下文相关文本提取新方法
• 3.3.1 总体框架
• 3.3.2 对网页“段落”的定位
• 3.3.3 对锚文本和邻近文本的定位
• 3.3.4 对相关“标题文本”的提取
• 3.3.5 总体算法流程的伪码表示
• 3.4 算法的系统实现及比较实验结果
• 3.4.1 系统实现
• 3.4.2 比较实验结果
• 3.4.3 新方法的局限性和可能的改进
• 第四章 本文技术贡献二：基于关系子群发现聚焦爬行
• 4.1 聚焦爬行新框架
• 4.1.1 关系知识表示
• 4.1.2 子群发现
• 4.2 具体算法流程
• 4.2.1 探索阶段
• 4.2.2 学习阶段
• 4.2.3 利用阶段
• 4.3 实验评估
• 4.3.1 算法实现
• 4.3.2 实验设定
• 4.3.3 实验结果
• 4.4 结论
• 第五章 总结与展望
• 5.1 本文的创新工作
• 5.2 不足之处与未来的工作
• 参考文献
• 攻读博士期间发表的学术论文及其它成果
• 致谢
• 摘要
• Abstract