基于社区增量自适应爬虫研究
摘 要：在分析传统的网络蜘蛛搜索特点的基础上，充分利用Web资源分布的特点，提出了基于在线增量自适应算法的搜索策略。该算法一方面避免了过早陷入Web搜索最优子空间的陷阱；另一方面不断对爬虫数据库更新，以提高其对链接主题的判断能力。通过对四所著名大学计算机网站做的搜索实验，表明新的算法可以有效地提高网络蜘蛛的搜索性能。
关键词：网络蜘蛛；搜索策略；在线增量自适应
随着Internet的快速发展，Web上的信息资源也呈指数级增长，搜索引擎已经成为网络用户获取各种信息的必备工具。对于搜索引擎来说，要抓取互联网上的所有信息几乎是不可能的，从公布的数据来看，容量最大的搜索引擎也只不过是抓取了整个网络信息的40%左右。传统的搜索引擎(如Google、Baidu、Yahoo等)大多数都是面向所有信息的搜索引擎，是一种通用搜索引擎。这种通用搜索引擎已经不能满足特定用户更深入的查询需求，他们对信息的需求往往是面对特定领域和特定主题的。面对挑战，适应特定人群需要的专业搜索引擎逐渐引起研究学者的重视。
主题网络蜘蛛是最近几年兴起的研究热点，它针对某个专门的领域进行搜索，以满足特定人群的个性化需求。网络蜘蛛研究的核心是解决页面和URL的主题相关性判别的问题，因此如何评价链接价值就成了网络蜘蛛爬进效率的关键。链接价值可以分为两类，即基于立即回报价值和基于未来回报价值。
立即回报价值算法是依据搜索时在线获得的文本或Web结构来对链接的页面重要程度进行预测，进而决定链接访问顺序。这类方法理论基础好，计算简单，在距离相关页面比较近的时候表现出良好的性能。但它很难反映Web的整体情况，网络蜘蛛在距离相关页面比较远的时候容易迷失方向。基于未来价值的算法利用Web上的信息分布在某种程度的相似性，对网络蜘蛛先进行训练，使其具有一些经验信息，对未来搜索具有一定的预测性。但其预测能力有限，而且需要用户选择种子集，搜索时不灵活，容易引起主题漂移[1-4]。
本文基于两类评价方法，提出了一种在线学习的自适应综合价值的网络蜘蛛搜索算法，利用Web资源分布的某些相似性和链接价值的关系，将立即价值和未来价值的评价方法相结合，在爬行过程中不断自身提高链接主题相关性的判断能力，从而改进网络蜘蛛的性能。
1 主题爬行策略
根据评价链接价值所采用的不同方法，现有的网络蜘蛛的搜索策略分为两大类：基于立即回报价值评价的搜索策略和基于未来回报价值的搜索策略。本文采用基于内容评价的策略(基于立即价值)和基于巩固学习的搜索策略(基于未来价值)。
基于内容评价的搜索策略，主要是根据主题与链接文本“语义”的相似度来评价链接价值的高低。链接文本是指周围的说明文字和和链接URLs上的文字信息。相似度的评价一般采用下面的公式：
其中，q代表主题关键词集合，p代表页面链接文本集合，Wkp代表d中单词对某一主题的重要程度，Wkp通常采用tf×idf公式计算。
基于巩固学习的搜索策略，巩固学习的优势在于能预测远期的回报价值(也称未来价值)。未来价值用Q来表示，这种方法的核心就是如何计算链接的Q价值。为此，搜索过程被分为训练和搜索两个阶段。训练阶段用巩固学习算法计算每个链接的Q价值，按价值的大小分为若干类，并用每一类中的文本信息训练一个Naive Bayes分类器；在搜索阶段，面对价值未知的链接，则根据链接文本，用Naive Bayes分类器计算链接落在每一类中的概率，并以这个概率为权值来计算链接的Q价值。因为Q价值反映的是未来的回报预测值，所以当搜索的页面与主题不相关时，网路蜘蛛也可以根据未来回报的预测值来确定正确的搜索方向。
该模型的核心就是如何计算链接的Q价值。Q价值的计算公式[５]：
2 在线增量自适应算法网络蜘蛛搜索策略
2.1 Web资源分布和链接价值的关系
