（计算机应用技术专业论文）面向领域的中文搜索引擎若干关键技术研究.pdf

中文摘要 面向领域的搜索引擎已成为为信息检索领域的一个重要研究课题。虽然该领 域已经取得许多研究成果，但目前相应的系统应用和检索效果却并不乐观。本文 就面向领域的搜索引擎的若干问题，包括爬取算法、文本关键词提取和文本分类， 进行了较深入研究。 w e b 信息采集是搜索引擎的基础，也是一个核心组成部分。本文讲解了w e b 爬取的基本原理和策略，并对常用的w e b 爬取算法进行了深入的分析。最后提 出了改进的基于s h a r k 算法的新算法。 关键词提取是文本处理的一个重要环节。本文以朴素贝叶斯定理为基础，以 文本中词语的传统权重、第一次出现位置、出现位置的样本标准差为特征项，构 建了关键词提取的朴素贝叶斯模型。实验结果表明。相对于传统的基于权重的关 键词提取算法，该算法具有较高的准确度。另外，本文针对特征项取值离散化对 模型的不利影响，对该算法做了修正，重新调整了上述三个特征项在模型中的相 对重要性，从而进一步提高了算法的准确度。 文本分类是某些搜索引擎中对w e b 文本进行组织、实现高效检索的一项关 键技术。本文改进了传统的朴素贝叶斯分类模型，考虑进了文本长度和文本结构 两个影响因素，修正了分类模型的计算公式，同时在特征项选择算法中，综合考 虑了频度、集中度、分散度三项指标，使得选出的特征项更为合理，从而使分类 结果在精确度、召回率和f m e a s u r e 值方面均获得了一定程度的提高。 关键词：搜索引擎，爬取，关键词提取，文本分类，朴索贝叶斯定理 a b s t r a c t t h ed o m a i n - s p e c i f i cs e a r c he n g i n eh a sb e e na ni m p o r t a n tr o s c a r e hb r a n c ho f i n f o r m a t i o nr e t r i e v a la n da c h i e v e dr a p i dd e v e l o p m e n ti nr e c e n ty e a r s h o w e v e r , t h e r e a r es t i l ls o m ei s s u e sn e e dt ob es t u d i e df u r t h e rf o rb o o s t i n gi t sp r a c t i c a la p p l i c a t i o n a n di m p r o v i n gi t se f f e c t i v e n e s sa n de f f i c i e n c y t h i sp a p e rp r o v i d e sam o r ed e t a i l e d s t u d yf o rs e v e r a li s s u e si n t h ed o m a i n - s p e c i f i cs e a r c he n g i n e , i n c l u d i n gc r a w l i n g p o l i c i e s ，t e x tk e y w o r de x t r a c t i o na n dt e x tc l a s s i f i c a t i o m t h ei n f o r m a t i o nc r a w l i n gi st h ef o u n d a t i o nf o rs e a r c he n g i n e a tf i r s tt h e c r a w l i n gp o l i c i e sa n ds t r a t e g ya r es t u d i e d t h e ns 0 i n ec o m m o nc r a w l i n ga l g o r i t h m s a l ea n a l y z e di n g r e a td e t a i l i nt h ee n d ，觚i m p r o v e da l g o r i t h mb a s e do ns h a r k a l g o r i t h mi sp r o p o s e d k e y w o r de x t r a c t i o ni so n eo fi m p o r t a n ts t e p sf o rt e x tp r o - p r o c e s s i n g b a s e do n n a i v eb a y c st h e o r e m , t h i sp a p e re s t a b l i s h e sav a l i dk c y w o r de x t r a c t i o nm o d e lb y t a k i n gt h et r a d i t i o n a lw e i g h t , t h ef i r s to c c u r r i n gp o s i t i o na n dt h ea v e r a g ed e v i a t i o no f s p a c i n go ft h ec a n d i d a t ew o r d si nat e x ta sf e a t u r et e r m s e x p e r i m e n t a lr e s u l t ss h o w m a lt h i sm o d e la c h i e v e sh i g h e ra c c u r a c yt h a nt h et r a d i t i o n a lk e y w o r de x t r a c t i o n m e t h o db a s e do nw o r d sw e i g h t i na d d i t i o n , f o rr e d u c i n gt h ea d v e r s ee f f e c to fv a l u e d i s e r e t i z a t i o no ff e a t u r et c ：r m s - t h i sp a p e rr e - a d j u s t st h er e l a t i v ei m p o r t a n c eo ft h e a b o v e - m e n t i o n e dt h r e ef e a t u r et e r m sb yp r e s e n t i n gd i f f e r e n tc o r r e c t i o nf a c t o r sf o r t h e m , s oa st of u r t h e ri m p r o v et h ea c c u r a c yo f t h i sm o d e l t e x tc l a s s i f i c a t i o ni so l l oo fi m p o r t a n tt e c h n i q u e sf o rg r o u p i n gw e bd o c u m e n t s f o re f f e c t i v ei n f o r m a t i o nr e t r i e v a li n8 0 m es e a r c he n g i n e t h i sp a p e ri m p r o v e st h e t r a d i t i o n a ln a i v eb a y e sc l a s s i f i c a t i o nm o d e lb yt a k i n gt h ed o c u m e n tl e n g t ha n d s t r u c t u r ei n t oc o n s i d e r a t i o nw h e nm o d i f y i n gt h ec l a s s i f i e r sf o r m u l a i na d d i t i o n , i n v i e wo f t h ev a r i o u sf a c t o l 瞎i n c l u d i n gf r e q u e n c y , c e n t r a l i z a t i o na n dd e c e n t r a l i z a t i o no f w o r d si nad o c u m e n t , t h i sp a p e rp r o v i d e sa ne f f e c t i v ef e a t u r et e r m ss e l e c t i o n a l g o d t h m e x p e r i m e n t ss h o wt h a tc o m p a r e dw i l ht h et r a d i t i o n a lm o d e l t h i si m p r o v e d m o d e lg e t sab e t t e rr e s u l ti nt e r m so f p r e c i s i o n , r e c a l la n df - m e a s u r ev a l u e k e y w o r d s ：s e a r c he n g i n e ，c r a w l i n g ，k e y w o r de x t r a c t i o n ，t e x tc l a s s i f i c a t i o n ， n a i v eb a y e st h e o r e m 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得云整盘堂或其他教育机构的学位或证书 而使用过盼材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作 了明确的说明并表示了谢意。 学位论文作者签名：轻氖氐 签字日期；h 占年工月工- 日 学位论文版权使用授权书 本学位论文作者完全了解云洼盘堂有关保留、使用学位论文的规定。 特授权云整太堂可以将学位论文的全部或部分内容编入有关数据库进行检索， 并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国 家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：径氖茂 签字日期：妒6 年工月2 湘 导师签名： 签字日期： 踊盈蓐 p 年2 月2 乙日 第一章绪论 第一章绪论 1 1 课题研究背景、目的和意义 伴随着社会的信息化和i n t e m e t 的迅猛发展，网络给人们提供了丰富的信息 资源，而且资源的形式也多种多样，最常见的是文本形式的，此外还有视频、音 频等形式。但是，庞大的信息量也使用户在网络上寻找自己所需的信息时，如同 淹没在信息的汪洋大海中，找到所需的信息如同大海捞针。有时，不相关信息还 会造成干扰，产生了所谓的。信息迷向”问题。为此，用户要花费大量的时间和 精力来过滤无关信息。为满足用户信息检索的需求，形形色色的搜索引擎网站应 运而生。如今，搜索引擎已经成为互联网的第三大服务【l 】。 搜索引擎的主要任务是实现信息的快速定位和有效利用；搜索引擎的核心功 能是信息检索，即快速准确地为用户提供所需信息。进而，为了让搜索引擎更便 于用户学习和使用，往往需要增加一些辅助功能，比如提供站点索引、个人索引， 以及友好的人机界面等。上述这些努力都是针对改进搜索引擎的外部表现。但是， 更重要的工作是优化搜索引擎的内在设计，努力实现一个高效合理的信息索引机 制，提高信息检索和存储的效率，并使系统具有良好的可扩充性和实现与其他相 关系统的接口。 通用搜索引擎是人们获取信息的一个重要途径，但它存在以下的问题： ( 1 ) 覆盖范围有限：通用搜索引擎越来越难提供范围广泛的信息，最大的搜索 引擎如g o o g l e ，a l t a v i s t a 等也只可以索引静态网页的一小部分，没有一 个搜索引擎可以检索出总网页数的3 0 。 ( 2 ) 平衡访问：通用搜索引擎主要用来检索主流网站，它们也更容易检索本国 的网站，其次才考虑其他地区的网站( a l t a v i s t a 是个例外) 【2 】。 ( 3 ) 返回结果多而繁杂：传统的通用搜索引擎动辄返回几千几万条，甚至上十 万条，其中包含了许多无关的、或者相关性很小的信息。用户要找到自己 的信息，仍很困难，往往还需要逐条将链接打开，判断其是否为所需要的 信息。这也使用户要耗费更多的时间。 ( 4 ) 更新周期长：通用搜索引擎无选择地盲目采集w e b 上的所有内容，这对 系统的扩展性和稳定性也是一个严峻的考验。在满足规模扩展和查询性能 稳定的时候，信息更新的频率必然受到影响。即使是目前最优秀的搜索引 擎g o o g l e 的索引更新周期也达2 8 天。如果没有进行有效的更新，那么用 户查询时就会在返回结果中存在大量空白链接，难以满足及时查询的需 第一章绪论 要。 ( 5 ) 查询歧义：例如“v c ”，可以理解为。v i s u a lc + + ”或“v i t m n i n ec ”， 搜索引擎可能会无法区分这两个概念，以致产生歧义理解。 目前的通用搜索引擎由于维护的数据量很庞大，数据的更新速度较慢。而且， 随着信息多元化的增长，不同用户的检索需求很可能会差异很大，如果对所有用 户都只提供一个相同的入口，就不能有针对性地满足不同用户的检索需求。针对 这种情况，一个分类细致精确、数据全面深入、更新及时的面向领域的搜索引擎 便应运而生，并成为发展趋势，它也称为专业搜索引擎、主题搜索引擎、专用搜 索引擎或垂直搜索引擎【3 】【4 】。面向领域的搜索引擎具备有效的信息采集策略， 索引更新周期大大缩短。 面向领域的搜索引擎面向某一特定的专业领域，保证了对该领信息的完全收 集和及时更新。它能够为具有相同兴趣的用户及时、集中地提供各种专业资源查 询，从一开始就注意避开不相关信息，这就避免了搜索时很大一部分“噪音”， 提高了查询效率。在提供专业信息方面有着传统的大型通用搜索引擎所无法比拟 的优势。 面向领域的搜索引擎的优势在于： ( 1 ) 小而全，小而精：通用搜索引擎检索的每个网站的页面有限，往往不能超 过一定的数量( o o o g t e 对每个网站最多收录3 0 0 0 个页面) ，这样一来，更 深层次的内容就不能够从这样的通用搜索引擎中检索出来。但是面向领域 的搜索引擎由于更专注于相关的专门网站，它可以检索所有的相关页面。 ( 2 ) 更新速度快：通用搜索引擎的另一个缺点是不能维持最新的索引，如g o o g l e 一般是2 8 天更新一次。面向领域的搜索引擎所维持的索引较小，从而使得 更新变得较为容易，这样就可以使用户得到最新的信息【5 】。 ( 3 ) 专门化、个性化的查询功能：可以针对特定领域，提供专门的查询功能。 比如在面向证券领域的搜索引擎中，用户可以直接输入股票代码，以获取 该股票的相关信息。 ( 4 ) 一定程度上可以避免查询歧义：由于关注于特定领域，从而也就从一定程 度上降低了查询歧义的出现概率。 ( 5 ) 优化的信息抽取：可以对特定领域的信息，采取优化的信息抽取模式。 由于上述优点和用户的需要，面向领域的搜索引擎具有广阔的市场应用前 景。 1 2 面向领域的搜索引擎的研究现状 针对面向领域的搜索引擎的研究，国外是从上个世纪9 0 年代末才开始的。 2 第一章绪论 1 9 9 9 年，致力于将统计机器学习和自然语言处理方法应用于非结构的w e b 挖掘研 究工作的j a s o nr e n n i e 、a n d r e wm c c a l l u m 等人，将机器学习方法，主要是强化学 习方法应用到特定领域的w e b 挖掘中，开发出了一个专门用于搜索计算机科学论 文的搜索引擎系统c o r a ( w w w c o m j u s t r e s e a r c h c o r n ) 【6 】【7 】，但是该系统的效果 并不是很理想。印第安纳大学信息学院的f i l i p p om e n e z e r 、g a u t a mp a n t 等人采用 进化计算、神经网络和小世界模型等方法，对w e b 页面的主题信息抽取进行了深 入的研究，以实现具有自适应和自治性的特定主题信息发现系统，他们还研究了 主题信息系统性能的评判方法 8 1 2 】。印度理工学院的s o m e nc h a k r a b a r t i 等人在 f o c u s e dc r a w l i n g ( 聚集爬行) 等方面也进行了深入的研究 1 3 1 6 。此外，加州 大学、斯坦福大学、康奈尔大学、m m 公司也在2 0 0 0 年左右进行了相关的研究 d 7 d s 。 c i t e s e e r 1 9 n e c 公司和宾夕法尼亚州共同推出，免费提供计算机和信息 科学论文的搜索，目前这个搜索引擎在网络上使用很广泛，优秀的表现使它获得 了用户的喜爱。 国内在中文搜索引擎技术方面的研究和应用起步较晚。中文和英文有很大 的差异，中文的词与词之间不像英文那样，有明确的分隔符；而且中文的字词 组合变化丰富，这也给研究中文搜索引擎带来了不少难题，中文搜索引擎的开 发相比于英文搜索引擎要复杂得多。目前，国内在搜索引擎方面做得最出色的 要数百度 2 0 】。此外，新浪也研究出了自己的搜索引擎。在面向领域的搜索引擎 方面的研究，主要以北大计算机网络与分布式系统实验室为代表。他们承担了 国家9 7 3 重点基础研究发展规划项目“网络环境下海量信息组织预处理的理论 与方法研究”，主题搜索引擎也被纳入其项目计划 2 1 】。 总之，国内外在面向领域的搜索引擎技术方面的理论研究和应用尚处于发 展阶段。搜索引擎核心技术往往被一些公司所掌握，已经商业化的技术也很难 公开。因而，对这一课题进行理论研究和实践探索具有较大的挑战性，也具有 较大的学术和应用价值。 1 3 本文的主要研究工作 本文在天津市科技发展计划项目“基于w e b 挖掘和n l p 技术的面向领域 的信息检索系统研究”的基础上，重点探讨和研究了以下几方面的内容：( 1 ) 在 信息收集采集阶段，如何准确、高效地判断所收集的信息是否属于领域范围，以 更好地利用带宽资源，快速地获取领域信息；( 2 ) 如何使用网页特征提取方法， 标识网页，便于进行快速查找；( 3 ) 如何更好地组织收集到的文本，便于系统检 索。 第一章绪论 本文的主要研究工作如下： 1 讲解了w e b 爬取的原理和策略，对w e b 爬取算法进行了分析，并提出了 一个改进的爬取算法。 2 关键信息提取是文本处理的一个重要环节。本文以朴素贝叶斯理论为基 础，综合考查了三个能够表示词语在文本中重要程度的指标，即词语在文本中 第一次出现的位置、词语的传统权重度量( 驴。i a j ) ，词语在文本中所有位置的 样本标准差，提出了一种关键词提取算法。实验结果表明，相对于传统的基于 权重的关键词提取算法，该算法具有较高的准确度。同时，本文针对算法中的 离散化问题，对该算法又傲了迸一步的修正，进一步提高了算法的准确度。 3 在文本组织方面，改进了传统的朴素贝叶斯分类模型，考虑进了文本长 度和文本结构两个影响因素，修正了分类模型的计算公式，同时采用了更为合 理的特征项选择算法。实验结果表明，改进模型相对于传统模型，在精确度、 召回率和f m e a s u r e 值方面均获得了一定程度的提高。 1 4 论文结构 本论文内容共分为六章： 第一章介绍了课题的研究背景、目的和意义，指出了通用搜索引擎中所存 在的若干问题以及面向领域的搜索引擎的优势，同时介绍了本文的主要研究工 作。 第二章介绍搜索引擎的基本工作原理，详细说明搜索引擎的架构，并在此 基础上，提出本文所要解决的问题。 第三章先介绍w e b 爬行器的基本原理和爬取策略，深入分析了w e b 爬取中 的常用算法。在s h a r k 算法的基础上，加入新的因素，对其进行了改进。 第四章研究文本的关键信息提取，提出了基于朴素贝叶斯理论的关键词提 取模型，并与传统的基于权重的方法进行了比较。同时，针对特征项取值离散 化对提取模型的不利影响，提出了相应的改进措施，并对改进前后的效果进行 了比较分析。 第五章研究了朴素贝叶斯理论在文本分类中的应用，在同时考虑文本长度 和文本结构两个因素的情况下，改进了传统模型，并对改迸前后的效果进行了 比较分析。 第六章对本文的研究工作进行总结，并对未来研究工作做出展望。 4 第二章搜索引擎的基本原理 第二章搜索引擎的基本原理 2 1 搜索引擎的基本结构 搜索引擎的基本结构如下： 搜索引擎 - 1w w w 站点 用 e 广 人索爬 仆 jw w w 站点 户 机引行 络 系 接器器 一| 新闻组站点 统 口 t 焉面粒据翻 v一f t i 蛳g u 1 “”j g o p h e r 站 图2 1搜索引擎基本结构 首先解释一下图2 1 中的名词g o p h e l 有一种解释认为这种菜单式搜寻 i n t e r a c t 网资源的工具有如地鼠，能灵活地穿梭于i n t e r a c t 网信息系统之间，因之 得名。 g o p h e r 2 2 是i n t e r a c t 提供的一种由菜单式驱动的信息查询工具，采用客户 机服务器模式。i n t e r n e t 上有上千个g o p h e r 服务器。它们将i n t e m e t 的信息资源 组织成单一形式的资料库，称作g o p h e r 空间。g o p h e r 不同于一般的信息查询工 具，它使用关键字作索引，用户可以方便地从i n t e r a c t 某台主机连接到另一台主 机，查找到所需的资料。 搜索引擎可以分为四个部分，这四个部分之间是紧密相连的，前一个部分是 后一个部分功能实现的基础。 ( 1 ) 蜘蛛( s p i d e r ) ：用于发现i n t e r a c t 上的u r l 链接。 ( 2 ) 爬行器( c r a w l e r ) , 定向到s p i d e r 发现的链接，下载网页，并根据网页 上的链接，重新定向s p i d e r 。 上述两个部分往往是结合在一起的，没有严格地区分开：根据u r l 下载 网页、发现新的链接。s p i d e r 和c r a w l e r 有时可以互称，它们也被称为 r o b o t 。 ( 3 )索引器( i n d e x e r ) ：提取下载网页的特征，建立索引，形成一系列的倒排 文件表，索引文件和网页的相关信息将被存放到一个网页数据库中。 ( 4 )人机接口( i n t e r f a c e ) 用户查询接口，提供友好的界面，使用户便于操 作。它也要有较快的反应速度，能够根据用户查询，在数据库中快速进 5 第二章搜索引擎的基本原理 行查询匹配，并将相关网页的链接地址按照网页内容的相似度返回给用 户。 2 2 搜索引擎的工作机制 在这个四部分中，涉及到的技术或机制包含下面三个部分：数据采集机制、 组织( 索引) 机制和检索机制。 2 2 1 搜索引擎的数据采集机制 有两种数据采集方式，人工采集和自动采集方式【2 3 】。人工采集由专门信息 人员跟踪和选择有用的w w w 站点或页面，并按规范方式进行分类标引并组建 成索引数据库，人工采集基于专业性的资源选择和分析标引，可以保证所收集的 资源质量和标引质量；自动采集通过r o b o t 来完成。自动采集能够自动搜索、采 集和索引网络上众多的站点和页面，从而保证对资源丰富和交化迅速的网络信息 的跟踪和检索的有效性和及时性。搜索引擎的自动信息搜集功能又分两种：一种 是定期搜索，即每隔一段时间，搜索引擎通过“s p i d e r ”程序，检索一定口地址 范围内的互联网站，如果发现新的网站，它就会自动提取网站的信息和网址加入 自身的数据库中；另一种是提交网站搜索。目前，很多搜索引擎采取自动方式和 人工方式相结合的方式。， r o b o t 是采用自动采集方式的搜索引擎的核心，它在网络上搜索网页且自动 跟踪该网页中的超文本结构并依次采集该网页链接到的网页。r o b o t 在信息采集 的过程中，还需要遵循网站的r o b o t 专用协议。其原理可用下图表示： 图2 - 2r o b o t 原理图 6 第二章搜索引擎的基本原理 2 2 2 搜索引擎的数据组织机制 搜索引擎的数据组织主要是利用健壮的数据管理系统来组织所采集索引的 网页信息，形成索引数据库。数据库中的一条记录基本上对应于一个网页，原则 上包括关键词、网页摘要、网页u r l 等信息。由于各搜索引擎的索引原则和方 式不同，它们的索引记录内容( 即使针对同一网页) 可能会很不相同。 搜索引擎对网页的索引处理过程如下： 它主要通过从网页中自动抽取能表达网页主题意义的词作为索引词来构建 网页索引记录：抽词的基本依据是词频。此外，自动索引器还利用其他信息，进 一步帮助选词或计算词的权重。例如，选择在网页的标题标签、链接标签、用黑 体或斜体表示、或网页中开始几段文字中出现的词作为索引词。目前，几乎所有 重要的搜索引擎都采用全文检索方式、分析整个网页的所有词汇，并依据词频和 超文本结构确认词汇权重。另外，多数搜索引擎直接使用网页的开头部分内容， 生成文摘，例如，a l t a v i s t a 利用网页开头的2 5 0 个字符。此外，网页中m e t a k e y w o r d 标签和m c t ad e s c r i p t i o n 标签的合理使用，也可以帮助网页编制者专门提供关键 词和整个站点的描述概要。因此，这两个标签的内容也可能包含索引词。 在索引构成中，索引数量越多，则意味着可检信息越多，并能促使查全率提 高。索引涉及到以下方面： ( 1 ) 所索引的网络信息种类，索引类型是部分索引还是全文索引，以及索 引的深度； ( 2 ) 索引更新频率越快，则索引的时效性越强； ( 3 ) 索引词的选取：以词频统计为主，辅之以加权法( 根据索引词的出现 位置和相对于全文的长度，对其赋予权值) 和语言法( 按语义学设置 同义词，近义词、相邻词等) 。 综合上述因素，为搜索引擎编制合理高效的索引系统，将会对搜索引擎整体 性能有很大的帮助。 搜索引擎的数据组织模块还和数据采集标引模块一同实现索引数据库的动 态维护。例如，针对不断更新内容的网页和不断变更的网页地址，对索引数据库 进行及时的更新、添加、删除等处理，以保证索引数据库准确反应网络信息资源 的当前状况。 索引数据库是用户进行检索的基础，它的数据质量直接影响到检索效果，而 搜索引擎的数据采集标引机制又是决定数据库质量的关键技术。 7 第二章搜索引擎的基本原理 2 2 3 搜索引擎的用户检索机制 当用户通过关键词的方式查找信息时，搜索引擎会在网页数据库中进行搜 寻，如果找到与用户要求内容相符的网站，便采用一定的算法计算出各网页的相 关度或排名，然后根据关联度高低，将这些网页链接按降序返回给用户。 2 3 本文研究重点 由于搜索引擎涉及到的技术内容较多，在本文中不可能全面阐述。本文结合 课题研究的需要，重点探讨以下三方面的内容； ( 1 ) 如何采集w e b 文本。a p s t j 定合理有效的爬取策略，采用有效的爬取算 法，以获取所需的文本资源； ( 2 ) 如何对获取的文本进行预处理，重点研究关键信息的提取； ( 3 ) 如何对获取的文本进行分类组织，以实现有针对性的高效检索。 8 第三章面向领域的爬行技术研究 第三章面向领域的爬取技术研究 3 1 爬取策略概述 我们可以把整个网络想象成一个有向图，网络中的每个站点看成该有向图的 一个子图，网络中的每个页面就是图中的相应顶点，页面到页面之间的链接就是 顶点之间的边。搜索引擎的爬行器在网络上漫游，搜寻资源，就可以看成是对网 络的遍历。根据图论方面的知识，我们知道，遍历一个图最基本的算法有深度优 先和广度优先。深度优先算法采用堆栈机制，将待访问页面的u r l ( u n i v e r s a l r e s o u r c el o c a t o r ，统一资源定位器) 存放到堆栈中，每次访问时都要先访问最上 端的u r l ，分析该u r l 指向的网页，同时获得该网页包含的链接，再将这些链接 加入堆栈中。可用如下的过程来描述： ( 1 ) 初始化栈； ( 2 ) 将种子u r l 放入栈中； ( 3 ) 根据u r l 所指向的地址进行相关处理，完成后，将其u r l 从栈中清 除； ( 4 ) 发现被访问网页上的链接，如果该网页没有被访问，则将其u r l 放入 栈中保存； ( 5 ) 重复执行( 3 ) 和( 4 ) ，直至栈为空。 这样，以后每次都是访问最上边的u r l ，而位于底部的u r l 将会长时间得不 到访问。相比之下，广度优先搜索就不存在这样的问题。它采用队列的先进先出 机制，将待访问页面的u r l 存放到队列中，从队列的前端取出u r l 地址，分析该 地址指向的网页，获得该网页包含的新链接，再将这些新链接加到队列的末尾。 正如在上一章中所述的，网页信息的爬取是整个搜索引擎系统的基础，爬取 策略将影响到搜索引擎的效率，反应速度和检索结果的精确度。w e b 爬行器作为 搜索引擎的一个关键部分，负责自动遍历w e b 上的信息，根据发现的u r l 地址， 下载网页，并根据该网页提供的链接，访问其他的网页。搜索引擎的索引部分对 爬取得到的网页提取特征，建立索引，然后将索引和网页的相关内容存放到数据 库中。在以后的用户查询中，搜索引擎将针对用户查询，在数据库中进行查找， 并将相关网页的u l 也地址返回。 搜索引擎的爬行器在网络上搜寻网页，下载网页信息，并进一步根据网页上 的链接，到达新的网页，并如此往复下去。由于通用搜索引擎的覆盖领域很广泛， 这就相应要求它的爬行器要获得尽可能多的信息，这样，爬行器在工作中就要访 9 第三章面向领域的爬行技术研究 问尽可能多的网页资源。对网页进行初步判断( 比如，判断该网页是否已经被访 问过) 后，如果符合条件，就把它下载到本地机器中；或者将访问的网页先下载 到本地后，再判断它是否满足要求，不满足的话就将它删除。不管怎样，这种通 用搜索引擎的爬取策略都占用了大量的带宽资源。 面向领域的搜索引擎的的覆盖深度较大，但是覆盖范围有限，所涉及的网页 信息仅限于某一领域，比如股票。某一特定领域的信息相对于整个网络上的信息 来说，内容要少得多，两者之间的数量差别巨大，就好比一只蚂蚁的重量相对于 一只大象的重量。面向领域的搜索引擎如果不加区分地下载网页，会导致一系列 的问题： ( 1 ) 会占用大量网络带宽； ( 2 )还会加重网络负载； ( 3 ) 采集来的网页很多都是无用的，都将被丢弃，这也是浪费资源； ( 4 )最后一点，如果保存很多的无关网页，也会降低检索的效率。 面向领域的搜索引擎和通用搜索引擎在信息采集上的主要区别在于前者要 将爬取的边界控制在领域范围之内。通用搜索引擎在进行w e b 爬取时多数使用的 是广度优先爬取算法，这种算法要优于深度优先算法，使得信息的获取面更广， 避免了深陷一个站点中而无法更好地访问其他更有价值站点的问题。然而广度优 先算法也无法完全适用于面向领域的搜索引擎的爬取工作。f o c u s e dc r a w l i n g 技术就是针对面向领域的搜索引擎而提出来的，它们可以有效地改善面向领域的 搜索引擎的效率。 本章主要研究应用于面向领域的w e b 爬取，深入分析了常用的爬取算法和爬 取策略。在以上研究的基础上，作者提出了一个改进的w e b 爬取算法。 3 2w e b 爬取原理 为了掌握w e b 爬取的原理，有必要先了解w e b 网页的特点。w e b 网页具有两 个重要特征： ( 1 ) 含有丰富的 盯札标签：h t m l 标签可以将网页结构化，用不同的标签来代 表网页中相应内容的位置，从而指示该网页内容在整篇网页中的重要性。 ( 2 ) 含有超链接：超链接反映了网页之间的参考或引用。类似于科技论文的引 用，如果一篇网页引用了很多其他的网页，那么这样的网页也具有较高的 价值。因此，网页被链接的次数和链接其他网页的次数都可以作为衡量网 页重要性的指标。 1 0 第三章面向领域的爬行技术研究 3 2 1w e b 爬行器的结构 初始时，选择一定数目的初始u r l 种子，并将这些种子存放到u r l 前端中。 爬行器将根据种子u r l 在网络上爬取信息。u r l 种子一般都是一些和主题相关的、 或者一些大型的门户网站。爬行器中有多个爬取线程共同工作。可以将u r l 前端 视为同步共享资源，在同一时刻至多只能有一个线程占用u r l 前端。 图3 - 1 爬行器的原理图 u l 也前端 u l 也 第三章面向领域的爬行技术研究 3 2 2w e b 爬取策略 目前，w e b 爬取的策略 2 4 3 有： ( 1 ) 最佳最先爬取：根据一个已经给定的u r l 前端，那些符合评价标准的u r l 被挑选出来，以待进一步爬取。如何判断给定的u r l 是否是最佳的，如何在 前端中挑选最佳的u r l ，即如何判断最佳u r l ，有不同的衡量标准。有基于 页面内容的，还有基于链接结构的。在下面的部分中，将有详细讲解。例如， 基于页面文本内容的爬取算法、p a g e r a n k 和h i t s 算法都有最佳最先爬取的 思想。前者通过计算页面的相似度，选取出与主题相似度最大的页面作为下 一步爬取的目标；而后者则是将基于链接结构的页面重要度( 比如权威度、 中心度、p a g e r a n k 重要度等) 作为“最佳”的标准。 ( 2 ) p a g e r a n k 爬取：这种方法根据p a g e r a n k 值爬行，每超过一定数目的网页， 重新计算p a g e r a n k 值。 ( 3 ) i n f o s p i d e r 爬取：采用神经网络的方法来判断如何选取合适的链接。 其中，使用最广泛的爬取策略是最佳最先爬取。上述的爬取策略只有用于具 体的爬取算法中，才能体现出它的价值。本章的下一部分就是分析和比较主要的 爬取算法。 3 3w e b 爬取算法研究 3 3 1p a g e r a n k 算法和h i t s 算法 p a g e r a n k 算法 2 5 和h i t s 算法 2 6 两种算法都在w e b 挖掘和搜索引擎领域被 广泛而深入地研究过，在实践中也有具体实现 2 7 3 1 8 3 。它们都是基于链接结构 的算法，根据网页之间的链接结构来发现一些重要性较高的链接，指导下一步的 爬取。 我们首先要理解链接结构中的两个关键概念：权威页面和中心页面。它们都 必须是与领域相关的。如果一个页面被较多其他的页面链接，就表明该页面具有 较高的认可度，它可以提供较好的参考价值，这样的页面就称为权威页面；如果 一个页面指向较多的其它与领域或主题相关的页面的页面，可以看作是一个提供 了较重要的链接指示信息的页面，从它这里出发可以得到较多的领域信息，好比 起到了一个枢纽的作用，因而中心页面也称为枢纽页面。 1 p a g e r a n k 方法 p a g e r a n k 算法基于这样的两个假设： 首先，用户浏览完一个页面后，跟随页面上的链接进入其他页面符合一定的 第三章面向领域的爬行技术研究 概率，假设为卜d ，那么用户如果想随机重新打开一个新地址的概率则为d ；这里 的d 就是下面要讲的阻尼因子d 。 其次，假设了用户只会根据链接向前浏览或随机打开一个新的地址，也就是 说用户只会一直向前走，不会后退再浏览以前看过的页面。 现假设有p 、q 、r 三个页面指向页面a ，而a 包含到页面b 、c 、d 的链 接。则页面a 的p a g e r a n k 值计算如下： p r ( a 州+ u _ a x p r ( p ) 4 - 等+ 静 。d 其中的p 、q 、r 为含有指向页面a 的页面。d 是阻尼因子，一般的取值为 0 1 5 。其中的p r ( p ) 、p r ( q ) ，p r ( r ) 是页面p 、q 、r 的p a g e r a n k 值。c ( p ) 是页面p 含有的链接数，那么从页面p 进入页面a 的机会也就是1 c ( p ) 。 进一步将该式扩展，假设有n 个包含指向页面a 的链接的页面。分别为t l ， t 2 ，t n 。上面的表达式即变成： p r ( 彳) ：d + ( 1 一d ) 宇丝盟 3 - 2 ) 。笥c ( 互) 从以上内容，可以得出这样的结论：如果一个网页被多个网页所引用，那么 其p a g e r a n k 值就会比较高；而且，如果被权威度较高的页面引用，其p a g e r a n k 值也会比较高。即页面的p a g e r a n k 值会随着链接进行传播。 p a g e r a n k 算法与查询无关，是一种基于全局的算法，在知道了页面的链接 关系后，可以进行离线计算。在实际中经常采用迭代的方法来计算页面的 p a g e r a n k 值。 首先，给每个页面赋予一个初始值，比如l 。随着爬取的不断进行，会发现 更多的链接。那么从整体来看，网页之间的链接关系就会不断变化，从而导致 p a g e r a n k 的计算表达式发生变化。即使某个页面的p a g e r a n k 表达式保持不变， 链接到该页面的页面的p a g e r a n k 值发生变化，也会导致该页面的p a g e r a n k 值 发生变化。往往采取迭代的办法计算页面的p a g e r a n k 值，一般进行大约1 0 0 次 迭代，计算结果即可收敛【2 8 】。 2 h i t s 方法 h i t s ( h y p e r l i n k - i n d u e e dt o p i cs e a r c h ) 算法由m m 的阿尔马登研究中心的 j k l e i n b e r g 提出。该算法的基础是：在i n t e r n e t 上权威度较高的页面往往会指向 中心度较高的页面，而中心度较高的页面也包含指向权威度较高的页面的链接， 也就是说权威页面和中心页面之间有相互增强的作用。即，若一个页面被多个具 有较大中心度的页面所链接，则该页面的权威度也相应较大；若一个页面链接到 1 3 第三章面向领域的爬行技术研究 多个具有较大权威度的页面，则该页面的中心度也相应较大。因而可以通过利用 中心页面发现权威页面。 可以用下述的步骤来描述h i t s 算法是如何进行w c b 爬取的： s t e p l ：使用通用搜索引擎，输入与领域相关的关键词进行查询，获得一个 初始的结果页面集合，这其中包括数千个u r l 甚至更多； s t e p 2 ：将初始页面集合作为根集r ，并将其作为领域知识的初始表达； s t e p 3 ：将基本集b 初始化为根集r 的内容。 s t e p 4 ：通过进一步搜索，找到集合r 中的页面指向的页面，以及指向r 中 的页面的页面，最后将它们加入到集合b 中。 s t e p 5 ：进行权重传播； s t e p 5 1 ：赋予b 中的每个页面f 一个非负的初始中心度h i ，和一个 非负的初始权威度a ，： s t e p 5 2 ：计算每个页面的权威度，也就是指向该页面的所有页面的 中心度的加权和，即q = 五， s t e p 5 3 ：计算每个页面的中心度，也就是该页面指向的所有页面的 权威度的加权和，即鸟= 4 ， s t e p 6 ：定义邻接矩阵a ，设共有n 个网页，a 中的每个元素为a j ：如果页 面i 链接到页面j ，则元素旷1 ，如果不存在该链接则元素口矿l ； s t e p 7 ：设向量4 = “a 2 ，q ) 是由集合b 中所有页面的权威度构成的，向。 量h = ，也，九) 为所有页面的中心度构成；则得 4 = a 7 h ；h = a 口i s t e p 8 ：对两个等式进行k 次展开，则得 h = a a = 爿爿h = ( a a 7 ) = ( 五4 7 ) 2 i l = = ( a a 7 ) h ( 3 3 ) 4 = a r h ；a r a a = ( 4 7 椰口= ( a r a ) 2 a = = ( a 7 a ( 3 - 4 ) 依据数学知识，将这两个序列规范化后，将分别趋于各自的特征向量以4 r 以 及a 7 a 。特征向量中的每个元素就可以作为集合b 中的相应页面的最终中心度和 最终权威度。这个结果就可以用来指导w e b 爬取了。 在爬取中，优先选择基本集中权威度较大的边界页面( 即在根集向基本集扩 展过程中没有进一步搜索的页面，目的是为了可以发现更多的资源) ，然后爬取 这些边界页面中的链接u r l 。当沿着这些边界页面进行一定规模( 可以预先指定) 的爬取后，所得到的页面集合将是基本集的一个扩展，得到一个超集。整理超集 中的页面链接结构，根据这个链接结构重新计算各页面的权威度和中心度。爬取 再次选择超集中具有较大权威度的边界页面从而做进一步扩展爬取，可以得到新 的超集。爬取按照这样的步骤逐步遍历资源。 1 4 第三章面向领域的爬行技术研究 3 p a g e r a n k 和h l t s 算法的比较分析 p a g e r a n k 算法和h i t s 算法的不同之处在于： ( 1 ) 算法的局域性不同：h i t s 算法是一种局部的算法，其权威值是查询相 关的；然而p a g e r a n k 算法是一种全局算法，它独立于查询，只要确定网页和网 页之间的链接关系，就可以计算出网页的p a g e r a n k 值。 ( 2 ) 网页的重要性传播方式不同：在h i t s 算法中，网页的重要性从中心 页面向权威页面传播，中心页面和权威页面之间是相互增强的关系，从而借由中 心页面发现权威页面；而在基于随机冲浪模型的p a g e r a n k 算法中，网页的重要 性则是从一个权威网页传递给另一个权威网页。 ( 3 ) 花费时