《信息存储与检索》课件-第二章 信息检索模型

第二章信息检索模型本章目录第一节引言第二节经典模型第三节集合理论模型第四节代数模型第五节结构化模型信息存储与检索》第一节引言任何检索策略都包含3个部分：文档表示、查询表示和匹配函数。文档表示反映文档在系统中的存储形式描述，可用一组关键词或标引词表示；查询表示反映对用户信息需求的描述；匹配函数用于将经过处理的文档表示和查询表示放入系统中进行匹配，以过滤输出结果。信息检索系统的实现首先要对文档集进行索引和归档，以支持信息检索。检索式代表用户的信息需求。检索系统分析查询与文档表示，进行相似性匹配，排序返回查询结果。因此文档信息检索过程实际上涉及文档集的逻辑表示、用户查询表示、相似性匹配及其排序三个重要的处理。信息存储与检索》第一节引言信息检索模型主要从两个方面抽象地研究信息检索方法：一是确定在检索模型中如何表示构成检索系统的两个要素，即文档和检索式；二是确定在模型中如何定义和计算文档和检索式之间的关系。

检索模型的重要作用主要体现在以下几个方面：更精确地描述出文档与文档、文档与查询间的相关关系，使之能比较和计算；安排更合理、更便于检索的文档存储形式；在此基础上设计出合理的检索方式；除信息检索外，进行一些信息辅助分析工作。传统的信息检索模型（又称经典信息检索模型）包括布尔模型、向量空间模型和概率模型。

信息存储与检索》第一节引言信息检索模型到底是什么？其描述如下:

信息检索模型是一个四元组/D，Q，F，R(qi,dj)/：（1）D是文档集中的一组文档逻辑视图（表示），称为文档的表示；（2）Q是一组用户信息需求的逻辑视图（表示），这种视图（表示）称之为查询；（3）F是一种机制，用于构建文档表示，查询及它们之间关系的模型；（4）R(qi,dj)是排序函数，该函数输出一个与查询qi

∈Q和文档表示dj

∈D有关的实数，这样就在文档之间根据查询qi定义了一个顺序。信息存储与检索》第一节引言基于经典布尔模型的信息检索模型中，文档和查询用标引词集合来表示，都是建立在集合理论的基础之上，因此，我们称该类模型为集合理论模型，包括模糊集合论模型、扩展布尔模型和粗糙集模型等。基于经典向量模型的信息检索模型中，文档和查询用t维空间的向量来表示，都是建立在代数理论的基础之上，则称该类模型为代数模型，包括广义向量模型、潜语义标引模型和神经网络模型等。基于经典概率模型的信息检索模型中，用于构建文档和查询模型的机制是基于概率论的，则称该类模型为概率模型，包括推理网络模型和信任度网络模型等。信息存储与检索》第一节引言除经典模型及其改进模式外，较重要的信息检索模型还有结构化模型，主要包括：非重叠链表模型、邻近结点模型、扁平浏览模型、结构导向模型和超文本模型等。在本章中，我们将讨论以上所述的除推理网络模型和信任度网络模型外的各种信息检索模型，推理网络模型和信任度网络模型的知识结构相对较为复杂，有兴趣的同学可利用相关资料进行学习。信息存储与检索》第二节

经典模型

2.2.1

布尔模型1

2.2.2向量模型2

2.2.3

概率模型3信息存储与检索》第二节

经典模型信息检索的经典模型认为，每篇文档可以用一组有代表性的关键词即标引词集合来描述，标引词(indexterm)是文档中的词，其语义可以帮助理解文档的主题；因此，标引词常用于编制索引和概括文档的内容。对于文档中的标引词集合来说，在描述文档内容时它们的作用是不尽相同的，因而应当明确标引词与文档内容的密切程度。

信息存储与检索》第二节

经典模型用ki表示标引词，dj表示文档，wi,j

≥0为二元组(ki,dj)的权值(weight)，该权值可以用来衡量描述文档语义内容的标引词的重要性。用t表示系统中标引词的数目，K={k1,k2,...,kt}是所有标引词的集合，wi,j

＞0是文档dj中的标引词ki的权值，对于没有出现在文档文本中的标引词，其权值wi,j

=0。文档dj可以用标引词向量dj来表示：dj=(w1,j,w2,j,…,wt,j)。此外，函数gi用以返回任何t维向量中标引词ki的权值，即gi(dj)=wi,j。其中，标引词的权重通常被认为是互相独立的。信息存储与检索》2.2.1布尔模型布尔模型(BoolenModel)是基于集合理论和布尔代数的一种简单的检索模型，它假定标引词在文档中要么出现，要么不出现。因此，标引词的权值全部被设为二值数据，wi,j∈{0,1}，查询q由连接词not、and、or连接起来的多个标引词所组成，如“奥运会”、“奥运会”and“中国”、“奥运会”and（“中国”or（not“体操”））等，通过对标引词与用户给出的检索式进行逻辑比较来检索文本。

信息存储与检索》2.2.1布尔模型设文本集D中某一文本i,该文本可表示为:Di

=(t1,t2,...,tm

),其中,t1,t2,⋯,tm

为标引词,用以反映i的内容。另设用户某一检索式如下:qj=(t1andt2)or(t3nott4)或者qj=(t1∧t2)∨(t3

t4)。对于该检索式,系统响应并输出的一组文本应为:它们都含有标引词t1和t2,或者含有标引词t3,但不含有标引词t4。信息存储与检索》2.2.1布尔模型如果sim(dj,q)=1，则布尔模型表示文档与查询相关（也可能不相关），否则文档dj与查询q不相关。定义对于布尔模型而言，标引词权值变量都是二值的，即wi,j∈{0,1}，查询q是一个常规的布尔表达式。用qdnf表示查询q的析取范式，qcc表示qdnf的任意合取分量。文档dj和查询q的相似度可以定义为：信息存储与检索》2.2.1布尔模型例如检索式是“图书馆”and“档案馆”，基于表2-1的内容进行检索，那么得到的结果是文档2，假如检索条件是“图书馆”or“档案馆”，则检索结果是文档1、文档2和文档3。信息存储与检索》2.2.1布尔模型布尔检索模型是最早提出的一个信息检索模型，它具有简单、易理解、易实现等优点,故得到广泛的应用。1967年后,布尔检索正式被大型文档检索系统采用,并渐成为各种商业性联机检索系统的标准检索模式，服务信息情报界30多年,直到现在,大多数商用检索系统仍采用布尔检索。尽管布尔模型有着种种的优点,但是它的缺点仍然是明显的,它存在的主要缺陷有以下几点：(1)布尔逻辑式的构造不易全面反映用户的需求。

