基于遗传算法的主题爬虫搜索策略研究

2020-07-26 来源：爱问旅游网

湖北工业大学硕士学位论文

基于遗传算法的主题爬虫搜索策略研究

姓名：梁云静申请学位级别：硕士专业：计算机应用技术指导教师：邵雄凯

20100301

湖北工业大学硕士学位论文

摘要

传统的搜索引擎需要对互联网上的信息进行广泛的收集和分析处理，随着互联网的急剧膨胀，传统的搜索引擎需要处理的网络信息也越来越多，同时也就不可避免的为用户提供了或多或少的无关信息。在专业化需求日益增长的今天，主题搜索引擎以其分类细致精确、数据全面准确的特点迅速流行起来，而主题搜索引擎的关键技术——主题爬虫的搜索策略就成为了近几年的研究热点。

本文将遗传算法应用在主题爬虫的搜索中，引入遗传算法来改进爬虫的搜索策略，利用遗传算法高效、并行、全局寻优的特点，提高爬虫的搜索效率。本文的研究内容主要有以下两个方面：根据网络特点改进传统的遗传算法；通过实验验证改进后的效果。

基于遗传算法的主题爬虫搜索策略，是将待检索的问题提交给通用搜索引擎，对其返回的结果集进行处理，选择一定数目的URL作为初始群体；通过交叉操作，提取初始群体中URL对应页面包含的所有超链，产生出大量新的个体，再对所有超链进行相似度预测，选出相关度高的种子作为交叉结果；通过变异操作，引入目录型网页，扩大搜索范围；通过选择操作，对遗传之后的结果进行处理，选出相关度高的个体作为新一代的种子进入新一轮的遗传；通过爬虫终止搜索条件，来结束爬虫的搜索。

本文在构造初始群时，将待检索的问题提交给通用搜索引擎Google，对其返回的结果集选择前n个URL，再扩展、去重、计算Authority和Hub值，重点是引入了Alexa排名，然后依据综合排名值选择初始种子集合。在交叉过程，根据超链的锚文本有效地预测对应的页面与主题的相似度。在变异阶段，根据目录型网页包含的大量链接和详细的分类来寻找相关网页。

本文设计了一个实验，来验证遗传算法在爬虫搜索中应用的可行性以及改进后的遗传算法的效果。在实验中，本文采用GA、HITS、Best-First三种算法分别对给定主题进行搜索，将搜索到的网页根据向量空间模型算法计算其与主题的相关度，再分别统计三种算法搜索到的相关的网页数。实验结果表明，本文的基于遗传算法的爬虫搜索策略在某种程度上具有一定的优势。关键词：主题爬虫，遗传算法，Best-First，HITS

湖北工业大学硕士学位论文

Abstract

Traditional search engine on the Internet requires extensive information collection and analysis and processing, with the rapid expansion of the Internet, traditional search engine need to handle more and more network information, while also inevitable that provides the user with more or less irrelevant information.

The Genetic Algorithm is used in our topic crawler search, the introduction of it improves the search strategy of the reptile, using the efficient, parallel, global optimization genetic algorithm to improve the search efficiency of the reptile. This study mainly includes the following two aspects: Improve the traditional Genetic Algorithm according to the network features; Test the improved results by experiments.

The topic of information search strategy,which based on Genetic Algorithm search strategy, first of all, submit the question will be retrieved to the general search engine，process result set returned，and select a certain number of URL as initial group; then it extract all the hyperlinks included in the page corresponding to the URL in initial group, produce a large number of new individuals, predict similarity among all the hyperlinks, and elect a high correlation of seeds as cross-cutting results, next, it introduce directory-type page to expand the search range through the mutation operation ,and elect the results come from the genetic treatment to get the individuals with high suitability degree which as a new generation of seeds go on into a new round of inheritance .At last, it end the search conditions by reptiles.

In this paper, when construct the initial cluster, it submit the questions will be retrieved to the general search engine Google. With the previous n-URL in the result set returned, there is a series of process like reexpand、de-emphasis、and calculate the Authority and Hub values。The paper focus on the Alexa ranking, then next select the initial seeds group according to integrated rank values. In the cross-process, it effectively predict the relevance between the corresponding page with the topic according to the anchor text of hyperlinks. In the variation phase, it find related pages according to the large number of links and a detailed classification included in the directory-type page.

This paper designed an experiment to test and verify the feasibility of Genetic Algorithm in reptile search as well as the effect of improved Genetic Algorithm. In the experiment, our paper used three kinds of algorithms searching the given topics, calculating the similarity of searched web pages to the topic according to the vector space model algorithm, then count related web pages which are searched out by this three algorithms. The results show that: the efficiency of GA algorithm is also higher than BF and HITS algorithms.

Keywords: Topic Crawler, Genetic Algorithm, Best-First, HITS

学位论文原创性声明和使用授权说明

原创性声明

本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进行研究工作所取得的研究成果。除文中已经标明引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在文中以明确方式标明。本声明的法律结果由本人承担。

学位论文作者签名：日期：年月日

学位论文版权使用授权书

本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权湖北工业大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。

学位论文作者签名：指导教师签名：

日期：年月日日期：年月日

湖北工业大学硕士学位论文

第1章引言

1.1 背景

随着互联网的快速发展，网络对人们的影响越来越大，而发展迅猛的万维网WWW(World Wide Web)技术，以其简单的使用方法和丰富的数据资源，成为了互联网上重要的信息发布和信息共享的平台。万维网作为一个全球性信息服务中心，丰富的数据资源和包罗万象的网络服务为人们的日常生活提供了很多便利。但是万维网庞大的数据量和迷宫般错综复杂的链接关系也给人们的使用带来了很多不便，试想，面对如此复杂而庞大的万维网，如何才能从海量的信息中找到自己的答案，这一问题困扰了越来越多的用户，也阻碍了互联网的发展。针对这个状况，人们开始研究一个新的技术——搜索引擎，搜索引擎就是根据用户提供的关键词在万维网上查找用户需要的信息并返回结果，这一技术的出现快速地打破了万维网复杂的局面，也解决了阻碍万维网发展的瓶颈问题。搜索引擎成为了指引人们走出“迷宫”的灯塔，它帮助全世界的网民方便快捷地找到了自己需要的信息，从而更好地展示着万维网独特的魅力。

传统搜索引擎，即通用搜索引擎，首先需要尽可能多、尽可能全面地采集互联网上的信息和页面，有时甚至是整个Web上的资源，然后把搜集到的页面下载并存储到本地，再为数据库中的页面信息建立索引，根据用户提供的关键词跟索引数据库进行匹配，从而查找相关页面并返回给用户。但是随着Web上信息的急速增长，全部采集万维网上的信息并且保持与万维网上信息变化同步已经越来越

[1]

困难，而且信息采集的速度也越来越不能满足人们实际应用的需要。为了解决

这些问题，传统搜索引擎采用了并行机制，但并行技术带来的效果仍不能满足广大网民的需要。此时，新一代的搜索引擎——主题搜索引擎应运而生，主题搜索引擎则是为了满足某些特定用户的需要，专门查询某一学科或某一主题的信息的查询工具，它可以在某个特定的范围内或者某个特定的主题上取得比传统搜索引擎更令人满意的结果。

1.2 搜索引擎分类

搜索引擎(search engine)是指根据一定的搜索策略、运用特定的计算机程序搜集互联网上的信息，再对信息进行组织和处理，将处理后的信息显示给用户，

湖北工业大学硕士学位论文

从而为用户提供检索服务的系统。

在1990年以前，没有人能搜索万维网。所有搜索引擎的祖先，是1990年由Montreal的加拿大麦吉尔大学(University of McGill)的三名学生(Alan Emtage、Peter Deutsch和Bill Wheelan)发明的Archie(Archie FAQ)，而在当时WWW尚未出现。虽然Archie搜集的信息资源不是网页（HTML文件），但和搜索引擎的基本工作方式是一样的：自动搜集信息资源、建立索引、提供检索服务。所以，Archie被公认为搜索引擎的鼻祖。时止今日，搜索引擎经历了二十年的时间，在这短短的二十年里，搜索引擎技术的发展一日千里，人们对搜索引擎的认识也越来越全面，目前，搜索引擎主要分为以下四类：

1. 目录式搜索引擎

目录式搜索引擎虽然有搜索功能，但严格意义上不能称之为真正的搜索引擎，它只是按照目录分类的网站链接列表。在互联网发展的早期，目录式搜索引擎完全依赖于手工操作，当用户提交网站后，编辑人员会亲自浏览此网站，然后根据一套自定的评判标准甚至编辑人员的主观印象，决定是否接纳该网站，若接纳该网站则同时会给网站分类。而用户完全可以不依靠关键词（Keywords）进行查询，只需通过分类目录即可找到所需要的信息。目前，目录式搜索引擎的代表是雅虎（Yahoo）和搜狐（Sohu），此类搜索引擎由于加入了人工操作，所以搜索到的信息比较准确，但是数据有限、更新速度也比较慢，而且人工成本较高。此类搜索引擎检索出的结果是网站，可看作是网站的分类查询。

2. 全文搜索引擎

全文搜索引擎是针对万维网上所有的网页进行全文检索。它利用下载系统从互联网提取各个网站的信息（以网页文字为主），建立起数据库，然后为搜集到的信息建立索引，用户通过查询系统输入关键词进行搜索，然后检索与用户输入的关键词相匹配的信息，并按照一定的排列顺序将查询结果返回给用户。根据信息来源的不同，全文搜索引擎的信息采集方式大概分为两类：

一类是爬虫定期搜索，即每隔一段时间（如Google一般是28天），搜索引擎会主动派出“爬虫”程序，对设定的IP地址范围内的互联网网站进行检索，若发现新的网站，爬虫会自动提取新网站的信息和网址并加入到搜索引擎的数据库中。

另一类是用户提交网站给搜索引擎，即网站拥有者自己主动向搜索引擎提交网址，搜索引擎会在一定时间内（2天到数月不等）向网站派出“爬虫”程序，扫描网站并将相关信息存入搜索引擎的数据库中，以备用户查询使用。

全文搜索引擎的代表是大名鼎鼎的Google和Baidu。此类搜索引擎的优点是信息量大，更新及时；缺点是返回的结果信息太多，包含很多价值不大的信息，

湖北工业大学硕士学位论文

用户需要在结果中进行筛选。

3. 元搜索引擎

元搜索引擎没有自己的数据库，它是将用户的查询请求同时向多个搜索引擎提交，然后将返回的所有结果进行消重和排序等处理，再作为自己的结果返回给用户。著名的元搜索引擎有WebCrawler、InfoSpace、Dogpile、Vivisimo等，中文元搜索引擎中最具代表性的是搜星搜索引擎。在搜索结果排列方面，有的直接按来源排列结果，如Dogpile；有的则按自定义的规则将结果重新排列，如Vivisimo。此类搜索引擎的优点是返回结果的信息量大；缺点是不能充分使用原搜索引擎的功能，而用户也需要做更多的筛选。

4. 智能搜索引擎

智能搜索引擎是指结合了人工智能等新技术的新一代搜索引擎，其检索方式是基于自然语言的，这样可以根据用户的需求，为用户提供更智能、更人性化的搜索服务。

主题搜索引擎是近几年才兴起的研究热点,它是为了满足特定人群的需要，从而借助于某项技术，在Web上发现并获取与特定主题相关的资源。现在人们对信息查询的要求越来越高，面向主题的搜索引擎也日益受到广大研究者的重视。

1.3 国内外的发展概况

国外的搜索引擎技术发展较早，己经有二十年的历史。Yahoo是最早提供目录式搜索的搜索引擎，根据用户的需要，Yahoo返回相关的分类目录、Web网站等。全文搜索引擎Google的数据库中有多达四十亿个可搜索网页，每天处理的搜索请求多达2亿次，操作界面上提供了30多种语言选择，有英语、日语、中文简繁体、主要欧洲国家语言等。

国内对搜索引擎的研究虽然只有十年的历史，但是己经涌现出一批很优秀的产品。目前国内搜索引擎技术水平最高的是百度，Baidu的搜索功能齐全，包括新闻搜索、MP3搜索、图片搜索、视频搜索、地图搜索等，在中文搜索方面有些地方甚至超越了Google，而且Baidu的更新速度也很快。随着搜索引擎市场价值的不断增加，越来越多的公司加入到搜索引擎的市场中来，他们都开发出了自己的产品，中国搜索、搜狐的搜狗、阿里巴巴的商机搜索等已经陆续面世，同时，搜索引擎技术也已经成为了技术人员关注的热点。

