（通信与信息系统专业论文）web信息检索排序函数技术研究.pdf

内容提要 w e b 作为信息的发布与获取渠道给人们带来了巨大便利，与此同时，海量w e b 信息环境中人们获取有用信息的困难h 益凸现，即所谓的“信息爆炸”与“信息 湮没”现象并存。人们只能求助于w e b 信息检索工具搜索引擎来获取w e b 上的有用信息，然而实际效果却难以让人满意。 排序函数是信息检索系统的核心。排序函数以某种准则计算文档表示与用户 查询表示的匹配程度，并据此对文档排序，最终返回一个有序的文档列表作为检 索的结果。本文研究w e b 信息检索排序函数技术。 本文研究w e b 信息检索排序函数技术，研究的主要内容包括以下三方面： ( 1 ) 基于统计语言模型的信息检索方法及其在中文信息检索中的应用。首 先深入分析研究了信息检索中的各种统计语占模型，并做了统计语言模型和传统 概率检索模型的对比研究。重点研究了n - g r a m 模型在中文信息检索中的应用。 研究表明，利用一元语言模型，中文信息检索可以取得和目前主流检索算法相当 的性能，但是却略过了分词这一环节。最后，分析了统计语言模型的不足，提出 了改进的思想，指出w e b 环境中研究的重点为统计语占模型框架下w e b 文档结构 信息的表达。 ( 2 ) w e b 信息检索结构化排序函数及标引词加权技术。从w e b 文档内部结 构和外部结构两方面深入探讨了w e b 信息检索结构化排序函数技术，即基于超链 分析和基于w e b 文档内部结构的排序算法。指出了对提高w e b 检索性能有着重要 意义的数个文档结构( 标题、粗体、元数据、锚文本等) ，同时指出有效的w e b 检 索算法是结合文档内容、超链分析及文档结构信息的混合算法。 ( 3 ) 遗传算法在信息检索中的应用及基于遗传算法的排序函数设计框架。 最后，研究了遗传算法在查洵优化、w e b 结构化文档检索中的应用，深入分析了 遗传算法在信息检索应用中存在的问题，提出了下一步研究的方向。重点讨论了 基于遗传算法的排序函数设计框架，并对该框架进行了扩展。扩展之后该框架可 以表达更多信息，如除w e b 文档内容之外，还包括网页创建时间、网页的评价等 ( p a g e r a n k 值、r e p u p a t i o i l 值等) 。 关键词：信息检索、信息检索模型、排序函数、统计语占模型、文档结构、 超链分析、遗传算法、排序函数 a b s t r a c t w e ba sac h a n n e lo fi n f o r m a t i o np u b l i s h i n ga n da c c e s s i n gh a sp r o v i d e dp e o p l ew i t hg r e a t c o n v e n i e n c e ，a tt h em e a nt i m e ，t h ed i f f i c u l t i e st og e tu s e f u li n f o r m a t i o ni nt h ew 曲 e n v i r o n m e n th a sb e e nb e c o m i n gi n c r e a s i n g l ys e r i o u s w h i c hi st h es oc a l l e d i n f o r m a t i o ne x p l o s i o na n di n f o r m a t i o no b l i t e r a t i o np r o b l e m s p e o p l eh a v et ot u r nt o w 曲i n f o r m a t i o nr e t r i e v a l ( 1 r ) t o o l s ，s u c ha ss e a r c he n g i n e s ( s e s ) t og e tu s e f u l i n f o r m a t i o no nt h ew e b ，b u ts e a r c h i n ge x p e r i e n c e sh a sp r o v e ds e s p e r f o r m a n c ea r e u n s a t i s f a c t o r y e s s e n t i a l l y , t h ep e r f o r m a n c eo fa s ei sd e t e r m i n e db yr a n k i n gf u n c t i o ni ta d o p t e d a c c o r d i n gt oc e r t a i nr u l e s ar a n k i n gf u n c t i o nc a l c u l a t em a t c hd e g r e eo fa d o c u m e n t s r e p r e s e n t a t i o na n daq u e r y sr e p r e s e n t a t i o n ，t h e nd o c u m e n t sw e r es o r t e db a s e do nt h e v a l u eo ft h i sd e g r e e ，a n dao r d e r e dl i s to fr e l e v a n td o c u m e n t sw a sr e t u r n e da st h e r e t r i e v a lr e s u l t t h i st h e s i ss t u d i e sw e bi n f o r m a t i o nr e t r i e v a lr a n k i n gf u n c t i o n t e c h n o l o g y , i tm a i n l yc o v e r st h r e ea s p e c t s ： 1 s t a t i s t i c a ll a n g u a g em o d e l i n gb a s e d1 rm e t h o d sa n di t s a p p l i c a t i o n si n c h i n e s ei n f o r m a t i o nr e t r i e v a l c o m p a r i s o ns t u d i e sw e r em a d eb e t w e e nv a r i o u ss l m o d e l s ，e s p e c i a l l yt h en g r a mm o d e l si nc h i n e s ei r i te a r lb ec o n c l u d e dt h a t ，w o r d s e g m e n t a t i o np r o c e s sb e e ns k i p p e d ，c h i n e s ei ru s i n gu n i g r a mm o d e l sp e r f o r m e d c o m p a r a t i v e l yb e t t e ra st r a d i t i o n a lm e t h o d s t h ew e a k n e s so fs l md i s c u s s e da n d p o s s i b l ew a y so fi m p r o v e m e n ts u g g e s t e d 1 1 1 es t u d yo fs l mi nw e b i rs h o u l df o c u s o nh o wt or e p r e s e n tw e bd o c u m e n ts t r u c t u r a li n f o r m a t i o nu n d e rt h es l mf r a m e w o r k 2 w e bi rs t r u c t u r e dr a n k i n gf u n c t i o na n di n d e xt e r mw e i g h t i n gt e c h n o l o g i e s w e bi rm a i n l yd e a l sw i t hs t r u c t u r e dh t m ld o c u m e n t s t h i si st h em a i nd i f f e r e n c e s r e g a r d i n gt r a d i t i o n a li r ，a n dt h eu s i n go fd o c u m e n ts t r u c t u r a l i n f o r m a t i o ni sa e f f e c t i v em e a n st oi m p r o v ew e bl rp e r f o r m a n c e t h e r ea r et w ok i n d so fw e b d o c u m e n ts t r u c t u r e s n a m e l yi n t e r n a ls t r u c t u r ea n de x t e r n a ls t r u c t u r er e s p e c t i v e l y t h e f o r m e rr e f e r st ot h es t r u c t u r e sf o r m e db yh t m lt a g s ，t h el a t t e rm e a n st h eh y p e r l i n k s b e t w e e nw e b p a g e s a f t e rs t u d yo fw e b d o c u m e n ti n t e r n a ls t r u c t u r ea n a l y s i sb a s e di r m e t h o d sa n dh y p e r l i n ka n a l y s i sb a s e di rm e t h o d s ，w ep o i n to u tt h ee f f e c t i v ew 曲 r e t r i e v a la l g o r i t h m sa r ef u s i o no n e sc o m b i n i n gd o c u m e n tc o n t e n ta n ds t r u c t u r a l i n f o r m a t i o na n a l y s i s 3 u s i n go fg e n e t i ca l g o r i t h m s ( o a ) i ni ra n dt h eg ab a s e dr a n k i n gf u n c t i o n d e s i g nf r a m e w o r k t h ea p p l i c a t i o n so fg ai nq u e r yo p t i m i z a t i o na n dw e bs t r u c t u r e d d o c u m e n tr e t r i e v a lw e r es t u d i e d t h eg ab a s e dr a n k i n gf u n c t i o nd e s i g nf r a m e w o r k w a st h e ne x t e n d e dt oe n a b l ej tt or e p r e s e n tm o r ee l e m e n t so t h e rt h a nd o c u m e n t c o n t e n t ，s u c ha st i m eap a g ew a sc r e a t e d ，o n e sj u d g m e n to fw e bp a g e s ( p a g er a n k v a l u e ，r e p u t a t i o nv a l u e ，e t c ) k e yw o r d s ：i n f o r m a t i o nr e t r i e v a l ( i r ) ，i n f o r m a t i o nr e t r i e v a lm o d e l ，r a n k i n g f u n c t i o n ，s t a t i s t i c a ll a n g u a g em o d e l ( s l m ) ，d o c u m e n ts t r u c t u r e ， h y p e r - l i n ka n a l y s i s ，g e n e t i ca l g o r i t h m ( g a ) ，r a n k i n gf u n c t i o n d e s i g n 1 1 1 海南大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究工作所取 得的成果。除文中已经注明引用的内容外，本论文不含任何其他个人或集体已经发表或撰写 过的作品或成果。对本文的研究做出重要贡献的个人和集体，均己在文中以明确方式标明。 本声明的法律结果由本人承担。 论文储弛巷驴欠 日期：如严l 月，岁日 学位论文版权使用授权说明 本人完全了解海南大学关于收集、保存、使用学位论文的规定，即：学校有权保留并向 国家有关部门或机构送交论文的复印什和电子版，允许论文被查阅和借阅。本人授权海南大 学可以将本学位论文的全部或部分内容编入有天数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存和汇编本学位论文。本人在导师指导下完成的论文成果知识产权门属海 南大学。 保密论文在解密后遵守此规定。 论文作者签名：赵j 乞l 日期“口7 年“f 7 日 导师签名： 网 l 印耀 k 。二u _ 日期：岬年b 月f 7 日 本人已经认真阅读。c a l l s 高校学付论文全文数据库发布章程”，同意将本人的学位论 海南人学硕l 学位论文 1 引言 1 1 研究背景 过去的数十年中，信息检索理论与技术得到了很大的发展，并且已经超越了它标引 文档和在某一特定文档集合中检索文档的最仞日标。特别是随着网络越来越普及，并由 此形成了海量w e b 信息环境，这对信息检索提出了新的要求与挑战。基于经典信息检 索的理论与数据处理技术，在w e b 环境中判定w e b 文档与用户信息需求之间的匹配程 度，由此就形成了w e b 信息检索。 第十九次中国互联网络发展状况统计报告指出，中国网站总数己超过8 4 万个，网 页总数达到4 7 亿个，网页字节总数超过1 2 2 3 t b 。时至今日，它已经渗透于经济社 会生活的各个领域，成为人们工作、生活中不可或缺的一部分。w e b 作为信息的发布与 获取渠道给人们带来了巨大便利，与此同时，网络上的海量信息和人们获取有用信息之 间的矛盾日益凸现。人们越来越依赖于搜索引擎来获取互联网上的有用信息。 g o r d o n 等”1 研究指出，在经常使用的w e b 应用中搜索引擎仅次于电子邮件名列第 二。由于网络存在大量分散、冗余的信息，人们在搜索自己需要的信息时，需要花费大 量的时间等待或者判断，才能筛选出部分重要的信息，这其中包括多次修改查询式、浏 览很多返回的文档等。因此，w e b 信息检索成为了一个重要而又困难的问题和目前的研 究热点，有不少研究活动围绕如何提高搜索结果的精确度，或缩短用户找到重要网页资 源的时间而展开。 首先对信息检索系统( i n f o r m a t i o nr e t r i e v a ls y s t e m ，i r ) 与搜索引擎( s e a r c he n g i n e s e ) 两个术语进行区分。我们认为，搜索引擎是信息检索系统中的核心，它专注于对文 档的标引和文档与查询条件之问的相关性计算这两个在信息检索系统中最根本的部分。 而信息检索系统除了这两部分以外，还包括文档的收集、用户模型( 如用户背景、兴趣、 行为、风格) 的设计、查询条件扩展、查询结果反馈、人机交互界面等辅助功能模块昭3 。 一个搜索引擎是一个w e b 信息检索工具，目前主流搜索引擎都是商业化的，如g o o g l e ， 百度等。 搜索引擎的性能表现有诸多决定因素，如查询表达式的质量以及索引、词干提取、 无义词的停用、查询扩展等技术的应用等，但根本上它是山搜索引擎采取的排序函数决 定的。信息检索排序函数以某种准则计算文档表示与用户查询表示的匹配程度并据此做 出文档相对于用户信息需求的相关性判断，然后将文档按照相对于用户查询相关的程度 降序排列，最后返回该有序文档列表作为检索的结果。w e b 信息检索是网上信息获取的 重要手段。因此，研究w e b 信息检索排序函数技术、对其发展趋势进行探讨，是一个 既迫切又实用的研究课题。 本文主要研究w e b 信息检索排序函数技术。 w e b 信息柠索排序函数技术研究第一节引者 为了从技术角度更清晰的阐述上述问题，首先定义信息检索领域的若干基本概念， 如文档与文档表示、用户信息需求与用户查询表示、用户相关性与查询相关性，信息检 索系统的目的等，这些定义将为本论文其它章节做一个概念性的铺垫。 1 2 信息检索基本概念 】2 ，1 信息检索的定义 信息检索( i n f o r m a t i o n r e t r i e v a l ，i r ) 是以文档为处理对象，对文档数据进行表示、 存储、管理和查询的方法和技术。给定一批文档d 和用户信息需求( u s e ri n f o r m a t i o n n e e d ) q ，信息检索的目标就是快速而准确地找出满足用户信息需求q 的文档( 称这些 文档与q 相关) 。在大多数情况下，还需要根据相关程度对这些文档进行排序。 l ，2 2 信息检索中的相关性 各类文档和用户的信息需求表述通常是自然语言文本，但是自然语言很难使之很好 的结构化，且自然语言文本可能存在语义上的歧异。另一方面，信息检索系统存储的是 文档的某种表示( 通常采用标引词来编制索引) ，用户信息需求也转换为i r 系统能够处 理的查询表示( q u e r y ) ，因而信息检索系统并不是直接处理原始文档和原始用户信息需 求的，它所能够提供给我们的只是文档表示和查询表示之间的关系。正因为如此，m a r o n 和k u h n s l 4 1 首先指出，信息检索系统不能用来判定文档对用户信息需求的适用性，而是 用来预占文档对于查询表示的相关性，即文档与查询表示相关的概率大小。 。相关性”的概念是信息检索中的一个重要概念。由于相关性概念本身的复杂和主 观性，目前对相关性并没有一个统一的定义，这里不讨论相关性的多种定义，而是从信 息检索系统判定文档对于用户查询相关的概率大小这一角度，阐述文档与用户信息需 求，文档表示与查询表示之间的关系。对相关性的深入探讨请参考 5 ，6 。 一篇文档对于特定的用户信息需求是否有用称为文档与用户查询的相关性，简称为 用户相关性；信息检索系统将文档表示与查询表示相比较，通过某一匹配函数计算二者 的相似程度，被成为文档表示与查询表示的相关性，简称为查询相关性。用户相关性是 由文档内容和用户信息需求的意义决定的；而查询相关性程度的大小表示用户相关性概 率的大小。信息检索系统就是通过计算查询相关性来近似用户相关性，从而实现文档对 于用户查询的相关性判断。 基于对相关性属性的不同考虑，就可以设计不同的检索模型。如从对查询相关性的 判定出发，m a r o n 和k u h n s “。提出了第一个概率检索模型，其主要思想是计算文档按用 户查询被认为相关的概率。r o b e r t s o n 和s p a r c kj o n e s 建立了第二个概率检索模型”0 。， 其主要思想是计算用户判断一篇文档为相关的概率。后续的研究者也是基于对相关性属 性的不考虑而得到不同的检索模型。 1 2 3 杯引词加权技术 渤南人学硕j 。学位论文世证文 2 0 0 7 年4 门 要计算排序首先要明确如何给标引词加权，标引词加权技术的思想与聚类技术的基 本原理密切相关并涉及了著名的z i p f 定律和l u h n 的思想，请参考 7 ，第1 2 页。在聚 类中必须解决两个问题：首先需要明确哪些特征可用于描述类内的特征；其次明确哪些 特征能将不同类之日j 的对象区分丌来。第一个特征集用于类内相似度的计算，第二个特 征集用于类删相异度的判断。内部聚类相似度通过文档中标引词出现的频率度量，称为 ，厂因子( t e r mf r e q u e n c yf a c t o r ) ，用于描述标引词描述文档内容的好坏程度；类问相异度 用文档集合中包含标引词的文档数量衡量，称为i d f 因子( i n v e r s ed o c u m e n tf r e q u e n c y f a c t o r ) ，它说明在许多文档中都出现的标引词对于区分相关文档和不相关文档是没有作 用的，信息检索最有效的标引词加权方案总是试图平衡这两种效果。 基于上述思想，s a l t o n 和b u c k l e y 提出了著名的，厂一i d f 加权公式： r 0 5 f r p 口 、n w j ，= t f , ，x 硼= io 5 + 二ll 1 0 9 二， l i “a x ，j r e q , ，jj 啊 此外，他们在 8 中描述了以上加权方案的几个变形，可以满足多数文档集合加 权标引的需要。此外尚有2 一p o s s i o n 标引词加权方案，b m 2 5 排序函数中的r s j 加权方 案旧。等，关于标引词加权技术的更深入探讨，请参考 7 第二章：文档内容的自动分 析与自动标引。 在对文档进行标引时，我们按照标引词反映文档主题内容的程度设计一个权值附加 该标引词，标引词反映文档主题内容的程度越高，权值越大，反之越小。在加权标时， 标引词的权值取值范围可以是一个闭区间1 0 ，li 。这些词语的权值用于计算文档和 用户查询之i 日j 的相似度( d e g r e eo f s i m i l a r i t y ) 。 1 2 4 信息检索排序函数技术 在信息检索系统中，通常都采用一组标引词来标引和检索文档。一般来说，标引词 就是一组关键词，这些关键词可以是从文档的文本中直接提取的，也可以是人为指定的， 它们都提供了一种文档表示形式。标引词更一般的形式是在某一文档中出现的任何词， 即全文( f u l lt e x t ) 标引。显然，全文本是最完整的文档表示形式，但它在实现上需要付 出很高的时空代价。实际上通常采用文本操作( t e x to p e r a t i o n ) 技术对文档文本进行预 处理，并最终实现了文档表示形式从全文本到标引词( i n d e x i n gt e r m ) 集合的转变。 基于标引词的检索通常假设文档的语义和用户信息需求的语义可以用标引词的集 合来表示。但是事实并非如此：当我们用标引词集合来代替全文本的时候会造成语义的 丢失，信息检索系统再计算被表达成关键词集合的文档与用户信息需求的匹配程度，据 此检出的文档通常无法满足用户的信息需求。 信息检索的核心问题就是判断哪螳文档相关，哪些文档不相关。这通常取决于所采 用的排序算法，排序算法计算文档表示与用户查询的相似性，并根据该干l f 以性的值对文 档进行排序，处在排列最顶端的文档被认为最有可能相关。排序算法是信息检索系统的 ( w e b 信息榆索排序函数 主术研究第一节j 占 核心。 排序算法是根掘对文档相关性的定义来计算的，不同的一组关于文档相关性的定义 形成了不同的信息检索模型。如在向量模型中，假定如果表示文档的向量与表示查询的 向量相似，则称文档与用户信息需求相关。而向量之间的相似可以量化，如可以计算两 个向量夹角的余弦值。 这旱有必要区分两个概念：信息检索模型和信息检索排序函数。信息检索模型是对 信息检索任务和方法的一种数学抽象，它避开了对具体实现细节的描述，而主要从以下 两个方面抽象的研究信息检索问题： ( 1 ) 确定在模型中，如何表示检索的两个要素文档和查询； ( 2 ) 确定在模型中，如何定义和计算文档和查询问的关系。主要任务是定义并计算表 示任意文档的d d 与用户查询q q 的相似程度的排序函数r ( q ，d ) ，排序函 数又称为匹配函数、信息检索函数，该函数值的大小表示文档满足用户查询的 程度。 可以看出，信息检索模型研究的第二个方面就是信息检索排序函数技术。 接下来给出信息检索模型的形式化描述。 1 2 5 信息检索模型的形式化表示 给定批文档d = d i d l ，吐，4 ，以 及用户查询q 。我们将构成文档的基本项， 如文本文档的字、词语等称为索引项，表示为t = ，it l , i ：，t 。 。同理，将构成查询的基 本项统称为查询项。 信息检索模型是一个四元组 ，其中： d 是文档集合中文档的表示； 9 是用户信息需求的表示，称为查询； ，是种机制，用于对文档表示、查询及文档表示与查询表示之间的关系建模； 曰( 吼，d ，) 为排序函数，该函数输出一个与查询q ，q 和文档表示d d 有关的实数 值，这样就能相对于查询q 对集合中的文档确定一个顺序。详尽探讨请参考【7 】第一章情 报检索系统和文档1 1 0 1 第二章m o d e l i n g 。 关于文档相关性的不同假定构成了排序函数的基础，从而决定了信息检索模型。建 立一个信息检索模型，首先要考虑文档的表示与用广1 信息需求的表示形式。一旦这种表 示形式确定下来，我们就可以构思一个框架来对这种文档表示和查询之问的关系建模， 同时在该框架内设计信息检索排序函数。如在经典布尔模型中，这种框架由文档集合及 作用在集合上面的标准运算所组成；在经典向量模型，这种检索框架由，维向量空间和 作用在向量上的标准线性代数运算所组成，在向置审问模型的框架内，著名的夹角余弦 公式就是个排序函数【7 】；而在经典概率模型中，这种框架由集合、标准概率运算和贝 叶斯理论所组成，概率模型框架内著名的排序函数包括o k a p ib m 2 5 1 9 1 ，及其改进模型 海南人学硕j 学协论文 赵一文2 0 0 7 年4 几 b m 2 5 0 0 1 1 2 l 等。本论文第二章介绍上述三个信息检索经典模型。 论文后续章节，我们没有详细的指明每个模型的d ，q ，f ，r ( q ，d ，) 分量，这些分量可 以通过上下文准确的识别出来，我们也没有详细的区分信息检索模型和信息检索排序函 数两个概念，以上的分析已经明确的界定了它们的涵义及其侧重，在绝多数情况下，它 们是可以互换使用的，读者不会因此而产生理解上的错误。 1 ，3 论文组织 本论文如下组织：第一章阐明研究背景和信息检索的基本概念之后，第二章介绍信 息检索的三个经典模型，并对三个经典模型进行比较和讨论，然后是信息检索评价，主 要分为传统评价方法，t r e c 评价体系和其他评价方法。 第三章介绍信息检索模型的发展，从集合论模型、代数模型和概率模型三方面展开， 其中详细探讨了扩展布尔模型和统计语占模型在信息检索中的应用，讨论了统计语言模 型的分类及其评价，进行了统计语言模型与传统概率检索模型的比较，讨论了中文信息 检索的特点，介绍了统计语言模型在中文信息检索中的研究应用情况，最后是信息检索 模型的分类。 w e b 信息检索有着与传统信息检索不同的特点，第四章讨论了w e b 信息检索排序 函数技术，从基于超链分析的检索方法、基于文档结构的检索算法和基于融合的检索算 法三方面进行了讨论。 第五章为基于遗传算法的排序函数设计框架。首先是遗传算法简介并给出了基本遗 传算法的伪代码描述，接着讨论了遗传算法在信息检索中的应用，讨论分为遗传算法在 查询优化中的应用、遗传算法在排序函数设计和选择中的应用和遗传算法在结构化文档 检索中的应用三方面展开，最后讨论了目前遗传算法在信息检索应用中存在的不足、面 临的问题和叮能的解决方案与发展方向。 最后一章为总结和展望，归纳了论文的研究成果，指出了下一步要做的工作。 w e b 信息柠索排序函数拙术酬究 第一节 绎典信息拎索模型肚j 发腱 2 经典信息检索模型及其发展 信息检索的三个经典模型分别是柿尔模型，向量模型和概率模型。关于这部分内容 的详细讨论请参考【7 第四、血、七章和文档【1 0 】第二章。 2 1 信息检索三个经典模型 2 1 】布尔模型 最早建立起来的是布尔检索模型，用标引词的逻辑组合表达用户查询由此出发就形 成布尔检索理论。在传统的布尔检索系统中，文档的表示形式为一组标引词的集合，标 引词的权值都是二值的，即w ， o ，l l 。用户查询则是由一组标引词构成的布尔表达式， 整个检索策略依赖于一个倒排文档，查询结果为文档表示与布尔查询式准确匹配的文 档。检索结果因其只有两种可能( 相关或不相关) ，而无法进行相关性排序。 设布尔查询为：q = ( ， ，：) v ( 如 1 ，。) ，则布尔检索将检出被标引词，。和1 2 标引的所 有文档，以及被标引词，标引但没有被，。标引的所有文档。 布尔检索可以表达与用户思维习惯相一致的查询要求且运算简单易行，这是它的优 点；同时它也存在下述不足： ( 1 ) 检索输出完全依赖于布尔查询与文档的匹配，难以控制输出量的大小： ( 2 ) 由于其二值相关性假设不能对检索结果按照相对用户的重要性排序； ( 3 ) 同时对描述文档和查询式的标引词没有一种加权的方法，认为出现的标引词都具 有相同的重要性且不能处理部分匹配，包含n 一1 个查询关键词的文档和一个查 询关键词也没有包含的文档被认为是一样无用的等。 s a h o n 于6 0 年代提出的向量检索模型与r o b e r s t o n ，s p a r kj o n e s 等在7 0 年代先后提 出的概率检索模型部分解决了上述问题。这两种模型对文档和查询中的标引词赋以非二 值权重，通过计算文档相对于用户查询的相关程度实现了对部分匹配文档的检索，检索 结果有序输出，同时可以控制输出量的大小。下面分别介绍这两种模型。 2 1 2 向量模型 布尔模型所采用的二值权值( b i n a r yw e i g h t ) 存在缺陷，它不能解决文档与查询部 分匹配的问题，可以通过给文档和查询中的标引词分配非二值权值来克服这个缺陷。 向量检索模型最基本的前提就是将文档和查询用向量表示。设整个文档集共包含t 个标引词，文档d 和用户查询向量q 可表示为，维向量： q 2 ( w 1 ，q ，w 2 ，口，w ，q ) - 4 d 2 tw 1 ，1 j , - - - w ，j ， 这种对文档和查询的处理方式把检索问题转化为一个向量空问上的问题，这为计算 带来了很大的方便。向量模型通过向量d 和q 之h j 的相似性来评价文档d 和查询q 的相 似程度，一般用这两个向量之间央角的余弦值计算。即： 海南人学硕i j 学位论文 赵正立2 0 0 7 年4 门 “帅，2 端 w ，w ， 霄产再； h l 是文档集合中的一个标准化因子，| g l 并不影响排序的结果，故常常简化为 s i m ( d j ，g ) = t q = ，x w , ，。 j = 1 w ，0 ，w 。0 ，所以s i m ( d ，g ) 的取值在区间 o ，1 ，即使文档与查询仅部分匹配该 文档也可以被检出。 2 1 3 概率模型 经典的概率模型基于如下思想：根据用户的检索q 可以将d 中的所有文档分为两 类，一类与检索需求q 相关，这些文档形成集合r ；另一类与检索需求不相关，这类文 档形成集合面。在同一类文档中，各个索引项具有相同或相近的分布；而属于不同类的 文档中，索引项应具有不同的分布。因此，通过计算文档中所有索引项的分布，就可以 判定该文档与检索的相关度。 通常定义文档d 和查询q 的相似度为： s i m ( d j 埘= 黜， 其中条件概率p f r j d ，) 表示文档d ，和查询q 相关的概率，p ( r i d ，) 表示文档d j 和查 询q 不相关的概率。 根据贝叶斯定理，上式可化为： ，、p ( dl r ) p ( r ) s i r e ( d q ) = 一， 。“p ( d ，l r ) 尸( 月) 其中p ( d ，i r ) 表示从相关文档集中随机采样到文档d j 的概率，p ( 胄) 表示从整个文档 集合中随机选择的一篇文档为相关文档的概率。显然，对文档集合中的所有文档来说 尸( r ) 的值都是一样的。类似可定义概率尸( d 1 面) 与p ( 面) 。 对文档集合中的所有文档来说，p ( r ) 、p ( r ) 都是一样的，故可略去，即得： 州圳。黜 由于标引词的数日很大，因此常常在计算中引入一些假设以简化计算。基于对如何 估计概率p ( 41 月) 和p ( d1 面) 的不同假设，就形成了三种不同的概率模型，分别是：二 元独立模型( b i n a r yi n d e p e n d e n tm o d e l ) ，二元一阶依赖模型( b i n a r yf i r s to r d e rd e p e n d e n t w e b 信息柃索栅序函数技术研究 第一节 绛典信息榆索摸型发j 发摧 m o d e l ) 和双p o i s s o n 分御模型( t w op o i s s o n i n d e p e n d e n t m o d e l ) ，请参考 1 3jc 这里只 介绍二元独立模型。 假设标引词独立，在相关和不相关文档中的出现服从二元分御： p t a , 1 月) = ( 兀删圳j p ( t i 月) ) ( 兀f 伊p ( j ( ：i r ) ) p ( t l i ) = ( 兀。) - j p ( k ，i 豆) ) ( 兀引) ：。p ( j l ：i 豆) ) 贿c 桫牝案器嶙， 其中岛( t ) = w i ，为文档t 中标引词，的权值， o ，1 。式以t1 月) 表示随机从r 中选取一篇文档包含标引词女，的概率，p ( j f ：j r ) 表示随机从r 中选取一篇文档不包含标 引词t 的概率，其余概率值可类似定义。注意到尸( t 只) 十以i f 月) = 】，对上式取对数， 并略去对所有文档都为常数的因子，得： s 打”c 一，。，= ：妻。w ，【，。s 了兰；j i i , j ；奏i + 。s 三 ；等j _ i、 1 1 、，i 儿，1 、“，i 儿， 这时估计概率p ( kl r ) 及j p ( t 1 豆) 即可。 首先，在查询式产生之后，我们假设对所有标引词t 概率j p ( ti r ) 为常数( 如0 5 ) ， 同时用标引词在整个文档集合中的分布来近似j p ( t1 两，可以得到： 地= o 5 ，p ( k , i r ) = 专， 啊为包含标引词女，的文档个数，n 为文档集合中的文档总数；第二步设v 为初步检 出的文档集合，为v 的包含t ，的文档构成的子集，此时可用检出文档中k ，的分布来近 似p ( k ，ir ) ，认为所有未被检出的文档都是不相关的，即： p ( k , i 舻等川= 糟， 这个过程可以迭代的进行。在实际应用中对于v ，值可能很小的问题研究者提出 了各种数据平滑方法，在此不作详细介绍。基于概率检索理论的著名的b m 2 5 0 0 公式如 下，它是由r o b e r t s o n 和s p a r kj o n e s 提出的【l l 】： s i m ( d , q ，= 丢w 等貉等 其中，k = 毛( ( 】一6 ) + 6 考 ， k k 6 为经验值。其中矿和q 矿分别为查询项，在 文档d 和查询中出现的次数，d 和a v d 分别为文档长度和平均文档长度，通常以词或 词组作为单元来表示。w 就是奄 自j 项本身的权重，一般称作r o b e r t s o n s p a r kj o n e s ( r s j ) 权基陶f ，定义如下： 海南人。? 颂f j 学位论文 。：l 。q ! ! ! ! ：型墨二! 塑 。( 甩一r + 0 5 ) ( n 一胛一r + r + o 5 ) 是集合中文档总数，玎是出现该项的文档数，r 是与查询主题相关的文档数，是 相关文档中含有该标引词的文档数，通常因为缺少相关性信息，月和r 取值为0 ，则上 式简化为文档频率权重： w ：l o g 坐掣，这与矿一i d t 加权公式中i d 因子是基于同样的思想：一个词被 玎十u ) 越多的文档包含，这个词越不重要。 2 2 经典信息检索模型讨论 布尔模型的主要优点在于形式简洁、结构简单，可以用与用户思维习惯一致的方式 准确自然地表达用户需求。其主要不足之处在于严格的匹配可能导致检出的文档过多或 过少，检索结果只有两种可能( 相关或不相关) ，因此无法按照相关性进行排序，这通 常导致检索效率低下。清华光盘版全文检索管理系统采用了布尔检索策略。 向量模型认识到使用二元权值的局限性，它通过对查询和文档的加权标引构建了支 持部分匹配的桠架。向量模型利用这些权值来计算每个文档和用户查询的相似度，并通 过对检出文档按照相似度降序排列的方式束实现文档和查询的部分匹配，然后将相似度 大于给定闽值的文档作为检索结果( a n s w e rs e t ) 输出，这样用户只需要浏览排在列表前 面的若干文档，从而可以更好地满足了用户信息需求。 向量模型的不足表现在以下方面： ( 1 ) 标引词相互独立的假设与事实不符，标引词之问可能存在多种相关关系。 ( 2 ) 标引词的一词多义现象会严重破坏相关性测算的结果； ( 3 ) 计算量较大：每次查询时先将查询化为一个向量并计算余弦； ( 4 ) 倾向于给大文档赋以较高的相似度：因为它们包含更多的词，比小文档来说有更 大的a j 能命中，同时，它们经常使用重复的词从而词频矿值较大。 尽管向量模型具有上述不足，但它对一般集合而言+ 仍然具有很强的适应性，是当| j 应用最广泛的检索模型之一。 概率模型是以概率论为基础，运用概率统计学方法来挖掘信息特征，理解用户查询 语义的。概率模型是为了解决检索模型中的词的不确定性问题而发展的模型，有较强的 理论基础。同时返凹的文档按相关概率递减的原则排列可以方便用户浏览检索结果，提 高了检索效率。信息检索过程就是检索系统对用户信息需求逐步逼近的过程，实践表明， 相关反馈技术足提高枪索结果的有力技术。而基于b a y e s 概率的信度修正理论，不但为 该过程提供了理论支持，而且已经为此建市的大量的使用方法。 概率模型存住的主要问题是检索中尉带有午 | 关性标注的训练文档( 即相天性判断已 知的文档) 的依赖。因此，研究在没有棚天性已知的训练文档，或文档很少的情况f 如 w e b 信息榆索排序函数技术研究第节绎典信包榆案模型灶j c 发胜 何修币模型的参数，提供较好的检索结果，是基于概率模型的信息检索目前的一个主要 研究方向。各种形式的棚关反馈技术是解决该问题的基本方法之一。 概；棼模型是否优于向量模型，至今仍存在一些争论。通过大量的实验，s a l t o n 和 b u c k l e y 指出：对于一般集合，向量模型预期比概率模型的检索效果更佳。这种观点在 研究者中问占主流地位。 下表从诸多方面对三个经典模型作了比较： 表i 三个经典检索模型比较 按照g u d i v a d a 等的定义1 6 7 1 ，上述三个经典模型中，布尔模型中文档和查询用标引 词集合表示，称之为集合论( s e tt h e o r e t i c ) 模型；在向量模型中，文档和查询用，维空 b j 的向量来表示，称该模型为代数( a l g e b r a i c ) 模型；概率模型中用于构建文档和查询 模型的机制都是基于概率论的，称之为概率( p r o b a b i l i s t i c ) 模型。本论文中采用该定义 作为分类标准来研究经典信息检索模型的发展，下面分别讨论之。 2 3 集合论模型的发展 w a l l e r 和k r a f t 等。m 。首先提出了加权布尔检索模型应遵循的基本原则：1 9 8 3 年， s a l t o n 将向量空间模型与布尔检索模型融为一体，提出扩展布尔检索模型：1 7 3o g a w a 等提出了模糊集合模型。1 8 10 其中，扩展布尔模型在信息榆索理论研究中占有特殊重要 的地位，本节主要介绍扩展布尔检索模型。 s a l t o n 模型的出发点是用矢量方法来讨论布尔检索。设文档集d 中各文档仅由两个 标引词l i t ，标引，其权值范围是【0 ，l 】，则各文档均可由，f 2 所确定的二维平面上的点来 表示。如图1 所示。点爿( 】，o ) 与文档表示中，的权为l ，：的权为0 的所有文档相对应； 类似定义点口，c ，d ，0 。而对于更一般的情况，即文档表示中的权为d l ，：的权为吐的 文档，可以用d ( 吐，以) 柬表示。 海南人学硕l ：学位论立 越正丘2 0 0 7 年4 _ r j a ( 1 d 图1 文档仅由两个标引词标引时标引词确定的平面 对于由，f 2 构成的查询9 = ，v t ：，在图1 中只有a , b ，c 三点所代表的文档才是理想 的命中文档，而对d 点所代表的文档，可以如下计算它们与查询的相关程度：因为三点 月，b 。c 代表着理想的命中文档，因而当点d 与三点爿，b ，c 中任意一点越接近时，d 点 所代表的文档关于查询q 的十h 似程度就越大。另一方面，当d 与0 点的距离越来越大时， 那么，平均来说，d 点与三点爿，b ，c 就越来越接近。因而d 与0 的距离 l d d | = 如i 再而=