（计算机应用技术专业论文）军训网主题搜索引擎技术研究.pdf

摘要 随着i n t e r n e t 的迅速发展，网络信息增长的速度和人们获取所需信息能力之间的矛 盾越来越突出。本文围绕主题搜索引擎这一社会研究的新热点技术，对主题搜索引擎 中占有重要地位的主题蜘蛛给予研究和讨论。主题搜索引擎中的信息采集，即主题蜘 蛛系统的搜索策略的研究，对于主题搜索引擎的应用与发展具有非常重要的作用。论 文首先对主题搜索引擎的原理和结构进行介绍，引出主题蜘蛛，分析了其基本结构和 工作原理。又详细的介绍了主题蜘蛛的其他相关技术，如文本分类和主题描述。然后 抓住如何评价页面的主题相关性和设计高效的爬行策略这两个关键问题，从军训网的 结构入手，在研究大量现有的主题蜘蛛搜索策略基础上，引入链接分析策略，对现存 的搜索策略进行改进，并设计了一个主题蜘蛛模型。最后对该主题蜘蛛的性能进行了 测试，同时给出了实验结果及分析。 关键词：军训网主题蜘蛛主题爬行策略链接分析 a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to ft h ei n t e r n e t ，t h ec o n f l i c ti sb e c o m i n gh u g e ra n dh u g e r b e t w e e nt h eg r o w t ho ft h ew e bi n f o r m a t i o na n dp e o p l e sa b i l i t yt oo b t a i ni n f o r m a t i o n s u r r o u n d i n gt h er e s e a r c ho nt h i sh o t s p o t ，t h ei m p o r t a n tp a r to ft h et o p i cs e a r c he n g i n et h a t i sc a l l e df o c u s e dc r a w l e ri sd i s c u s s e di nt h i sp a p e r t h er e s e a r c ho nt h es e a r c h i n ga l g o r i t h m i sv e r yi m p o r t a n tt ot h ea p p l i c a t i o na n dd e v e l o p m e n to ft h et o p i cs e a r c he n g i n e a tf i r s t ，t h e b a s i ct h e o r yo ft h et o p i cs e a r c he n g i n ea n di t sf r a m e w o r ka r es i m p l yi n t r o d u c e di nt h i s p a p e r t h ef o c u s e dc r a w l e ri sb r o u g h tf o r w a r d a n di t sw o r kt h e o r yi sa n a l y z e d t h e ns e v e r a l r e l a t e dt h e o r ys u c ha st e x tc l a s s i f i e da n dt o p i cd e s c r i p t i o na r ed i s c u s s e d a n dt h e nw e c o n c e n t r a t eo nt w ok e yi s s u e s ，h o wt oe v a l u a t i o nt h er e l e v a n c eb e t w e e nt h ep a g ea n dt h e t o p i ca n dd e s i g nah i g he f f i c i e n ts t r a t e g y , s t a r tf r o mt h ea n a l y z i n gt h es t r u c t u r eo ft h e m i l i t a r yt r a i n i n gn e t w o r k ，b a s e do nl a r g e rn u m b e ro fe x i s t i n gs t r a t e g y , i m p o r tl i n ka n a l y s i s s t r a t e g y , i m p r o v et h ee x i s t i n gs t r a t e g y , a n dd e s i g nat o p i cs p i d e r a tl a s t ，t h ep e r f o r m a n c eo f t h es p i d e ri st e s t e da n dt h er e s u l ti sp r e s e n t e d k e yw o r d s ：m i l i t a r yt r a i n i n gn e t w o r k t o p i c a ls p i d e rt o p i cc r a w l i n gs t r a t e g y l i n ka n a l y s i s 长春理工大学硕士学位论文原创性声明 本人郑重声明：所呈交的硕士学位论文，军训网主题搜索引擎技术研究是本人 在指导教师的指导下，独立进行研究工作所取得的成果。除文中已经注明引用的内容 外，本论文不包含任何其他个人或集体己经发表或撰写过的作品成果。对本文的研究 做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的 法律结果由本人承担。 作者签名： 立月_ 日 长春理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“长春理工大学硕士、博士学位论文版权使 用规定”，同意长春理工大学保留并向中国科学信息研究所、中国优秀博硕士学位论文 全文数据库和c n k i 系列数据库及其它国家有关部门或机构送交学位论文的复印件和电 子版，允许论文被查阅和借阅。本人授权长春理工大学可以将本学位论文的全部或部 分内容编入有关数据库进行检索，也可采用影印、缩印或扫描等复制手段保存和汇编 学位论文。 作者繇施垡l 净年立月以日 指导导师签名：铷4 年4 月疆日 4 2 第一章绪论 1 1 背景 生产力的发展和人类文明的进步都离不开知识的积累。从古到今，人们一直梦想 着将世界上所有的知识汇总起来，做成一部百科全书，以便在解决问题的时候能够更 方便。然而在网络的快速发展看来要将这个乌托邦式的梦想付诸实现的时候，一个更 严峻的问题摆在了人们面前，即如何利用这部包罗万象的知识宝库呢，如何翻阅这本 厚厚的百科全书呢? 随着i n t e m e t i n t r a n e t 的迅速发展，网络正深刻地改变着我们的生活。而在网上发 展最为迅猛的w w w ( w r o r l dw i d ew r e b ) 技术，以其直观、方便的使用方式和丰富的 表达能力，已逐渐成为i n t e r a c t 上最重要的信息发布和传输方式。随着信息时代的到来 和发展，w e b 上的信息如雨后春笋般迅速增长起来。截止到2 0 0 7 年1 2 月，中国网页 数约为8 4 7 亿个，年增长率达到8 9 4 ，网上信息资源的增长速度非常迅猛。 然而，w e b 信息的急速膨胀，在给人们提供丰富信息的同时，又使人们在对它们 的有效使用方面面临一个巨大的挑战。一方面网上的信息多种多样、丰富多彩，而另 一方面用户却找不到他们所需要的信息。为解决“信息爆炸带来的这些问题，各种 新技术应运而生；传统的信息检索( i n f o r m a t i o nr e t r i e v a l ) ，机器学习，自然语言处理 技术也被广泛的应用于w e b 。其中最突出的技术莫过于搜索引擎。因而基于w w w 的 网上信息的采集、发布和相关的信息处理日益成为人们关注的焦点。 1 1 1 通用搜索引擎 为此，人们发展了以w e b 搜索引擎为主的检索服务。为了解决网上信息检索的难 题，人们在信息检索领域进行了大量的研究，开发了各种搜索引擎( 如g o o g l e 、b a i d u ) 。 这些搜索引擎通常使用一个或多个采集器从i n t e m e t 上收集各种数据，然后在本地服务 器上为这些数据建立索引，当用户检索时根据用户提交的检索条件利用索引库迅速查 找到所需的信息。 ( 1 ) 通用搜索引擎工作原理 搜索引擎的实现原理，可以分为四步：从互联网上抓取网页一建立索引数据库一 在索引数据库中搜索一对搜索结果进行处理和排序。通常由三个子系统组成口1 ，如图 1 1 所示。数据采集子系统从一个或多个初始网页出发遍历互联网自动地采集网上信 息，数据索引子系统对采集来的网页进行索引并存储到索引数据库中。而数据检索子 系统则等待用户的查询指令，对用户的查询信息进行分析，然后在索引数据库中进行 检索，并根据一定的策略对结果进行排序，最后将结果返回给用户。 图1 1 搜索引孥工作流程图 ( 2 ) 通用搜索引擎存在的问题 传统的w e b 信息采集的目标就是尽可能多地采集信息页面，甚至是整个w e b 上的 资源，而在这一过程中它并不太在意采集的顺序和被采集页面的相关主题。这样做的 一个极大好处是能够集中精力在采集的速度和数量上，并且实现起来也相对简单，例 如g o o g l e 采集系统在并行4 个采集器时的速度可以达到每秒1 0 0 页，从而它配合搜索 引擎给网络用户带来了很大的便利。但是，这种传统的采集方法也存在着很多缺陷。 随着万维网信息的爆炸性增长，信息采集的速度越来越不能满足实际应用的需要。即 使大型的信息采集系统，它对网络的覆盖率也只有3 0 - - 一4 0 。解决这一问题的直接办法 是升级信息采集器的硬件，采用处理能力更强的计算机系统，然而这种方法的扩展性 有限，性价比也不高。一个更好的解决方法是采用分布式方法来提高并行能力，但是 并行不但增加了系统的开销和设计的复杂性，并且并行换来的效益也随着并行采集器 数目的增加而显著地减小。目前，一般的大型采集系统都采用了并行机制，但并行带 来的改善效果仍远不能满足人们的需要。人们需要从其它角度改善目前的困境。比如 说对整个网络分块采集，并将不同块的采集结果整合到一起，以提高整个w e b 的采集 覆盖率。i n t c r n e t 信息的分散存储、管理和动态变化也是困扰着信息采集的问题之一。 由于信息源随时可能处于变化之中，信息采集器必须时常地刷新数据，但仍无法避免 采集到的页面失效的情况。对于传统的信息采集来说，待刷新页面数量的巨大使得很 多采集系统刷新一遍需要数周到一个月的时间，这使得页面的失效率非常地巨大。一 个显然的缓解办法就是减小采集页面的数量，从而减小刷新一遍的时间，进而减小页 面已采集页面的失效率。 传统的基于整个w e b 的信息采集需要采集的页面数量十分浩大，这需要消耗非常 大的系统资源和网络资源，而对这些资源的消耗并没有换来采集到页面的较高利用率， 事实上，它们中有相当大的部分利用率很低。这是因为，用户往往只关心其中极少 量的页面，并且这些页面往往集中在一个主题或几个主题内，而采集器采集的大部分 页面对于他们来说是没有用的。尽管许多用户合起来的效果提高了整个采集到页面的 2 利用率，但仍然显得利用率偏低，这显然是对系统资源和网络资源的一个巨大浪费。 为了有效的提高它们的利用效率，有必要另辟蹊径。对于用户的一般信息查询检索要 求，传统信息采集器所组成的搜索引擎能够提供较好的服务，但对于用户更多的具体 要求，这种传统的基于整个w e b 的信息采集所提供的服务就难以令人满意。对于每个 用户来说，尽管他们输入同一个查询词，但他们渴望得到的查询结果却是不一样的， 而传统的信息采集和搜索引擎却只能死板地返回相同的结果，这是不合理的，需要进 一步提高。 这些问题主要都源于两点：采集页面的数量过于庞大和采集页面内容的过于杂乱。 对整个w e b 页面进行分类，按类别采集，基于主题进行采集的思想应运而生。它有效 的减少了采集页面的数量，增加了采集页面的规整程度，进而有效的缓解了上述问题。 因此需要开展对主题搜索引擎技术的研究。 1 1 2 主题型搜索引擎 主题搜索引擎是在传统的搜索引擎基础上发展而来的。根据用户需求主题，搜索 有限的网络空间，发现、下载与主题相关的信息，建立主题资源库，提供专题信息服 务。 主题搜索引擎面向某一特定的专业领域，专注于自己的特长和核心技术，它最大 的优势就在于能够把具有相同兴趣点的人们集中在一个主题社区内，通过及时集中提 供各种专业资源查询，避免了大量的搜索噪音，提高了查询效率。在提供专业信息方 面有着很大的优势。 主题搜索引擎的性能关键点在于主题蜘蛛的设计。主题式搜索引擎的网络蜘蛛的 设计目标是搜索与特定主题相关的网页，主题搜索引擎网络蜘蛛的资源搜索目的是获 得尽可能多的相关专业领域的资源。由于一个网络蜘蛛系统的数据处理能力和获取资 源的总的网络带宽是有限的，特别是主题搜索引擎的规模一般都远小于通用搜索引擎， 因此主题搜索引擎更加关注于搜索回来的资源的高质量。所以需要一个有效的主题蜘 蛛的搜索策略。 1 1 3 主题蜘蛛搜索策略 主题搜索最早是由c h a r k r a b a r t i 等人口1 于1 9 9 9 年提出的。在他的论文中，给出了主 题搜索的基本框架。其后的几年，对于主题搜索的研究进入了空前繁荣的时期。对于 主题搜索的研究，主要集中在两个热点： 一是如何定义主题，也就是用户如何表示自己想要获取的网页；二是如何有效地 组织爬行队列，使爬行过程可以尽可能少的下载与主题不相关的网页。 对第一个问题的研究，主题搜索领域基本确立了以文本分类器定义主题的基本框 架。文本分类是数据挖掘的一个分支，它通过对训练样例的学习，可以获取相关的知 识框架，利用这个知识框架，可以进一步挖掘待分类文本的属性。将文本分类用于主 题定义是一种自然的选择。网页本身就是文本，而网页的主题正蕴含在文本中，使用 文本分类正可以对文本中的主题进行获取，继而对爬行器获取的网页的主题进行判断。 3 对第二个问题的研究，又称之为搜索策略的研究。目前，搜索策略的研究，集中 在两个方向。一是基于内容的搜索，二是基于链接结构分析的搜索。 1 基于内容的搜索 此类搜索方式是传统信息检索技术的延伸。它的主要方式就是在搜索引擎内部建 立一个主题对应的关键词表，搜索引擎的爬行器根据其内设的关键词表对网上的信息 进行索引。这种关键词表的设置越来越多的引入了知识表示的方法。 基于本体论的搜索引擎开始出现。一个本体强调相关领域的本质概念，同时也强 调概念间的本质联系。以o n t o l o g y h l 为基础的关键词表能更好的显示领域主题中的概念 间的关系，从而更好的表现一个主题。在主题信息检索应用中，o n t o l o g y 通常作为用户 感兴趣领域的领域模型，同时还可作为文档统一注释的知识表示语言。 一些研究者还提出了概念空间的理论畸1 ，用其来实现语义索引。概念空间是指领域 中一组抽象概念的集合，在集合中，概念之间并不是相互独立的，而是在语义上存在 着一定的关联。基于概念空间的文本检索系统较好的解决了信息检索过程中词汇不匹 配的问题和信息过载问题，极大提高了信息检索的效率和质量。 2 基于链接结构分析的搜索 9 0 年代末期，国外信息检索界开始以s o c i a ln e t w o r k 为模型对互联网进行检索。一 些学者认为网页之间的链接关系同社会关系网络中的人际关系有着相似之处，特别地 与传统的引文索引非常相似。通过对链接结构进行分析，可以找出网页之间的引用关 系。由于引用网页与被引用网页间内容上一般都比较相关，所以就可以很容易地按照 引用关系将大量网页分类。例如在美国，很多基于超链结构分析的检索系统原型己经 出现，并应用于数字图书馆系统中。 上述两种搜索技术都被用于主题搜索引擎的搜索策略的设计中。基于内容相似度 的评价策略主要特点是利用页面中的文本信息作为领域知识指导搜索，根据页面或链 接文本与主题( 如关键词、主题相关文档等) 之间相似度的高低来评价链接价值。这类搜 索策略中，代表性的有f i s h s c a r c h 和s h a r k s e a r c h 算法。优点是对每个链接的评价直接 且计算简单。缺点是忽略了链接结构信息，无法预测链接价值。基于w e b 结构的评价 策略主要特点是利用w e b 结构信息指导搜索，通过分析w e b 页面之间相互引用的关系 来确定页面和链接的价值，通常认为有较多入链的页面具有较高的价值。p a g e r a n k 和 h i t s 是其中具有代表性的算法。优点是能通过链接关系发现以某个主题而互链的大批 资源，便于深度的资源采集。缺点是在某些情况下，会出现搜索偏离主题的“主题漂 移问题。w e b 结构挖掘算法和内容相似度的计算都需要大量的计算，且都还存在着 不足。如何利用各自的优点? 如何才能用较小的代价来实现搜索策略的优化? 这都是 主题搜索引擎搜索策略研究需要解决的问题。 1 1 4 国内外的研究现状 目前在国外，主题型搜索引擎大都处于研究和试验阶段，但利用它搜索的结果再 经过专业人士的加工而形成的面向某一学科、领域的网络垂直门户网站己经出现。下 4 面介绍一些较具有代表性的系统。 1 ) e l s e v i e r 的s c i r u s 系统 s c i r u s 科学搜索引擎是一种专为搜索高度相关的科学信息而设计的搜索引擎，由爱 思唯尔( e l s e v i e r ) 科学出版社开发，获得2 0 0 1 搜索引擎观察授予的“最佳专业搜 索引擎”奖。s c i r u s 是目前互联网上最全面、综合性最强的科技文献门户网站之一。它 过滤非科学方面的信息，收录同行评审( p e e r - r e v i e w e d ) 的文章，为科学家们在网络上和 专有数据库中快速查找所需的信息打开了一道便捷之门。 2 ) b e r k e l e y 的f o c u s e dp r o j e c t 这个系统由一个印度裔的科学家c h a r k r a b a r t i 带头从事，他是最早从事这方面研究 的人之一。该系统通过两个程序来指导爬行器：一个是分类器c l a s s i f i e r ，用来计算下 载文档与预订主题的相关度；另一个程序是净化器d i s t i l l e r ，用来筛选那些指向很多相 关资源的页面。 3 ) n e c 研究院的c i t e s e e r c i t e s e e r 是一个非常有名的针对计算机科学领域论文的检索系统。c i t e s e e r 的核心 是a c i ( a u t o m a t i c a l l yc i t a t i o ni n d e x ) 哺1 ，其基本原理是根据文献的相互引用关系建立索 引系统，它可以自动地对互联网上的电子文件( p o s t s c r i p t 和p d f 等格式) 进行索引并分 类。 4 ) n o r t hc a r o l i n a 大学的l i bc l i e n t i r i sw e b l i bc l i e n t i r i sw e b 系统是由n o r t hc a r o l i n a 大学计算机科学系和法学院联合开发 研制的。它可以用自然语言对网络上的法律信息进行全文检索，使得法律工作人员、 研究人员、法律专业学生及所有对法律感兴趣的人获取全面高质量的专业信息的效率 大大提高，取得较为令人满意的效果。 5 ) 美国国家科学数字图书馆的c o l l e c t i o nb u i l d i n gp r o g r a m ( c b p ) 这个项目旨在为科学、数学、工程和技术创建大规模的在线数字图书馆，试图研 究在某一主题上资源自动建设的可能性。c b p 具有自己的特点： 因为c b p 是面向教育、面向教学，主题查准率( p r e c i s i o n ) l l 查全率( r e c a l l ) 更为重 要。 c b p 不存储资源原文，而只是提供u r l 。 c b p 只需要用户最少量的输入，如关键词，系统就可以全自动的将有关该主题的 最相关的有限数量u r l 返回给用户。 在国内，研究主题搜索引擎的团队也越来越多。现在开始研究该领域的主要是一 些大学的研究机构和一些搜索引擎公司。比如，北京化工大学就推出了关于化学方面 的专业搜索引擎，其他方面如医药、林业等也有相应的产品。北京大学实现了“天网” 主题搜索引擎。百度等多家搜索引擎提供商也相应的推出了图片搜索、m p 3 搜索、行 业搜索。这些都可以看作是主题式搜索引擎的应用。 5 1 2 军训网简介 军事训练网是依托国防通信设施，为军事训练、教学科研及管理服务的，独立于 i n t e m e t 的专用计算机信息网络系统，简称军训网。与i n t e m e t 相比，军事训练网上的 大部分信息资源是经过筛选的，与教学科研、军事训练工作密切相关的，具有较高参 考价值的信息资源h 1 。随着时间的增长，也积累了相当丰富的信息，如何有效的对这些 信息进行分类，对有用的信息及时的检索利用已经引起了重视。 1 3 本文的工作 本论文主要开展两方面的工作i 一是在仔细研究当前主题搜索引擎相关文献的基 础上，抓住如何评价页面的主题相关性和设计高效的爬行策略这两个关键问题，结合 现有的搜索策略，对搜索策略进行改进，确定主题蜘蛛的搜索策略。分析主题搜索策 略中基于内容的策略、基于链接结构的策略，提出本系统将要采取的搜索策略；二是 通过对军训网的分布特征的研究，提出了基于链接分析的策略对军训网的主题蜘蛛进 行改进。 1 4 本文的组织 本文余下部分组织如下： 第二章概述主题爬虫的原理及其相关知识。 第三章详细分析现有的主题爬虫搜索算法。 第四章详细介绍系统的设计过程。 第五章对实验结果进行了分析。 第六章是对本文工作的总结以及未来工作的展望。 6 第二章主题蜘蛛概述 本章主要围绕主题蜘蛛的基本问题展开研究。主要内容包括主题蜘蛛的基本原理、 主题页面分布情况、主题描述和文本分类。 2 1 主题蜘蛛的基本原理与结构 网络信息提取，主要是指根据页面间相互的链接关系，自动从网络中获取页面信 息，并且随着链接不断的进行页面扩展的过程。实现这一过程主要是由网络蜘蛛 ( s p i d e r ) 来完成的。根据应用习惯的不同，也常称为网络爬虫和网络机器人。网络蜘 蛛程序从一个初始的u r l 集合出发，将这些u r l 全部放入到一个有序的队列里面， 信息提取器从这个队列里按顺序取出u r l ，通过网络协议，获取u r l 指向的页面，然 后再从这些已获取的页面中分析提取新的u r l ，并将他们按照一定策略放入到待提取 u r l 队列里，然后重复上述过程，直到信息提取器根据自己的搜索条件停止为止。 主题搜索引擎的基础和核心就是主题蜘蛛。主题蜘蛛是在通用蜘蛛基础上加入页 面的过滤，其基本结构如图2 1 所示。 请求页面一 下载页面 下载的页面 提取链接结构信息 出队一 提取的u r l 入队 图2 1 主题蜘蛛模型 主题蜘蛛对w e b 的搜索是一个循环迭代的过程：首先从一个“种子集( 如种子链 接或种子页面) 出发，通过h 1 r r r p 协议请求并下载w e b 页面；预处理器负责解析w e b 页面，提取链接文本、结构信息和链接的u r l s ；链接价值计算器按照某种评价方法( 如 链接文本与预先定义的主题集的相似度) 计算出每个链接的价值；暂时未被访问的链接 被暂存在一个链接优先权队列中，链接优先权控制器按照某种策略决定下一步将要访 问的链接；当s p i d e r 获得新选定的链接时，以上过程重复进行。主题蜘蛛通常采用“最 好优先”原则访问网络，即为快速、有效地获取更多的与主题相关的网页，每次选择 7 最有价值的链接进行访问。由此可知，链接价值计算器和u r l 优先权控制器是蜘蛛模 型的核心，决定蜘蛛搜索策略的关键是如何评价链接价值，即链接价值的计算方法， 不同的链接价值评价方法决定不同的链接访问顺序，从而决定不同的搜索策略。 2 2 军训网主题页面的分布特征 军训网虽然与i n t e r n e t 在物理上隔绝，但原理是相通的。由于其没有商业化，使得 军训网比i n t e r n e t 更加规律，噪音更加少。主题页面在军训网上的分布服从一定的规律。 主题页面容易成团出现，而在具体的内容网页上，通常会出现与所表现内容相关的网 页的链接。可以将这些分布规律总结为以下几个特征：h u b 特征，l i n k a g e s i b l i n g l o c a l i t y 特征，站点主题特征，t u n n e l 特征。通过对他们的研究和开发利用，可以对主 题蜘蛛的搜索策略进行改进。 2 2 1h u b 特征 美国康奈尔大学k l e i n b e r g 教授发现w e b 上存在大量的h u b 页面，这种页面不但 含有许多指出链接，并且这些链接趋向于同一主题。换而言之，h u b 页面是指向相关 主题页面的一个中心页面。另外，k l e i n b e r g 还给出了权威页面( a u t h o r i t y ) 的概念1 ，即 权威页面是那些关于某一主题有价值的页面。好的h u b 页面指向多个a u t h o r i t y 的页面， 并且所指向的a u t h o r i t y 页面权威性越高，h u b 页面的质量越好；反之，h u b 页面的质 量越好，它所指向的页面也越权威。根据这个思想，k l e i n b e r g 提出了h i t s 算法。 权威网页，即给定主题下的一系列重要的参照网页，对于主题搜索引擎的实现有 重大意义权威网页的重要性和样本性体现在以下两方面：第一，网页内容本身对于这 个给定主题来说是重要的；第二，这个网页是被其他网页承认为权威的，主要体现在 和这个主题相关的很多网页都有链接指向这个网页。由此可见，主题搜索引擎一个关 键的任务就是从网络上无数的网页之中最快最准地找出这些可数的权威网页，并为其 建立索引。 目录网页是包含指向一个或者多个权威网页的超链接的网页的集合。目录网页具 有数据仓库的一般特征： 面向主题性，它排除对于决策无用的数据，提供特征主题的简明视图，即含有指 向各主题权威网页的超链接的集合。 集成性，构造的目录网页是将多个异种数据源集成在一起，即指向多个主题不同 类型信息的集合体。 时变性，目录网页的关键结构中包含的时间因素，即具有明显的动态时变性。 目录网页起到了隐含说明某主题权威网页的作用。通常，好的目录网页指向许多 好的权威网页；好的权威网页也必然由许多好的目录网页所指向。这种权威网页和目 录网页之间的相互作用可用于权威网页的挖掘。 2 2 2 l i n k a g e s i b l i n gl o c a l i t y 特征 a g g a r w a l 阳3 等人提出了主题页面的l i n k a g e s i b l i n gl o c a l i t y 特征。 8 1 ) l i n k a g el o c a l i t y ，即页面倾向于拥有链接到它的页面的主题； 2 ) s i b l i n gl o c a l i t y ，对于一个链接到某个主题页面的页面而言，它所链接指向的其 它页面也倾向于和这个主题相关。该特征其实是h u b 特性的另一种表达形式，只不过 它是从页面编辑者的角度来考虑的：即一个页面的编辑者倾向于在本页面中添加指向 与本页面相关的其他页面的超级链接。 在军训网中，这个特征尤为明显。由于军训网的建站目的，使得其网站的分布规 律性特别的强。 2 2 3 站点主题特征 通过对军训网观察研究发现，相同主题的页面较紧密地在此站点内部链接成团， 而各个主题页面团之间却链接较少。对i n t e r n e t 上的网站有研究对站点页面树按照自底 向上进行主题聚类，这样一个站点所要说明的一个主题或多个主题就确定了( 如果聚为 一个类，说明站点只有一个主题，如果聚为多个类，则说明站点有多个主题) n 们。这种 特征主要与人们使用分类分层的思维对进行事务处理的习惯有关。每个网站均有一个 明确的设计目标，其所包网页往往只和一个或几个主题相关。而多数浏览者在浏览网 页的同时往往带有一定的目的性，即一个用户倾向于浏览一些特定主题的页面。 2 2 4t u n n e l 特征 在w e b 中还有一种现象，就是尽管在w e b 上存在很多主题页面团，但是在这些页 面团之间，往往是通过较多主题无关链接连接在一起。这些无关链接在主题页面团之 间，就好像一个长长的隧道。这就是t u n n e l 特征。在面向主题的页面提取过程中，t u n n e l 的存在会影响着w e b 信息提取的质量。为了提高提取页面的准确率，需要提高主题相 关性判别算法中的过滤阀值，但是阀值的提高会过滤掉大量的t u n n e l ，使得采集系统 很可能会丢失掉t u n n e l 另一端的主题页面团，从而影响查全率( r e c a l l ) 。反之，为了 提高查全率，就得大量保存t u n n e l ，需要降低主题相关性判别算法中的过滤阀值，但 阀值的降低使得在保留t u n n e l 的同时，也混入了大量无关页面，从而造成页面提取的 准确率的降低。这是一个两难问题。该问题随着提取页面数量的不断增加会逐渐减轻， 因为根据s i b l i n g l i n k a g el o c a l i t y 特征，绝大多数主题团还是可以被主题网络蜘蛛通过 其它的链接途径发现的。 2 3 主题描述 主题搜索引擎的实现首先要对让机器知道你所要搜索的主题，本节对主题描述进 行研究。 准确反映主题是决定主题型w e b 搜索器质量的前提。主题的描述通常有两种方法： 一种方法被称为k e y w o r d d r i v e n ，即给出各主题关键字的方式定义主题，这种方 式比较简单，但准确性不高，而且客观因素比较大；另一种方法被称为 e x a m p l e d r i v e n 即为各主题分别给出一些示例文档，这种方式定义主题需要一个 学习过程，但比第一种方法复杂性要高。 9 这里需要指出的是：提交反映主题的样例文档( 事先人工收集好的w e b 网页集合) 是准确表达主题的强有力方式。这种方式下，主题蜘蛛把样例文档作为训练集，利用 特征提取技术和机器学习中的分类算法自动识别模式，然后，主题蜘蛛通过己识别的 模式来判别下载网页与主题的相关性。 显然，要准确反映主题就必须拥有高质量的样例文档集合。有效的文档自动分类 算法都需要一个非常大的样例文档集合作为训练集。而收集这样的样例文档集合需要 事先花费专家( 或普通用户) 许多宝贵的时间。这又为主题搜索引擎的设计提出了一个挑 战：如何利用一个非常小的训练文档集来构造一个能够相当准确地反映用户兴趣主题 的分类器。s i z o v 等n 妇提出了一种有效的方法，它将爬行分为两个阶段：第一段称为学 习阶段，通过采用深度优先的爬行策略，从初始的训练集合( 种子) 直接下载相邻的网页， 然后利用分类器进行分类。这时为了保证分类质量，需要设定一个较高的可信度阈值， 大于该阈值的被分类网页将被认为是相关的，并放入训练集。这样，可以不断扩展知 识库( 更大的特征集) ；第二阶段称为收获阶段，在成功扩展了训练集合后，重新训练所 有主题分类器，然后采用最佳优先搜索来广泛获取与主题相关的资源。 2 4 文本分类 有了可理解的主题，就可以对下载下来的页面进行分类。文本分类主要是根据文 本的内容自动地确定与文本关联的类别。下面对文本分类进行简单介绍。 2 4 1 文本的表示 计算机并不具有人类的智能，人在阅读文章后，根据自身的理解能力可以产生对 文章内容的模糊认识，而计算机并不能轻易地“读懂 文章，从根本上说，它只认识0 和1 ，所以必须将文本转换为计算机可以识别的格式。根据“贝叶斯假设”，假定组成 文本的字或词在确定文本类别的作用上相互独立，这样，可以就使用文本中出现的字 或词的集合来代替文本，不言而喻，这将丢失大量关于文章内容的信息，但是这种假 设可以使文本的表示和处理形式化，并且可以在文本分类中取得较好的效果。目前， 在信息处理方向上，文本的表示主要采用向量空间模型( v s m ) 。 向量空间模型是s a l t o n 等人于6 0 年代末提出的，并成功的应用于著名的s m a r t 系统。该模型及其相关的技术，包括项的选择、权重赋值策略，以及采用相关反馈进 行查询优化等技术，在自动索引、信息检索等许多领域得到了广泛的应用，已成为最 简单高效的文本表示模型之一。向量空间模型的一个基本假设是，一份文档所属的类 别仅与某些特定的单词或词组在该文档中出现的频数有关，而与这些单词或词组在该 文档中出现的位置或顺序无关。也就是说，如果将构成文本的各种语义单位( 如单词、 词组) 统称为“词项”，以及词项在文本中出现的频数成为“词频”，那么一份文档中 蕴涵的各个词项的词频信息足以用来对其进行正确的分类。向量空间模型的基本思想 是以向量来表示文本： 假设出现在文档集合c 中有n 篇文档d 1 ，d 2 ，d 。，含有m 个特征项t l ，t 2 ， 1 0 t m 。则有： d i = ( d i l ，d i 2 ，d i m )( 15 isn ) ( 2 - 1 ) c 一( w ) ( 1sisn ，1s js m ) d 即c 的第i 个行向量。 那么选取什么作为特征项呢，一般可以选择字、词或词组，普遍认为选取词作为 特征项要优于字和词组，因此，要将文本表示为向量空间中的一个向量，就首先要将 文本分词，由这些词作为向量的维数来表示文本，最初的向量表示完全是0 、1 形式， 即，如果文本中出现了该词，那么文本向量的该维为1 ，否则为0 。这种方法无法体现 这个词在文本中的作用程度，所以逐渐o 、1 被更精确的词频代替。词频分为绝对词频 和相对词频，绝对词频，即使用词在文本中出现的频率表示文本，相对词频为归一化 的词频u 2 1 。 2 4 2 特征项的抽取 构成文本的词汇，通常数以万计，因此，表示文本的向量空间的维数也相当大， 可以达到几万维，所以需要进行降维的工作。降维技术可以分为两类：特征选择及特 称重构n3 l 。这里主要介绍特征选择的一些方法。 首先要对特征项进行深入理解。特征项的权重反映了该特征项对文本内容的贡献 程度和文本之间的区分能力。特征项在不同文本中出现的频率满足一定的统计规律， 因此可以通过特征项的频率特性计算其权重。一个有效的特征项集合必须满足以下两 个特点： 概括性：特征项能够反映目标文本的内容； 区分性：特征项能够将目标文本和其他文本相区分的能力。 根据以上两个特点，特征权重的计算必须遵循以下两个原则：一是正比与特征项 在文本中出现的频率；二是反比于文本集合中出现该特征项的文档频率。 特征项抽取的目的主要有两个，第一，为了提高程序的效率，提高运行速度；第 二，所有几万个词汇对文本分类的意义是不同的，一些通用的、各个类别都普遍存在 的词汇对分类的贡献较小，在某特定类中出现比重大而在其他类中出现比重小的词汇 对文本分类的贡献大，为了提高分类精度，对于每一类，应去除那些表现力不强的词 汇，筛选出针对该类的特征项集合。目前，中文文本分类中经常采用的特征抽取方法 包括最简单的文档频率( d f ) 、互信息( m i ) 、信息增益( i g ) 和c h i 统计等n 4 1 。 1 文档频率( d f ) 词条的文档频率( d o c u m e n tf r e q u e n c y ) 是指在训练语料中出现该词条的文档数。采 用d f 作为特征抽取是基于如下基本假设：d f 值低于某个阈值的词条是低频词，它们 不含有类别信息，将这样的词条从原始特征空间中移除，能够降低特征空间的维数， 不会对分类器的性能造成影响。如果低频词恰好是噪音词，还有可能提高分类器的性 能。在实验中，统计每个词条在训练语料中的文档频率，从原始特征空间中移除文档 频率低于某一阈值的词条，保留文档频率高于该阈值的词条作为特征。文档频率是最 简单的特征抽取技术，由于其具有相对于训练语料规模的线性计算复杂度，它能够容 易地被用于大规模语料统计。但是在信息抽取研究中却通常认为d f 值低的词条相对于 d f 值高的词条具有较多的信息量，将这些词条从特征空间中移除会降低分类器的准确 率。 2 互信息( m i ) 互信，皂, ( m u t u a li n f o r m a t i o n ) 在统计语言模型中被广泛采用。词条t 和文档类别c 的 互信息定义为： ( 2 2 ) 其中p ( t c ) 表示语料中属于c 且包含t 的文档频数，p ( t ) 表示语料中包含词条t 的文档的 概率，p ( c ) 表示语料中c 类文档出现的概率。 用互信息的方法，在某个类别c 中的出现概率高，而在其它类别中的出现概率低的 词条t ，将获得较高的词条和类别互信息，也就可能被选取为类别c 的特征。词条和类 别的互信息体现了词条和类别的相关程度，互信息越大，词条和类别的相关程度也越 大。 3 信息增益0 g ) 信息增益评估的是通过一项是否出现在文档中所获得的能够用于分类预期的信息 量。在文本特征抽取中，对于词条t 和类别c ，i g 考察c 中出现和不出现t 的文档频数 来衡量t 对于c 的信息增益。信息增益的计算公式如下： ，g ( t ) ；一z p ) l o g p ( c 0 + p o ) p ( c ；i f ) l o g e ( c r l f ) + p ( f ) p ( c t l f ) l o g p ( c t i t ) ( 2 - 3 ) 其中p ( c j ) 表示a 类文档在语料中出现的概率，p ( t ) 表示语料中包含词条t 的文档的概率， p ( c ；i t ) 表示文档包含词条t 时属于c i 类的条件概率，p o ) 表示语料中不包含词条t 的文 档的概率，p ( c il f ) 表示文档不包含词条t 时属于c ；的条件概率，m 表示类别数。 4 c h i 统计 c h i 统计方法度量词条t 和文本类别c 之间的相关性，并假设t 和c 之间符合具有 一阶自由度的z 2 分布。词条对于某类的z 2 统计值越高，它与该类之间的相关性越大， 携带的类别信息也较多。令n 表示训练语料中的文本总数，c 为某一特定类别，t 表示 特定的词条，a 表示属于c 类且包含t 的文档频数，b 表示不属于c 类但包含t 的文档 频数，c 表示属于c 类但不包含t 的文档频数，d 是既不属于c 也不包含t 的文档频数。 则t 对于c 的c h i 值由公式计算： 轵i ) ：焉共黑( 2 - 4 ) 於，c j ) 5 而酉丽汉鬲丽而 目前，已经有多项研究完成了不同降维方法的比较，结果显示这些降维方法都可以 1 2 提高d f 方法的效果。但是i g 计算信息量较大，c h i 统计是基于z 2 分布的，所以本文 选择m i 进行特征选择。 2 4 3 训练方法与分类算法 训练方法和分类算法是文本分类系统的核心部分，目前存在多种基于向量空间模 型的训练算法和分类算法，例如，支持向量机算法( s v m ) n5 1 、神经网络方法、r o c c h i o s 方法、决策树方法、最近k 邻近方法和朴素贝叶斯方法等等，本文以下具体介绍四种 分类算法： 1 r o c c h i o s 方法 r o c c h i o s 算法n 町是基于高等数学向量理论的一种经典分类算法。它首先将文本表 示为向量模型的形式。其分类的基本思想是：使用训练集为每个类构造一个原型向量， 构造方法如下： 给定一个类，训练集中所有属于这个类的文档对应向量的分量用正数表示，将该 类向量求和并求平均值；所有不属于这个类的文档对应向量的分量用负数表示，同样 的将该类向量求和并求平均值；最后将二者分别乘以不同的系数，相加，得到的和向 量就是这个类的原型向量。具体的可以用公式表示为： 夏蛐高荟尚一高b 。羡禹( 2 - 5 ， 其中c k 为属于c k 的文档的集合，口，卢分别为相关，不相关文档的影响因数。 给定一篇待分类文档，则逐一计算这篇文档与原型向量的距离。计算距离的方法 可以使用求向量点乘积，或者计算j a c c a r d 相似度等方法。距离越近，则这篇文档与这 个类就越相关，反之亦然。r o c c h i o s 算法的突出优点是容易实现，计算( 训练和分类) 简单。 2 朴素贝叶斯方法 贝叶斯分析方法的特点是使用概率去表示所有形式的不确定性，学习或者其他形 式的推理都用概率规则来实现。对于分类问题，有些情况下，输入的特征向量唯一对 应一个类别，这种问题称为确定性的分类问题；而有些情况下，则会出现类别重叠的 现象，也就是说，来自不同类别的样本从外观特征上具有极大的相似性，这时只能说 此样本属于某一类别的概率是多大，然而却必须为它选择一个类别，贝叶斯算法通常 使用的是选择后验概率最大的作为该样本的类别。 设文本向量d ，类别q ，根据贝叶斯理论有： p m = 鼍驴 ( 2 - 6 ) 在具有许多特征的文本向量中，算- p ( c i i a ) 的开销非常大。为了降低这种计算开 1 3 销，给出了一种朴素假设：假定文档的特征对于给定的类别独立，那么p ( c i i a ) 可以分 解成几个分量的积： ( d 。lc i ) p ( d 2ic ，) “甲( d 。ic i ) 基于以上可知后验概率的简化式为： p ( c f l a ) = 篇盼一i )p 旧jj 1 1 ( 2 - 7 ) 朴素贝叶斯分类模型的训练过程其实就是统计训练集合中出现的每个特征在各个 类别中出现的规律过程。通常选取后验概率p i d ) 作为文本向量d 的类别，而在对新 文本类别判定时，计算公式中p ( d ) 是相同的，所以可以忽略此项，得到最终类别判断 公式为： c o b ( d ) 一a r g m a x