第四章信息检索模型

第四章信息检索模型南京中医药大学文献检索教研室教学内容1、信息检索模型概述2、传统布尔检索模型3、向量空间模型4、扩展布尔检索模型5、概率模型信息检索模型概述信息检索是一门研究从一定规模的文档库中找出满足用户需求的信息的学问，它指的是对非结构化或半结构化信息的检索，半结构化信息检索人们通常称为文本信息检索，而非结构化信息检索多指多媒体信息检索。信息检索是对信息集合与需求集合的匹配和选择。信息检索基本原理：用户通过一些列关键词来阐明自己的信息需求，信息检索系统则检索与用户查询最为匹配的文献，同时借助某种相关性指标对检索出的文献进行排序。信息检索的实质问题：对于所有文档，根据其与用户查询的相关程度由大到小进行排序信息检索模型概述什么是数学模型？为了某种特定目的，通过对现实世界的某一特定对象做出一些必要的简化与假设，运用适当的数学工具得到的一种数学结构。模型是采用数学工具，对现实世界某种事物或某种运动的抽象描述面对相同的输入，模型的输出应能够无限地逼近现实世界的输出举例：天气的预测模型信息检索模型概述信息检索的模型，就是运用数学的语言和工具，对信息检索系统中的信息及其处理过程加以翻译和抽象，表述为某种数学公式，再经过演绎、推断、解释和实际检验，反过来指导信息检索实践。即信息检索模型是指如何对查询和文档进行表示，然后对它们进行相似度计算的框架和方法。信息检索模型的核心问题是检测哪些文献相关，哪些文献不相关，即判断一篇文献是否与用户的查询条件相关，以及相关的程度。信息检索模型概述本质上是对相关度建模。信息检索模型是IR中的核心内容之一。信息检索模型的组成用户的需求表示：包括用户查询信息的获取与表示。文档的表示：文档内容的识别与表示。匹配机制：用户需求表示与文档表示之间的查询机制，以及它们之间相关性排序的准则反馈修正：对检索结果进行优化。信息检索系统的形式化表示[D,Q,F,R(di,q)]D→文档集合的机内表示D={d1,d2,…,dm}为了满足检索匹配所要求的快速与便利，文档di通常由从文档中抽取的能够表达文档内容的特征项（如索引项/检索词/关键词）来表示设K={k1,k2,…,kn}为系统索引项集合则di={ωi1,ωi2,…,ωin}(ωij≥0)ωij→索引词kj在文档di中的重要性（权值weight）文档逻辑视图D是一个文档集合，通常由文档逻辑视图来表示。可以是一组索引词或关键词。既可以自动提取，也可以是由人主观指定。信息检索系统的形式化表示Q→用户查询的机内表示用户需求的各种状态潜在的真实需求（RealInformationNeed，RIN）意识到或感知到的需求（PerceptionInformationNeed，PIN）表达出的需求（Request）用户查询（Query）用户查询一般采用与文档类似的形式化表示匹配处理框架（F）F→文档与查询查询之间的匹配框架在信息集合（D）与需求集合（Q）之间建立模型化处理的框架与规则。不同检索模型的匹配处理的数学机制是不同的。布尔模型：集合论的基本运算向量空间模型：多维向量空间理论和向量线性代数概率模型：集合论、概率运算和Bayes法则匹配计算函数R(di,q)R(di,q)→文档与用户查询之间相关度计算函数匹配函数R(di,q)用于计算任一信息di（di∈D）与任一提问q（q∈Q）形成的信息—提问对（di，q）之间的相似度大小。一般地，R(di,q)的函数值为一实数，其取值区间为[0，1]匹配函数的特点：计算方法简单，计算量小；函数值在取值区间均匀分布；针对某一提问所获取的相关文档集合，能够实现合理的排序输出。结构化文本模型集合论模型文本检索模型非重叠链表模型邻近节点模型布尔模型向量模型概率模型浏览模型超文本模型基于本体的模型经典模型超文本模型知识检索模型扩展布尔模型模糊集合模型广义向量模型潜语义标引模型神经网络模型推理网络模型信任度网络模型语言模型代数模型概率模型信息检索模型的类型布尔检索模型最早的IR模型1957年，Y·Bar-Hille就对布尔逻辑应用于计算机信息检索的可能性进行了探讨目前仍然应用于商业系统中典型系统：Lucene布尔检索模型布尔（Boolean）模型是基于集合论和布尔代数的一种简单检索模型。用布尔表达式表示用户提问，通过对文献标识与提问式的逻辑运算来检索文献。优势：“集合”概念直观容易被理解和接受文档表示在传统的布尔模型中，一个文档被表示为关键词的集合。Dj=(K1,K2,K3,…,Km)表示文献Dj，式中K1,K2,K3,…,Km表示文献Dj中的所有标引词集合。布尔检索模型文档与标引词建立一个布尔关系。用若干标引词的布尔表达式来表达和解释查询Q。对于一个表示为Q=(K1ANDK2)OR(K3AND(NOTK4))的提问式，系统的响应必须是这样一组文献集合：这些文献中都含有标引词K1和K2，或者含有标引词K3但不含有标引词K4。常用的布尔逻辑组配运算符有：逻辑“与”(AND，常用符号“∧”表示)、逻辑“或”(OR，常用符号“∨”表示)、逻辑“非”(NOT，常用符号“－”表示)。

