（通信与信息系统专业论文）主题web信息采集系统的研究与设计.pdf

戳南科技大学硕士职究生学位论文第l 页 摘要 海量w e b 信息采集是播存结构源端的个重要课题。随着w e b 信息的 爆炸性增长，传统的w e b 信息采集无针对性，页面失效率高，不能满足人们 曩益增长的个性纯需求的缺点越柬越骧显。针对这种情况，本文围绕主题 w e b 信息采集技术展开了具体的理论研究和实验工作。 论文首先分析了主题w e b 信息采集的原理霸主题贾面在w e b 上的分布 规律，研究了主题相关性判别算法，网页去重以及u c l 标引技术，其中重点 研究了u r l 与主题的相关性判别算法。 其次，设计并实现了一个主题w e b 信息采集系统f o c u s e d s p i d e r 。该系 统考虑子页两的主题相关性反馈影响，采用w e b 结构和网页文本内容相结合 的一种u r l 与主题的相关性判别算法，准确地预测u r l 的主题相关度；网 时根据去重对象的不同，采用一种网页三级去重机制，有效地消除重复网页； 并对采集到的网页进行u c l 标弓| ，以便信息的组织。 荐次，本文研究了r s s 技术，设计并实现了基于r s s 的主题w e b 信息 采集，能够有效地采集r s s 种子中薪增加的主题页面。 最后，对f o c u s e d s p i d e r 进行了实验测试，完成了对实验结果的分析。实 验结果表明翔c u s e d s p i d e f 具有较高的采集效率和准确率。 关键词：主题w e b 信息采集主题相关性网页去重 u c l 标引 r s s 西南科技大学硕士研究生学位论文第1 | 页 a b s t ra c t m a s s i v ew e bi n f o r m a t i o nc r a w l i n gi sa ni m p o r t a n ts u b j e c ti nt h es o u r c e - e n d o fb r o a d c a s t s t o r a g es t r u c t u r e w i t ht h ee x p l o s i v eg r o w t ho fw e bi n f b r m a t i o n ， t h ed j s a d v a n t a g e s0 ft r a d i t i o n a lw e bc r a w l i n g ，s u c ha sn o n - s p e c i f i ci n f o r m a t i o n c o l l e c t i o n ，h i g hr a l e so fp a g e sm i s s i n g ，a n dw i l h o u tm e e t i n gp e o p l e si n c f e a s i n g i n d i v i d u a t i o nr e q u i r e m e n t ，a r eb e c o m i n gm o r ea n dm o r ee x p l i c i t a j m i n ga tt h e s i t u a t i o n ， t h et h e s i sc a r r i e so u tc o r r e s p o n d i n gt h e o r e t i c a la n de x p e r i m e n t a l r e s e a r c ha r o u n df b c u s e dw e bc r a w l i n gt e c h n o l o g y f i r s t l y ， t h e p r i n c i p l eo ff o c u s e dw e bc r a w l i n g a n dt h er u l e so ft h e d i s t r i b u t i o no ft o p i co nt h ew e ba r ea n a l y z e di nt h et h e s i s ，t h e nt o p i cr e l a t i v i t y j u d g i n ga l g o r i t h m s ，d u p l i c a t e dw e bp a g e sd e l e t i o na n du c l i n d e x i n gt e c h n o l o g y a r es t u d i e d a m o n gt h e m ，r e l a t i v i t yj u d g i n ga l g o r i t h m sb e t w e e nu r l a n dt o p i c a r em a i n l ys t u d i e d s e c o n d l v ， af b c u s e dw e bc f a w l e rc a l l e df o c u s e d s p i d e ri sd e s i g n e da n d r e a l i z e d a f t e rc o n s i d e r i n gf e e d b a c ki n f l u e n c eo fs u b p a g e st o p i cr e l a t i v i t y ，a k i n do fr e l a t i v i t yj u d g i n ga l g o r i t h mb e t w e e nu r la n dt o p i cb a s e do nw e b s t r u c t u r ea n dp a g ec o n t e n ti sa d o p t e dt 0p r e d i c tt o p i cr e l a t i v i t y 0 fu r l a c c u r a t e l y a n da c c o r d i n gt od j f f e r e n to b j e c to fd u p l i c a t e dw e bp a g e sd e l e t i o n ，a t h r e e 1 e v e lm e c h a n i s mo fd u p l i c a t e dw e bp a g e sd e l e t i o ni sa d o p t e dt od e l e t e d u p l i c a t e dw e bp a g e se f f e c t i v e l y t h e nc r a w l e dw e bp a g e sa r ei n d e x e db yu c l f o ri n f b r m a t i o n0 r g a n i z a t i o n t h i r d l v ，r s st e c h n o l o g yi sa l s os t u d i e d ，a n df o c u s e dw e bc r a w l i n gb a s e d o nr s si sd e s i g n e da n dr e a l i z e dt oc r a w ln e wa d d e dt o p i cp a g e si nr s sf e e d s e f f e c t i v e l y f i n a l l y ，t h ef o c u s e d s p i d e ri st e s t e da 玎de x p e r i m e n tf e s u l t sa r ea n a l y z e d t h er e s u l t ss h o wt h a tf o c u s e d s p i d e rh a sh i g h e rc r a w l i n ge f f i c i e n c ya n da c c u r a c y f o rw e bp a g e sr e l e v a n tt oap r e d e f i n e ds e to ft o p i c s k e y w o r d s ：f o c u s e dw e bc r a w l i n g ；t o p i cr e l a t i v i t y ； d u p l i c a t e dw e bp a g e sd e l e t i o n ；u c li n d e x i n g ；r s s 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工俸及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢酶地方羚，论文中不包含其毽入 已经发表或撰写过的研究成果，也不包含为获褥透南科技大学或其它教育机构的 学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已 在论文中作了明确的说鹱并表示了谢意。 签名： 阀栖匿期：潮谚吖 关于论文使用和授权的说明 奉人完全了解西南辩技大学有关保留、使用学位论文韵规定，即；学校有权 保窝学位论文的复印件，允许该论文被查阅和借阕；学校可以公布该论文的全部 或部分内容，可以采用影印、缩印或箕拖复利手段保存论文。 ( 保密的学位论文在解密后应遵守此规定) 一，司摇 翮躲及量吼期冽。纠7 西南科技大学硕士研究生学位论文第1 页 1绪论 1 1课题来源 论文的研究工作来源于国家8 6 3 计划项目“具有语义标引的互补结构网 络( 2 0 0 5 a a l 2 1 5 2 0 ) 。 “具有语义标引的互补结构网络”项目旨在实验室构造具有语义标引的 互补结构实验网，为构造规模化网络积累必要的理论依据与实验仿真数据。 本课题正是以上述项目为背景开展理论和实验研究的，主要解决播存结构源 端的海量w e b 信息采集问题，重点研究了主题w e b 信息采集。 1 2 课题的研究背景 1 2 1播存结构源端的需求 互联网的发展，使网络数据急剧增长，用户很难快速、准确地在海量的 信息中搜索到符合自己要求的信息。同时基于互联原理的万维网使人能随时 随地的共享存储在网站服务器罩的信息资源，但是随着用户访问的大量增长 产生了“你用妨碍我用 的共享冲突，没能体现“信息共享本无冲突”和“规 模无上限”的优势。 为此，李幼平院士提出了将广播与存储技术相结合的“播存结构”创新 理念：先将互联网资源经过前端整合，再将大规模数据通过单向广播网推送 到客户端，利用其大容量的存储器将用户感兴趣的共享信息存储在本地，这 样共享冲突矛盾将不复存在1 。 播存结构由信源、信道与信宿三大部分组成，它们分别称为“整合一体的 资源平台”、“覆盖全国的广播信道”和“透明计算的结构终端”，结构如图卜1 所示。 中国工程物理研究院马卫东等，根据中国互联网中心c n n l c 发表的实 测数据，初步描绘了我国万维网网站连接数的数学模型，并得出结论：当 9 9 5 以上的网站连接数均低于1 0 0 次时，却有万分之四的网站大于1 0 0 0 次， 十万分之三的网站超出1 0 0 0 0 0 次。因此，尽管中国向网民提供内容的网站有 六十七万个，但是只要整合2 至3 千个网站作为主流资源，就可以在很大的 程度上满足老百姓的日常需求。因此，我们设计的整合体的资源平台结 构如图卜2 所示。 西南科技大学硕士研究生学位论文第2 页 透瞬计算静网格终端 图 一播存结构”1 一母爵昏圃 圈1 2整合一体的资源平愈 互联网中的主流网站分散在全国各地，整合一体的资源平台可以通过对 主流网站上的w e b 信息自动采集，并对w e b 数据进行聚类和分类，按照x m l 的形式存储在广播中心的网站数据库中，最后通过广播信道传输到全国各地。 因此，w 曲信息采集是整合一体的资源平台中的重要组成部分，为播存 结构用户不断地提供海量信息。w e b 信息采集，主要是通过w e b 页面之间的 链接关系，从w 曲主自动地获取页面信息，并且随着链接不断商整个w e b 扩展的过程。实现这一过程主要通过w e b 信息采集器( w e bc r a w l e r ) 来完 成的，w e b 信息采集器也被成为网络蜘蛛、网络爬虫等。 1 2 2传统辫e b 信息采集的不足 作为搜索引擎的基础和组成部分，w e b 信息采集正发挥着举足轻重的作 用，并且随着应用的深化和技术的发展，它越来越多的应用于站点分析、页 整合一体静资源平台 西南科技大学硕士研究生学位论文第3 页 面有效性分析、w e b 图形化、内容安全检测、用户兴趣挖掘以及个性化信息 获取等多种服务和研究中。 随着因特网技术的迅速发展和广泛应用，传统w e b 信息采集正面临巨大 的挑战k 川，。挑战一是通用搜索引擎采用的是传统w e b 信息采集，它的目标 是尽可能多地采集页面信息，甚至是整个w e b 上的资源。随着w w w 信息 的爆炸性增长，信息采集的速度越来越不能满足实际应用的需要。实验表明， 即使大型的搜索引擎，它对w e b 的覆盖率也只有3 0 4 0 。解决这一问 题的直接办法是升级信息采集器的硬件，采用处理能力更强的计算机系统， 然而这种方法的扩展性有限，性价比也不高。一个更好的解决方法是采用分 布式方法来提高并行能力，但是并行不但增加了系统的开销和设计的复杂性， 并且并行换来的效益也随着并行采集器数目的增加而显著地减小。目前，一 般的大型搜索引擎都采用了并行机制，但是并行带来的改善效果仍然远不能 满足人们的需要，人们需要从其它角度改善目前的困境。 挑战二是w e b 信息资源动态变化，搜索引擎无法保证对信息的及时更 新。近年来的研究表明，w e b 上平均5 0 天就有约5 0 的页面发生变化，而 目前通用搜索引擎更新的时间至少需要数星期之久；挑战三是通用搜索引擎 提供的信息检索服务，不能满足人们日益增长的对个性化服务的需要。 面对这些挑战，主题w e b 信息采集技术应运而生。 1 3 课题的研究现状 主题w e b 信息采集器也称为主题网络蜘蛛，是通过预先设定的种子集( 种 子链接或者页面) ，利用各种w e b 协议访问并下载页面，在用各种分析算法 分析页面与主题的相关性之后提取出待访问的链接，预测链接指向主题相关 页面的可能性，再以各种不同的搜索策略循环迭代地访问w e b 。 目前，有关主题w e b 信息采集的研究是一个热点，国外学者们提出了许 多评价标准和模型。 f i s h 旧系统是最早的主题网络蜘蛛模型。它是一个基于客户端的实时信息 检索系统，它假设相关页面在逻辑上彼此接近，采用深度优先算法搜索相关 页面，并用一组关键词和短语判断页面的相关性。 h e r s o v i c i l 7 】对f i s h 系统进行了改进，它从一个特定点丌始并跟踪相关文 本的链接，使用向量空间模型来计算页面的相似度，根据链接周围文本价值 和链接的“继承 价值决定优先级及爬行的深度。 西南科技大学硕士研究生学位论文第4 页 c h o ，提出了通过先爬行更重要的网页使爬行更有效。他讨论了几种评价 链接重要性的方式，提出了基于“驱动查询 ( d r i v i n g q u e r y ) 相似度、页面入 度( b a c k l i n k s ) 、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 提出的h l t s 算法 作为两种主要的链接分析算法很快被众多研究者用于指导主题爬虫预测 u r l 的重要性，目前很多用于u r l 评价的w e b 分析算法都可以在不同程度 上视为这两种算法的变体。 印度理工学院的学者c h a k r a b a r t i 等，利用已分类的实例集训练分类器， 来衡量页面与主题的相似度，并用于指导搜索顺序。 m c c a l l u m “o 】将巩固学习引入网络蜘蛛模型，其主要特点是利用巩固学习 的方法预测和选择未来回报最大的链接进行搜索。 d i l i g e n t i i l l j 从相关页面出发，构建“语境图”和分类器，并根据语境图的 层次预测距离相关页面的远近，较近的页面较早访问。 e s t e r t n 2 采用“隧道”技术指导搜索，当搜索精度低于某一预先定义的阈 值时，则将主题范围增大，搜索未来回报较大的链接。 m e n c z e f 1 评价了三种w e b 分析算法：b e s tf i s tc r a w l e f ( 通过计算链接所 在页面与主题的相似度来得到采集优先级) 、p a g e r a n k 和i n f o s p i d e r s ( 通过链 接周围的文字，利用神经网络和遗传算法来得到采集优先级) 。通过实验比较， 发现b e s t f i r s t 方法最好，l n f o s p i d e r s 方法次之，p a g e r a n k 算法较差。此后， 基于链接结构的分析算法与基于内容的分析算法的结合逐渐成为主流。 a g g a 州a l n 将页面内容、页面的u r l 结构抽象为页面特征，并利用它们 构建w e b 的概率模型，用于预测链接的价值。 a l t i n g o v d e 等- 人利用一个规则的主题分类系统去训练一个贝叶斯分类 器，并用一个来源于主题链接模式之间的简单规则决定下一个访问的链接， 提高了主题蜘蛛的收获率和查全率。 y u v a r a n i 等引人利用链接里的关键词和链接周围文本预测文档与主题的 相关性，表现出较好召回率。 我国的主题w e b 信息采集技术研究才开始起步，许多学者也对主题w e b 信息采集技术的研究作出了贡献。 李盛韬等硝人在分析主题w e b 信息采集基本问题的基础上，提出了主题 网络爬虫的难点以及相关解决方案，并在此基础上设计实现了“天达主题 w e b 信息采集系统。 傅向华等“引人将w e b 爬行看作执行序列动作的过程，结合改进的快速q 西南科技大学硕士研究生学位论文第5 页 学习和半监督贝叶斯分类器，提出了一种新的具有在线增量自学习能力的聚 焦爬行方法。 李卫等，人以全信息理论为支撑，吸收传统向量空间模型的思想，采用 基于概念的向量空问模型，从词的语义层次对文本进行主题相关性分析，研 究并实现了一个基于主题的智能信息采集系统l f w c 。其使用扩展元数据的 语义相关性判定算法，对页面内的u r l 进行主题相关性预测。 黄建斌等他0 1 人提出了一个基于连续随机模型和巩固学习的主题采集方 法，实验验证该方法有较好的性能。 尽管众多的网络蜘蛛模型设计各不相同，但归根结底是采用不同的链接 价值评价标准。虽然现有主题w e b 信息采集技术取得了令人鼓舞的进步，但 从系统性能上看还难尽如人意，准确率还需要较大的提高。因此，未来主题 网络爬虫的研究主要是围绕如何提高链接价值预测的准确性，降低计算的时 空复杂度，以及增加主题网络蜘蛛自适应性这三个方面展开托“。 提高链接价值预测的准确性一直是近年来研究的焦点。将各类评价方法 相结合进行链接价值预测值得迸一步研究。另外，w e b 上存在大量的重复网 页，为了节约网络带宽和不影响采集的效率，网页去重也成为研究的重点。 1 4 研究的目的及意义 主题w e b 信息采集系统可以通过对整个w e b 按主题分块采集，并将不 同块整合，从而提高整个w e b 的采集覆盖率；由于采用主题采集，采集页面 大大减少，不仅提高了资源的有效利用率，极大的节省了资源的消耗，也大 大缩短了更新时间；它同时也向专业用户提供对特定专业领域的信息服务， 实现个性化服务。 系统采用网页去重机制，可以节约大量的存储空间，提高系统的效率。 在系统中引入统一内容定位( u c l ) 技术，可以对采集到的网页进行标引， 一方面能够方便地管理和组织信息，另一方面可以使用户方便地进行检索， 定制和过滤等。 本文的主要目的是从互联网上及时收集某个主题的无重复的海量信息， 并对每个网页进行标引，为播存结构、搜索引擎、脱线浏览、个性化信息代 理等系统提供满足个性化服务的丰富的信息资源和标引信息。因此，研究与 设计主题w e b 信息采集系统不仅具有较强的现实意义，也具有较强的理论研 究意义。 西南科技大学硕士研究生学位论文第6 页 1 5 本文的主要研究内容和组织结构 1 5 1本文的主要研究内容 本文深入分析了主题w e b 信息采集的原理，主题页面在w e b 上的分布 特征以及主题w e b 信息采集系统中涉及到的主题相关性判别算法，网页去重 和u c l 标引技术，设计并实现了一个主题w e b 信息采集系统f o c u s e d s p i d e r 。 论文将讨论本人在课题歼发过程中所参与的实际研究工作，主要包括以下几 个方面： ( 1 ) 研究主题页面在w e b 上的分布特征与主题相关性判别算法，考虑父 页面和兄弟页面对u r l 主题相关性判别的影响以及子页面的主题相关性反 馈影响，提出了一种融合网页文字内容和w e b 结构的u r l 主题相关性判别 算法。 ( 2 ) 研究网页去重，提出了一种网页三级去重机制。 ( 3 ) 研究u c l 标引技术，对采集到的网页进行u c l 自动标引，便于信息 的进一步组织。 ( 4 ) 研究r s s 技术，设计并实现了基于r s s 的主题w e b 信息采集。 ( 5 ) 主题w e b 信息采集系统的设计与实现，以及实验结果的分析。 1 5 2本文的组织结构 本文主要分为五章，组织结构如下： 第一章绪论，简要介绍课题来源、背景、现状、研究的目的及意义与本 文的主要内容和组织结构。 第二章详细分析了主题w e b 信息采集的原理与结构，以及主题页面在 w e b 上的分布特征，是全文研究的重要理论部分。 第三章详细研究了主题w e b 信息采集系统的关键技术一主题相关性判 别算法，网页去重和u c l 标引技术，是全文研究的技术基础。 第四章给出了主题w e b 信息采集系统f o c u s e d s p i d e r 的总体结构，对结 构中的s p i d e r 采集，页面解析，u r l 主题相关性判别，网页去重、u c l 标 引以及基于r s s 的主题w e b 信息采集分别作了较为详细的论述，并给出了 设计方案和算法，是全文的重点。 第五章给出了实验系统及结果分析。 结论部分对整个论文的主要工作做了总结，同时也提出了今后需要进一 步做的研究和工作。 西南科技大学硕士研究生学位论文第7 页 2 主题w eb 信息采集概述 播存结构源端需要整合海量的w e b 信息，因此海量w e b 信息采集成为 源端需要解决的一个重要问题。而随着w e b 信息的爆炸性增长，传统的w e b 信息采集无针对性、页面失效率高、不能满足人们对个性化信息服务的需求 的缺点越来越明显。针对这些日益突出的问题，人们的兴趣开始逐渐转移到 主题领域，开始研究主题w e b 信息采集。 本章分析了一般的主题w e b 信息采集的原理及结构，详细分析了各模块 的具体功能，重点研究了主题页面在w e b 上的分布特征，是本文设计主题 w e b 信息采集系统的理论基础。 2 1 主题w e b 信息采集的原理及结构 2 1 1主题w e b 信息采集的原理 主题w e b 信息采集主要是指选择性地搜索那些与预先定义好的主题集 相关的页面进行采集的行为，它尽可能多的采集与某个主题相关的w e b 资 源，扩大该主题资源的覆盖率。粗略地说它主要是指这样一个w e b 应用程序， 从一个初始u r l 集出发，通过w e b 协议访问u r l ，并根据一定的网页分析 算法过滤与主题无关的链接，保留与主题相关的链接并将其放入待采集的 u r l 队列；然后根据一定的搜索策略从队列中选择下一步要采集的网页 u r l ，并重复上述过程，直到达到系统的某一条件时停止。图2 1 给出了传 统w e b 信息采集和主题w e b 信息采集的比较。 在图2 一l 中，白框代表主题无关页面，黑框代表主题相关页面，虚线代 表没有访问的链接，箭头代表访问的链接。由图可知，传统w e b 信息采集按 照宽度优先策略，循着每一个链接进行采集，因此有大量与主题无关的页面 被采集。而主题w e b 信息采集则先确定最有可能与主题相关的链接，忽略主 题无关的页面，只采集与主题相关的页面，因此大大节约了采集时问，提高 了采集效率。 因此，相对于传统w e b 信息采集，主题w e b 信息采集需要解决以下三 个关键问题瞳“： ( 1 ) 怎样决定待访问u r l 的访问次序? 许多主题w e b 信息采集是根据已 下载的网页的相关度，按照一定原则，将相关度进行衰减，分配给该网页中 的超链接，而后插入到优先级队列中。此时的爬行次序就不是简单的以深度 西南科技大学硕士研究生学位论文第8 页 优先或者宽度优先为序，而是按照相关度大小排序，优先访问相关度大的 u r l 。不同主题w e b 信息采集之间的区别之一也就在于它是如何决定u r l 的访问次序。 ( 2 ) 怎样判断一个网页是否与主题相关? 对于已经访问的网页，我们可以 获取它的文本内容，采用文本挖掘技术来实现。不同w e b 信息采集之间的区 别之二就是如何计算当前访问网页的主题相关度。 ( 3 ) 怎样提高主题w e b 信息采集的覆盖率? 如何穿过质量不好f 与主题不 相关) 的网页得到与用户感兴趣的主题相关的网页，从而提高主题资源的覆盖 率。 t j 届 ，r 1 7 一一 毋- 爿脬掣 一可】? l 一爿一1 ；f l ： 、一j 、_ + ”蔷 0 ，_ 。+ 一 _ _ a )传统辩e b 信息采集b )主题鬻e b 信息采集 图2 1传统w e b 信息采集和主题w e b 信息采集对比 f i g 2 1e o m p a r i s o nb e t w e e nt r a d i t i o n a l 嚣e bc r a 肆li n ga n df o e u s e d 骤e bc r a 舅ll n 鬈 2 。 。2 主题磷e b 信息采集的结构 主题w e b 信息采集的搜索任务本质上是一个顺序决策过程，其目标是寻 找到一个最谯的行动选择净列，使得按这穿列访闯w e b ，获得的主题稆关页 面越多。另外，对于已访问的页面，判断是否与主题相关，如果不相关则抛 弃，相关则保存到主题页谣库。图2 2 给出了一个典型的主题w e b 信息采集 模型，。该模型主要分为盘大模块：主题与初始u r l 选择，s p i d e f 采集，页 面分析，页萄过滤器，链接过滤器。 西南科技大学硕士研究生学位论文第9 页 图2 2主题w e b 信息采集模型 f i g 2 2 豫o d e lo ff o c u s e d 弹e bc r a w ii n g 主题与初始u r l 选择：为了有效地进行采集，系统一般会给用户提供一 个主题分类目录以供选择和一个初始u r l 集以供采集器采集。为了有效地确 定用户主题的含义，用户要提供对主题的进一步描述，如主题文本等。初始 u r l 集的选择，会影响采集的准确率，因此，一般采集系统需要选择质量较 高的主题u r l 作为初始种子u r l 集。 s p i d e r 采集：这个部分处于系统的底层，也叫“网络蜘蛛 ，是系统专 门与具体的w e b 打交道的部分。主要通过各种w e b 协议来自动采集i n t e r n e t 上w w w 站点内有效的消息( 包括文本、超链接文本、图像、声音等各种文 档) 。一般来说w e b 协议包括h t t p 、f t p 、g o p h e r 以及b b s 等，但从主流 上来看，仍以h t t p 为主。 页面分析：在页面采集到以后，我们要从中提取出链接来，然后在链接 过滤模块中根据链接与主题的相关性判别来过滤与主题无关的链接，接受与 主题相关的链接并进行下一步的采集；另外，为了在页面过滤模块中进行页 面与主题的相关性判定，也必须提取出页面中的正文和关键词来；为了其它 操作的需要，我们还要进行对页面内容标题、摘要、时间等的提取。 页面过滤：该部分主要是进行页面与主题的相关性判别，过滤掉与主题 西南科技大学硕士研究生学位论文第1 0 页 无关的页面。为了进一步提高采集页面的准确率，需要对已采集的页面进行 主题相关性评价。通过对评价结果较低的页面删除，来提高所采集主题页面 的准确率。这个问题是检索领域内的一个经典问题，已经有许多成熟的基于 关键词相关性判别算法。 链接过滤：该部分主要是进行u r l 与主题的相关性判别，过滤掉与主题 无关的u r l ，是主题w e b 信息采集系统中的核心模块。为了有效的提高主 题w e b 信息采集的准确率和效率，系统需要预测待采集的u r l 与主题的相 关度，并提供相关的采集策略用以指导系统的采集过程。u r l 的预测值越高， 采集的优先级就越高。反之，若通过一定的评价策略，发现u r l 与主题无关， 则将该u r l 及其所有隐含的子链接一并去除，这个过程我们称之为剪枝。通 过剪枝，系统就无需遍历与主题不相关的页面，从而保证了采集的效率。但 是，剪枝的行为也可能将潜在的与主题相关的页面也剪掉。因此，u r l 与主 题相关性判别的好坏直接影响着整个系统的采集效率以及采集质量。 2 2主题页面在w e b 上的分布特征 整个w e b 上的页面分布看似杂乱无章，但是经过研究发现，主题页面在 w e b 上分布服从一定的规律。我们可以将这些分布规律总结为四个特征：h u b 特征、s i b l i n g “n k a g el o c a l i t y 特征、站点主题特征和t u n n e l 特征。通过对 这些特征的研究和开发利用，可以发现一些在主题w e b 信息采集过程中对无 关u r l 和页面过滤有用的规律。 2 2 1h u b 特性 美国康奈尔大学的教授j k l e i n b e r g 发现w e b 上存在大量的h u b 页面， 这种页面不但含有许多出链，并且这些链接趋向于同个主题。也就是说， h u b 页面是指向相关主题页面的一个中心。另外，他还定义了权威页面 ( a u t h o r i t y ) 的概念，即权威页面是那些关于某一主题有价值的页面。如图2 3 所示，好的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 a u t h o r i t v ( h l t s ) 算法幢“，这个算法我们将在3 1 2 2 小节介绍。该算法对于计算广泛 的和概念模糊的主题效果不错，但由于算法会产生概念扩散现象，使得计算 后的中心页面和权威页面不太适合具体主题。 西南科技大学硕士研究生学位论文 第1 1 页 图2 3 h u b 页和a u t h o r i t y 页 f i g 2 3 h u bp a g e sa n da u t h o ri t yp a g e s 2 2 2 s ；bl in g lin k a g el o c al it y 特性 在h u b 特征的基础上，a g g a r w a l 等人又提出了s i b l i n l i n k a g el 0 c a l i t y 特性n ”。如图2 4 所示，( 1 ) l i n k a g el o c a l i l y ，即页面趋向于拥有链接到它的 页面的主题；( 2 ) s i b l j n gl o c a l i t y ，对于链接到某主题页面的页面，它所链接 到的其它页面也趋向于拥有这个主题。该特性实际上是h u b 特性的另一种表 现形式，主要是从页面的设计者设计的角度考虑的：一个页面的设计者趋向 于把本页面指向于与本页面相关的其它页面。 图2 4 s i b ii n g l i n k a g el o c a li t y 特性 f i g 2 4 s i b li n g l i n k a g el o c a ll t yc h a r a c t e ri s t i c 其中，宰代表一个主题，a ，b ，c d ，e 代表网页，根据s i b l i n l i n k a g e l 0 c a l i t y 特性可知，a ，b ，c ，d ，e 拥有同一个主题。 2 2 3 站点主题特性 通过观察可以发现，一个站点趋向于说明一个或几个主题，并且那些说 明每个主题的页面较紧密地在此站点内部链接成团，而各个主题团之间却链 接较少。这主要与网站的设计者的设计思路有关。每个网站在设计时都有目 标，而这种目标往往就集中在一个或几个主题中。而w e b 上的浏览者往往也 西南科技大学硕士研究生学位论文第12 页 有一定的目的性，即一个用户趋向于浏览同一主题的页面。为了满足浏览者 的这一需求，网站设计者通常将相关内容紧密地链接在一起。 2 2 4t u n n el 特性 在w e b 中还有一种现象，w e b 中的主题页面团之间往往要经过很多无关 链接才能互相到达，。这些无关链接就像一个长长的隧道一样，连接着两个 主题团，因此称为“隧道现象”。在主题w e b 信息采集过程中，t u n n e l 的存在 极大地影响着采集的页面质量，覆盖率和准确度。为了提高采集页面的准确 率，我们需要提高u r l 与主题相关性判别以及页面与主题相关性判别的阈 值，而阈值的提高将过滤掉大量的t u n n e l ，使得采集系统很可能丢失t u n n e l 另一端的主题团，进而影响了查全率( 或者说资源发现率) 。反过来，为了提 高查全率，就得大量发现t u n n e l ，就得降低u r l 与主题相关性判别以及页 面与主题相关性判别的阈值，但是阈值的降低使得在得到t u n n e l 的同时，也 混进了大量的其它无关页面，从而大大降低了页面的准确率。这是一个两难 问题，但关键还是不能有效地区别t u n n e l 和其它大量无关页面，事实上两个 主题团之间的隧道数也较少。该问题随着采集页面数量的不断增加会逐渐减 轻，因为根据s i b l i n g “n k a g el o c a l i t y 特征，绝大多数主题团还是可以被主 题w e b 信息采集系统通过其它的链接途径发现。 2 2 5四个特性的关系 w e b 中的页面对于主题来说是杂乱的，但是也存在一些规律。h u b 特性 说明了主题容易成团出现的现象，s i b l i n “n k a g el o c a l i t y 特性进一步对成团 的特征有所扩展，站点主题特性说明了主题团所在的位置，而t u n n e l 特性说 明了主题团在w e b 上分布并不稠密，并且由较少的链接和t u 仰e l 连接。 2 3本章小结 本章详细分析了主题w e b 信息采集，为进一步的研究与设计奠定了理论 基础。首先介绍了一般的主题w e b 信息采集的原理及结构，详细分析了各模 块的具体功能，然后重点研究了主题页面在w e b 上的分布特征。 西南科技大学硕士研究生学位论文第13 页 3主题w e b 信息采集系统关键技术研究 主题w e b 信息采集主要采集特定主题的信息资源，因此，主题相关性判 别可以使w e b 信息采集器只获得本主题的相关资源。另外，w e b 上存在大量 的重复网页以及如何对采集到的网页进行标引组织，也是需要解决的问题。 本章研究了主题w e b 信息采集系统的关键技术：主题相关性判别算法、 网页去重和u c l 标引技术，其中重点研究并比较了u r l 与主题的相关性判 别算法，为进一步实现系统作好技术准备。 3 1主题相关性判别算法研究 3 1 1页面与主题的相关性判别算法 最好的页面主题相关性判别算法应该从基于语义理解的角度解决，但是 常常要花费很大的计算代价。从目前实际应用来看，页面的主题相关性判别 仍然是基于关键词的，主要有全文本扫描、布尔模型、向量空间模型和概率 模型等，其中向量空间模型是用的最多的。 3 1 1 1向量空间模型 向量空间模型心引是关于文档表示的一个统计模型。向量空间模型是基于 这样一个关键假设，即文章中词条出现的顺序是无关紧要的，它们对于文档 的类别所起的作用是相互独立的，因此可以把文档看作一系列无序词条的集 合。向量空间模型的基本概念如下： 文档：由基本的语言符号组成的字符串，也泛指一般的文本或文本的片 段，一般指一篇文章。尽管文档可以是多媒体对象，但在本文中，我们假设 为文本对象。 特征：文档内容由一些特征来表示，一般由文本所含有的基本语言单位 来表示，包括字、词、词组或短语等，主要是词。即文档d 可以表示为 d o c “_ r ，l e ，l f = d ( 1 ，2 ，厶) ，其中f 表示各个特征。因此，由这些特征张开了一 个向量空间，每个特征表示一个维度。 特征权重：在一个文档中，每个特征都被赋予了个权重w ，表示这个 特征在该文档中的重要程度。权重一般都是以特征的频率为基础进行计算的， 比如采用t f i d f 公式表示等。这样文档d 就表示为d = 珧1 ，m 2 ，屹；靠，) ， 可简记为d = d ( m ，屹，) ，此刻，项缸的权重为，其中，1s 七s 刀。 西南科技大学硕士研究生学位论文第14 页 向量空间模型：给定一自然语言文档d = d ( l ，；2 ，w 2 ；岛，) ，我们可 以把1 ，2 ，厶看作一个n 维的坐标系，而，w 2 ，为相应的坐标值，因此一 个文档就表示为n 维空间的一个向量，我们称d = d ( m ，w 2 ，) 为文档d 的 向量表示或向量空间模型。 相似度度量：两个文档d 1 和d 2 之间的相关程度常常用它们的相似度 跏( d l ，d 2 ) 来度量。相似度可以通过向量间的内积公式m 1 计算： n 、1 跏( d l ，d 2 ) = 露w 2 七 ( 3 1 ) j _ 一 七= l 也可以通过向量夹角余弦公式n 7 ，计算： & ，l ( d 1 ，d 2 ) = c 口= 3 1 1 2 页面与主题的相关性判别 判断页面与主题的相关性的重要手段就是分类。目前存在多种基于向量 空间模型的分类算法，如：简单向量距离算法，贝叶斯算法，k 最近邻( k n n ) 算法，人工神经网络，支持向量机等。 因为w e b 信息采集系统要求速度和性能，而向量空间模型计算简单、处 理能力强、正确率高等优点决定了它比较适合网络信息的采集。基于向量空 间模型的简单向量距离分类算法与其它分类算法相比较，它能把文档内容的 处理简化为特征项及权重的向量表示，把对文档内容的处理简化为向量空间 中向量的运算，使问题的复杂性大大降低。因此本文采用了基于向量空间模 型的简单向量距离分类算法来实现页面与主题的相关性判别，页面与主题的 相关性判别的过程如图3 1 所示。 其中，特征向量的权重用t f i d f 值表示，词条i | 在文档d f 中的t f i d f 值由下式旧引定义： 喙= 珥贼= 缘l o g ( o ，+ o o 1 ) ( 3 3 ) 。k 如是词条在文档q 中出现的频数，称为相频；玎七表示训练集d 中 包含词条的文档数，z 称为反转文档频率；n 表示训练集中的文档数。 屹 厶捌 西南科技大学硕士研究生学位论文 第15 页 为消除文档长度对文本表示方式造成的可能影响，往往需要对加权后的向量 进行规范化处理。归一化公式9 ，如下： 魄2 1 0 9 ( 疗七+ o 0 1 ) ( 3 4 ) 获得文本的特征向量和权重后，根据他们计算页面与主题的相关度，具 体的计算见公式( 3 2 ) 。比较主题相关度和阂值d ，如果大于d ，则表示页面 与主题相关，保留到数据库；否则判为不相关，丢弃该页。 训练文本集 学到该主题的特征 向量及向量的权重 w e b 翌h 套黼煮圣h 主题相关性计算 蘸垂 墼望萎? l 1 0 是 保存网页i 图3 1 页面与主题的相关性判别 3 1 2u r l 与主题的相关性判别算法 3 1 2 1 基于链接标签数据的判别 人们发现，通过对链接标签属性、链接文本信息、链接上下文文本等链 接标签数据可以进行u r l 与主题相关性的评价和描述。因此，链接标签数据 信息能够有效地指导主题w e b 信息采集。 ( 1 ) h t m l 链接标签 在h t m l 页面中，主要有4 种标签用于超链接：a n c h o r 标签，i m a g e 标 签，m a p 和a r e a 标签，f r a m e 和i f r a m e 标签。在这几种标签中，a n c h o r 标 签最常用，主要包括t i t l e ，a l t ，o n m o u s e o v e r ，h r e f 和链接文本等几种和超链 西南科技大学硕士研究生学位论文第16 页 接相关的属性。而l m a g e 标签则主要包括s r c 和a l l 两种与超链接相关的属性。 对于m a p 和a r e a 标签，它们相关的属性和a n c h o r 标签基本相同。f r a m e 和 l f f a m e 一般与f 豫黻e s e l 一起使耀，用予网页分割，相关的属性主要包括s f c 和n a m e 等属性。 如果把页面看成点，这些超链接看成边，则w e b 构成了一个有向图，则 这些链接所含的信息对页面的语义有着重要的解释作用。因此，我们可以通 过链接标签及其属性进行u r l 与主题的相关性判别，用于指导主题w e b 信 息采集。 ( 2 ) 基于链接标签数据的相关性判别算法 针对h t m l 链接标签的统计分析表明”，链接标签的h f e f 属性、链接 t e x t 和链接上下文文本在w e b 中分布最常见。