（计算机应用技术专业论文）基于增量反馈和自适应机制的主题爬虫系统的设计与实现.pdf

南京理工大学硕士论文基于增量反馈和自适应机制的主题爬虫系统的设计与实现 摘要 近年来，随着互联网信息的快速几何增长，如何及时准确地从互联网上获取有 用信息显得十分重要。主题爬虫是一种基于主题的信息采集系统，可以从互联网上 采集到与主题相关的有用信息，在主题搜索引擎、站点结构分析等方面取得越来越 广泛的应用。 本论文进行了基于主题的爬虫系统的设计与实现，其主要的研究工作和特点包 括： 研究了主题爬虫系统的基本理论和基本结构，深入分析和探讨了与主题爬虫 相关的技术，并设计和初步实现了一个基于增量反馈和自适应机制的主题爬虫系统 h j s p id e r 。 在页面与主题相关性判定中，引入了文本分类的思想，应用了在自然语言处 理中比较成熟的基于向量空间模型的主题相似度计算方法。 在u r l 与主题的相关性判定中，综合运用了网页文本内容和w e b 结构图的 启发策略，并在经典的如t s 算法基础上提出了引入增量反馈和自适应机制的新的 算法。 总结了主题页面在w e b 上的分布规律，给出了主题选择的方法以及对主题页 面中基于h t m l 语法的分析方法。 关键词：主题爬虫，h i t s ，向量空间模型，超链分析 a b s t r a c t 硕士论文 a b s t r a c t t h ee n o r m o u sg r o w t ho ft h ew o r l dw i d ew e bi nr e c e n ty e a r sh a sm a d ei ti m p o r t a n t t op e r f o r mr e s o u r c ed i s c o v e r ye f f i c i e n t l y c o n s e q u e n t l y , s e v e r a ln e wi d e a sh a v eb e e n p r o p o s e di nr e c e n ty e a r s ；a m o n gt h e mak e yt e c h n i q u ei sf o c u s e dc r a w l i n gw h i c hi sa b l e t oc r a w lp a r t i c u l a rt o p i c a lp o r t i o n so ft h ew o r l dw i d ew e bq u i c k l yw i t h o u th a v i n gt o e x p l o r ea l lw e bp a g e s a n dn o w ，i ti s n l o r ea n dm o r ew i d e l ya p p l i e di nt h ef i e l d so f t o p i c s p e c i f i cs e a r c he n g i n e s ，s i t es t r u c t u r ea n a l y z i n ga n ds oo n t h em a j o rr e s e a r c hw o r ka n dc o n t r i b u t i o n so ft h i sd i s s e r t a t i o na r ea sf o l l o w s ： t h eb a s i ct h e o r ya n dt h ec o n s t r u c t i o no ft h ef o c u s e dc r a w l e ra r ei n v e s t i g a t e d r e s p e c t i v e l y b a s e do nt h e s ei n v e s t i g a t i o n s ，t h et h e s i se x p l o r e st h er e l a t e dt e c h n i q u e so f t h ef o c u s e dc r a w l e ra n d b r i n g sf o r w a r das t r u c t u r ed e s i g nm o d e lo fi t ，w h i c hw a sn a m e d h j s p i d e r i nt h ec o u r s eo ft h er e l a t i v 姆j u d g i n gb e t w e e nt h ep a g ec o n t e n ta n dt h et o p i c ，w e a p p l i e dt h et e r m b a s e dv e c t o rs p a c em o d e lw h i c hi sw i d e l yu s e di nt h e 衄e do ft h et e x t c l a s s i f i c a t i o n i nt h ec o u r s eo ft h er e l a t i v i t yj u d g i n gb e t w e e nt h eu r la n dt h et o p i c ，w e d e v e l o p e dan e wa r i t h m e t i cw h i c hb a s e do nt h ep a g ec o n t e n t , t h ew e bs t r u c t u r ea n dt h e h y p e f l i n ka n a l y s i sm e t h o dh i t s w es u m m e du p 廿1 er u l e so ft h ed i s t r i b u t i o no ft o p i co nt h ew e b a n dd e s c r i b e dt h e w a yh o wt o s e l e c tt h et o p i ca n dh o wt o a n a l y s i st h eh y p e r l i n kb a s e do nt h eh t m l s y n t a x k e yw o r d s ：f o c u s e dc r a w l i n g ，f l i t s ，v s m ，h y p e r l i n k a n a l y s i s 声明 本学位论文是我在导师的指导下取得的研究成果，尽我所知，在 本学位论文中，除了加以标注和致谢的部分外，不包含其他人已经发 表或公布过的研究成果，也不包含我为获得任何教育机构的学位或学 历而使用过的材料。与我一同工作的同事对本学位论文做出的贡献均 已在论文中作了明确的说明。 研究生签名： 巡一，够年月j 目 学位论文使用授权声明 南京理工大学有权保存本学位论文的电子和纸质文档，可以借阅 或上网公布本学位论文的全部或部分内容，可以向有关部门或机构送 交并授权其保存、借阅或上网公布本学位论文的全部或部分内容。对 于保密论文，按保密的有关规定和程序处理。 研究生签名： 主垒p 巧年多月r 日 南京理工大学硕二b 论文基于增量反馈和自适应机制的主题爬虫系统的设计与实现 1 绪论 1 1 背景 当今，随着因特网( i n t e m e t ) 的迅速发展，网络已经成为人们获得信息的必要 途径和重要手段，正深刻地改变着我们的生活。而在网上发展最为迅猛的w w w ( w o r l dw i d ew e b ) 技术，以其直观、方便的使用方式和丰富的表达能力，已经发 展成为一个全球化信息发展空间。据2 0 0 3 年一项统计表明，i n t e m e t 上的信息总量 在6 6 9 6 7 t b 到9 2 0 1 7 t b 之间，上网用户超过6 亿，熬个万维网的规模已经快速发 展到包含大约8 0 亿个网页和5 6 0 亿个超链接( 2 l 。w w w 技术的迅猛发展在一定程度 上解决了信息匮乏的问题，但其缺陷也日益突出。好多人面对着浩如烟海的网络信 息仍然感到所需信息的不足，究其原因，并不是真正信息量的不足，而是因为人们 在如此大的信息库里，很难用浏览的方式找到自己所需的信息。 一方面网上的信息多种多样、丰富多彩，而另一方面用户却找不到他们所需要 的信息。这样的矛盾促使一种以w e b 搜索引擎为主的，用于提取网络有效资源的信 息检索技术应运而生了。g o o g l e 、 n f o s e e k 、b a i d u 、a l t a v t s t a 、天网等国内外知名 的搜索引擎正是人们为了解决网上信息检索的难题，而在信息检索领域进行大量研 究后的成果。这些搜索引擎通常使用一个或多个资源采集器从i n t e r n e t 上收集各种 数据( 如w w w 、f t p 、e m a i l ) ，然后在本地服务器上为这些数据建立索引，当用户 检索时根据用户提交的检索条件从索引库中迅速查找到所需的信息【3 1 。这些采集器 被叫做：s p i d e r s ，c r a w l e r s ，w 曲r o b o t s ，w a n d e r e r s 本论文在后面章节将统使用 “爬虫”作为采集器的标准术语。 网络爬虫是一个沿着链接漫游w e b 文档集合的程序，它一般驻留在服务器上， 通过给定的一些u r l ，它能够利用像h 1 r r p 这样的标准协议读取相应文档，然后以 文档中包括的所有新的( 未访问过的) u r l 作为新的起点，继续进行漫游，赢到没有 满足条件的新u r l 为止【4 。网络爬虫的研究开始于上世纪九十年代，被认为世界 上的第一个爬虫w a n d e r e r 实现于1 9 9 3 年。它的优势在于自动化程度高、维护费用 低，更强调技术上的创新和提高，也更适合于开展研究工作，因而成为当前研究的 热点。 目前，常见的综合型搜索引擎的优点是用户可以查到范围很广的信息，但不足 之处在于由于其涉及领域太广，因此在某些特定领域的查询上则不够深入和专业化， 在整个采集过程中，它也并不太在意采集的顺序和被采集页面的相关主题。同时采 集所得的页面的数量过于庞大和采集页面内容过于杂乱。 针对上述状况，人们提出了对某一专题的主题搜索引擎，它可以在某些小范围 1 1 绪论硕士论文 的领域取得比综合型搜索引擎更满意的结果，满足了某些特定用户的需要。采用主 题搜索算法的爬虫程序仅对给定主题相关的网页文档进行搜集，搜索算法在访问页 面之前进行预测分析，从而识别出这些页面是否与主题相关，决定是否采集或者制 定采集的优先顺序。毛题爬虫可以有效地减少采集页面的数量，增加了采集页面的 规整程度，同时也节约了网络带宽，提高信息搜索的效率。因此开展对主题爬虫的 研究是很有必要的。 1 2 主愿穗虫的研究现状 在1 9 9 4 年，出现了最早使用查询来指导爬虫爬行的系统_ f j s h 搜索系统( f i s h s e a r c hs y s t e m ) 5 1o 后来相继在1 9 9 8 年和1 9 9 9 年分别出现了s h a r k 搜索系统( s h a r k s e a r c hs y s t e m ) 旧和主题爬虫( f o c u s e dc r a w l i n g ) 1 7 , 8 1 , 如今，主题爬虫又有了新的 发展，典型的系统有c o r a 9 1 、i b mf o c u s e dc r a w l 0 7 1 、c o n t e x tg r a p h sf o c u s e d c r a w l e r 1 0 1 等。 1 2 1c 班认 c o r a t 9 是美国卡内基梅隆大学的a k m c c a l l u m 和m n i g a m 等人于1 9 9 9 年 针x - ；t 算机科学设计的一个主题型搜索引擎。它利用机器学习( m a c h i n ek e a m i n g ) 技术，在w e b 上搜索与计算机科学相关的论文，当时它只能搜索p s 格式的论文。 如果一篇文章含有题名、作者、摘要和参考文献，它就认为是一篇学术论文。然后 ：街p s 文件转换成文本文件，利用隐式马尔可夫模型来找出题名、作者、摘要和参 考文献，利用统计型文本分类算法将其按照y a h o o 分类体系进行分类。现在的c o r a 站点地址是h t t p ：c o m w h i z b a n g , c o m l 。c o r a 思想比较先进，很容易扩展成为其它 学科主题的搜索引擎，对w e b 垂直门户网站资源自动建设具有相当重要的意义。但 是，c o r a 没有在预测u r l 与主题的相关度上作深入研究，也没有对w e b 网页进 行采集分析。实际上，由于论文的结构清晰，有很多明显特征，用词规范，所以对 p s 等格式的论文采集的难度要略低于对w e b 网页进行页面主体采集的难度。 1 2 2i 圈lf o e u s e dc r a w l e r i b mf o c u s e dc r a w l e r t 7 1 是印度理工学院的学者s c h a k r a b a r t i 在伯克利大学计算 机系读博士期间从事的一个项目。在该项目中，作者提出了一种新的w e b 资源爬行 系统，即主题爬虫( f o c u s e dc r a w l e r ) 。它对主题的定义即不是采用关键词也不是加 权矢量，而是一组具有相同主题的网页。尽管成为主题爬虫。但它实际上是一整套 关于特定资源的自动建设方案，用来建设w e b 主题资源。 南京理工大学颈士论文基于增量反馈和自适应机制的主题爬虫系统的设计与实现 该系统的早期版本7 1 采用了两个模块：一个是分类器，用来计算下载文档与主 题的相关度，同时也用来指导爬行器优先爬行的相关资源；另一个是汾化器，用来 确定哪些是中心页面。在该系统的改进版本嘲中，作者将分类器分成两个，一个用 来指导爬行，一个用来计算下载网页与主题的相关度。从而使系统有了更好的性能。 1 2 3c o n t e x tg r a p h sf o c u s e dc r a v l e r c o n t e x tg r a p h sf o c u s e dc r a w l e 一o 是由d i l i g e n t i 等人研究没计的一种主题爬虫。 他们提出了一种通过建立上下文图( c o n t e x t g r a p h s ) 来学习网页间相互关系的方法。 他们先给系统提供一组种子主题页面，然后利用g o o g l e 提供的反向链接( 通过在 g o o g l e 中键入“l i n k ：u r l ”就可以获得所有指向该页面的页面链接，如：“l i n k ： w w w q i a n l o n g c o m ”) 服务来寻找到所有拥有指向种子页面链接的页面。所有拥有 指向种子页面链接的页面被称作第一层页面，而所有拥有指向第一层页面链接的页 面被称作第二层页面，依次类推。页面的层数根据用户参数的改变而改变。见图 ( 1 2 1 ) 展示了一个深度为2 的上下文图。 牟砌口。；姗4 e 憎￥女t ln 。蛐e n 黪“y h2 e e “ 图1 2 1 深度为2 的上下文图 当每一个种子页面都建立好一个上下文图后，研究人员将不同的上下文图的相 应各层进行合并，形成一个合并上下文图( m e r g e dc o n t e x tg r a p h ) 。同时为每一层 训练一个贝叶斯分类器。在爬行过程中，分类器被用来确定所要爬行的页面应该属 于哪一层。一旦页面的所属层次被确定，那么该页面所包含的链接就会被加入到与 该层相对应的队列中。然后再从靠前的非空队列中提取所要爬行的页面u r l 。 1 。3 研究的目的及意义 本系统的研究范畴属于网络信息采集和数据挖掘领域，课题源于中共中央政策 研究室的信息采集研究项目。因此，我们的主要目的是在互联网上收集用户关心的 主题信息。除此现实意义外，本课题的理论意义是更值得我们关注的。 绪论 硕士论文 目前各大数字图书馆和主题网站在利用w e b 主题资源的时候，迫切希望有一个 工具或技术来代替或辅助工作人员进行主题资源的搜集、整理等工作。主题搜索系 统可以自动地搜索w e b 上的主题资源，从而摆脱对专家的依赖，减少人工干预，提 高主题网站资源建设的速度、效率和质量，为科研人员和相关用户提供高质量的信 息资源和信息服务。 作为实现自动主题搜索的最佳方法，主题爬虫技术不但可以提高某个主题的资 源覆盖度，而且使得主题爬虫所下载的网页尽可能地与所需的主题相关，从而有效 地提高主题爬虫的爬行性能和网络带宽的利用效率。 l 4 论文安捧 本论文安排如下： 第一章主要介绍系统的研究背景和相关技术发展现状，以及论文的研究目标： 第二章主要剖析主题爬虫的原理和结构以及与普通爬虫的区别，总结了主题页 面在w e b 中的分布特征； 第三章主要研究和探讨系统中所要用到的关键算法，其中包括w e b 超链接分析 的算法、u r l 主题相关性算法、页面主题相关性算法等； 第四章主要说明系统的设计过程，对主题的选择、页面的分析、主题相关性的 判定策略的选择等主要方面作了详细的论述，并给出我们的设计方案和算法，提出 系统的增量反馈和自适应机制； 第五章给出系统的实际应用过程和部分实验数据，说明我们的系统是切实有效 的： 第六章对本论文作了工作总结，同时也提出了进一步需要做的工作。 4 南京理i _ 大学颇十论文基于增量反馈和自适应机制的主题爬虫系统的设汁与实现 2 主题爬虫概述 爬虫在设计之初，其目的是在给定爬行周期内，尽可能多地下载w e b 网页。但 当面临着w e b 网页发展规模和数量成几何增长的现实时，通用的爬虫要想在爬行网 页时既保证网页的质量和数量，又要保证网页的时效性显然已经是力不从一1 1 , 了。于 是，爬虫的设计目的就变成了在给定的爬行周期内尽可能多地爬行高质量的网页， 并且保持网页的时效性。而主题爬虫在上述设计目的的基础上，还考虑了网页与主 题的相关度，尽可能多地下载相关网页，尽可能少地下载无关网页，提高主题资源 的覆盖度。 一个好的爬虫需要达到以下两个要求1 1 2 1 ：它必须要有一个好的爬行策略，即 决定下一步要爬行哪些网页的策略。它必须要有一个高度优化的系统结构，且健 壮性、可控性良好。对于主题爬虫而言，它还必须对下载的网页进行与搜索主题的 相关度分析，以决定其是否符合主题搜索的要求。因此要有一个好的分析方法。 由于相关主题资源的规模相对整个因特网来说要小得多，也相对容易控制和掌 握，所以主题爬虫可以提供更精确的搜索结果。但相对普通爬虫，主题爬虫还需要 解决以下两个主要问题： 1 为了提高爬行效率，主题爬虫需要解决如何从待爬行u r l 队列中挑出最可能 包含主题相关信息的网页进行爬行。 2 对于每个已下载的网页，主题爬虫需要判断它与主题的相关性，用来指导以 后的爬行过程。主题爬虫应尽量避免爬行主题不相关的和低质量的网页。 2 1 通用爬虫模型 2 1 1 通用爬虫的结构 爬虫是搜索引擎中最关键的部分，它的性能好坏直接影响着搜索引擎整体性能 和处理速度。爬虫一般都要维护个u r l 队列，用来存储已经发现但还没访问的 u r l 。u r l 的访问次序一般有：广度优先、深度优先、随机访问等。通用爬虫基本 流程图见图( 2 1 1 1 ) ，结构见图( 2 1 1 2 ) 。 其各个模块的主要功能介绍如下： 1 页面采集模块：该模块是爬虫和因特网的接 = 】，主要作用是通过各种w e b 协议( 一般以h t t p 、f t p 为主) 来完成对网页数据的采集，然后将采集到的页面 交由后续模块作进一步处理。 2 页面分析模块：该模块的主要功能是将页面采集模块采集下来的页面进行分 2 主题爬虫概述顾- 上论文 析，提取其中满足用户要求的超链接，加入到超链接队列中。页面链接中给出的u r l 一般是多种格式的，可能是完整的包括协议、站点和路径的，也可能是省略了部分 内容的，或者是个相对路径。所以为处理方便，一般先将其转化成统一的格式。 3 链接过滤模块：该模块主要是用于对重复链接和循环链接的过滤。 4 页面库：用来存放已经爬行下来的页面，以备后期处理。 5 u r l 队列：用来存放经链接过滤模块过滤得到的u r l ，当u r l 为空时爬虫 程序终止。 6 初始u r l ：提供u r l 种子，以启动爬虫。 6 开蛄 种子站点u r l 入拽 空否 满足结毫蠢件? l 否 从枝中取一个u r i 从w c b 上下戟对窿同耍 是 是 结柬 图2 ，1 1 1 通用爬虫流程图 蕊 莆一 南京理工大学硕士论文基于增量反馈和自适应机制的主题爬虫系统的设计与实现 2 1 2 通用爬虫的不足 图2 1 1 2 通用爬虫结构 通用爬虫设计思想存在以下两个问题： 第一，网页爬行的数量和范围，严重依赖于给定的种子站点的数量和质量。即 使在没有时间限制、w e b 规模不够大的情况下，从给定的种子站点出发，通用爬虫 也不可能遍历整个w e b 。以图( 2 1 2 1 ) 为例，假设选取的种子站点是c 3 和s 3 ， 无论是用何种访问次序，最终都爬行不到s 1 ，s 2 ，c 1 ，c 2 。尽管s l 和s 2 都指向 c 3 ，它们有密切联系，只是因为种子站点选得不好，导致不能访问。 图2 , 1 2 1w e b 超链按结构示意图 2 主题爬虫概述 硕士论文 第二，在爬行的过程中，没有考虑网页的质量。由于w e b 的发展规模，任何的 爬虫都不可能下载和索引所有的网页，只能是尽可能多地下载高质量网页，尽可能 少地下载低质量的网页。 2 2 主题爬虫模型 2 2 1 主题爬虫的原理 假设一个用户的w e b 信息检索表示为一组目标主题集合：7 = f t ，t ，t 。 ，每个 主题t f 分别由主题爬虫来处理。我们可以用一组关键词k = ( k l ，也，k 。 来表示 一个主题的关键特征，而用一系列样本集w 来详细描述一个主题，其中w = l u ，是一个样本u r l ：i i = 0 或l ，是该u r l 的正反例标号) 。f f 值为】表示啦与主题 相关，为0 表示与主题不相关。主题爬虫一股从组种子u r l 开始沿着己爬行页面 中的超链接遍历w e b 以搜集更多的主题相关页面。对于主题爬虫来说，k 与w 是 它的初始学习资源。 整个w e b 从逻辑上可以看作一个有向图g = ( v ，e ) ，其中图的节点集v 表示 页面的集合，有向边集e 表示页面之间的超链接。给定一个目标主题，根据页面内 容与目标主题的相关度，节点集v 可以分为两部分：相关集v + 和不相关集v 一。主 题爬虫的爬行过程可以看作对一个有向图的遍历过程，即从一组节点( 种子节点) 出发，尽可能多地搜索到那些属于v + 集合的节点，同时尽可能避免搜集到那些属 于v 一的节点。 简单来说，主题爬虫就是指具有识别主题功能的爬虫，它尽可能多地爬行与某 个主题相关的w e b 资源，扩大该主题资源的覆盖度。 主题爬虫的基本思路是按照事先给出的主题，分析超链按和已经下载的网页内 容，来预测下一个要爬行的u r l ，保证尽可能地多下载与主题相关的网页、尽可能 少下载无关网页。因此，主题爬虫需主要解决以下三个关键问题： 怎样判断一个已经下载的网页是否与主题相关? 对于已经下载的网页，因为 我们可以知道它的文字内容，可以采用传统的文本挖掘技术来实现。 怎样决定u r l 的访问次序? 许多主题爬虫是根据已下载的网页的相关度， 按照一定的原则，将相关度进行衰减，分配给该网页中的超链接，而后插入到优先 级队列中。此时的爬行次序就不是简单的以深度优先或者广度优先为序，而是按照 相关度大小排序，优先访问相关度大的u r l 。不同主题爬虫之间的主要区别也就在 于它是如何决定u r l 的爬行次序。 怎样提高主题爬虫的覆盖度呢? 这个问题要解决的就是如何穿过质量不够 好( 与主题不相关) 的网页得到我们所感兴趣的网页，从而提高主题资源的覆盖度。 8 南京理工大学硕士论文基于增量反馈和自适应机制的主题爬虫系统的设计与实现 2 2 2 主题爬虫的结构 主题爬虫是在普通爬虫的基础上发展起来的，最早的主题爬虫是在通用爬虫的 基础上改造而成的。其结构见图( 2 2 2 ，1 ) 。 图2 2 2 1 主题爬虫结构示意图 、殴计者只是为爬虫提供了主题关键字，并在存储之前增加了一个主题识别步骤 ( 相关度判定) ，若页面与主题相关就存储，否则就丢弃。尽管这样的爬虫也能实现 对主题资源的爬行，但它在爬行中依然要遍历整个网络，并没有提高爬行的效率。 网页爬行的数量和范围也依然严重依赖于给定种子站点的数量和质量。同时，这种 爬虫还会下载很多与主题无关的资源，然后丢弃，造成对带宽和网络资源的严重浪 费。 为解决以上的不足，研究者们采用了很多轻巧的算法和策略，来保证爬虫尽可 能多地爬行相关网页，尽可能少地爬行无关网页，并且确保网页有较高的质量。研 究的主要工作集中在如何将待爬行的u r l 按定策略进行排序，使得与主题相关且 质量高的u r l 优先爬行。在第三章中，我们将详细介绍并讨论u r l 排序的启发策 略。 主题爬虫发展到现在，其结构要比原始的复杂得多，也有效得多。一般，一个 主题爬虫包括以下三个关键组成部分： 1 页面相关度评价器。该模块主要特点是引入了文本分类的思想。在系统爬行 之初，页面相关度评价器根据用户输入的关键字和初始文本信息进行学习，训练一 个页面相关度评价模型。当一个被认为是主题相关的页面爬行下来之后，该页面就 被送入页面相关度评价器计算其主题相关度值，若该值大于或等于给定的某阈值， 则该页面就被存入页面库，否则丢弃。 2 主题爬虫概述硕士论文 2 超链接评价器。该模块是主题爬虫的核心模块，主要用于评估从主题相关页 面解析出来的u r l 与主题的相关度，并提供相关的爬行策略用以指导爬虫的爬行过 程。u r l 的超链接评价得分越高，爬行的优先级就越高。反之，若通过一定的评价 策略，发现某链接与主题无关，则将该u r l 及其所有隐含的子链接一并去除，这个 过程我们称之为剪枝。通过剪枝，爬虫就无需遍历与主题不相关的页面，从而保证 了爬行效率。但是，剪枝的行为也可能将潜在的与主题相关的页面也剪掉。因此， 超链接评价器所用的评价策略的好坏直接影响着爬虫的爬行效率以及爬行质量。 3 爬行器( 页面采集模块) 。该模块是任何爬虫郡不可或缺的通用模块。该模 块承担着连接超链接评价模块和页面相关度评价模块的重任。首先，爬行器从待爬 行u r l 队列中取出超链接得分最高的u r l ，将该u r l 相应的网页爬行到本地，然 后，将该页面交由页面相关度评价器处理。在整个爬行过程中，爬行的次序和爬行 策略都有超链接评价器提供。 2 2 3 与普通爬虫的区别 举例来说，假设在整个w e b 上有t 个网页文件，其中关于某主题的文件个数为 s 。通过普通爬虫在一个爬行周期( 7 天) 能够爬行所有w e b 资源的2 0 ，而其中 关于某个主题的资源为5 ，则在一个爬行周期内，只能采集到1 ( 2 0 * 5 ) 的 主题相关资源，而且还有大量的资源与主题无关。但如果采用主题爬虫，在一个爬 行周期内，能够爬行所有w e b 资源的1 0 ，其中5 0 与主题相关，则在一个爬行周 期内采集到了5 ( 1 0 + 5 0 ) 的主题相关资源，而且只有5 ( 1 0 一5 ) 是资源 浪费部分。 这样，主题爬虫的主题爬行覆盖度r = p 1 0 * 5 0 s = 5 * ( t s ) ，而普通爬虫的主 题覆盖度r = t * 2 0 * 5 s = l + ( t s ) 。 通过上述分析发现，主题爬虫爬行资源的数量只有普通爬虫的二分之一，而它 的主题资源覆盖度却是普通爬虫的五倍，能发现更多的w e b 主题资源。这也正是主 题爬虫存在的意义。它除了可以提高主题资源的覆盖度外，在减少网络负担、优化 网络结构等方面也均有显著意义【i “。 相比于普通爬虫，一个主题爬虫需要能有效地发现主题相关的文档，并且能通 过网络内容和链接结构来指导自身的资源发现过程”。图( 2 2 3 1 ) 形象的展示了 普通爬虫和标准主题爬虫的爬行过程中的不同。 l o 南京理工大学硕士论文 基于增囊反馈和自适应机制的主题腿虫系统白句设计与实现 a ) 普通爬虫b ) 主题爬虫 图2 2 3 1 普通爬虫与主题爬虫扩展链接策略比较图 其中，白框代表主题无关页面，黑框代表主题相关页面，虚线代表链接，箭头 代表访问次序。 a ) 普通爬虫以广度优先的策略，循着每一个链接进行爬行。假设从起始阿页到 目标网页需要爬行i 步，那么在爬行目标网页前必须先将i - 1 步内的网页爬行完。 b ) 主题爬虫则先确定最有可能与主题相关的链接，忽略主题无关的网页。假设 从起始网页到目标网页需要爬行i 步，那么在爬行目标网页前仅爬行i 1 步内的网页 的一个子集，理想情况下只要爬行i 个链接就可以达到目标，大大节约了爬行时间， 提高了爬行效率。 如果同一主题相关的网页在w w w 上是平均分布的，那么主题爬虫相比于普通 爬虫在效率上就没有明显改善。然而，经过研究表明，w w w 上的网页分布具有主 题聚合性( 详见2 3 节) 。利用这一特性，主题爬虫就可以优先对主题相关网页中的 超链接进行爬行。 2 3 主题页面的分布特征 w e b 与传统的信息媒介相比，具有许多的不同点：信息容量是巨大性；动 态性，整个w e b 的内容和结构每时每刻都在改变；异构性，w e b 中所包含的文件 类型各式各样，包括图像、图片、声音、文本等； w e b 页面的重复性，最近的研 究表明，将近3 0 的页面是重复的；高链接性，一项研究表明平均每个页面有超 过8 个链接指向别的页面；多语性，w e b 上所用语言是多种多样的，目前页面语 种超过了1 0 0 种。 虽然整个w e b 充满了半结构化的和非结构化的各类信息，显得杂乱无章。但它 也是有一定的规律可循的，我们可以将主题页面的分布规律总结为以下几个基本特 征呱“1 5 - 1 6 1 7 , 1 8 1 9 j ：中心页面特性、主题关联特性、主题聚集特性、隧道特性。 2 主题爬哇i 概述 硕士论文 2 3 1 中心页面特性 在整个w e b 中大量存在着这样一类页面，它们不但含有许多指向其他页面的链 接，而且这些链接还趋向于同一主题。也就是说，这类页面是指向相关主题页面的 中心，我们称之为中心页面或h u b 页面。另外，w e b 中还有这样一类被许多网页都 认为与某一主题相关的有价值的网页，我们称之为权威页面或a u t h o r i t y 页面。存在 链接关系的页面间，其描述的主题一般都比较相似。一般的，一个好的中心页面会 指向多个权威页面，一个好的权威页面会被多个中心页面指向。据于这个思想，美 国康奈尔大学的教授j o nm k l e i n b e r g 还提出了h u b a u t t t a r i t y 算法【i3 1 ，这个算法将 在3 ，1 2 节中介绍。 在内容关联特性的基础上，科研人员又对w e b 结构进一步深入的观察和研究， 提出了主题关联特性，即每个页面所包含的链接都趋向于链接到与它本身同主题的 页面：对于链接到某一主题页面的页面，它所包含的其它链接也趋向于链接到该主 题。这个结论实际上是从网页设计者的角度考虑的，一个网页的设计者趋向于将本 页面指向于与本页面主题相关的其它页面；同时也趋向于将本页面链接在与本页面 主题相关的页面之后。 2 3 3 主题聚集特性 研究人员还发现，每一个非门户的普通站点都趋向于说明个或几个主题，而 且那些相同的主题页面之间会有紧密的内部链接，但是不同的主题之间却很少有相 互问的链接。产生这种现象主要原因应该是网站的设计者在设计网站时都有预定的 设计目标和定位，而这种目标往往就集中在一个或几个主题上。同时，对于网页浏 览者来说，他们在上网时一般也趋向于浏览同一主题的页面。为适应上网者的需求， 网站设计者也需要将相关内容相互链接。这样在w e b 中就出现了一个一个主题团。 这个特性为主题爬虫的剪枝操作的可行性提供充分的理论依据。 2 3 4 隧道特性 尽管在w e b 中存在很多主题页面所聚集而成的主题页面团，但在这些页面团之 间，有时往往需要经过较多的无关链接才能够到达。这些无关的链接就像长长的隧 道一样连接着两个主题页面团，因此，这种现象被称为“隧道现象”。在主题爬虫的 运行过程中，“隧道现象”极大地影响页面爬行的质量和爬虫的最终的资源发现率。 1 2 南京理工大学硕士论文 基于增量反馈和自适应机制的主题爬虫系统的设计与实现 为提高爬行页面的查准率，我们就需要提高u r l 以及页面与主题相关性判定的阈 值，而阈值的提高会过滤掉大量“隧道”。这样的结果就是将“隧道”另一端的相关 主题团全部丢弃，从而影响系统的资源发现率。但如果为了提高资源发现率而降低 阈值，则系统在爬行过程中可能混入很多主题无关的网页，从而影响系统资源的查 准率。为了解决这一问题，我们在算法设计过程中采用了增量反馈和自适应机制( 详 见4 5 节) 。该方法将爬行下来的网页信息实时地反馈给爬行系统，从而使系统能动 态地调整u r l 在待爬行队列中的权值，能够有效地在资源的查全率和查准率之间找 到平衡。 以上提到的互联网上主题资源分布的四个特征，虽然各有侧重，但是它们仍然 是共通的。中心页面特性说明了主题资源容易成团出现，并会集中与某一个或多个 固定的网页发生链接关系。主题关联特性进一步论证了主题资源成团出现的可能性， 并对主题资源内部的网络关系进行了分析和扩展。而主题聚集特性说明了主题资源 团所可能出现的位置，隧道特性说明了主题资源的团与团之间的连接并非像主题资 源团内部那么稠密。 3 主题爬虫的关键算法研究硕士论文 3 主题爬虫的关键算法研究 在主题爬虫系统中，最核心的问题就是选择利用何种策略来判定从页面分析中 得到的u r l 与主题的相关性以及爬行下来的页面与主鼷的相关性。 虽然，每次爬行一个页面之后，系统可以从该页面中得到很多的u r l ，但是并不 是所有的u r l 所对应的页面都是与主题相关的。因此，为了在采集主题资源的同时 能够有效地剪枝，我们就需要对已有的相关信息进行分析和处理，用来预测u r l 所对应的页面的主题相关度，根据最终所得的相关度值对u r l 进行排序或者剔除。 为了进一步提高采集页面的准确率，我们还将已爬行下来的页面进行主题相关 性判定，通过计算页面与主题的相关度值与给定阈值的比较来决定页面的舍取。其 实，这个问题的实质就是如何计算页面相似度的问题。 本章的以下部分将重点介绍在主题爬虫的设计和实现过程中会用到的关键算法 及其思想。 3 1w e b 超链分析的算法研究 3 1 1p a g e r a n k 算法 如前所述，整个w e b 是由通过链接相互连接起来的网页以及其他资源所组成， 我们可以把它抽象成一个w e b 图。在该图中，每个节点代表一个网页，有向边代表 一个超链接( h y p e r l i n k ) 。令有向图：g = ( v ，e ) ，其中v 是节点( 网页) 集， e 是边( 当且仅当存在从页面i 到页面j 的链接时存在从节点i 到节点j 的边) 集【2 “。 传统情报检索理论中的引文分析方法是确定学术文献权威性的重要方法之一， 即根据引文的数量来确定文献的权威性。p a g e r a n k 2 ，2 0 ，2 1 ，2 2 ，2 3 ，2 4 ，2 5 1 的发明者s b r i n 和l p a g e 对网络的超链接结构和文献引用机制的相似性进行了研究，把引文分析 思想借鉴到网络文档的重要性计算中来，利用网络自身的超链接结构给所有的网页 确定一个重要性的等级数，当从网页a 链接到网页b 时，就认为“网页a 投了网 页b 一票”，增加了网页b 的重要性。最后根据网页的得票数评定其重要性，以此 来帮助实现排序算法的优化，而这个重要性的量化指标就是p a g e r a n k 值【2 2 。 p a g e r a n k 方法最初用于搜索引擎信息检索中对查询结果的排序过程，近年来被 应用于网络爬虫对链按重要性的评价l 圳。在该方法中，页面的权威值通常用 p a g e r a n k 值来表示。其定义如下1 2 1 1 ： 假设u 为一个页面，凡为被u 指向的网页的集合，鼠为指向u 的网页的集合。 令肌= i 凡| ，即页面u 的出度( 页面u 指向外的链接数) 。令c 为常量。则p a g e r a n k 1 4 南京理工大学硕士沦文基于增量反馈和自适应机制的主题爬虫系统的设计与实现 的简单公式可表示为： 肌m 荟警 图( 3 1 1 1 ) 展示了公式的迭代计算过程。 ( 3 1 1 1 ) 图3 1 1 1 p a g e r a n k 值计算示意图 公式( 3 1 1 1 ) 只考虑了理想情况下的w e b 图。但在现实中，可能会出现一些 干扰情况。比如说，两个页面互相关联，却没有指向第三个页面的链接。在迭代中， 这样的循环会增加页面的p a g e r a n k 值，从而导致与页面的实际重要性不符。另一 方面，网络上还存在着一些特殊的链接，它们所连接的页面没有出度，从而导致迭 代时此种页面的权值无从分布，影响计算结果。再者，人们在上网时是否点击一个 链接，点击哪个链接都是有其随机性的，因此，在公式中也应该体现这种随机性。 综合以上情况，s b r i m 和l p a g e 经过更深入的研究，得出了更为有效的计算公式： i ( 1 c ) + c 掣 氓2 ) 憾埋；2 ” 其中，c 的最佳值为0 8 5 。 分析公式( 3 1 1 2 ) ，我们可以发现，影响一个网页u 的p a g e r a n k 值的因素 有以下三点： 1 网页u 的链入网页数量( 入度) ：如果链入网页数量越多，则网页u 的p a g e r a n k 值就越大； 2 网页u 的链入网页的重要性：链入网页本身越重要，则网页u 的p a g e r a n k 3 主题爬虫的暮键算法研究硕士论文 值就越大； 3 网页u 的链入网页的链出数( 出度) ：由于链入网页的p a g e r a n k 值被均匀 地分布并且传递到它所指向的w e b 网页。所以，链入网页的链出数量越大，每个链 接对网页u 的p a g e r a n k 值的贡献就越小。 p a g e r a n k 算法是最早并且最成功地将链接分析技术应用到商业搜索引擎中的 算法，g o o g l e 搜索领域的巨大成功，证明了p a g e r a n k 算法的有效性。它的基本出 发点是试图为搜索引擎所涵盖的所有页面赋予一个量化的价值度。每个网页被量化 的价值通过一种递归的方式来定义，由所有链接向它的网页的价值程度所决定【劲。 根据这种方法对网页排序后，搜索引擎g o o g | e 就可以确定以一种什么样的顺序将结 果返回查询用户了。 3 1 2h i t s 算法 p a g e r a n k 算法中对于向外链接的权值贡献是平均的，也就是不考虑不同链接的重 要性。而w e b 上的链接具有以下特征 2 5 1 ： 1 有些链接具有注释性，也有些链接是起导航或广告作用。其中，有注释性的 链接才用于权威判断。 2 基于商业或竞争因素的考虑，很少有w e b 网页指向其同一领域的竞争对手的 权威网页。 3 权威网页很少具有显式的描述，比如g o o g l e 主页不会明确给出w 曲搜索引擎 之类的描述信息。 由此可见，平均的分布权值并不符合链接的实际情况。 k l e i n b e r g ：1 9 9 9 i g 提出7 r o t s 2 1 1 n 7 2 72 8 1 ( h y p e r l i n k i n d u c e dt o p i cs e a r c h ) 算 法，他在算法中定义了两个重要的概念：a u t h o r i t y 页面( 权威页面) 和h u b 页面( 中 心页砸) 。a u t h o r i t y 值表示个页面被其他页砸引用的数量，即该页面的入度。网页 的入度越大，则该网页f f 9 a u t h o r i t y 值越大；h u b 值表示一个页面指向其他页面的数量， 即该页面的出度。网页的出度越大，其h u b 值越大。由于h u b 值高的页面通常都提供 了指向权威页面的链接，因而起到了隐含说明某一主题页面权威性的作用1 2 6 1 。通常， 好的中心页面是指向许多好的权威页面的页面；好的权威页面是指由许多好的中心页 面所指向的页面。这种中心页面与权威页面之间的相互作用，可用于权威页面的挖掘 和高质量w e b 结构和资源的自动发现，这就是h i t s 算法的基本思想。图( 3 ，1 21 ) 展 示了两种页面的简单结构。 南京理工大学硕士论文基于增量反馈和自适应机制的主题爬虫系统的设计与实现 h u b sa u t t l o r i t i e s 图3 1 2 1 两种网页结构示意图 x ( u ) = s u m ( y ( v ) ) ，v v ：( v ，“) e y ( u ) = s u m ( x ( v ) ) ，v v ：( u ，v ) e 图3 1 2 2 两种操作示意图 我们可以利用中心页面和权威页面之间的相互关系来计算各个页面的权重。对 于每个页面u ，假设其a u t h o r i t y 值为，其h u b 值为y 。如果页面有高的x 值， 它就是好的a u t h o r i t y 页面，有高的y 值，它就是好的h u b 页面。很自然地两种页 面之间就存在着以下数学关系：如果页面u 被很多高x 值的页面链入，那么，它 肯定会获得高y 值：相反，如果u 被很多高y 值的页面链