(2)匹配标准存在某些不合理的地方。

(3)检索结果不能按照用户定义的重要性排序输出。信息存储与检索》2.2.2

向量模型向量模型又叫向量空间模型(VectorSpaceModel,简称VSM)。由于使用二值权值(binaryweight)的布尔检索存在太多的局限，信息检索研究中便提出了一种框架以便能够进行部分匹配，即通过给查询和文档中的标引词分配非二值权值(non-binaryweight)来实现这个目标。该权值用于计算存储在系统中的文档和用户查询之间的相似度，向量模型通过对检出文档按相似度降序排列的方式来实现文档与查询的部分匹配。信息存储与检索》2.2.2

向量模型一个向量空间是由一组线性无关的基本向量组成，向量维数与向量空间维数一致，并可以通过向量空间进行描述。设文档集D中某一文档i，该文档可表示为：Di

=(t1,t2,...,tm

)，其中,t1,t2,⋯,tm

为标引词,用以反映i的内容。则相应的特征项tn能够代表文档Di能力的大小，体现了特征项在文档中的重要程度，文档Di的向量可以表示为Di(wi,1,wi,2,...,

wi,m)，其中wi,1,wi,2,...,

wi,m分别代表文档D特征项t1,t2,...,tm的特征项权重。相似度S指两个文档内容相关程度的大小，当文档以向量来表示时，可以使用向量文档向量间的距离来衡量,一般使用内积或夹角θ的余弦来计算，两者夹角越小说明相似度越高。信息存储与检索》2.2.2

向量模型由于查询也可以在同一空间里表示为一个查询向量，可以通过相似度计算公式计算出每个文档向量与查询向量的相似度，即:

Sim(D1,D2)=或Sim(D1,D2)=cosθ

=排序这个结果后与设立的阈值进行比较,如果大于阈值则页面与查询相关,保留该页面查询结果；如果小于则不相关,过滤此页。这样就可以控制查询结果的数量,加快查询速度信息存储与检索》2.2.2

向量模型图2-1文档VSM及相似度Sim(D1,D2)信息存储与检索》2.2.2

向量模型从向量空间模型的特点可以看出，在特征项确定的情况下，特征项的权重计算是文档分类的关键，特征项权重计算常用的方法有布尔函数、开根号函数、对数函数、TFIDF函数等，其中TFIDF函数应用最为广泛。设N表示系统中的文档总数，ni表示包含标引词ki的文档数目，freqi,j表示语词ki在文档dj中的初始频率（如语词ki在文档dj文本中被提及的次数）。则文档dj中语词ki的标准化频率fi,j为：fi,j=信息存储与检索》2.2.2

向量模型最大值是通过计算文档dj文本中出现的所有语词来获得的。如果语词ki不出现在文档dj中，则fi,j=0，语词ki的逆文档频率idfi为：fi,j=最著名的语词加权方案为：wi,j=fi,j

或者是这个公式的一个变形。对于查询语词的权值，Salton和Buckley指出可以采用如下方法，即wi,q=信息存储与检索》2.2.2

向量模型VSM作为基于统计学方法的一个数学模型，充分发挥了计算机量化处理文档的特长，由于它一开始并没有对特征项的权值评价、文档向量与提问向量的相似度计算等问题做出统一的规定，加之它对文本语种的无关性，使它在文本信息处理的研究与应用具有广泛的适应性。30余年来，它在文本信息出来领域一直占据非常重要的地位，近乎成为文本处理领域的经典方法，主要优点在于：（1）标引词加权改进了检索效果；（2）其部分匹配策略允许检出与查询条件相接近的文档；（3）余弦公式根据文档资料与查询之间的相似度对文档进行排序。信息存储与检索》2.2.2

向量模型在VSM的应用过程中也逐渐显现出了它的不足（1）由于特征项在文档中的不同位置代表不同的权重，而不同的关键词长度也会影响权重的大小。在传统的TFIDF

函数中，每增加一个文档都要重新计算向量，导致查询速度降低，同时由于使用频率因子，在扩大查询范围时，不可避免地会影响到查询的准确性。

（2）查询和文档向量间是依靠链接来判断的，而且判断的依据是两者间相同关键词的简单比较，但实际情况是，大量的关键词具有相同的语义，同一关键词也会有多种语义的解释描述(即产生了语义分歧)。

信息存储与检索》2.2.3

概率模型概率模型的基本思想为：根据用户的检索q，可以将文档集D中的所有文档分为两类：一类与检索需求q相关（集合R），另一类与检索需求不相关()。在同一类文档中，各标引词具有相同或相近的分布；而属于不同类的文档中，标引词应具有不同的分布。因此，通过计算文档中所有标引词的分布，就可以判定该文档与检索的相关度。

经典概率模型是由Roberson和SparckJones提出的，他对文档与检索相匹配的概率进行估计，估计值作为衡量文档相关性的尺度。

信息存储与检索》2.2.3

概率模型对于检索q，任意文档d∈D与其相关和不相关的概率分别表示为：，根据贝叶斯公式：上述两式中的后两项只与检索需求q有关，而与每个文档无关，可以不计算，则将计算P(R|d)转化为计算P(d|R)。同理，对的的计算也将转化为的计算。信息存储与检索》2.2.3

