（计算机应用技术专业论文）中文信息检索系统研究.pdf

硕士学位论文m a s t e r st h e s i s摘要随着互联网和信息技术的发展，w 曲搜索技术在人们的日常生活和学习中发挥着越来越重要的作用。如何在海量数据中准确快速的搜索到有用信息，成为现代信息检索技术的主要研究内容。而信息检索的主要困难，一方面来自于用户难以准确地表达自己的查询请求，有效地和信息检索系统交互；另一方面，来自于信息检索系统很难对文档集进行整理加工。本文综合考虑了这两方面的内容，提出了查询扩展和文档扩展相结合的中文信息检索系统。本文的主要工作包括以下方面：第一，对已有查询扩展技术在中文信息检索中的有效性分析的基础上，提出了一种基于w e b 资源查询扩展策略。该策略自动从互联网上下载网页，并对其进行分析并从中提取相关术语群用于进行查询扩展。相对传统扩展方法利用人工构建的静态语义资源进行扩展，该策略可以根据w e b 资源自动的构建语义资源，具有更好的时效性和实用性。第二，利用文档集内部的信息，提出基于文本聚类的文档扩展方法。该方法首先得到单个文档与查询之间的相似度；然后将前n 篇文档聚类，再次计算类别与查询之间的相似度，并将它赋给该类别中的每一个文档：最后，将这两个相似度线性组合起来，得到了每个文档与查询之问最终的相似度，并以此重排结果集。第三，将这两种方法结合起来，形成了查询扩展和文档扩展相结合的中文信息检索系统。在n t c i r 一6 中文信息检索测试集上进行的实验表明，相对于传统的信息检索技术，本文的方法在检索精度上取得了一定的提高。关键词：信息检索；查询扩展；文档扩展；相关术语群a b s t r a c ta l o n gw i mt h ed e v e l o p m e i l to fm eh i t e m e ta i l dh l f o r m a t i o nt e c t m o l o g y w e br e t r i e v a lt e c h n o l o g yi sp l a y i n ga ni n d i s p e n s a b l er 0 1 ei np e o p l e sl i f ea n ds t u d y h o wt oa c q u i r eu s e f u li n f o 肿a t i o ne 伍c i e n t l yh a sb e c o m et h em a j o rc o n t e n ti nw e br e t n e v a lt e c h n o l o g y t w oa s p e c t so fd i 伍c u l t yw ea r ei nf a c eo f 主ni n f o 咖a t i o nr e t r i e v a la r e ，n a m e ly ，h o wu s e r sa c c u r a t e l ye x p r e s sq u e r yr e q u e s t sa n de f r e c t i v e l yi n t e r a c tw i t ht h ei n f o 咖a t i o nr e t r i e v a ls y s t e m ，a sw e l la st h ec o n s e q u e n c eo ft h es y s t e mi t s e l fo r d e r i n gt h ed o c u m e n t s t h i sp a p e rc o m p r e h e n s i v e l ya 1 1 a l y z e st h et 、oa s p e c t sa n ds h o w sac o m b i n a t i o no ft h e mv i ao p t i m i z i n gt h eq u e r ya n dt h ed o c u m e n t s t u d i e si nt h et h e s i sm a i n l yi n c l u d e ：( 1 ) t h i sp a p e ra n a l y s i st h ee f f e c t i v e n e s so fs e v e r a lc a t e g o r i e so fq u e r ye x p a n s i o nu s i n gt e m le x p a n s i o no rt e 册r e - w e i 曲t e da n dp r o p o s e san o v e lm e t h o db yu s i n gw e b 七a s e dr e s o u r c e sf o ru s e rq u e r ye x p a n s i o n i nt h i sm e t h o d ，w ed o w n l o a dp a g e s 矗o mt h ei n t e m e t ，t h e na n a l y z et h ep a g e sa n de x t r a c tr e l e v a n tt e r n l sg r o u pt oe x p a n dt h eu s e rq u e 哆c o m p a r e dw i t ht 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 du s i n gp r e c o n s t r u c ts t a t i ct h e s a u r i ，o u rm e t h o dc a na u t o m a t i c a l l yc o n s t r u c tt h es e m a n t i cr e s o u r c e sa c c o r d i n gt ow e bi n f o m l a t i o n 0 u rm e t h o dh a sl e s sc o n s t r a i n tb u th i g h e re 伍c i e n c y ( 2 ) w ew a n tt oc o n s i d e rt h ec o n t e x to ft h ew h o l ed o c u m e n tc o l l e c t i o na n dp r o p o s ead o c u m e n te x p a n s i o nb a s e do nc l u s t e r i n g f i r s t ，w er e t n e v ed o c u m e n t sb yt r a d i t i o n a lm e t h o da n dg e tt h es i m i l a r i t yb e t w e e nq u e 叫a n dd o c u m e n t ；s e c o n d ，w ec l u s t e rt h et o p nd o c u m e n t s ，a n dc a l c u l a t et h es i m i l a f i t i e sb e t w e e nq u e 巧a n dc l u s t e r s ；l a s t ，w ec o m b i n et h et w os i m i l a r i t i e sa sm e6 n a ls i m i l a r i t i e sb e t w e e nq u e r ya n de v e r yd o c u m e n t ，a n dr e r a n k i n gt h er e s u l ts e t ( 3 ) t h ec o m b i n a t i o no fq u e r ye x p a n s i o nb a s e do nr e l a t e dt e n ng r o u pa n dd o c u m e n te x p a n s i o nb a s e do nc l u s t e r i n gi sp r o p o s e di nt h i sp a p e r e x p e r i m e n t so nn t c i r 一5a n dn t c i r 一6c l i rs e ts h o wm a to u rm e t h o da c k e v e sac e r t a i ni m p r o v e m e n tc o m p 撕n gw j n lt h et r a d i t i o n a lm e t h o d k e yw o r d s ：i n f o m l a t i o nr e t r i e v e ，q u e 巧e x p a n s i o n ，d o c u m e n te x p a n s i o n ，r e l a t e dt e mg r o u p硕士学位论文m a s t e r st h e s i s华中师范大学学位论文原创性声明和使用授权说明原创性声明本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进行研究工作所取得的研究成果。除文中已经标明引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在文中以明确方式标明。本声明的法律结果由本人承担。作者签名：磊互日期：潲年厂月夕日学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有权保留并向国家有关部门或机构送交论文的复印件和电予版，允许论文被查阅和借阅。本人授权华中师范大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。同时授权中国科学技术信息研究所将本学位论文收录到中国学位论文全文数据库，并通过网络向社会公众提供信息服务。作者签名：芳互日期：如和年莎月汐日本人已经认真阅读“c a l i s 高校学位论文全文数据库发布章程”，同意将本人的学位论文提交“c a l i s 高校学位论文全文数据库”中全文发布，并可按“章程”中的规定享受相关权益。回重途塞握童厘溢卮! 旦堂生；旦二生；旦三生筮壶!作者签名：专互日期脚年月妙日歹4 峭1 巧午名“弛州师期导日硕士学位论文m a s t e r st h e s i s第1 章引言1 1 研究目的、意义及研究背景随着互联网的普及和社会信息化的发展，信息呈指数级增长，h l t e m e t 越来越成为人们搜寻各方面信息的主要来源，信息检索技术也在人们的日常生活和学习中发挥着无可替代的重要作用。信息检索是一个具有丰富内涵和广泛外延的术语，虽然没有统一的定义，但已经被人们所广为使用。综合一些现有的定义，可以对其作如下简单描述：“信息检索，是指从大量文档资源集合中自动地找到与用户查询请求相关的各种信息。”虽然该定义不是十分精确，但是却说明了信息检索所具备的特点。用户在检索信息时，通常把其需要用查询词的形式表达出来，检索系统根据查询词返回可能的相关文档。但随着互联网上信息的急剧膨胀，为用户提供海量信息的同时，也带来了大量的噪声，用户已经无法忍受大量的无关信息淹没了自己所需要的信息，快速即时地处理大量信息，提高信息检索系统的准确率，势在必行。因此，大规模和高精度成为现代信息检索技术研究的两个重要方向。目前的通用互联网搜索引擎，比如g o 0 9 1 e ，百度等，与早期的搜索引擎相比，虽然在速度上有了很大的发展，基本能够满足大部分的需求，可是在检索质量上仍存在不少问题。影响一个检索系统性能的因素包括：文档和查询条件的表示方法、评价文档和查询相关性的匹配策略、查询结果的排序方法和用户进行相关反馈的机制等。这些因素的根源均来自于自然语言的模糊性和复杂性。当用户提交查询来表达信息需求时，往往提交仅含有一个或者两个和用户需求主题相关的术语，这样，由于提交查询时使用的词不尽规范和完整，与文档索引使用的词或词组有很大差别，给准确的信息检索带来不便。尽管目前众多搜索引擎提供短文( s n i p p e t ) ，但是这种短文只是关键词的上下文，并不总能准确的反映用户的需求。同时，另一种互联网搜索引擎，不仅仅着眼于用户提交的查询与文档之间的相似性，而是进一步考虑了文档集合中各网页之问的联系，我们称之为垂直搜索引擎。垂直搜索大多是针对某一个行业的专业搜索引擎，是通用搜索引擎的细分和延伸，是对网页库中的某类专门的信息进行一次整合，定向分字段抽取出需要的数据进行处理后再以某种形式返回给用户。垂直搜索引擎是相对通用搜索引擎的信息量大、查询不准确、深度不够等提出来的新的搜索引擎服务模式，通过针对某一特定领域、某一特定人群或某一特定需求提供的有一定价值的信息和相关服务。其特点就是硕士学位论文m a s t e r st h e s i s“专、精、深”，且具有行业色彩，相比较通用搜索引擎的海量信息无序化，垂直搜索引擎则显得更加专注、具体和深入。垂直搜索引擎具有广阔的市场前景，目前知名的有雅虎、酷讯等等。垂直搜索引擎性能的好坏，很大程度上取决于系统对信息的整合分类，与通用搜索引擎相比，需要花费更多的代价来进行资源重组工作。信息检索的主要困难，一方面来自于用户如何准确地表达自己的查询请求，有效地和信息检索系统交互；另一方面，来自于信息检索系统本身对文档的有序化。这两方面的内容，可以通过对查询和文档的优化来实现。在计算机技术发展的初期，由于系统的运算能力有限，价格昂贵并且可靠性差，信息检索系统不大可能提供优化的方式。随着计算机性能的提高，系统能够用一部分资源来处理查询和文档优化的问题，因此也成为信息检索中的一个研究热点。1 2 查询扩展和文档扩展国内外研究现状对于如何提高信息检索系统精确率，关键的因素是信息检索模型，经过相关研究人员近半个世纪的努力，一些有效的信息检索模型陆续提出并应用到相关的系统中。其中影响比较大的检索模型包括：布尔模型、向量空问模型、概率模型以及语言模型等。而作为对向量空问模型的一种扩展，潜在语义索引模型提供一种基于主题的检索方法，由于词与词之间的相互依存性被纳入考虑范围，查询与文档之间即使没有相同的词，也极有可能会非常的相关。随着信息检索技术的不断发展，挖掘更加有效的信息对检索的结果进行优化成为一种有效的手段。f o x ，n u n n ，l e e 曾经提出：有效的将各方面的附加信息融合进信息检索的过程将带来更好的检索效果。该假设在实践中得到了不断证实。1 9 6 0 年，m a r o n 和k u h n s 在其发表的文章中提出了用高度相关的词语来扩展用户查询。在1 9 6 5 年，r o c c h i o 应用s m a n 系统【2 j 为测试平台研究了在向量空间模型中把查询扩展和词语重新加权相结合的经典技术，并在随后出版发行【3 1 。i d e 【4 】继承了r o c c h i o 的研究，并提出了词语重新加权公式的变形。1 9 7 8 年，h a 巾e r 和v a n 砌j s b e 唱e n 【5 】使用基于最大生成树的词语一词语聚类技术来选择词语进行概率查询扩展。两年后，他们又提出了一种新的相关加权方案，称为e m m ，用于查询扩展技术。1 9 8 1 年w u 和s a l t o n 【6 j 使用相关反馈来给从相关文档中提取出来的词语( 用概率公式) 重新加权，并用这些词语来扩展查询。实验表明了这些方法能够提高检索的性能。关于自动查询扩展，l e s k 【7 】在s m a r t 系统中尝试使用了词语一词语聚类的变形，但并没有得出比较好的实验结果。之后，s p a r c kj o n e s 和b a r b 一引，m i l l l ( e r ，、聃l s o n 和z i m m e m l a i l l 9 j 也发现了基于词语一词语全局聚2硕士学位论文m a s t e r st h e s l s类的查询扩展并没有提高检索的性能。这些早期的研究结果给人们留下了这样的印象，即基于全局聚类的查询扩展并没有提高检索的性能。这些早期的研究结果给人们留下了这样的印象，即基于全局分析的查询扩展技术并不是一种很有效的技术。然而，最近的研究结果表明情况并非如此。事实上，v o r h e e s ，c r o u c h 和y 抽g ，q i u& f r e i l lo j 的研究成果表明，基于全局分析技术的查询扩展确实能够提高检索的精度。关于通过局部聚类的查询扩展的讨论是基于a t t a r 和f r a e n l ( e l 【1 1 】从1 9 7 7 年来所作的工作，局部上下文分析的思想是最近才由x u 和c r 0 r 在1 9 9 6 年提出的【1 2 】，而对使用全局相似性叙词表来进行查询扩展的讨论是基于q i u 和f r e i 的文章【1 3 】。最后使用全局统计叙词表来扩展查询的讨论是基于c r o u c h 和y a n g 的文章【1 4 】，它主要受s a l t o n 、y a n g 和y u 提出的词语分辨值理论的影响。目前流行的查询优化技术主要有相关反馈( r e l e v a l l c ef e e d b a c k ) 、伪相关反馈( p s e u d of e e d b a c k ) ，伪相关反馈是在相关反馈( r e l e v a n c ef e e d b a c k ) 的基础上发展起来的。相关反馈机制由用户对检索出的文档进行相关性判定，系统根据这些判定生成新的查询，从而提高最终结果的准确率。伪相关反馈不需要与用户交互，它将初次查询的前n 篇文档自动认为是相关文档，以此为依据对查询进行扩展。提到相关反馈，由于其效果显著，在信息检索方面的应用和研究比较多，r o c c h i o 在1 9 7 1 年就提出了一种用反馈来改进查询的效果的方法，这种方法就可以同时实现查询的扩充和缩减，其他的很多方法都由此扩展而来。典型的有i d e 的i d er e g u l a r 方法，i d ed e c 小i 方法等。查询扩展仅仅是查询优化的一个手段，为了达到优化查询的目的，不仅可以扩展查询，还可以消除或削弱查询中不相关的词。相关反馈技术是信息检索中的查询优化的一个非常重要的机制。相关反馈方法通过增加或削减检索到的关键词的权重，一步一步地修正关键词的权重来达到修正查询的目的，以提高检索的效果。随着自然语言处理技术的发展，越来越多的方法被应用到信息检索领域中，文档扩展就是其中之一。文档扩展的实质，即通过文本分类，将来自同一总体的对象划分成两个或更多的类别概念，按照文档的结构、内容等信息，把相似的文档整合到一起。所以文档扩展技术的雏形，正是文本分类的基本方法，如决策树分类模型、最大熵模型、k 最邻近算法等等。另外，文本聚类方法也是实现文档扩展的重要途径之一。如果把每个文档当作一个节点，对所有节点进行聚类的过程，也就可以看作是文档扩展的过程。因此，将文本分类和聚类的相关技术，用到信息检索领域中，对查询文档进行预处理时，就是本文提到的文档扩展方法。1 9 9 4 年c sb u c k l e v ，g e r a r ds a l t o n ，硕士学位论文m a s t e r st h e s i sj a m e sa l l a j l 【1 5 】等人利用文档集本身的信息，提出了一种多特征融合的扩展技术。1 9 9 5 年j 锄e sa l l 一】进一步发现，一般的查询扩展方法很容易将一些不相关的术语加入到原始查询中，造成信息的冗余，因此在他的论文中提出了将整篇文档当作扩展单元，在有足够多相关文档支持的情况下，进行文档扩展，可以使信息检索系统的效率得到较大的提升。k y u n g s 0 0 nl e e ，y 0 u n g c h a np a r k 和k e y s u nc h o i 【1 7 】等人在他们2 0 0 0 年发表的论文当中，直接提出了将首次检索后的文档集聚类，再利用获得的类别信息对结果集进行重排的方法。随后j a r o s l a wb a l i n s k i 和c z e s l a wd a n i l o w i c z 也使用了类似的方法。g u n h a np a r k ，y u n j ub a e k 和h e u n g k y ul e e 【1 9 】将这一方法运用到图像检索方面，也获得了比较好的效果。国内方面，北大方正集团有限公司提出了一种“基于文档扩展的单文档摘要方法”，充分利用了相似文档之间的信息冗余性来改进现有的单文档自动摘要方法，并于2 0 0 6 年0 9 月0 1 日申请专利( 专利号：2 0 0 6 1 0 1 1 2 7 8 8 ) 。1 3 论文研究内容及本文工作近年来，查询扩展技术日益成熟。其中，伪相关反馈方法得到的结果常被作为基线用来衡量检索系统的优劣。而基于词典的查询扩展方法更是研究的热点，人们常通过h o w n e t 、w o r d n e t 、词林、互连网上的海量语料等已有资源进行词典构建，进而进行查询的扩展。在t r e c 等各种比赛中，这种方法都显示出了很强的活力，大多数参赛队伍都发现该方法能较大的提高信息检索的结果质量。另一方面，各式各样的重排算法逐渐成为信息检索系统的核心组成部分，而文档扩展也在其中占据了重要的位置。特别是对专业领域的查询任务而言，更加准确、更加细化的查询要求使得信息检索系统必须了解文档集本身的特性，才能得到较好的结果。本文中的主要的工作是，一方面利用机器自动构建的相关术语群来进行查询扩展，另一方面，通过对首次检索的结果聚类，来实现文档扩展，进而重排结果集。我们采用本文所使用的查询扩展和文档扩展相结合的方法，参加了n t c 瓜6 ，在其中文信息检索测试集上进行的实验表明，相对于一般的方法，查询扩展和文档扩展相结合的方法在检索效果上取得了一定程度的提高。1 4 论文内容安排本文各章安排如下：第一章是绪论，概述了查询扩展和文档扩展的意义和应用背景，介绍了国内外研究现状。4硕士学位论文m a s t e r st h e s l s第二章介绍了基于内容的文本信息检索的背景、基本原理、评价方法以及各种典型的文本信息检索模型。第三章分析了通过查询扩展和词语重新加权来改进原查询的各种方法，并提出了一种使用自动构建的相关术语群进行中文查询扩展的方法，给出了实验结果分析。第四章总结了前面的查询扩展方法的局限性，提出了本文的方法：查询扩展和文档扩展相结合的中文信息检索。第五章是系统设计和实验部分，首先描述了系统的框架结构和具体实现，并给出新的实验结果。最后一章给出了本文所有中文文本信息检索相关研究工作的总结。硕士学位论文m a s t e r st h e s l s第2 章相关理论与关键技术2 1 信息检索背景随着社会的不断进步，特别是在互联网迅猛发展的今天，信息生活在人们的日常生活中占据了越来越重要的地位。面对i n t e r n e t 海量的信息，如何对其进行过滤，从而提取出对自己真正有用的内容，成为目前亟待解决的问题之一。早在4 0 0 0 年前，人们就开始使用图书目录，方便快速查找大量的书籍。当面对更大规模的数据量时，传统的目录已经远远不能满足人们的需求，于是出现了专门的数据结构来存放目录信息，并逐渐的出现了索引的概念。电子计算机出现之后，索引即可通过指向相关信息或文档的指针来实现。索引是每个现代信息检索系统的核心，它们提供了数据的快速查询处理任务的速度。自从1 9 4 8 年c n m o o e r s 在其m i t 的硕士论文中第一次创造了“i n f o r m a t i o nr e t r i e v a l ”这个术语以来，在经过了以康奈尔大学的s a l t o n 等人为代表的学者的精心研究之后，信息检索技术终于从实验室走向了大规模的商业应用之中。8 0 年代已经出现了一些商用的较大规模数据库检索系统，例如：l e x is n e x is 、d i a o g 、m e d l i n e 。9 0 年代是i n t e r n e t 的繁荣时期，单纯的手工检索和机械检索都显现出各自或多或少的缺点，因此有必要发展一种新型的信息检索方式，第一个网络搜索引擎加拿大蒙特利尔大学开发的f t p 搜索工具a r c h je 于1 9 9 0 年应运而生了。受到a r c h i e 的启发，美国明尼苏达大学的一个学生m a r km c c a h i 】l 于1 9 9 1 年发明了一种叫g o p h e r 的搜索引擎，不仅能够搜索网络j 二的文件，同时对网页也能进行索引。随着1 9 9 4 年美国卡耐基梅隆大学的m i c h a e lm a u l d i n 创建了l y c o s ，搜索引擎终于迎来了它的繁荣时代。l y c o s 最大的优势是远胜过其它同时代搜索引擎( 如：e x c i t e 、g a l a x y 、y a h o o 等) 的数据量，1 9 9 4 年创立之初收集了大约3 9 4 0 0 0 个文档；到1 9 9 5 年1 月，这个数量达到了1 5 0 万；而到1 9 9 6 年1 1 月，l y c o s 已经有超过6 0 0 0 万个的文档。如今，g o o g l e 和b a i d u 的巨大成功让整个世界都把眼光投入到搜索引擎这个领域中。仿佛一夜之间，各种各样的搜索服务席卷而来。从最初的g o o g l e 、y a h o o 到现今的b a i d u 、m s n 、中搜、s o g o u 等等，搜索引擎的品牌越来越多，服务也越来越丰富。同时，伴随着w e b 2 o 的普及，网络信息的膨胀速度呈指数级增长，各种各样的网站都需要为其加入检索功能，以满足用户的需要。另外，在企业级应用的市场上，全文信息检索的需求也一直在增加，各种文档处理、内容管理软件都需要加6硕士学位论文m a s t e r st h e s l s入全文检索的功能。在这样的背景下，信息检索技术迅速发展。同时，信息检索也是一门交叉学科，从其出现开始，一直都与其它学科有着密切的联系。它包括学术领域的众多先进思想和设计，其涉及的学科包括自然语言处理、人工智能、离散数学、排列组合、编译原理等。本文所涉及的方法主要集中在自然语言处理领域。自然语言处理( n a t u r a ll a n g u a g ep r o c e s s i n g ) 关注自然语言文本的语法( s y n t a c t i c ) 、语义( s e m a n t i c ) 及语用( p r a g m a t i c ) 分析。自然语言处理可以分析短语结构和语义，使得信息检索可以在短语上、或者从语义上进行处理，而不是仅仅基于单个关键词。自然语言处理和信息检索天生就是融合的。其中，汉语分词、机器学习、文本分类和聚类都将是本文的重点内容。2 2 信息检索基本原理检索( r e t r i e v a l ) 即查找之意。广义的信息检索( i n f o 硼a ti o nr e t r ie v a l )包括信息的存储过程和查找过程，而狭义的信息检索仅指信息的查找。我们可以这样定义信息检索：从信息集合中迅速、准确地查找出所需信息的程序和方法。这里所说的信息集合指的是有组织的信息整体。它可以是数据库的全部记录，也可以是某种检索工具，还可以是某个图书馆的全部馆藏。信息检索也就是从数据库、检索工具以及馆藏中查找所需信息的活动。广义的信息检索包括信息的存储和检索两个过程。信息的存储就是将搜集到的信息，通过提取其特征( 如题名、著者、主题词、内容等) 而形成款目，并将这些款目组织起来以某种格式存放到计算机磁盘之中。信息的检索就是依据某种规程，将存放在计算机磁盘中的信息快速高效的读取出来。这个过程是针对已存储好的信息库进行的，是存储的逆过程。存储是为了检索，而为了快速而有效地检索，就必须存储。没有存储检索就无从谈起。这是存储与检索相辅相成、相互依存的辩证关系。现代搜索引擎技术建立在这两个过程之上，同时也具备了新时代的特征。首先，面对i n t e r n e t 上海量的数据资源，需要一个网络爬虫下载大量的网页，并通过解析模块对其进行预处理，之后交给索引模块将这些网页内容建好索引；当用户提交一个查询请求时，解析模块分析查询内容，在索引中查找相关文档，重排模块进一步调整文档的顺序，最后提交给用户。7硕士学位论文m a s t e r st h e s l s总体上，系统可分为四个部分：数据预处理，索引生成，查询处理，检索。下面我们分别对各个部分采用的技术加以介绍。1 数据预处理目前检索系统的主要数据来源是w e b ，格式包括网页、w o r d 文档、p d f 文档等，这些格式的数据除了正文内容之外，还有大量的标记信息，因此从多种格式的数据中提取正文和其他所需的信息就成为数据预处理的主要任务。此外，众所周知，中文字符存在多种编码，比如g b 2 3 1 2 、b i g 5 、u n i c o d e ( c j k 区) ，而原始数据集往往包含多种编码，因此要正确地检索到结果必须进行统一编码转换。研究者们对预处理部分要提取哪些信息并没有共识，这与后续处理所需的信息密切相关，一般来说，正文、锚文本和链接地址都是要提取出来的。2 索引生成对原始数据建索引是为了快速定位查询词所在的位置，为了达到这个目的，索引的结构非常关键。目前主流的方法是以测为单位构造倒排文档表，每个文档都由一串词组成，而用户输入的查询条件通常是若干关键词，因此如果预先记录这些词出现的位置，那么只要在索引文件中找到这些词，也就找到了包含它们的文档。为了进一步提高查询的速度，在组织索引时还可以采用一些更复杂的方法，比如b 树、t r i e 树、哈希表等。这个阶段还需要对预处理之后的文档进行词法分析，这是因为很多语言的文本都不宜直接把诈文中的字符串用于建立索引。例如，中文里的词与词之问不存在分隔符，因此必须先进行分词；而英文中的词存在很多变形，比如“c f ) m p u t e ”就存在“c o m p u t e s ”、“c o m p l j ti n g ”、“c o m p u t e d ”等多种变形，应先进行词根还原。此外，有些词虽然出现频率很高，但对于查询没有任何帮助，比如“的”、“了”等，就无需放入索引，为此需要预备一个停用词表( s t o pw o r dl i s t ) 对这类词进行过滤。3 查询处理用户输入的查询条件可以有多种形式，包括关键词、布尔表达式、自然语言形式的描述语句甚至是文本，但如果把这些输入仅当作关键词去检索，显然不能准确把握用户的真实信息需求。很多系统采用查询扩展来克服这一问题。各种语言中都会存在很多同义词，比如查“计算机”的时候，包含“电脑”的结果也应一并返回，这种情况就需要利用查询扩展。4 检索最简单的检索系统只需要按照查询词之间的逻辑关系返回相应的文档就可以了，但这种做法显然不能表达结果与查询之间的深层关系。为了把最符合用户需求硕士学位论文m a s t e r st h e s i s的结果显示在前面，还需要利用各种信息对结果进行重排序。目前有两大主流技术用于分析结果和查询的相关性：链接分析和基于内容的计算。许多研究者发现，w w w上超链结构是个非常丰富和重要的资源，如果能够充分利用的话，可以极大地提高检索结果的质量。基于这种链接分析的思想，s e r g e yb r i n 和l a r r yp a g e 在1 9 9 8年提出了p a g e r a n k 算法，同年j k 1 e i n b e r g 提出了h i t s 算法，其它一些学者也相继提出了另外的链接分析算法，如s a l s a ，p h i t s ，b a y e s i a n 等算法。这些算法有的已经在实际的系统中实现和使用，并且取得了良好的效果。而基于内容的计算则沿用传统的文本分类方法，多采用向量空间模型、概率模型等方法来逐一计算用户查询和结果的相似度( 相关性) 。两者各有优缺点，而且恰好互补。链接分析充分利用了w e b 上丰富的链接结构信息，但它很少考虑网页本身的内容，而直观上看，基于内容的计算则较为深入地揭示了查询和结果之间的语义关系，但忽略了不同网页之间的指向关系，因此现在很多系统尝试把两者结合起来，以达到更好的性能。信息检索的一般流程如图2 1 所示：用户解析器甸甸爬虫器-引结构图2 1 经典的信息检索流程图2 3 信息检索的评价方法在信息检索领域中，评测指标的选择往往是至关重要的。评测指标直接关系到9硕士学位论文m a s t e r st h e s l s参评系统的最终评价，指标不合理会导致对系统的评价也不合理，因此规范化的评测会议对于评价指标的选择都是很慎重的。早期常用的评测指标包括准确率( p r e c i s i o n ) 、召回率( r e c a l l ) 、f 值、e 值等。准确率又称“查准率”、“正确率”，召回率又称“查全率”。在个大规模数据集合中检索文档时，可把集合中的所有文档分成四类：表2 1 信息检索评价分类标准相关不相关检索到ab未检索到cd一般来说，希望数据集中相关的文档，被检索到的越多越好，这是追求“查全率”，即( a + c ) 值，越大越好。同时我们还希望，检索到的文档中，相关的越多越好，不相关的越少越好，这是追求“准确率”，即( a + b ) ，越大越好。在此我们给出准确率和召回率的形式化定义如下：对于信息检索要求i ，如果用r 表示相关文档的集合，a 表示检索结果组成的文档集合，并用r a 表示r 和a 的交集，即检索到的相关文档集合，i x i 表示集合x 的元素个数，则：谢。，z ：群r e 删，：掣( 2 1 )h吲其中p r e c i s i o n 被称作为准确率，表示检索到的相关文档占检索结果义档的比例；r e c a l l 被称作为召回率，表示检索到的相关文档占实际相关文档的比例。从上面公式可以看出，召回率与准确率虽然没有必然的关系，然而在大规模数据集合中，这两个指标却是相互制约的。这两个值虽然能够算出大致上的结果，但是各有偏重，前者偏重于结果中有尽量多的有用信息，为此可能不惜牺牲一部分相关数据；而后者则倾向于尽量找出所有相关文件，即便因此而参杂如很多垃圾信息也在所不惜。在这种情况下，引入了将两个数据结合的f 值和e 值。f 值为召回率r 和准确率p 的调和平均值，若p ：o 或者r = 0 那么f = o ，否则，= 音( p o ，r o )( 2 2 )二+ 二pre 值为召回率r 和正确率p 的加权平均值，b l 表示更重视p1 0硕士学位论文m a s t e r st h e s l se = 1 一* ( p o ，r o )( 2 3 )u1上pr不过，随着测试集规模的扩大以及人们对评测结果理解的深入，更加准确反映系统性能的新评价指标逐渐出现。目前，国际上最为通用的搜索引擎测试标准是美国t r e c 会议( 文本检索会议，t e x tr e t r i e v a lc o n f e r e n c e ) 所提出的标准。它是2 0 世纪9 0 年代美国国防部高级研究计划署( d a r p a ) 出资推行的一个文本处理计划。自1 9 9 2年d a r p a 同m s t ( n a t i o n a li n s t i t u t eo fs t a n d a r d sa n dt e c l l n o l o g y ) 共同举办第一届n 迮c 会议召开以来，t r e c 已经成功举办了1 4 届。该协会组织者认为：对不同系统的比较，其意义并不在于要证明某个系统优于其他系统，而是要把更多不同的技术放在一起公开讨论，这对技术的发展有很大好处。为此协会提出了四大目标：( 1 ) 鼓励对基于大测试集合的信息检索方法的研究；( 2 ) 提供一个可以用来交流研究思想的论坛，增进工业界、学术界和政府部门之间的互相了解；( 3 ) 示范信息检索理论在解决实际问题方面的重大进步，提高信息检索技术从理论走向商业应用的速度；( 4 ) 为工业界和学术界提高评估技术的可用性，并开发新的更为适用的评估技术。不过，由于中英文评测的巨大差别，t r e c 往往不能够对中文信息处理技术进行有效的检验。为此，国内相继召开了多个面向中文信息处理技术的评测会议，其中比较有影响的8 6 3 评测、全国搜索引擎和网上信息挖掘会议( s e w m ) 等。这些测试基本上以m a p 、r p r e c e s i o n 和p ( n ) 为基本指标。( 1 ) 平均准确率( m e a na v e r a g ep r e c i s i o n ，即m a p ) ：单个主题的m a p 是每篇相关文档检索出后的准确率的平均值。主题集合的m a p 是每个主题的m a p的平均值。m a p 是反映系统在全部相关文档上性能的单值指标；( 2 ) r p r e c i s i o n ：单个主题的r p r e c i s i o n 是检索出r 篇文档时的准确率。其中r 是测试集中与主题相关的文档的数目。主题集合的r - p r e c i s i o n 是每个主题的r - p r e c i s i o n 的平均值。( 3 ) p x ：p x 是系统对于该主题返回的前x 个结果的准确率。考虑到用户在查看搜索引擎结果时，往往希望在第一个页面( 通常为1 0 个结果，在本系统中就是l o 个) 就找到自己所需的信息，因此设置了这样一个拟人化的指标，p x 常常能比较有效地反映系统在真实应用环境下所表现的性能。硕士学位论文m a s t e r st h e s l s2 4 检索模型信息检索模型是指如何对查询和文档进行表示，然后对它们进行相似度计算的框架和方法。本质上是对相关度建模。信息检索模型是瓜中的核心内容之一。图2 2 相关度模型由此可见，信息检索模型主要包括以下三个要素：1 文本集早期文本信息检索基本局限于目录或摘要等二次文献，它们的建立一般都采用传统的人工赋词标引方法。这种标引方法需要由标引人员手工对各种信息进行加工处理，给出检索标识。计算机根据这些标引词建立索引，用传统的数据库技术实现管理和检索。因此，标引的工作量大，标引质量囚人而异，带有很大的局限性。随着大量且不断变化的各类信息的出现以及相关技术和硬件设备的发展，人们对全文检索系统的需求越来越大，对检索的要求也越来越高。全文检索不同于早期的检索系统，它是将全文本信息作为检索对象，建立文本集，利用计算机抽取标识符，建立索引，再用全文检索技术实现检索。2 用户查询用户提交问题给检索系统，系统将其作为处理目标，搜寻文本集，并判断其中哪一对象与用户的问题相匹配。用户首次提出问题时，对问题的描述也许并不完全，因此，系统还需不断修改或扩充用户提问。用户的问题包括用户感兴趣的关键词、自然语言、逻辑关系式等。这与数据库查询处理不同，数据库中的查询有一定的语义定义，且缺乏真i e 的自然语言表示。3 文本与用户提问相匹配1 2硕士学位论文m a s t e r st h e s i s给定文本集与用户提问的描述，通常要判断该文本集与用户提问间的匹配程度。匹配处理的技术基础是自然语言处理技术以及能对文本集和用户提问做出严格的表示。根据查找相关信息的实现方式不同，经典的信息检索模型有布尔模型( b 0 0 1 e a nm o d e l ) 、向量空间模型( v e c t o rs p a c em o d e l ) 和概率模型( p r o b a b i l i s t i cm o d e l ) 。布尔模型是许多商业信息检索系统的理论基础。在布尔模型中，文档和查询都被表示为索引项的集合，因此该模型是集合论( s e tt h e o r e t i c ) 模型；在向量空间模型中，把文档和查询表示成一个n 维空间中的向量，用距离作为相似度的度量，该模型是代数( a l g e b r a i c ) 模型【2 0 】；在概率模型中，把检索看作是文档和查询之间匹配成功的概率估计问题，用于构建文档和查询的机制是基于概率论的，该模型是概率( p r o b a b i l i s t i c ) 模型【z 1 j 。随着信息检索技术的深入研究与发展，又从这三类经典模型又派生出许多扩展模型。图中概括了这些模型的分类方法r 扩展布尔模型厂称删t = 模型l厂广义向量模型柃索模犁向量窄问模型潜在语义模型li、神经网络模型l概率模型，：吴篓量概率模型l 语言模型图2 3 信息检索模型的分类下面分别对三类中的代表模型作详细的介绍。2 4 1 布尔模型布尔模型是基于集合理论和布尔代数的一种的简单的检索模型。由于集合的概念非常直观，所以布尔模型为信息检索系统的普通用户提供了一种易于掌握的框硕士学位论文m a s t e r st h e s i s架。由于布尔模型内部简单、形式简洁，引起了广泛的关注，并且在早期的许多商业书目系统中得以采用。设文本集d 2 ( d i ，d 2 ，d 3 ，d 。) ，d i ( i _ l ，2 ，n ) 为文本集中某一文档；又设i = ( t 订，t 渺，t i 。) 为d i 的标引词集合，则：对于形如q = wnw 2n nw k 的检索式，如果w l i ，w 2 i ，w k i ，则d i 为查询q 的命中文档，否则d i 为q 的不命中文档；对于形如q = w juw 2u uw ：的检索式，如果至少存在某个w ；王( j = l ，2 ，k ) ，则d i 为q 的命中文档，否则d i 为不命中文档。模型是文档数据库系统中的主要模型。模型定义索引术语只有两种状态：出现或者不出现在某一篇文档中，这样就导致了索引术语的权重都表现为二元性，它只能给出精确匹配的结果，文档要么相关，要么不相关。布尔模型的缺陷是显而易见的：第一，它的检索策略是基于二元判定标准( b i n a r yd e c i s i o nc t e r i o n ) ( 例如，对于检索来说一篇文档只有相关和不相关两中状态) ，缺乏文档分级( r a n l ( ) 的概念，限制了检索功能。第二，虽然布尔表达式具有精确的语义，但常常很难将用户的信息需求转换为布尔表达式，实际上大多数捡索用户发现在把他们所需的查询信息转换为布尔时并不是那么容易。布尔模犁的主要优点在于具有清楚和简单的形式，而卡要缺陷在于完全匹配会导致太多或者太少的结果文档被返回。众所周知，索引术语的权重从根本f ：提高了检索系统的功能，从而导致了向量空问模型的产生。2 4 2 向量空间模型向量空间模型是一种广泛应用于