（计算机软件与理论专业论文）基于文档分类及超链接优选策略主题蜘蛛的研究与实现.pdf

西南交通大学硕士研究生学位论文第1 页 捅斐 随着i n t e r n e t 的迅速发展，网络信息增长的速度与人们获取所需信息能 力之间的矛盾越来越突出。搜索引擎这一新兴技术也越来越体现出其自身的 重要价值。作为搜索引擎的数据后勤保障，网络蜘蛛的发展也越来越迅速。 论文从研究互联网络上信息的分布特征入手，对“主题网络蜘蛛 这一 新型的网络蜘蛛原理、策略、结构、工作模式、调度机制以及实现上进行了 深入的分析研究。论文设计了一个主题网络蜘蛛系统一一f o c u sc r a w l i n g s p i d e r ，在w i n d o w s 环境下采用c + + 实现了该系统。 在f o c u sc r a w l i n gs p i d e r 系统的页面主题相关性判定策略中引入了文档 自动分类的思想，提出了基于简单向量距离法、k n n 算法以及朴素贝叶斯算 法综合对页面进行主题相关性判定的页面相关性的方法；同时在u r l 剪枝部 分，论文提出了将“侵入式鱼群算法( i n v a s i v ef i s hs e a r c h ，i f s ) ”应用于 f o c u sc r a w l i n gs p i d e r 系统，增强了该系统穿越“隧道的能力，增加了该系 统的爬行覆盖率。 论文对f o c u sc r a w l i n gs p i d e r 系统的各个功能模块的设计与实现都进行 了详细的论述，包括大量的效率瓶颈的分析以及解决方案。在系统结构、页 面采集、u l u ( u n i f o m lr e s o u r c el o c a t o r ，i j l u ) 管理、u r l 评价、d n s ( d o m a i n n a m es e r v e r ，d n s ) 缓存系统、d o m ( d o c u m e n to b j e c tm o d e l ，d o m ) 结 构生成、h t m l ( h y p e r t e x tm a r k u pl a n g u a g e ，h t m l ) 解析等方面都提出并 实现了一些创新点。 论文从运行效率和爬行策略的改进效果等方面对f o c u sc r a w l i n gs p i d e r 系统进行了运行测试。通过对测试数据的分析比较，得到了较好的结果。 关键词：搜索引擎；网络蜘蛛；主题爬行；文本分类； 西南交通大学硕士研究生学位论文第l i 页 a b s t r a c t w i t ht h er a p i dg r o w t ho ft h ei n t e r n e t ，t h ec o n f l i c tb e t w e e nt h eg r o w t ho ft h e w e bi n f o r m a t i o na n dt h ea b i l i t yo fp e o p l eo b t a i nt oi ti sb e c o m i n gh u g e ra n dh u g e r t h es e a r c he n g i n e ，a l le m e r g i n ga r e ao ft e c h n o l o g ya l s om a n i f e s t si t so w n i m p o r t a n c e w e bs p i d e r t h ed a t as u p p o r t e ro fs e a r c he n g i n e s ，b e c o m e sm o r ea n d m o r ea d v a n c e d i nt h i st h e s i s ，t h ed i s t r i b u t e dc h a r a c t e r i s t i co fw e bp a g e s ，a n da n a l y z e dt h e p r i n c i p l e ，s t r a t e g y , s t r u c t u r ec o m p o s i t i o n ，w o r k i n gm o d e l ，d i s p a t c h e rm e c h a n i s m o fw e bs p i d e r sh a v eb e e nr e s e a r c h e dd e e p l y , a n daw e bs p i d e rs y s t e mu n d e r w i n d o w se n v i r o n m e n t - f o c u sc r a w l i n gs p i d e rs y s t e m i si m p l e m e n t e d ，w h i c hi s d e v e l o p e d w i t hc + + a u t o m a t i ct e x t c a t e g o r i z a t i o n sa r e i n t r o d u c e di nf o c u sc r a w l i n gs p i d e r s y s t e m t h ep a g et o p i cd i s t i n g u i s h i n gm o d u l ei sb a s e do na na l g o r i t h mw h i c h i n t e g r a t e d s i m p l ev e c t o rd i s t a n c e k n n a n d n a i v eb a y e s m e t h o d i n a d d i t i o n ，w eh a v ed e s i g n e d “i n v a s i v ef i s hs e a r c h ( 环s ) ”m e t h o df o rt h eu r l p r u n i n gm o d u l es ot h a tt h es p i d e rs y s t e mc a np a s st h r o u g ht h e t u n n e l s e a s i e r , a n dc r a w lw i d e l yi nt h ei n t e r n e t t h ed e s i g na n di m p l e m e n t i o no ft h ef u n c t i o nm o d u l e si nf o c u sc r a w l i n g s p i d e rs y s t e ma r ea l s od i s c u s s e d ，i n c l u d i n gp l e n t yo fa n a l y s i sa n ds o l u t i o n so f s p i d e rs y s t e m sr u n n i n gb o t t l e n e c k s t h e r ea r em a n yn e wm e t h o db r o u g h ti n f o c u sc r a w l i n gs p i d e rs y s t e m t h ef o c u sc r a w l i n gs p i d e rs y s t e mh a sb e e nt e s t e d a n do b t a i n e ds a t i s f i e d r e s u l t s k e yw o r d s ：s e a r c he n g i n e s ，w e bs p i d e r , f o c u sc r a w l i n g ，a u t o m a t i ct e x t c a t e g o r i z a t i o n 西南交通大学 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定， 同意学校保留并向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查阅和借阅。本人授权西南交通大学可以将本论文的全部 或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等 复印手段保存和汇编本学位论文。 本学位论文属于 1 保密口，在年解密后适用本授权书； 2 不保密瓯使用本授权书。 ( 请在以上方框内打“) 学位论文作者签名严组 日期：p p 字年q 目l 弓b 指导老师签名：喙l 芎 日期：乒卅6 岭厂 西南交通大学学位论文创新性声明 本人郑重声明：所呈交的学位论文，是在导师指导下独立进行研 究工作所得的成果。除文中已经注明引用的内容外，本论文不包含任 何其他个人或集体已经发表或撰写过的研究成果。对本文的研究做出 贡献的个人和集体，均已在文中作了明确的说明。本人完全意识到本 声明的法律结果由本人承担。 本学位论文的主要创新点如下： 一、在主题网络蜘蛛系统的网页数据采集模块中，采用了w s a 事件选择模型与非阻塞套接字绑定数据采集线程的新设计，提高了网 页采集工作的效率及适应性。 二、在d n s 缓存模块中提出了“相似规整串集合的概念，用 于细粒度划分网络主机名，使其在存储结构上的空间分布更加离散、 均匀，以便更好地引入散列机制查询主机名；同时采用了“元素索引 表”结构增强相似规整串集合中元素的操作的“粒子 特性。 三、在h t m l 解析器中，创新性地使用了线性存储结构维护传 统意义上的“链式”树这一做法，提出了“文档地图表结构”。使h t m l 解析过程更加快速、高效，并且更加适用于蜘蛛系统。 四、采用基于简单向量距离法、k n n 算法及贝叶斯算法的页面 主题相关性综合评价器，简化分类样本集，增加判定结果可能，并采 用“首次判定 、“二次判定 两次判定过程，使得主题判定结果更加 准确、客观。 五、提出了“侵入式鱼群算法 实现u r l 优选策略的优化。该 算法克服了传统鱼群算法的缺点，并借鉴了p a g e r a n k 思想，通过“侵 入发生周期及“侵入成功指数 两个概念引入了“侵入”行为，控 制u r l 群结构，使得系统的u r l 优选功能具备更强的覆盖度及隧道 穿越能力。 西南交通大学硕士研究生学位论文第1 页 1 1 研究背景 第1 章绪论 随着互联网的不断发展和日益普及，网上的信息量呈爆炸性增长。据统 计，截止2 0 0 4 年4 月，全球i n t e m e t 上w e b 页面数已超过4 0 亿，中国的网 页数估计也超过了3 亿，包含的超链接数量则超过5 6 0 亿。最初用户在网上 获取信息的方式即输入自己关心的或熟悉的站点超链接地址，如 _ h t t p ：w w w s w j t u e d u c n 一等，并通过浏览器浏览服务器返回的页面，寻找自己 关心的信息。由于互联网信息量的急剧增长，这样的方式早已不能满足用户 对信息发现的需求。如何能快速、准确、全面地发掘用户关心的信息数据成 了互联网应用开发的热点【l 】。 搜索引擎技术的诞生，为用户提取互联网上的有效信息提供了较好的途 径。目前商业化的搜索引擎在全球已经非常普及，如g o o l g e ，b a i d u ，s o s o ， i n f o s e e k ，天网等。目前的搜索引擎通常使用一个或多个资源采集器从i n t e m e t 上收集各种有价值的数据( 如页面资源等) ，然后在本地服务器上索引这些数 据，并为用户提供关键字方式的信息查询服务。搜索引擎用于自动采集数据 的采集器又称为网络蜘蛛( s p i d e r ) 、网络爬虫( c r a w l e r ) 或网络机器人( r o b o t ) 等【2 】。这些网络蜘蛛构成了搜索引擎的重要组成部分，搜索引擎公司的网络 蜘蛛开发需要多个部门协同工作才能完成。 尽管早期的网络蜘蛛实现了i n t e m e t 上的信息自动采集，然而采集到的数 据往往涉及的领域太广，信息量仍然太庞大。用户检索信息时，会出现得到 结果不准确或是响应效率太低等状况，结果仍不能令人满意。针对这些问题， 人们提出了一种能在互联网上采集针对于某个或某些特定主题资源的网络蜘 蛛，称为主题网络蜘蛛【3 】。主题网络蜘蛛可以有效地减少资源采集数量、提 高采集资源的主题规整性、提高网络带宽利用率，同时提高了信息检索的效 率，是一种非常有使用价值的网络信息资源自动采集解决方案。 西南交通大学硕士研究生学位论文第2 页 1 2 网络蜘蛛的研究现状 网络蜘蛛的研究开始于上世纪九十年代，被称为世界上第一个蜘蛛的 w a n d e r e r 系统由m a t t h e wg r a y 实现于1 9 9 3 年，几乎与互联网同时出现。由 于蜘蛛的自动化程度高、维护费用低，且更强调技术上的创新和提高，也更 适合于开展研究工作，因而迅速成为研究热尉引。 在1 9 9 4 年，出现了主题蜘蛛的雏形，即最早使用查询来指导蜘蛛爬行的 系统一“鱼群搜索系统”。鱼群搜索系统是一个客户端的实时检索系统，虽然 在实现上较为粗糙，但鱼群系统指出了聚焦爬行系统的一个主要研究方向， 即如何使用启发式策略来为u r l ( u n i f o r mr e s o u r c el o c a t o r ，u r l ) 评分、 预测u r l 的相关性；同时鱼群算法基于自治a g e n t 的想法也颇有吸引力。1 9 9 8 年h e r s o v i c i 等人提出s h a r k 搜索系统，它是对鱼群系统的一个重要改进【5 j 。 1 9 9 8 年g o o g l e 的创始人l a w r e n c ep a g e 和s e r g eb r i n 发表文章讨论了 g o o g l e 所使用的蜘蛛g o o g l ec r a w l e r 的设计，g o o g l ec r a w l e r 采用多台机器 进行分布式爬行，每个蜘蛛包括五个功能模块。在这之前，很少有文章考虑 蜘蛛所面临的海量数据问题。 c h o 等人提出应根据页面的“重要性来访问页面，重要的页面应优先 访问，同时该文考虑了多种重要性度量方法，包括与查询词的相似性、反向 链接数( 即页面中含有指向该页面的超链接的网页的总数) 和p a g e r a n k 值， 并得出结论认为由p a g e r a n k 指导的蜘蛛表现最佳。此后，p a g e r a n k 算法和 h i t s 算法作为两种主要的链接分析算法很快被众多研究者用于指导主题蜘 蛛、预测u r l 的重要性，目前很多用于u r l 评分的w e b 分析算法都可在不 同程度上视为这两种算法的变体1 6 j 。 d i l i g e n t i 等人提出了基于语境图( c o n t e x tg r a p h ) 的聚焦爬行方法，语 境图可用来学习网页距目标( 相关) 页面的距离，但其构造需要依赖于通用 搜索引擎的反向链接功能，因此引起了一些争议。 印度理工学院的学者s c h a k r a b a r t i 中明确提出了聚焦爬行的概念，他提 出的系统不再使用关键词或加权矢量来标识主题，而是从一个规范的主题分 西南交通大学硕士研究生学位论文第3 页 类系统和用户指定的种子集合( u pu r l 集合，如浏览器中的书签等) 出发建设 w e b 主题资源；在爬行过程中，使用分类器( c l a s s i f i e r ) 和精炼器( d i s t i l l e r ) 来指 导爬行方向，其中分类器用于评价采集文本是否与主题相关：精炼器用于识 别能够在较少的链接内就连接到大量相关页面的超文本节剧7 1 。 a g g a r w a l 等人提出了智能爬行框架，在该框架下，用户可指定一个计算 文档相关性的函数，系统负责保证根据该相关性函数自动聚焦，抓取相关页 面。 m e n c z e r 等人评价了三种w e b 分析算法：b e s tf i r s t ( 通过计算链接所在 页面与主题的相似度来得到采集优先级) 、p a g e r a n k 和i n f o s p i d e r s ( 通过链 接周围的文字，利用神经网络和遗传算法来得到采集优先级) 。经过试验比较， m e n c z e r 等人发现b e s t f i r s t 方法最好，i n f o s p i d e r s 方法次之，p a g e r a n k 算法 最差。他们给出的解释是p a g e r a n k 算法过于通用，未考虑到页面内容与主题 的相关性，不适合作为聚焦爬行的分析算法。此后，基于链接结构的分析算 法与基于内容的分析算法的结合逐渐成为主流【8 】。 本节只对聚焦爬行研究中的一些重要文献作一简单介绍，在后文中将陆 续详细介绍这些模型的关键思想和技术细节。 1 3 课题研究意义 目前各大数字图书馆、主题网站及商业搜索引擎在利用w e b 主题资源的 时候，迫切希望有一个工具或技术来代替或辅助工作人员进行主题资源的搜 集、整理等工作 9 】。主题搜索系统可以自动地搜索w e b 上的主题资源，从而 摆脱对专家的依赖，减少人工干预，提高主题网站资源建设的速度、效率和 质量，为科研人员和相关用户提供高质量的信息资源和信息服务。 作为实现自动主题搜索的最佳方法，主题蜘蛛技术不但可以提高某个主 题的资源覆盖度，而且使得主题蜘蛛所下载的网页尽可能地与所需的主题相 关，从而有效地提高主题蜘蛛的爬行性能和网络带宽的利用效率。 现今网络蜘蛛的开发还没有形成行业标准，网络蜘蛛的结构模型多种多 西南交通大学硕士研究生学位论文第4 页 样。本文将现有的算法和技术相结合并加以改进，实现了一个基于文档自动 分类理论以及超链接优选策略的搜索引擎主题网络蜘蛛系统原型，为主题网 络蜘蛛系统的开发探索新的方向。 1 4 论文内容安排 本文由分析i n t e m e t 上的资源分布特性入手，利用现有的研究理论成果， 经过改进现有的主题蜘蛛爬行算法以及策略，构建了一个基于文档自动分类 及超链接优选策略的针对主题页面爬行的主题网络蜘蛛系统，并对其技术性 能指标进行测试评估。 第一章为绪论，介绍主题蜘蛛的研究背景、国内外研究现状以及研究意 义。 第二章简要介绍网络蜘蛛以及主题网络蜘蛛系统，着重讨论与主题蜘蛛 爬行密切相关的策略、算法以及相关的改进机制等，主要有页面质量评价策 略、u r l 主题相关性评价算法以及页面主题相关性得分算法及其改进。 第三章与第四章分别论述f o c u sc r a w l i n gs p i d e r 系统的总体设计，对现 有的网络蜘蛛系统的改进以及各个功能模块详细设计、实现细节等。 第五章对f o c u sc r a w l i n gs p i d e r 系统进行测试评估，给出相关实验结果。 第六章是对本文工作的总结与展望。 西南交通大学硕士研究生学位论文第5 页 第2 章网络蜘蛛及相关算法研究 网络蜘蛛系统的工作可行性，主要基于这样的事实：整个i n t e m e t 中有大 量的网页、链向这些页面的u r l 以及这些页面包含的链向其他页面的u r l ， 分别构成了一幅巨大的w 曲有向图( d i r e c tg r a p h ) 的节点和边【1 0 1 。通过这 些边( u r l ) ，从某一或某些确定的节点( 页面) 出发，理论上可以遍历整个 i n t e m e t 全部的节点( 页面) ，如图2 1 所示： l 图2 - 1i n t e r n e c 页面的有向图特性 需要指出的是，w e b 有向图结构并不理想化，并非全部节点都相互可达 ( 如有的页面只有出度没有入度) ，合理选择u r l 种子集合( 访问初始节点 集) 是网络蜘蛛系统的重要工作之一。 基于上述模型，绝大部分网络蜘蛛的爬行寻路算法都依据有向图遍历算 法b f s ( b r e a d t hf i r s ts e a r c h ) 或d f s ( d e p t hf i r s ts e a r c h ) ，并出现了在此基 础上的启发式爬行策略以及结合自动分类思想的爬行策略等【1 1 】。 西南交通大学硕士研究生学位论文第6 页 2 1 通用蜘蛛系统与主题蜘蛛系统 2 1 1 通用蜘蛛系统 通用蜘蛛结构如图2 - 2 所示，主要包括以下几个重要功能模块：u r l 等 待队列、u r l 判重模块、页面采集模块、u r l 提取模块以及页面存储及索引 模块。 图2 2 通用网络蜘蛛的结构示意 图2 2 显示了页面采集、页面处理及页面存储等部分同步工作的网络蜘 蛛系统简化的结构。网络蜘蛛系统通过并发地递交多个h t t p 客户端请求同 时与多个站点服务器交互并下载资源，工作步骤大致如下： 1 ) 将u r l 种子放入u r l 等待队列。 2 ) 从u r l 队列中取出u r l ，判别u r l 是否已经被爬行过。若队列空， 则结束爬行。 3 ) 若u r l 还未被爬行则爬行其所指页面，若失败重复步骤2 ) 。 西南交通大学硕士研究生学位论文第7 页 4 ) 提取该页面中的u r l ，放入u r l 队列，并将页面存储到资源库。 5 ) 重复步骤2 ) 到4 ) 直到满足爬行结束条件( 工作限时、u r l 数量采 集到达上限、致命错误等情况) 。 2 1 2 通用蜘蛛系统的不足 我们把获得的与主题相关的页面称为“回报，1 1 2 】。通用网络蜘蛛系统是 在对i n t e m e t 上的页面分布特性不做任何假设以及计算的情况下进行的盲目 爬行。对于用户的特定主题相关的检索需求来说，尽管通用蜘蛛系统召回率 较高，但通用蜘蛛系统采集的资源回报率是非常低的，同时浪费了大量带宽 与系统资源( 13 1 。 举例来说，假设在整个w e b 上有t 个网页文件，其中关于某主题的文件 个数为s 。通过普通蜘蛛在一个爬行周期( 7 天) 能够爬行所有w e b 资源的 2 0 ，而其中关于某个主题的资源为5 ，则在一个爬行周期内，只能采集到 1 ( 2 0 5 ) 的主题相关资源，而还有大量的资源与主题无关。 2 1 3 主题蜘蛛的原理概述 主题网络蜘蛛系统不同于通用网络蜘蛛系统，通过引入对u r l 的主题相 关性剪枝策略以及页面主题相关性判定策略，能使蜘蛛有目的地在互联网上 爬行并下载资源，主题蜘蛛的爬行又称为“主题爬行”或“聚焦爬行( f o c u s c r a w l i n g ) 1 1 4 ，图2 - 3 为主题网络蜘蛛爬行的剪枝示意： 西南交通大学硕士研究生学位论文第8 页 图2 3 主题无关页面的“剪枝”示意 图中方框表示页面，箭头线表示u r l 。深色方框为主题相关的页面，即 具有回报价值的页面。主题蜘蛛系统由初始页面只出发，由于引入了主题爬 行指导策略，在爬行过程中与主题页面无关的u r l ( 细箭头表示) 会被从爬 行的可选路径集合中“剪”掉( 细箭头所示分支路径) ，或者是滞后爬行，实 现只爬行或优先爬行主题相关性强的u 也( 粗箭头表示) 的爬行线路“剪枝”。 采用这些策略能明显地增加资源回报率，节省有限的网络带宽。对于特定领 域的信息查询，可以极大地提高信息检索服务质量与效率。 2 1 4 主题蜘蛛的结构模型 典型的主题蜘蛛系统结构如图2 4 所示： 西南交通大学硕士研究生学位论文第9 页 图2 - 4 主题网络蜘蛛结构示意 主题网络蜘蛛系统增加了两个重要功能，分别是u r l 价值评价功能和页 面主题相关性判定功能。u r l 评价器负责评估u r l 是否主题相关，以确定 何时或是否爬行该u r l ( 剪枝) ；页面分析器则负责考察经过某u r l 下载到 的页面内容是否主题相关。这两个模块直接影响到主题蜘蛛聚焦爬行的回报 率、覆盖度及准确性 1 5 】，图2 - 5 和图2 - 6 分别为主题网络蜘蛛系统的简要爬 行工作流程图及单个聚焦爬行工作流的爬行流程图： 西南交通大学硕士研究生学位论文第1 0 页 图2 - 5 主题蜘蛛系统简要工作流程图示意 西南交通大学硕士研究生学位论文第11 页 空 图2 - 6 单个聚焦爬行线程工作流程图示意 可见，通过u r l 评价剪枝模块及主题判定模块的协同工作，主题蜘蛛系 统能够预先估计出u r l 回报的价值度，蜘蛛系统能够指导自己对分布在庞大 的互联网信息库上的某一特定主题的资源做效率更高、更全面更准确的爬行。 西南交通大学硕士研究生学位论文第12 页 2 2 面向主题的信息提取的划分 根据提取信息主题的范围和规模，面向主题的页面信息提取可以划分为 泛指主题信息提取及具体主题信息提取。泛指主题信息提取又称为领域信息 提取，主要是指对于主题涵盖面较广、意义较为模糊的一类信息的提取。具 体主题信息提取则与之相对，主要指针对主题含义较窄、主题含义明确的一 类信息的提取。 泛指主题信息提取的特点是提取信息较多，能够保证较高的召回率，然 而主题针对性较差；具体主题信息提取则相反，提取信息量较小，u r l 剪枝 时限定更加严格，提取的信息有更强的针对性【l 6 1 。 2 3 网络主题页面分布特性 主题网络蜘蛛系统的工作对w e b 页面的分布特性具有较强的依赖性1 7 1 。 尽管整个w e b 上充斥着半结构化和非结构化的各类信息，显得杂乱无章，但 研究人员还是从中找出了页面分布规律的重要分布特性，分别是中心页面特 性、主题特性以及隧道特性。 2 3 1 中心页面特性 在整个w e b 中大量存在着这样一类页面，它们不但含有许多指向其他页 面的链接，而且这些链接还趋向于同一主题 1 8 】。也就是说，这类页面是指向 相关主题页面的中心，我们称之为中心页面或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 h o r i t y 算法【l 引。 西南交通大学硕士研究生学位论文第13 页 2 3 2 主题关联及主题聚集特性 科研人员对w 曲结构进一步深入的观察和研究，提出了主题关联特性， 即每个页面所包含的链接都趋向于链接到与它相同主题的页面：对于链接到 某一主题页面的页面，它所包含的其它链接也趋向于链接到该主题【2 0 1 。这个 结论实际上是从网页设计者的角度考虑的，一个网页的设计者趋向于将本页 面指向于与本页面主题相关的其它页面；同时也趋向于将本页面链接在与本 页面主题相关的页面之后。 研究人员还发现，每一个q 乍f - i 户的普通站点都趋向于说明一个或几个主 题，而且那些相同的主题页面之间会有紧密的内部链接，但是不同的主题之 间却很少有相互间的链接。产生这种现象主要原因应该是网站的设计者在设 计网站时都有预定的设计目标和定位，而这种目标往往就集中在一个或几个 主题上。同时，对于网页浏览者来说，他们在上网时一般也趋向于浏览同一 主题的页面。为适应上网者的需求，网站设计者也需要将相关内容相互链接。 这样在w e b 中就出现了一个一个主题团【2 1 1 。 这种特性为主题蜘蛛的剪枝操作的可行性提供了充分的理论依据。 2 3 3 “隧道 特性 尽管在w e b 中存在很多主题页面所聚集而成的主题页面团，但在这些页 面团之间，有时往往需要经过较多的无关链接才能够到达。这些无关的链接 就像长长的隧道一样连接着两个主题页面团，因此，这种现象被称为“隧道 现象 【2 2 】。在主题蜘蛛的运行过程中，“隧道现象 极大地影响页面爬行的 质量和蜘蛛的最终的资源发现率。 以上提到的互联网上主题资源分布的四个特征，虽然各有侧重，但是它 们仍然是共通的。中心页面特性说明了主题资源容易成团出现，并会集中与 某一个或多个固定的网页发生链接关系。主题关联特性进一步论证了主题资 西南交通大学硕士研究生学位论文第1 4 页 源成团出现的可能性，并对主题资源内部的网络关系进行了分析和扩展。而 主题聚集特性说明了主题资源团所可能出现的位置，隧道特性说明了主题资 源的团与团之间的连接并非像主题资源团内部那么稠密( 2 3 1 。 2 4w e b 结构链接挖掘策略 如前所述，整个w e b 是由通过链接相互连接起来的网页以及其他资源所 组成，我们可以把它抽象成一个w e b 图。基于这样的模型，人们提出了两种 重要的超链接评价算法，即p a g e r a n k 以及h i t s 。 p a g e r a n k 的发明者s b r i n 和l p a g e 把引文分析思想借鉴到网络文档的 重要性计算中来【2 4 1 ，利用网络自身的超链接结构给所有的网页确定一个重要 性的等级数，当从网页a 链接到网页b 时，就认为“网页a 投了网页b 一 票，增加了网页b 的重要性。最后根据网页的得票数评定其重要性，以此 来帮助实现排序算法的优化，这个重要性的量化指标就是p a g e r a n k 值。 p a g e r a n k 近年来被应用于网络蜘蛛对链接重要性的评价。在该方法中， 页面的权威值通常用p a g e r a n k 值来表示。其定义如下：假设u 为一个页面， f 。为被u 指向的网页的集合，b 。，为指向u 的网页的集合；v 也为该集合中的 页面。令l 。= | f 。i ，即页面u 的出度( 页面u 指向外的链接数) ；c 为常量。 则p a g e r a n k 的简单计算公式为式( 2 1 ) ： r ( “) = c 掣( 2 - 1 ) v 吼1 v 算法迭代规则如图2 7 所示： 西南交通大学硕士研究生学位论文第15 页 图2 7p a g e r a n k 算法示意 方框表示页面，内含的数字为页面的p a g e r a n k 得分，箭头线为超链接。可以 看到，页面的p a g e r a n k 值对u r l 有决定性影响，同时页面的反向链接( b a c k l i n k ) 又决定了页面的p a g e r a n k 值。的以上公式仅仅适用于人们设想理想的 情况。通过对互联网中页面分布特性的研究及出于排除“干扰”因素的考虑， 两位发明者经过深入的研究得出了更为有效的p a g e r a n k 计算公式如式( 2 2 ) 所示： 尺似) ：1 一c + c y 型( 2 - 2 ) 一，氧， 。 其中c 经验性的最佳值为0 8 5 。p a g e r a n k 算法是最早并且最成功地将链接分 析技术应用到商业搜索引擎中的算法，g o o g l e 搜索领域的巨大成功，证明了 p a g e r a n k 算法的有效性。 尽管如此，p a g e r a n k 算法也还存在局限性，其中最严重的在于p a g e r a n k 算法对于每个页面中的所有链接的贡献都认为是平均的，这与事实严重不符 合，如一个页面中的广告链接与链向一个“强壮”页面的链接权重不应相同。 基于上述考虑，k l e i n b e r g 于19 9 9 年提出了h i t s ( h y p e r l i n k - i n d u c e dt o p i c s 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 值表示一个页面被其他页面引用的数量， 即该页面的入度。网页的入度越大，则该网页的a u t h o r i t y 值越大；h u b 值表 示一个页面指向其他页面的数量，即该页面的出度。网页的出度越大，其h u b 值越大。由于h u b 值高的页面通常都提供了指向权威页面的链接，因而起到 了隐含说明某一主题页面权威性的作用。通常，好的中心页面是指向许多好 的权威页面的页面；好的权威页面是指由许多好的中心页面所指向的页面。 这种中心页面与权威页面之间的相互作用，可用于权威页面的挖掘和高质量 w e b 结构和资源的自动发现，这就是h i t s 算法的基本思想，如图2 8 所示： 西南交通大学硕士研究生学位论文第16 页 图2 8 权威页面与中心页面 对每个页面u ，设a u t h o r i t y 值为x 引，h u b 值为y 引，使用i o 操作分别计算 其工( “以及y ( ，i 操作计算公式： x 似 - - - y “ ( 2 3 ) y ：( “，y ) 层 同理，o 操作计算公式为： y - - x 扣 ( 2 4 ) v ：( “，v ) e e h i t s 算法处理对象( w e b 网页) 个数相对较少，一般在几万以内，计算速 度相对p a g e r a n k 要快得多。但由于网页本身有多个不同的主题，这使得h i t s 算法的结果容易出现主题漂移【2 5 1 。为使结果单一化，很多学者利用许多其他 的文字信息来克服，如u r l 对应的锚文字、u r l 周围的上下文信息、u r l 本身的文字信息等。另外，也有人提出了基于引文分析的超链接分析法【2 6 】。 由于理想的p a g e r a n k 计算需要页面全集进行迭代，而h i t s 需要在线查 询页面的反向链接，时间效率低，故在本文论述的系统中，借鉴了p a g e r a n k 算法及h i t s 的思想评价u r l 质量：即并不做大规模的离线迭代计算，但综 合考虑互联网上页面强壮性( p a g e r a n k ) 以及页面的链接分布特性( h i t s ) 等因素，后面的章节会详细讨论。 2 5 基于文字内容的o r l 主题相关性评价启发策略 上一节简单介绍了基于w e b 结构挖掘的蜘蛛系统寻路指导策略，对于一 西南交通大学硕士研究生学位论文第17 页 个主题网络蜘蛛系统来说，仅仅考虑网页及链接的链接结构、分布特性是远 远不够的。我们将网页中链接的锚为本以及环绕链接一定深度的文字信息称 为上下文( c o n t e x t ) 【2 7 1 ，通过分析这些文字信息能够更好的指导主题蜘蛛系 统的聚焦爬行。如 西南交：适六学主万 与 这两个标签中的u r l 指向同一页 面，但锚文本文字信息对评估链接所指页面的主题相关度起到了巨大作用。 目前基于文字内容的启发策略主要有下面几种 2 8 、2 9 、3 0 】： 1 b e s tf i r s ts e a r c h 算法的主要思想是通过分析链接上下文文字信息，对于某给定的主题， 为u r l 计算主题相关性权重。依据该权重建立u r l 等待优先级队列，每次 爬行都优选权重得分最高的u r l ；若队列满则替换掉队列中优先级最低的 u r l 。 b e s tf i r s ts e a r c h 是一种朴素优选策略，这种算法的优点是计算量比较小， 对宽泛主题比较有用。但在关键字很多的情况下，由于锚文本和链接信息不 能很好地反映页面主题，导致效果不佳。也容易使算法过早陷入w e b 搜索空 间中局部最优子空间的陷阱，导致整体回报率不高。 2 f i s hs e a r c h 算法 此算法是1 9 9 3 年提出来的，把一个u r l 比喻成一条鱼。鱼能活多久， 它们能繁殖多少后代，取决于它们找到食物的多少。当一个文件被爬行下来 之后，很多的新的u r l 就会被解析出来( 鱼繁殖很多的后代) 。其中，有用 的u r l 的数量取决于该文件是否与主题相关( 包含多少食物) ，以及它本身 包含链接后代的数量。每次，当鱼找到大量食物( 主题相关页面) 之后，它 就能变得强壮，并繁殖更多的后代。反之，鱼就变得虚弱，后代也少。当鱼 找不到食物( 无相关页面) 或者水被污染( 带宽不够) 的时候，鱼就死掉。 该算法的关键是根据种子站点和查询关键字，动态地维护一个u r l 爬行优先 队列。 3 s h a r ks e a r c h 算法 顾名思义，该算法是针对f i s hs e a r c h 算法的缺陷而进行改进的算法。鲨 西南交通大学硕士研究生学位论文第18 页 鱼( s h a r k ) 是比一般鱼( f i s h ) 更凶猛的鱼，说明这种算法比f i s hs e a r c h 更 有效。其对f i s hs e a r c h 的改进有如下几点： ( 1 ) f i s hs e a r c h 中，只有“是 、“否主题相关的二值判断，而在s h a r k s e a r c h 中引入了相似度度量方法，取值在o 到1 之间； ( 2 ) 在计算u r l 的权值得分上，充分利用了锚文本及其上下文( 围绕 锚文本周围一定距离的文本) 。 在本文论述的主题网络蜘蛛系统中，借鉴了f i s hs e a r c h 与s h a r ks e a r c h 算法思想，同时引入“入侵”概念，阻止了某个方向上的u r l “宗族 霸 占整个“水域”，避免算法过早陷入网页的局部最优子空间中，对“隧道特 性有一定穿越能力，这部分将在第4 章详细讨论。 2 6 页面主题相关性判定策略 在进行w e b 主题信息提取的实施过程中，所提取的u r l 已经通过了主 题相关性判别，尽管如此，所提取的页面内容还是可能与设定的主题相差甚 远。这种现象将影响主题页面信息的提取准确率。因此，在页面提取之后， 需要对页面进行主题相关性判别，以过滤掉主题无关页面。在本文实现的主 题蜘蛛系统对页面的主题相关性判定采用了基于向量空问模型的文档自动分 类策略。 2 6 1 向量空间模型( v s m ) 向量空间模型( v e c t o rs p a c em o d e l ，s v m ) 是关于文档表示的一个统计 模型”】。向量空间模型基于这样一个关键假设，即文章中词条出现的顺序是 无关紧要的，他们对于文档的类别所起的作用是相互独立的，因此可以把文 档看作一系列无序词条的集合。该模型以特征项作为文档表示的坐标，以向 量的形式把文档表示为多维空间中的一个点。例如，k 维二值向量空间模型 中我们这样表示一篇文档： 西南交通大学硕士研究生学位论文第19 页 d ，= ( d i l d 加，d 醍) d 扩= o 或l( 2 - 5 ) 其中d 扩为特征项乃在文档d 。中的权值。图2 - - 9 为文档的向量空间模型示意： d l 图2 9 文档向量空间模型示意 图中三根粗黑箭头构成了一个三维坐标空间，细空心箭头分别为文档d 、d ， 及d ：的三维向量表示。由此可以看出，如果特征向选取得当，特征统计策略 合理，我 f f s p 二够用量化的方法将不同主题的文档分类。 通常二值向量空间模型表示文档不能准确对文档进行主题类别划分，原 因是0 ，1 两个值无法体现特征向在文档中的重要程度【3 2 1 。现代文档分类科 学中，采用t f i d f 词频统计法为文档统计特征权值，该方法将在2 6 2 小节 中详述。 2 6 2 页面信息抽取与逆文档频率指数 在对文档进行主题含义分类之前，需要先对文档内容进行特征信息抽取， 用以对文档内容所包含的信息建立泛化模型。目前效果最好、使用最多的方 法是逆文档频率指数统计法。 逆文档频率指数方法( t f i d f ) 基于一个基本假设：在真实语料中，出 现频繁的词条( 特征) 带有较少的信息，如“我 、“是”等；而出现较少的词 条具有较多的内容信息。我们设疋为特征词条，该词条在文档d 。中的权重使 用t f i d f 值表示，t f i d f 值的计算使用式( 2 6 ) 【3 3 j ： 西南交通大学硕士研究生学位论文第2 0 页 = 砭1 0 9 ( + c ) ( 2 - 6 ) 其中珥为特征词条瓦在文档4 中出现的频率，称为相频( t e r mf r e q u e n c y ， 吓) ；o f , 表示语料统计集合中包含词条瓦的文档的数量，其倒数为仞峨，称 为逆文档频率( i n v e r t e dd o c u m e n tf r e q u e n c y ，i d f ) ；n 表示统计语料集合中 文档的总数；c 为修正因子，通常取o 1 。由此，任意文档都可以用如下泛 化k 维特征向量表示： d f = ( 仞f l ，仞f 2 ) ( 2 7 ) 本文中论述的f o c u sc r a w l i n gs p i d e r 系统在做文档主题分类时，引入了 t f i d f 的统计方法，在第四章中详细讨论。 2 6 3 训练与分类方法简介 在w e b 出现之前，人们已研究过许多普通文档分类的方法，形成了各种 文档自动分类( a u t o m a t i ct e x tc a t e g o r i z a t i o n ，a t c ) 方法，包括词匹配法、 统计学习方法及知识工程的方法。目前使用最频繁的自动分类方法大都是基 于统计学习和向量空间模型的方法。 ( 1 ) 简单向量距离法【3 4 】 对以一个训练样本集，我们将每类文档中所有文档的特征向量做算术平 运算，可以得到用于文档类别考评的特征向量，称为该类别的中心向量。简 单向量距离法即将待分类文档抽象成特征向量，与各个类别的中心向量比较， 计算相互间的距离( 相似度) ，将待分类文档归入与其距离最近的那个中心向 量所代表的类别中去。通常使用向量夹角作为距离参考标注，由公式( 2 8 ) 计算： 西南交通大学硕士研究生学位论文第2 1 页 s i m ( d f ，d _ ，) - - - c o s l 9 =( 2 8 ) 其中d ；为待分类文档的特征向量，d 为第j 类文档的中心向量。图2 1 0 为 简单向量距离法的示意图： j 类中 图2 1 0 简单向量距离法示意 图中虚线箭头分别为j 类与k 类的中心向量，由于d ，与j 类中心向量具体小 于其与k 类的中心向量的距离，故将