概率模型由于标引词的数目很大，因此常常在计算中引入一些假设，以简化计算。对应不同的假设，就形成了三种不同的经典概率模型，分别是：二元独立模型(binaryindependentmodel)、二元一阶相关概率模型(binaryfirstorderdependentmodel)和双Poisson分布概率模型(twoPoissonindependentmodel)。

信息存储与检索》2.2.3

概率模型（一）二元独立模型二元独立模型对文档中标引词的分布做了如下两个假设：

假设1（二元属性取值）任意一个文档d可以表示为d(x1,x2,…,xi,…)，其中二元随机变量xi表示标引词ti是否在该文档中出现，如果出现，则xi=1；否则xi=0。

假设2（标引词独立性假设）在一个文档中，任意一个标引词的出现与否不会影响到其它标引词的出现，它们之间相互独立。根据假设1和2有：信息存储与检索》2.2.3

概率模型至此，我们可以定义文档d与检索q的相关度排序函数fr(q,d)为：

该值越大，表示文档d与检索q越相关，将第一式与第二式代入第三式，去掉常数并整理后有：信息存储与检索》2.2.3

概率模型其中，。对上式右边取对数并整理，就得到相关度排序函数的计算公式为：

上式中需要确定的参数为pi，qi，它们分别表示标引词ti在两类文档R和中的出现概率，如果能够预先得到一定数量的带有标记（相关性标记）的文档，则可以通过最大似然估计法来确定参数pi，qi的值。

信息存储与检索》2.2.3

概率模型假设对给定的文档集的统计结果如表2-2所示：表2-2二元独立模型的参数估计表则信息存储与检索》2.2.3

概率模型在实际应用中，一般无法预先给出带有相关性标记的文档集，所以常常通过相关反馈(RelevantFeedback)技术来获取标记文档：即先采用其它检索技术，如全文检索技术等获得一批文档，并有用户对这些文档进行相关性标记，然后再将这些标记后的文档作为确定参数的文档集。信息存储与检索》2.2.3

概率模型（二）二元一阶相关概率模型标引词独立性假设只是为了数学上处理方便，并不符合实际情况。可以看到，一些标引词在文档中的出现往往不是相互独立，而是存在某种关系，如某些标引词经常会同时出现在一篇文档中，因此要想获得更好的检索结果，就必须考虑各个标引词之间的相互依赖关系这一信息，这就是建立二元依赖模型的背景，与二元独立模型相比，后者在假设1上与前者完全一致（也就是对文档的表示两者一致）。唯一的区别在于或者不承认假设2，从而对

和

的计算与前者不同。信息存储与检索》2.2.3

概率模型（三）双Poisson分布概率模型双Poisson分布模型最先是由Harter在研究文档标引时提出的，该模型的基本思想来源于如下的实验观察：文档中的单词可分为两类：一类单词与表达文档的主题相关，称为内容词(content-bearingwords)；另一类只完成一些语法功能，成为功能词(functionalwords)，统计实验发现：功能词在文档中的分布与内容词不同，前者出现的概率比较稳定，其波动情况可以近为泊松分布，即如果用x表示某个功能词在文档中的出现频率，则：信息存储与检索》2.2.3

概率模型

其中，u为该分布的均值，表示该功能词的平均出现频率。可见内容词在文档中的出现频率，在一定意义上反映了一个文档的主题。因此Harter假设：根据一个内容词可以将文档从主题上分为两类，同时该内容词在两类文档中的出现频率也会很不相同：一类文档的主题与该内容词相关，那么该内容词在其中的出现频率应该比较高，其波动特征可以用一个Poisson分布表示；而另一类文档的主题与内容词不相关，所以内容词在其中的出现频率应该比较低，其波动特征也可以用一个Poisson分布表示。信息存储与检索》2.2.3

概率模型综合起来，一个内容词在文档中的出现频率x可以表示为两个Poisson分布的加权组合：

其中，u，v分别为内容词在两类文档中出现频率的均值，表示了任意一个文档属于第一类的概率，该假设被称为双Poisson分布假设。只要将所有的标引词看作是内容词（其实，在实际的检索中，标引词一般都是内容词），则它们也满足2-Poisson模型，则就形成了双Poisson模型。与二元独立模型相比，2-Poisson模型的不同在于不承认假设1，其余都相同。信息存储与检索》2.2.3

概率模型概率模型的主要优点在于：它利用概率论原理，通过赋予索引词某种概率值来表示这些词在相关文档集合和非相关文档集合中的出现概率，然后计算某一给定文档与某一给定用户体温相关的概率并做出检索决策。不同于布尔检索和向量空间模型，概率模型具有一种内在的相关反馈机制，它把检索处理过程看作是一个不断逼近并最终确认命中文档集合特征的过程，并通过运用某种归纳式学习方法实现系统对检索结果的优化与完善，从理论上讲，它吸收了相关反馈原理，将文档根据它们相关的概率按递减的顺序排列。信息存储与检索》2.2.3

概率模型概率模型虽然具有坚实的理论基础，仍然存在一些局限，主要表现在：（1）需要最初把文档分成相关的集合和不相关的集合；（2）这种方法并不考虑标引词在文档中出现的频率，即所有的权值都是二值的；（3）假设标引词相互独立。然而如同VSM一样，并不能明确标引词的独立性在实际情况中是否是一个不利假设。

信息存储与检索》第三节集合理论模型

2.3.1

模糊集合模型1

2.3.2

扩展布尔模型2

2.3.3

