简述社区增量自适应爬虫项目研究

　　随着Internet的快速发展，Web上的信息资源也呈指数级增长，搜索引擎已经成为网络用户获取各种信息的必备工具。对于搜索引擎来说，要抓取互联网上的所有信息几乎是不可能的，从公布的数据来看，容量的搜索引擎也只不过是抓取了整个网络信息的40%左右。传统的搜索引擎（如Google、Baidu、Yahoo等）大多数都是面向所有信息的搜索引擎，是一种通用搜索引擎。

　　主题网络蜘蛛是近几年兴起的研究热点，当"蜘蛛"程序出现时，现代意义上的搜索引擎才初露端倪。它实际上是一种电脑"机器人",电脑"机器人"是指某个能以人类无法达到的速度不间断地执行某项任务的软件程序。由于专门用于检索信息的"机器人"程序就象蜘蛛一样在网络间爬来爬去，反反复复，不知疲倦。网络蜘蛛即Web Spider,是一个很形象的名字。把互联网比喻成一个蜘蛛网，那么Spider就是在网上爬来爬去的蜘蛛。网络蜘蛛是通过网页的链接地址来寻找网页。如果把整个互联网当成一个网站，那么网络蜘蛛就可以用这个原理把互联网上所有的网页都抓取下来。 所以，搜索引擎的"机器人"程序就被称为"蜘蛛"程序。它针对某个专门的领域进行搜索，以满足特定人群的个性化需求。网络蜘蛛研究的是解决页面和URL的主题相关性判别的问题，因此如何评价链接价值就成了网络蜘蛛爬进效率的关键。链接价值可以分为两类，即基于立即回报价值和基于未来回报价值。

　　立即回报价值算法是依据搜索时在线获得的文本或Web结构来对链接的页面重要程度进行预测，进而决定链接访问顺序。这类方法理论基础好，计算简单，在距离相关页面比较近的时候表现出良好的性能。但它很难反映Web的整体情况，网络蜘蛛在距离相关页面比较远的时候容易迷失方向。基于未来价值的算法利用Web上的信息分布在某种程度的相似性，对网络蜘蛛先进行训练，使其具有一些经验信息，对未来搜索具有一定的预测性。但其预测能力有限，而且需要用户选择种子集，搜索时不灵活，容易引起主题漂移。

　　本文基于两类评价方法，提出了一种在线学习的自适应综合价值的网络蜘蛛搜索算法，利用Web资源分布的某些相似性和链接价值的关系，将立即价值和未来价值的评价方法相结合，在爬行过程中不断自身提高链接主题相关性的判断能力，从而改进网络蜘蛛的性能。

　　1 主题爬行策略

　　根据评价链接价值所采用的不同方法，现有的网络蜘蛛的搜索策略分为两大类：基于立即回报价值评价的搜索策略和基于未来回报价值的搜索策略。本文采用基于内容评价的策略（基于立即价值）和基于巩固学习的搜索策略（基于未来价值）。

　　基于内容评价的搜索策略，主要是根据主题与链接文本"语义"的相似度来评价链接价值的高低。链接文本是指周围的说明文字和和链接URLs上的文字信息。相似度的评价一般采用下面的公式：

　　其中，q代表主题关键词集合，p代表页面链接文本集合，Wkp代表d中单词对某一主题的重要程度，Wkp通常采用tf×idf公式计算。

　　基于巩固学习的搜索策略，巩固学习的优势在于能预测远期的回报价值。未来价值用Q来表示，这种方法的就是如何计算链接的Q价值。为此，搜索过程被分为训练和搜索两个阶段。训练阶段用巩固学习算法计算每个链接的Q价值，按价值的大小分为若干类，并用每一类中的文本信息训练一个Naive Bayes分类器； 分类器是一种计算机程序。他的设计目标是在通过学习后，可自动将数据分到已知类别。应用在搜索引擎以及各种检索程序中。同时也大量应于数据分析与预测领域。   分类器是一种机器学习程序，因此归为人工智能的范畴中。人工智能的多个领域，包括数据挖掘，系统，模式识别都用到此类程序。 在搜索阶段，面对价值未知的链接，则根据链接文本，因为Q价值反映的是未来的回报预测值，所以当搜索的页面与主题不相关时，网路蜘蛛也可以根据未来回报的预测值来确定正确的搜索方向。

