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

硕士学位论文 摘要 随着i n t e r n e t 技术的高速发展，w e b 已经成为人们获取信息的一个重要途径， 由于w e b 上的文本信息日益增长，如何有效地检索用户所需信息成为一个非常重 要的研究课题。信息检索是指信息按一定的方式组织和存储起来，并根据用户的 需要找出有关信息的过程，是处理海量信息的重要手段。本文主要研究w e b 中的 信息检索算法及其应用。 本文首先介绍了信息检索的发展概况和相关技术，其次分析了信息检索技术 中三类典型的检索模型，系统地研究了大范围检索系统中基于内容检索算法、基 于超链分析检索算法以及混合检索算法的特点，并针对目前搜索引擎的个性化、 智能化趋势，介绍和分析了个性化信息检索的发展状况和几种基本模型。 针对短查询式造成的查全率高而查准率低的问题，本文将查询扩展和文本 分类技术融合辅助检索，提出了一种基于查询扩展和文本分类相结合的信息检索 算法。该算法引入了查询扩展和文本分类，增加了短查询式的信息，避免了传统 的查询扩展算法的时间复杂度过大缺点。实验结果表明，新算法提高了检索精度 和时效，并有效地克服了查询主题发生漂移的缺陷。 对于传统检索技术不能根据用户兴趣检索信息的问题，本文引入用户兴趣模 型并将内容过滤和文本分类方法相结合，提出一种基于内容过滤和分类的个性化 信息检索算法。该算法通过观察用户的浏览文档的行为，采用机器学习的方法不 断地更新兴趣模型，从而使该模型越来越贴近用户的真实兴趣：同时，根据用户 兴趣模型，算法采用内容过滤和文本分类的方法有效地检索用户感兴趣的信息。 实验结果表明，该算法具有较高的查准率和查询速度。 最后，本文将提出的算法和技术相结合，实现了一个的信息检索原型系统。 关键词：信息检索；向量空间模型；查询扩展；文本分类；用户兴趣模型：内容 过滤 1 1 1 信息检索算法在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 ft h ei n t e r n e t ，w e bh a sb e c o m ea ni m p o r t a n tw a y t of i n di n f o r m a t i o n s i n c et h eo n l i n ei n f o r m a t i o nk e e p si n c r e a s i n gr a p i d l y ，h o wt o i m p r o v et h ee f 诧c t i v e n e s sa n de m c i e n c yo fi n f o r m a t i o nr e t “e v a lh a sb e c o m et h e m o s tc h a u e n g i n gp r o b l e mf o rs e a r c he n g i n e s i n f o r m a t i o nr e t r i e v a li st h ep r o c e s st o f i n dm o r er e l e v a n ti n f o r m a t i o nf o ru s e r sr e q u i r e m e n ti nac o l l e c t i o no fd o c u m e n t s t h i sp a p e rm a i n l yc o n d u c t sr e s e a r c ho nt 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 ns e a r c he n g i n e s f i r s t l y ，w ei n t r o d u c e dt h ec u r r e n tr e s e a r c hp r o g r e s sa n dr e l e v a n tt e c h n o l o g yi n i n f o r m a t i o nr e t r i e v a l ，a n dc o m p a r e dt h ep e r f o r m a n c eo ft h r e ec l a s s i c a lm o d e l sf o r i n f o r m a t i o nr e t r i e v a ls y s t e m a t i c a l l y w ea l s oi n v e s t i g a t e dt h ed e v e l o p m e n ta n ds o m e p r i m a r ym o d e l so fp e r s o n a l i z e di n f o r m a t i o nr e t r i e v a l ，w h i c hi sb e c o m i n gm o r ea n d m o r ep o p u l a rw i t ht h er e q u i r e m e n t so fp e r s o n a l i z e da n di n t e l l i g e n ts e r v i c e s s e c o n d l y w i t ht h eo b s e r v a t i o nt h a tv e r ys h o r tq u e r i e si ni n f o r m a t i o ns e a r c h i n g o f t e nt e s u l ti nd e p r e s s e dp r e c i s i o n ，w ep i o p o s e dan o v e li n f b r m a t i o nr e t r i e v a l a l g o r i t h mb a s e do nq u e r ye x p a n s i o na n dc l a s s i n c a t i o n o u ra p p r o a c ha t t e m p t st o c a t c hm o r er e l e v a n td o c u m e n t sb yq u e r ye x p a n s i o na n dt e x tc l a s s i 6 c a t i o n t h e r e s u l t so fe x p e r i m e n t ss h o wt h a tt h ea l g o r “h mw ep r o p o s e di sm o r ep r e c i s ea n d e m c i e n tt h a nt h et r a d i t i o n a lq u e r ye x p a n s i o nm e t h o d s f u r t h e r m o r e ，w ep r o p o s e dap e r s o n a l i z e ds e a r c ha l g o r i t h m ，w h i c hc o m b i n e s c o n t e n t - b a s e df i l t e r i n ga n dt e x tc l a s s i f i c a t i o n ，t os o l v et h ep r o b l e mt h a tt r a d i t i o n a l i n f o r m a t i o nr e t r i e v a lt e c h n o l o g i e sc a n t s a t i s f ya n yq u e r yf r o m t h ed i f f e r e n t b a c k g r o u n dw i t ht h ed i f f e r e n ti n t e n t i o na n da tt h ed i f 托r e n tt i m e i no u ra p p r o a c h ， u s e r si n t e r e s tm o d e li su p d a t e db ym a c h i n e1 e a r n i n g ，b a s e do nt h eo b s e r v a t i o no f u s e r sb e h a v i o rw h e nt h eu s e ri sb r o w s i n gw e bp a g e s w i t ht h ec o n t i n u o u su p d a t e ， u s e r si n t e r e s tm o d e li sb e c o m i n gm o r ea n dm o r ea c c u r a t et ou s e r si n t e r e s t t h u s ， t h ei n f o r m a t i o ni nw h i c hu s e ri sr e a l l yi n t e r e s t e dc a nb er e t r i e v e de f f e c t i v e l yb y c o n t e n t b a s e df i l t e r i n ga n dt e x tc l a s s i f i c a t i o na c c o r d i n gt ou s e r si n t e r e s tm o d e l t h e r e s u l t so fe x p e r i m e n t ss h o wt h a tt h en e wa l g o r i t h mi sm o r ee f f e c t i v ec o m p a r e dw i t h t h et l a d i t i o n a li n f b r m a t i o nr e t r i e v a lm e t h o d s f i n a l ly ，ap r o t o t y p eo fi n f o r m a t i o nr e t r i e v a lw a sd e s i g n e da n di m p l e m e n t e d ， b a s e do nt h ea b o v ea l g o r i t h m sa n dt e c h n i q u e s k e y w o r d s ： i n f i 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 ；q u e r ye x p a n s i o n ；t e x t c l a s s i f i c a t i o n ；u s e rp r o f i l e ；c o n t e n tf i l t e “n g 硕士学位论文 图1 1 图1 2 图1 3 图2 1 图2 2 图3 1 图3 2 图3 3 图4 1 图4 2 图4 3 图4 4 图5 1 图5 2 图5 3 图5 4 图5 5 插图索引 大范围信息检索系统的体系结构 个性化信息检索系统的体系结构 全文结构图 基于内容的过滤 基于协作的过滤 四种算法查准率查全率比较图示 四种算法时间性能比较 扩展用词数量对查询性能的影响 用户兴趣模型学习及过滤流程图 基于分类和内容过滤的个性化检索算法架构图 三种算法查准率查全率比较图示 对比算法时间性能比较 系统体系结构图 数据处理初始界面 数据处理状态 信息检索系统主界面 检索有关“g e n e t i ca l g o r i t h m ”的论文结果 v 一一一一一一一一一一一一一一一一一 |；|；|； 篡羔墨羔|一 湖南大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所 取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任 何其他个人或集体己经发表或撰写的成果作品。对本文的研究做出重要贡 献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的 法律后果由本人承担。 作者签名：岳支日期：二鲴6 年j 月) 孑日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文 被查阅和借阅。本人授权湖南大学可以将本学位论文的全部或部分内容编 入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇 编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密回。 ( 请在以上相应方框内打“”) 作者签名：岳主 导师签名：燎弓乞 f 日期：弘“年弓月格日 日期：彳年乒月5 日 1 1 信息检索概述 1 1 1 研究背景 第1 章绪论 随着i n t e m e t 的迅速发展，w w w 已经成为世界上最大的信息库，它正曰益改 变着人类的生活方式。然而，由于w w w 信息资源庞大，结构复杂，如何高效地 从中找到需要的信息，已经成为困扰网络用户的一大难题。据统计，w 曲已经拥 有1 0 0 亿左右的静态网页和5 5 0 0 亿左右的动态网页【l 】。用户要在信息海洋里查找 信息，就象大海捞针一样，搜索引擎则是为了解决w e b 信息”迷航”问题而出现的 技术( 它可以为用户提供信息检索服务) 。现今搜索引擎技术面临着如下的挑战： 1 ) 搜索的反应速度和查询的准确性，要求系统能迅速从海量信息中获得指定信 息并及时跟踪信息的动态变化；2 ) 用户需求的不断提高，要求系统能查找特定 的主页或网页并获得同主题相关的站点；3 ) 自主个性，能够主动向用户推荐信 息并提供个性化信息服务。 信息检索( m f o r n l a t i o nr 咖i e v a l ) 是指从大量文档的集合c 中找到与给定的 查询请求q 相关的、恰当数目的文档子集s 【2 】，是搜索引擎用来处理海量文本的 重要手段之一，它在搜索引擎中是面向用户的最后环节，也是搜索引擎的目的所 在，无论系统如何设计，最终是为了信息检索，为了为用户提供服务。因此，信 息检索是在系统架构基础上，一个搜索引擎的关键部分。搜索引擎的好坏对用户 来说，取决于检索系统。信息检索通常指文本信息检索，包括信息的存储、组织、 表现、查询、存取等各个方面，其核心为文本信息的索引和检索。从历史上看， 信息检索经历了手工检索、计算机检索到目前网络化等多个发展阶段。适应网络 化、智能化以及个性化的需要正逐渐成为当前信息检索技术发展的新趋势。 面对这些挑战，开发出新的检索工具和技术，提高检索性能，满足用户日益 增加的需求，是近年来信息检索研究的焦点之一。 1 1 2 研究进展 信息检索起源于图书馆的参考咨询和文摘索引工作，从1 9 世纪下半叶首先 开始发展，至2 0 世纪4 0 年代，索引和检索成已为图书馆独立的工具和用户服务 项目。随着1 9 4 6 年世界上第一台电子计算机问世，计算机技术逐步走进信息检 索领域，并与信息检索理论紧密结合起来；脱机批量情报检索系统、联机实时晴 报检索系统相继研制成功并商业化。为了尽可能多地找出与用户查询请求相关的 文档信息，许多研究学者提出了很多的检索技术，并相继在索引模型，文档内容 表示以及匹配策略等方面取得了许多研究成果。同时，在信息处理技术、通讯技 术、计算机和数据库技术的推动下，信息检索在教育、军事和商业等各领域高速 发展，得到了广泛的应用。 g e r a r ds l a t o n 等人在本世纪六十年代末年提出的向量空旬模型( v e c t o rs p a c e m o d e l ) pj 是近年来应用较多的文本特征表示方法之一，它是一个关于文献表示的 统计模型，使用t p i d f 将给定的文本( 文章、查询、或文章的一段等) 转换成 一个维数很高的向量，然后进行查询向量与文档向量的相似度比较，具有较强的 可计算性和可操作性，并已经被广泛地应用于文本检索、自动文摘、关键词自动 提取、文本分类和搜索引擎等信息检索领域的各项应用中，取得了较好的效果。 r d c c h l o s a l t o n 提出了相关反馈模型【4 1 ，用户向信息检索系统提交查询表达 式，系统进行初始的查询，返回的文档集根据文档与查询的相关性排列，然后用 户进行相关判断，系统基于前一次查询检索到的文档相关性判断，进行相关反馈， 自动重新构建查询表达式。该模型利用用户和系统之间的交互，有效地提高了检 索结果精度。 针对用户输入查询串短，不能给搜索引擎足够信息进行检索从而导致的查准 率低的现象，查询扩展被提出来作为改善检索的一种方法。d c e n e s t e r 【5 】提出了 全局分析方法l s i 来扩展查询串，而x u 和c r o f i 【6 】提出了局部上下文分析方法， 目前流行的局部分析方法主要是局部反馈( 1 0 c a lf e e d b a c k ，也称为p s e u d o f e c d b a c k ) ，它是在相关反馈( r e l e v a i l c ef e e d b a c k ) 的基础上发展起来的。它将初次 查询的前篇文章认为是相关文章，并以此为依据对查询进行扩展。 由于w 曲上的超链接信息被作为重要的资源进行了很多方面的研究。对被链 接的信息具有某种导向的作用，可以用来提高搜索引擎的查询效果、分析某个网 站的拓扑结构等等，因此被作为重要的资源进行了很多方面的研究。s e r g e y & l a 聃t e n c e 在1 9 9 8 年提出了p a g e 黜m k 算法【7 】 其基本思想是：一个页面被多次引用， 则这个页面很可能是重要的；一个页面尽管没有被多次引用，但被一个重要页面 引用，则这个页面也很可能是重要的：一个页面的重要性被均分并被传递到它引 用的页面。同年，k l e i n b e 嬉鼹出了h i t s 算法 8 】，它利用页面的被引用次数及其向 外链接数目来决定不同网页的价值。其它一些学者也相继提出了另外的链接分析 算法，如s a l s a ，p h i t s ，b a y e s i a n 等算法。超链接分析技术已经在实际的系统 中实现和使用，并且取得了较好的效果。 随着网络技术的发展，个性化服务已经成为目前网络技术和智能信息处理中 的研究热点。在传统i n t e m e t 服务模式下，为了找到目标信息，用户要耗费大量 的时间和精力。个性化信息检索则根据用户的兴趣和特点进行检索，返回与用户 硕士学位论文 需求相关的检索结果。舡n j c 一9 1 、m l a d e i l i c 【10 1 、b o l l a c k e r 等对基于内容过滤的 个性化信息检索做了不同层面的研究。k o n s t a n 【12 1 ，l i e b e m a n 【1 3 】，a l t o n i s c h e i d l 【1 4 】 对基于协作过滤的个性化系统提出了自己的方法。由于在检索中考虑了用户的差 异，个性化信息检索可以大大提高检索的效率。 1 2 信息检索系统类型 人们在进行信息检索时，通常抱有两种期望，一种是期望找到所有与感兴趣 的主题相关的文档，即期望获得较高的检索率；同时又希望尽可能排除掉与检索 主题不相关的文档，即获得较高的检索精度。因此，目前网上的信息检索系统主 要分为两大类：一类是大范围的信息检索系统( 又称传统的信息检索系统) ，以 尽量多地检索到和用户要求相关的内容为其根本任务；一类是个性化的信息检索 系统，以尽量准确地检索到和用户要求相关的内容为其根本任务。 1 2 1 大范围信息检索 现有的搜索引擎如a l t d s t a ，y 曲o o ! ，g o o g l e 基本上都是采用传统的大范 围的信息检索模式，以尽量多地检索到与用户要求相关的内容为根本任务，不考 虑特定用户的特定检索需求，因此这类系统具有通用的性质。 w e b 上最多的是文本信息，大范围的信息检索技术将构成文档的基本项，如 构成文本文档的单词、短语等，构成图像文档的纹理特征项、图像内容标注的单 词等，统称为索引项。将构成检索的基本项统称为检索项一般情况下，检索项 和索引项是同一个集合。信息检索的目标是快速而准确地找出满足检索条件q 的 文档( 称这些文档与检索q 相关) 。在大多数情况下，还需要根据与检索条件q 的相 关程度对这些文档排序。 目前搜索引擎的检索方法主要为基于内容检索方法( 3 ”1 “、基于超链分析的 检索方法【7 8 ，1 7 枷1 以及混合的检索方法【1 9 。捌三大类。基于内容的检索是传统的检 索方法，它主要是从用户查询特征项在文档中的出现情况角度来考虑，包括特征 项频率、特征项位置信息等等。它的很多理论都是由小型的、静态的、同构型文 档集推导出来。基于超链分析的检索方法将w 曲看成一个有向图g = ( v ，e ) ，其中 v 是页面集合，e 是页面之间超链接集合。该方法认为链接信息与被链接的对象之 间必然存在着某种可信的映射关系。它适应了i n t e l c t 所具有的开放性、动态性和 异构性，作为基于内容检索方法的补充。混合的检索方法则是将几种不同的检索 技术根据其各自的优缺点进行有机的结合而形成的新检索方法。 大范围的信息检索的主要过程是：首先，通过删除停用词等操作对文本进行 处理形成索引：然后建立倒排索引表，表中记录每个索引项出现的文档编号和 具体出现的位置：根据索引表检索出与用户提问相关的文档，最后将检索出的文 档根据相关性排序；用户界面则是管理和用户的交互过程，它包括查询输入、文 档输出、用户反馈、结果的可视化。 该类系统的体系结构如图1 1 ： 图11 大范围信息检索系统的体系结构 然而，现有的检索系统仍然存在一些缺陷或不足。 ( 1 ) 非个性化检索方式适应用户兴趣变化的能力较差。现有大部分信息检 索系统采用关键词输入方式进行检索，对任何用户都是一种模式，很容易让用 户感到迷茫，使得用户无法准确地表述自己的兴趣。 ( 2 ) 没有综合利用个性化检索和集中浏览的各自优点。现有信息检索系统 不是注重发展大范围信息检索系统，就是注重解决特定需求信息检索问题1 2 引。 ( 3 ) 缺少分布式智能信息检索和适应信息源信息变化的能力。 1 2 2 个性化信息检索 现实中，不同的用户由于背景知识、兴趣爱好等方面的差异，需要的信息 往往是不同的。特别是由于一些词存在多义性，这些不同领域的内容将混合呈现 在返回的结果中，从而大大耗费检索的时间，导致检索信息的效率低下。针对这 种问题，个性化的信息检索的概念由此提出。它首先收集用户信息，根据用户信 息对用户进行建模，进而在构建的用户模型的基础上提供个性化的检索，返回与 用户需求相关的检索结果。个性化信息检索系统在传统的信息检索模块当中增加 了个性化服务模块，增加的个性化体系结构通常包括四个层次，如图1 2 所示。 婀 产 反 馈 图1 2 个性化信息检索系统的体系结构 在个性化服务系统的体系结构中，用户信息收集模块是个性化服务系统的基 础模块。由于个性化服务是为用户量身定制的，因而无论是何种个性化服务，用 户信息的收集都是个性化服务的基础：个性化服务系统收集到用户信息以后，将 用户信息提交给用户建模模块进行处理。用户建模模块根据收集到的用户信息采 用用户建模方法构建用户兴趣模型；个性化服务模块将文档与用户兴趣模型进行 匹配，将匹配的文档推荐给用户。 个性化信息检索模型根据其所采用的技术可以分为两种：基于规则的系统和 信息过滤系统，信息过滤系统又可分为基于内容过滤的系统和协作过滤系统。 1 3 信息检索系统性能评价标准 查全率( r e c a l l ) 、查准率( p r e c i s i o n ) 和查找速度( s p e e d ) 是信息检索系统常用 的重要评价指标。当查询由用户递交给检索系统后，整个文档集在逻辑上划分为 四部分：检索到的相关文档、检索到的不相关文档、未检索到的相关文档、未检 索到的不相关文档。由此可以得到查准率和查询率的定义。 查准率= 检索到的相关文档数检索到的全部文档数 查全率= 检索到的相关文档数文献库全部相关文档数 查准率从一个方面描述了检索系统的查询开销，查全率是检索系统查找用户 所需信息能力的标志，速度是检索系统响应用户要求的时间度量。这三者相互制 约，对于检索系统而言，查准率随查全率的增加而减少，查询速度会随着查全率 的增加而减慢【2 5 1 。 1 4 本文研究内容 由于中文文本信息涉及到短语切分等技术难点，本文只针对英文文本信息进 行研究，着重研究了面向w e b 的信息检索算法。本文的主要工作包括以下几个方 面： 一、对大范围信息检索中的主要算法进行了比较深入的研究。分析、比较了 基于内容检索方法、基于超链分析检索方法和基于混合检索方法的优缺点，并对 代表性算法的实现过程做了细致地研究和分析；总结了提高检索性能的几个关键 因素。 二、分析了几种典型的个性化信息检索模型，对于用户兴趣和资源的描述， 用户信息的收集与更新，个性化推荐等关键性技术和算法进行了比较深入的学习 和研究，并总结了这些检索模型的优缺点。 三、针对检索中时常遇到的短查询式造成的查全率高查准率低的问题，本文 将查询扩展和文本分类技术融合辅助检索，提出了一种基于查询扩展和文本分类 相结合的信息检索算法。该算法引入了查询扩展和文本分类技术，不仅增加了短 查询式的信息，同时也避免了传统的查询扩展算法的时间复杂度过大缺点。实验 结果表明新算法提高了检索精度和时效，并有效地克服了传统查询扩展算法中 的查询漂移现象。 四、针对传统检索技术不能根据用户兴趣特点检索信息的问题，本文引入了 用户兴趣模型，并将内容过滤和文本分类方法相结合，提出一种基于内容过滤和 分类的个性化信息检索算法。该算法通过观察用户浏览文档的行为，采用机器学 习的方法不断地更新兴趣模型，从而使该兴趣模型越来越接近用户的真实兴趣； 同时，利用用户兴趣模型，算法采用内容过滤和文本分类的方法有效地检索用户 感兴趣的信息。实验结果表明，该算法具有较高的查准率和时效。 五、本文将提出的算法和技术相结合，实现了一个信息检索原型系统。 1 5 论文结构 全文分为五章，主要内容如下： 第一章概述了信息检索的研究背景、研究进展、现存的两大信息检索系统类 别，并介绍了本文所作的主要工作；第二章对两类信息检索系统中的主要信息检 索算法进行了总结，分析了基于内容检索、基于超链分析检索、混合检索以及基 6 于规则和基于信息过滤的个性化检索的优缺点，并对代表性算法的实现过程做了 细致地研究：第三章提出了基于查询扩展和分类的信息检索算法研究；第四章提 出了基于分类和内容过滤的个性化检索算法；第五章实现了一个信息检索的原型 系统；第六章总结全文，并展望未来的工作。 本文各章的联系与全文的结构如图1 2 所示。 图1 3 全文的结构图 7 第2 章信息检索模型及算法研究 随着互联网逐步成为获取信息的主要手段之一，相关网络信息的信息量与信 息复杂度也成倍增加。如何准确快捷地获取信息已成为人们非常关注的焦点。 本章对经典的信息检索模型以及主要的信息检索算法和技术进行了分析和 比较。首先详细地阐述了布尔模型、向量空间模型和概率模型的特点，其次针对 传统的信息检索方法如基于内容检索方法、基于超链分析的检索方法、混合的检 索方法做了分析和比较；再针对现有的个性化信息检索算法及其主要的检索模型 做了详细的分析并对其进行了总结。 2 1 经典信息检索模型 在信息检索引擎中，信息获取方式的优劣主要取决于信息模型的建立方法。 信息模型建立打法主要可咀分为三类：布尔模型、向量模型和概率模型。在布尔 模型中。文档和查询式都表示为特征项的集合，可以通过运用集合运算来进行检 索；在向量空间模型中，文档和查询式则表示为高维空问中的向量，可以通过对 于向量的代数运算进行检索；概率模型中。文档和查询式则是通过概率理论形式 化为概率分布，检索模型也建立在概率运算的基础之二。 2 1 1 布尔模型 布尔( b o o l e a l l ) 2 ”模型是基于集台论和布尔代数的一种简单检索模型。 在布尔检索中，要定义一个二值变量的集合，这些变量都对应文档的某个特 征，称为索引项。索引项一般是词或词组等简单的文本项，文档由这些索引项的 组合来表征和索引，如果该项对文档的内容表示有贡献，则赋值为l ，否则为0 。 查询式是索引项和操作符d 、o r 、n o t 组成的表达式。匹配函数遵循布尔逻辑的 原则，检索时根据用户查询和简单的布尔逻辑规则将文档划分为匹配集和非匹配 集。布尔模型的主要优点在于具有清楚和简单的形式，而主要缺陷在于完全匹配 会导致太多或者太少的结果文档被返回。 2 1 2 向量空间模型 向量空间模型【3 l ( c t o rs p a c em o d e l ) 由s a l t o n 等人于上世纪6 0 年代末提 出并成功地应用于s m a r t 口7 1 系统环境中。该模型主要是将文档看作由相互独立 的特征项组( r 。，r ：，。) 构成，对于每一特征项f 。，都根据其在文档中的重要程度 的特征项组( r 。，f ：，。) 构成，对于每一特征项f ：，都根据其在文档中的重要程度 赋以一定权值w l ，将( r 1 ，r ：，j 。) 看成一个挖维坐标系中的坐标轴，( w ，w ：，w 。) 为 对应的坐标值，从而转化为一个向量空间。文档映射成为空间中的一个点，从而 文档信息的匹配问题转化为向量空间中矢量匹配问题。特征项气在文档t 中的权 值通常由两部分计算获得：一部分是特征项七在文档d ，中出现的次数，即吮， 另一部分是整个文档集合中包含特征项t 的文档个数，即矾。直观上看，吮越 大，w 。值越大；同样匆越小，w 。值也越大，说明特征项更能代表文档d ，的 内容。在查询进行时，查询同样也要向量化。 向量空间模型突破了一般的布尔模型中索引项在文档中的权重及索引项和 文档的相似度都只能是o 或1 的局限，其权重和相似度是某个范围中的一个实数， 该模型可以将检出的文档按相似度的大小进行排序，让更相关的文档排在前面。 2 1 3 概率模型 在2 0 世纪6 0 年代m a r o n 和k l l h n s 提出了概率模型，该模型在i n q u e r y 【2 卅 系统环境中取得了较好的检索效果。富有代表性的模型是二值独立检索模型 ( b i r ) 。b i r 模型实现简单且检索效果好，它根据用户的查询d ，可以将所有 文档分为两类，一类与查询相关( 集合嚣) ，另一类与查询不相关( 夏) ，两者概率 分别表示为：p ( r l d ) 和p ( 瓦i d ) 。索引项的分布基于以下两条假设：( 1 ) 文档d 可以表示为d ( 一，x ：，j 。) ，其中二元随机变量表示索引项r ，是否在该文档中 出现，如果出现，则x ，= 1 ，否则x = o 。( 2 ) 索引项与索引项之间相互独立，任 意一个索引项的动作不会影响到其它索引项。 文档。与查询d 的相关度排序函数为： 跏( d ，q ) = 篇播 d 利用b a y s e 公式并经简化，文档与查询q 的相关函数可转换成一下形式： 跏( d ，q ) - 加g 刺 眨2 其中p = 衫，吁，= c ，：一哆移一，) ，表示训练文档集中文档总数，r 表示训练 文档集中与用户查询相关的文档数，表示在训练文档集中包含特征项i 的文档 数，表示r 个相关文档中包含特征项z 的文档数。 概率模型的主要优点是文档按照其相关概率的降序排列，其效率明显优于布 尔模型，但比向量空间模型略差口9 1 。其主要缺点是需要初始时将文档分为相关和 不相关的集合。 2 2 信息检索算法研究 确定了信息检索模型后，下一步的重要工作即是对信息进行加工处理，并选 择适当的算法进行检索。 2 2 1 传统的信息检索算法 现有的搜索引擎基本上使用的是传统的信息检索算法，它以尽量多的检索到 与用户要求相关的内容为根本任务，不考虑特定用户的特定检索需求，具有通用 性质。下面介绍几种主要的传统信息检索方法。 2 2 1 1 基于内容的检索 基于内容的检索方法主要是考虑用户提交的查询串在文档集中的出现情况， 包括特征项频率、特征项位置信息等等。代表性的方法有：基于特征项频率的检 索方法、基于特征项位置信息检索方法【3 。 1 ) 特征项频率的检索方法 向量空间模型是根据特征项频率进行检索的典型算法口 ，最初由s a l t o n 等人 提出并发展起来的。该模型主要是将给定的文本( 文章、查询串、或文章的一段 等) 看作由相互独立的特征项蛾，如，j 。) 构成，将“，f ：，。) 看成一个“维坐标系 中的坐标轴；对于每一特征项f ，都根据其在文档中的重要程度赋以一定的权值 w 。，( w ，w ：，u ) 对应为n 维坐标系中坐标值，于是该文计算档便映射为向量空 间中的一个点。特征项“在文档d 。中的权值w ，。通常由两部分计算获得：一部分 是特征项七在文档d 。中出现的次数，即如，另一部分是整个文档集合中包含特 征项t 的文档个数，即毵。具体的方法如下： w m2 矿； 碱2 矿；十( 1 0 9 2 ( n t ) 十1 )( 2 3 ) 其中，代表文档集合中的文档数量，代表在文档集合中出现特征项“的文 档数目。如越大，值越大：同样n 。越小，w 。值也越大，说明该特征项f 。更 能够代表文档d ，的内容。文档向量与查询向量的相似度通常采用余弦方法： 1 0 2 一w * + q 女 & m ( d 。，q ) = c o s 秽= 1 些一 ( 2 4 ) 1 f ( 喊) ( 吼2 ) y ；li = l 向量空间模型算法中，相似度值的大小反映了文档与用户查询要求的相关程 度，值越高则代表文档与用户的查询要求越相关。该算法简单有效，己得到广泛 的应用p “。但是它也存在着不足：1 ) 没有考虑各个特征项在文档中出现的位置。 比如处在标题或摘要中的特征项应该正文中的特征项对文档的主旨更接近；2 ) 没有涉及w 如文档检索中的文档链接信息，链接信息从某个角度上来说包含了 被链接w 曲文档的重要讯息，而利用向量空间模型检索w 曲文档则忽视了这些 信息。 2 ) 特征项位置信息检索方法 m i c h a lc u t l e r 算法是根据特征项位置信息，利用h t m l 文档结构和链接信 息进行检索的方法。该方法首先将h t 也标记分为六类：p l a i mt e x t ( 正文) 、 t i t l e ( 标题) 、h 1 一h 2 、h 3 一h 6 、s 仃( m g ( 包括强调、粗体、斜体、下划线) 、加l c h o r ( 链 接标记文本) ，并根据重要程度对每类赋以不同的重要度因子a 矿。特征项权值 的计算公式为： 形= 咿y 。c ，矿) + 缸矿( 2 5 ) 其中，开矿代表特征项频率向量，卯y = ( 咖。，咖：，痧，咖。，咖，咖。) ，分别 表示特征项f 在正文、s t r o n g 、h 3 h 6 、h 1 h 2 、标记以及标题中出现的次数。当 d 矿= ( 1 ，1 ，l ，1 ，0 ，1 ) 时，特征项r 的权值计算转变为向量空间模型的权值计算公式： 矿= 咿矿。a 矿) 渺= l + 咖2 + 咖3 + 咖4 + 咖6 ) f 矽= 矿够 ( 2 6 ) 该方法对于不同类别赋以了不同的重要度因子，因此有效地提高了检索质 量。但同时由于该方法在文档总数改变时，必须重新计算文档集中每一特征项的 权值，计算量大，不适用于文档的动态更新。 文献 1 6 】在m i c h a l c u t l e r 算法基础上提出了改进算法，根据特征项出现在不 同部分将一篇文档从逻辑上划分为个相对独立的文本段，有效地改善了检索 质量。 2 2 1 2 基于超链分析的检索 随着i n t e r n e t 的兴起，w e b 和信息检索的研究越来越受到人们的关注，信息 检索的对象从相对封闭、稳定一致、由独立数据库集中管理的信息内容扩展到开 放、动态、更新快、分布广泛、管理松散的w e b 内容。人们发现合理地利用超链 接信息对提高w 曲检索的精度和召回率起着重要的作用d0 1 。 1 ) p a g e r a n k 方法 p a g e r 孤k 算法由s e r g e yb m 和l a w r e r l c ep a g e 提出m 。对于描述同一个主题 的文档，人们总是喜欢先看重要( 权威) 的文档，再看次要( 不权威) 的文档。w w w 上的超文本文档相互之间的链接可以看成是引用，这种弓l 用关系体现出的文档的 重要性能够较好地符合人们主观意识中的文档的重要性。p a g e r a n k 算法就是基 于以上思想提出的：一个网页的质量和重要性可以通过其它网页对其超文本链接 的数量来衡量。页面重要性的计算公式如下： r ( 炉c ( r ) ( 2 7 ) v e 巩、 7 7 其中“代表一个w 如页面，f u 是“引用的页面集合，b 。是引用甜的页面集 合，c 是小于1 的常系数，用于保证所有网页排名值的总和保持为常量，。= e l ， 即“的出度。 为了克服因页面互相指向而造成迭代陷阱，引入衰退因子e ( 辩) ，e ( “) 对应 网页集的某一向量，对应r a i l l 【的初始值，算法改进如下： r ( “) = c r ? + 扭( “) ( 2 - 8 ) v e b 。 ，1 p a g e r a n k 算法分析页面之间通过超链接形成的链接关系，对每个页面计算 出一个重要度，以提高信息检索的质量。有研究表明，p a g e r a n k 算法计算效率 还可以得到很大地提高【3 2 】。 2 ) h l t s 算法 h l t s 算法由j o i l l lk l e i n b e 坞【8 l 提出。该算法为每个页面引入两个权值： a u t h o r i t y 权值和h u b 权值，最后分别输出一组具有最大a u t h o r i t y 权值的页面 而和一组具有最大h u b 权值的页面。a u t h o r i t y 页是相对某主题来说权威的网页， h u b 页是指向很多相对某主题来说权威网页的网页。算法的基本思想是：一个好 的h u b 页指向很多好的a u 吐1 州粤网页，同时，个好的a u t h o r 时网页也有很多 好的h u b 网页指向它。它们之间是一种环状的关系，相互增强。 算法的具体步骤：从搜索引擎中获取查询结果集，取排名最高的前，个网页 作为根集s ，然后根据这些网页的入链和出链进行前后一级扩展，构成一个更大 的基集t 。集合t 中每一成员都分别有两个值：a u t h o 衄值和h u b 值。算法首先 进行初始化，然后执行网页权重的迭代传递，即i 操作( h u b 到a u t i l o r i t v ) 和0 操作( 跏m o r i t y 到b u b ) ： 1 2 i 操作： o 操作 n ( “) = 厅( v ) 厅( “) = 口( v ) v 只 ( s i i x lx vn e e ) ( s o - 俐x vn 仨e ) ) ( 2 9 ) ( 2 1 0 ) 每次迭代后对口和& 缈进行规范化处理。式( 2 9 ) 反映了若一个网页由很多好的 h u b 页指向，则其权威值会相应增加；式但1 0 ) 反映了若一个网页指向许多好的 权威网页，则h u b 值也会相应增加。 与p a g e r 趾k 算法不同，h l t s 算法考虑了不同链接的重要性。但在实际应用 中，h i t s 算法中由s 生成t 的时间开销很昂贵，计算量比p a g e r a l l k 算法大： 在集合t 中如果有少数与查询主题无关的网页，但是两者又紧密链接，算法的检 索结果可能就是这些无关网页，从而发生主题漂移问题( t o p i cd r i f c ) 1 7 ，20 1 。 3 ) s a l s a 算法 s a l s a 算法由r l e m p e l 和s m o r a i l 提出【17 1 ，基于马儿可夫理论。算法的 原理为计算出链网页漫游中到达某个出链网页的概率和入链网页漫游中到达某 个入链网页的概率。再按概率从大到小的次序输出概率大的若干个h u b 网页和 a u t h o r i t y 网页。算法具体实现如下： ( 1 ) 和h i t s 算法的第一步相似，得到根集s 并且扩展为网页集合r ，除去孤 立节点： ( 2 ) 定义2 条马儿可夫链的变化矩阵，也是随机矩阵，分别为h u b 矩阵h ， a u t h o r i t ) r 矩阵a ； 删) = 。纛刚，始( f ) 七) i ( 2 1 1 ) 女：e b ) n b f n i 一， l 7 i 邯2 。蒹。、屉( f ) 驯 ( 2 1 2 ) 女e f ( j ) n f ( ，) r 、7 i l v 。7 i 其中b ( f ) 表示指向页面f 的所有其它页面，f ( f ) 表示从页面f 出发的所有其 它页面。 ( 3 ) 求出矩阵a ，h 的主特征向量， ( 4 ) a 中值大的对应的网页就是所要找的重要网页。 s a l s a 算法只考虑直接相邻的网页对自身h 的影响，没有h i t s 中相互 加强的迭代过程，计算