粗糙集模型3信息存储与检索》2.3.1模糊集合模型模糊集合理论(Fuzzysettheory)研究的是边界不明确的集合的表示，其中心思想是把隶属函数(membershipfunction)和集合中的元素结合在一起。该函数的取值在区间[0,1]上，0对应于不隶属于该集合，1表示完全隶属于该集合，隶属值在0和1之间表示集合中的边际元素。因此，模糊集合中的隶属关系与在传统布尔逻辑中一样是一个逐步派生出来的固有概念，而不是突然出现的。定义论域U的一个模糊子集A可以用隶属函数来描述:→[0,1]，为U的每个元素u分配一个数值，该数值在区间[0,1]上。信息存储与检索》2.3.1模糊集合模型采用叙词表来建立模型是信息检索过程构建模型的一种常用方法，叙词表可以通过定义一个词-词关联矩阵(term-termcorrelationmatrix)C来构建，这个矩阵的行和列分别对应于文档集合中的标引词。在矩阵C中，语词ki和kl之间的标准化关联因子ci,l可以定义为：

其中ni表示包含语词ki的文档的数目，nl表示包含语词kl的文档的数目，ni,l表示同时包含语词ki、kl的文档的数目。信息存储与检索》2.3.1模糊集合模型我们可以使用语词关联矩阵C来定义与每个标引词ki相关联的模糊集合，在这个集合中，文档dj的隶属度可以计算如下：

即计算文档dj中所有语词的代数和(在此是通过负代数积求补来实现的)。如果文档dj自身的语词与ki有关，则该文档属于语词ki的模糊集合。只要文档dj中至少有一个标引词ki密切相关，则，且标引词ki是文档dj的一个很好的模糊索引；如果文档dj中的所有标引词与ki不是密切相关的，则标引词ki不是文档dj的一个好的索引（如）。信息存储与检索》2.3.1模糊集合模型用户通过一个布尔型的查询表达式来阐述他的信息需求，模糊集合模型将查询转换为析取范式。例如查询[q

=ka∧(kb∨kc)]可以写成析取范式的形式：[qdnf

=(1,1,1)∨(1,1,0)∨(1,0,0)]，其中的每一个分量都是三元组(ka,kb,kc)的一个二值加权向量，这些二值加权向量是qdnf的合取分量。用cci表示第i个合取分量的参量，则qdnf

=cc1∨cc2∨…∨ccp其中p是qdnf的合取分量的数目。计算文档与查询相关的过程类似于采用经典布尔模型进行比较的过程。其区别在于：此处的集合是松散的集合而不是布尔集合。信息存储与检索》2.3.1模糊集合模型重新考虑[q

=ka∧(kb∨kc)]，用Da表示与索引ka相关联的文档模糊集合，比如该集合由隶属度大于给定阈值K的文档dj组成；此外，用表示Da的补集，模糊集合与相关联，它是标引词ka的否定。类似地，我们可以分别定义标引词kb的模糊集合Db和标引词kc的模糊集合Dc，因为所有的集合都是模糊的，即使文档dj的文本中并不包含索引ka，该文档dj也有可能属于集合Da。信息存储与检索》2.3.1模糊集合模型查询模糊集合Dq是与qdnf三个合取分量(就cc1、cc2、cc3而言)相关联的模糊集合的并集，模糊结果集合Dq中文档dj的隶属度可以通过以下的公式来计算：，是与ki有关联的模糊集合中文档dj的隶属度。析取模糊集合中的隶属度是用代数和来计算的，而不是最常用的最大值函数。此外，合取模糊集合中的隶属度是用代数积来计算的，而不是常见的最小值函数。采用代数和与代数积得出的隶属度，比用最大值函数和最小值函数计算得出的隶属度数值的变化更小，从而更适合于信息检索系统。信息存储与检索》2.3.2扩展布尔模型扩展布尔检索模型,它是将向量检索模型与布尔检索模型融为一体，克服经典布尔模型的一些缺点。主要原因是向量空间模型简单、快捷，并能产生较好的检索效果。用部分匹配和语词加权功能来扩展布尔模型，可以使布尔查询表达式与向量模型的特征结合在一起。下面我们用矢量的方法来讨论扩展布尔模型。信息存储与检索》2.3.2扩展布尔模型设文本集中每篇文本仅由两个标引词t1和t2标引,并且t1、t2允许赋以权值,其权值范围为[0,1],权值越接近1,说明该词越能反映文本的内容,反之,越不能反映文本的内容,在扩展布尔,上述情形用平面坐标系上某点代表某一文本和用户给出的检索式,见下图。图中的横、纵坐标用t1、t2表示,其中A(0,1)表示词t1权值为0,词t2

权值为1的文本,B(1,0)表示词t1权值为1,词t2权值为0的文本,C(1,1)表示词t1、t2的权值均为1的文本,文本集D中凡是可以用t1、t2标引的文本可以用四边形OACB中某一点表示,同样,用户给出检索式后,也可用四边形OACB中某一点表示。信息存储与检索》2.3.2扩展布尔模型对于由t1和t2构成的检索式q=t1∨t2,在图2-2中只有A、B、C三点所代表的各文本才是最理想的文本,对于某一文本D来说,当D点离A、B、C三点越接近时说明相似度越大,或者说,当D点离O点越远时,相似度越大。因而D与O的距离：布尔检索矢量表示法信息存储与检索》2.3.2扩展布尔模型可以作为我们衡量一文本与查询q的相关程度的一个尺度,显然,为了使相似度控制在0与1之间,将相似度定义为:

对于由t1和t2构成的查询q=t1∧t2，只有C点才是最理想的文本,用D与C的距离：

作为衡量一文本与查询q的相关程度的一个尺度,于是,把相似度定义为:

