（计算机应用技术专业论文）基于web的文本信息检索算法研究.pdf

硕士学位论文 摘要 随着互联网技术的迅速发展，网上文本数量成指数级增长，如何有效检索这 些海量信息成为当前重要的研究课题。文本信息检索( i n f o r m a t i o nr e t r i c v a l ) 是指 从大量文档集合中找到与给定的查询请求相关的、恰当数目的文档子集。文本信 息检索足处理海量文本的重要手段。本文主要研究基于w e b 的文本信息检索算 法。 本文首先介绍了信息检索的发展概况和相关技术，分析了基于内容检索算 法、基j 二超链分析检索算法以及融合检索算法的特点。针对内容检索方法查全率 不高、超链分析检索方法容易产生主题漂移的缺点，本文将基于内容和超链分析 的检索方法相结合，提出一种基于超链接和标记文本的信息检索算法。该算法利 用网页之间的链接关系和超链接中的标记文本内容计算网页的综合权值，在此基 础上将检索结果进行排序输出。实验结果表明，该算法具有较高的查全率和查准 率。 为了提高检索的查准率和降低检索时间，本文将文本分类和信息抽墩技术辅 助检索，提出了一种基于分类和关键词组抽取相结合的信息检索算法。该算法加 入了分类和拙取技术，避免了向量空间模型算法中时间复杂度过大，查准率不高 的缺点。实验结果表明，所提算法具有更快的查询速度和更高的查准率。蚓时， 针对传统的信息检索性能指标无法有效地衡量检索结果的排序状况，本文还引入 了排序误差率概念用于评价检索结果的排序，并将其应用于向量空间模型算法、 基于分类的交互式检索算法以及分类和关键词组抽取相结合的检索算法中，实验 结果表明，本文所提算法具有较小的排序误差率。 最后，本文在已有信息检索算法的基础上，结合所提出的改进算法及技术， 实现了一个专业领域的全文检索原型系统。 关键词：文本信息检索；向量空间模型；超链接；标记文本；关键词组抽取 查全率：查准率 基于w e b 的文本信息检索算法研究 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 fi n t e r n e tt e c h n o l o g y ，t h en u m b e ro fd o c u m e n t so n t h ei n t e r n e ti n c r e a s e se x p o n e n t i a l l y o n eo fi m p o r t a n tr e s e a r c h e sf o c u s e so nh o wt o d e a lw i t ht h e s eg r e a tc a p a c i t i e so fo n l i n ed o c u m e n t s t e x ti n f o r m a t i o nr e t r i e v a li sa t a s kt h a ti n v o l v e sf i n d i n gm o r er e l e v a n td o c u m e n t sf o rau s e rq u e r yi nac o l l e c t i o no f d o c u m e n t s t h i st h e s i sm a i n l ys t u d i e st h ea l g o r i t h m so fi n f o r m a t i o nr e t r i e v a lb a s e d o n w e b f i r s t l y ，t h i st h e s i sb r i e f l yi n t r o d u c e st h ed e v e l o p m e n t a n dt e c h n o l o g yr e g a r d i n g t h ei n f o r m a t i o nr e t r i e v a l b a s e do nt h i s ，t h ec o n t e n t - b a s e da l g o r i t h m ，t h el i n k b a s e d a l g o r i t h ma n df u s i o n b a s e da l g o r i t h ma b o u tt h ei n f o r m a t i o nr e t r i e v a l a r ea n a l y z e d s e c o n d l y ，i no r d e r t oa v o i dl o wr e c a l li nc o n t e n t b a s e dr e t r i e v a la n d t o p i cd r i f t p h e n o m e n a i nl i n k - b a s e dr e t r i e v a l ，an e w a l g o r i t h mb a s e do nh y p e r l i n k sa n da n c h o r s i s p r o p o s e dw h i c hc o m b i n e st h ec o n t e n t - b a s e dw i t hl i n k b a s e dr e t r i e v a la l g o r i t h r 矗 i nt h i s a l g o r i t h m ，h u ba n da u t h o r i t yv a l u e s a r e f i r s t l yc a l c u l a t e df r o mt h e l i n k s b e t w e e nt h ew e b p a g e s ，a n dt h er e l e v a n tw e i g h to fe a c hp a g ei sg a i n e db ym a t c h i n g l i n ka n c h o ro rd o c u m e n tc o n t e n tw i t hq u e r y ，a n dt h e nr a n k st h er e t r i e v a lr e s u l t s t h e e x p e r i m e n tr e s u l t ss h o w t h a tt h en e w a l g o r i t h mf o ri rh a sm u c hh i g h e rp r e c i s i o na n d r e c a l l i no r d e rt oi m p r o v et h ep r e c i s i o na n dr e d u c et h er e t r i e v a lt i m e ，t h i st h e s i sp u t s f o r w a r da ni n f o r m a t i o nr e t r i e v a la l g o r i t h mb a s e do nc l a s s i f i c a t i o na n dk e yp h r a s e e x t r a c t i o n c o m p a r e dw i t ht r a d i t i o n a lv e c t o rs p a c em o d e l ，t h i sa l g o r i t h mr e d u c e s t i m ec o m p l e x i t ya n d i m p r o v e sp r e c i s i o n t h ee x p e r i m e n tr e s u l t sp r o v et h a tt h en o v e l a l g o r i t h mw o r k sw e l l t h e nan e wc r i t e r i o n n a m e dr a n k i n ge r r o ri sc o n t r i b u t e dt o s o l v et h ep r o b l e mt h a tt h et r a d i t i o n a lp e r f o r m a n c ee v a l u a t i o nm e t h o d o l o g yc a n t e v a l u a t et h er a n k i n gr e s u l t so ft h er e t r i e v e dd o c u m e n t se f f i c i e n t l y t h ee x p e r i m e n t r e s u l t si n d i c a t et h a tt h ep r o p o s e da l g o r i t h mo u t p e r f o r m st f 4 i d fa n di n t e r a c t i v e r e t r i e v a lb a s e do nc l a s s i f i c a t i o ni nr a n k i n ge r r o r c o m b i n e dw i t ht h e p r o p o s e da l g o r i t h m s a n d t e c h n i q u e s ，a ne n g l i s h d o m a i n - b a s e df u l lt e x ti n f o r m a t i o np r o t o t y p ei s i m p l e m e n t e do nt h e b a s i so ft h e i n f o r m a t i o nr e t r i e v a la l g o r i t h m k e y w o r d s ：t e x t i n f o r m a t i o nr e t r i e v a l ；v e c t o rs p a c em o d e l ；l i n k ；a n c h o r k e y p h r a s ee x t r a c t i o n ；r e c a l l ；p r e c i s i o n i l 湖南大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取 得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其 他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个 人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律后果 由本人承担。 作者签名：翰蝎砧蠛日期：炒q ，年f 月7 b 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学 校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查 阅和借阅。本人授权湖南大学可以将本学位论文的全部或部分内容编入有关 数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位 论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密团。 ( 请在以上相应方框内打“4 ”) 作者签名：缉删日期：妒1 年1 月7b 导师签名：d 绝彩 日期：细牛年月7 日 硕士学位论文 1 1 信息检索概述 1 1 1 研究背景 第1 章绪论 近年来，随着互联网技术的迅速发展和广泛应用，传统的搜索引擎面临着巨 大的挑战：( 1 ) 信息容量的巨大性，据统计，w e b 已经拥有1 0 0 亿左右的静态网页 和5 5 0 0 亿，- ：右的动态网页。尽管各种通用搜索引擎，如g o o g l e 、f a s t 、a l t a v i s t a 和g o t o 等在索引技术、索引数量上有所提高，但远远无法跟上w e b 本身的增长 速度，即使是目前全球最大的搜索引擎g o o g l e ，其索引的页面数量仅占w e b 总量的3 0 4 0 1 2j ；( 2 ) w e b 的动态性，w e b 页面的内容和结构每天都在变化， 索引数据库的更新维护很困难，返回给用户的信息许多都是无效的：( 3 ) w e b 的 异构性，w e b 中包含的文档类型各式各样，包括文本、图像、图片、声音等等； ( 4 ) w e b 贝面的重复性，最近的研究表明，将近3 0 的页面是重复的；( 5 ) 高链接 性，平均每个页面有超过8 个链接指向别的页面。 面埘这些挑战，如何在传统的信息检索技术基础上开展针对w e b 特点的研 究工作，开发出新的检索工具和技术，提高检索性能，从而解决信息定位问题， 是近年来信息榆索研究的焦点之+ 。 1 ，1 2 研究进展 信息检索的研究已有多年历史。早在上个世纪5 0 年代，当计算机被图书馆 等部门用于存储和管理文档时，信息检索就作为个研究领域而诞生了。到了 8 0 年代，信息检索领域在索引模型，文档内容表示以及匹配策略等方面取得了 许多研究成果，这些成果成功地应用于w e be ，产生了搜索引擎。w e b 信息检 索是指从大量w e b 文档的集合c 中找到与给定的查询请求印相关的、恰当数目的 文档子集s 15 1 。为了尽可能多地找出与用户查询请求相关的文档信息，许多研究 学者提出了很多的检索方法。 s a l t o n 提出了向量空间模型算法m 1 ， 用t f * i d f 将给定的文本( 文章、查询、 并成功应用于s m a r t 系统17 1 。该模型使 或文章的一段等) 转换成个维数很高 的向量，进行查询向量与文档向量的相似度比较。r o c c h i o & s a l t o n 提出了相关反 馈模型，该模型利用用户和系统之间的交互，有效地提高了检索结果精度。 m i c h a lc u t l e r i ”结合h t m l 标记的特性，在向量空间模型基础上提出了依据位置 信息的检索算法，提高了检索质量。 近年来，许多研究者发现，w w w 上超链结构是非常丰富和重要的资源，如 基于w e b 的文本信息检索算法研究 果能充分利用，可以极大地提高检索结果质量。基于这种超链分析的思想，许多 研究学者相继提出了链接分析算法1 1 0 一】，并成为研究的热点。k l e i b e r g t l 3 l 提出了 h i t s ( 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 网页) 。它的主要思想是利用页面的被 j ；f 用次数及其向外链接数目来决定不同网页的价值。b r i n & p a g e t l , i 提出了 p a g e r a n k 方法，其基本思想是：一个页面被多次引用，则这个页面很可能是重 要的；一个页面尽管没有被多次引用，但被一个重要页面引用，则这个页面也很 可能是重要的；一个页面的重要性被均分并被传递到它引用的页面。r l e m p e l 和s m o r a n 提出了s a l s a 算法1 15 1 ，该算法考虑了用户回退浏览网页的情况，保 留了p a g e r a n k 的随机漫游和h i t s 中把网页分为a u t h o r i t y 和h u b 的思想，但取 消了a u t h o r i t y 和h u b 之间的相互加强关系。 基于超链分析的检索方法虽然可以提高检索的查全率，但是研究学者认为结 合多种技术和方法的融合检索比单一检索方法更能有效地提高检索系统的性能 1 1 一s l 。h e n z i n e e r & b h a r a t 以及i b ma l a m a d e n 研究中心的c l e v e r 工程组均在 h i t s 算法的基础上结合内容的匹配策略分别提出了b & h 算法! ”】和a r c 算法t 2 。i 。 k i d u k 将分类技术融合内容的检索，提出了分类字典的检索方法i 。本文第二：章 将对这些代表性的检索方法进行详细讨论。 1 2 信息检索模型 信息检索的目的是从大量纷繁复杂的信息中筛选出符合用户需要的信息，构 造检索模型是其核心技术，它包括三个方面的内容：文档与用户查询的表示；查 询匹配策略：匹配结果的相关度表示。下面介绍几种代表性的检索模型：布尔模 型、向量空问模型、概率模型、以及隐含语义索引模型。 1 。2 。1 布尔模型 布尔模型 2 1 1 是一种简单而且常用的严格匹配模型，它定义了一个二二值变量集 合来表示文档。这些变量对应文档中的特征项，一般是由训练文档集中的词条或 短语组成，如果词条对文档内容有贡献则赋予t r u e ，否则为f a l s e 。检索时，根 掘用户提交的检索条件是否满足文档表示中的逻辑关系将检索文档分为两个集 合：匹配集和非匹配集。因匹配结果的二值性，所以无法在匹配结果集中进行查 询结果的相关性排序。布尔模型实现简单，检索速度快，在许多检索系统中得到 应用，例如y a h o o ! ，i n f o s e e k 等诸多网络检索站点均采用了这种模型。但布尔 模型的文档表示能力差，无法区分特征项对文档内容贡献的重要程度，并且逻辑 表达式过于严格，往往会因一个条件未满足而忽略了其他全部特征，造成漏检。 2 帧十学位论文 p 范数模型m 】是对布尔模型的扩展，它克服了简单布尔模型匹配函数过于严 格而导致漏检的致命缺陷。在p 范数模型中，假设文档d 可表示为： d = ( d 。，d ：，d 。) ，用户查询可表示为：q = 白，q ：，q 。) ，其中d ，和q i 分别表示第i 个特征词条对文档内容和查询内容的贡献程度，d i ，q 。在 o ，1 的区间上取值。定 义文档与查询条件问的相似度为： n ( d , q ) = 1 - l 地黑等! 巡r ， l强十耐+ + 吼1l 其中15 p s m ，根据具体应用改变d 。，q 。和p 的取值可达到不同的检索效果。在 实际使用中p 的取值由实验得出，取值范围一+ 般为 2 ，5 】。 1 2 2 向量空间模型 向量空间模型是近些年使用较多且效果较好的一种信息检索模型。该模型 在s m a r t i ，l 系统环境中获得较好的检索质量。这一模型主要是将文档看作由相 瓦独立的词条组o ，t ：，z 。) 构成，对于每一词条f ，都根据其在文档中的重要程度 赋以一定权值，将( t x , t ：，。) 看成一个n 维坐标系中的坐标轴，( w 。，w ：，w 。) 为对 应的坐标值，从而转化为个向量空问。文档映射成为空间中的一个点，从而将 文档信息的匹配问题转化为向量空间中矢量匹配问题。词条t 。在文档d 中的权值 通常由两部分计算获得：一部分是词条k 在文档d i 中出现的次数，即如，另 培b 分是整个文档集合中包含词条k 的文档个数，即吼。直观上看，巩越大，w 。 值越大；同样矾越小，值也越大，说明特征项t 。更能代表文档d ；的内容。 搜索引擎进行查询时，其查询条件也要进行向量化，才能方便计算，一般采 用布尔框架。所谓布尔框架就是：t 的值要么是l ，要么是0 ：如果文档d 中包含 f ，则t 的权值为1 ，否则为o 。同样在进行查询匹配时，查询条件q 的向量化过 程也是如此，如查询条件q 包含f ，则f 的权值为1 ，否则为0 。 12 3 概率模型 布尔模型和向量空间模型都将文档表示诃条视为相互独立的项，忽略了表示 词条问的关联性，概率模型则考虑了词条、文档间的内在联系，利用词条之间以 及词条与文档f b j 的概率相依性进行信息的检索。 基于w e b 的文本信息检索算法研究 概率模型方法最早是由m a r o n 和k u h n s ( 1 9 6 0 ) 提出的，该模型在i n q u e r y i z 。 系统环境中获得比较好的检索质量。二值独立检索模型( b i r ) 是一种实现简单且 效果较好的概率模型m - 。在b i r 中，根据用户的检索q ，可以将所有文档分为两 类，一类与检索需求q 相关( 集合r ) ，另一类与检索需求不相关( 瓦) ，它们的概 率分别表示为：p ( r i d ) 和p ( r - l d ) 。索引项的分布有如下两条假设：( 1 ) 文档d 可 以表示为db 。，z ：，x 。) ，其中二元随机变量x 。表示索引项t ：是否在该文档中出现， 如果出现，则x ，= 1 ，否则x ，= 0 。( 2 ) 在一个文档中，任意一个索引项的出现与否 不会影响到其它索引项的出现，它们之间相互独立。 文档d 与检索q 的相关度排序函数为： s 咖( 。，口) 2 而p ( r i d ) i ( 1 2 ) 利用b a y s e 公式并经过简化后可得文档与用户查询的相关函数： s 拥( 。，q ) = z 。g 考篇 ( ，) 其中p l = 形，吼= ( 一7 一，) ，表示训练文档集中文档总数，r 表示训练文 档集中与用户查询相关的文档数， 表示在训练文档集中包含词条i 的文档数， 表示r 个相关文档中包含词条z 的文档数。 1 2 4 隐含语义索引模型 隐含语义索引l s i ( l a t e n t s e m a n t i ci n d e x i n g ) 是1 9 8 8 年s t d u m a i s 等人提出 的一种新的信息检索代数模型】，它主要是为了克服以上三种传统的信息检索模 型基于字、词匹配带来的局限性。l s i 可以看成是一种扩展的向量空间模型，它 利用统计计算导出的概念索引进行信息检索，而不再是传统的索引字、词。 l s i 基于这样一种断言，即文档库中存在隐含的语义结构，这种语义由于被 文档中词的语义和形式上的多样性掩盖而不明显。l s i 对原文档库的词文档矩 阵进行奇异值分解，取莳k 个最大的奇异值及其对应的奇异矢量构成一个新矩阵 来近似表示原文档库的词一文档矩阵。由于新矩阵消减了词和文档之问语义关系 的模糊度，从而更有利信息检索。针对一些t r e c 文档库的实验结果 2 6 , 2 7 】和初步 的理沦分析1 2 8 1 证实了基于l s i 的信息检索系统的优越性。 4 硕十学位论文 在l s i 模型中，一个文档库可以表示为个m n 的词一文档矩阵a 。这里， n 表示文档库中的文档数；m 表示文档库中包含的所有不同词的个数。a 中元素 a 。，为非负值，表示第i 个词在第j 个文档中出现的频度。客观上，由于词和文档 的数量都很大，而单个文档中出现的词又非常有限，因此a 一般为稀疏矩阵。 与前面几种传统的检索模型相比，l s i 模型的优势表现在： ( 1 ) 词和文档同处于一个空阳j ，l s i 应用更具灵活性。查询既可以是词和文档， 也可以是词和文档的组合，甚至表示为多主题。当然，返回给用户的也可以是词， 而非仅仅为通常的文档； ( 2 ) 向量空间中每一维的含义发生了很大的变化，它反映的不再是词的简单出 现频度和分布关系，而是强化的语义关系； ( 3 ) 用低维词、文档向量替代原有词、文档向量，可以有效地处理大规模文档 库： ( 4 ) 便于实现自动文档榆索、查询构成以及相关反馈。 1 3 基于概念的检索 目静，搜索引擎提供的检索服务主要分为基于关键字的检索和基于概念的检 索。基于关键字的检索其核心是关键字的机械匹配，即检索出的文章要显式地包 含有用户所提交的词条。显然，这种方式的固有缺点是参与匹配的只有字符的外 在表现形式，而非它们所表达的概念。因此，关键字检索显然是不够的，实现真 正意义上的语义蕴涵扩展、语义外延扩展、语义相关扩展的概念检索将成为一种 需求。m c c u n e t2 9 l 最先开始在关键字检索的基础上引入基于概念的检索( c o n c e p t s e a r c h ) 。该方法利用了词条在概念上的相关性，可以检索出那些并不显式地包 含用户指定词条，但是却包含其同义词的文档。 搜索引擎在实现概念检索时，一般通过对用户的查询条件进行概念词条扩 展，从而转化为关键字检索。概念词条关系的获得可以有以下两种方法： ( 1 ) 手工建立词典来存储概念层次及词条之间的交叉联系，该工作通常由领域 专家来完成。 ( 2 ) 使用语法分析、统计等技术从文档集合中自动学习。 1 4 相关度反馈 在很多情况下，用户难以提出查询，其初始的查询请求q 通常是不精确、不 完全的。与概念检索类似，相关度反馈技术i8 i 也可以帮助用户形成查询请求。但 是，基于概念检索的目的是通过扩展查询请求来提高系统的召回率，而相关度反 基t - w e b 的文本信息检索算法研究 馈技术则通过对查询请求不断修正以提高系统的精确度，其相关反馈过程如图 1 1 所示。 s + 00 s l 查询修正 i l f 修正后的矗询 初始查询检索结果 检索器用户 评估 图1 1 相关反馈 在具有相关度反馈功能的系统中，系统按照下述过程对用户的查询请求进行 逐步求精。( 1 ) 检索器给出查询q 的检索结果集合s ；( 2 ) 用户对s 中文档的相关度 进行评估，并反馈给系统。所有被用户标记为“相关”的结果组成了正反馈集合 s + ，标记为“不相关”的结果组成了负反馈集合s 一；( 3 ) 系统根据用户的反馈对 查询q 进行修正；( 4 ) 重复步骤( 1 ) ，( 2 ) ，( 3 ) ，直到用户得到满意的结果为止。 b o r g m a n i ，o j 指出一次好的反馈可以提高4 0 到6 0 的精度。但是，目前仍然很少 有搜索引擎支持该功能。其原因可能是因为相关度反馈需要用户的参与，而普通 用户在使用搜索引擎时不太愿意花时间利用这些附加功能。 1 5 信息检索系统性能评价标准 查全率( 又叫召回率，r e c a l l ) 、查准率( p r e c i s i o n ) 和查找速度( s p e e d ) 是信息 检索系统常用的重要评价指标。当用户将自己的查询提交给系统后，整个文档集 在逻辑上划分为四部分：检索到的相关文档、检索到的不相关文档、未检索到的 相关文档、未检索到的不相关文档。因此，查全率和查准率的定义如下： 查准率= 检索到的相关文档数检索到的全部文档数 查全率= 检索到的相关文档数文献库全部相关文档数 查准率从一个方面描述了检索系统的查询开销，查全率是检索系统查找用户 所需信息能力的标志，速度是检索系统响应用户要求的时间度量。这三者是相互 制约的，对于一个具体的检索系统，其查准率随查全率的增加而减少，速度随着 奁全率的增加而减慢 3 1 】。 6 硕+ 学位论文 1 6 本文研究内容 由于中文文本信息涉及到短语切分等技术难点，本文只针对英文文本信息进 行研究，着重研究了基于w e b 的文本信息检索算法，主要工作包括以下几个方 面： 一、对主要的信息检索算法进行了比较深入的研究。分析、比较了基于内容 检索方法、基于超链分析检索方法和基于融合检索方法的优缺点，并对代表性算 法的实现过程做了细致地研究；总结了提高检索性能的几个关键因素。 二、针对基于内容的检索方法查全率不高，基于超链分析的检索方法容易产 生主题漂移的缺点，本文将基于内容的检索方法和超链分析的检索方法相结合， 提出了一种超链接和标记文本的信息检索算法。该算法利用网页之间的链接关系 和超链接巾的标记文本内容计算网页的综合权值，在此基础上将检索结果进行排 序输m 。实验结果表明，该算法具有较高的查全率和查准率。 三、为了提高检索的查准率和降低检索时间，本文将文本分类和信息抽取技 术辅助检索，提出了一种基于分类和关键词组抽驳相结合的信息检索算法。浚算 法加入了分类和抽取技术，避免了向量空间模型算法中时间复杂度过大，查准率 不高的缺点。实验结果表明，所提算法具有更快的查询速度和更高的查准率。蚓 时，针对传统的信息检索性能指标无法有效地衡量检索结果的排序状况，本文还 引入了排序误差率概念崩于评价检索结果的排序，并将其应用于向量空间模型算 法、基于分类的交互式检索算法以及分类和关键词组抽取相结合的检索算法中， 实验结果表明，本文所提算法具有较小的排序误差率。 四、本文将提出的算法和技术相结合，实现了一个针对计算机论文的专业信 息检索原型系统。 全文分为六章，主要内容如下： 第一章概述了信息检索的研究背景、研究进展、相关技术以及性能评价标准， 介绍了本文所作的主要工作；第二章对主要文本信息检索的算法进行了总结，分 析了基于内容检索、基于超链分析检索和基于融合检索的优缺点，并对代表性算 法的实现过程做了细致地研究：第三章提出了基于超链接和标记文本的信息检索 算法；第四章提出了基于分类和关键词组抽取的信息检索算法；第五章实现了一 个计算机相关论文的专业信息检索原型系统；第六章总结全文，给出了本文的主 要结论和进一步研究方向。 本文各章的联系与全文的结构如图1 2 所示。 7 基于w e b 的文本信息检索算法研究 图1 2 全文的结构图 8 硕十学位论文 第2 章主要文本检索算法研究 2 1 引言 当前w w w 正在深度和广度方面飞速发展，i n t e r n e t 上包含了大量信息资源， 它变成人们交流思想，获取信息的便利手段。但是，i n t e r n e t 所具有的丌放性、 动态性和异构性使得w w wl 的资源分布很分散，没有统一的管理和结构，大 大降低了人们对信息资源的利用效率。如何快速、准确地从海量信息资源中寻找 所需信息已成为困扰网络用户的大难题。w w w 上最多的是文本信息，因此 w e b 信息处理的核心就是如何处理这些w e b 文档。 本章对主要信息检索算法进行了分析和比较，详细地阐述了基于内容检索方 法，基于超链分析的检索方法以及融合的检索方法，并对其进行了总结。 2 2 基于内容的检索 基于内容的检索是传统的检索方法，它主要是从用户查询词条在文档中的出 现情况角度来考虑，包括词条频率、词条位置信息等等。 2 2 1 词条频率的检索方法 向量空间模型是根据词条频率进行检索的典型算法，最初由s a l t o n 等人在 六十年代初期提出并发展起来的。这一模型主要是将给定的文本( 文章、查询、 或文章的一段等) 看作由相互独立的词条组“，t ：，。) 构成。对于每一词条t ，都 根据其在文档中的重要程度赋以一定的权值。将( f ，t ：，j 。) 看成一个n 维坐标系 中的坐标轴，( w 1 ，w ：，w ) 为对应的坐标值，从而转化为一个向量空间。词条t 。在 文档d 。中的权值通常由两部分计算获得：一部分是词条k 在文档d ；中出现的 次数，即如，另一部分是整个文档集合中包含词条k 的文档个数，即识。这样 有： w * 2 靠* i d f k 2 以 ( 1 0 9 2 ( n ) + 1 )( 2 1 ) 其中，代表文档集合中的文档数量，代表在文档集合中出现特征项t 。的文档 数目。从公式( 2 1 ) 可知，如越大，w 。值越大；同样越小，值也越大，说 9 基丁w e b 的文本信息检索算法研究 明该特征项t 。更能够代表文档d 。的内容。 进行文档向量与查询向量的相似度s i m ( d j ，q ) 比较，通常采用余弦法： s 砌( d ，q ) ：。口：f ：坠( 2 2 ) 1 ( 善嘲荟q k 2 ) 在进行查询匹配时，查询条件q 的向量化过程可采用布尔模型进行： 旷i n 妻，q ( 2 - 3 )q j2 0 若t j g o u 3 ) 特征向量t ，出现在查询条件q 中，则q 为1 ，否则为0 。 相似度值越高说明两者之间越相关，越能反映用户的查询要求。因此，向量 空问模型算法计算简单并巨有效，得到广泛的应用j 3 2 , 3 3 。但是它也存在以下缺点： ( 1 ) 各个特征项不论处于文档中何种位置，表达文档内容的能力是相同的。而 实际上出现在文档不同位置的特征项对文档内窖的贡献程度是不一样的，比如出 项在标题的特征项应该比出现在摘要中的特征项显得更为重要。 ( 2 ) w e b 文档信息之间的变迁是通过链接完成的，因此，链接的文本信息从某 个角度上来说代表了被链接w e b 文档的重要信息，而利用向量空间模型进行w e b 信息查询忽视了这些信息。 2 2 2 词条位置信息检索方法 m i c h a lc u t l e r l 。】算法是根据词条位置信息，利用h t m l 文档结构和链接信息 进行检索的方法。该方法首先将h t m l 标记分为六类：p l a i n tt e x t ( 正文) 、t i t l e ( 标 题) 、h 1 一h 2 、h 3 h 6 、s t r o n g ( 包括强调、粗体、斜体、下划线) 、a n c h o r ( 链接 标记文本) ，并根据重要程度对每类赋以不同的重要度因子c w 。特征项权值的 计算公式为： w = ( t f v 。c 缈) i d f( 2 4 ) 其中，职y 代表特征项频率向量，t f v 一( 咖，t f v ：，咖，咖。，t f v ，咖。) ，分别表示 特征项t 在正文、s t r o n g 、h 3 h 6 、h 1 一h 2 、标记以及标题中出现的次数。当 c w ：( 1 ，1 1 1 0 ，1 ) 时，特征项t 的权值计算转变为向量空间模型的权值计算公式： w ：( t f v 。c v ) m i d f = ( v 1 + t f v 2 + t f v 3 + t f v 4 + t f v 6 ) + i d f = t f4 i d f ( 2 5 ) 刁i 同类别赋以不同重要度因子是因为查询匹配过程中，出现在w e b 文档中 l o 硕士学位论文 不同位置的同一关键词表达文档内容的能力是有差别的。比如，出现在标题中的 特征项应该比出现在链接中的特征项更能确切代表文档的内容，同样出现在链接 中的特征项也要比出现在正文中的特征项更能代表文档的内容，因此该方法有效 地提高了检索质量。但同时该方法也存在不足：特征项权值的计算使用了反比文 献频率i d l ，每当文档集合增加一篇文档，文档总数就会发生改变，包含该特征 项的文档数日也随之发生变化，因此必须重新计算每特征项的权值，计算量太 大，不适用于文档的动态更新。文献 3 4 ，3 5 在m i c h a lc u t l e r 算法基础上提出了 改进算法。文献f 3 4 根据特征项出现在不同部分将一篇文档从逻辑上划分为个 相对独立的文本段，出现在不同独立段的特征项具有不同的权值，权值的计算公 式为： 2 以，。( 2 6 ) 其中，坑。表示第k 个特征项在第i 个文本段中出现的频率，z 。表示第i 个文本 段的长度，这样既避免了使用反比频率i d l ，有利于实现文档的动态更新，又体 现了1 ；同位置信息的特征项表达文档内容的不同能力。文献 3 5 认为m i c h a l 算 法将h t m l 标签分为6 类仅仅基于作者对文章标题等的一般性看法，并不能证 实这样的分类是合理的。因此，它提出了利用聚类将h t m l 标记进行划分的思 想。分类在一组相似性很高的h t m l 文档中进行，根据标签类别合并文档，然 后将这些标签文档相互比较，如果文档两两相近，则合并两个标签，有效地改善 了检索质量。 2 3 基于超链分析的检索 基于内容的检索方法是一种传统的检索方法，它的很多理论都是由小型的、 静态的、同构型文档集推导出来。然而i n t e r n e t 所具有的开放性、动态性和异构 性给信息检索领域带来了新的挑战。近几年许多研究学者开始利用w e b 页面的 结构特性，提出了基于超链分析的方法，作为基于内容检索方法的补充。该方法 将w e b 看成一个有向图g = ( v ，e ) ，其中v 是页面集合，e 是页面之间超链接集 合。该方法认为链接信息与被链接的对象之间必然存在着某种可信的映射关系， 一个页面被其它站点引用的次数基本上反映了该页面的受欢迎程度( 重要性) 3 6 1 。 目前，有关这方面的研究提出了如下方法： 2 3 1 p a g o r a n k 方法 p a g e r a n k 算法是b r i n & p a g e 提出的”4 】，并在搜索引擎g o o g l e i 圳中得到应用。 基于w e b 的文本信息检索算法研究 它的基本思想是：一个页面被多次引用，则这个页面很可能是重要的；一个页面 尽管没有被多次引用，但被一个重要页面引用，则这个页面也很可能是重要的： 个页面的重要性被均分并被传递到它引用的页面。页面重要性的计算公式如 下； - c 荟( r ，) b ， 其中u 代表一个w e b 页面，f 。是u 引用的页面集合，b 。是引用u 的页面集 合，c 是小于1 的常系数，用于保证所有网页排名值的总和保持为常量，n 。= 峨j ， 即u 的出度。 这是算法的形式化描述，也可以用矩阵来描述此算法。定义邻接矩阵a ，行 和列对应网页集里的网页，如果存在一条网页u 到网页v 的超链接，则4 ”。局。 否则为0 。设r 对应网页集的个向量，上面的公式可以转化为rz 酬噼，所以 r 是a 的特征根为c 的特征向量。经过对初始向量的多次跌代可以得到收敛后 的r 。 以上方法的缺点是当两个页面互相指向，但不指向其它任何页面时，在迭代 中将造成陷阱，不断的累加排名值而不传递出去。为此，引入了衰退因子q ) ， e m ) 对应网页集的某一向量，对应r a n k 的初始值，算法改进如下： 脚) _ c 荟尺。+ 卿) ( 2 8 ) p a g e r a n k 算法除了对搜索结果进行排序外，还可以应用到其它方面，如为 用户导航等。a r v i n da r a s u 等经过试验表明，p a g e r a n k 算法计算效率还可以得到 很大地提高m ，。 2 3 2h lt s 算法 p a g e r a n k 算法中对于向外链接的权值的贡献是平均的，也就是不考虑不同 链接的重要性。而w e b 的链接具有以下特征：( 1 ) 链接具有注释陛、导航性或者 广告性，但只有注释性的链接才用于权威判断。( 2 ) 基于商业或竞争因素，很少有 w e b 网页指向其竞争领域的权威网页。( 3 ) 权威网页很少具有显式地描述。可见平 均分布权值不符合链接的实际情况m l 。k l e i g b e r g i ”】提出的h i t s 算法引入了两类 网页，一种称为权威网页( a u t h o r i t y 网页) ，另种称为集中网页( h u b 网页) 。 a u t h o r i t y 网页是一种包含丰富信息资源的w e b 页面，而h u b 网页是提供指向权 威网页链接集合的w e b 网页。h u b 网页本身可能并不重要，或者说没有几个网 页指向它，但是它却提供了指向就某个主题而言最为重要的站点的链接集合。 硕士学位论文 般来说，好的h u b 网页是指向许多好的权威网页；好的权威网页是由许多好的 h u b 网页指向的w e b 网页。它们之间存在着互相增强的关系。 h i t s 算法从现有的搜索引擎( 如a l t a v i s t a ) 中获取查询结果，从中选出接 近目标的t 个网页作为根集s ，然后根据这些网页的入链和出链进行前后一级扩 展，构成一个更大的基集t 。集合t 中每一成员都分别有两个值：a u t h o r i t v 值和 h u b 值。算法首先进行初始化，然后执行网页权重的迭代传递，即i 操作( h u b 到a u t h o r i t y ) 和o 操作( a u t h o r i t y 到h u b ) ： l 搛作： ) = ：h ( v ) ( s i = x lx vn e e ) ( 2 9 ) 怠 0 操竹： ) = y a ( v ) ( s o = x lx e vn e ) )( 2 1 0 ) 愿 每次迭代后对口f “) 和 f h j 进行规范化处理。式( 2 9 ) 反映了若一个网页由很多好的 h u b 贝指向，则其权威值会相应增加；式f 2 一l o ) 反映了若一个网页指向许多好的 权威网页，则h u b 值也会相应增加。因此，h i t s 算法最终将输出一组具有较 大h u b 权重的页面和具有较大a u t h o r i t y 权重的页面。 但存实际应用中，h i t s 算法也存在以下几个问题： ( j ) 由s 生成t 的时间歼销很昂贵，需要下载和分析s 中每个网页包含的所 有链接，并且还要排除重复链接，计算量比p a g e r a n k 算法大： ( 2 ) 有时某主机a 上的很多文档可能同时指向另外一台主机b 上的某个文档， 这就增加了a 上文档的h u b 值和b 上文档的a u t h o r i t y 值，相反的情况也是如此。 而h i t s 算法是假定某一文档的权威值是由不同的单个组织或者个人决定的，上 述情况影响了a 和b 上文档的h u b 值和a u t h o r i t y 值。 ( 3 ) h i t s 算法最大的弱点是处理不好主题漂移问题( t o p i cd r i f t ) d 5 , 1 9 , 4 0 1 ，也就 是紧密链接t k c 5 1 ( t i g h t l y k n i tc o m m u n i t ye f f e c t ) 现象。如果在集合t 中有少数 与查询主题无关的网页，但是它们是紧密链接的，h i t s 算法的结果可能就是这 些网页，从而偏离了原来的查询主题。下面讨论的s a l s a 算法则有效地解决了 t k c 问题。 2 3 3s a l s a 算法 p a g e r a n k 算法是基于用户向前浏览f 6 9 页的直觉知识，h i t s 算法考虑的是 a u t h o r i t y 网页和h u b 网页之间相互加强关系。实际应用中，用户大多数情况下 虽然向前浏览网页，但很多时候也会回