2009年，中国搜索引擎市场报告显示，国内搜索引擎的市场份额如图1.1所示：

湖北工业大学硕士学位论文

图1.1 2009中国搜索引擎市场份额

近年来，随着万维网技术的广泛应用，Web信息资源呈指数级增长，通用搜索引擎已经无法获取网络上的所有资源，而且无法保证对互联网信息的及时更新，尤其是越来越不能满足人们日益增长的对个性化服务的需要。面对这些危机和挑战，为了满足特定人群需要的“主题搜索引擎”应运而生，它的出现引发了搜索引擎研究的又一个浪潮。而主题搜索引擎就是专门为用户提供与某个主题相关的网页资源，在服务上更具专业特色。而且在某个领域或者某个专题上比通用搜索引擎更加准确和有效。

对于主题搜索引擎来说，主题爬虫的爬行技术则是其研究的核心，而爬虫使用哪种爬行策略才能在万维网上获取大量的与主题相关的信息资源就成为了研究的重点。而对于爬虫来说，它不仅要尽可能多地收集与主题相关的页面，同时要最大限度地避免下载无关的页面，这样可以更好地节省硬件资源和网络资源的使用。

目前，国内对于主题爬虫搜索策略的研究主要有三类：基于内容评价的搜索策略，主要有Best-First算法、Fish-Search算法、Shark-Search；基于链接结构评价的搜索策略，主要有PageRank算法和HITS算法；基于未来回报的搜索策略，主要有基于巩固学习的搜索策略。这三类搜索策略的侧重点虽然不同，但是对于搜索引擎技术的发展都起到了重要的作用，而且目前主流的搜索引擎都是使用的这三类搜索策略，例如Google使用的是PageRank算法。

为了促进爬虫搜索技术的发展，基于遗传算法的搜索策略也得到了越来越多

湖北工业大学硕士学位论文

的研究者的关注，尤其是在主题搜索引擎中，遗传算法全局搜索的特性得到了发挥，而且已经有研究者做出了一定的研究成果。

1.4 搜索引擎未来的发展

搜索引擎自诞生以来已经从第一代单纯的文字搜索发展到今天具有文字、图片、音频、视频等信息的搜索。而搜索引擎的最终任务是搜索一个问题，得到一个答案，而不是用户输入一些搜索词，得到一百万个甚至更多的结果。搜索引擎未来主要有移动化、个性化、智能化三大发展趋势：

移动搜索引擎。目前中国有3亿多网民，手机用户有7亿多，手机用户是网民总数的2倍有余，手机的普及率和使用率比个人PC要高很多，但是目前基于手机平台的搜索引擎却还不是很完善，所以在未来所有能上网的多媒体设备，包括汽车、电视机等都应该而且都会具有搜索功能，这将会大大增加用户对搜索这个概念的认知。

个性化搜索引擎。个性化搜索引擎也叫做垂直搜索引擎，这种搜索引擎能够让用户依照自己的个性需求自由地调整搜索的结果，比如用户可以选择时间排序、重要性排序或者地域性排序等排序方式，从而可以快速地找到满意的搜索结果。

智能化搜索引擎。目前的搜索引擎是将搜索出来的网页呈现给用户，而没有真正意义的帮助用户解决问题，用户仍然需要自己寻找答案。但是智能化搜索引擎的目标就是：如果用户搜索“送某某一个什么样的贺卡”，它就能自动地买这个样子的贺卡然后送给某某。

1.5 本文研究内容和创新点

对于主题搜索引擎来说，主题爬虫的搜索策略是核心。目前，主题爬虫搜索策略有很多，比如Google的PageRank算法和李彦宏的超链分析。而基于遗传算法的全局寻优特点，也已经有研究者提出将遗传算法应用在爬虫搜索策略中而且进行了实施。

本文主要研究以下三个问题：

1.遗传算法是模拟生物进化的智能优化算法，具有高效的全局搜索的特点。

[4]

它的特性决定了其在网络爬虫搜索策略中应用的可能性。本文提出了将遗传算

法应用到爬虫搜索策略中，这样可以更好地发挥遗传算法的优势，而且可以更好地解决爬虫全局寻优问题。

2.遗传算法是根据生物进化论优胜劣汰、自然选择、适者生存和物种遗传的

湖北工业大学硕士学位论文

原则，借助选择、交叉、变异等操作，使所要解决的问题在竞争中得以进化，从而求得问题的最优解。本文结合主题搜索的需要在构造初始群、交叉、变异和选择阶段进行了改进，从而提高搜索效率和准确度。

3.为了验证改进后的遗传算法的搜索效率，本文分别用Best-First、HITS和遗传算法三种算法对给定主题进行搜索，经过对实验数据的分析发现改进后的遗传算法对提高爬虫的搜索效率较有成效。

本文的创新点归纳如下：

1.本文的基于遗传算法的搜索策略，在构建初始群时，加入了Aleax排名，综合了网页的权威值、目录值和访问量进行排名，在选取初始种子时更加准确，选取的URL与主题的相关度更高，对于后面寻找相关种子更有帮助。

2.本文在遗传算法的交叉阶段，利用超链的描述信息来预测页面与主题的相似度，这样可以根据相似度的大小有选择地扩展种子集合。

3.本文在遗传算法的变异阶段，有选择地引入了目录型网页，即引入Hub值高的种子，这样可以扩展爬虫的搜索范围，从而达到全局寻优。

1.6 本文结构安排

本文的组织结构如下：

第一章介绍了搜索引擎的发展概况、分类以及本课题的研究背景和目的，重点介绍了本文的研究内容和创新点。

第二章首先介绍了现今主流搜索引擎的体系结构以及网络爬虫在搜索引擎中的位置，然后依次介绍了主题爬虫的工作原理和常见的主题爬虫的搜索策略，最后介绍了本文在爬虫搜索策略的改进中所要使用的遗传算法，以及主题爬虫的设计目标，重点介绍的是主题爬虫的搜索策略。

第三章依次介绍了不重复抓取策略、向量空间模型算法、搜索策略分类和正向最大匹配分词。重点介绍了主题爬虫搜索策略中的BF算法和HITS算法。

第四章提出了将改进后的遗传算法应用在主题爬虫的搜索策略中，并依次详细讲解了改进后的遗传算法涉及到的构造初始群、交叉、变异、选择、终止搜索等步骤。

第五章分别用Best-First算法、HITS算法和改进后的GA算法对给定主题进行搜索，将搜索到的网页根据向量空间模型算法计算其与主题的相似度，然后分别统计三种算法搜索到的相关的网页数，并对实验数据进行分析。

第六章对本课题的研究内容做了总结并提出了以后的研究方向。

湖北工业大学硕士学位论文

第2章相关研究内容

2.1 搜索引擎体系结构

对于搜索引擎来说，不管是通用搜索引擎，还是主题搜索引擎，其结构都很清晰，各部分分工明确，而且体系结构大体相同，不同之处主要在于爬虫给用户提供的网络资源不同。根据功能划分，搜索引擎大体可分为下载、分析、索引和查询四大系统。工作流程如图2.1所示：

用户互联网检索器爬虫索引服务器数据服务器

图2.1 搜索引擎工作流程图

2.1.1 下载系统

网络爬虫(Crawler)，也称为网络蜘蛛(Spider)，是指一组运行在计算机中的程序，在搜索引擎中负责抓取互联网上的网页、图片和文档等资源。

互联网上的网页是不计其数的，网络爬虫是不可能抓取所有的网页，因为在爬虫抓取网页的同时，Web的规模也在不断增大，所以一个好的爬虫是指在短时

[5]

间内能够抓取更多的网页。网络爬虫的运行过程如图2.2所示：

湖北工业大学硕士学位论文

开始URL列表IP地址缓存 URL解析DNS服务器抓取已抓取网页新URL列表

图2.2 爬虫运行过程图

在爬虫开始抓取网页的时候，需要给爬虫输送一个初始URL列表，此列表中的URL地址便是爬虫的起始位置，爬虫从抓取这些URL对应的页面中包含的链接开始，不断地发现新的URL,然后再根据某种策略抓取这些新发现的URL,如此重复下去，直至获取所有的URL。一般的爬虫都会建立自己的DNS缓冲，建立DNS缓冲可以加快URL解析成IP地址的速度。而在网络爬虫爬行过程中最重要的就是爬虫不重复抓取网页，即判断网页是否已经被抓取，这样可以减少后续的分析、索引等工作。

下载系统相当于搜索器的功能，通过总体调度分布在互联网上各个不同区域的并行爬虫，然后对整个互联网的信息进行严密的梳理并获取相关的资源，并把搜集到的信息下载到本地以便后期进行数据处理。并行爬虫几乎遍历了整个互联网，因此所获得的信息是非常全面的，它保证了搜索引擎对信息检索的全面性。

2.1.2 分析系统

分析系统在搜索引擎的体系结构中承担了网页结构化、网页消重、文本分词和PageRank计算4个基本任务。分析系统结构如图2.3所示：

湖北工业大学硕士学位论文

图2.3 分析系统结构图

分析系统的工作主要有以下几个步骤：

1.对爬虫下载的网页建立标签树并从网页中抽取有价值的属性，对网页结构化，即把原始的网页转换成一个网页对象。在信息抽取过程中所获取的网页链接信息会发给PageRank计算服务器，对于网页的PageRank计算非常耗时，一般采用离线计算方式，计算的结果则形成一个PageRank列表。

2.对结构化之后的网页消重，包括丢弃冗余的页面、对于相似的或者相同的页面此时仅保留一个然后传给分词模块。

3.文本分词则是通过分词算法把正文分成以词汇为单位的集合。 4.将文本分词的结果发给索引模块。

2.1.3 索引系统

搜索引擎需要处理的信息量是巨大的，比如Google就需要在几十亿的文档中进行检索，但是Google基本上都可以在几秒钟内返回结果，之所以能够如此快速，就是因为有索引的存在，而在搜索引擎中索引一般是以倒排表的形式存在。

索引系统就是将普通文档进行分词处理，然后以正排表的形式描述文档，再将此形式进行反转，在反转过程中可以统计关键词Term在所有文档中出现的总次数，最后形成倒排表。

2.1.4 查询系统

查询系统负责对用户提交的查询请求进行分析，然后从数据库中检索出相关的网页并根据设定的排序方法将网页排序，再把查询结果返回给用户。而在查询

湖北工业大学硕士学位论文

系统中使用缓存则是为了提高检索的速度和效率，因为对检索频率较高的信息无需每次都进行类似的计算，而只需把最终的结果放在缓存中即可。而对于第一次进行的检索必须进行相似度比较，从而确定用户需要的信息且生成结果页面。

2.2 网络爬虫的工作原理

从目前公布的数据来看，容量最大的搜索引擎也只是抓取了整个万维网网页总量的百分之四十左右，所以对于搜索引擎来说，要抓取万维网上所有的网页几乎是不可能的。一方面是因为抓取技术的瓶颈，爬虫无法访问到Web上的所有网页；另一方面是因为存储技术和处理技术的问题。所以对于部分搜索引擎来说，他们只是抓取相对比较重要的页面和链接，这在一定程度上缓和了技术瓶颈所带来的问题，同时也不会影响到用户的使用，主题搜索引擎便是属于此类。

本文在2.1节中提到，传统搜索引擎和主题搜索引擎的主要区别在于爬虫给用户提供的网络资源不同，而对于爬虫来说，传统爬虫和主题爬虫的区别就在于搜索过程的不同。传统爬虫与主题爬虫工作流程对比如图2.4所示：

开始开始初始URL获取网页初始URL获取网页抓取新的URL放入待处理URL队列否满足停止条件抓取新的URL放入待处理URL队列评价网页及URL根据搜索策略选择URL是结束满足停止条件是结束否(a)(b)图2.4 传统爬虫与主题爬虫工作流程对比图

传统爬虫的工作流程如图(a)所示：传统爬虫从一个预先定义好的初始URL集合开始，将这些URL按顺序放入一个待处理的URL队列中，然后从此队列中顺

湖北工业大学硕士学位论文

序取出URL并获取URL所对应的页面，再分析并提取已获取的页面中包含的新的URL，并将新获取的URL顺序放入到待处理的URL队列中，重复上述过程，直至满足停止条件时爬虫结束搜索。