信息存储与检索》2.3.2扩展布尔模型上述两式还可推广到对检索标引词进行加权的情形,设检索标引词t1、t2的权值分别为a,b,0≤a,b≤1,则可进一步推广为:扩展模型还给出了把标引词推广到n个时的相似度计算公式。设D=(d1,d2,…,

dn),其中表示第i个标引词ti的权值,0≤di≤1。由布尔运算符“∨”及“∧”所确定的检索式分别为:信息存储与检索》2.3.2扩展布尔模型其中ai表示第i个检索标引词ti的权值,0≤ai≤1,这里,p是一个可变的量,1≤q≤∞,在扩展布尔模型中，以前述推广式作为基本的出发点,在n个标引词生成的n维欧氏空间中应用LP矢量模公式进行欧氏模的计算,将文本和查询的相似度定义为:信息存储与检索》2.3.2扩展布尔模型扩展布尔模型是经典布尔检索模型精确匹配的严格性和向量处理模式提问的无结构性的折中，它用代数距离的方式来解释并放松了布尔操作的要求，因而有效融合了传统的布尔模型、向量空间模型的处理思想，它的主要特点有：①与传统布尔检索中的倒排档技术相兼容，支持使用标准布尔检索逻辑表达的提问式结构；②允许在稳谠和提问式中进行词加权处理；③支持按相似度的大小排序输出检索结果；④通过调整参数p的取值，可以灵活选择并得到不同的检索结果。信息存储与检索》2.3.3粗糙集模型信息检索的关键就是对相关文本进行检索来回答用户的查询。提高检索算法的有效性是一个很重要的研究目标。查询提炼是信息检索中的一个重要部分，它通过修改初始查询产生一个更高效的查询，对于那些查询不完备，还不足以进行有效检索的用户来说，这一步是非常关键的。粗糙集模型在检索和基于词汇的查询提炼之间提供了高度的完整性，因为任何时候考虑到用户的信息需求，必须保证字眼算子关系的完整性。实际上，检索操作是在查询提炼之后进行的，在检索开始之前字眼和关系被自动用来进行查询提炼，粗糙集提供了一个在检索之前对词汇进行自动挖掘的方法。信息存储与检索》2.3.3粗糙集模型粗糙集理论是波兰科学家Pawlak于1982年提出的一种处理不精确、不相容和不完全数据的新的数学工具，它的独到之处在于不需要先验知识，就可以从数据中获取潜在依赖规律。在粗糙集理论中，一个等价关系将一个非空集合划分成互不相连的等价类，根据这个关系等价类中的对象是不可区分的。全集和等价关系一同定义了一个近似空间，等价类和空集被称为这个近似空间的基本集或原子集。这样一个近似空间可以用来描述全集的任意子集，这要用到两个近似集：上近似集和下近似集，它们是这样定义的：信息存储与检索》2.3.3粗糙集模型设R是划分非空全集U的一个等价关系，近似空间为aprR=(U,R)，一个划分被定义为U/R={C1,C2,…,

Cn)，这里Ci是U/R的一个等价类，对于U的任意一个子集S，上近似集和下近似集近似描述了近似空间(U,R)中的子集S，粗糙集就可以用这两个近似集来描述。信息存储与检索》2.3.3粗糙集模型利用粗糙集在信息检索中可以将词汇建立模型。该模型是将给定范围的单词（单个词汇和段落）当作全集U，表示等价关系R的定义为字眼的相似关系，R对U产生一个划分，这样一个类中的字眼彼此都是同义的，用向量来表示文本和查询，通过近似空间aprR=(U,R)中的上、下近似集进行比较。显然文本和查询是全集的子集，分别求出它们在近似空间aprR=(U,R)中的上、下近似集。下近似集中的属性确定地描述了子集，而上近似集中的属性可能地描述了子集，这些确定性和可能性当然很大程度上是由近似空间决定的，因此，下近似集自动向核心描述靠近，而上近似集在词汇空间允许的范围内扩大了描述。信息存储与检索》2.3.3粗糙集模型当对文本和查询进行比较时，采用非自反的相似度方法，设U的两个子集S1和S2，S2作为中心：这里|-|表示边界差，然后计算：在比较中，保持S2为中心，如果上式为0，表示不匹配；上式为1，表示S2和S1之间的最大匹配。同样：在实际比较中，可以把这两个相似度结合到一个检索状态值中。

信息存储与检索》2.3.3粗糙集模型粗糙集模型也有一些局限性，比如它不能使用用权值描述的文本和查询，也不能利用除了同义词之外的字眼关系。为了解决这个问题并且使粗糙集模型在检索中更加灵活，一般将粗糙集和模糊集合理论结合起来进行扩展，使检索模型适用的范围更加广泛，更进一步地提高检索效率。

信息存储与检索》第四节代数模型

2.4.1

广义向量空间模型1

2.4.2

潜语义标引模型2

2.4.3

神经网络模型3信息存储与检索》2.4.1广义向量空间模型如前所述，对VSM而言通常有如下解释：用ki表示标引词ki的一个向量，向量模型中标引词的相互独立意味着向量集合{k1,k1,…,

kt}是线性独立的，并构成了目标子空间的基。该空间的维数就是集合中标引词的数目t。

通常，VSM中标引词之间相互独立性在某种更严格的意义上可以理解为标引词向量两两正交，即ki·kj=0。然而在实际情况中，标引词之间总存在着一定的相互关系，即不是两两正交的，一个词的出现可能会引起另外一个相关词的出现。因而，标引词向量不能作为向量空间的正交基（在向量模型中常把{k1,k1,…,

kt}作为目标子空间的基），这就导出了广义向量空间模型。

信息存储与检索》2.4.1广义向量空间模型在广义向量空间模型中，标引词向量是线性独立但不是两两正交的，标引词向量由一组更小分量所组成的正交基向量来表示，词与词之间的关系可直接由基向量表示给出较为精确的计算。系统中的标引词集合为{k1,k1,…,

kt}，其生成的布尔代数表示为<B,,∧,∨>。则文档中词出现的所有模式可以用最小项来表示。定义布尔代数<B,,∧,∨>上由x1,x2,…,

xn产生的形如

的布尔表达式称为由x1,x2,…,

xn产生的最小项，其中当=1时

=xi；当=0时

。信息存储与检索》2.4.1广义向量空间模型t个标引词生成2t个互不相同的最小项，在每个最小项中，ki和ki之一出现且只出现一次。最小项不能被进一步简化，他们构成布尔代数的基本元素；其它的任何元素都可以由基本元素的析取范式表示。令表示B的元素，则每一个基本元素可以由布尔向量