布尔检索模型在布尔检索模型中标引词在文献中要么出现、要么不出现，因此标引词Ki在文档Dj中的权重全部被设为二值数据，即Wij∈（0，1）。用户提交的查询条件由若干个标引词用与、或、非等逻辑符号相联结，在布尔检索模型中被表示成了布尔表达式Q=(K1，K2，…)，其本质可以表示为多个标引词权值的合取向量的析取Qi（Qi为表达式Q的任意合取向量），则文献Dj和查询Q的相关度表示为布尔检索模型如要检索“布尔检索或概率检索但不包括向量检索”方面的文档，其相应的查询表达式为：Q=检索and(布尔or概率not向量)，那么Q可以在其相应的（检索,布尔,概率,向量）标引词向量上取（1,1,0,0）（1,0,1,0）（1,1,1,0），那么文档Dj的向量如果与这中间一个相等，那么即可认为他们之间存在相似关系，而这种相互关系也是布尔值，即sim(Q,Dj)只能为0或1。相关概念合取范式：若干个互不相同的合取项的析取称为一个合取范式例：析取范式：在布尔逻辑中，析取范式(DNF)是逻辑公式的标准化（或规范化），它是合取子句的析取。

布尔提问的析取范式根据布尔逻辑的运算规定，提问式q可以被表示成由合取子项（conjunctivecomponents）组成的析取范式（disjunctivenormalform,简称dnf）形式。如：提问式q=k1and（k2ornotk3）可写成等价的析取范式形式：

qdnf

=(k1andk2andk3)or(k1andk2andnotk3)or(k1andnotk2andnotk3)

这里qdnf是提问式q的主析取范式。可进一步简化表示为：qdnf=(1,1,1)or(1,1,0)or(1,0,0)

