本 科 毕 业 论 文
主题网络爬虫的设计与实现
Design and implementation of subject-oriented crawler
姓 名：路 刚 学 号：23020051204554 学 院：软件学院
系：软件工程
专 业：软件工程 年 级：2005级
指导教师：史亮 副教授
二〇〇九 年 六 月
摘 要
目前信息网上蕴含了大量的信息，但通过人工浏览的方法很难做到对信息的安全浏览、整理，很多有用的信息也就白白流失，产生了大量信息不能及时应用的矛盾，给用户造成了很大的不便，为了解决这一问题，搜索引擎这一新热点技术应运而生，本文结合信息网的特征，运用信息抽取和网页解析技术，设计和实现了搜索引擎中最重要的部分——网络爬虫，以提供分类更细致精确、数据更全面深入、更新更及时的因特网搜索服务。
本文首先对概述了网络爬虫的发展概况，然后分析了网络爬虫的体系结构以及实现原理，并深入分析了主题页面在Web上的分布特征与主题相关性的判别算法，具体工作如下：
(1)爬虫部分，通过设计种子网站进行爬虫，下载尽可能全且与用户要求相符合的网站。
(2)网页预处理过程，包括分词、HTML解析和网页消噪。在对树节点进行裁剪的基础上，设计了基于样式的网页消噪方法，进一步提高网页消噪过程。
(3)主题相关性判断，包括特征提取和权值计算阶段。在特征提取阶段，通过组合文档频率，得到新的特征，达到降维和提高分类精度的效果。在权值计算阶段，结合信息增益、传统TFIDF算法和空间向量模型VSM算法，得到了更适合主题相关性判断的权值计算方法。
(4)最后，在MYECLIPSE平台上，实现了一个简易的网络爬虫系统，并简要分析了爬虫的运行效果，达到了令人满意的效果。 关键词：网页解析；TFIDF算法；VSM算法
I
Abstract
Currently there is lot of information in the public security information website,but it is not possible to visit and clean up all information only through artifical manner,so much import information would be lost,also would go aginst cracking a criminal case,which causes a great deal of inconvenience to users.To deal with this problem,search engine technology came into being the new hot spot.Based on the characteristics of information networks,the paper designed and implemented the most important part of search engine—Web Spider，using information extraction and web analytic technology to provide more detailed classification accuracy, data is more comprehensive and in-depth, more timely updates of Internet search services.
This paper first outlined the development of search engines and reptile research network status and then analyzed the architecture of topic search engine and depthly analysd the theme of the page in the Web on the distribution of subject characteristics and the identification algorithm.In this paper,the concrete work as follows:
(1)Spider part. By set seeds through the design of website, download as much as possible and with the whole site in line with user requirements.
(2)Page pre-processing process, including Word particiling, HTML parsing and page de-noising.
(3) To determine the relevance of the theme, including the feature extraction stage and the right value. In the feature extraction stage, through the combination of document frequency, new features, to achieve dimensionality reduction and improving the classification accuracy results. Value in the right phase, combined with information gain, TFIDF algorithm and the traditional vector space model algorithm, have been more suitable for the theme of the relevance of the right to determine the value of the calculation.
(4) Finally, in MYECLIPSE platform to realize a simple network system reptiles, and reptiles a brief analysis of the effect of the operation, reached a satisfactory result. Key words: page analysis; TFIDF algorithm; space vector algorithm.
II
目录
第一章 绪论 ........................................................................................................................................................... 1
1.1 选题背景和研究意义 ..................................................................................................................................... 1 1.2 搜索引擎的发展............................................................................................................................................... 1 1.3 国内外研究现状............................................................................................................................................... 3 1.4 本文的主要工作和论文结构 ....................................................................................................................... 5
第二章 网络爬虫工作原理 ............................................................................................................................ 7
2.1 网络爬虫在搜索引攀中的地位 .................................................................................................................. 7 2.2 网络爬虫的基本原理 ..................................................................................................................................... 9 2.2.1 主题网络爬虫的体系结构 ................................................................................................................... 9 2.2.2 系统模块功能说明 ................................................................................................................................ 10 2.3 内容提取 ........................................................................................................................................................... 11 2.4 主题页面在WEB上的分布特征 .............................................................................................................. 12 2.5 本章小结 ........................................................................................................................................................... 14
第三章 网络爬虫的关键算法 .................................................................................................................... 15
3.1 网页搜索策略 ................................................................................................................................................. 15 3.2主题爬虫的搜索策略 .................................................................................................................................... 16 3.2.1 基于内容评价的搜索策略 ................................................................................................................. 16 3.2.2 基于链接结构评价的搜索策略 ........................................................................................................ 19 3.3 主题相关性算法............................................................................................................................................. 21 3.3.1 向量空间模型(VSM) ............................................................................................................................ 21 3.3.2 页面主题相关性算法 ........................................................................................................................... 23 3.4 本章小结 ........................................................................................................................................................... 24
第四章 主题爬虫的分析与设计 ............................................................................................................ 25
4.1 主题爬虫的体系结构 ................................................................................................................................... 25 4.2 初始种子选取和URL队列维护 ............................................................................................................. 26
I
4.2.1 初始种子选取 ......................................................................................................................................... 26 4.2.2 URL队列维护 ......................................................................................................................................... 27 4.3 网页解析 ........................................................................................................................................................... 28 4.3.1 HTML语法的分析 ............................................................................................................................. 28 4.3.2 网页中信息资源的提取 ...................................................................................................................... 29 4.4 主题相关性算法实现 ................................................................................................................................... 30 4.4.1 分词算法 ................................................................................................................................................... 31 4.4.2 权值计算:TF-IDF算法 ........................................................................................................................ 31 4.4.3 权值算法的改进：IG算法 ................................................................................................................ 34 4.4.4 VSM算法 .................................................................................................................................................. 37 4.5 建立索引 ........................................................................................................................................................... 38 4.6 系统实现 ........................................................................................................................................................... 39 4.6 总结 .................................................................................................................................................................... 41
第五章 总结与展望 ........................................................................................................................................ 42
5.1 本文总结 ........................................................................................................................................................... 42 5.2 研究展望 ........................................................................................................................................................... 42
参考文献 .................................................................................................................................................................... 43 致谢 ............................................................................................................................................................................... 44
II
Contents
Chapter 1 Introduction ..................................................................................................................................... 1
1.1 Background of the topics and research significance.......................................................................... 1 1.2 History of the development of search engines ...................................................................................... 1 1.3 Research status at home and abroad ....................................................................................................... 3 1.4 Main work and structure of this paper .................................................................................................. 5
Chapter 2 Working principle of crawler .............................................................................................. 7
2.1 Status of crawler in search engine domain ............................................................................................ 7 2.2 The basic principles of crawler .................................................................................................................. 9 2.2.1 Architecture of subject-oriented crawler ............................................................................................. 9 2.2.2 Introduction of module function .......................................................................................................... 10 2.3 Information extraction ................................................................................................................................ 11 2.4 Distribution features of subject-oriented page on web ................................................................... 12 2.5 Summary of this chapter ............................................................................................................................ 14
Chapter 3 Key algorithm of crawler ..................................................................................................... 15
3.1 Web searching strategy ............................................................................................................................... 15 3.2 Searching strategy of subject-oriented crawler ................................................................................. 16 3.2.1 Link-based relevance algorithm .......................................................................................................... 16 3.2.2 Content-based relevance algorithm .................................................................................................... 19 3.3 Subject relevance algorithm ...................................................................................................................... 21 3.3.1 VSM(Vector Space Model) ................................................................................................................... 21 3.3.2 Relevance algorithm about web page subject .................................................................................. 23 3.4 Summary of this chapter ............................................................................................................................ 24
Chapter 4 Analysis and design about subject-oriented crawler ........................................ 25
4.1 Architecture of subject-oriented crawler ............................................................................................. 25 4.2 Beginning seeds selection and URL queue maintaince ................................................................... 26 4.2.1 Beginning seeds selection ...................................................................................................................... 26
III
4.2.2 URL queue maintaince ........................................................................................................................... 27 4.3 Web page extraction ..................................................................................................................................... 28 4.3.1 HTMLsyntax analyze ............................................................................................................................. 28 4.3.2 Information resources extraction of the web page ......................................................................... 29 4.4 Implementation of Relevance algorithm .............................................................................................. 30 4.4.1 Segmentation algorithm ......................................................................................................................... 31 4.4.2 Weight caculate: TF-IDF algorithm .................................................................................................... 31 4.4.3 Improve：IG algorithm ......................................................................................................................... 34 4.4.4 VSM algorithm ......................................................................................................................................... 37 4.5 Create index ..................................................................................................................................................... 38 4.6 Implementation of this system ................................................................................................................. 39 4.6 Summary of this chapter ............................................................................................................................ 41
Chapter 5 Summary and Outlook .......................................................................................................... 42
5.1 Summary of this paper ................................................................................................................................ 42 5.2 Prospect resarch ............................................................................................................................................. 42
References ................................................................................................................................................................ 43 Thanks ........................................................................................................................................................................ 44
IV
主题网络爬虫的研究与实现
第一章 绪论
1.1 选题背景和研究意义
随着Internet的快速发展，网络正在深刻地影响着我们的生活。而在网上发展最为迅
速的WWW（World Wide Web）技术，以其直观、简单、高效的使用方式和丰富的表达能力，已逐步成为Internet上最为重要的信息发布和交互方式，据美国因特网监制公司Netcraft 28日宣布，截止2008年2月底，全球互联网网站数量超过1.6亿，达162662053，较一个月前增加了450万。网页数量也达到百亿级别。
随着网络信息资源的急剧增长，越来越多的信息涌到人们的面前，然后Web信心在人们提供丰富信息的同时，却在Web信息的高效便捷使用方面给人民带来巨大的挑战：一方面Web上的信息种类繁多、丰富多彩，而另一方面却很难找到真正有用的信息，搜索引擎就是在这样的背景下出现的，并且已经发挥出不可替代的作用，成为帮助人们从浩瀚的信息海洋中获取自己想要的信息的有效工具和一种举足轻重的网络应用手段。
1.2 搜索引擎的发展
伴随互联网爆炸式的发展，普通网络用户想找到所需的资料简直如同大海捞针，这时为满足大众信息检索需求的专业搜索网站便应运而生了。自上世纪就是年代诞生以来，搜索引擎经历了四个发展阶段[1]：
所有搜索引擎的祖先，是1990年由Montreal的McGill大学的Emtage等发明的Archie。该软件可以根据用户的文件名查找分布在各个ftp主机上的文件。受Archie的启发，Nevada大学于1993年开发了一个Gopher搜索工具Veronica。
(1) 第一代搜索引擎出现于1994年。这类搜索引擎一般数据量少，而且无法及时更新网页，检索速度比较慢。在实现上基本沿用较为成熟的IR、数据库、网络等技术。早期，一些编程者设想既然所有网页都可能有连向其他网站的链接，那么从一个网站开始，跟踪所有网页上的所有链接，就有可能检索整个互联网。到1993年底，一些基于此原理的搜索引擎开始纷纷涌现，比如：Scotland的JumpStation大学McBryan的The World Wide Web Worm。
1994年4月，Stanford University 的两名博士生，美籍华人杨致远和David Filo共同创办了“Yahoo！”。在早期，“Yahoo！”的数据是手工输入的，是一个可搜索的目录，也可称作目录型搜索引擎。
1
主题网络爬虫的研究与实现
1994年7月20日，Lycos的发布是搜索引擎史上又一个重要的进步。除了相关性排序外，Lycos还提供了前缀匹配和字符相近限制，Lycos第一个在搜索结果中使用了网页自动摘要。
(2) 第二代搜索引擎大约出现于1996年。这一时期的搜索引擎大概采用分布式方案来提高数据规模、响应速度等性能，并且在检索阶段开始采用数据挖掘等技术来提高结果的相关性；1997年8月出现的Northernlight是第一个支持对检索结果进行简单聚类分类的搜索引擎。这一时期也出现一种新的搜索引擎——元搜索引擎。用户只需提交一次搜索请求，由元搜索引擎负责提交给多个预先选定的独立搜索引擎，并将各独立搜索引擎返回的所有查询结果，集中起来处理后再返回给用户。第一个元搜索引擎是Washington大学硕士生Eric Selberg 和Oren Etzioni 在1995年开发的Metacrawler。
(3) 第三代搜索引擎大约出现于1998年。此时索引数据库的规模继续增大，并结合用户反馈信息进一步提高检索结果相关性。在1998年10月之前，Google只是Stanford大学的一个小项目BackRub。1999年2月，Google完成了从Alpha版到Beta版的蜕变。现在Google的数据库已经超过四十亿网页。除了数据规模的剧增，功能也变得多样，比如开始出现主题搜索和地域搜索。Google就包括PageRank、动态摘要、网页快照、多语言支持、用户界面等功能。
值得一提的是，2000年1月，两位北大校友，超链分析专利发明人、前Infoseek资深工程师李彦宏在背景中关村创立百度公司，并于同年10月正式发布Baidu搜索引擎，专注于中文搜索。Baidu搜索引擎的特色包括：百度快照、网页预览、相关搜索词、错别字纠正等特色搜索。凭借其多样的服务、简洁的界面和高效的性能，百度以纪念馆占领国内大部分市场份额。
(4) 为满足搜索需求的多样化和进一步提高相关性的要求，以主题搜索引擎为代表的第四代搜索引擎开始成为人们研究的热点。现在人们将更多的新技术融入到搜索引擎中，比如将人工智能技术融入爬虫的搜索策略，并结合自然语言处理技术来理解用户搜索行为，学习新词和提高搜索结果的相关性。网络上开始出现各种专业领域的搜索万站。
随着互联网规模的急剧膨胀，一家搜索引擎光靠自己单打独斗已无法适应目前的市场情况，因此现在搜索引擎之间开始出现了分工协作，并有了专业的搜索引擎技术和搜索数据库服务提供商。像国外的Inktomi，它本身并不是直接面向用户的搜索引擎，但像包括Overture、LookSmart等在内的其他搜索引擎提供全文网页搜索服务。
2
主题网络爬虫的研究与实现
1.3 国内外研究现状
人们于20世纪80年代开始对Web信息抽取技术进行研究，研究的方向主要集中在两个领域。一方面研究的主要目的是把网页中的无结构化数据或半结构化数据变成结构化数据，在这方面已有大量的研究工作，包括HTML结构分析方法(如XWRAP[2]和Lixo[3])、基于自然语言处理的方法(如SRV)、机器学习学习方法和基于Ontology方法等，这些方法通常是面向特定领域、特定网站或者目前针对特定格式。信息抽取另一方面的研究主要目的不是提取细粒度的数据而是提取标题、正文等主题内容或兴趣区域，本章将介绍这一领域的研究现状[4]。
在国外方面，Finn等人将HTML文档看作字符和标签组成的序列，在字符集中的区域提取文字。这种方法仅适合主题文字集中的网页，如果段落间有表格或链接标签丰富的结构，就不能有效处理。Kaasinen等人提出Desk-Card模型，将网页(Desk)分为若干Card，每次显示一个Card，减少了页面大小，但是没有提取出信息，用户需要阅读多个Card才能确定主题。Buyukkokten等人提出了STU模型，STU对应网页中的快(block)，将网页分割为平行的STU，Desk-Card模型和STU模型都采用了分块思想，后者减少了定位时间，但是它们都改变了源网页的结构和内容，而且没有提取出主题信息，保留了无关的文字和链接。Gupta等人的方法是从网页中删除无关部分，维持了网页的结构和内容，但在删除链接较少考虑上下文的语义，极易删除正文中的链接列表，使提取结果不完整。
在国内方面，对网页中主题内容的抽取近年来也被广泛的研究。王琦等基于DOM规范，针对HTML的半结构化特征和缺乏语义描述的不足，提出含有语义信息的STU-DOM模型，它以STU节点内的链接数和非链接文字数为节点的语义信息，将HTML文档转换为STU-DOM树，并对其进行基于结构的过滤和基于语义的剪枝。胡国平等人针对新闻网页，提出了基于统计的正文抽取的方法，它只适合于一个网页中所有正文信息都放在一个TABLE中的情况。孙承杰等将节点内非链接文字、链接文字占本节点文字以及整棵HTML树的比例，以及节点是否出现TABLE、DIV、TR、TD标签等方面的信息作为节点的特征向量，提出了基于双层决策的正文抽取策略，并利用特征向量提取和决策树算法对上述决策进行建模。
主题爬虫就是根据一定的网页分析算法过滤与主题无关的链接，保留主题相关的链接并将其放入待抓取的URL队列中;然后根据一定的搜索策略从队列中选择下一个要抓取的网页URL，并重复上述过程，直到到达系统的某一条件时停止。所有被爬虫程序抓
3
主题网络爬虫的研究与实现
取的网页将会被系统存储，进行一定的分析，对于主题爬虫来说，这一过程所得到的分析结果还可能对后续的抓取过程进行反馈和指导。为了高效地抓取与主题相关的信息资源，研究者提出了许多主题定制策略和相关算法，使得主题爬虫尽可能多地爬行主题相关的网页，尽可能少的爬行无关网页，并且确保网页的质量。通过分析比较，本文将它们分为如下四类。
(1) 基于文字内容的启发式方法
基于文字内容的启发策略主要是利用了Web网页文本内容、URL字符串、锚文本等文字内容信息。不同的分析方法构成了不同的启发策略和相应的算法。主要包括:
① Best first search方法:基本思想是给定一个待爬行URL队列，从中挑选最好的URL优先爬行。爬行主题采用关键词集合来描述，待爬行URL的优先级是根据主题词和已爬行网页p的文字内容来计算，用它们的相关度来估计p所指向网页的相关度。相关度大的网页，它所指向的网页优先级就高，从而决定了待爬行队列中URL的优先级顺序。在主题爬虫研究领域，该算法具有一定的竞争力，所以很多研究者将其作为算法性能的比较基准。
② Fish search方法。 1994年由学者De Bra等人[5]提出。它将在网络上遍历的爬虫比喻成海里的一群鱼，当它们发现食物(相关信息)时，这些鱼就继续繁殖，寻找新的食物;当没有食物时(没有相关信息)或水被污染(带宽不够)时，它们就死掉。该算法的关键是根据代表用户感兴趣主题的种子站点和主题关键词，动态地维护待爬行的URL优先级队列。
③ Shark search方法[6]。它在 Fish seareh算法的基础上进行了改进。此算法综合考虑网页以及链接文本的相关性，对网页中的U甩按照优先权值进行排序，通过乘上一个衰减因子来继承父页面的相关性。与fish算法相比，Shark算法精确度高，能更好地保证爬行器正确的搜索方向，提高相关信息的发现率。
(2) 基于Web超链接结构图评价的方法
基于Web图的启发策略的基本思想来自于文献计量学的引用分析理论。尽管引用分析理论的应用环境与Web并不相同，但到目前为止，网页之间的超链接还是比较有价值的一种信息。基于Web超链接结构图评价的爬行算法有以下几种:
① BackLink:一个网页被其他网页所引用的次数越多，就说明越重要。待爬行URL队列按照BackLink的数量来排序，数量大的优先爬行。
② PageRank:基于Web图，首先计算每个网页的PageRank值，然后对待爬行URL队列按照PageRank的值进行排序。
4
主题网络爬虫的研究与实现
PageRank算法是由Google的创始人S.Brin和LPage提出的，它是一种与查询无关的算法[7]。在BackLink算法中，一个网页的链入网页数量越大，它的重要性就越大，而没有考虑入链的质量问题。实际上，不同质量的网页对网页重要性的贡献是不同的。简单地说，按照BackLink算法，要想提高某网页的重要性，只要建立许多网页指向它就可以了。S.Brin和L.Page提出的PageRank算法就是为了克服BackLink的这种不足而设计的。
(3) 基于分类器预测的方法
为了克服基于文字内容难以精确描述用户感兴趣的主题，研究者提出了基于分类器导引的主题爬虫[8]，从而可以基于分类模型来描述用户感兴趣的主题和预测网页的主题相关度。通过文本分类模型可以从更深的层次来描述用户感兴趣的主题信息，并可以更加准确地计算网页的主题相关性，而不只停留在基于关键词的匹配上。文本分类技术应用于主题信息搜索中有利于提高主题搜索的正确率和准确率。Chakrabarti等人提出了分别基于两种不同的模型来计算网页主题相关性和URL访问次序。计算网页主题相关性的模型可以是任何二值分类器，而计算机URL访问次序的模型(简称为apprentice)是通过包含父网页和子网页及其相关度的训练样本集合在线训练得到的。傅向华等人将Web爬行看作执行序列动作的过程，结合改进的快速Q学习和半监督贝叶斯分类器，提出了一种新的具有在线增量学习能力的聚焦爬行方法。李盛稻等人在分析主题web信息采集基本问题的基础上，提出了主题爬虫的难点以及相关的解决方案。
(4) 其他主题爬行方法
J.Cho等人[9]提出通过先爬行更重要的网页使得爬行更有效，而提出了各种计算网页重要性的方法，如网页与查询项的相关性、指向该网页的网页个数(BackLinks)、该网页的PageRank值和该网页所出的位置。M.Diligenti等人提出了使用上下文图表来引导主题爬虫，作者认为该领域主要的问题是在爬行中把任务分配给网页。C.Aggarwal等人提出了Web主题管理系统(WTMS)，他们使用主题爬行技术，只下载相关网页附近的网页(如双亲、孩子和兄弟)。
1.4 本文的主要工作和论文结构
本文在通用爬虫的基础之上，通过引入网页预处理，对网页的内容和链接结构做深入细致的分析，改进传统的权值计算方法，利用空间向量模型，从而实现主题爬虫的搜索策略，本文的研究内容体现在以下四个方面:
(1) 爬虫部分，根据主题和种子网站，在信息网上尽可能地下载与主题相关的网页到
5
主题网络爬虫的研究与实现
mirror中。
(2) HTML解析策略，通过对HTML语法的分析，对网页进行解析，分析得到网页的URL地址、标题title、内容context等内容。
(3) 主题相关度算法，本论文对传统的TF-IDF算法进行了改进，并结合VSM算法，对各个网页的title进行相关度排序，使相关度比较高的网页排在呈献给用户的前面，提高爬虫的搜索准确度和效率。
(4) 在实现简易爬虫基础上，结合实际数据分析了爬虫的搜集效率。 本文共分五章，篇节安排如下:
第一章，绪论:介绍了Internet和搜索引擎的发展历史，网络爬虫的国内外研究现状，以及本文研究内容和篇章结构。
第二章，主题爬虫简介:阐述了网络爬虫在搜索引擎中的重要地位，分析介绍了网络爬虫的结构及基本原理，然后分析了网络爬虫的分类以及这几种分类的比较，结合主题页面的分布特性、网页内容以及链接结构，提出了主题爬虫的设计目标。
第三章，介绍了网络爬虫设计到的关键算法：首先讲述了主题爬虫的搜索策略，分别说明基于内容和基于链接结构评价的搜索策略的原理。然后介绍了Web结构链接挖掘算法，PageRank和HITS算法，分析了它们的工作原理和比较。最后介绍了主题相关性算法。
第四章，主题爬虫的分析与设计：该章介绍具体的爬虫设计过程。先讲述网络爬虫的爬虫工作过程，然后讲述了HTML解析方法和策略，接着重点分析主题相关性判断算法——TF-IDF算法以及改进和VSM算法，最后介绍了如何建立索引。
第五章，总结与实现。
6
主题网络爬虫的研究与实现
第二章 网络爬虫工作原理
本章主要介绍构建一个网络爬虫系统所需的基础知识和框架，为实现网络爬虫程序打下基础。
网络爬虫是一个自动提取网页的程序，它为搜索引擎从万维网上下载网页，是搜索引擎的重要组成。传统爬虫从一个或若干个初始网页的URL开始，获得初始网页上的URL，在抓取网页的过程中，不断从当前页面上抽取新的URL放入队列，直到满足系统的一定停止条件。主题爬虫的工作流程较为复杂，需要根据一定的网页分析算法过滤与主题无关的链接，保留有用的链接并将其放入等待抓取的URL队列。然后，它将根据一定的搜索策略从队列中选择下一步要抓取的网页URL，并重复上述过程，直到达到系统的某一条件时停止。另外，所有被爬虫抓取的网页将会被系统存贮，进行一定的分析、过滤，并建立索引，以便之后的查询和检索；对于主题爬虫来说，这一过程所得到的分析结果还可能对以后的抓取过程给出反馈和指导。
2.1 网络爬虫在搜索引攀中的地位
搜索引擎的工作原理基本都是一样的，利用一个称为网络爬虫Cwarler(也叫做网络蜘蛛Spider或网络机器人Robot)的程序，本论文统一称为网络爬虫，采用多线程并发搜索技术，在互联网中访问各节点，定期搜索信息，抓取网页，并根据网络链接提取其他网页，对网页进行分析，提取关键词、URL等信息，然后索引器对爬虫所提取的信息进行排序并存入索引数据库，用户可以通过用户接口输入所需信息的关键词进行查询，检索器则根据用户提交的关键词在索引数据库中查找相关信息，并按照相关度进行排序输出。
因为搜索引擎与网络用户的关系非常密切，因此它一直专注于在三个方面提升用户的体验度，即为准、全、快。用专业术语讲就是:查准率、查全率和搜索速度(即搜索耗时)。其中比较容易提高的是搜索速度，因为对于搜索耗时在1秒以下的系统来说，用户已经很难辨别其快慢了，再加上网络速度的影响，就更难分辨搜索引擎本身的搜索速度。因此，对搜索引擎的评价就集中在了另外两方面:准和全。搜索引擎的查全需要保证一些比较重要的结果不被遗漏，而且能够找到最新的网页，这需要搜索引擎有一个强大的网页收集器，即网络爬虫;搜索引擎的查准，则需要保证搜索的前几十条结果都和搜索的关键词的相关度很高，即使用户很满意，这是由排序技术来决定的。
搜索引擎是一个技术含量很高的网络应用系统。它包括网络技术、数据库技术、检
7
主题网络爬虫的研究与实现
索技术、语言处理技术及智能技术等等。
各种搜索引擎虽然在设计细节上有所不同，但是基本构造通常都可分为四部分：网络爬虫、索引模块、信息检索和用户接口，功能如下所述[10]:
(1) 网络爬虫:网络爬虫Crwaler日夜不停地在互联网的各节点中自动爬行，从一个或一组URL开始访问，并尽可能多、尽可能快地从中发现和抓取信息。因为互联网上的信息更新很快，所以还要定期更新己经搜集过的旧信息，以避免死链接和无效链接。
(2) 索引模块:索引分析器Indexer对网络爬虫所下载的页面进行分析，过滤掉无用的信息，把文件表示成一种便于建立索引的方式，抽取最优索引信息以表示文档，并利用所抽取信息建立索引数据库，从而使用户能够很容易的查找到所需要的信息。硕生:论文搜索引擎中主题爬虫的研究与实现
(3) 信息检索:检索器Searcher根据用户查询的关键词从索引数据库中快速查找相应的文档，并进行相关度的计算，然后将输出结果按照相关度排序回馈给用户，其中检索算法、信息查询和组织的方式都会在很大程度上影响检索模块的系统性能。
(4) 用户接口:提供用户与搜索引擎的交互窗口，用于关键字的输入，查询结果的输出，用户接口应尽量设计的人性化。
搜索引擎虽然外在表现呈现出多样化，所提供的功能也有所不同，但是就其实现来说，构造基本都是一样的。本论文所讨论的搜索引擎其结构分为四部分，即上文所提到的网络爬虫、索引模块、信息检索以及用户接口。网络爬虫在搜索引擎中占有重要地位，对搜索引擎的查全、查准都有一定程度的影响，它决定了搜索引擎数据容量的大小，而且网络爬虫设计得好与坏直接影响搜索结果页面中的优等页面和死链接(即链接所指向的网页已经不存在)的个数。目前如何发现更多的网页、如何正确提取网页内容、如何提高信息抓取的速度以及如何识别网站中内容相同的网页等都是网络爬虫需要进一步改进的问题。
根据上文的讨论，可以得到搜索引擎的基本框架结构以及网络爬虫在搜索引擎中的位置如图2-1所示。
本论文的主要研究工作就是针对图中网络爬虫部分的分析，在文章的接下来部分将对其进行讨论，详细介绍网络爬虫的工作原理以及功能等。
8
主题网络爬虫的研究与实现
图2-1 搜索引擎体系结构
2.2 网络爬虫的基本原理
主题爬虫又称网络蜘蛛，即Web Spider，是一个很形象的名字。把互联网比喻成一个蜘蛛网，那么Spider就是在网上爬来爬去的蜘蛛。网络蜘蛛是通过网页的链接地址来寻找网页，从网站某一个页面（通常是首页）开始，读取网页的内容，找到在网页中的其它链接地址，然后通过这些链接地址寻找下一个网页，这样一直循环下去，直到把这个网站所有的网页都抓取完为止。如果把整个互联网当成一个网站，那么网络爬虫就可以用这个原理把互联网上所有的网页都抓取下来。下面大体介绍主题爬虫的工作原理。
2.2.1 主题网络爬虫的体系结构
主题网络爬虫系统选择种子网页，解析出其中的链接并保存到URL队列，Crawler管理器负责分配爬虫程序下载目标网页，其URL 及经过Web分析器分析后得到的其它相关信
9
主题网络爬虫的研究与实现
息将被存放到候选网页队列，相关信息包括网页内容主题相似度，种子页面到该网页的链接数目，及网页到种子网页集的链接数目。每个阶段开始，系统将在己经抓取并被保存在候选网页队列中的网页中选择相关度权值最高的网页作为种子网页。主题爬虫系统的系统结构如图2-2所示[11]。
图2-2 主题爬虫的系统结构
2.2.2 系统模块功能说明
这一节我们将详细说明各个模块的主要功能。
(1) 种子网页集:在系统初始阶段，我们将指定一个网页作为系统的种子网页(Yahoo首页，hub网页)。在每个子阶段开始，系统将会从候选网页队列中选择相关度权值最高的网页作为种子网页。
(2) URL 队列:种子网页中会存在大量指向其它网页的链接。这些URL将被提取出来并存放到URL 队列中，等待爬虫管理器分配给爬虫程序。
(3) Crawler管理器:Crawler管理器组件主要功能是管理爬虫程序从网络中下载相关Web页面。它首先从URL队列中取得URL，并将它存放到一个URL缓冲区中(该缓冲区是一个FIFO队列)。动态创建爬虫程序下载目标URL文件。同时爬虫管理模块还监视爬虫工作状态，来控制爬虫的爬行速度，以及控制爬虫程序间的负载平衡。
(4) Crawler:爬虫是主要负责下载爬虫管理器提供的URL地址目标文件。每个爬虫程序都拥有一个自己的URL 队列用来保存需要下载的Web的URL。爬虫从队列中取得URL，访问并下载相关Web文件。同时，其它爬虫可能访问同一Web服务器，从而导致服务器的过载。因此我们引入一个防止服务器过载模块，该模块存放爬虫己经发出访问请求并等待
10
主题网络爬虫的研究与实现
服务器响应的URL。如果之前没有对该URL的Web服务器的访问请求，针对该URL的访问请求将立即发送到HTTP模块，否则进入等待访问URL队列。
(5) 防止服务器过载模块:Crawler程序非常消耗服务器资源，同时占用大量带宽，如果不对Crawler的抓取目标进行控制，很可能导致众多Crawler同时访问同一Web服务器，造成服务器过载，爬虫程序的性能急剧下降，网络阻塞。所以该模块将限制Crawler对服务器的同时访问。
(6) URL解析器:URL解析器模块从Web数据库中提取得Web文件，并解析出其中的URL地址和网贞内容，删除重复的URL地址。然后该模块将相关信息(URL地址，内容)传送给Web分析器。
(7) Web分析器:Web分析器组件接受URL解析器模块传送过来的网页相关信息计算网页的相关度权值。然后将网页URL，相关度权值，网页到种子页面集的链接数目，种子页面集到该网页的链接数目，网页内容的主题相似度等信息存放到候选网页队列中。
(8) 种子网页选择器:种子网页选择器负责从候选网页队列中选择相关度最高的网页作为系统的种子网页。并修改候选网页队列中的存储的网页的相关链接数目信息，并重新计算相关网页的相关度权值。
2.3 内容提取
搜索引擎建立网页索引，处理的对象是文本文件。对于网络爬虫来说，抓取下来网页包括各种格式，包括html、图片、doc、pdf、多媒体、动态网页及其它格式等。这些文件抓取下来后，需要把这些文件中的文本信息提取出来。准确提取这些文档的信息，一方面对搜索引擎的搜索准确性有重要作用，另一方面对于网络爬虫正确跟踪其它链接有一定影响。
对于doc、pdf等文档，这种由专业厂商提供的软件生成的文档，厂商都会提供相应的文本提取接口。网络爬虫只需要调用这些插件的接口，就可以轻松的提取文档中的文本信息和文件其它相关的信息。
HTML等文档不一样，HTML有一套自己的语法，通过不同的命令标识符来表示不同的字体、颜色、位置等版式，提取文本信息时需要把一些不需要的标识符都过滤掉。过滤标识符并非难事，因为这些标识符都有一定的规则，只要按照不同的标识符取得相应的信息即可。但在识别这些信息的时候，需要同步记录许多版式信息，例如文字的字体大小、是否是标题、是否是加粗显示、是否是页面的关键词等，这些信息有助于计算单
11
主题网络爬虫的研究与实现
词在网页中的重要程度。同时，对于HTML网页来说，除了标题和正文以外，会有许多广告链接以及公共的频道链接，这些链接和文本正文一点关系也没有，在提取网页内容的时候，也需要过滤这些无用的链接。例如某个网站有“产品介绍”频道，因为导航条在网站内每个网页都有，若不过滤导航条链接，在搜索“产品介绍”的时候，则网站内每个网页都会搜索到，无疑会带来大量垃圾信息。过滤这些无效链接需要统计大量的网页结构规律，抽取一些共性，统一过滤；对于一些重要而结果特殊的网站，还需要个别处理。这就需要网络蜘蛛的设计有一定的扩展性。
对于多媒体、图片等文件，一般是通过链接的锚文本（即，链接文本）和相关的文件注释来判断这些文件的内容。例如有一个链接文字为“张曼玉照片”，其链接指向一张bmp格式的图片，那么网络蜘蛛就知道这张图片的内容是“张曼玉的照片”。这样，在搜索“张曼玉”和“照片”的时候都能让搜索引擎找到这张图片。另外，许多多媒体文件中有文件属性，考虑这些属性也可以更好的了解文件的内容。
动态网页一直是网络蜘蛛面临的难题。所谓动态网页，是相对于静态网页而言，是由程序自动生成的页面，这样的好处是可以快速统一更改网页风格，也可以减少网页所占服务器的空间，但同样给网络蜘蛛的抓取带来一些麻烦。由于开发语言不断的增多，动态网页的类型也越来越多，如：asp、jsp、php等。这些类型的网页对于网络蜘蛛来说，可能还稍微容易一些。网络蜘蛛比较难于处理的是一些脚本语言（如VBScript和javascript）生成的网页，如果要完善的处理好这些网页，网络蜘蛛需要有自己的脚本解释程序。对于许多数据是放在数据库的网站，需要通过本网站的数据库搜索才能获得信息，这些给网络蜘蛛的抓取带来很大的困难。对于这类网站，如果网站设计者希望这些数据能被搜索引擎搜索，则需要提供一种可以遍历整个数据库内容的方法。 对于网页内容的提取，一直是网络蜘蛛中重要的技术。整个系统一般采用插件的形式，通过一个插件管理服务程序，遇到不同格式的网页采用不同的插件处理。这种方式的好处在于扩充性好，以后每发现一种新的类型，就可以把其处理方式做成一个插件补充到插件管理服务程序之中。
2.4 主题页面在web上的分布特征
从表面上看，Web上页面的分布杂乱无章，但是经过研究发现，其实主题页面的分布是有规律可循的，大致总结为四个特征:Hub特性、主题关联特性、站点主题特性、Tunnel特性[10]。通过对这些特性的研究，在爬虫进行基于主题的爬行过程中以找到一些对链接
12
主题网络爬虫的研究与实现
预测和页面过滤有用的规律。
(1) Hub特性
美国Cornell大学的J.Kleinberg发现Web上存在大量的Hub页面，这种页面不但含有许多出链，并且这些链接趋向于同一个主题。也就是说，Hub页面是指向相关主题页面的一个中心。另外，他还定义了权威页面(Authority)的概念，指其它许多页面都认为相关于某一主题的有价值的页面。好的Hub页面一般指向多个Authority的页面，而好的Authority页面会被多个Hub页面所指向。根据这个思想，他还提出了Authority and hubs算法，这个算法将在以后章节中介绍。
(2) 主题关联特性
在Hub特性的基础上，又有人提出了主题关联特性的概念。主题关联特性是指页面所包含的链接趋向于指向和该页面同主题的页面;对于链接到某主题页面的页面，它所包含的其它链接指向的页面也趋向于该主题。这实际上源于Hub特性，主要是从页面设计者的角度考虑的。页面设计者一般会把本页面指向于与本页面相关的其他页面。
(3) 站点主题特性
研究人员发现，一个站点趋向于说明一个或几个主题，并且那些关于同一主题的页面较紧密地在此站点内部链接成团，而各个主题团之间却链接较少。这应该与网站设计者的设计思路有关。每个网站在设计时都有目标，而这种目标一般就集中在一个或几个主题中。而网站的浏览者往往也有目标，他们一般也趋向于浏览同一主题的页面。网站设计者为了满足浏览者的实际需要而将相关内容紧密链接。
(4) Tunnel特性
Web中主题页面团之间往往要经过很多无关链接才能相互到达。这些无关链接就像一个长长的隧道，因此称为“隧道现象”(Tunnel)。主题爬虫在爬行时，Tunnel的存在将会对爬行的页面质量、覆盖率和准确度都造成极大地影响。在设计爬虫的搜索算法时，为了提高爬行页面的准确率，需要提高相关性判定阂值，这样将过滤掉大量的Tunnel，但同时也会丢掉Tunnel另一端的主题团，从而影响覆盖率。反过来，如果为了提高覆盖率而降低相关性判定阈值，就会混入大量的无关页面，从而影响准确率。为了解决这个问题，在设计链接预测算法时通过给被判定为不相关的链接一个再次被选择的机会，这个机会发生的概率一般要大于Tunnel出现的估计概率值。
13
主题网络爬虫的研究与实现
2.5 本章小结
本章从搜索引擎的角度出发，首先对搜索引擎的基本结构、原理和功能进行了分析和简单介绍，从而引出在搜索引擎中占有最重要地位的网络爬虫，接着对爬虫的结构和功能进行了详细介绍，并对其的各个部分和步骤进行了简要的说明，最后分析了主题页面在Web中的分布特征，为本论文以下内容的研究提供了理论基础。
14
主题网络爬虫的研究与实现
第三章 网络爬虫的关键算法
前面已经讲述了主题网络爬虫的结构和工作原理，这章主要介绍网络爬虫的关键算法。
搜索引擎中最关键的部分是网络爬虫，它的性能好坏直接影响着搜索引擎的整体性能和处理速度。网络爬虫的搜索策略与搜索引擎的性质和任务密切相关。传统的通用搜索引擎的主要目的是获得较高的Web覆盖率，尽可能多的下载网页，它的网络爬虫通常采用图的遍历算法(如广度或深度优先策略)来搜索Web;主题搜索引擎的特点是搜索的内容只限于特定的主题或专门的领域，因而在搜索过程中没有必要对整个Web进行遍历，只需要选择与主题页面相关的页面进行访问即可。即主题搜索引擎更注重下载网页的准确性，因此可以说主题信息搜索策略是主题搜索引擎技术的核心。对主题搜索引擎而言，决定网络爬虫搜索策略的关键是如何将不相关的网页快速地过滤并删除掉，因为网页过滤的速度和准确性将会直接影响网络爬虫的性能。以何种策略访问Web，成为近年来主题搜索引擎网络爬虫研究的焦点之一。为了优先爬行高质量的相关网页，研究者们设计了许多启发策略和相关算法，这些策略大致分为两大类:基于文字内容的搜索策略和基于Web图的超链接结构的搜索策略。
这一章将重点介绍本论文所设计的主题爬虫在设计和实现的过程中将会用到的各种关键算法及其思想[10]。
3.1 网页搜索策略
网页的抓取策略可以分为深度优先、广度优先和最佳优先三种。深度优先在很多情况下会导致爬虫的陷入(trapped)问题，目前常见的是广度优先和最佳优先方法。
(1) 广度优先搜索策略
广度优先搜索策略是指在抓取过程中，在完成当前层次的搜索后，才进行下一层次的搜索。该算法的设计和实现相对简单。在目前为覆盖尽可能多的网页，一般使用广度优先搜索方法。也有很多研究将广度优先搜索策略应用于聚焦爬虫中。其基本思想是认为与初始URL在一定链接距离内的网页具有主题相关性的概率很大。另外一种方法是将广度优先搜索与网页过滤技术结合使用，先用广度优先策略抓取网页，再将其中无关的网页过滤掉。这些方法的缺点在于，随着抓取网页的增多，大量的无关网页将被下载并过滤，算法的效率将变低。
15
主题网络爬虫的研究与实现
(2) 深度优先搜索策略
深度优先搜索策略是指网络爬虫会从起始页开始，一个链接一个链接跟踪下去，处理完这条线路之后再转入下一个起始页，继续跟踪链接。这个方法的优点是网络爬虫在设计的时候比较容易。
(3) 最佳优先搜索策略
最佳优先搜索策略按照一定的网页分析算法，预测候选URL与目标网页的相似度，或与主题的相关性，并选取评价最好的一个或几个URL进行抓取。它只访问经过网页分析算法预测为“有用”的网页。存在的一个问题是，在爬虫抓取路径上的很多相关网页可能被忽略，因为最佳优先策略是一种局部最优搜索算法。因此需要将最佳优先结合具体的应用进行改进，以跳出局部最优点。研究表明，这样的闭环调整可以将无关网页数量降低30%~90%。
3.2主题爬虫的搜索策略
基于通用网络爬虫的搜索引擎抓取的网页一般少于1 000 000 个网页, 极少重新搜集网页并去刷新索引. 而且其检索速度非常慢, 一般都要等待10 s甚至更长的时间. 随着网页页信息的指数级增长及动态变化, 这些通用搜索引擎的局限性越来越大, 随着科学技术的发展, 定向抓取相关网页资源的主题爬虫便应运而生.
主题爬虫的爬行策略只挑出某一个特定主题的主题爬虫会给它所下载下来的页面分配一个评价分, 然后根据得分排序, 最后插入到一个队列中. 最好的下一个搜索将通过对弹出队列中的第一个页面进行分析而执行, 这种策略保证爬虫能优先跟踪那些最有可能链接到目标页面的页面. 决定网络爬虫搜索策略的关键是如何评价链接价值, 即链接价值的计算方法, 不同的价值评价方法计算出的链接的价值不同, 表现出的链接的“重要程度”也不同, 从而决定了不同的搜索策略. 由于链接包含于页面之中,而通常具有较高价值的页面包含的链接也具有较高的价值, 因而对链接价值的评价有时也转换为对页面价值的评价. 这种策略通常运用在专业搜索引擎中, 因为这种搜索引擎只关心某一特定主题的页面.
3.2.1 基于内容评价的搜索策略
基于内容评价的搜索策略的主要特点是利用页面中的文本信息作为领域知识指导搜
16
主题网络爬虫的研究与实现
索，并根据页面或链接文本与主题(如关键词、主题相关文档等)之间相似度的高低来评价链接价值的高低。这类搜索策略的代表有Fish-Search算法、Shark-Search算法，下面分别介绍:
(1) Fish Seareh
Fish Search算法于1993年由荷兰TUE大学的Debra教授提出，并整合到了当时流行的Mosaic浏览器上，是实时搜索中比较有名的算法[12]。
该算法的关键是根据用户的种子站点和查询的关键词或短语，将包含查询串的页面看作与主题相关，计算该页面与主题的相关度，动态地维护待爬行URL的优先级队列URL_Queue。这个队列分为前端，中部和尾部三部分，另外还需要几个参数:depth,width和potential_score，分别用于记载被搜索网页的层深、每页最多分析的链接数目(在此，我们称其为孩子数)和URL的相关度。这个算法的基本思想是:它以一个URL为起始搜索网页，在搜索这个URL的基础上动态的建立一个列表，这个列表中包含有待搜索的URL。这个列表中的URL(即孩子链接)具有优先级的区分，优先级高的URL将排在列表中的前端，将会比排在列表后面的URL提前被搜索。在每一步开始时，取出列表中的第一个URL进行分析。如果该网页可以访问，则经过分析对它的potential--score赋值，并改变其相应的depth和width值，然后再重新进行下一个URL的检索。
FihsSeaerh算法的具体描述如下:
①从最初的URL列表中选择URL，并取得与之对应的网页文件，将这个文件与用户的查询内容对比，检查二者的相关性。
②给每个URL赋相应的depth值。如果这个文件是相关的，那么这个文件中所出现的URL的potential_score将被赋值为l，并获得一个最初设定的depth值。如果这个文件不相关，那么将这个文件中出现的URL的potential_score赋值为0.5或0两种值，获得的depth值将减少，具体赋值情况如③中维护方法所述。
③将此文件中的URL按下面的方法加入到URL列表中:
如果这个文件相关，则把这个文件前a*width个孩子(a是预定义的大于1的 常量)加入到URL_Queue的前端。
如果这个文件不相关，则把这个文件前width个孩子的URL加入到URL_Queue队列中紧挨着相关网页的孩子节点后面。
剩下的孩子URL加入到URL_Queue的尾部(也就是说只有在时间允许的情况下才有可能被爬行)。
17
主题网络爬虫的研究与实现
④在获取文件的时候，对Web服务器的传输速度进行监测，如果速率很低，则将文件中的URL的depth设为0。
⑤在经过一段特定的时间之后，或URL_Queue己为空时，停止运行。
Fish Search搜索算法是对鱼群捕食以及生产后代情况的模拟，对于查询相关的网页，适当地增加了搜索宽度，如上面算法中width增加了1.5倍，它表示鱼在找到食物之后可以生产更多的后代。搜索深度的增加表示，这些鱼还可以生产更多有用的后代。加入到URL_Queue列表尾部的URL表示鱼已经死了，这些URL只有在其他URL都访问完的时候才可能被访问到。
Fish Search鱼群搜索算法的核心是维护URL_Queue中URL项的顺序，它不像传统的搜索算法按照URL在父网页中出现的顺序来依次搜索，而是动态的根据
potential_score的值改变其在列表中的顺序，即改变网页被搜索的顺序，实现了可能的相关网页的优先处理。该算法的主要缺点是相关性计算过于简单，只有相关和不相关两种，其次每个节点的potential_score精度不高，只有三种情况(0、0.5、1)，因此不能精确代表网页相关度。
(2) Shark Search
针对Fish Search算法所存在的问题，Michael Hersovici对其进行改进，提出了Shark Search算法[13]，主要改进了页面与查询信息的相关度计算和potential_score的计算方法，具体改进如下:
①引入向量空间模型(后面章节会详细介绍)，计算页面与用户查询之间的相关度，改善对于相关度计算时的简单的两值判断所带来的问题，对相关度的值进行细化。
②考虑超链接附近的文字(锚文本及其上下文)所包含的提示信息，并计算其与用户查询之间的相关度。
上面所讨论的两种算法都是基于内容评价的搜索算法，根据语义相似度的高低决定链接的访问顺序。这类方法起源于文本检索中对文本相似度的评价，它的显著优点是计算量比较小。但是，因为Web页面不同于传统的文本，它是一种半结构化的文档，其中包含了许多结构信息，Web页面不是单独存在的，页面中的超链接在一定程度上表示了页面之间存在着某些关系。由于基于内容评价的网络爬虫忽略了这些信息，因而在预测超链接的价值方面存在一些缺陷，容易造成网页的误选。此外，评价的准确性也依赖于对主题关键词集合的选择和构建。
18
主题网络爬虫的研究与实现
3.2.2 基于链接结构评价的搜索策略
基于链接结构评价的搜索策略, 是通过对Web页面之间相互引用关系的分析来确定链接的重要性, 进而决定链接访问顺序的方法. 通常认为有较多入链或出链的页面具有较高的价值. PageRank 和Hits 是其中具有代表性的算法.
(1) PageRank算法
PageRank是Google算法的重要内容,该算法是1998年由斯坦福大学的Sergey Brin和Lawrence Page提出的[14]，2001年9月被授予美国专利，专利人是Google创始人之一拉里·佩奇（Larry Page）。因此，PageRank里的page不是指网页，而是指佩奇，即这个等级方法是以佩奇来命名的它独创的“链接评价体系”(PageRank 算法) 是基于这样一种认识, 一个网页的重要性取决于它被其它网页链接的数量, 特别是一些已经被认定是“重要”的网页的链接数量. PageRank 算法最初用于Google搜索引擎信息检索中对查询结果的排序过程,近年来被应用于网络爬虫对链接重要性的评价，Lawrence Page和Sergey Brin在个别场合描述了PageRank最初的算法。这就是：PR(A) = (1-d) + d (PR(T1)/C(T1) + ... + PR(Tn)/C(Tn)) 式中：
PR(A) :网页A页的PageRank值；
PR(Ti) :链接到A页的网页Ti的PageRank值； C(Ti) :网页Ti的出站链接数量； d :阻尼系数，0 页面A的PageRank值取决于那些连接到A的页面的PageRank的递归值。PR(Ti)值并不是均等影响页面PR(A)的。在PageRank的计算公式里，T对于A的影响还受T的出站链接数C(T)的影响。这就是说，T的出站链接越多，A受T的这个连接的影响就越少。PR(A)是所有PR(Ti)之和。所以，对于A来说，每多增加一个入站链接都会增加PR(A)。最后，所有PR(Ti)之和乘以一个阻尼系数d，它的值在0到1之间。因此，阻尼系数的使用，减少了其它页面对当前页面A的排序贡献。 (2) Authorities and hubs算法 HITS算法是Web结构挖掘中最具有权威性和使用最广泛的算法[15]。 其基本思想是利用页面之间的引用链来挖掘隐含在其中的有用信息（如权威性），具 19 主题网络爬虫的研究与实现 有计算简单且效率高的特点。HITS算法通过两个评价权值——内容权威度（Authority）和链接权威度（Hub）来对网页质量进行评估。 内容权威度与网页自身直接提供内容信息的质量相关，被越多网页所引用的网页，其内容权威度越高；链接权威度与网页提供的超链接页面的质量相关，引用越多高质量页面的网页，其链接权威度越高。 HITS算法认为对每一个网页应该将其内容权威度和链接权威度分开来考虑，在对网页内容权威度做出评价的基础上再对页面的链接权威度进行评价，然后给出该页面的综合评价。然而HITS算法也有其明显的不足。 首先，它完全将网页的内容或文本排除在外，仅考虑网页之间的链接结构来分析页面的权威性，这与现实网络中的权威页面相比，其不科学性显而易见。因为权威页面必须针对某一主题或关键词而言。某一页面对一确定主题的具有较大权威性的页面并不意味在其他与其无关的主题方面同样具有权威性。 其次一个页面对另一页面的引用有多种情况，其中包含了一页面对另一页面的认可，但除此之外也有其他目的链接，如为了导航或为了付费广告。而HITS算法在实现过程中均没有考虑以上情况．导致了结果与目标的差距。就HITS算法的思想与实现过程做了细致的研究与概括。 针对前面第一种不足，就有相关的学者提出了一种利用超链文字及其周围文字与关键字相匹配而计算超链权值的方法，并引入系数对周围文字和超链文字进行权值的相对控制，很好地将页面文本信息引入到HITS算法，提高了算法的可靠性，并在现实中取得了很好的效果。 对HITS算法的第二个不足，即非正常目的的引用．在HITS算法看来，也误认为是正常引用，导致实际结果与目标的出入。后来，经过不断的改进。HITS算法又引入了时间参数，即利用对一链接引用的时问长短来评价是否为正常引用。因为非正常链接其引用时问肯定不会很长（如交换链接、广告链接），相反，如果一页面对另一页面的链接时间较长，则必然反映此页面就是用户的寻找页面。即目标页面或至少是正常引用。 如果设定时间阀值，则可以将非正常引用的链接在HITS算法的实现过程中筛选出来。如设定访问时间少于１分钟者为非正常引用。另外可构造时间访问函数，控制权威页面的相对大小。如随访问时间的增大而其权威性也逐渐非线性增大．这样可为HITS算法的权威页面提供更合理、更科学的解释。链接稳定性，在外部链接的建设中，占据非常重要的地位。链接越稳定，对排名的帮助就越大。 20 主题网络爬虫的研究与实现 (3) 基于巩固学习的主题搜索 近年来对Web信息资源分布的研究表明很多类型相同的网站在构建方式上, 主题相同的网页在组织方式上都存在着一定的相似性, 有的学者就考虑将巩固学习引入网络爬虫的训练过程中, 从这些相似性获取一些“经验”, 而这些经验信息在搜索距相关页面集较远的地方往往能获得较好的回报, 而前两种策略在这种情况下容易迷失方向.在巩固学习模型中, 把网络爬虫经过若干无关页面的访问之后才能获得的主题相关页面称为未来回报, 对未来回报的预测值称为未来回报价值, 用Q价值表示. 这种方法的核心就是学习如何计算链接的Q 价值, 根据未来回报价值确定正确的搜索方向. 目前这类搜索策略不足之处在于学习效率低的问题, 而且在训练过程中增加了用户的负担. (4) 基于语境图的主题搜索 基于巩固学习的网络爬虫通过计算链接的Q价值可以确定搜索方向, 但它却无法估计距离目标页面的远近.为此, Diligent等提出了基于“语境图”的搜索策略, 它通过构建典型页面的web“语境图”来估计离目标页面的距离, 距离较近的页面较早得到访问. 基于“语境图”的搜索策略需要借助已有的通用搜索引擎构建“语境图”, 而搜索引擎的检索结果并非一定代表真实的web 结构, 因而这种方式也具有局限性。 3.3 主题相关性算法 3.3.1 向量空间模型(VSM) 搜索引擎的根源是传统的全文检索技术，搜索引擎沿用了传统的信息检索模型。在传统的计算文档相似度的算法中，以Salton教授提出的向量空间模型(Vector Space Model)应用最为广泛。向量空间模型基于这样一个关键假设，即组成文章的词条所出现的顺序是无关紧要的，它们对于文章的主题所起的作用是相互独立的，因此可以把文档看作一系列无序词条的集合。 VSM模型以特征项作为文档表示的坐标，以向量的形式把文档表示成多维空间中的一个点，特征项可以选择字、词和词组等(根据实验结果，普遍认为选取词作为特征项要优于字和词组)，表示向量中的各个分量。 它的基本思想是这样的，把文档di看成是由一组词条(T1，T2，„，Tn)构成的，对于每一个词条Ti，都可以根据它在文档中的重要程度赋予一定的权值Wi。可以将T1，T2，„，Tn看成一个n维坐标系，W1，W2„，Wn为对应的坐标值，因此每一篇文档都可被看作 21 主题网络爬虫的研究与实现 向量空间中由一组词条矢量构成的一个点(如图3-1所示)。 图3-1 VSM模型示意图 向量空间模型中文档的特征表示方法如下所描述： 在向量空间模型中，设D是一个包含m篇文档的文档集合： D = {di,…, db,…dm},i=1,2,…,m ; (3.3.1.1) 集合中的每篇文档di都被表示成如下形式的向量： Di = (wi1,…, wij,…, win),i=1,2,…,m; (3.3.1.2) 其中，wij表示第j个特征项Tj在文档di中的权值。 权值的计算有以下几种方法: 3．TF-IDF词频统计方法。该方法基于这样一个假设:在真实语料中，出现频率较高的词条(特征)带有较少的信息，而出现频率较少的词条带有较多的信息。TF-IDF的值表示权重，词条Tj在文档di中的TF-IDF值由下式定义： 22 主题网络爬虫的研究与实现 其中，TFi是词条Tj在文档di中出现的次数；DFi表示整个文档集D中包含词条Tj的文档数，称为文档频率，IDFi为DFi的倒数，称为反转文档频率；N表示统计语料中的文档总数。因此，文档di可以表示成一个特征向量: di=（wi1,…, wij,…, win） 本论文所用的是TF-IDF算法的改进算法。因为特征词可能出现的位置不同，所以它对网页的相关性提供的价值也不同。例如，出现在标题中的关键词是网页建设者提供的，而锚文本中的关键词是别人对该网页的客观评价。 3.3.2 页面主题相关性算法 页面主题相关度的计算有多种方法，例如Naive Bayes、神经网络(Neural Netwok)、实例映射模型、向量空间模型(VSM)等。其中向量空间模型对训练文档的要求较低，从少量的训练文档中就能提取出主要的目标特征，而且计算简单、正确率较高，比较适用于网络信息的发现。本论文采用的就是基于向量空间模型 VSM的简单向量距离算法。该算法的基本思想就是计算图3-1中两个向量之间夹角的余弦值，下面就对该算法进行介绍。 简单向量距离算法的实现步骤如下: ①将训练文档集中的文档表示成特征向量。 ②对于每一类中的特征项词条，计算其在该类所有文档特征向量中权值的算术平均值，作为该词条在类别特征向量中的权值。 ③用平均值构造类别特征向量。 ④将待分类的新文本表示成特征向量。 ⑤计算新文本特征向量和类别特征向量间的相似度。 ⑥比较每类类别特征向量与待分类文本之间的相似度，将文本分到相似度最大的那个类别中。 其中，di为待分类的文本的特征向量，di为第j类的中心向量，M为特征向量的维度， 23 主题网络爬虫的研究与实现 Wik和Wjk分别为向量的第k维在文本di和dj中对应的权值。Wk采用上节中的TF-IDF算法来计算。 3.4 本章小结 本章主要探讨了主题爬虫的搜索策略，主要分成两部分来讨论，基于Web链接结构的策略和基于网页内容的策略，最后对计算相似度的经典模型VSM和本论文所用到的相似度的计算方法进行了介绍，为本论文的主题爬虫的研究提了理论基础和技术指导。 基于Web链接结构评价的爬虫利用了链接的结构和页面之间的引用关系，但忽略了页面内容与主题相关性的判断，有时候会出现搜索结果偏离主题的“主题漂移”等问题。另外，爬虫在爬行的过程中为了维护爬行队列需要重复计算PageRank值或是Authority权重以及Hub权重，计算复杂度将会随着页面和链接数量的增长而增长。 基于内容评价的网络爬虫，根据网页内容相似度的高低决定链接的访问顺序，优点是计算简单。 24 主题网络爬虫的研究与实现 第四章 主题爬虫的分析与设计 通用网页爬虫的目标是尽可能多地搜集信息页面，而在这一过程中它并不太在意被搜集页面的相关主题。主题网页爬虫则是尽可能快地搜集尽可能多的与预先定义好的主题相关的网页。 为了实现网络爬虫的短响应时间、高覆盖率、高准确度，本论文在设计网络爬虫的时候，其主要设计目标有以下几点: (1) 良好的参数配置:本系统充分考虑了爬虫的运行中可能出现的不同情况，从而对一些参数进行修改，如初始地址、搜索的时间、连接重试次数以及开启的线程数量等。 (2) 主题自选性:本论文所实现的爬虫能够对不同的主题进行搜索，所涉及的搜索算法中会尽量获取并利用主题相关信息。 (3) 多线程:采用多线程处理技术可以提高主题爬虫的效率，能够并行执行和处理多任务。在爬行过程中，由于网络响应时间等原因，不同网页的下载时间都有差别，硕士论文搜索引攀中主题爬虫的研究与实现多线程的应用使URL得到并行处理，从而可以加快处理速度，有效利用网络带宽，并节约时间。 (4) 操作人性化:用户可以对系统多个参数进行实时调整以适应不同网络的需要，而且在系统的运行过程中随时可以进行暂停、继续和停止等操作。 (5) 一定的智能化。为了提高整个系统的查全率、查准率及搜索速度，搜索算法的设计具备一定的智能化，可以对主题相关性进行预测。 本章首先介绍了主题爬虫的体系结构;然后介绍了如何进行种子站点选取和URL队列维护；接下来描述了如何对下载下来的网页进行解析和建立索引；最后对这些下载下来的网页进行主题相关度判断，进行一些消噪等工作。 4.1 主题爬虫的体系结构 25 主题网络爬虫的研究与实现 图 4-1 主题爬虫的体系结构 图4-1给出了主题网络爬虫系统的系统结构。主题爬虫开始运行时，待搜集链接队 列（Link Queue）中保存的是种子链接，这些链接的获取以及排序方法将在4.3节中详细介绍。网页下载模块（Page Downloading）负责从Link Queue队列按照重要度值大小的原则提取链接并从信息网上下载相应的网页。页面内容抽取模块（Page Content Extraction）负责对搜集的网页进行内容提取，提取出网页的标题、正文等主题信息，另外本模块还负责抽取出网页中的链接已经链接对应锚文本和链接上下文。网页内容主题相关度评价模块（Page Content Relevanc Scoring）根据已经抽取的网页主题信息对网页进行主题相关度评价并保存到网页历史信息库中（Page history information）。链接重要度评价模块（Link Importance Scoring）根据链接对应的描述文档已经保存网页历史信息对链接的重要度进行评价，并按照值的大小插入到Link Queue中。 4.2 初始种子选取和URL队列维护 4.2.1 初始种子选取 主题爬虫的设计是以普通爬虫为基础, 对其进行功能上的扩充, 在对网页的整个 处理过程中需要增加如下模块: 主题确立模块、优化初始种子模块、主题相关度分析模块、排序模块。主题确立模块用于确立爬虫工作所面向的主题, 爬行模块用其进行网页主题相关度的计算。 初始种子模块用于生成面向特定主题的较好的种子站点, 使爬行模块能够顺利展开爬行工作Z由于主题爬虫是面向选定主题的, 所以初始种子的赋予应该来自相关主题本 26 主题网络爬虫的研究与实现 领域。具体作法是采用元搜索引擎搜索出网页, 从中选取质量较高的种子U RL , 通常由人工完成可信度会更高。 4.2.2 URL队列维护 为了能够方便地处理链接和主题相关度的计算, 使系统各组成模块能够有机地协调运作, 需要使用5个URL 队列, 每个队列保存着同一处理状态的URL 。 (1) 等待队列 在这个队列中,URL 等待被爬虫处理, 新发现的U RL 加入到该队列； (2) 处理队列 爬虫开始处理URL 时, 被传送到处理队列, 为了保证同一个U RL 不能多次被处理, 当一个URL 被处理后, 被移送到错误队列或者抛弃队列或者完成队列； (3) 错误队列 如果在下载网页时发生错误, 它的URL 将被加入到错误队列, 一旦移入错误队列,爬虫不会对它做进一步处理； (4) 抛弃队列 如果下载网页没有发生错误, 且经过主题相关度的计算小于阈值, 则放入该队列, 一旦移入抛弃队列, 爬虫不会对它做进一步处理； (5) 完成队列 如果下载网页没有发生错误, 且经过主题相关度的计算大于等于阈值, 就要把从中发现的URL 放入等待队列, 处理完毕把它加入到完成队列, 到达这一队列后等待排序模块的处理Z同一时间一个URL 只能在一个队列中, 这也叫做URL的状态, 图4-2说明了这些状态的关系以及网页如何从一个状态转换到另一个状态。 图4-2 URL状态流程图 27 主题网络爬虫的研究与实现 4.3 网页解析 前面爬虫部分已经根据种子站点进行了响应的爬行和搜索，并将相关性可能性比较大的站点下载到镜像中，但是如何得到这些网页的具体信息，比如URL、title、context等具体内容，我们必须要对下载下来的镜像文件进行解析，下面具体介绍HTML语法的解析。 4.3.1 HTML语法的分析 因为Web中的信息都是建立在HTML协议之上的，网页采用了半结构化的HTML语言，包含有丰富的结构信息，在抽取网页的主题内容时应加以利用。所以，网络爬虫在搜索网页时的第一个问题就是如何解析HTML。在讨论如何解析HTML语法之前，先来介绍一下HTML中的几种数据: (1) 标记:出现在正文中分别以字符“<”和字符“>”表示开始和结束的一个字符串。不考虑正文、单纯研究标记中所包含的语义信息是没有意义的。页面分析器在读取到“<”后将生成一个标记结构，并将该标记后面的标记名称、标记中的参数等都记入这个结构中，其中参数由多个参数名/值对组成。当读到“>’’时表示标记结束。若在‘，<”后紧跟着字符“/’’，则表明此标记是个结束标记。标记中所包含的信息主要是为了对文中同一位置的关键词的重要程度给以不同的表示。比如各级小标题(代码为 (2) 文本:所能看到的HTML页面上的文字部分，除了脚本和标记之外的所有数据，是页面的初始状态。脚本语言是包含在HTML文档内的程序代码。文本是格式化的，并且受嵌套它的标签控制。 (3) 标题:即网页源代码中用 (4) 超链接:链接元素用来描述两个文档或者文档和URL之间的关系。整个WWW世界就是通过这样的超链接连起来的。网络爬虫程序正是通过超链接在网络中不断的爬行提取数据。通常，一个页面上的链接所指向的页面基本和本页内容都有一定关系的。 28 主题网络爬虫的研究与实现 4.3.2 网页中信息资源的提取 在本系统中，网页处理模块先将HTML文本以数据流的形式读入缓存，然后根据输入流中的当前字符执行相应的语义操作。我们需要分析HTML网页文本，得到其中记载的超链接信息和正文文本，从而为搜索策略提供这些信息对相关度的贡献情况。硕士论文搜索引擎中主题爬虫的研究与实现下面分别介绍超链接信息的提取和正文的提取。 (1) 超链接信息的提取 超链接中所含信息包括超链接的URL地址和网页中对超链接的文字说明。例如在HTML语句: 中，对超链接的文字说明为与标记间的文字，即“进口汽车”;超链接的URL地址为“„/„/„/jinkouqiche„html”。超链接的文字说明和URL地址中都含有很重要的信息。对于主题爬虫来说，提取超链接中的信息是很重要的，链接的提取是为了程序的持续运行，而文字说明则是为了提取相关度更高的页面。具体操作流程如下所述: ①分析器从页面队列中取出一个页面文件，首先判断其页面类型。我们只处理“text/html”类型的页面。如对于:如果content不是“text/html”，放弃该网页，重新第l)步操作。如果页面队列为空，则转到第5)步。 ②依次读取缓存中的文件数据流，如果遇到如下标记 ④链接信息提取结束。 29 主题网络爬虫的研究与实现 以上所提取出来的信息将被用于网页相关度的预测算法中，具体应用在上一节有详细介绍。 (2) 正文的提取 虽然我们已经提取出URL及其相关信息，从而可以预测该URL是主题相关的，但是实际上，爬虫虽然在相关度预测算法的指导下对页面进行爬取，但仍会有部分相关度不高甚至不相关的页面产生，因此，为了对这些页面进行过滤，就要进一步通过页面内容与主题进行比较，通过计算结果过滤掉无关页面，从而提高主题爬虫信息采集的准确率。所以准确有效地提取已爬行下来的网页的正文对主题爬虫系统来说是非常重要的。 正文的处理比较简单，由HTML的半结构化特性，只需根据不同的标记区分出页面标题和内容，分开存放即可。HTML文件的正文部分，范围在 ”，空格“ ’’等之类的标记，则需要单独处理。如果条件允许，网页正文的不同字体或字型之类的信息也要进行存储，用于VSM模型相关度的计算。提取页面特征时可以根据它们对主题相关性所贡献的重要性的不同为他们赋予不同的权值。 在得到正文信息后，通过3.3.2节中所提到的算法计算页面内容的主题相关度。值得一提的是，在实际中，组成特征向量的特征项的个数不宜过多，否则将会大大影响系统的处理速度。而且，有实验表明对某专业类别的前100个特征项(按权值从大到小排序)而言，仅前30个特征项就己经覆盖了该专业类的85%以上的文档信息详，从第60个以后的特征项对整个向量的影响就很小了。因此，为了提高内容匹配的实时性，在计算出文档中所有词条的权值后，要把权值由大到小排序，取权值较大的部分词条作为特征项参与相关度的计算。 4.4 主题相关性算法实现 前面爬虫部分已经将与主题具有相关性的网站下载了下来，并对这些网页进行了解析析，得到了每个网页的具体信息，但是有这么多的网页，不可能全部呈现给用户，用户也不想得到无关紧要的信息，所以我们必须给用户呈现的是用户所希望看到的网页，即与主题相关性比较大的网页，这就牵扯到了网络爬虫中最重要的核心算法——主题相关度算法，我们需要对网页的title、context等内容进行分析判断，本文主要对网页的title进行分析判断，并按照其与主题的相关性大小进行排序，从中就可以找到适合用户要求 30 主题网络爬虫的研究与实现 的网页，本文对于权值计算采用的比较经典的TF-IDF算法，主题相关度算法采用的是VSM算法。 4.4.1 分词算法 我们在进行关键词统计的时候，需要对每个网站的title进行分词。在做此工作前， 我们需要为某个主题定制一个相应的关键词词库，然后根据这些词库进行文档划分，便于以后的关键词统计。拿汽车主题来说，词库中除了简单的一些常见关键字之外，会有一些汽车的词库，这样对title进行分析，将每个关键词用“/”分开。 4.4.2 权值计算:TF-IDF算法 (1) 简介：TF-IDF（term frequency–inverse document frequency）是一种用于资讯检索与资讯探勘的常用加权技术。TF-IDF是一种统计方法，用以评估一字词对于一个文件集或一个语料库中的其中一份文件的重要程度。字词的重要性随著它在文件中出现的次数成正比增加，但同时会随著它在语料库中出现的频率成反比下降。TF/IDF的概念被公认为信息检索中最重要的发明。TF-IDF加权的各种形式常被搜寻引擎应用，作为文件与用户查询之间相关程度的度量或评级。 (2) 原理： 在一份给定的文件里，词频 (term frequency, TF) 指的是某一个给定的词语在该文件中出现的次数。这个数字通常会被正规化，以防止它偏向长的文件。 逆向文件频率 (inverse document frequency, IDF) 是一个词语普遍重要性的度量。某一特定词语的IDF，可以由总文件数目除以包含该词语之文件的数目，再将得到的商取对数得到。 TF*IDF就可以得到该词的权重。 比如document1的term总量为1000，k1,k2,k3在document1出现的次数是100，200，50。包含了 k1, k2, k3的docuement总量分别是1000， 10000，5000。document set的总量为10000。则： TF1 = 100/1000 = 0.1 TF2 = 200/1000 = 0.2 31 主题网络爬虫的研究与实现 TF3 = 50/1000 = 0.05 IDF1 = log(10000/1000) = log(10) = 2.3 IDF2 = log(10000/100000) = log(1) = 0; IDF3 = log(10000/5000) = log(2) = 0.69 这样关键字k1,k2,k3与docuement1的相关性= 0.1*2.3 + 0.2*0 + 0.05*0.69 = 0.2645.其中k1比k3的比重在document1要大，k2的比重是0. (3) 实现代码： public static String[][][] selectFeatureByTFIDF(List } px(waitSelect, tfidfHM); for (int m = 0; m < fileLen; m++) { 32 Map // TODO Auto-generated method stub String[] waitSelect = new String[wordList.size()]; int i = 0; for (String word : wordList) { } String[][][] featureVSM = new String[pages.size()][Dimensionality][2]; int[] nj = new int[wordList.size()]; int k = 0; for (String word : wordList) { } Map for (int n = 0; n < wordLen; n++) { double subValue = 0; subValue = wordInFileHM.get(\"page\"+m + \"/\" + waitSelect[n]) } } double v = tfidfHM.get(waitSelect[n]); tfidfHM.put(waitSelect[n], v + subValue); tfidfHM.put(\"page\"+m + \"/\" + waitSelect[n], subValue); * Math.log(totalWordHM.get( \"totalWords\" + \"/\" + \"allFiles\").doubleValue()/ nj[n]); for (int j = 0; j < pages.size(); j++) { } k++; if (wordInFileHM.get(\"page\"+j + \"/\" + word) != null) { } nj[k]++; waitSelect[i++] = word; 主题网络爬虫的研究与实现 } for (int n = 0; n < Dimensionality; n++) { } featureVSM[m][n][0] = waitSelect[n]; if (wordInFileHM.get(\"page\"+m + \"/\" + waitSelect[n]) == null) { } featureVSM[m][n][1] = String.valueOf(0); featureVSM[m][n][1] = String.valueOf(tfidfHM .get(waitSelect[n])); } else { return featureVSM; } (4) TF-IDF的缺点 TF-IDF算法是基于这样一种假设：对区别文档最有意义的词语应是在某些文档中出现频率高，但在整个文档集合的其他文档中出现频率小的词语。TF-IDF权值计算的基础是词语的出现频率和文档频率。 传统TF-IDF算法有一定的缺陷，如在某些特征的文档频率近似的情况下，权值就完全取决于词频。如假设有两篇文档text1和text2，其中有两个特征term1和term2其分布如表4-1[1]： 表4-1 关键词分布表 关键词 text1 term1 term2 词频 text2 40 10 40 36 根据上面的公式得出的权值如表4-2： 表4-2 关键词权值分布表 关键词 text1 term1 term2 0.086427 0.077784 权值 text2 0.086427 0.021606 33 主题网络爬虫的研究与实现 从表4-1可以看出关键词term1和term2的文档频率都等于2，直观上，term2是更能区分文档1和2的，而term1更像一个停用词（分布均匀），也即直观上term2的权值应该比term1更大。从表4-2可以看出，term1的TF-IDF权值明显比term2要大，这个结果正好与直观相反。造成这个结果的原因是IDF在权重计算中失去了作用。某些关键词虽然文档频率高，但由于在文档集合的分布均匀，失去了对文档的区分能力；相反，某些关键词的文档频率小，但在文档集合的分布差异大，获得了较好的区分文档的能力。这种由于在文档集合的分布差异而产生的对文档的区分能力在TF-IDF公式中无法体现出来。进一步分析，如果某一类C中包含关键词t的文档数为m，而其它类包含t的文档总数为k，显然所有包含t的文档数n=m+k，当m大的时候，n也大，按照idf公式得到的idf的值会小，则表示该关键词t类别区分能力不强。但是实际上，m大，说明关键词t在C类的文档中频繁出现，就说明词语t能够很好地代表C类的文本特征，应该赋予较高的权重并选作该类文本的特征词。另一方面，虽然包含t的文档数n较小，但是如果其均匀分布在各个类间，这样的特征词不适合用来分类，应该赋予较小的权值，可是按照传统的tfidf算法计算其idf值却很大。TF-IDF算法产生上述这些缺点的原因主要是因为：TF-IDF公式是将文档集合作为整体来考虑的，特别是其中IDF的计算，并没有考虑到关键词在各个类别中的分布情况。 4.4.3 权值算法的改进：IG算法 TF-IDF算法的缺点在上节中已经提到过，关键词在文档集合的分布差异会使TF-IDF公式对文档的区分能力无法显示出来。 弥补这种差异的方法是将这种差异加权到权值计算公式当中。这种差异越大则所加的权值应越大，反之越小。方差可以代表数据的离散型，将方差加权到权值计算公式当中是一种体现上述差异的方法。 本文采用的是信息增益，信息增益也可以体现这种分布差异，信息增益是指期望信息或者信息熵的有效减少量。信息增益大的特征更能够区分不同的文档。为了体现关键词在各文档中分布差异对权重计算的影响，本文在权值计算公式中引出信息增益。以下是相关说明和具体应用： (1)熵和信息增益的定义 熵是德国物理学家克劳修斯1850年提出的[16]，表示一种能量在空间中分布的均匀程度，量分布得越均匀，熵就越大。1948年，Shannon把熵应用于信息处理， 34 主题网络爬虫的研究与实现 提出了“信息熵的”概念。信息熵（又称Shannon熵）在随机事件发生之前，它是结果不确定的量度；在随机时间发生之后，它是人们从该事件中所得到信息的量度（信息了量）。 信息论量度信息的基本出发点，是把获得的信息看作用以消除不确定性的东西，因此信息数量的大小，可以用被消除的不确定性的多少来表示。设随机事件X在获得信息y之前结果的不确定性为H（X），得到信息y之后为H（X/y），那么包含在消息y中的关于事件X的信息量：I（X，y）=H（X）- H（X/y）。 信息增益就是信息熵的差，表示为：IG（X，y）=H（X）- H（X/y）。 H（X）表示在观测信息y前，系统的熵。就文本分类系统来讲，H（X/y）表示一个随机文档落入某个类的概率的空间熵，即观察到y后对分类的不确定程度。这种不确定程度减少的量就是信息增益，即表示关键词y对分类的作用，关键词y所能提供的分类信息量。 (2) 使用信息增益计算关键词权重：IG算法 本论文从信息论的角度出发，把文档集合看作一个复合某种规律分布的信息源，依靠训练数据集合的信息熵和文档中关键词的条件熵之间信息量的增益关系确定该关键词在分本分类中所能提供的信息量，即关键词的重要程度，并把这种重要程度反映到词语的权重中，提出了IG算法，提高了传统TF-IDF的效果。公式如下[17]： IG的计算公式如下： (3) IG的算法的优点及分析 当关键词在文档集合的类别中分布不均匀时，即在某个类别中分布较高，其他 35 主题网络爬虫的研究与实现 类别中分布较少，关键词带有较大的类别信息，应用信息增益公式计算可得到较高的信息增益值，用上述公式计算所得的权重值也会较高，从而提高词语t的权重；另一方面当词语t在文档集合中的数量虽小，但是如果其均匀分布在各个类别间，则其带有的类别信息少，对系统的不确定性程度影响小，则由信息增益公式计算得到的信息增益值较小，用该公式计算关键词的权重也相对较低，因而改进的权重公式能很好的反应关键词在文档中的分布情况。 由表4-3的数据结合前面三个公式可以得到： 表4-3 信息增益计算结果表 H（D） H（D|term1） 1.0 1.0 IG（D|term1） IG（D|term1） 0 0.244624 H（D|term2） 0.755375 表4-4关键词的改进权值分布表 文档 Text1 Text2 由表4-2和表4-4课件，在改变权值计算公式前后，term1，term2的权值大小关系由W（term1）>W(term2)变成W(term1) public static void computePlusValue(Map Map 关键词权重 Term1 0 0 Term2 0.006710 0.018636 int fileLen = pages.size(); for (int i = 0; i < fileLen; i++) { for (String word : wordList) { 36 主题网络爬虫的研究与实现 } } } if (wordInFileHM.get(\"page\"+i+ \"/\" + word) != null) { } double wf, w, nwf, nf; wf = wordInFileHM.get(\"page\"+i + \"/\" + word).doubleValue(); w = wordHM.get(\"total\" + \"/\" + word).doubleValue(); nwf = totalWordHM.get(\"totalWords\" + \"/\" + \"page\"+i) } valueHM.put(\"page\"+i + \"/\" + word, subValue); double nwf = totalWordHM.get(\"totalWords\" + \"/\" + \"page\"+i) .doubleValue(); .get(\"totalWords\" + \"/\" + \"allFiles\").doubleValue() - wordHM.get(\"total\" + \"/\" + word).doubleValue(); double nf = totalWordHM .doubleValue() - wf; .doubleValue() - w; * Math.log(nwf / nf * fileLen); nf = totalWordHM.get(\"totalWords\" + \"/\" + \"allFiles\") double subValue = wf * Math.log(wf / w * fileLen) + nwf try { double v = valueHM.get(word); valueHM.put(word, v + subValue); valueHM.put(word, subValue); } catch (Exception e) { } else { double subValue = nwf * Math.log(nwf / nf * fileLen); try { } valueHM.put(\"page\"+i + \"/\" + word, subValue); double v = valueHM.get(word); valueHM.put(word, v + subValue); valueHM.put(word, subValue); } catch (Exception e) { 4.4.4 VSM算法 本论文采用的是vsm算法。前面第三章已经简述了VSM算法的思想，在上面利用 37 主题网络爬虫的研究与实现 TF-IDF算法得到了关键词的个数以及关键词向量，每个关键词的取值为它的权值，即 a=(a1, a2,…, an), i=1,2,…,n ai=wi 接下来对页面进行分析，统计关键词出现的频率，并求出频率之比，以出现频率最高的关键词作为基准，其频率用xi=1表示，通过频率比，求出其他关键词的频率xi，则该页面对应向量的每一维分量为xiwi，页面主题用向量表示为： b=(x1w1, x2w2,…x2w2),i=1,2,…n 用两个向量夹角的余弦表示页面的主题相关度： 指定一个阈值r，当cos 空间向量模型具有如下优点： （1）向量模型使得对查询向量中关键词权重的赋值成为可能，也就是可以查询向量中通过权重来体现不同关键词在查询中的重要性。 （2）利用计算得到的相似度可以对获取的文档按照相关度排序，这样就可以方便用户在众多获取的信息中先看相关性强的内容。 （3）许多实验表明：向量模型比其它模型，比如布尔模型能得到更加正确的结果。 4.5 建立索引 在对网页进行了解析和主题相关度的判断之后，我们过滤掉那些不需要的网页，将与主题相关度比较高的网页进行下载并保存，但是为了防止以后每次用户搜索都重新搜索，我们为其建立索引，以便提高以后搜索的速度。 本论文采用索引分析器Indexer对网络爬虫所下载的页面进行分析，把文件表示成一种便于建立索引的方式，抽取最优索引信息以表示文档，并利用所抽取信息建立索引数据库，从而使用户能够很容易的查找到所需要的信息。 38 主题网络爬虫的研究与实现 4.6 系统实现 根据前面几节所描述的系统模型和设计方案，我们在WindowsXP系统下面用 MyEclipse实现了一个主题爬虫系统——MySpider。下面本文将给出系统的运行结果。 系统运行的初始界面如图4-3所示，该界面是用户打开MySpider系统时的欢迎界面。 图4-3 MySpider主题爬虫欢迎界面 用户点击进入后就可以进入用户参数设置界面，在该界面中，用户可以设置初始爬行的网站地址，可以选取job的名字，可以设置线程个数，后缀格式等所有参数，还可以选择保存地址，如图4-4所示。 39 主题网络爬虫的研究与实现 图4-4 参数设置界面 参数设置完成后，点击确定，就可以进入如图4-5所示的爬虫爬行界面，在这里可以看到已下载的网站数量，已下载的网站名称等信息，用户还可以随时进行暂停和停止，比较具有人性化。 图4-5 MySpider主题爬虫爬行界面 40 主题网络爬虫的研究与实现 4.6 总结 本章主要研究主题网络爬虫的设计方案。主要是对系统在具体设计中所涉及到的相关内容分别进行了分析。首先分析了爬虫的性能评价指标，接着给出主题爬虫的体系结构，然后就系统结构图分析各个组成部分的功能需求，并以此给出了本论文设计的爬虫所采用的技术方案，详细说明了种子网站选取、HTML解析、主题相关度算法的策略，并对此进行了深入的分析和讨论，通过数据说明，本论文采用的主体相关度算法具有较好的准确性和稳定性，并在此基础上实现了爬虫系统，完成了爬虫的大部分功能，最后给出了主题网络爬虫的运行界面。 41 主题网络爬虫的研究与实现 第五章 总结与展望 5.1 本文总结 随着网络信息量的日益增长，并且对网络信息精确化，个性化需求的不断增加，基于主题网络爬虫的专业搜索引擎成为当前发展的热门。本文从主题网络爬虫的抓取策略的分析和研究入手，讨论了主题网络爬虫适合的抓取策略，并给出了主题网络爬虫在Java下的实现概述，基于这里介绍的主题网络爬虫的实现结构，可以实现一个较为完善，并且效率较好的主题网络爬虫。 随着Internet的迅速发展，网络信息的增长也达到了惊人的速度，人们对网络信息的获取也有了新的要求，搜索引擎技术成为计算机业界争相研究和开发的对象。通用搜索引擎因其搜索海量信息为目标，难以满足用户对特定信息的查询要求，主题式搜索成为研究重点。 本论文在分析了通用搜索引擎的弊端和主题搜索引擎的优势之后，详细讨论了主题搜索引擎中最重要的部分——主题爬虫的关键技术及算法，并设计和实现了一个主题爬虫系统MySpider。它采用了改进的权值计算公式，从种子网页开始，收集与主题相关的网页，多线程进行网页的下载和分析，提高了网页搜集的效率。 5.2 研究展望 主题爬虫随着网络信息的突增起到了越来越重要的作用，它的应用也越来越广泛。本文在所设计的主题爬虫的网页分析和主题相关度分析方面都有所尝试，但是限于时间、精力、水平有限，下一步要做的工作还有很多。 (1) 体系结构上有待改进。如果采用分布式的体系结构，比如基于P2P技术的爬虫，将会使爬虫的搜集效率进一步的提高，而且可以满足个性化的需求。 (2) 在搜索策略中引入更多的人工智能技术。 (3) 动态网页的获取。动态网页数据量大，信息实时，但是很难获取，因此如何有效地获取动态网页也是下一步要做的工作。 42 主题网络爬虫的研究与实现 [参考文献] [1] 朱良峰．主题网络爬虫的研究与设计[D],2008. [2] Liu P,Pu C,Han W.XWPAP:An XML-enabled wrapper construction system for Web information sources.Proceedings of the 16th International Conference on Data Engineering,Washington,2000:611-622. [3] Baumgartner R,Flesca S,Gottlob G..Visual web information extraction with Lixto.Proceedings of the 27th International Conference on Very Large Data Bases.San Franciso,2001:119-128. [4] 谢德辉．面向刑侦网页的信息抽取与主题爬虫应用研究[D],2007. [5] BraD P,Houben G,Kornatzky et al.Information retrieval in distributed hypertexts. Proceedings of the 4th RIAO Conference,New York,1994:481-491. [6] Hersovici M,Jacovi M,Maarek Y et al.The shark-search algorithm an application:tailored Web site mapping.Computer Networks and ISDN System,1998,30(3):256-264. [7] Brin S,Page L.The anatomy of a large-scale hypertextual Web-search engine.Proceedings 7th International World Wide Web Conference,Brisbane,1998:146-164. [8] Chakrabarti S,Dom B,NDYK P. Enhanced hypertext categorization using hyper links. Proceedings of the ACM SIGMOD International Conference on Management of Data,New York,1998:307-318. [9] Ramaswamy S,Rastogi R,Shim K.Efficient algorithms for mining outliers from large data sets.Proceedings of ACM International Conference Management of Data,Dallas,2000:427-438. [10] 刘玮玮，搜索引擎中主题爬虫的研究与实现[D].南京理工大学硕士学位论文. [11] 倪贤贵，蔡明，基于链接结构和内容相似度的聚焦爬虫系统[N].江南大学学报 [12] P.M.E.De Bra,R.D.J.Post. Information Retrieval in the World-Wide Web: Making Client-based searching feasible[C]. [13] 李学勇，田立军. 一种基于非贪婪策略的网络蜘蛛搜索算法[J].计算技术与自动化,2004(23):35-39 [14] 黄德才，戚华春.PageRank算法研究[J].计算机工程,2006(4):145-146,162. [15] 杨炳儒，李岩，陈心中，王霞.Web 结构挖掘[J].计算机工程,2003(11):28-30. [16] 周荫清.信息理论基础[M].北京航空航天大学出版社,1993. [17] 张玉芳，陈小莉，熊忠阳.基于信息增益的特征词权重调整算法研究[J],2007. 43 主题网络爬虫的研究与实现 致谢 在此论文完成之际，谨向所有关心和帮助过我的人表示诚挚的感谢！ 感谢我的指导老师史亮教授。导师渊博的专业知识，严谨的治学态度，精益求精的工作作风，平易近人的人格魅力对我影响深远。本论文从选题到完成，每一步都是在史老师的指导下完成的，倾注了史老师大量的心血。在此，谨向史老师表示崇高的敬意和衷心的感谢。 感谢同一研究小组的王振山、文珊珊同学，我们在学习上相互勉励、共克难关，生活上相互照顾、共同进步，愿我们的友谊长存。 感谢我的舍友邓祥等同学，他们在平时生活、学习中给了我很大的帮助，难忘我们的同心互助，更难忘我们宿舍内欢乐融洽的情谊。 感谢我的父母和两位姐姐，他们的关爱始终伴随着我，他们在各方面一直默默地支持着我，使我有信心战胜一切困难，在此祝他们永远健康快乐。 感谢厦门大学软件学院的各位老师，他们的言传身教使我在学习、生活和工作等各方面都增长了知识，开拓了视野，使我受益匪浅，母校之恩毕生难忘。 44 因篇幅问题不能全部显示，请点此查看更多更全内容