主题爬虫的工作流程如图(b)所示：主题爬虫从一个预先定义好的初始URL集合开始，将这些URL按顺序放入一个待处理的URL队列中，然后根据一定的网页分析算法对网页和URL进行评价，从而剔除掉与主题无关的链接，保留相关的链接并将其放入到等待抓取的URL队列中，然后根据一定的搜索策略从URL队列中选择下一步要抓取的网页。重复上述过程，直至满足停止条件时爬虫结束搜索。

2.3 网络爬虫的搜索策略

爬虫在网络上爬行的时候，若将Web上的网页集合看成是一个有向图，爬虫从给定的起始URL开始，沿着网页之间的链接，按照一定的策略进行爬行，则可以抓取到需要的页面[6]。目前，爬虫抓取页面的策略大概可以分为深度优先、广度优先、启发式搜索和基于自动分类的搜索四种。

1.深度优先算法。该算法是指爬虫从选定的某个超链接开始，沿着一条线路，按照页面间的链接顺序访问下去，直至这条线路的叶子节点，即到达某个不包含任何超链接的HTML文件时为止，访问完这条线路之后再转入下一个设定的起始页，继续访问此起始页中所包含的链接直至叶子结点。此算法的优点是网络爬虫的设计比较简单。

2.广度优先算法。此算法是指网络爬虫在抓取过程中，先完成当前层次的搜索后，才进行下一层次的搜索。此种搜索方法是实现传统爬虫的最佳方法，因为该算法的设计和实现相对简单，且能够避免爬虫陷进一个无穷尽的深层分支中去，这样可以让爬虫进行并行处理，从而提高网页抓取速度。此方法的缺点在于，抓取的网页越来越多，大量的无关网页将被下载，这样会影响算法的效率。

3.启发式搜索算法。此算法源于人工智能，先通过在线获得的知识评价待访问链接的价值，借此推断信息资源的分布情况，再按照一定的原则选择价值最大的链接进行下一步的搜索，找出到达目标节点的最佳路径，删除不好节点，保留好的节点。此算法主要用于主题爬虫的搜索策略，但此方法的缺点在于，在主题爬虫抓取的路径上有很多相关网页可能被忽略，因为这种搜索方法是一种局部最优搜索算法，因此需要结合实际的应用进行改进从而跳出局部最优点。

4.基于自动分类的搜索算法。此算法是把网络爬虫看成Agent，使其具有一定的自主性，可以学习互联网上的知识并具备一定的经验信息，然后可以计算网页是否属于所需要的主题类型，从而得到正确的下载方向。

湖北工业大学硕士学位论文

总之，如何在合理的时间限度内，通过消耗较少的网络资源、存储资源和计算资源而获得更多的与主题相关的页面是主题爬虫追求的最终目标。

2.4 神经网络与遗传算法

人工神经网络（Artificial Neural Networks,ANN），是一种模仿动物的神经网络行为特征，并进行分布式并行信息处理的算法数学模型。它是依靠系统的复杂程度，通过调整网络内部大量节点之间的相互连接的关系，从而达到信息处理的目的。

人工神经网络是一个能够学习、能够总结归纳的系统，通过对局部情况的对照比较(这些比较是由不同情况下的自动学习和需要实际进行解决的问题的复杂性所决定的),从而推理产生一个可以自动识别的系统。

近年，人工神经网络正向模拟人类认知的道路上深入发展，与模糊系统、遗传算法、进化机制等结合，形成了计算智能，成为人工智能的一个重要方向。

早在20世纪60年代，美国Holland教授最先提出了遗传算法，80年代时，Goldberg对遗传算法进行了归纳总结，形成了算法的基本步骤。

遗传算法(Genetic Algorithms，GA)是一种模拟生物进化的智能优化算法，根据生物进化论优胜劣汰、自然选择、适者生存和物种遗传的原则，借助交叉、变异、选择等操作，使所要解决的问题在竞争中得以进化，从而求得问题的最优解。遗传算法的特点是一种高效的全局搜索的方法。

遗传算法的特性决定了其在网络爬虫搜索策略中应用的可能性,本文提出的基于遗传算法的主题信息搜索策略，即将待检索的问题提交给通用搜索引擎，对其返回的结果集进行处理，选择一定数目的URL作为初始群体；通过交叉操作，提取初始群体中URL对应页面包含的所有超链，产生出大量新的个体，再对所有超链进行相似度预测，选出相关度高的种子作为交叉结果；通过变异操作，引入目录型网页，扩大搜索范围；通过选择操作，对遗传之后的结果进行处理，选出相关度高的个体作为新一代的种子进入新一轮的遗传；通过爬虫终止搜索条件，来结束爬虫的搜索。

2.5 主题爬虫的设计目标

主题爬虫在互联网中漫游，从中搜集与主题相关的网络资源，再通过索引器的索引由检索器排序输出给用户，以此完成主题搜索引擎的整个过程。对于主题搜索引擎来说，主题爬虫的性能直接决定了整个搜索引擎的性能。

主题爬虫的基本工作流程是根据预先给定的主题，分析Web中的超链接和己

湖北工业大学硕士学位论文

下载的页面内容，预测出下一个要爬行的URL，以此保证尽可能多地下载与主题相关的页面，也尽可能少地下载与主题无关的页面，从而提高主题爬虫的爬行效率和准确率。设计主题爬虫时主要考虑以下四个方面:

1.下载高质量的网页。随着Web上网页数量的极速增长，爬虫几乎不可能下载所有的页面，要想满足用户的需求，就必须尽量提高所下载的页面的质量，以此保证所下载的页面的可用价值度。如何才能为用户下载高质量的网页是设计主题爬虫时首先需要考虑的问题。

2.判断己下载的网页与主题的相关性。将爬虫抓取到的网页下载到本地，通过提取页面中的文字信息，包括对于链接的文字说明和网页内容，充分利用页面中的信息，根据某种策略来计算已经下载的网页与主题的相关性。

3.设定待爬行URL的访问次序。主题搜索引擎是以尽可能多地从海量数据中搜集与主题相关的页面为目标，爬虫在爬行的时候按照设定的方法(深度优先遍历、广度优先遍历等)下载页面，尽量扩大搜索范围，而对于主题爬虫来说，在爬行的时候就要优先访问与主题相关的页面，那么如何管理待爬行的URL队列才能使每次爬行都从相关度最高的页面开始就是设计爬虫时必须考虑的问题。

4.尽量降低爬虫爬行的网站的负担。爬虫在爬行的过程中，需要访问网站的服务器，这样就会占用网站服务器的计算机资源，比如CPU、磁盘空间等，同时也会占用网络带宽，增加网络的负担。那么设计爬虫时就应该将这些资源消耗降到最低，否则网站管理员会屏蔽爬虫。

2.6 本章小结

本章首先以Google公司的搜索引擎为蓝本介绍了现今主流搜索引擎的体系结构，主要讲解了网络爬虫在搜索引擎中的位置以及作用，然后介绍了爬虫的工作原理以及爬虫的搜索策略。

本文研究的重点是将改进后的遗传算法应用在爬虫的搜索策略中，所以本章介绍了遗传算法的来源、优缺点以及它的应用范围，重点讲解了主题爬虫的设计目标和设计爬虫时必须要注意的问题。

湖北工业大学硕士学位论文

第3章主题爬虫的关键技术

3.1 不重复抓取网页策略

对于主题爬虫来说，在爬虫爬行的过程中，会遇到很多一样的URL种子，或者有很多相似的网页，此时，如果重复抓取相同网页或者相似网页，则会占用大量的CPU资源和带宽，也会对某个网站重复进行分词和相似度比较，这样会严重影响效率，所以爬虫爬行过程中必须避免重复抓取相同和相似的网页。

不重复抓取网页的关键在于爬虫能够记住历史，只有记住过去已经抓取的网页才能不重复，而需要记住历史的程序的设计相对是比较复杂的。而爬虫记录历史的方式是哈希表，对于所有的网页，每一个网页都对应有一个槽位，如果某网页在过去的某个时刻被抓取了，则此网页对应的槽位上的值就置为1，反之置为0。但是每一个网页具体映射到哪一个槽位，则由哈希函数来决定。这就是所谓的MD5签名算法。

MD5的全称是Message-Digest Algorithm 5(信息-摘要算法)，在1992年，Ronald L.Rivest提出了MD5算法的原理，鉴于这种算法的公开性和安全性，在90年代被广泛使用。MD5签名是一个哈希函数，可以将任意长度的数据流转换成一个固定长度的数字(一般为4个整型，即128位)，而这个数字称为“数据流的签名”或“指纹”，而且数据流中的一个微小的变化都会导致签名值发生变化。

标准MD5签名的整数空间很大，一般为128位，那么这128位整数就可以表达2的128次方个完全不同的数，这是十分巨大的，但是实际分配的哈希表空间却不能这么大，现在的计算机一般是64位处理器，除去操作系统占用的内存，实际上可以提供给搜索引擎的内存就很有限了。所以在实际应用中，是将MD5的签名值进行模运算之后再映射到实际的哈希表中，那实际的哈希函数就是MD5%n（%表示取模运算，n代表哈希表的长度），在搜索引擎中，实际的哈希函数就是URL%n（%表示取模运算，n代表哈希表的长度），即一个URL被映射到大小为n的哈希表的某个槽位上。例如图3.1所示：

湖北工业大学硕士学位论文

www.sohu.com www.sohu.com www.sina.com MD5签名函数0 1 0 0 0 0 1 0 图3.1 哈希函数示例图

假设爬虫抓取顺序为www.sohu.com、www.sina.com和www.sohu.com，首先抓取www.sohu.com时为该URL签名得到的结果为2，查询数组的第2个槽位，发现其结果为0(初始状态时所有槽位上的值都置为0)，即此URL尚未被抓取，然后将数组的第2个槽位上的值置为1，表示已经被访问过。然后继续抓取www.sina.com，计算该URL签名得到的结果为7，查询数组的第7个槽位，发现其结果为0，即此URL尚未被抓取，然后把数组的第7个槽位上的值置为1，之后再重复抓取www.sohu.com，而MD5签名函数的特性就决定了一个自变量只能惟一对应一个因变量，所以计算www.sohu.com的签名得到的结果仍然是2，然后查询数组的第2个槽位，发现该槽位上的值为1，即此URL已经被抓取过了，此时就不再重复抓取www.sohu.com，直接跳过抓取下一个URL。这样就可以很好地避免重复抓取网页了。

MD5算法在爬虫搜索中应用的具体过程如下所示：

首先将网页的URL字符串数字化，即对于任何一个URL在哈希函数的映射下，任意一个字符串都能惟一地对应一个整数，这个整数称之为MD5签名值。然后将MD5的签名值进行模运算之后再映射到实际的哈希表中，即实际的哈希函数就是URL%n（%表示取模运算，n代表哈希表的长度），此时一个URL就被映射到大小为n的哈希表的某个槽位上。根据MD5的特性，任意一个URL对应的都是惟一的槽位。抓取某一个URL之前，查询一下对应的槽位上的值，如果为0，则抓取此URL，而且把对应槽位上的值置为1；如果为1，则说明此URL已经被抓取了，则直接跳过此URL抓取下一个。

3.2 向量空间模型算法

向量空间模型(Vector Space Model，简称VSM)是一个应用于信息过滤、信息撷取、索引以及评估相关性的代数模型[7]。它是Salton.G教授在1975年提出的经典模型，在信息检索中得到了广泛应用。

湖北工业大学硕士学位论文

VSM模型基于这样一个假设：组成文档的词条出现的顺序是无关紧要的，它们对于文档的主题所起的作用是相互独立的，因此可以把文档看成一系列无序词条的集合。

VSM的基本思想是这样的：把文档di看成是由一组词条T(Tl，T2，…,Tn)构成的，对于每一个词条都可以根据它在文档中的重要程度赋予一定的权值wi，若将T1,T2,…,Tn看作一个n维坐标系，w1, w2,…,wn为对应的坐标值，则每一篇文档di都可看作向量空间中由一组词条矢量构成的一个点。如图3.2所示：

图3.2 VSM模型示意图

在VSM模型中，设D是一个包含m篇文档的文档集合，则 D={d1,L,diL,dm},i=1,2,Lm

则集合中的每篇文档di都被表示成如下形式的向量：

di=(wi1,Lwij,Lwin),i=1,2,Lm;j=1,2,Ln

其中，wij表示第j个特征项Tj在文档di中的权值。权值的计算有以下三种方法：

⎧1(第j个特征项属于文档di)

1、wij=⎨

0(第j个特征项不属于文档d)i⎩