唯一确定，即：标引词也是B中的一个元素，则其可以表示成基本元素的析取式，即ki=m1∨m2∨…∨mr。

信息存储与检索》2.4.1广义向量空间模型标引词ki的向量是通过把所有最小项mr的向量相加求和得出的：式中的关联因子用于计算文档dj中标引词的权值之和，函数gi(mr)返回最小项mr中标引词的权值（通常为1）。信息存储与检索》2.4.1广义向量空间模型在广义向量空间模型中，把文档和提问表示直接转化成最小项向量的集合，然后利用标准余弦函数来计算文档向量dj和提问向量q之间的相似度，并将文档按相似度的大小以递减顺序排列输出。这种方法既考虑了语词之间的关系，又没有陷入对相似函数的复杂讨论中。

信息存储与检索》2.4.1广义向量空间模型向量空间模型和广义向量空间模型都是用标引词来概括文档和提问文本的内容，由于受到同义词、多义词的影响，语义的准确表达不仅取决于对词汇的恰当选择，而且也取决于上下文对语义概念的限定。如果没有上下文的语境而孤立地依赖于标引词的简单组配，可能导致检索效果低下，其准确性、完整性也不够理想：许多不相关的文档也有可能包括在结果集合中，没有用任何关键词进行标引的文档有可能被遗漏掉。因此，文本的思想内容虽然与标引词有关联，但相比之下，它与其中的概念关系更为密切，基于概念匹配而不是标引词匹配的潜语义标引模型较好地解决了这些问题。信息存储与检索》2.4.2潜语义标引模型在传统的向量空间模型中，文档集合中的文档被抽取成若干个标引词，每个文档由标引词构成一个文档向量空间，而每个特征项在文档集合中的各个文档中的权值集合则构成了一个特征项向量空间。两者结合在一起构成了文档集合的向量空间。但是，在检索过程中，用标引词集合来概括文档和查询的内容可能降低检索结果，其最终结果有两种情况：（1）许多不相关的文档可能包含在结果集合中；（2）没有用任何查询关键词进行标引的相关文档也有可能不被检出。产生这两种结果的原因是基于关键词集合的检索过程固有的模糊性。信息存储与检索》2.4.2潜语义标引模型潜语义标引模型(latentsemanticindexingmodel)是将标引词之间、文档之间的依赖关系以及标引词与文档之间的语义关联都考虑在内，将文档向量和提问向量映射到与语义概念相关联的较低维空间中，从而把文档的标引词空间向量转化为语义概念空间；在降维的语义概念空间中，计算文档向量和提问向量的相似度，然后根据所得的相似度把排列结果返回给用户。信息存储与检索》2.4.2潜语义标引模型设表示t行n列的关键词-文档矩阵，t表示系统中标引词的数目，n为总的文档数目，则：矩阵中的每一个元素Mi,j为关键词-文档(ki,dj)的权值，如上所示，该权值可以用传统向量空间模型中普遍采用的tf-idf加权方案来确定。潜语义标引模型的思想是用数学方法把关键词-文档矩阵进行奇异值分解。奇异值分解是一种与特征值分解、因子分析紧密相关的矩阵方法。信息存储与检索》2.4.2潜语义标引模型定义

M为t×n矩阵，MTM的特征值为：

为矩阵M的奇异值。定理任何矩阵均可以被分解成三个矩阵的乘积。所以，关键词-文档矩阵也可以分解成三个部分：

上式称为M的奇异值分解，其中矩阵是由词-词关联矩阵导出的t×t正交特征向量矩阵(kkt=ktk

=E)，称为M的左奇异向量；是由文档-文档关联矩阵导出的n×n正交特征向量矩阵(DDt=DtD=E)，称为M的右奇异向量；

信息存储与检索》2.4.2潜语义标引模型是n×n奇异值对角矩阵，对角元为

，且，此对角为M的奇异值；r=min(t,n)是矩阵M的秩。奇异值分解允许用一个维度较小的矩阵做初始矩阵的最优近似，选定一个合适的x值，保留S中的前x个最大奇异值，并保留K,D中对应的行和列，删去其余的行和列。则矩阵M的秩—x近似矩阵Mx为：其中Kx是由K的前x列组成的t×t矩阵，Sx是由S的前x行、前x行列组成的x×x矩阵，是由Dt前x行组成的x×n矩阵。信息存储与检索》2.4.2潜语义标引模型这样，通过M的秩—r近似矩阵将文档的关键词向量空间转化为语义概念空间，且语义概念空间的维度x≤t（t是文档关键词向量空间的纬度，也即系统中所使用的标引词的数量），因而，次要的术语区别就被忽略了，有相似用法的关键词，其向量也就相似，用法不同的关键词，对应的向量也就不相似，从而降低了同义词、多义词的影响，减少了冗余。值x的选择是折中的。首先，x必须足够大，以能包括所有的实数结构；其次，x又必须足够小，以便能忽略掉一些错误和不重要的描述细节。如果k值太小，那么分辨文档或标引词的能力不足；如果k值过高，则接近于传统的向量空间模型，失去了它可以表示词相互关系的能力。信息存储与检索》2.4.2潜语义标引模型在维度为x的降维空间中，两篇文档的相似度等于的两个相应列向量的点积：矩阵中的元素(i,j)是矩阵的第i、j行的点积，它量化了文档di和dj之间的关系。同理，标引词ki与文档dj的相似度是Mx的第(i,j)元素。由于