其中：(1,1,1)or(1,1,0)or(1,0,0)是qdnf的三个合取子项qcc，他们是一组向量，由对应的三元组(k1,k2,k3)的每一个分量取0或1得到。简单实例Q=病毒AND（计算机OR电脑）ANDNOT医D1:…据报道，计算机病毒近日猖獗…D2:…小王虽然是学医的，但对研究电脑病毒也很感兴趣，最近发明了一种…D3:…计算机程序发现了爱滋病病毒的传播途径…D4:…最近我的电脑中病毒了…请问：哪些文档会被检索出来？布尔模型的优点到目前为止，布尔模型是最常用的检索模型，因为：由于查询简单，因此容易理解通过使用复杂的布尔表达式，可以很方便地控制查询结果相当有效的实现方法相当于识别包含了一个某个特定term的文档经过某种训练的用户可以容易地写出布尔查询式布尔模型可以通过扩展来包含排序的功能，即“扩展的布尔模型”布尔模型存在的问题布尔模型被认为是功能最弱的方式，其主要问题在于不支持部分匹配，而完全匹配会导致太多或者太少的结果文档被返回非常刚性:“与”意味着全部;“或”意味着任何一个很难控制被检索的文档数量原则上讲，所有被匹配的文档都将被返回很难对输出进行排序不考虑索引词的权重，所有文档都以相同的方式和查询相匹配很难进行自动的相关反馈如果一篇文档被用户确认为相关或者不相关，怎样相应地修改查询式呢？无法体现文档之间的细微差别相关度的大小只有两个值，模型这种“非此即彼”的二值判断标准无法区分文档相关度大小的细微差别向量空间模型向量空间模型（VectorSpaceModel，VSM）是由G·Salton等人在1958年提出的代表系统SMART（SystemfortheManipulationandRetrievalofText）这一系统理论框架到现在仍然是信息检索技术研究的基础向量空间模型向量模型通过分派非二值权重给查询和文档中的标引词来实现检索目标。这些权重用于计算系统中的每个文档与用户的查询请求的相似程度，向量模型通过对文档按照相似程度降序排列的方式，来实现文档与查询项的部分匹配。这样做的结果中的文档排列顺序比通过布尔模型得到的结果要合理得多。文档提问关键字的权重矢量关键字的权重矢量匹配检索到文献向量空间模型的基本原理模型的描述文档D(Document)：泛指文档或文档中的一个片段（如文档中的标题、摘要、正文等）。索引项K（key）：指出现在文档中能够代表文档性质的基本语言单位（如字、词等），也就是通常所指的检索词，这样一个文档D就可以表示为D(k1,k2,…,kn)，其中n就代表了检索字的数量。d1：土豆的美容功效d2：土豆的栽培d3：土豆的后期加工K={土豆、美容、栽培、加工}

特征项权重Wk（KeyWeight）：指特征项kn能够代表文档D能力的大小，体现了特征项在文档中的重要程度。

相似度S（Similarity）：指两个文档内容相关程度的大小模型的特点基于关键词(一个文本由一个关键词列表组成)根据关键词的出现频率计算相似度例如：文档的统计特性用户规定一个词项(key)集合，可以给每个词项附加权重未加权的词项:Q=database;text;information加权的词项:Q=database0.5;text0.8;information0.2查询式中没有布尔条件根据相似度对输出结果进行排序支持自动的相关反馈有用的词项被添加到原始的查询式中例如：Q

database;text;information;document

模型中的问题怎样确定文档中哪些词是重要的词？（索引项）怎样确定一个词在某个文档中或在整个文档集中的重要程度？（权重）怎样确定一个文档和一个查询式之间的相似度？索引项的选择若干独立的词项被选作索引项(indexkeys)or

词表vocabulary索引项代表了一个应用中的重要词项计算机科学图书馆中的索引项应该是哪些呢?体系结构总线计算机数据库….XML计算机科学文档集文档集中的索引项这些索引项是不相关的(或者说是正交的)

，形成一个向量空间vectorspace向量空间模型定义：

在向量空间模型中，标引词Ki在文档Dj中的权重Wij是一个大于0的非二值数。文档Dj可以看做是一个向量：

Dj=（W1j，W2j，W3j………Wtj）其中，t是文档集中所有标引词的数目。用户查询中的标引词也是有权重的，设Wiq是用户检索提问式（查询）Q的标引词Ki的权重，且Wiq≥0，则查询向量Q被定义成：