⎧⎪tij(第j个特征项在文档di中出现的次数)

2、wij=⎨

⎪⎩0(第j个特征项不属于文档di)

3、TF/IDF（term frequency–inverse document frequency）词频统计方法。此方法基于这样一个假设：在真实语料中，出现频率较高的词条带有较少的信息，而出现频率较少的词条带有较多的信息。若wij表示权值，第j个特征项Tj在文档di中的TF/IDF值通过公式(1)计算：

(1)

其中，tfi为词条Tj在文档中出现的次数；dfi表示整个文档集D中所包含的

湖北工业大学硕士学位论文

词条Tj的文档数，称之为文档频率；N表示统计语料中的文档总数。

爬虫搜索网页时，判断网页与主题是否相似就需要计算网页与主题的相似度，基于向量空间模型的简单向量距离算法的基本思想就是计算VSM模型示意图中两个向量之间的夹角余弦值，余弦值通过公式(2)计算公式:

(2)

其中，di为待分类的文本特征向量，dj为第j类的中心向量，M为特征向量的维数，wi,k和wj,k分别为向量的第k维在文本di和dj中对应的权值,wi,j采用上面的公式(1)计算。

3.3 主题爬虫的搜索策略分类

3.3.1 基于内容评价的搜索策略

基于内容评价的搜索策略是以传统信息检索模型--向量空间模型为理论基础，根据主题（如关键词、主题相关文档等）与文本内容（包括网页内容、链接文本）的相似度来评价链接价值的高低，并以此来决定其搜索策略。链接文本是指对于链接的说明文字和链接URL上的文字信息。此类搜索策略的代表有Best-First算法、Fish-Search算法、Shark-Search算法，其优点是具有较好的理论基础且计算简单，但忽略了Web页面之间的链接关系，不能很好地发挥网页链接的作用。下面分别介绍:

1、Best-First算法

Best First算法是由Cho和Hersovici等人在1998年提出的[8]，后人在此基础上做了很多改进。其基本思想是：首先利用通用搜索引擎获取初始URL队列，然后根据某种评价选择策略选择出优先级高的URL进行爬行，而URL优先级是由URL链接的文字说明内容与设定的主题的相关度来决定的，此处相关度的计算使用的是VSM算法。计算出的相关度值高的，URL链接对应的网页的优先级就高，则待爬行队列中URL的优先级也高。反之，相关度低的网页，URL的优先级也低。若待爬行队列的缓冲区满了，则将优先级低的URL从队列中移出。

Best First算法的流程如下：首先建立两个队列url_queue和crawled_queue,分别存放待爬行URL和已经爬行的URL。然后把利用通用搜索引擎获取的初始URL

湖北工业大学硕士学位论文

放入url_queue中，通过VSM算法计算出所有URL对应的页面与主题的相关度并根据相关度大小对URL进行降序排序。选择相关度最高的URL开始爬行，且将该URL放入crawled_queue队列中，然后下载URL对应的页面并对此页面中包含的所有链接进行预测，即通过对URL的锚文本和链接信息计算与主题的相似度，从而根据计算出的相似度值将该页面中提取出的URL插入到url_queue中。重复上述操作，直至爬虫抓取的网页数超过最大页面数或者url_queue中无URL。

此种算法的优点是计算量较小，但是在预测URL与主题的相关度时，只是利用URL的锚文本和链接信息来计算相似度的，导致效果不佳。而且容易造成搜索效果局部最优，不能很好地全局搜索。

Best-First算法的伪代码如下：

Best_First_Search(Starting_URLs,topic) {

enqueue(url_queue,Starting_URLs); int numVisited=0;

While(numVisitedenqueue(crawled_queue,url); url_list=Extract_link(page); sim_score=sim(topic,page);

enqueue(buffered_page,page,sim_scroe); For Each u In url_list{ }}

If(u not in url_queue and u not in crawled_queue) }

Enqueue(url_queue,sim_score); Dequeue_bottom_links(url_queue); If(number(url_queue)>Max_Buffer)

Reorder_queue(url_queue);

2、Fish-Search算法

[9]

Fish Search算法是De Bra在1994年提出的，该算法视互联网为一个有

向图，网页为节点，链接为边，网络爬虫比喻成海里的一群鱼，当鱼发现“食物” （与主题相关的信息）时，鱼就可以继续生存也就可以继续繁殖，而繁殖的数量

湖北工业大学硕士学位论文

就取决于寻找到的食物的个数，当食物规则地存在于几个区域时，鱼群也规则地分布在几个相应的区域；当某个区域没有食物时，此处的鱼就会死掉。

此算法的关键是当爬虫抓取到一个网页时，抽取出此网页包含的所有URL，把这些URL对应的页面称之为“孩子”页面。如果此页面与主题相关，则继续对孩子页面进行深度搜索，而且搜索深度为预先设定的值，搜索深度不会发生变化。反之，如果此页面与主题无关，仍然对孩子页面进行搜索，但是搜索深度减1，当此条路径上的深度减为0时，这个方向上的搜索就终止了。

3、Shark-Search算法

Shark Search算法是在Fish Search算法的基础上进行了修改，由Michael Hersovici等人在1998年提出来的了Fish Search算法的局限性。

[10]-[13]

。该算法比Fish Search算法还有效，

通过更好地估计在被访问分析前的相邻页面的相关性，Shark Search算法克服

3.3.2 基于链接结构评价的搜索策略

基于链接结构评价的搜索策略是通过对Web页面之间相互引用关系的分析来确定链接的重要性，从而决定链接访问顺序。一般认为有较多入链或出链的页面具有较高的价值。

超链接做为互联网的重要技术之一，它不仅为用户提供了方便快捷的获取信息的通道，也在一定程度上反应了互联网的结构，即网页间的一些关系——包含、从属、引用等，而这些关系不仅是网络结构的简单体现，其中也包含了很多隐藏的有用信息。研究发现，利用页面间的链接结构可以更多更好地挖掘用户需要的信息，那么在信息检索中就可以明显地提高检索效率。

基于上述状况，很多研究者开始对页面间的超链接结构进行分析并提出了一些基于超链接的算法。目前，超链接分析算法已经被应用在搜索引擎的文档排序、网络爬虫的爬行策略等领域。现今被公认为较为成熟并在实际中得到广泛应用的超链接分析算法主要有：以Google创始人之一拉里·佩奇（Larry Page）命名的PageRank算法和Kleinberg提出的HITS算法。此类算法的优点是考虑了网页间的链接结构，但忽略了页面本身与主题的相关性，易出现“主题漂移”问题。下面分别介绍两种算法：

1、PageRank算法

PageRank算法最初用于搜索引擎信息检索中对查询结果的排序过程，近年来被应用于定题爬虫对链接重要性的评价采用如下迭代公式(3)计算：

[14][15]

。PageRank算法中，页面的价值

通常用页面的PageRank值表示，若设页面p的PageRank值为PR(p)，则PR(p)

湖北工业大学硕士学位论文

(3)

其中，T为计算中的页面总量，γ<1是阻尼常数因子，in(p)为所有指向p的页面的集合，out(r)为页面r出链的集合。基于PageRank算法的定题爬虫在搜索过程中，通过计算每个已访问页面的PageRank值来确定页面的价值，并优先选择PageRank值大的页面中的链接进行访问。

PageRank算法是针对万维网的整体分析，通过模拟用户在万维网上的随机浏览计算每一个网页的PageRank值,而网页PageRank值的计算是采用离线的机制，即相似度的计算不是针对查询的，所有进行排序的网页是预先下载的。也就是说当用户输入查询请求时，服务器会快速地产生响应，搜索引擎不会为查询过程产生时间上的额外代价。但是，如果用户是基于某个特定主题的查询，那么在返回的结果中一些与主题无关但是权重较高的网页就可能会排在比较靠前的位置。

2、HITS算法

Comell大学的J.Kleinberg提出的HITS算法

[16]-[18]

，把网页分为：权威型网页

(即Authority网页)和目录型网页(即Hub网页)。权威型网页和目录型网页是根据网络拓扑结构的“蝴蝶结”理论提出来的[19][20]。网络的拓扑结构如图3.3所示：

图3.3 网络拓扑结构图

从上图可以看出，互联网上的网页分为以下4种类型，各约占1/4。

湖北工业大学硕士学位论文

(1)蝴蝶结的中部(SCC)

这部分网页彼此相连，任意去掉有限个网页不会影响其连通度。若选择此部分网页为起始点，然后采用正向遍历的方法，则大概可以遍历全部网页的3/4。若采用反向遍历也可以遍历大致同样数量的网页。

(2)蝴蝶结的左部(IN)

此部分的网页指向中心部分(SCC)，称为“目录型网页”(hub page),即通常所说的导航网页。若选择此部分网页为起始点，然后采用正向遍历的方法，则大概可以遍历全部网页的3/4。若采用反向遍历则只能遍历很有限的网页，其所占比例可以忽略不计。

(3)蝴蝶结的右部(OUT)

此部分的网页被中心部分指向，称为“权威性网页”(authority page)。此部分网页被引用次数较多，即大部分网页对其“认可度”较高。若选择此部分网页为起始点，然后采用正向遍历的方法，则只能遍历有限的网页。若采用反向遍历的方法则大概可以遍历全部网页的3/4。

(4)蝴蝶结的须脚(Tendrils)

此部分网页表现为从左部链出到其他网页，或者从其他网页链入右部，或者从左部直接链入右部，还有少部分与中部、左部和右部都没有链接(DISC)的网页。若选择此部分为起始点，则无论采用正向遍历还是反向遍历都只能遍历到很有限的网页。

根据蝴蝶结理论，J.Kleinberg在HITS算法中提出，目录型网页是提供指向权威网页链接集合的Web网页，它本身可能并不重要，或者说没有几个网页指向它，但是Hub网页提供了指向就某个主题而言最为重要的站点的链接集合。权威型网页是有许多好的网页指向的Web网页，这种网页的反向链接数很多，而正向链接数相对较少，通常认为Authority网页的内容具有较强的主题相关度。Authority网页和Hub网页的结构

[21]-[23]

分别如图3.4和图3.5所示：

湖北工业大学硕士学位论文

Authority1Authority2HubAuthority3Authority4 图3.4 Hub网页

Hub1Hub2Hub3AuthorityHub4Hub5 图3.5 Authority网页

一般来说，Authority页面常常是那些非常著名的、被人们普遍认可的权威网页，例如中英文网站中的主流新闻网站(sina，CNN，NYTimes)、著名的分类目录网站、行业领先者网站(Macromedia，HP，Nike)等；而Hub页面多是一般的普通网页，它提供了指向那些权威页面的链接集合，Hub页面本身常常没有几个链接指向它们，但是Hub页面却提供了指向某个权威结点的链接。通常，好的Hub会指向许多好的Authority页面，好的Authority页面一般会被许多好的Hub所指向。

HITS算法的具体流程

[24][25]

如下所示：对于主题爬虫来说，首先利用通用搜

索引擎获取初始URL，记为集合M，则集合M中包含的URL对应的页面均是与主题相关的，而且有很多权威型网页。然后对集合M进行扩展，扩展分为两

湖北工业大学硕士学位论文

部分，第一部分是根据网页出链扩展，即对集合M中所有页面包含的超链提取出来；第二部分是根据网页入链扩展，即把所有的链接了集合M中的URL的页面对应的URL提取出来。把扩展之后的所有URL记为集合N。集合N即为初始种子集合，然后开始计算网页的Authority和Hub值。

对于网页p，将网页p的Authority值记为ap，Hub值记为hp，为所有待搜索网页赋初值：ap(0)←1，hp(0)←1。再通过以下迭代公式(4)(5)对ap和hp进行反复修正，直至ap和hp的结果收敛：

atp+1=

p′→p

∑

(t)hq

(4)

t+1p

p′→q

∑a

ap(t+1)q

(5)

而每次迭代之后需要对ap和hp利用如下公式(6)(7)进行规范化处理以保证其不变性：

ap=

∑q∈T⎡⎣aq⎤⎦2 (6)

hp=

hp∑⎡⎣hq∈Tq⎤⎦2 (7)

J.Kleinberg证明了在经过足够多的迭代之后，ap和hp的值会趋向于一个稳定的结果，即ap和hp的结果收敛。