　　该模型的就是如何计算链接的Q价值。Q价值的计算公式：

 

　　2 在线增量自适应算法网络蜘蛛搜索策略

　　2.1 Web资源分布和链接价值的关系

　　虽然整个网络资源的分布是无序的，但近年来的研究表明，与某一主题相关的页面以不同群聚群体的方式分散在网络中，把这些群体称为Web社区。图1中显示了这种Web社区的分布关系。在网页的设计过程中不可能把所有相关的网页链接在一起，网页中只包含了极少部分与该主题相关的网页链接，这些资源信息一起构成了一个与某一主题相关的Web社区。在某一站点附近有很多紧密联系的站点，它们都能基本地反映某个主题。但在网页的发布过程中，可能会出现与之有一定关联但又与主题不相关的无关网页，这些无关网页在网络蜘蛛的爬行过程中会导致中心主题发生漂移。正是由于这些无关网页的"干扰",使得网络蜘蛛在爬行的过程中随着时间的推移，爬行出来的链接会与初链接的主题相关性差别越来越大，系统爬行到的网页也越来越少。

　　2.2 算法思想

　　根据Web资源的分布信息，本文把网络蜘蛛爬行的过程人为地分为两个阶段：挖掘和探索。在Web社区内，由于和主题相关的网页比较多，立即价值比较大，这个时候就要求能尽快地挖掘Web社区内与主题相关的网页信息。这个时候适合选取注重发掘立即价值的搜索策略。而在Web社区之间，由于存在大量与主题无关的网页，这个时候要注重探索，尽可能地探索到与主题相关的Web社区。但这个时候链接的立即价值会很小，适合选取基于未来价值的搜索策略，本文采用基于巩固学习的搜索策略。同时为减少网络蜘蛛在爬行过程中的主题漂移，提高主题相关性的判断能力，在每爬完N个Web社区后，系统选取爬虫数据库中爬行到的与主题相关度高前100名的页面，与其对应的正向链接信息组成的实例加入链接分类器的训练数据。链接分类器一旦训练完成，就可以对新产生的链接进行相关度分析。网络爬虫（又被称为网页蜘蛛，网络机器人，在FOAF社区中间，更经常的称为网页追逐者），是一种按照一定的规则，自动的抓取万维网信息的程序或者脚本。随着网络的迅速发展，万维网成为大量信息的载体，如何有效地提取并利用这些信息成为一个巨大的挑战。搜索引擎（Search Engine），例如传统的通用搜索引擎AltaVista,Yahoo!和Google等，作为一个辅助人们检索信息的工具成为用户访问万维网的入口和指南。自身通过爬虫数据库新进的主题相关度高的页面和页面正向链接信息不断修正，提高主题相关性的判断能力。

　　2.3 在线增量自适应算法的设计和实现

　　在线增量自适应算法的本质是：通过网路蜘蛛的爬行，在Web社区内尽可能地挖掘和主题相关的页面，而在社区外获取那些具有较高的未来Q价值的链接。反过来，在搜索时又根据链接文本的Q价值估算出链接的价值，决定选择行动的概率。同时，不断通过爬虫数据库新进的主题相关度高的页面和页面的正向链接信息修正，提高链接主题相关性判断能力。Java 5.0是自Java出现以来重要的版本。随着对Java语言的主要修改和Java平台中重要的新API的出现，需要精通的新特性有很多。Java,是由Sun Microsystems公司于1995年5月推出的Java程序设计语言和Java平台的总称。用Java实现的HotJava浏览器（支持Java applet）显示了Java的魅力：跨平台、动态的Web、Internet计算。从此，Java被广泛接受并推动了Web的迅速发展，常用的浏览器现在均支持Java applet.本文利用Java技术，算法实现过程如下：