Q=（W1q，W2q，W3q…………Wtq）。衡量文档和查询的相关度转化成计算文档向量和查询向量之间的相似度。一般使用文档向量和查询向量之间的夹角余弦值来计算它们之间的相似度。向量空间模型WijK1k2…KnD101…0D210.8…0.5……………Dn0.20…1文档向量空间的表示：文档D1(W11,W21,…Wn1)查询Q(W1q,W2q,…Wnq)文档D2(W12,W22,…Wn2)特征项1特征项2特征项3文档向量空间模型：文档和文档之间的相似度Sim可以表示如下：文档和查询之间的相似度Sim可以表示如下：向量空间模型例子D1=2K1+3K2+5K3D2=3K1+7K2+K3Q=0K1+0K2+2K3文档D1=2K1+3K2+5K3查询Q=0K1+0K2+2K3文档D2=3K1+7K2+K3特征项1特征项2特征项3文档中关键词的权重两方面因素词表达文档内容的能力tfij→关键词的词频（关键词tj在文档di中的频率）词区分其所在文档与其它文档的能力dfj

→关键词的文档频率（包含关键词tj的文档数量）tf-idf（词频-逆文档频率）公式标引词的权重计算（TF-IDF）N为文档集合，ni为包含标引词Ki的文档篇数，TFij表示标引词Ki在文档Dj中出现的频数，则文档Dj中标引词Ki的标准化频率Fij为

Fij=TFij/maxj

TFij最大值是通过计算文档Dj中出现的所有标引词来获得的。如果标引词Ki没有出现在文档Dj中，则Fij=0。标引词Ki的IDF为IDFi=log(N/ni)标引词Ki在文档Dj中的权重Wij=Fij*IDFi向量空间模型例如：文档总数为1000，出现关键词k1文档为100篇，出现关键词k2文档为500篇，出现关键词k3文档为800篇N=1000,n1=100,n2=500,n3=800根据公式：idfi=log(N/ni)，可计算出idf1=3-2=1idf2=3–2.7=0.3idf3=3–2.9=0.1Idf越大，表明区别（分）文档的能力越强。TF-IDF举例说明

文本：“俄罗斯频繁发生恐怖事件，俄罗斯的安全部门加大打击恐怖主义的力度。”TFIDFTF-IDFTFIDFTF-IDF俄罗斯2较高高安全1中等高恐怖2较高高部门1较低低的2非常低很低加大1较低低频繁1较低低打击1中等高发生1较低低主义1较低低事件1较低低力度1中等高Idf计算示例查询式的词项权重如果词项出现在查询式中，则该词项在查询式中的权重为1，否则为0也可以用用户指定查询式中词项的权重一个自然语言查询式可以被看成一个文档查询式：“有没有周杰伦的歌？”

会被转换为:

<周杰伦,歌>查询式：“请帮我找关于俄罗斯和车臣之间的战争以及车臣恐怖主义首脑的资料”

会被转换为:

<俄罗斯2,车臣

2,战争1,恐怖主义1,首脑1>过滤掉了：“请帮我找”，“和”，“之间的”，“以及”，“的资料”两个文档之间的相似度可以同理计算由索引项构成向量空间2个索引项构成一个二维空间，一个文档可能包含0,1或2个索引项di=0,0 (一个索引项也不包含)dj=0,0.7 (包含其中一个索引项)dk=1,2

(包含两个索引项)类似的，3个索引项构成一个三维空间，n个索引项构成n维空间一个文档或查询式可以表示为n个元素的线性组合相似度计算相似度是一个函数，它给出两个向量之间的相似程度，查询式和文档都是向量，各类相似度存在于：两个文档之间（文本分类，聚类）两个查询式之间（常问问题集）一个查询式和一个文档之间（检索）人们曾提出大量的相似度计算方法，因为最佳的相似度计算方法并不存在。通过计算查询式和文档之间的相似度可以根据预定的重要程度对检索出来的文档进行排序可以通过强制设定某个阈值，控制被检索出来的文档的数量检索结果可以被用于相关反馈中，以便对原始的查询式进行修正。(例如：将文档向量和查询式向量进行结合)相似度度量–内积(InnerProduct)文档D