当ap和hp的结果收敛时，网页的Authority和Hub值也就趋向于一个稳定的结果，此时对集合N中所有URL根据Authority值的大小进行降序排列，选择Authority值大的URL作为新的种子，再重复上述步骤，直至抓取不到新的种子或者获取的页面数达到了用户设定的最大值，爬虫就结束搜索。对已经抓取的URL按照Authority值的大小进行降序排列，返回Authority值大的作为权威型网页；对已经抓取的URL按照Hub值的大小进行降序排列，返回Hub值大的作为目录型网页。

湖北工业大学硕士学位论文

3.3.3 基于未来回报的搜索策略

近年来对Web信息资源分布特点的研究表明，web上信息资源的分布具有某种程度“相似性”，如同种类型站点在构建方式上存在一定相似性；同一主题的相关页面在组织方式也存在着一定相似性。因此，有些研究者考虑利用这种相似性，先对主题爬虫进行一些训练，使其具备一些“经验信息”而这些经验信息通常用于预测较远的回报，此类搜索策略的代表有基于巩固学习的搜索策略[26]-[28]。

1、基于巩固学习的搜索策略

基于巩固学习（reinforcement learning）的搜索策略在预测远期回报方面具有优势，此策略是把定题爬虫看作代理体，爬虫面对的web环境代表状态，爬虫对链接的访问代表行动。在搜索过程中，经过对若干无关页面的访问之后才能获得与主题相关的页面称为未来回报（或远期回报），而对未来回报的预测值称为未来回报价值。在巩固学习模型中，用Q价值表示未来回报价值，这种方法的核心是学习如何计算链接的Q价值。

为此，搜索过程分为训练和搜索两个阶段。训练阶段利用巩固学习算法来计算每个链接的Q价值，且按照价值大小将链接分类，再根据类中链接的文本信息训练一个Navie Bayes分类器；搜索阶段面对价值未知的链接，则根据链接文本用Navie Bayes分类器计算链接落在每一类中的概率，并以此概率为权值计算链接的综合Q价值。

基于巩固学习的搜索策略，就是通过训练学习可以得到哪些链接文本具有较高的Q价值，反过来，在搜索时又会根据链接文本的Q价值估算出链接的价值。由于Q价值反映的是对未来回报的预测值，所以，对于此类主题爬虫，即使搜索的页面与主题不相关时它也可以根据未来回报价值确定正确的搜索方向。

3.4 正向最大匹配分词

对于搜索引擎来说，分析系统中抽取信息之后，进行网页查重，然后对正文进行分词，而分词的方法很多，基本上分为两类：第一类是基于字符串匹配的分词，主要有正向最大匹配分词(MM法)、逆向最大匹配分词(RMM法)和最少切分等方法。第二类基于统计的分词方法。本课题采用的是正向匹配分词[29]-[31]。

基于字符串匹配的分词是指事先准备一个分词词典，分词词典中大量的词，一般词典中词的数量在十几万到几十万不等。然后将待分词的句子按照一定的扫描规则与词典中的词进行匹配。如果能匹配上，则将这个词分出来。

正向最大匹配算法是最早提出的自动分词方法，而最大匹配是要求对每一句

湖北工业大学硕士学位论文

话分词之后，词汇的总量最少。例如：“我们是中华人民共和国的公民”，对于这句话，其中包含的词有：我们、是、中华、人民、共和国、的、公民，一共有7个词，但是为了实现最大匹配，我们就将这句话切分成：我们/是/中华人民共和国/的/公民，一共是5个词。所以我们选择第二种分词结果。

正向最大匹配分词的基本思想是：首先将句子读入，然后对句子进行字典的匹配，如果匹配失败则从句子末尾删除一个字，再进行字典的匹配，一直这样匹配下去，直至匹配上字典的某个单词。然后对句子的剩余部分依照上述步骤重复进行，直至句子全部分解成词汇。分词过程如图3.6所示：

开始读入一个句子读入词典文件待切分的临时变量匹配失败，句子减一个字，继续匹配匹配匹配成功分词结果句子减为零个字结束词典图3.6 分词过程图

为了让用户快速、准确的搜索定位到自己所需要的资源，对中文分词技术的研究也在逐渐深入。本文选用是中科院中文分词器ICTCLAS2009版。

3.5 本章小结

在爬虫的设计中不可避免要对超链接进行分析，目前主流的超链接分析有PageRank算法和HITS算法，两种算法各有特点并且都得到了广泛的应用。其次在搜索引擎中文本分词和文本相似度计算都是非常重要的步骤。

本章介绍了向量空间模型的原理、特点和计算方法，主题爬虫的搜索策略分类以及正向最大匹配分词技术。重点介绍了VSM、Best-First、HITS算法。

湖北工业大学硕士学位论文

第4章基于遗传算法的主题爬虫的实现

4.1 构造初始群

主题搜索是面向特定主题的，则初始种子集应该来自该主题领域，否则爬虫无法展开爬行工作。具体做法是将待检索的问题提交给通用搜索引擎，对其返回的结果集进行处理，选择一定数目的URL组成初始群体[32]-[34]。

1、初始种子集合

本文选用搜索引擎Google，将其返回的结果集的前n个结果页面对应的URL组成集合S1, 再对S1进行如下扩展：

(1)根据集合S1中网页的入链进行扩展。将集合S1中网页的所有入链对应的URL组成集合S2。根据网页的反向链接进行扩展，扩大初始URL的范围，因为一般链接到这部分网页的网页自身与主题相关度比较高。

(2)集合S3=S1+ S2。

扩展之后获得的集合S3如图4.1所示：

图4.1 种子集合

2、网页去重

根据互联网的链接结果可以知道，集合S3中会有很多重复的URL，而对于爬虫来说，必须避免重复抓取这些相同的URL所对应的网页，只有这样才能避免不必要的重复劳动，才可以提高搜索效率[35]。

在本课题中，选择3.1节的不重复抓取策略，避免重复抓取URL，根据MD5签名算法，对于所有的网页，每一个网页都对应有一个槽位，若某网页在过去的某个时刻被抓取了，则此网页对应的槽位上的值就置为1，反之为0，初始状态时所有槽位上的值都置为0。对于集合S3，进行URL去重之后得到的集合记为S，此时集合S中无重复的URL，然后再进行下一步计算。

湖北工业大学硕士学位论文

3、网页排名

考虑到用户的实际使用，网页的排名仅仅依靠Authority和Hub值是不够准确的，因为有很多官方的、专业的、知名的网站是不需要用户进行搜索的，也就是说用户基本上都能记得，这一部分网站基本上就不需要其他的网站进行链接，比如baidu、google、csdn等，而这些网站的Authority和Hub值都不是最高，如果只按照Authority和Hub值进行排名，这部分网站在返回的结果中位置不会太靠前，所以需要对集合S中所有网站的月访问量排名进行统计，然后综合访问量和Authority和Hub值进行排名。

本文有关网站访问量的排名是通过网站http://cn.alexa.com/(Alexa中文官方网)查询得来。Alexa是一家专门发布网站世界排名的、以搜索引擎起家的、创建于1996年4月（美国）的网站，目的是让互联网用户在分享虚拟世界资源的同时，更多地参与互联网资源的组织。Alexa每天在网上搜集的信息超过1,000GB，不仅给出多达几十亿的网址链接，而且为其中的每一个网站进行了排名，目前，Alexa是拥有URL数量最庞大、排名信息发布最详尽的网站。Alexa网站上的世界排名主要分为两种

[36]-[38]

：综合排名和分类排名。综合排名也叫绝对排名，即

某个网站在所有网站中的名次，Alexa每三个月公布一次新的网站综合排名，此排名的依据是用户链接数（Users Reach）和页面浏览数（Page Views）三个月累积的几何平均值。分类排名，一是按主题分类，比如新闻、购物、娱乐、体育等，Alexa给出某个网站在同一类网站中的名次。二是按语言分类，目前共有20种语言，比如英文网站、中文网站[Chinese (simpl) 和Chinese (trad) ]、日语网站等，Alexa给出某个网站在同一类语言网站中的名次。分类排名如图4.2所示：

图4.2 中文网站排名图

事实上，Alexa 排名是根据对用户下载并安装了 Alexa Tools Bar 嵌入到 IE、

湖北工业大学硕士学位论文

FireFox等浏览器，从而监控其访问的网站数据进行统计的，因此，其排名数据并不具有绝对的权威性。但由于其提供了包括综合排名、到访量排名、页面访问量排名等多个评价指标信息，且目前还没有更科学、更合理的评价参考，所以本文选用的是Alexa排名。

如果想要查询某个网站的排名，则通过http://cn.alexa.com/siteinfo输入网站域名，比如输入tudou.com，则查询结果如图4.3所示：

图4.3 网站流量图

4、构建初始群

根据3.3.2节中的HITS算法，计算集合S中所有网页的Authority和Hub值。将集合S中所有网页按照Authority值的大小进行排名，则S的Authority排名记为集合A={a1,a2,…ai,…ak}，通过Alexa查询的集合S所有网页的排名记为集合L={l1,l2,…li,…lk}。然后把集合AL={a1m+l1n, a2m+l2n,…aim+lin,…akm+lkn} (其中m=0.8,n=0.2)作为集合S的Authority和Alexa综合排名值。通过实验和综合统计，选择m=0.8、n=0.2即网站的访问量所占的比重为20%。将集合S的节点根据综合排名从大到小排列，选取前α(α为预先设定的，本文α取值80%)个节点组成初始群S11。此处选择Authority值高的，即比较权威的网站做为初始种子，然后在此基础上进行交叉、变异、选择等操作，这样可以避免严重偏离主题。

同理，将集合S中所有网页按照Hub值的大小进行排名，则S的Hub排名

湖北工业大学硕士学位论文

记为集合B={b1,b2,…bi,…bk},集合S的Alexa排名记为集合L={l1,l2,…li,…lk}，则集合BL={b1m+l1n, b2m+l2n,…bim+lin,…bkm+lkn}(其中m=0.8,n=0.2)为集合S的Hub和Alexa综合排名值。然后将S按照Hub和Alexa综合排名值从大到小排列，组成集合H。

构造初始群的具体过程如下：首先通过Google获取n(n是自己设定的)个与主题相关的URL，进行扩展后得到集合S3，再对S3进行URL去重得到集合S，然后计算集合S中所有URL的Authority和Hub值，查询S中所有URL的Alexa排名，再计算集合S的所有URL的综合排名值，然后按照综合排名值降序排列，得到的集合记为初始群S11，此S11就是第一代遗传的初始种子，此时集合S11中的所有URL都已经被爬虫抓取且下载URL对应的页面到本地，而且没有重复的URL。然后再开始交叉、变异、选择等操作。构造初始群的流程如图4.4所示：

用google获取初始化种子集根据S1入链扩展，所有入链对应URL记为集合S2 记S3=S1+ S2 MD5算法是否被抓取？是否记为集合S HITS算法计算S的Authority值，记为集合 Alexa查询记为集合L={l1,l2,…li,…lk} A={a1,a2,…ai,…ak} 记为集合AL={a1m+l1n, a2m+l2n,…aim+lin,…akm+lkn}， m=0.8,n=0.2 选取前α个组成初始群S11，α=0.8退出图4.4 构造初始群流程图

湖北工业大学硕士学位论文

4.2 交叉

下载初始群S11中所有URL对应的页面，并提取初始群S11中每个URL对应的页面包含的超链及关于超链的描述信息，描述信息通常以文本和图片的形式出现[39][40]。下面是一个超链的实例：

中关村在线。其中，“中关村在线”是超链“http://www.zol.com.cn”的描述，也称之为一个“锚文本(anchor text)”。

对于此实例，通过锚文本“中关村在线”可以预测此URL对应的网页与设定的主题是否相关，因此，提取锚文本然后进行分析可以有效地预测与主题的相关性，然后选择相关度高的进行抓取，去除相关度低的URL，这样可以提高搜索的准确度。

提取出S11中所有超链的锚文本之后，利用3.3节的正向最大匹配分词算法对锚文本进行解析，例如上例的“中关村在线”解析之后分成“中关村/在线”，此时就只有两个关键词中关村和在线，然后利用这两个关键词来预测与主题的相关度。此处是采用3.1节的向量空间模型算法来计算相关度的，然后选择相关度高的URL，去除相关度低的URL，去除的URL里也包括无关的广告等。

在实际中，很多网页包含的链接中有广告和其他的娱乐信息等，他们与网页本身内容是无关的，那么对于爬虫来说，抓取这些无关的链接是会影响搜索效果的，所以要剔除那些与主题无关的链接，包括广告、娱乐等，这也是此处需要进行相似度计算的原因之一。