　　ZX-ZL（topic,startUrls）{

　　Link_1=fetch link（startUrls）；

　　While（visited<MAX_PAGES）{

　　//小于爬虫访问量

　　score_r1=sim（topic, doc）；  //计算立即价值

　　If（socre_r1>r1）

　　enqueue_1（frontier,extract_links（doc），score_1）；

　　else{

　　score_r2=Q（topic, doc）；   //计算未来价值

　　if（score_2>r2）

　　continue;

　　else

　　enqueue_2（links）；

　　}

　　}

　　}

　　2.4 算法过程描述

　　（1）网络蜘蛛首先从一个"种子集"出发，并选择其中的一个链接访问。

　　（2）按照式（1）计算链接节点的立即价值。

　　（3）判断所得的立即价值是否大于系统给定的阈值r1,如果大于给定阈值，则将该链接加入到候选URL列表里。如果小于给定的阈值r1,就利用式（2）计算此链接的未来价值。

　　（4）如果经计算所得未来价值大于系统给定的阈值r2,系统就并发另一个线程从此节点开始，返回步骤（2）。

　　（5）如果所得的未来价值小于给定的阈值r2,将该链接列入被舍弃的URL列表里。结束此线程。

　　另外每隔T的时间后，手动选择与主题相关度高前100的页面加入链接分析器进行训练，对爬虫数据库进行更新。

　　3 实验与结果分析

　　3.1 实验背景

　　本文选取了如表1所示的美国四所大学的计算机网站做了实际的搜索实验，搜索目的是寻找本地服务器中的计算机论文，以PDF和。PS结尾的计算机论文定义为相关文档。采用基于立即价值、未来价值和基于本文所描述的在线增量学习的自适应算法三种不同搜索策略的网络蜘蛛，在线统计Web上与计算机相关的论文数，并计算各自的查全率和查准率。本文采用FOLDOC在线计算机字典作为主题关键字集合。其中包括13 000个计算机词汇，并进行了一些扩充。

　　3.2 实验结果和性能分析

　　图2中，三种不同搜索策略在不同阶段的查全率不同。其原因在于，基于立即价值的搜索策略在相关社区中的搜索率很高，可以很快地找到相关网页，所以其增长率很快。但在找无关网页集合时容易迷失方向，从一个Web社区搜索完毕后进入另一个Web社区的能力较弱，查全率会降低；基于未来价值的搜索策略，在寻找无关页面集合中，未来价值对预见远期回报很有帮助，它可以很快地找到论文的目录所在，但早期的回报率不高；基于在线增量自适应算法采用综合的搜索策略，除在搜索初期其回报略低于基于立即价值的网络蜘蛛外，其增长率很快超过两种算法。不论是在社区内的搜索还是过度无关网页来获取远期回报，它都表现出了优异的性能。

　　图3中基于在线增量自适应算法的网络蜘蛛查准率显然高于其他两种。除了初的阶段外，其余时间的查准率都高于50%.其原因在于每隔一定的时间，爬虫数据库不断自我更新，提高主题相关性的判断能力。在Web社区外，在一定程度上避免了采集大量的无关文档；在主题相关的Web社区内又提高了其搜索能力，因此其查准率很高。而基于立即价值的网络蜘蛛在跨越Web社区时常常会发生主题偏移，容易导致局部。基于未来价值的网络蜘蛛在跨越Web社区时采集了大量与主题无关的文档，同时在主题相关社区内的搜索能力又比较低，因此查准率不高。

　　本文将基于改进的巩固学习方法的行动策略的在线增量自适应算法引入搜索引擎中，避免了过早陷入Web搜索局部子空间的陷阱。同时，不断更新爬虫数据库，提高了其对主题相关性的判断能力，从而提高了搜索引擎的查准率。实验表明，该算法的查全率不但大大高于两种传统的单一算法，同时也整体提高了搜索引擎的性能。