则Mx的(i,j)元素可以由的第i行与的第j行的点积得出。信息存储与检索》2.4.2潜语义标引模型为了对与用户提问相关的文档进行排序，我们通常把用户提问向量Q作为初识词-文档矩阵的一个伪文档向量（例如，假定查询被构建成数值为0的文档，那么矩阵的第一行即为关于提问的所有文档的排序）。转化为x维语义概念空间的向量后，才能在语义概念空间中进行文档相似性的比较；用户提问的转化公式为：。然后计算文档向量与提问向量的相似度，并根据相似度的计算结果，把文档排列起来返回给用户。潜语义标引模型将文档和提问向量从t维关键词向量空间转化为x维语义概念空间，降低了空间的维度，消除了基于标引词表示的描述的噪音，克服了多义词和同义词对检索的影响，提高了检索的精度。信息存储与检索》2.4.3神经网络模型神经网络是大脑中相互连接的神经元网络结构的一种过于简单化的图形表示，图中的结点(node)表示处理单元，边表示突触链接。为了模拟突触链接在大脑中随时间不断变化的强度，为神经网络的每一条边分配一定的权值；起初，结点的状态根据它的活跃值（它是一个关于初状态和接收信号的函数）来定义，依据结点的活跃值，结点A可能向邻近的结点B发送一个信号，结点B信号的强度取决于结点A和结点B之间的边的权值。用于信息检索的神经网络可以用下图来描述，在图中可以看出神经网络由三层所组成：一层表示查询语词，一层表示文档语词，第三层表示文档本身。信息存储与检索》2.4.3神经网络模型用于信息检索的神经网络模型

