信息存储与检索复习资料2.ppt

Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,信息存储与检索技术,*,Click to edit Master title style,第二章 信息检索模型,信息检索模型概述,1,布尔检索模型,2,向量空间检索模型,3,扩展布尔检索模型,4,信息存储与检索技术,第一节 信息检索模型概述,一、信息检索模型的基本概念,1,、信息检索模型的概念,信息检索模型（信息检索的数学模型）：,就是运用数学的语言和工具，对信息检索系统中的信息及其处理过程加以翻译和抽象，表述为某种数学公式，再经过演绎、推断、解释和实践检验，反过来指导信息检索实践。,信息检索模型由以下几部分组成：,（,1,）用户的需求表示,（,2,）文档的表示,（,3,）匹配机制,最简单的信息检索模型就是单项检索模型。,Q=Tk,DocA=(Ta,Tb,Tc),DocB=(Tb,Tk,Tm),信息检索模型主要从两个方面抽象地研究信息检索方法（,P27),：,确定在检索模型中如何表示构成检索系统的两个要素，即文档和检索式；,确定在检索模型中如何定义和计算文档与检索式之间的关系。,信息存储与检索技术,第一节 信息检索模型概述,一、信息检索模型的基本概念,2,、信息检索模型表示,一般一个信息检索系统可以形式化地抽象表示为如下的四元组（,P28),，如下：,System=(D,Q,F,R(dj,q),D,：信息检索系统的信息资源集合,Q,：用户信息需求集合,F,：信息资源与信息需求的匹配处理框架,R(dj,q),：（相似性）匹配函数,信息存储与检索技术,第一节 信息检索模型概述,一、信息检索模型的基本概念,2,、信息检索模型表示,（,3,）信息资源与信息需求的匹配处理框架（,F,）,匹配处理框架（,F,）提供对文档视图、提问式以及它们之间关系进行模型化处理的框架与规则。,布尔模型而言，匹配规则为二值相关性判断，匹配运算主要基于集合论的集合基本运算；,向量空间模型而言，匹配规则采用多值相关性判断，匹配处理建立在代数论的多维向量空间操作基础之上。,信息存储与检索技术,第一节 信息检索模型概述,一、信息检索模型的基本概念,2,、信息检索模型表示,（,4,）匹配函数,R(dj,，,q),匹配函数,R(dj,，,q),用于计算任一文档,dj,与任一提问,q,形成的文档提问对（,dj,，,q,）之间的相似度的大小,一般,R(dj,，,q),的函数值为一实数，其取值区间为,0,1,。,从数学上来讲，匹配函数的选取，要求能够具备一下特点：,计算方法简单，计算量小；,函数值在取值区间均匀分布；,针对某一提问所获取的相关文档集合，能够实现合理的排序输出,。,信息存储与检索技术,第一节 信息检索模型概述,一、信息检索模型的基本概念,3,、信息检索模型的分类,传统的文本信息检索模型主要有三种：布尔模型、向量空间模型和概率模型，也称经典的信息检索模型。,经典信息检索模型的基本假设：,（,1,）被检索对象主要是文档对象；,（,2,）标引词是相互独立的、彼此无关的。,（,3,）所有文档的内容和所需信息的表示都是非常精确的。,信息存储与检索技术,布尔模型,（集合论模型）：文献和查询用标引词集合来表示，匹配规则为二值相关性判断。,向量模型,（代数模型）：文献和查询用,t,维空间的向量来表示，匹配规则采用多值相关性判断。,概率模型,（概率模型）：检索是文献和查询之间匹配程度的概率估计问题,。,经典模型（如集合论，代数，概率模型）的各种不同的改进模式：,集合论模型：模糊集合论和扩展布尔模型；,代数模型：广义向量模型、潜语义标引模型和神经网络模型。,大多数检索系统往往将各种检索模型混合以达到最佳的检索效果。,信息存储与检索技术,第二节 布尔检索模型,一、布尔逻辑模型的概念,文献表示,：每一文献用一组标引词表示，标引词可以是关键词、作者、篇名等能反映文档特征的词。,提问表示,：每个提问都表示为提问词（检索词）的布尔组配，称其为布尔逻辑表达式。,布尔逻辑表达式指采用布尔运算符（逻辑与“,and”,、逻辑或“,or”,、逻辑非“,not”,等）来连接运算分量（检索词），以及表示运算优先级的括号组成的一种表达检索要求的一种算式，简称提问逻辑式。,匹配函数,：布尔模型对于任一篇文档,djD,，定义,dj,与用户提问,q,的匹配函数为：,Sim(dj,q),1,：,dj,中包含有,Q,的合取向量，,dj,与,Q,相关,Sim(dj,q),0,：,dj,中不包含有,Q,的合取向量，,dj,与,Q,不相关,信息存储与检索技术,第二节 布尔检索模型,二布尔逻辑运算符及其运算含义,常用的布尔逻辑运算符有三种，它们是逻辑或“,or”,、逻辑与“,and”,、逻辑非“,not”,。,（,1,）逻辑或（“,or”,，逻辑加，）,逻辑或可使检索命中结果的区域扩大，达到了扩检的目的，从而增强了检全率。,（,2,）逻辑与（“,and”,逻辑乘，,）,通过对检索词之间的与运算，增强了查找的专指性，可提高查准率。,以网络搜索引擎为例：见,P30,。,（,3,）逻辑非“,not”,（实质上为与非）,信息存储与检索技术,第二节 布尔检索模型,二布尔逻辑运算符及其运算含义,（,4,）布尔逻辑运算符的运算次序,绝大多数检索系统是按照如下规则进行检索运算的：,同级运算是从左向右进行的；,括号内的逻辑运算优先执行，括号有多层时，最内层括号中的运算最先执行；,当检索提问式含有截词符、位置算符、限制符时，布尔运算最后执行；,但对于运算符,or,、,and,、,not,，它们的运算优先次序在不同的系统中有着不同的规定：,DIALOG,的,RECON,软件：,not,最先执行，,and,其次执行，,or,最后执行；,STAIRS,软件、,ORBIT,软件：,and,与,not,同级，并高于,or,，它们依其自然顺序执行，,or,最后执行；,在,UNIVAS,上运行的,UNIDAS,软件：,and,最先执行，,not,其次执行，,or,最后执行。,信息存储与检索技术,第二节 布尔检索模型,三、传统布尔查询的评价,优点：,（,1,）与思维习惯相一致；,（,2,）方便扩检与缩检；,（,3,）易于计算机实现。,缺点：,（,1,）信息集合的标引问题,无权重设计,（,2,）用户需求的表示问题,逻辑运算符的理解和应用；,提问词的选择（例如整体与部分3,）匹配问题：,二值匹配策略问题,相关性排序以及检索结果输出量控制；,匹配标准不尽合理。,信息存储与检索技术,第三节 向量空间检索模型,20,世纪,60,年代末期，,Gerard Salton,（现代信息检索的奠基人），,SMART,系统。,向量空间检索模型：,Vector Space Model,简称,VSM,向量空间模型,是用提问词和标引词的向量空间来表示用户的查询要求和文档信息，根据向量空间的相似度，排列查询结果。,向量空间方法的,基本思想要点,是：,（,1,）将文档,D,和查询,Q,都用向量表示；,（,2,）检索的过程就是计算文档向量和查询向量之间的相似度；,（,3,）根据相似度的不同，对检索结果进行排序。,信息存储与检索技术,第三节 向量空间检索模型,一向量空间模型的基本原理,（,1,）文档向量的构造,考虑到一个有,n,个记录（文献）的集合：,D=d,1,，,d,2,，,d,n,对一条属于该集合的特定的文档记录,di,，可以用属性向量把它表示成：,d,i,（,t,i1,，,t,i2,，,t,im,）,d,i,就称为文档向量，其中：,m,：用于描述这些记录的属性的个数，一般情况下，该属性为主题词；,tij,：表示文献,d,i,中具有属性,tj,（,j,1,，,2,，,m,）的程度。把这种程度用数值的形式表示出来，就是人们常说的“加权”。,一般来讲，若文献,di,具有属性,tj,，则,tij,1,；否则,tij,0,。,我们称向量,di,（,ti1,，,ti2tim,）为,文档向量,。,信息存储与检索技术,第三节 向量空间检索模型,一向量空间模型的基本原理,（,1,）文档向量的构造,把文档向量,di,（,i,1,，,2,，,n,）看成矩阵,C,的第,i,行，那么整个文献集合可以用矩阵,C,来表示：,C=(c,ij,),nm,（,i,1,，,2,，,n,；,j,1,，,2,，,m,）,N:,是文献集合中文献的篇数；,M:,是用来标引文献的主题词的个数。,我们把矩阵,C,叫做文献集合的,文献属性相关矩阵。,信息存储与检索技术,第三节 向量空间检索模型,一向量空间模型的基本原理,（,2,）提问向量的构造,对于一个特定的提问,Q,也可以用属性向量把它表示成：,Q,（,q,1,，,q,2,q,m,）,这里,q,j,（,j,1,，,2,，,m,）表示提问,Q,包含属性,t,j,的程度。,信息存储与检索技术,第三节 向量空间检索模型,一向量空间模型的基本原理,（,3,）匹配函数的选择及相似度阈值的确定,较常采用的相似度计算指标是两个向量夹角的余弦值。按照两个向量夹角余弦的计算含义，文档,dj,和提问,q,的相似度值可以通过下面的计算公式获得（,P31,）：,1,）简单匹配系数：,2,）余弦系数：,信息存储与检索技术,第三节 向量空间检索模型,一向量空间模型的基本原理,（,3,）匹配函数的选择及相似度阈值的确定,利用相关性计算结果，可以：,计算系统中所有文档与某一提问的相似度，并能够按照其相似度值的降序排列方式输出命中的结果文档。,量化地判断系统文档两两之间的相似程度,文档相关矩阵,D,；,量化地判断系统中标引词（属性）两两之间的相似程度,属性相关矩阵,T,；,信息存储与检索技术,第三节 向量空间检索模型,量化地判断系统文档两两之间的相似程度,文档相关矩阵,D,；,文献相关矩阵,D,：,为了表示文献之间的相关关系，分别计算,C,矩阵中第,i,行与第,j,行之间的相关系数,d,ij,，由,d,ij,构成的一个,nn,的矩阵就称作文献相关矩阵。,当,C,矩阵中的值取,1,和,0,时，,d,ij,k,，说明这两篇文献中有,k,个相同的标引词。,矩阵中,d,ij,元可以理解成第,i,篇文献与第,j,篇文献包含的属性词的重复面的大小，,d,ij,越大，说明第,i,篇文献与第,j,篇文献包含的相同主题越多，因此两篇文献的相关程度也就越大。,信息存储与检索技术,第三节 向量空间检索模型,量化地判断系统中标引词（属性）两两之间的相似程度,属性相关矩阵,T,；,标引词（属性）相关矩阵,T,：,分别计算文献集合中第,i,列和第,j,列之间的相关系数,t,ij,，由,t,ij,构成的,mm,矩阵,T,称标引词相关矩阵。,当,C,矩阵中的值取,1,和,0,时tij,k,，则说明有,k,篇文献同时用第,i,个词和第,j,个词标引。,T,矩阵中,t,ij,元可以理解成第,i,个属性词与第,j,个属性词在整个文献库中存在于同一文献中的“相遇机会”的大小，,tij,越大，表示第,i,个属性词与第,j,个属性词在同一篇文献中相遇的次数愈多，它们二者的相关性一般也就越大。,信息存储与检索技术,第三节 向量空间检索模型,已知主题词表：,A,汽车,a1,，拖拉机,a2,，摩托车,a3,，发动机,a4,，废气,a5,，传动结构,a6,，处理,a7,，修理,a8,文献集合：,D,d1,，,d2,，,d3,d1,取标引词：汽车、发动机、废气、处理；,d2,取标引词拖拉机、传动结构；,d3,取标引词：汽车、拖拉机、摩托车、发动机、修理。,提问,Q,取提问词“汽车、拖拉机、发动机、废气、处理”,要求写出（相关系数的计算采用简单匹配系数的方法）：,1,）文献向量；,2,）提问向量；,3,）属性文献相关矩阵,C,；,4,）文献相关矩阵,D,；,5,）标引词相关矩阵,T,。,问：,1,）哪篇文献最符合提问要求？,2,）哪两篇文献内容比较接近？,信息存储与检索技术,第三节 向量空间检索模型,二、向量空间模型的技术特征分析与应用,（,1,）向量空间模型技术特征分析,部分匹配策略；,词加权处理模式；,对检索结果排序输出。,（,2,）向量空间模型的应用,典型的基于,VSM,理论的文本信息处理主要包括以下几个分支领域：文本检索、文本分类、文本过滤、文本挖掘、文本浏览与可视化等。应用前提：,VSM,的量化处理思想充分发挥了计算机的计算特长；,VSM,理论没有对其特征项（即属性词）的权值评价、文档向量与提问向量的相似度计算等问题做出统一的规定；,VSM,理论的文本语种无关性。,各检索词之间的关系是相互独立的（两两正交假设）。,信息存储与检索技术,第三节 向量空间检索模型,三向量空间模型实际应用中的局限性,（,1,）信息检索系统的向量模型要求用于检索的计算机的内存容量是相当大的。,解决方法：稀疏矩阵的存储与处理。,（,2,）上述理论要求属性词表是相对稳定的,-,不但其个数不能变，且其位置也不能变。,解决方法：预留空号。,（,3,）提问向量反应不出提问式主题词之间的多种逻辑组配关系。,解决方法：提问式变换。,例如：根据,7,个主题词,A,B,C,D,E,F,G,的主题词，有：,Q,A*D*-E,Q,（,A+D,）*,-E.,信息存储与检索技术,第四节 扩展布尔检索模型,一、扩展布尔检索模型的概念,例子：有以下检索式：,Q1,k1 and k2 and k3 and and k8,Q2,k1 or k2 or k3 or or k8,1983,，,Salton,，,扩展的布尔检索模型。,该模型中巧妙地引入了一个参数，通过适当调节这个参数，,Salton,模型可以分别为布尔模型、向量模型和模糊模型。,信息存储与检索技术,第四节 扩展布尔检索模型,二、扩展布尔模型的工作原理,基本思想：,将所检索的文档信息中的标引词与用户的查询表达式进行相似度的比较，按照相关的优先次序排列查询结果。,扩展布尔检索模型常用的方法：,MMM,模型；,Paice,模型；,P-Norm,模型。,本课以,P-Norm,模型为例。,信息存储与检索技术,第四节 扩展布尔检索模型,二、扩展布尔模型的工作原理,假设文本集中仅有两个标引词,t1,和,t2,，并且,t1,和,t2,允许赋以权值，其权值范围为,0,，,1,。在扩展布尔检索模型中，上述情形用平面坐标系上某点代表某一文本和用户给出的检索式。如,P39,图,2-2,所示。,信息存储与检索技术,第四节 扩展布尔检索模型,信息存储与检索技术,第四节 扩展布尔检索模型,二、扩展布尔模型的工作原理,可以将上述只包含两个项目的查询式的相似度计算进一步扩展：,（,1,）可将检索词的个数扩充为,m,个；,（,2,）将该式用于对检索词加权的情况下。,P-Norm,模型公式如下：,Xm,：表示第,m,个标引词在文献,d,中的权重；,P,：表示检索词间逻辑关系严格的程度。,信息存储与检索技术,第四节 扩展布尔检索模型,二、扩展布尔模型的工作原理,P,1,：,P,：,当,P,1,时，布尔逻辑式中算符“,or”,和“,and”,之间的差别消失，模型等价于向量空间模型；,当,P,时，提问式中的逻辑算符又符合模糊逻辑的形式，可以看作是布尔逻辑的一种泛化，相对应的模型是布尔模型,/,模糊逻辑模型；,P,值取,1,到之间的值时：,“,or”,：提问式中多出现几个提问词总比少出现好；,“,and”,：提问式中所有词都出现总比仅出现几个词更有价值，但同时又不苛求所有提问词都出现。,信息存储与检索技术,第四节 扩展布尔检索模型,二、扩展布尔模型的工作原理,（,1,）,P,值的大小，表达了对布尔逻辑算符的约束强度，取值越小约束越松，取值越大约束越严。,（,2,）,P,的实际值通常可以在,1.5,9,之间选择。,三、扩展布尔模型的优缺点,扩展布尔模型是常规布尔模型和向量模型相结合的产物。,1,、扩展布尔模型的优点,（,1,）与传统布尔检索中的倒排档检索技术相兼容，支持使用标准布尔逻辑表达的提问式结构；,（,2,）允许在文档和提问式中进行词加权处理；,（,3,）支持按相似度大小排序输出检索结果；,（,4,）通过调整参数,P,的值，可以灵活选择并得到不同的检索结果。,2,、扩展布尔检索模型的缺点,“集成化模型”,臃肿、不够简洁,不是很普及。,信息存储与检索技术,Thank You!,