在本课题中，交叉操作的具体过程如下：提取初始群S11中所有URL对应的页面包含的超链URL，记为集合C，取出集合C中所有URL对应的锚文本，利用正向最大匹配分词解析每一个锚文本，然后利用VSM算法计算锚文本与主题的相关度r，然后将所有超链的URL按照主题相关度r的大小进行降序排列，得则选取前M*P1个URL作为交叉结果，到的URL集合记为M，设交叉概率为P1，记为集合S12。经过实验和各方面的数据统计，选定交叉概率P1为0.8。具体过程如图4.5所示：

湖北工业大学硕士学位论文

初始群S11所有URL对应的页面包含的超链，记为集合C取出集合C中所有URL对应的锚文本正向最大匹配分词，VSM算法计算锚文本与主题的相关度r根据r 的大小降序排列C，记为集合M设交叉概率P1=0.8，取前M*P1个URL作为交叉结果，记为集合S12 S11∪S12 退出图4.5 交叉操作过程图

对于主题爬虫来说，抓取并下载完集合S11中所有的URL对应的页面之后，就需要抓取集合S12中的URL，而S12是交叉后的种子集合，此集合中可能会有重复的URL，而且可能有部分URL是集合S11中所共有的，即此部分URL已经被爬虫抓取了，所以爬虫在抓取集合S12中的URL时必须采用3.1节的不重复抓取策略，也就是说爬虫在抓取S12中的URL时会自动剔除掉重复的URL和已经访问过的URL，这样就可以保证URL的唯一性，也减少一些重复的操作。此时，爬虫抓取并下载的种子集合就是S11∪S12，这样就扩大了种子集合，从而获取更多的与主题相关的页面。

4.3 变异

目录型网页(Hub网页)是各种网页链接的集合，它所链接的网页大多与目录网页本身不相关，即目录网页自身可能与设定的主题无关，但是目录网页链接的网页却可能有很多与主题相关的[41]-[44]，而且在实际中确实有这样的情况，比如http://www.hao123.com/，网页自身没有明确的主题，但是包含的网页链接却各种各样，大多还是以分类的形式出现的。如果在搜索中，增加这部分页面所包含的

湖北工业大学硕士学位论文

链接，那么就可以扩大网页的搜索范围,而且可以更好地寻找到与主题相关的页面。而如何加入这部分页面就是变异所需要做的工作。

在本课题中，变异操作的具体过程如下：在构造初始群时，已经将集合S按照Hub和Alexa综合排名值从大到小排列，组成集合H，然后通过变异操作根据设定的变异概率引入Hub网页，适当地增加URL。设变异概率为P2,则从Hub网页集合H中选取前H*P2个URL作为变异结果，记为集合S13。其中P1+P2=1，P2=0.2。变异操作过程如图4.6所示：

交叉后集合S11∪S12集合S按照Hub和Alexa综合排名，组成集合H。设变异概率P2=0.2，取前H*P2个URL作为变异结果，记为集合S13 S14=S11∪S12∪S13 退出图4.6 变异操作过程图

对于主题爬虫来说，抓取并下载完集合S11∪S12中包含的所有URL对应的页面之后，就要抓取变异之后的集合，即集合S13。集合S13的引入是依据目录型网页中所包含的大量的与主题相关的超链，引入集合S13后会扩大相关种子的搜索范围，但是集合S13中也必然包含一些已经被爬虫抓取的URL，所以爬虫在抓取集合S13时依然需要采用3.1节的不重复抓取策略，从而保证种子集合中URL的惟一性。此时，爬虫抓取并下载的种子集合就是S14=S11∪S12∪S13，这样更进一步扩大了种子集合，从而获取更多的与主题相关的页面。

现在，交叉、变异操作完毕之后，第一代遗传操作就结束了，此时爬虫抓取并下载的页面就是第一代遗传之后的种子集合，即集合S14就作为第一代遗传的结果。此时爬虫已经抓取了较多的与主题相关的页面，而且爬虫在抓取URL时都采用了不重复抓取策略，所以集合S14中没有重复的URL，但是互联网的链接结构错综复杂，依旧有很多相关页面未被抓取，所以需要继续查找相关种子然后抓取。而遗传算法的原理就是根据遗传原则反复进行选择、交叉、变异，不断重复直至获取最优解。所以对于爬虫来说，仍然需要重复上述操作直至满足退出条件时终止，这样才可以获得让用户满意的结果。

湖北工业大学硕士学位论文

4.4 选择

选择是对第一代遗传的结果进行一定的处理，即将种子集合中相似度高的个体选出来，处理后的结果作为第二代遗传的初始种子，然后再进行新一轮的交叉、变异。重复上述步骤，直至获取最优解。

对于集合S14，第一代遗传结束之后，爬虫已经抓取并下载了集合S14中所有URL对应的页面，但是在进入第二代遗传之前需要对第一代的结果进行分析和处理，这样可以适当地收敛种子集合范围，然后重复进行，从而获取最优解。

首先就需要提取所爬虫已经抓取和下载了集合S14中所有URL对应的页面，

有页面中包含的超链和超链的描述信息，然后利用3.3节的正向最大匹配分词算法对超链的锚文本进行解析，解析之后提取关键词，再利用3.2节的向量空间模型算法预测超链对应的URL与主题的相关性。而在第一代遗传的交叉操作中，集合S11中所有URL对应的页面包含的超链都已经被提取出来而且进行了相似度计算，所以此时进行选择操作时就不需要重复计算这部分网页的相似度，在具体的实现过程中，每一个URL在爬虫抓取的过程中都利用MD5算法进行了定位，即不会重复抓取，所以对已经抓取的URL，只要计算了其与主题的相关度，则对应的将相关度值存储起来，需要时直接查询，这样就可以避免重复劳动。

在本课题中，新一代种子集合的选择操作具体流程如下所示：提取集合S14中所有URL对应的页面包含的超链，利用VSM算法预测其与主题的相关度，再将所有超链按照相关度r的大小进行降序排列，得到集合N，选取前N*α(本并将集合S21作为第二代的初始种子进入第文设定为80%)个URL组成集合S21，

二轮的遗传。选择操作具体过程如图4.7所示：

第一代遗传结果S14提取S14中所有URL对应的页面包含的超链VSM算法计算超链与主题的相关度r，根据r大小降序排列，得到集合N 选取前N*α个URL组成集合S21，α=0.8退出图4.7 选择操作流程图

湖北工业大学硕士学位论文

第二轮遗传重复4.2节和4.3节的交叉、变异操作，得到的种子集合再进行4.4节的选择操作，选择之后的结果又作为新一代遗传的初始种子。一直重复上述步骤，直到满足终止搜索的条件，爬虫就结束此次搜索。

4.5 终止搜索

对于主题爬虫来说，它根据遗传原则在互联网上不断地搜索与主题相关的页面，而基于遗传算法的搜索策略是不停地循环反复的，那么爬虫何时可以停止搜索就是设计爬虫时必须考虑的问题，目前，判断爬虫是否终止搜索的方式大概有以下三种[45]-[48]：

1.已下载的页面数是否超过用户设定的最大值。

在实际的使用中，用户提交一个问题之后，搜索引擎返回的结果可能多达几千甚至上万，而返回的结果是按照与用户提交的问题相似度的高低来排列的，即根据相似度值从大到小排列，而对于用户来说，用户一般也只会浏览结果列表中的前面的页面，所以爬虫即使搜索出了所有相关的页面，而在实际中却没有任何用处。由于搜索引擎的目的就是为了满足用户的需要，所以爬虫在抓取过程中可以适可而止，那么就可以根据实际情况，确定需要下载的相关页面的个数，然后爬虫在抓取网页时，只要爬虫抓取并下载的页面数达到了预先设定的最大值，爬虫就会终止搜索。

2.遗传进化代数是否超出用户设定的最大进化代数。

基于遗传算法的主题搜索策略，遗传进化代数是可以预先设定的，如果不设定遗传代数，则爬虫会一直进行搜索，直至满足其他终止条件时中止，比如：爬虫已下载的页面数达到设定的最大值，没有新种子出现。但是如果设定了遗传进化代数，则爬虫不仅可以抓取大部分与主题相关的页面，而且会避免爬虫陷入无穷的死循环中，同时可以节约计算机资源，也可以提高搜索效率。

3.是否有新种子出现。

对于爬虫来说，最终目的就是抓取所有与主题相关的种子，而互联网的链接结构决定了爬虫可以抓取所有的种子，所以可以通过查看是否有新种子出现来决定是否继续搜索。如果不设定爬虫终止条件，那爬虫可以不停地进行搜索，但是却不能搜集到新的种子，这样是无法高效地完成搜索任务的。所以只要爬虫不能搜集到新的种子，就认为爬虫搜索过程结束了，直接跳出搜索。

在实际的使用中，具体使用哪种方式来终止爬虫的搜索是因情况而定的，而且可以同时使用这几个条件，只要满足了其中一个终止条件爬虫就可以终止搜索。例如，设定的最大下载页面数为1000，遗传进化代数最大为6，而设定的主

湖北工业大学硕士学位论文

题比较生僻，爬虫4次遗传进化之后搜索到的相关页面数为600，而且继续搜索时已经搜集不到新的种子，但是此时爬虫不满足终止条件，只能遗传进化6代之后才会终止，这样就浪费了资源，也浪费了时间，所以爬虫的终止搜索的条件中加上“没有新种子出现时就结束”，那爬虫在4次遗传进化之后就直接退出结束了。这样就可以很好地提高搜索效率。

4.6 本章小结

本章提出了将改进后的遗传算法应用在主题爬虫的搜索策略中，详细讲解了改进后的遗传算法涉及到的构造初始群、交叉、变异、选择、终止搜索等步骤。构造初始群是将待检索的问题提交给通用搜索引擎，对其返回的结果集进行处理，选择一定数目的URL作为初始群体；交叉操作是对初始群体中页面包含的超链进行相似度预测，选出相关度高的种子作为交叉结果；变异操作是引入目录型网页来扩大搜索范围；选择操作是对遗传之后的结果进行处理然后作为下一代遗传的初始种子；终止搜索是爬虫结束搜索需要满足的几个条件。

湖北工业大学硕士学位论文

第5章性能分析

5.1 实验设计

关于搜索引擎的体系结构，现在大体分为四个模块：下载系统、分析系统、索引系统和查询系统，其中下载系统的主要功能是：由计算机控制的下载中心控制并统筹管理网络上各个并行的爬虫，对整个网络进行大规模的网页抓取工作（即下载并保存符合相关要求的网页）。而在下载系统中，网络爬虫是一个非常重要的组成部分。在确定主题的搜索引擎系统中，定题网络爬虫的优劣直接决定了所获取的网络资源的主题相关度，它将直接影响最终的查全率和查准率等性能指标。

网络爬虫即一个小的网络程序，它由计算机控制不断的抓取符合相关规定的网页，在网络爬虫的设计中必须解决两个问题：一是爬虫策略，二是抓取条件。抓取条件是网络爬虫抓取网页时必须满足的网页限定的被抓取的条件，实际中，部分网页涉及到隐私保护或其它经济、政治原因，对于这部分网页来说，网页拥有者本人是不允许该网页被搜索出来供其他用户浏览的，也就是说并不是所有的网页都可以被网络爬虫抓取，所以爬虫在抓取网页前必须先读取网页本身的限制（包括该网页是否可以抓取，哪些内容可以抓取等），爬虫在获取相关的信息后才可以在允许的条件下进行抓取工作；爬虫策略是指网页在满足被抓取的条件下，爬虫抓取所有相关的网页所使用的方法策略，但是实际使用中，爬虫几乎不可能抓取所有的可以被抓取的相关网页，因为互联网的网页数量巨大，而且链接结构复杂，所以一个好的搜索策略是指在某个时间段内爬虫获取的相关信息量最多。

在主题爬虫的设计中，对于爬虫抓取条件问题较易解决，在爬虫程序的头部加入读取网页抓取限制的代码，然后解析之，检查该网页是否可以被抓取，或者该网页的哪些内容不可以被抓取，对于这种有限制的网页，爬虫直接跳过，然后根据搜索策略继续爬行。在主题爬虫的实际设计中，爬虫搜索策略的好坏直接影响着搜索效率的高低和搜索效果的优劣。目前，主题搜索策略多种多样，这些不同的策略往往需要借助于各种不同的算法。简言之，主题搜索策略的不同即为搜索算法的不同。而主题爬虫就是通过特定的算法，在Web上遍历并有选择地下载网页，将规范化的资源描述文件保存到本地并存储起来，然后搜索引擎的其它部分再对存储的文件进行后续处理。