信息存储与检索》2.4.3神经网络模型查询语词结点通过向文档语词结点发出信号来开始推理过程，文档语词结点自身也可以向文档结点发出信号。信号从查询语词结点到文档结点（上图中从左到右）就完成了第一个阶段。神经网络在信号传递的第一个阶段之后并没有停顿下来。实际上，文档结点依次直接向文档语词结点返回新的信号，这是由于文档语词结点和文档结点之间是双向边的原因。一旦接受到这种信号，文档语词结点再次直接向文档结点发出新的信号并重复这一过程。信号在每一次反复中会逐渐衰减，传递激活过程最终会停顿下来。即使文档dl不包含任何的查询语词，它也有可能在这一过程中被激活。因此，这一过程可以解释为内置叙词表的激活。信息存储与检索》2.4.3神经网络模型为查询语词结点分配初始/固定的最大活跃值(activation)，然后查询语词结点向文档语词结点发出信号，而文档语词结点已用规范化的查询语词权值来衰减：采用查询向量的范数来规范化。信息存储与检索》2.4.3神经网络模型一旦信号到达文档语词结点，这些结点就直接向文档结点发出新的信号，这些信号已用规范化的文档语词结点的权值来衰减：采用文档向量的范数来规范化。信息存储与检索》2.4.3神经网络模型对到达文档结点的信号进行求和，在信号传播的第一个阶段之后，与文档dj相关联的文档结点的活跃值可以表示为：这是经典向量模型的准确排序。然而，神经网络设计是一个复杂问题。其复杂性主要表现在两个方面：第一，采用什么类型的网络模型；第二，网络结构和参数的确定。信息存储与检索》2.4.3神经网络模型对于神经网络设计复杂性对应的第二个方面，基于进化算法的神经网络进化学习为解决该问题提供了一条新的更有潜力的途径。进化算法(EA)是从自然进化的思想和理论发展而来的一类基于群体的随机搜索算法，包括遗传算法（GA）、进化策略(ES)、进化规划(EP)、遗传规划(GP)。进化算法着重用于解决结构性优化、非线性优化、并行计算等复杂问题。在求解问题时,其根本目标是追求群体收敛性,保证算法趋于全局最优。其中，遗传算法是进化计算中提出得最早、应用最广、研究得最深入的一种算法，它是最早用于神经网络自动设计的进化算法并且获得的实验结果也最多。信息存储与检索》2.4.3神经网络模型遗传算法主要是借助生物进化机制和遗传学原理，按照自然选择和适者生存的原则，利用简单的编码技术和繁殖机制，模拟自然界生物群体优胜劣汰的进化过程，实现对复杂问题的求解，遗传算法的运算过程是一个反复迭代过程。它操作的对象是一组编码化的可行解，即由M个个体组成的集合(又称为群体)，通过三种遗传算子——选择算子、交叉算子和变异算子不断地对其进行遗传和进化操作，并且每次都是按照优胜劣汰的规则，将适应度较高的个体以较大的概率更多地遗传到下一代，这样最终在群体中会得到一个优良的个体，使得它能达到或接近于问题的最优解。因此遗传算法有着鲜明的优点：全局优化性和鲁棒性；良好的并行性；可操作性和简单性。信息存储与检索》2.4.3神经网络模型遗传算法的基本步骤如下：（1）初始化。设置最大进化代数T；随机生成M个个体作为初识群体P(0)。（2）个体评价。计算群体P(t)中各个个体的适应度。（3）选择运算。将选择算子作用于群体。（4）交叉运算。将交叉算子作用于运算。（5）变异运算。将变异算子作用于群体。群体P(t)经过选择、交叉、变异运算之后得到下一代群体P(t+1)。（6）终止条件判断。若t≦T，则：t→t+1,转到(2)，若t>T,则以进化过程所得到的具有最大适应度的个体作为最优解输出，终止计算。信息存储与检索》2.4.3神经网络模型由于网络提供了海量信息，因此用户很难从中查找到自己感兴趣信息，而遗传算法在用户兴趣模型的提取与信息检索方面有着得天独厚的优势：（1）遗传算法是一种基于自然选择的自适应算法，它的这种特性使得它非常适合于动态环境中的应用，而通常用户的兴趣也是随着时间的变化而变化的；（2）从某种意义上来说提取用户兴趣模型也是一个优化问题；（3）遗传算法中存在演化的随机性，使得发现用户没能正确表达出来的兴趣需求成为可能。信息存储与检索》2.4.3神经网络模型在基于遗传算法的信息检索方面的研究，国际上已经有了相当一些的成果，它们有许多共同点而又各有不同侧重点。首先，在演化群体中的个体的含义方面，都是以用户模型来表示一个个体，进行演化。但是在GA的应用中，有些主要应用于用户兴趣的提取，而有些是设计来支持一个在线的信息检索的动态环境。最后在个体的适应值的评价方面，有些以适应值函数来计算值，而有些则以用户反馈来取值，这样后者的交互性更强，但同时用户在演化过程中的介于也更多，通常为了达到一个平衡，使得群体规模比较小。信息存储与检索》2.4.3神经网络模型一般说来用户兴趣模型可描述为：以一组含有权重的关键字来表示用户兴趣。Profile={(T1,W1),(T2,W2),…,(Tm,

Wm)}，其中，Ti表示关键字，Wi表示权(表示用户对该关键字的偏好)。并从中提取一组向量：P=(Wi)其次，用一个多维向量来表示Web文档的内容：Di=(fij)其中fij表示关键字Tj在文档Di中的出现频率。两个向量之间的相似度表示为：信息存储与检索》2.4.3神经网络模型用Ri表示用户对Web文档Di的评分，则提取用户兴趣模型的问题就变成了找到一个P，使得对于任意的Web文档Di，|Ri*Sim(P,Di)|都最小的优化问题。下面对用户兴趣模型的提取算法进行描述和分析：(1)从用户浏览的Web网页中提取N篇{D1,D2,…,DN}作为文档资源。文档资源的大小N取值不能太大，否则增加用户的干预负担；也不能太小，太小就不能准确地从中提取用户兴趣，一般N取10。(2)由用户分别给每篇文档Di评分Ri，以表示用户偏好。对文档的评分Ri取值为0~1.0之间的实数，最好是取一些固定的数值，如0.1，0.3，0.7和1.0等。信息存储与检索》2.4.3神经网络模型(3)分别提取文档Di的特征空间，表示为Di={(Ti1，Fi1）,（Ti2，Fi2），…，(Tim，Fim)}，其中Tij表示Di中出现频率最高的前m个单词，Fij表示Tij的出现频率。在提取文档特征空间时，需要对文档中单词出现频率进行分级，应用中取前4个等级的单词来组成这个特征空间，并注意整个过程必须排除一些介词、冠词和定冠词。(4)初始化群体P={Profile1,Profile2,⋯,Profilen}。

Tij为随机从文档的特征空间中选取的单词，Wij为一个-1~1之间的随机数值，表示权重，并由这些权重组成一个向量Pi=(Wij)。信息存储与检索》2.4.3神经网络模型

初始化群体时，每个个体的基因长度为可变量，它的长度可在初始化时随机产生一个1~15之间的数值决定。在基因权值的选取上，保持有利的值占80%左右，若权值取得都过低，会使演化的收敛速度下降。(5)当演化代数小于Maxgen时，执行下列过程：①随机选取一个个体Profilei进行变异演化，产生一个后代；②随机选取两个个体Profilej和Profilek进行杂交演化，产生两个后代；③通过适应值函数Fitness()，计算它们的适应值，取值最大的前N个个体作为下一代群体组成。信息存储与检索》2.4.3神经网络模型信息存储与检索》2.4.3神经网络模型针对于个体的变异算子有两种：一种是权值变异，即只改变个体中对应单词的权值；一种是单词变异，即个体中的单词和相应权值都改变。两个个体通过杂交算子产生两个后代，杂交算子为：随机从两个个体中选择两个基因点，然后从这个基因点开始交换两者后面的基因，从而产生两个新的个体，但要注意的是，算法中的个体基因必须唯一，也就是说在同一个体中每个基因单词都必须在个体中唯一，无论是杂交还是变异，都不能违背这一点。(6)返回适应值最好的个体作为结果，算法结束。信息存储与检索》第五节

结构化模型

2.5.1

非重叠链表模型1

2.5.2

邻近结点模型2

2.5.3

扁平浏览模型3

2.5.4

结构导向模型4

2.5.5

超文本模型5信息存储与检索》2.5.1非重叠链表模型Burkowski提出将文档的整个文本划分成若干个非重叠的文本区域，并用链表连接起来。由于将文本分为非重叠区域的方法有多种，所以会产生多种链表。比方说，我们可以构建一个文档中所有章的链表，第二个链表是关于文档中所有节的链表，第三个链表包含文档中的所有子节。这些链表彼此独立，并且有不同的数据结构。尽管相同扁平的链表中的文本区域没有重叠，但不同链表中的文本区域可能会重叠。下图阐明了同一文档中的4种不同的链表。信息存储与检索》2.5.1非重叠链表模型通过4个独立的索引链表来表示文档中的结构信息存储与检索》2.5.1非重叠链表模型为了允许对标引词和文本区域进行搜索，需要为每个链表构建一个独立的倒排文档。在这个倒排文档中，每个结构单元作为索引中的一个项。与每个项相关的是一个文本区域的链表，表示文本区域在哪些文档中出现。此外，这个链表还可以很容易地与传统的倒排文档和合并，以表示文本中的单词。因为文本区域是不重叠的，所以可以被提交的查询类型很简单：(a)选择一个包含给定单词的区域（不包含其他区域）；(b)选择一个不包含任何区域B的区域A（B属于一个不同于链表A的链表）；(c)选择一个不被包含于任何其他区域的区域。信息存储与检索》2.5.2邻近结点模型Navarro和Baeza-Yates提出了一种新的模型，该模型允许在相同文档的文本上定义独立分层（非扁平的）索引结构。每个索引都有严格的层次结构，即由章、节、段、页、行所组成，这些结构单元通常称之为结点，如下图所示。每个这样的结点都与一个文本区域相关。此外，两个不同的层次结构可能会涉及到重叠的文本区域。对于涉及不同层次结构的用户查询而言，所汇集的结果只能由来自其中一个层次结构的所有结点形成。因此，最终结果不能由两个不同层次的结点所组成，这样做的目的是允许以较少的表达式获得较快的查询处理。然而应该考虑到，由于结构是层次型的，在结果集中允许出现来自于相同层次的嵌套文本区域。

信息存储与检索》2.5.2邻近结点模型结构