信息检索的概率模型-.doc

信息检索的概率模型一、 综述一、 信息检索技术由于以因特网为主体的信息高速公路的不断普及和发展，信息技术已经渗透到我们社会生活的各个角落，正以前所未有的速度和能力改变着我们的生活的工作方式，我们真正处于一个“信息爆炸”的时代。一方面，因特网上面蕴含的海量信息远远超过人们的想象；另一方面，面对信息的汪洋大海，人们往往感到束手无策，无所适从，出现所谓的“信息过载”和“信息迷向”的现象。于是一个极富挑战性的课题：如何帮助人们有效地选择和利用所感兴趣的信息，尽量剔除不相关的信息。同时保证人们在信息选择方面的个人隐私权利？成为学术界和企业界所十分关注的焦点。随着在线文本的日益增多，其中包括新闻、电子杂志、电子邮件、技术报告、文档以及网上图书馆。如此众多的信息，仅仅依靠大脑来收集和整理所需要的信息显然是不够的。所以，自动收集和整理所需要的各类信息成为信息产业面临新的挑战和新的发展契机。根据不同的应用背景和不同的使用目的，信息处理技术已经演化信息检索、信息过滤、信息分类、问题回答等方向。由于目前网上信息的表现形式大多数为文本，而且文本也是广大用户所习惯接收的形式。因此我们在下面主要讨论中文文本检索和相关的评价方案。1、信息检索技术的发展信息检索（information retrieval）是指信息按一定的方式组织起来，并根据信息用户的需要找出有关的信息的过程和技术。狭义的信息检索就是信息检索过程的后半部分，即从信息集合中找出所需要的信息的过程。信息检索起源于图书馆的参考咨询和文摘索引工作，从19世纪下半叶首先开始发展，至20世纪40年代，索引和检索成已为图书馆独立的工具和用户服务项目。1945年，vannevar bush的论文就像我们可能会想的第一次提出了设计自动的，在大规模的存储数据中进行查找的机器的构想。这被认为是现在信息检索技术的开山之作。进入50年代后，研究者们开始为逐步的实现这些设想而努力。在50年代中期，在利用电脑对文本数据进行检索的研究上，研究者取得了一些成果。其中最有代表性的是luhn在ibm公司的工作，他提出了利用词对文档构建索引并利用检索与文档中词的匹配程度进行检索 的方法，这种方法就是目前常用的倒排文档技术的雏形。在著名的国际文本检索会议(text retrieval conference,trec)上，有两个最重要的研究方向：routing task和ad hoc task。其热点问题包括从早期的文本检索、文本过滤到当前的问题回答。文本信息检索就是根据用户提出的具体查询，在大量相对稳定的文本源中，检索出符合用户查询条件的文本，并按其满足查询的程度排序列出。文本检索技术的发展已经有四十多年的历史，取得了很大的成就，产生了大批实用的检索系统，积累了很多成熟的技术。1992年，nist(美国国家标准和技术研究所)与darpa联合赞助了每年一次的trec，对于文本检索和文本过滤和问题回答等专题倾注了极大的热忱。目前随着因特网的迅速发展，需求的不断增加，文本检索以及相关技术方面取得了长足的进展，成为信息产业新的增长点。2、信息检索技术的简介信息检索系统流程大致如下图所示：总体上，系统可分为四个部分：数据预处理，索引生成，查询处理，检索。下面我们分别对各个部分采用的技术加以介绍。1. 数据预处理目前检索系统的主要数据来源是web，格式包括网页、word 文档、pdf 文档等，这些格式的数据除了正文内容之外，还有大量的标记信息，因此从多种格式的数据中提取正文和其他所需的信息就成为数据预处理的主要任务。此外，众所周知，中文字符存在多种编码，比如gb2312、big5、unicode（cjk 区），而原始数据集往往包含多种编码，因此要正确地检索到结果必须进行统一编码转换。研究者们对预处理部分要提取哪些信息并没有共识，这与后续处理所需的信息密切相关，一般来说，正文、锚文本和链接地址都是要提取出来的。2. 索引生成对原始数据建索引是为了快速定位查询词所在的位置，为了达到这个目的，索引的结构非常关键。目前主流的方法是以词为单位构造倒排文档表，其结构大致如下图所示：每个文档都由一串词组成，而用户输入的查询条件通常是若干关键词，因此如果预先记录这些词出现的位置，那么只要在索引文件中找到这些词，也就找到了包含它们的文档。为了进一步提高查询的速度，在组织索引时还可以采用一些更复杂的方法，比如b树、trie 树、哈希表等。这个阶段还需要对预处理之后的文档进行词法分析，这是因为很多语言的文本都不宜直接把正文中的字符串用于建立索引。例如，中文里的词与词之间不存在分隔符，因此必须先进行分词，而英文中的词存在很多变形，比如“compute”就存在“computes”、“computing”、“computed”等多种变形，应先进行词根还原。此外，有些词虽然出现频率很高，但对于查询没有任何帮助，比如“的”、“了”等，就无需放入索引，为此需要预备一个停用词表（stop word list）对这类词进行过滤。3. 查询处理用户输入的查询条件可以有多种形式，包括关键词、布尔表达式、自然语言形式的描述语句甚至是文本，但如果把这些输入仅当作关键词去检索，显然不能准确把握用户的真实信息需求。很多系统采用查询扩展来克服这一问题。各种语言中都会存在很多同义词，比如查“计算机”的时候，包含“电脑”的结果也应一并返回，这种情况通常会采用查词典的方法解决。但完全基于词典所能提供的信息有限，而且很多时候并不适宜简单地以同义词替换方法进行扩展，因此很多研究者还采用相关反馈、关联矩阵等方法对查询条件进行深入挖掘。4. 检索最简单的检索系统只需要按照查询词之间的逻辑关系返回相应的文档就可以了，但这种做法显然不能表达结果与查询之间的深层关系。为了把最符合用户需求的结果显示在前面，还需要利用各种信息对结果进行重排序。目前有两大主流技术用于分析结果和查询的相关性：链接分析和基于内容的计算。许多研究者发现，www 上超链结构是个非常丰富和重要的资源，如果能够充分利用的话，可以极大地提高检索结果的质量。基于这种链接分析的思想，sergey brin 和larry page 在1998 年提出了pagerank 算法，同年j.kleinberg 提出了hits 算法，其它一些学者也相继提出了另外的链接分析算法，如salsa，phits，bayesian等算法。这些算法有的已经在实际的系统中实现和使用，并且取得了良好的效果。而基于内容的计算则沿用传统的文本分类方法，多采用向量空间模型、概率模型等方法来逐一计算用户查询和结果的相似度（相关性）。两者各有优缺点，而且恰好互补。链接分析充分利用了web 上丰富的链接结构信息，但它很少考虑网页本身的内容，而直观上看，基于内容的计算则较为深入地揭示了查询和结果之间的语义关系，但忽略了不同网页之间的指向关系，因此现在很多系统尝试把两者结合起来，以达到更好的性能。3、信息检索技术的模型信息检索模型可形式化地表示成为一个四元组，d是一个文档集合，q是一个查询集合，f是一个对文档和查询建模的框架，r(qi,dj) 是一个排序函数，它给查询qi和文档 dj 之间的相关度赋予一个排序值。3.1、布尔模型所谓布尔检索, 就是采用布尔代数的方法, 用布尔表达式表示用户提问, 通过对文本标识与用户给出的检索式进行逻辑比较来检索文本。设文本集d 中某一文本i, 该文本可表示为:di = ( t1 , t2, , tm) ,其中, t1 , t 2, , t m 为标引词, 用以反映i 的内容。另设用户某一检索式如下:qj = ( t1 t 2) ( t3 ( t4) ) .对于该检索式, 系统响应并输出的一组文本应为: 它们都含有标引词t1 和t2 , 或者含有标引词t 3, 但不含有标引词t 4。布尔检索具有简单、易理解、易实现等优点, 故得到广泛的应用。1967年后, 布尔检索模型正式被大型文献检索系统采用, 并渐成为各种商业性联机检索系统的标准检索模式, 服务信息情报界30多年, 直到现在, 大多数商用检索系统仍采用布尔检索。尽管布尔检索有着种种的优点, 但是它的缺点仍然是明显的, 它存在的主要缺陷有以下几点。( 1) 布尔逻辑式的构造不易全面反映用户的需求。用标引词的简单组配不能完全反映用户的实际需要, 用户需要那一方面内容的文本, 需要到多大程度, 这是检索式无法表达清楚的, 如对上述检索式, t1 和t2 , 究竟用户希望能得到更多地反映t1 内容的文本还是反映t2 内容的文本, 传统的布尔检索无法解决此问题。( 2) 匹配标准存在某些不合理的地方。例如, 在响应某个用“”连接的检索时, 系统把只含有其中一个或数个但非全部检索词的文本看作与那些根本不含有其中一个检索词的文本一样差, 同样加以排除; 另一方面, 用响应某个用“”连接的检索式时, 系统都不能把含有所有这些检索词的文本看作比那些只含有其中一个检索词的文本更好一些。( 3) 检索结果不能按照用户定义的重要性排序输出。系统检索输出的文本中, 排在第一位的文本不一定是文本集中最适合用户需要的文本, 用户只能从头到尾浏览才能知道输出文本中那些更适合自己的需要。针对于标准的布尔模型中文献表达形式过于简单、检索条件过于严格而出现的问题，人们对其采取了扩充和修改，提出了扩展的布尔模型。如salton 于1983年提出的一种所谓的扩展布尔检索模型, 它是将向量检索模型与布尔检索模型融为一体, 并克服了传统希尔模型的一些缺陷, 下面我们用矢量的方法来讨论布尔检索。设文本集中每篇文本仅由两个标引词t1 和t2 标引, 并且t1、t2允许赋以权值, 其权值范围为 0, 1 , 权值越接近1, 说明该词越能反映文本的内容, 反之, 越不能反映文本的内容, 在salton 模型中, 上述情形用平面坐标系上某点代表某一文本和用户给出的检索式, 如图：图中的横、纵坐标用t1、t2 表示, 其中a( 0, 1) 表示词t1 权值为0, 词t 2 权值为1 的文本, b( 1, 0) 表示词t 1权值为1, 词t 2 权值为0 的文本, c( 1, 1) 表示词t 1、t 2 的权值均为1 的文本, 文本集d 中凡是可以用t 1、t 2 标引的文本可以用四边形oacb 中某一点表示, 同样, 用户给出检索式后, 也可用四边形oacb 中某一点表示。下面我们来看看salton 模型中是如何构造相似度计算式的。对于由t1 和t2 构成的检索式q = t1 t2 , 在图1中只有a 、b、c 3点所代表的各文本才是最理想的文本, 对于某一文本d 来说, 当d 点离a、b、c 3点越接近时说明相似度越大，或者说，当d点离o点越远时，相似度越大。因而d与o的距离 = = 可以作为我们衡量一文本与查询q 的相关程度的一个尺度, 显然0 2 , 为了使相似度控制在0 与1 之间, 将相似度定义为:sim( d, q( t1 t2 ) ) = (1)对于由t1 和t 2 构成的查询q = t1 t 2, 只有c 点才是最理想的文本, 用d 与c 的距离 = 作为我们衡量一文本与查询q 的相关程度的一个尺度, 于是, 把相似度定义为:sim( d, q( t1 t2 ) ) = 1 -(2) ( 1)、( 2) 式还可推广到对检索标引词进行加权的情形, 设检索标引词t1、t2 的权值分别为a, b,0 a, b 1, 则( 1) 式、( 2) 式可进一步推广为:sim( d, q( t1 , a) ( t2, b) ) = 1 - (4)salton 模型还给出了把标引词推广到n 个时的相似度计算公式。设d = ( d1 , d2, , dn ) ,其中d i 表示第i 个标引词t i 的权值, 0 di 1。由布尔运算符“”及“”所确定的检索式分别为:q( p ) = ( t1 , a1) ( t 2, a2) ( tn, an ) ,q( p ) = ( t1 , a1) ( t 2, a2) ( tn, an ) ,其中ai 表示第i 个检索标引词ti 的权值, 0 ai 1, 这里, p 是一个可变的量, 1 q , 在salton 模型中, 以( 4) 式作为基本的出发点, 在n 个标引词生成的n 维欧氏空间中应用l p矢量模公式进行欧氏模的计算, 将文本和查询的相似度定义为:sim( d, q( p) ) = 1 - 在文本信息检索中, 布尔检索不仅具有简单、易理解等特点, 而且易于在计算机中加以实现, 是一种最为常用的检索方法。扩展的布尔模索模型salton 模型克服了传统布尔模型的一些缺陷, 更符合了用户的需要。3.2、向量空间模型向量空间模型是由salton及其学生们在六十年代末到七十年代初提出并发展起来的。这一模型将给定的文本(文章、查询或文章中的一段等)转换成一个维数很高，由一系列关键词组成的向量。模型并没有规定关键词如何定义，但是一般来说，关键词可以是字，词或者短语。假设我们用“词”作为term，那么在词典中的每一个词，都定义向量空间中的一维。如果一篇文档包含这个词，那么表示这个文档的向量在这个词所定义的维度上应该拥有一个非0值。这个模型最大特点是可以方便地计算出任意两个向量的近似程度，即向量所对应的文本间的相似性。用信息检索的术语来说，如果两个向量是相近的，则其对应的文本是语义相关的。将所有文献和查询以向量形式表示，则针对特定的查询向量，比较它与所有文献向量的相似度，并依相似度将文献降序排列，这便是现代信息检索系统中常用的方法。salton及其学生们还根据向量空间模型实现了smart系统。该系统在过去的30多年中，对信息检索的研究有非常重要的影响。信息检索的许多理论和技术(如自动索引、加权技术、相关反馈、文献聚类等)都是在smart上首先实现或测试的。假设表示文档向量，而表示查询向量，文档与查询的相关性可以用余弦距离表示如下：如果我们用和表示和中的第i维的值，并且对每个文档矢量进行归一化，即令，那么上式有可以表示为在此，究竟如何取值是一个重要的问题，其取值一般被称为关键词i在文档d中的权重。目前，对关键词权重的确定方法一般都需要获取一些关于关键词的统计量，而后根据这些统计量，应用某种认为规定的计算公式来得到权重。 最常用的统计量包括： tf，term frequency的缩写，表示某个关键词在某个文档中出现的频率。 qtf，query term frequency的缩写。表示查询中某关键词的出现频率。 n，集合中的文档总数 df，document frequency的缩写，表示文档集合中，出现某个关键词的文档个数。 idf，inversed document frequency的缩写。 dl，文档长度 adl，平均文档长度权重的计算：在向量空间模型下，构造关键词权重计算公式有三个基本原则：1. 如果一个关键词在某个文档中出现次数越多，那么这个词应该被认为越重要。 2. 如果一个关键词在越多的文档中出现，那么这个词区分文档的作用就越低，于是其重要性也应当相应降低。 3. 一篇文档越长，那么其出现某个关键词的次数可能越高，而每个关键词对这个文档的区分作用也越低，相应的应该对这些关键词予以一定的折扣。 早期的权重往往直接采用tf，但是显然这种权重并没有考虑上述第二条原则，因此在大规模系统中是不适用的。目前，常用的关键词权重计算公式大多基于tf和df进行构建，同时，一些较为复杂的计算公式也考虑了文档长度。现简要列举如下：tf-idf得分。严格地说，tf/idf得分并不特指某个计算公式，而是一个计算公式集合。其中tf与idf都可以进行各种变换，究竟何种变换较能符合实际需求，需要由实验和应用来验证。常见的变换方法有：其中，最后一个公式，即:被大量系统证明是最有效的。此外，较为常用的关键词权重算法还包括okapi权重和pivoted normalization 权重(pnw)。这些公式综合考虑了查询和文档中的词频，以及文档的长度。okapi权重需要预设三个参数： k1，在1.0-2.0之间 b,通常为0.75 k3,在0-1000之间 而pnw则需要预设一个参数s，大部分情况下取0.20。 在经典模型中，假设索引项是独立的，或者说是正交的。这个假设极大地简化了索引项权值的计算过程，尽管这一假设有时不符合自然语言的实际情况，但是在这个假设下，计算权值的过程简单快捷，因而在目前很多实用的信息检索模型中仍被广泛采用。向量空间模型中索引项权重的算法提高了检索的性能，改进了检索效果，同时采用了部分匹配的策略和一定的相似度计算方法，使得模型可以根据结果文档与检索项的相似度进行排序，检索出与用户查询要求接近的文