和查询式Q

可以通过内积进行计算:sim(D

,Q)=

(dik

qk)dik

是文档di中的词项k

的权重，qk

是查询式Q中词项k的权重对于二值向量,内积是查询式中的词项和文档中的词项相互匹配的数量对于加权向量,内积是查询式和文档中相互匹配的词项的权重乘积之和示例内积的特点内积值没有界限不象概率值，要在(0,1)之间对长文档有利内积用于衡量有多少词项匹配成功，而不计算有多少词项匹配失败长文档包含大量独立词项，每个词项均多次出现，因此一般而言，和查询式中的词项匹配成功的可能性就会比短文档大。余弦向量度量法用向量夹角的余弦值表示向量的相似度夹角余弦值越大，相似度越高其实质是利用向量长度对内积进行归一化2t3t1t2D1D2Q1示例示例Jaccard系数法二值化的相似度度量向量空间模型的主要优点对标引词的权重进行了改进，其权重的计算可以通过统计的办法自动完成，使问题的繁杂性大为降低，从而改进了检索效率。把文档和查询本身简化为标引词及其权重集合的向量表示，把对文档内容和查询要求的处理简化为向量空间中向量的运算。根据文档和查询之间的相似度对文献进行排序，有效地提高了检索效率。可以实现文档自动分类。（1）标引词仍然被认为是相互独立，会丢掉大量的文本结构信息，降低语义准确性。实际上，这些词项是相互关联的当你在一个文档中看到“计算机”,非常有可能同时看到“科学”当你在一个文档中看到“计算机”,有中等的可能性同时看到“商务”当你在一个文档中看到“商务”，只有很少的机会同时看到“科学”（2）相似度的计算量大，当有新文档加入时，必须重新计算词的权值。向量空间模型的主要缺点扩展布尔模型扩展布尔模型布尔模型和VSM各自有着自己的优点和不足，能否将两者结合起来，克服自身的缺点，发挥相互的长处？1983年G.Salton及其学生提出一种基于布尔逻辑框架的混合布尔、向量特性的“扩展布尔模型”。扩展布尔模型布尔模型和向量空间模型相结合，先做布尔过滤，然后进行排序：首先进行布尔查询将全部满足布尔查询的文档汇集成一个文档用向量空间法对布尔检索结果进行排序布尔过滤排序布尔查询式向量空间模型查询式文档结果如果忽略布尔关系的话，向量空间查询式和布尔查询式是相同的先“布尔”，后“排序”存在的问题如果

“与”

应用于布尔查询式,结果集可能太窄,因而影响了后面的排序过程如果

“或”

应用于布尔查询式,

就和纯向量空间模型没有区别了在第一步，如何最佳地应用布尔模型呢？提出扩展布尔模型扩展布尔模型假定文献集合中的文献Dj仅用两个标引词Kx和Ky标引，并且Kx和Ky允许被赋予一定的权值，其权值分别为Wx,j、Wy,j，权值的取值范围为[0,1]，权值越接近于1，说明该词越能反映文本的内容,反之，反映文本的内容差一些。为了简单起见，用x,y分别表示权值Wx,j、Wy,j。我们采用二维图来表示文献的提问，用距离的概念表示文献与提问的相似度。（0，0）B（1，0）A（0，1）C（1，1）D（x，y）扩展布尔模型中的“或”关系给定一个或关系的查询式：x

y假设文档di中x和y的权重被归一化在(0,1)区间内:wx,j=（tfx,j/maxl

tfl,j

）

（idfx/maxi

idfi）

sim(qor,

dj)=[(x2+y2)/2]0.5

