（计算机应用技术专业论文）email检索系统的设计与实现.pdf

复旦大学硕士学位论文摘要 摘要 2 0 世纪9 0 年代互联网的成功，对信息检索领域产生了巨大的变革。互联网 由于数据量庞大、广告、风格的多样化导致了网页检索的兴起。现在，信息检索 领域又面临一个同样巨大的挑战：找到一种高效的检索算法来处理复杂的企业内 部局域网信息。e m a i l 检索是企业检索领域的7 大关键开放问题之【1 。网页和文 本文件己经有比较成熟的技术。然而，e m a i l 检索，包括e m a i l 线索树的拓扑关系， e m a i l 结构( 主题，发信时间，发信人等) 的处理，e m a i l 对其回复e m a i l 的全部或 部分抄写等问题，都没有没行之有效的方法。t r e c2 0 0 5 年e m a i l 检索任务的第 一次提出，提供了研究和评测的平台。 作者在t r e c 平台下设计和实现了e m a i l 检索系统。从e m a i l 邮件本身的内 部结构，查询，训练问题等角度对e m a i l 检索进行了分析，提出了一系列需要解 决的问题，并使用命名实体识别方法和基于e m a i l 文档结构的方法来解决，定 程度上改进了检索的效率。 本文工作的主要贡献总结如下： 本文建立了e m a i l 信息检索系统，一个包含语料处理，查询处理，查询等功 能的系统，并且在t r e c 中得到实际应用。 本文从e m a i l 邮件本身的内部结构，查询，训练问题等角度对e m a i l 检索进 行了分析，提出了e m a i l 检索系统需要解决的问题和难点。 本文分析了e m a i l 的文档结构特征，给出了提取抄写部分的方法，并分析了 在各种检索模型中文档结构的应用效果。 本文提出了使用命名实体识别方法对查询作预处理并很好的运用于e m a i l 检 索领域，实验表明，改进是明显的。 关键字：e m a i l 检索，企业检索，命名实体识别 中图分类号：t p 3 9 1 复旦大学硕士学位论文 a b s t r a c t a b s t r a c t w i t ht h es u c c e s so fw w wi n1 9 9 0 s h u m o r o u sc h a n g e sh a v et a k e np l a c e b i g c h a l l e n g e sh a v eb r o u g h ti n t ot h ei n f o r m a t i o nr e t r i e v a lf i e l db yt h ei n t e r n e tb e c a u s eo f e n o r m o u ss c a l e ，f l u i dc o l l e c t i o nd e f i n i t i o n ，g r e a th e t e r o g e n e i t y ，u n f e t t e r e di n t e r l i n k i n g ， d e m o c r a t i cp u b l i s h i n g ，t h ep r e s e n c eo fa d v e r s a r i e sa n dm o s to fa l lt h ed i v e r s i t yo f p u r p o s e sf o rw h i c hw e bs e a r c hm a yb eu s e d n o w ，t h ei n f o r m a t i o nr e t r i e v a la r e ai s c o n f r o n t e dw i t hac h a l l e n g eo fs i m i l a r l yd a u n t i n gd i m e n s i o n s h o wt of i n de f f e c t i v e e n t e r p r i s es e a r c h i n gm e t h o d e m a i lr e t r i e v a li so n eo f t h e7b i gk e yo p e nq u e s t i o n so f e n t e r p r i s es e a r c h f i e l d 1 。t h e r ea r e m a t u r e t e c h n o l o g i e s f o r t h e w e bo r t e x tr e t r i e v a l h o w e v e r ，n oe f f e c t i v em e t h o d sh a v eb e e nf o u n df o rt h ee m a i lr e t r i e v a l ，c o n t a i n i n g t o p o l o g i c a lr e l a t i o n so fe m a i lt h r e a dt r e e ，e m a i ls t r u c t u r e ( s u b j e c t ，d a t e ，f r o me t c ) ， q u o t e dt e x t t r e c2 0 0 5i st h ef i r s ty e a rf o re m a i lr e t r i e v a lt r a c k ，w h i c hi sr e a l l y h e l p f u lf o rt h er e s e a r c ha n de v a l u a t i o n t h ea u t h o rf i n d sal o to fp r o b l e m sb a s e do nt h ea n a l y s i so fe m a i l s i n t r a - s t m c t u r e ，q u e r i e s ，a n dt r a i n i n gq u e r i e s t h e nw eu s en a m e de n t i t yr e c o g n i t i o n a n de m a i ls t r u c t u r et e c h n o l o g i e st os o l v et h ea b o v ep r o b l e m s g e n e r a l l y , t h i sp a p e rd i s c u s s e st h ef o l l o w i n gt h r e ea s p e c t s ： t h i sp a p e rb u i l d su pa ne m a i lr e t r i e v a ls y s t e m c o n t a i n i n gf u n c t i o n so fc o r p u s p r o c e s s i n g ，r e t r i e v a lp r o c e s s i n ga n dr e t r i e v a l ，a n da l s oh a v i n gg e t t i n gu s e di n t r e c t h i sp a p e rh a sa n a l y s e se m a i l si n t r a s t r u c t u r e ，q u e r i e s ，a n dt r a i n i n gq u e r i e s ，t h e n p r o p o s eas e to f p r o b l e m sa n d h a r dp o i n t s t h i sp a p e ra n a l y s e se m a i ls t r u c t u r ef e a t u r e s g i v et h em e t h o dt oe x t r a c tt h e q u o t e dt e x t ，t h e ns h o wt h ee f f e c t t h i sp a p e rp r o p o s e st h en a m e d e n t i t yr e c o g n i t i o nm e t h o df o rt h eq u e r yp r o c e s s e r a n di ti sr e a l l yh e l p f u lf o rt h ee m a i lr e t r i e v a lf i e l d k e y w o r d ：e m a i lr e t r i e v a l ，e n t e r p r i s es e a r c h ，n a m e de n t i t yr e c o g n i t i o n c h i n e s el i b r a r yc l a s s i f i c a t i o n ：t p 3 9 1 2 复旦大学硕士学位论文第1 章绪论 第1 章绪论 1 1 背景介绍 e m a i l 检索属于信息检索的范畴，是从一个e m a i l 库中检索到符合用户查询 的e m a i l 。e m a i l 检索不同于o u t l o o k 中的个人e m a i l 检索，其对象是企业内部互 联网中的e m a i l ，而不是个人邮件。其中包含的信息量大，涉及的内容广。 e m a i l 的检索不同于普通的网页检索，根本原因在于e m a i l 不同于普通的网 页，体现在：1 e m a i l 的结构不同于普通的网页，e m a i l 有主题、发件人、收件 人、抄送人、发信时间等结构；2 e m a i l 的长度通常很短。3 e m a i l 的拓扑关系 不同于普通的网页见得链入链出的关系 2 】。从而在检索的各个环节都有相应的 调整。 e m a i l 检索有很强的应用背景，可以用于企业内部信息挖掘。企业搜索引擎 一方面通过接口和企业内各信息系统相联结，有序地采集各信息系统中结构化 数据，按预定好的规则组合和展示。对企业中的邮件系统、文档系统、内部网 站和论坛中的非结构化数据进行采集和索引，最终可以形成企业层面全面的信 息整合共享，实现全面的企业信息监控和发现。本文研究的e m a i l 检索是企业 检索内部的部分。企业内部有很多涉及技术和商业的邮件往来，企业员工内部 每天会收到非常多的邮件，如果没有一个对企业内部所有邮件的检索平台，主 管或相关人员很难找到针对一个重要事件的来往邮件。 与e m a i l 检索很相似的是新闻组的检索。现在有很多针对不同兴趣团体的 讨论组，即新闻组，以邮件列表的形式存在，里面有其信息发布和成员讨论的 邮件往来。新闻组检索与e m a i l 检索的区别 2 在于：1 用户查询的意图不同。 新闻组常被用作知识库，搜索主要出于信息需求。然而，e m a i l 检索可以满足作 为导航工具，可以用来定位某个特定时间，或者发送人或特定关键词的邮件。2 内容不一样，e m a i l 检索的隐私方面的要求较高。3 熟悉程度不同。人们对自己 所有或有权限访问的e m a i l 库的熟悉度要远高于对新闻组的熟悉度。 复旦大学硕士学位论文第1 章绪论 1 2 研究现状与不足 1 2 1 信息检索的研究现状和趋势 信息检索的发展经过了几个阶段，第一阶段是以查全为主，以搜集更多的网 页数量为目标。然而，普通网络检索用户更关注的是精度。第二阶段，也就是1 9 9 6 年起，信息检索技术开始注重网页质量与相关性的结合，即精度的要求。这主要 是通过三种手段：一是对网上的超文本链接结构进行分析，如i n f o s e e k 和g o o g l e ； 二是对用户的点击行为进行分析，如d i r e c t l l i t ；三是与网站目录相结合。最新的趋 势则是检索的智能化( 包括个性化) ，垂直化检索系统等。现在信息检索关注包括 职能化检索，垂直化网络检索等。 智能化搜索，表现在三个方面： 第一，输入查询智能化，即以自然语言提问； 第二，输出结果智能化，在现有页面输出的结果之上，还能以分类、聚类、 摘要等智能处理过的格式输出； 第三，检索导航智能化，比如肖邦的相关提示最好是莫扎特，而不是刘邦。 以上功能的实现依赖于面向内容分析的自然语言处理技术和知识挖掘技术 的发展，而检索导航和结果输出的智能化方面，又依托于相关领域知识体系的建 立，即前文提到的领域或行业的元数据和目录资源体系，只有掌握行业或领域的 相关知识才能提供好智能服务，这给行业搜索引擎留下了优势空间。 垂直化网络检索系统是指用于搜索某一学科专业( 如搜索自然科学、军事、金融 经济) 或某一类信息( 如图像、影像) 并对其进行检索，有人称之为专题检索系统、 专门检索系统。t r e c 中提出的基因检索，法律文档检索，b l o g 检索，e m a i l 检索 等属于这个范畴。综合检索系统满足了用户全方位搜索信息的需求，但给那些专 注于某个专业或某一类信息搜索的用户带来诸多的不便，他们不得不花费大量的 时间与精力去进行信息筛选。又由于学科的纵深发展和新信息类型的出现，综合 检索系统显得力不从心；专指性强的垂直化检索系统正好能满足用户特定信息搜 索的需求，它建立的网页数据库较综合搜索引擎的小得多，搜索程序容易控制， 更新周期短，其检索精确度也更高。 1 2 2e m a i l 检索的研究现状与不足 互联网的发展推动了信息检索技术的发展和应用，文档的表现形式和规模都 4 复旦大学硕士学位论文第1 章绪论 发生了巨大的改变。文档的表现形式多种多样，有传统的网页，e m a i l ，b o l g ， 基因文献，法律文献等等，对于针对不同文档集的检索通常需要根据其表现形式 作不同的定制，这都属于结构化文档的范畴。结构化文档的方法主要如下： 信息检索的一个研究得比较充分的问题是寻找最合适的段来代表文档。早期 的研究是把文档分成长度相等的段；实验验证1 5 0 3 0 0 个词的段落比全文检索效 果更好【3 】。之后，又有两步式方法，第一步，在全文种检索得返回前n 个结果； 第二步，用段的方法对返回的结果列表作重排【4 】。固定窗口或者自然边界分割 的技术被证明有鲁棒性并且在文档检索尤其是长文档检索比较有效。把文章看成 一系列的集中话题，并且使用了自动分组的方法把小的段落合并成大的节段，这 种方法被证明比单纯的文档检索或段落检索性能有优【5 。推测段落边界和隐马 尔可夫模型的方法检索，也可改进检索性f l 6 1 。 随着网络的迅速发展，针对结构化网页的检索成了研究热点。e m b l e y 使用 启发式规则发现并记录网页内部边界并且从网页中提取相关段落 7 】。c h a k r a b a r t i 使用精化的主题提取和中心聚类方法研究了链接结构【8 】。c h e n 使用基于功能的 对象模型进行内容的理解和组织【9 】。g u 尝试了用网页内容组织文档对象模型树 ( d o m ) 并比较结构树中结点的相似度【1 0 】。上述工作分析研究了网页不同组成部 分的结构功能关系。 e m a i l 检索是结构化文档的一种，w e n s ix ie m a i l 对新闻组检索作了研究的 作者重要度，线索树拓扑结构，线索树上下文内容作了分析，得出线索树上下文 是比较有效的。 g m a i l 检索目前还没有被比较成熟有效的方法。难点在于要解决e m a i l 线索 间的联系，线索树中e m a i l 对之前的e m a i l 的部分或全部引用，附件的出现，e m a i l 邮件的结构( 主题，发件人，收件人等) 1 】。 1 3 论文结构 第一章是绪论介绍当前e m a i l 检索的研究现状及难点。 第二章阐述了e m a i l 检索领域的基本概念。 第三章详述了e m a i l 检索系统的设计与实现。先跟据查询和语料分析e m a i l 检索的特点及需考虑的因素，并给出了相应解决方案。包括命名实体识别和文档 结构信息的应用。 第四章对介绍了t r e c 中的e m a i l 检索项目及相关实验。 第五章是总结和展望。 复旦大学硕士学位论文 第2 章e m a i l 检索的相关概念和项目 第2 章e m a i l 检索的相关概念和项目 2 1 信息检索模型 目前信息检索主要有两大类的方法，基于语言学和人工智能的方法( 即理性 主义) 以及基于语料库和统计语言模型的新方法( 即经验主义) 。目前得到广泛 应用的是基于语料库和统计语言模型的方法，而基于语言学和人工智能的“理性 主义”方法一般结合到“经验主义”方法之中【1 1 。 6 0 年代中期以来，人们提出了大量检索模型。自最初的为一些较小的和较 为结构化的文档所设计的特殊模型( 如文献记录，包括题目、作者和主题码等) ， 发展到现在具有较强理论基础和能处理多种文档格式的模型。当前的模型能够处 理具有复杂内部结构的文档，并且一般都具有学习和利用相关反馈进行查询优化 等功能，使得系统性能大大提高。 常用的信息检索模型主要有三种： 严格匹配模型。它是许多商业信息检索系统的理论基础。 概率模型。把检索看作是文档表示和查询之间匹配程度的概率估计问题。 向量空间模型。把文档和查询看作是多维向量空间中的向量，用距离作为 相似度的度量。 信息检索模型用被称为索引项的关键词来表示一篇文档。索引项可以是字、 词或词组。将一篇文档表示成了一批索引项的集合后，我们就会发现不同的索引 项对描述这篇文档所起的作用是不一样的。通常我们认为如果一个词在每篇文档 都出现，那么它对描述文档起不到任何作用；如果个词只在很少的文档中出现， 那么这个词就能显著缩小我们需要检索的空间，即它对描述这篇文档能起到很大 作用。这就引出了权重的概念。 令k i 表示一个索引项，a j 表示一个文档，w i ，j 0 表示索引项k i 在文档a j 中的 权重。权重w j 量化了项k i 对描述文档d j 所起到的作用。 定义：令t 表示文档集里所有不同索引项的数目，k i 表示一个索引项。k = f k l ， k 2 ，k t 表示索引项构成的集合。 对于文档d j 中有的索引项k i ，权重w o 。对于文档d j 中没有的索引项k i ，权重w i = o 。 这样我们就可以将文档d j 表示成一个向量西= ( “l j ，w 2 ，w l j ) 。向量d ，的第i 维就对 应丁二项k 在文档d j 中的权重。 6 复旦大学硕士学位论文第2 章e m a i l 检索的相关概念和项目 2 1 1 严格匹配模型 严格匹配模型( e x a c tm a t c hm o d e l ) 是给定一个查询，利用匹配函数，将文 档集分为两个集合：匹配集和非匹配集。在匹配的文档子集中文档一般不在匹配 程度上进行排序。当然可以根据文档日期、字母顺序或其他属性来排序。严格匹 配模型中最简单而且具有代表性的便是布尔模型。 布尔检索模型是基于集合理论和布尔代数的一种最简单的检索模型。在布尔 检索模型中项k i 在文档d i 中的权重w i ，i 0 ，1 ) ，即权重是二值的。如果项k i 出现在文档d i 中，则w i ，f _ l ；如果k i 未出现在文档d j 中，则w i ，i _ 0 。在布尔检 索模型中查询被表示成了布尔表达式。如用户要检索美国军事预算方面的文档， 查询就表示为“美国a n d 军事a n d 预算”。布尔检索模型中文档和查询相似度是 二值的，s i m ( d j ，q ) o ，1 ，即文档要么是相关的，要么是无关的。 布尔检索模型在六、七十年代得到了较大发展，也出现了许多可以应用的商 业系统，比如d i a l o g ，s t a i r s ，m e d l a r s 等。其主要优点是定义清晰，使 用简单，速度快。缺点是文档是很不精确的，不能反映出特征变量对文档表示的 重要程度；相关性判断太单一：要么是0 ，要么是1 ，而没有介于0 和1 之间的 值。这样就无法对检出的文档进行排序( 因为检出的文档相关度都是1 ) ，使更 相关的文档排在前面。 针对布尔模型的缺点，研究者们提出了各种各样的方法，如根据命中关键词 的词频排序、支持部分匹配等等。推广的一个结果是e x t e n d e d 布尔模型以及 p - n o r m 模型；推广的另一个结果是向量空间模型。需要指出的是，现今的大部 分商业搜索引擎仍然采用了布尔模型的主要思想。 2 1 2 概率模型 概率检索模型是通过概率的方法将查询和文本联系起来。最经典的概率检索 模型是由英国伦敦城市大学的r o b e r t s o n 和剑桥大学的s p a r c kj o n e s 提出的二 值独立检索模型( b i n a r yi n d e p e n d e n c er e t r i e v a l ，b i r ) 。它主要通过计算查 询词中每个标引项和文本的相关概率来计算整个查询和文本的概率。b i r 模型的 关键问题是对其中各参数的估计，r o b e r t s o n 和s p a r c kj o n e s 利用伪相关反馈 技术来计算模型的参数，从而最终实现检索。概率模型和向量空间模型在测试中 表现出的性能不相上下，很难说哪种模型就比另一种模型优越。另外，概率检索 中的相似度计算公式也融入了不少向量空间模型的思想，比如文本长度的引入。 最著名的概率检索原型系统是伦敦城市大学的o k a p i 系统。其他的概率检索模型 7 复且大学硕士学位论文 第2 章e m a i l 检索的相关概念和项目 还包括基于神经网络的概率模型、基于语言学模型的检索模型。后者9 0 年代中 期由麻省大学( u m a s s ) 提出，已经引起了广泛的关注。c m u 实现的原型系统l e m u r ( 同时实现了多种检索模型) 已经支持基于语言学模型的检索模型。 2 1 _ 2 1二值独立检索模型 对应于用户提出了的查询，有一个由相关文档构成的集合( 这个集合由哪些 文档构成事先并不知道) ，我们把这个集合称为理想答案集合，记为r 。如果我 们知道r 的特征，就可以找到所有的相关文档，排除所有的无关文档。因此， 我们可以把查询看成是一个寻找r 的特征的过程。问题在于我们在第一次查询 时并不知道r 的特征，我们只能去估计r 的特征来进行查询。第一次查询完成 后，我们可以让用户判断一下检索到的文档哪些是相关文档( 通常只要求用户判 断排在最前面的若干篇，如前十篇) ，根据用户的判断，我们可以更精确地估计 r 的特征。通过如下图所示的迭代过程，我们对r 的估计越来越准确，检索性能 也会越来越好。 3 i r 要估计文档d 。与查询q 相关的概率p ( riq ，“) ，其基本假设是项( 文 档由表示概念的项构成) 在相关和不相关的文档中的分布是不同的。设t = ( k 。 k 2 一k m ) 表示文档集中项的集合，文档“可以被表示为一个二值向量x = ( x 。 x 2 x n ) 。这里项k 出现在文档d 。中则x i = l ，否则x i = 0 。 上面将文档“表示成了二值向量x ，计算p ( rq ，d m ) 就变成了计算p ( r q ，x ) 。 在计算p ( rq ，x ) 之前，先介绍两个公式： ( 1 ) b a y e s 公式p ( ab ) = p ( ba ) p ( a ) p ( b ) ( 2 ) 有利条件o o ) = p ( y ) ，p ( 豳) _ p ( y ) 1 p ( y ) 计算二值向量x 表示的文档和查询q k 的有利条件为： o ( r lq ，x ) ：业! ：旦幽坐! 堡：塑 4 。p ( r f g ，z ) p ( r 叮) p f r ，叮) 做独立性假设，由公式( 2 3 ) 可得 公式2 1 公式2 2 公式2 3 复旦大学硕士学位论文第2 章e m a i l 检索的相关概念和项目 。( r q , x ) = o ( r i q ) 冉剩筹 公舰。 该公式表示x 出现在查询q 的相关文档集和非相关文档集的概率的比率等于 单个项的相应概率的比率的乘积。b i r 模型中的这种独立性假设一般是不成立 的，但它可以看作为较好的近似。 由公式( 2 4 ) ，可将公式( 2 3 ) 变为 吧i 脚帅r ，疆揣骢揣 公虮s 记p i k = p ( x 。= 1 i r ，q ) ，q i ，k = p ( x ，= 1 l r ，q ) ，并在做第一次检索时假设所 有在查询中未出现的项p i ，k = q i ，k ( 这种假设也是为了简化) ，于是得到 o ( ri ) - o 川r q兀尝兀器_0(rq。l-i,ttedmtnqt i a g d m i k。筹焉兀t i e q 啬q mj q“e 口q * 1 一，* j1 一q m 公式2 6 因为o ( rq ) g l - i ；二争不影响文档按相关程度的排序，我们可以忽略这两 项。对剩下部分取对数，我们就得到文档d 。的检索状态值( r s v ) r s v = 。_ c ，其中c m2 l 。g 丽p , k ( 1 - - q f k )公式27tt a mc nq 1 m 、-r ， 在第一次查询时，因为没有任何先验知识，我们估计p ，k 和q m 的最初值。 以后根据对查询结果的相关反馈，对p i ，k 和q 眦值进行修正。 二值独立检索模型的优点是：它的公式推导有理论基础，而且文档是按照相 关的概率降序排列的。 其缺点是： ( 1 ) 最初估计项在相关文档出现的概率是没有任何先验知识的，很可能与 实际情况出入很大； ( 2 ) 文档的表示模型十分粗糙，其权重是二值的，没有考虑项在文档中出 现的频率。 2 1 _ 2 2 o k a p i 算法 b m 2 5 权重计算公式是由英国伦敦城市大学r o b e r t s o n 等在t r e e 一3 会议上提 出并被应用于著名的基于概率检索模型设计o k a p i 系统；在t r e c 评测会议中得 到了广泛的应用，该权重计算公式在概率模型中已经成为公认的成熟的标准计算 方法。 9 复旦大学硕士学位论文 第2 章e m a i l 检索的相关概念和项目 对于一个给定的查询q = f t l ，t 2 ，t n ) ，文档的评分值由以下公式计算： y 。 堕! ! ! 盔：! 。! 坠! ! ：五! 公式2 8 智。“( 1 +b-b) 。鲁 + 厶， 也+ ， 嘲 “( 1 + 生 + 厶， 3 吖 l 口曙 其中： w t 是查询中每个特征项的权重。：i 。g j ! ! 堕业坚二! ! ! ：! l 公式2 9 一，+ 0 5 ) ( j 一n r + ，+ 0 - 5 ) n 是语料集中的文档数； n 是含有特征项t 的文档数； r 是与查询相关的文档数； r 是相关文档中含有项t 的文档数； f “是某一文档中项t 的出现频数； f 。是项在查询q 中的出现频数： l d 是文档长度； l 。是语料集中文档的平均长度： k - ，b ，k 。是参数，k 与b 默认取值分别为1 2 和0 7 5 ；k 。一般被设置为7 或者 1 0 0 0 ( 此时公式( 2 8 ) 的第一部分可以简化为厶，。) 。 2 1 _ 2 3 语言模型 生成语言模型 1 2 】，是基于概率的模型，是一种生成文字的概率机制。这种 模型可以用来合成人工文本，最初被c l a u d es h a n n o n 发明，用于猜测、模拟人类 语言 1 3 1 。 然而和经典的概率模型区别很大。经典的概率模型是估计文档和给定查询的 相似的概率；生成语言模型，按文档能产生特定查询的概率来排序。该模型定义 了语料库中所有词的一种多维概率分布。对查询中的每一个词，都计算从该文档 产生这个查询词的概率，这种概率，作为词的生成概率；把查询项中每个词的生 成概率累乘，就是文档d 可以生成查询q 的概率。，文档依据这些词生成查询的 概率来计分从而排序 1 4 。 p ( q i d ) = p ( q io 。) = 兀p ( w l o o ) 公式2 1 0 其中，q 是查询( 由一系列涮、衣q 不- - ) d 是文档 0 是语言模型 w 查询q 中的项w 0 。是文档d 的文档表示模型 复旦大学硕士学位论文 第2 章b m a i l 检索的相关概念和项目 语言模型运用到信息检索领域的一个很重要的改进是平滑算法。目标是估计 p ( wd ) 。最简单的方法是最大似然估计，用相关频数来计算。 以w 旧2 端 馘2 1 1 但是，最大似然估计常常会低估了在文档中未出现词的概率。而平滑的目的 在于对未出现词赋非零概率，并从而从整体上改善词概率的估算准确性。 现有的平滑方法很多，主要是用于语音识别领域 1 5 】通常，所有的平滑 方法都是消减出现词的概率，并对未出现词的概率提供补偿。对于信息检索，平 滑是非常必要且普遍的，使用了基于语料的办法来做处理。如我们假设平滑模型 的统一形式为 咖旧- f 兹如黝篇 公北，z 其中，p a w i d ) 是文档中出现词的平滑后概率，p ( w i c ) 是语料的语言模 型，是系数，控制未出现词概率，并且保证所有概率和为1 。 平滑方法的本质不同在于如何定义且( wd ) ，平滑方法既可以是简单地对频 数加一个数值( 附加，即l a p l a c e 平滑) ，也可以是复杂的如k a t z 平滑 1 6 】。对不 同的词频数作不同处理。检索领域最常用的三种平滑方法是。 1 j e l i n e k - m e r c e r 方法 使用线性插值和最大似然模型。 p i d ) = ( 1 2 ) p ，( w l d ) + 2 p ( w c ) 公式2 1 3 这属于简单的混合模型。 2 d i r i c h l e t 方法 使用d i r i c h l e t 先验的贝叶斯定理。对多项式分布的语言模型，进行贝叶斯分 析，使用的是d i r i c h l e t 分布的参数。( k t p ( w 1c ) ，p p ( w 2c ) ，p ( jc ) ) 咖2 笔器 公越 l a p l a c e 方法就属于这种方法的一个特例。 3 a b s o l u t ed i s c o u n t i n g 这种方法的通过对出现词的概率减去一个常量来降低出现词的概率 1 7 。这 和j e l i n e k - m e r c e r 访法有类似之处。只不过j e l i n e k m e r c e r 是通过乘以( 1 九) 来降 复日大学硕士学位论文 第2 章e m a i l 检索的相关概念和项目 低出现词的概翠。 p ；( w | d ) = 旦翌至；警+ 仃p ( w i c ) 公式2 1 5 其中j o ，1 1 是折扣常量； 仃= 巧i d l 。l d i ，可以确保概率和为1 ： l di 。是文档d 中出现的不同项的个数。 i d l 是文档d 中出现的长度，从而有id 。c ( w ；d ) 2 1 3 向量空间模型 向量空问模型( v e c t o rs p a c em o d e l ，v s m ) 是6 0 年代末由g e r a r ds a l t o n 等人提出的。其中最为著名的应用该模型的检索系统是s m a r t 系统。 与布尔检索类似，向量空间模型对所有文档以及用户的查询都用同一组特征 集合，即项集t = ( t l ，t 2 ，恤) 来索引。在简单布尔查询模型中，项的权重以及查 询和文档的相似度都只能是0 或1 ，致使无法对文档的相似度进行排序，而向量 空间检索模型则突破了这一点，每个项t k 在用来表示文档d i 时被赋予一定的权 重w i k ，以表征( 的重要程度，即d i 被表示为n 维向量d i = ( w i l ，w i 2 ，w i n ) ， 其中若t k 在d i 中不出现时w i k = 0 。同样，查询q 也用n 维向量表示为 q = ( w q l ，w q 2 ，w q k ，w q n ) ，其中w q k 表示项t k 在q 中的权重a 图2 4 文档的向量空间模型( v s m ) 及文档问的相似度s i m ( 口，历) 检索时根据向量内积： s i m ( d l ，d 2 ) = w l + w 2 女 公式2 1 6 = 1 或向量之间的夹角余弦： 复旦大学硕士学位论文 第2 章e m a i l 检索的相关概念和项目 “m ( 咖) 2 蒜3 w i ，jx w w f f 2 f f 2 1 ，蝥1 ，蛩9 公式2 1 7 来求出向量间的相似度，以度量文档d i 对查询q 的满足程度然后根据给定的门 限s 。( 或文档数m ) 选出相似度超过s o 的文档( 或相似度最大的m 个文档) 作为检索结果。必要时可通过相关反馈技术进行查询优化，或修正d i 的索引， 使输出结果更能满足用户的需要。 公式( 2 1 7 ) 中i d j l 和i9 1 分别表示向量d j 和g 的模。因为1g l 不会影响到排 序，因而它对所有的文档都是一样的。因子ld jl 提供了一种归一化的方法，以避 免长文档总是被检出。 因为w i _ i 三0 ，w i c o ，所以s i m ( q ，d i ) 0 ，l 】。这样向量空间检索模型不仅 可以用来判定个文档是否和查询相关，而且可将文档按相关度从大到小顺序进 行排序，然后按用户指定的数目返回相关度最大的若干篇文档。即使是一篇文档 只是部分地匹配了查询，它依然有被检出的机会。 当把检索看成一个分类问题时，假设现在有一个文档集c ，和一个对相关文 档r 的模糊描述( 查询) 。我们要把文档集c 分成两个部分，一个部分是相关文 档的集合r ，另一个是无关文档的集合r 。分类问题主要要解决两个问题：一个 是怎样选择能够更好地描述对象的特征；另一个是怎样选择能够更好地把一个对 象和其它对象区分开来的特征。也就是既要认清内涵，也要认清外延。内涵特征 量化了类内的相似度，外延特征量化了类间的区分度。一个成功的分类方法要注 意做到相似度和区分度的平衡，做到类内相似度大，类间区分明显。 在向量空间模型中，类内的相似度用项k i 在文档d j 中出现的频数来量化。 项在文档中出现的频数通常被称为t f 因子，它提供了用来衡量一个项在多大程 度上描述了一篇文档的标准。假设一个项k i 在文档集里的n 篇文档中出现了， 则我们可以用n 的倒数来衡量类间的区分度，通常我们把n 的倒数称为反比文 档频数或称为i d f 因子。项t i 的i d f 越大，则它区分文档的能力越强。和一个好的 聚类算法一样，一个有效的赋权策略要平衡好t f 和i d f 这两个因子的效果。 向量空间检索模型的主要优点在于它把文档和查询本身简化为项及其权重 集合的向量表示，把对文档内容和查询要求的处理简化为向量空间中向量的运 算，而权重的计算又可以通过统计的办法自动完成，使问题的繁杂性大为降低。 它的缺点是丢掉了大量的文本结构信息( 如文本句子中词序的信息) ，降低了语义 的准确性。 复旦大学硕士学位论文第2 章e m a i l 检索的相关概念和项目 2 2 检索性能的评价 人们使用检索系统来找到自己所需要的信息，自然会希望：( 1 ) 找到的信息 全是自己所需要的( 准) ；( 2 ) 自己所需要的信息全部被找到了( 全) 。这就引出 了衡量检索性能的两个最基本的指标：精度( p r e c i s i o n ) 和召回率( r e c a l l ) 。下面 从精度和召回率开始，介绍评价检索性能的若干的重要指标。 2 2 1 精度和召回率 要评测一个检索性能，就必须知道相关文档集r 到底有哪些文档。最为常 用的是p o o l i n g 技术。 要确切地得到所有的相关文档，最好的方法当然是由专家去仔细阅读文档集 里的所有文档，判断文档是否相关。但在大语料集里( 如t r e c l lw e b t r a c k 语 料集有一百多万篇文档，超过一百亿的字节) ，由人去看所有的文档显然是不现 实的。一种常用的变通做法就是把不同检索系统的返回结果前若干篇( 如前1 0 0 篇) 文档的并集提交给专家进行人工评价。假如总共有2 0 个系统，取前1 0 0 篇， 那么每个查询需专家评测的文档就介于1 0 0 和2 0 * 1 0 0 之间，这就大大减少了需 要评测的文档的数量。这种方法被称为p o o l i n g 。虽然不能说p o o l i n g 是准确的， 有可能有些未被评测的文档也是相关文档；但至少p o o l i n g 是公平的，它没有偏 袒任何一个系统。而且p o o l i n g 也得到了业界的广泛认可。 得到相关文档集r 后，我们就可以把r 和检出文档集a 做比较。 召回率的定义：召回率是检出的相关文档占总的相关文档的比例。 精度的定义：精度是检出的相关文档占检出的文档的比例。 jj 根据( 图表1 ) ，p r e c i s i o n2 i 品，r e 伽盯= 三a u c r e l e v a n tn o tr e l e v a n t r e t r ie v e dab n o tr e t r ie v e dc d 图表1 召回率精度示意图 用召回率和精度这两个指标来衡量检索性能，是假设用户会看所有的检出文 档。而实际上检出文档是按相关度从高到低排列的，用户是先看排在前面的文档， 1 4 复旦大学硕士学位论文第2 章e m a i ! 检索的相关概念和项目 而且用户往往不看排在后面的( 如1 0 0 名以后) 文档。因此，捡出文档的排序是 非常重要的。一个能把相关文档排在前面的系统能更好地为用户找到所需要的文 档，节省用户的时间。 为了充分体现排序的重要性，人们提出了用召回率一精度图、平均精度、 r p r e c i s i o n 等一系列的指标。另外有些情况下用户只对检出的前n 篇文档感兴 趣，我们用p n ( 如p 1 0 ，p 2 0 ，p 1 0 0 等) 来衡量前n 篇检出文档中相关 文档占的百分比。 2 2 2 召回率精度图 召回率精度图用来说明在r e c a l l 由0 ，1 0 ，2 0 ，一直到1 0 0 时， p r e c i s i o n 的变化情况。下面用一个例子来说明召回率精度图。假设对于一个查 询q ，某个检索系统返回了1 0 0 0 篇文档，按相关度从大到小排列，这一千篇文 档分别是d l ，d 2 ，d 1 0 0 0 。再假设这个查询的相关文档集r q = d l ，d 5 ，d 9 ，d i s ， d 3 9 ，d 4 4 ，d 5 6 ，d t l ，d 8 9 ，d 1 2 3 ，民共有1 0 篇文档。 用户看第一篇文档d 1 时，d l 是相关文档，此时r e c a l l = l 1 0 ，p r e c i s i o n = l 1 用户看第二篇文档d 2 时，d 2 是无关文档，此时r e c a l l = l 1 0 ，p r e c i s i o n = 1 2 用户看第三篇文档d 3 时，d 3 是无关文档，此时r e c a l l = 1 1 0 ，p r e c i s i o n = 1 3 把上面各点用直线段连起来我们就可以绘制召回率一精度图( 表格1 ) 。它是 一个二维图，横坐标是r e c a l l ，纵坐标是p r e c i s i o n ，它反映了在不同r e c a l l 下 p r e c i s i o n 的变化情况。 复旦大学硕士学位论文 第2 章e m a i l 检索的相关概念和项目 下面我们讨论如何使用召回率一精度图来比较两个检索系统的性能孰优孰 劣。假设这两个检索系统的召回率一精度图分别为( 图表2 ) 的实线和虚线所示： 比较这两个系统的原则是哪条曲线更偏向右上方，则哪个检索性能更好。从 图中可以看出a 的性能明显优于b ，但假如a 和b 的两条线交织在一起，比较 就没那么直观了。 召回率精度图和平均精度都是强调了排序的重点，一个系统要在这两个指 标上取得好成绩，不但要尽量找到相关文档，而且要尽可能地把相关文档排在前 面。 2 2 3 精度的其他变体 p n 是指在前n 篇文档中的相关文档数除以n ，即前n 篇文档里的精度。 这里的n 是一个常数，常用的有p 1 0 ，p 5 0 ，p 1 0 0 等。 r - p r e c i s i o n 是指前r 篇检出文档中的相关文档数除以r ，即在前r 篇文档 的精度。这里的r 是文档集里的所有相关文档数。 m a p ( m e a n a v e r a g ep r e c i s i o n ) 。a p ( a v e r a g ep r e c i s i o n ) 是对每个检索出文档 的精度的平均值，是就文档而言；m a p 是每个查询检索出文档列表的a p 值平 均，是对查询丽言。 i v l r r ( m e a nr e c i p r o c a lr a n k ) ，平排名倒数，是正确答案在检索结果列表中 排名的倒数的平均，主要是评测检索的精度。 2 2 4 召回率的其他变体 s n ，s i i l f 分别是正确答案在参与方e m a i l 检索结果列表中的前n 名和所 有结果出现与否的平均；这两个指标主要用来评价召回率。这两项指标常作为已 1 6 复旦大学硕士学位论文第2 章e m a i l 检索的相关概念和项目 知项查找任务的评价指标。如t r e c 中的w e b 任务的主页查找任务和浏览任务 e m a i l 检索任务中的已知项查找任务。 复旦人学硕士学位论