湖北工业大学硕士学位论文

5.1.1 实验目的

目前，爬虫搜索策略已经取得了较大的研究成果，比较成熟的包括：基于内容评价的搜索策略，基于链接结构评价的搜索策略和基于未来回报的搜索策略。不同的搜索策略侧重点也有所不同，基于内容评价的搜索策略忽略了Web页面之间的链接关系，不能很好地发挥网页链接的作用. 基于链接结构评价的搜索策略考虑了网页间的链接结构，但忽略了页面本身与主题的相关性，易出现“主题漂移”问题。鉴于以上问题，本文根据遗传算法的全局寻优的特点，将改进后的遗传算法应用在爬虫搜索策略中，并对改进后的算法进行性能分析以验证改进后的算法的效果和可行性。

为了验证算法改进后的效果，本文分别采用三种较常用的算法——Best-First算法、HITS算法和基于神经网络的遗传算法(一般简称为GA算法)对给定主题进行搜索，然后将搜索到的网页根据向量空间模型算法计算其与主题的相似度，相似度超过给定值的网页被认为是相关网页，反之为不相关网页，最后分别统计三种算法搜索到的相关的网页数。在相同的条件下，得到相关网页数多的算法可以认为具有较好的效果和较高的可行度。

5.1.2 实验原理

主题爬虫的主要工作就是：通过特定的算法，按照一定的规则在网络中遍历并有选择地下载网页，然后将规范化的资源描述文件保存到本地并存储。一般来说，作为商业应用的搜索引擎必须对整个互联网进行大规模的、系统的搜索，然而在实验中这样做不仅不现实而且没有必要。所以在本课题的实验中，首先使用Google对给定的主题进行初步的检索并保存检索结果，然后以检索结果为进一步的研究对象进行深入的研究。本实验的主要工作包括：分别使用三种不同的算法对初步的检索结果进行二次检索，然后对二次检索结果进行分析比较。实验的基本框架如图5.1所示：

湖北工业大学硕士学位论文

图5.1 实验框架图

在爬虫子系统中，爬虫所抓取的各种Web内容都存储到本地数据库中。爬虫子系统由多个爬虫组成，各个爬虫可以运行在一个或多个计算机中，它们并行地访问Web，并完成各自的任务。其中，每一个爬虫又都是由多个线程组成，每一个线程都运行着相同的代码块，这些线程并行地在网络上抓取所需资源。为了避免重复工作，必须为各个爬虫分配不同的任务，而每个爬虫又可以把分配的任务交给不同的进程去完成，这样就可以实现在多个不同的网络区域同时，独立的获取资源。其中，任务分配和多个并行爬虫的管理工作由调度模块解决。爬虫子系统的架构如图5.2所示：

图5.2 爬虫系统架构图

每一个爬虫都运行了多个线程，不同的线程可以并发地访问读写共享的数据表。由于每个线程都能访问后台的数据库，可以从数据表中读取URL，也可以将新获取的URL存入到数据表中，这就要求爬虫子系统必须通过一定的同步机制，来协调各个线程的并发工作以保持数据库中数据的一致性。此时则可以通过

湖北工业大学硕士学位论文

对线程中数据表访问时进行加锁操作来实现基本的同步机制。在系统中，由于在后台数据库和前台的爬虫之间，使用抽象的逻辑队列来实现数据的交互，所以同步机制的实现，实际上就是对队列的入队和出队操作同步机制的实现。在爬虫子系统中，同步机制由总调度模块负责。

实验的基本硬件、软件环境如下：

硬件环境 CPU：AMD Athlon(tm)X 2 2.0 G

DRAM：2G Hard Disk：250G

软件环境开发语言：Java

开发工具：MyEclipse 6.0 操作系统：Window XP 数据库：SQL Server2000

5.1.3 VSM模块

向量空间模型算法(VSM)常用来计算文本相似度，在本实验中需多次计算页面与主题的相似度。为了能在实验流程的不同阶段方便的计算相似度，本课题设计了“VSM模块”及相关接口。

VSM模块通过接口接受相关数据信息，然后经过内部程序计算得出相似度最后将结果输出[49][50]。VSM模块的结构如图5.3所示：

图5.3 VSM模块结构图

5.1.4 Authority和Hub计算模块

在互联网上对网页的Authority和Hub值进行计算是个复杂而艰巨的工作，本实验所使用的Authority和Hub值并不是对整个互联网进行计算后得出的，而是对临时的结果集合进行计算后得出的。由于本实验所使用的Authority和Hub

湖北工业大学硕士学位论文

值具有临时性，所以对Authority和Hub值的计算必须快速有效。为了在较短的时间内快速有效的对相当数量的网页集合计算并得出集合内所有网页的Authority和Hub值我们设计了“Authority和Hub计算模块”。

Authority和Hub计算模块的功能[51]是：首先接受相关网页集合，然后计算集合内所有网页的Authority和Hub值，最后把计算结果发送给后续系统。Authority和Hub计算模块的结构如图5.4所示：

图5.4 Authority和Hub模块结构图

5.2 实验过程

本文以“计算机安全”为搜索主题，即本文的主题搜索引擎是针对“计算家安全”这个主题的，从《中国分类主题词表》中得到主题特征集[52][53]，并根据资料统计出主题词的权重。实验首先利用Google搜索主题特征集，得到初次检索的结果集合（集合包含与主题相关的页面大约31,800,000条），然后基于三种不同算法分别对结果集合进行二次检索，最后统计二次检索结果的相关性。

三次实验是在相同条件下进行的，二次检索的相关性统计结果可以表明三种不同算法的优劣程度。在三次实验中，统计相关性即：计算二次检索结果网页与主题特征集的相似度。其中，相似度的计算采用向量空间模型算法（VSM），分词采用正向最大匹配算法。

5.2.1 基于Best-First算法的实验过程

基于Best-First算法的实验过程[54]如下：

1. 利用通用搜索引擎Google检索“计算机安全”，获取初始URL。 2. 计算URL对应的网页与主题之间的相似度；相似度的计算采用VSM模

型。

湖北工业大学硕士学位论文

3. 对URL根据相似度大小进行降序排列，选择相似度最高的URL开始进

行二次检索，并将此URL放到已抓取URL队列中，其它URL放到未抓取URL队列中且根据相似度大小保持降序排列。

4. 提取此URL对应的页面中包含的所有链接和锚文本，采用VSM模型预测

链接与主题的相似度。

5. 根据URL与主题的相似度大小，将URL插入到未抓取的URL队列中且

保持降序排列。

6. 回到步骤3。从未抓取的URL队列中选择相似度最高的URL开始继续

搜索。

7. 重复上述操作，直至爬虫抓取的网页数超过最大页面数或者未抓取的

URL队列中无URL，则爬虫搜索结束。 8. 对二次检索结果进行相关性统计。

实验过程如图5.5所示：

图5.5 基于Best-First算法的实验过程图

5.2.2 基于HITS算法的实验过程

基于HITS算法的实验过程[55]如下：

1. 用Google检索“计算机安全”，并把相关的检索集合保存在本地数据库

中。

2. 根据Authority和Hub计算模块计算集合中所有网页的Authority和Hub

值。

3. 根据网页的Authority值的大小进行降序排列，选择Authority值较大的

网页作为种子开始新一轮的搜索。

湖北工业大学硕士学位论文

4. 回到步骤2，重复上述操作，直至爬虫抓取的网页数达到用户设定的最

大页面数或者没有新的URL出现，则爬虫搜索结束。

5. 将抓取到的URL分别按照Authority值和Hub值的大小进行降序排列，

返回的Authority值较大的网页作为权威型网页，返回的Hub值较大的网页作为目录型网页。 6. 对检索结果进行相关性统计。

实验过程如图5.6所示：

图5.6 基于HITS算法的实验过程图

5.2.3 基于GA算法的实验过程

基于GA算法的实验过程如下：

1. 用Google检索“计算机安全”，并获取初始URL。

2. 对初始URL进行扩展、消重，结合访问量进行综合排名，构造初始群。

Authority和Hub值的计算使用“Authority计算模块”。

3. 利用锚文本预测超链与主题的相关性，通过交叉操作获取适应度高的种

子。相似度的计算直接使用“VSM模块”。

4. 通过变异操作引入目录型网页，扩大爬虫搜索范围。

5. 提取超链接并预测URL与主题的相关性，选择相关度较高的URL作为

第二代遗传的初始种子。

6. 回到步骤3。继续第二代遗传的交叉、变异操作。

7. 重复上述操作，直至爬虫抓取的网页数达到用户设定的最大值或者遗传

进化代数达到用户设定的最大值，也或者没有新种子出现，则爬虫搜索结束。

8. 对检索结果进行相关性统计。

湖北工业大学硕士学位论文

实验过程如图5.7所示：

图5.7 基于GA算法的实验过程图

GA算法中，对结果集的选择、交叉、变异等操作已经在第四章进行了详细的介绍。

5.3 实验结果分析

在基于GA的主题爬虫搜索策略中，交叉和变异概率的大小对爬虫搜索性能有一定的影响。因此，在本课题中，首先选用了四组不同的概率组合，分别使用遗传算法进行爬虫搜索。设交叉概率为P1，变异概率为P2，其中P1+P2=1。实验统计的数据如表5.1所示(列数据为相关的页面数)：

表5.1 交叉、变异概率实验数据表

下载页面数 P1=0.3 1000 2000 3000 4000 5000 6000 7000 8000 9000 10000 11000 12000

411 632 732 1045 1143 1434 1701 2109 2317 2850 3152 3346

P1=0.5 459 732 1034 1435 2037 2459 2557 3038 3216 3710 4183 4431

P1=0.8 649 953 1387 2186 3137 3732 4482 5420 5839 6038 6949 7793

P1=0.9 664 1194 1743 2387 2463 2731 3418 3731 4168 4763 4832 4973

湖北工业大学硕士学位论文

实验结果如图5.8所示：

图5.8 交叉、变异概率实验结果图

上图中线条周围标注的数字代表的是交叉概率，从上图曲线可以看出：交叉概率的选择对整个搜索性能有较大影响，下载的页面数越多，交叉概率为0.8时获取的相关页面数也就越多。若交叉概率太小，则变异概率变大，而变异过程中引入的Hub节点就过多，这样就会影响搜索效果。所以比较合理的交叉概率选择范围为(75％～85％)。在本课题中，选择交叉概率P1=0.8，变异概率P2=0.2。

本文以“计算机安全”为搜索主题，首先利用Google搜索与主题相关的页面，获得大约31,800,000条查询结果，选取前100个结果组成初始集合，然后爬虫分别采用基于Best-First、HITS和GA三种算法的搜索策略进行爬行。实验中，爬虫不重复抓取网页采用的是MD5算法，相似度计算采用向量空间模型算法，分词采用正向最大匹配算法。实验统计的数据如表5.2所示：

表5.2 算法比较实验数据表

下载的页BF相关率面数 1000 2000 4000 6000 8000 10000 12000

HITS相关率 0．414 0．297 0．331 0．243 0．287 0．337 0．301

GA相关率 0．424 0．321 0．421 0．741 0．532 0．575 0．701

0．542 0．721 0．520 0．434 0．397 0．411 0．425

湖北工业大学硕士学位论文

实验结果如图5.9所示：

图5.9 算法比较实验结果图

从数据表和对应的图中可以看出：在爬虫搜索初期，本文提出的遗传算法搜索效率低于BF算法。随着下载的页面数的增加，搜索到的相关页面数与下载的页面数的比例也随之增加，GA算法的搜索效率也高于了BF和HITS算法，由此可见，本文提出的基于遗传算法的搜索策略具有一定的优势。

5.4 本章小结

为了验证算法改进后的效果，本章分别采用三种较常用的算法——Best-First算法、HITS算法和基于神经网络的遗传算法(一般简称为GA算法)对给定主题进行搜索，并统计最终搜索结果与主题的相关性。

为了提高实验的效率而设计了相关的实验模块——VSM模块和Authority和Hub计算模块。VSM模块用来计算与主题的相关度，Authority和Hub模块用来计算网页的Authority和Hub值。实验结果表明遗传算法在爬虫搜索策略中的使用是可行的，改进后的遗传算法在某种程度上对搜索效果有所改进。

湖北工业大学硕士学位论文

第6章总结与展望

6.1 本文总结