wherex=

wx,j

andy=

wy,j

在传统布尔模型中，(0,1)、(1,0)、(1,1)几个点的相关度都是1，扩展模型中将它们加以区分，体现为“所有词都出现比只出现几个词更有价值”一个文档在(1,1)处获得最高的权重，此时意味着文档包含了全部两个查询词，并且查询词在文档中的权重也是最高的函数sim()度量了从原点出发的文档向量长度，距离越大，相似性越大。扩展布尔模型中的“与”关系给定一个联合的查询式

x

ysim(qand,

dj)=1{[(1

x)2+(1

y)2]/2}0.5函数sim()表示从(1,1)

出发到d的向量长度(1,1)wx,jwy,j(1,0)(0,1)(0,0)最期望的点dx

y在传统布尔模型中，(0,1)、(1,0)、(0,0)几个点的相关度都是0，扩展模型中将它们加以区分，体现为“出现几个词总比一词都不出现更有价值”

函数sim()度量了点(wx,wy)到点(1,1)的距离。距离越小，相似性越大。示例观察如果权值是布尔型的，x出现在文档dj中，则x在文档dj中具有权重1，否则为0当dj

包含x和y时

sim(qand,dj)=sim(qor,dj)=1当dj

既不包含x

也不包含y时

sim(qand,dj)=sim(qor,dj)=0当dj

包含x

和y二者之一时

sim(qand,dj)=1

1/20.5=0.293

sim(qor,dj)=1/20.5=0.707(1,1)wx,jwy,j(1,0)(0,1)(0,0)观察一个词项的存在将对“或”关系查询式提供0.707的增益值，但对“与”关系查询式仅提供0.293的增益值一个词项不存在，将给“与”关系的查询式提供0.707的罚分当x

和y

有权值0.5,sim(qand,d)=sim(qor,d)=0.5在一个“与”关系查询中，两个词项的权重均为0.5，则相似度为0.5。其中一个权重为1，另一个为0，相似度为0.293。在“或关系”查询中，情况恰好相反在“与关系”查询中，如果一个词项的权重低于0.5，将给相似度贡献一个较大的罚分p-norm模型扩展布尔模型可以被泛化为m

个查询项:

sim(qor,d)=[(x12+x22+...+xm2)/m]0.5

sim(qand,d)=1{[(1

x1)2+(1

x2)2+...+(1

xm)2]/m}0.5它可以被进一步地

泛化为p-normmodel:

sim(qor,d)=[(x1p+x2p

+...+xmp

)/m]1/p

sim(qand,d)=1{[(1

x1)p+(1

x2)p+...+(1

xm)p]/m}1/p当p=1时,sim(qor,d)=sim(qand,d)=(x1+x2

+...+xm

)/m通过语词-文献权值的和来求合取和析取查询的值，和向量空间中的内积相似当p=,sim(qor,d)=max(xi);sim(qand,d)=min(xi)模糊逻辑模型(Fuzzylogicmodel)扩展布尔模型的特点：与传统的布尔检索中的倒排文档技术相兼容，支持使用标准布尔逻辑表达的提问式结构；允许在文档和提问式中进行词加权处理；支持按相似度的大小排序输出检索结果；通过调整参数p的值，可灵活选择并得到不同检索结果。概率模型概率论模型主要基于概率论原理来理解和解决信息检索问题。在概率论的基础上，目前提出的检索模型主要有经典概率模型（二值独立检索模型,BinaryIndependenceRetrieval,BIR)、基于Bayesian网络的推理网络模型(InterenceNetworkModel)和信念网络模型（BeliefNetworkModel）等。概率模型经典概率模型最早在1976年由英国城市大学Robertson和Sparck-Jones提出。基本思想：给定一个用户提问，则检索系统中存在一个与该提问相关的理论命中结果集R。如果能已知R的主要特征及其描述，则用户的检索要求便不难实现。事实上，