本文提出的基于遗传算法的主题信息搜索策略，是利用遗传算法的全局寻优特点，根据网页间的链接结构，借助超链的描述信息预测链接对应的页面与主题的相关度，然后进行初始群的构造、交叉、变异、选择等一系列的操作，经过遗传进化，最终得到最优解。经过实验表明改进后的遗传算法在一定程度上提高了爬虫搜索效率。

本文在研究传统搜索引擎的同时，结合用户的实际需要，对主题搜索引擎进行了深入、系统的研究。本论文的主要贡献如下：

1、利用遗传算法改进爬虫的搜索策略。鉴于目前爬虫搜索中的问题，根据遗传算法的全局寻优的特点，将遗传算法应用到爬虫的搜索中，使爬虫可以获取更全面更好的信息。

2、根据网络特点改进传统的遗传算法。本文对遗传算法的具体实施过程进行了改进，在构造初始群时增加了网页访问量的考虑；在交叉阶段，利用超链的描述文本来预测页面的主题相似度，根据相似度的大小有选择地扩展种子集合；在变异阶段，引入了目录型网页，扩展爬虫的搜索范围，从而达到全局寻优。

3、通过对三种不同算法搜索出的结果进行实验比较，得到了合理的实验结果。

6.2 研究展望

本文提出的基于遗传算法的主题爬虫搜索策略，虽然在一定程度上改进了搜索效果，但是由于时间、精力和水平的原因，还有很多方面需要改进，下一步需要做的工作还很多。

1、本文利用锚文本来预测超链与主题的相似度，此处还存在一些不足，下一步的研究重点是从半结构化网页中抽取出有价值的能够代表网页的属性，例如锚文本、标题和正文等。将这些属性结合起来作为网页的对象，从而更好地预测网页与主题的相关性。

2、在本文中，所用到的参数的设置，还需要经过实践检验然后做出调整，这还需要在今后的实践中不断完善。

湖北工业大学硕士学位论文

参考文献

[1] 李勇，韩亮．主题搜索引擎中网络爬虫的搜索策略研究．计算机工程与科学[J]，2008. [2] CHEN H．CHUNG Y M，RAMSEY M，et a1．An intelligent personal spider(agent)f-

or dynamic Internet／Intranet searching[J]．Decision Support Systems，1998，23(1)：41-58.

[3] 许欢庆，王永成.基于遗传算法的定题信息搜索策略[J].中文信息学报，2002,1(17):

25-31.

[4] 唐志，王成良. 遗传算法在主题Web信息采集中的应用研究[J].计算机科学，2006，

33(7)：71-74.

[5] 刘玮玮.搜索引擎中主题爬虫的研究与实现[D].南京：南京理工大学，2006. [6] 郑健珍.定题爬虫搜索策略研究[D].厦门:厦门大学,2007.

[7] 庞剑锋,卜东波,白硕.基于向量空间模型的文本自动分类系统的研究与实现[J].计算机

应用研究,2001,18(9):23-26.

[8] F.Menczer,G.Pant and P.Srinivasan.Topic-Driven crawlers:machinelearning is-sues[Z].[2004-07-02].http://dollar.biz.uiowa.edu/～fil/papers.html. [9] Dr.P.M.E.,DeBra and Drs.R.D.J.Post.Searching for arbitrary information in

the WWW:the fish-search for Mosaic[A].http://archive.ncsa.uiuc.edu/SDG/IT94/Proceedings/Searching/debra/article.html.

[10] Michael Hersovici,Michal Jacovi,Yoelle S.Maarek,Dan Pelleg,Menachem Shtal-haim and Sigalit Ur.The shark search algorithm-An application:TailoredWeb-site mapping[A].In Proceedings of the 7th International World wide web co-nference,1998.

[11] Jon.M.Kleinberg.Authoritative Sources in a Hyperlinked Environment[J].Jou-rnal of the ACM,1999:46(5).

[12] DeBra,Post.Information retrieval in the World Wide Web:Making client-based

searching feasible[A].Proceedings of the 1st International World Wide Web Conference,1994.

[13] 曾春，邢春晓．基于内容过滤的个性化搜索算法[J]．软件学报，2003,14(5):999-

1004.

[14] 王晓宇,周傲英.万维网的链接结构分析及其应用综述[J].软件学报,2003,14(10):

1768-1780.

湖北工业大学硕士学位论文

[15] 林海霞, 原福永, 陈金森等.一种改进的主题网络蜘蛛搜索算法[J].计算机工程与应

用,2007,43(10):174-176.

[16] 刘国靖,康丽,罗长寿.基于遗传算法的主题爬虫策略[J].计算机应用,2007,27(12):

172-175.

[17] 吴安清,张颖江.主题搜索ROBOT综合爬行策略的研究[J].武汉理工大学学报,2006,

28(2):74-76.

[18] 王灏，黄厚宽，田盛丰.文本分类实现技术.广西师范大学学报(自然科学版)，2003（1）：

173-179.

[19] 刘开瑛等.中文文本中抽取特征信息的区域与技术.中文信息学报.1998（12）：1-7. [20] 王伟强等.Internet上的文本数据挖掘.计算机科学.2000（27）：32-36.

[21] Salton.G, Yang.C. A Vector Space Model for Automatic Indexing[J]. Communi-cations of ACM. 1975,18(11):613-620.

[22] Cho.J, Garcia-Molina.H, Page.L.Efficient crawling through URL ordering:the

Seventh International World-Wide Web Conference[C], 1998,Australia. [23] Kleinberg.J.M.Authoritative sources in a hyperlinked environment:the Ninth

Annual ACM-SIAM Symposium on Discrete Algorithms[C],1998,USA.

[24] Matthew.P.D.Richardson.The intelligent surfer:Probabilistic combination of

link and content information in PageRank. Neural Information Processing S- ystems[J].2002.673-680.

[25] 李淑英.中文分词技术[J].计算机与信息技术,2007,36:95.

[26] Ricardo Baeza2Yates,Berthier Ribiero2Neto and Berthier Ribeiro Ne2 to.Mod-ern Information Retrieval[J].Addison－Wesley,1999:73-96.

[27] 翟凤文,赫枫龄,左万利.字典与统计相结合的中文分词方法[J].小型微型计算机系统,

2006,27(9):1767-1769.

[28] 金在全,赵照,等.一种改进的增字最大匹配算法[J].科学技术与工程,2007,7(18):

4762-4764.

[29] 张桂林.中文文本自动分类系统的研究与实现[D].吉林：吉林大学，2007. [30] 彭涛.面向专业搜索引擎的主题爬行技术研究[D].吉林：吉林大学，2007. [31] 宗校军.中文网页定题采集及分类研究[D].武汉：华中科技大学，2006.

[32] 刘铮.定题Web搜索与挖掘的研究与系统实现[D].西安:西安电子科技大学，2007. [33] 吴丽辉.个性化的Web信息采集技术研究[D].北京：中国科学院，2005.

[34] 代六玲, 黄河燕, 陈肇雄. 中文文本分类中特征抽取方法的比较研究[J].中文信息学

报,2004.18(1):26-32.

[35] 尹存燕，戴新宇，陈家骏．Internet上文本的自动摘要技术[J]．计算机工程，2006，

湖北工业大学硕士学位论文

32(3)：88-90.

[36] 李珩,朱靖波,姚天顺.基于SVM的中文组块分析[J].中文信息学报,2004,18(2):1-7. [37] 梁斌.走进搜索引擎[M].北京：电子工业出版社.2007:24-249.

[38] 苏金树,张博锋,徐昕.基于机器学习的文本分类技术研究进展.软件学报[J].17(9):

1848-1859.

[39] 李荣陆,李建会,陈晓云.使用最大熵模型进行中文文本分类[J].计算机研究与发展,

2005,42(1):94-101.

[40] 林永民,朱卫东,尚文倩.KNN文本分类器中决策规则的改进[J].计算机研究与发展,

2005,42(增):378-382.

[41] 陈涛,谢阳群.文本分类中的特征降维方法综述[J].情报学报2005,24(6):690-694. [42] 周茜,赵明生.中文文本分类中的特征选择研究[J].中文信息学报,2004,18(3):17-23. [43] 黄萱菁,吴立德.独立于语种的文本分类方法[J].中文信息学报,2000,14(6):1-7. [44] 秦进,陈笑蓉,汪维家,等.文本分类中的特征抽取[J].计算机应用,2003,23(2):45-46. [45] 刘少辉,董明楷,张海俊,等.一种基于向量空间模型的多层次文本分类方法[J].中文信

息学报,2001,16(3):8-26.

[46] 刘群,李素建.基于《知网》的词汇语义相似度计算[J].Computational Linguistics

and Chinese Language Processing,2002,7(2):59-76.

[47] 庞剑锋,卜东波,白硕.基于向量空间模型的文本自动分类系统的研究与实现[J].计算

机应用研究,2001,18(9):23-26.

[48] 李素建.基于语义计算的语句相关度研究[J].计算机工程与应用,2002,(7):75-76. [49] 李凡,鲁明羽,陆玉昌.关于文本特征抽取新方法的研究[J].清华大学学报,2001,41(7):

98-101.

[50] Yang.Y and X.Liu.A re-examination of text categorization methods[C].In:Pr-oceedings,22nd Annual International ACM SIGIR Conference on Research and Develop-ment in Information Retrieval(SIGIR 99),42-49,1999.

[51] Yang.Y.Expert network:effective and efficient learning from human decisio- ns in text categorization andretrieval[J].In Proceedings of the Fourth An- nual Symposium on Document Analysis and Information Retrieval(SIGIR’94), 1994,13-22.

[52] Yang.Y,Chute.C.G.An example-based mapping method for text categorization

and retrieval[J].ACM Transaction on Information Systems (TOIS),1994,12(3):252-277.

[53] The Lancaster corpus ofmandarin Chinese (LCMC) [EB/OL].http://www.ling.la- ncs.ac.uk/corplang/lcmc.

湖北工业大学硕士学位论文

[54] Salton.G.Automatic text processing:the transformation analysis,and retrie- val of information by computer.Reading,Pennsylvania:Aoldison-Wesley,1989. [55] Rudolph.G.Convergence Properties of Canonical Genetic Algorithms[J].IEEE

Trans.on Neural Networks,1994,5(1):96-101.

湖北工业大学硕士学位论文

致谢

三年的硕士研究生生活很快就要过去了，在毕业论文完成之际，我衷心地感谢给我无私帮助的老师、同学和家人。

首先感谢我的导师邵雄凯教授。邵老师治学严谨、专业背景深厚、待人和蔼可亲。在学习期间，邵老师在理论知识和科研实践上给予了我极大的帮助，尤其在研究方向和研究思路方法上的指导，使我受益匪浅。在邵老师的帮助下，我逐步深入的掌握了研究的方法和技巧，从而才得以顺利完成了毕业论文。

还要感谢三年来给予我鼎力支持的各位老师，他(她)们是：刘建舟老师、康瑞华老师。他(她)们在专业方面无私地传授给了我很多经验和知识，并始终指导着我的研究课题，使我在非常好的学术氛围中锻炼成长。还要感谢和我朝夕相处的同学：周雪琴、徐彩云、王巧玉、詹圣君等，他们在学习上和生活上也给我提供了许多帮助和支持，他们的深厚情谊我也将铭记在心。

尤其深情感谢我的父母对我巨大的支持和鼓励，在我多年的求学过程中，他(她)们始终在默默的支持着我，他(她)们给我提供了强大的精神力量和物质后盾，为我的成长花费了无数的精力和心血，这份情意是我毕生都难以回报的。

再次诚挚的感谢所有支持我的老师、同学和家人！

湖北工业大学硕士学位论文

附录

作者在攻读学位期间发表的学术论文：

1.邵雄凯，梁云静，刘建舟。基于遗传算法的主题信息搜索研究，网络安全技术与应用。2009(11).

国际标准刊号ISSN1009-6833 国内统一刊号CN11-4522/TP

作者在攻读学位期间参加的主要项目：

1.武汉市东西湖土地资源管理局办公自动化管理系统的开发与设计 2.主题搜索引擎中信息采集技术研究

基于遗传算法的主题爬虫搜索策略研究

作者：

学位授予单位：

梁云静

湖北工业大学

本文链接：http://d.g.wanfangdata.com.cn/Thesis_D094813.aspx

因篇幅问题不能全部显示，请点此查看更多更全内容

查看全文

全部栏目

基于遗传算法的主题爬虫搜索策略研究