信息管理和信息系统第2章.ppt

《信息管理和信息系统第2章.ppt》由会员分享，可在线阅读，更多相关《信息管理和信息系统第2章.ppt（117页珍藏版）》请在三一办公上搜索。

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

2、排序三个重要的处理。,3,第一节 引言,信息检索模型主要从两个方面抽象地研究信息检索方法：一是确定在检索模型中如何表示构成检索系统的两个要素，即文档和检索式；二是确定在模型中如何定义和计算文档和检索式之间的关系。检索模型的重要作用主要体现在以下几个方面：更精确地描述出文档与文档、文档与查询间的相关关系，使之能比较和计算；安排更合理、更便于检索的文档存储形式；在此基础上设计出合理的检索方式；除信息检索外，进行一些信息辅助分析工作。传统的信息检索模型（又称经典信息检索模型）包括布尔模型、向量空间模型和概率模型。,4,第一节 引言,信息检索模型到底是什么？其描述如下:信息检索模型是一个四元组/D，Q

3、，F，R(qi,dj)/：（1）D是文档集中的一组文档逻辑视图（表示），称为文档的表示；（2）Q是一组用户信息需求的逻辑视图（表示），这种视图（表示）称之为查询；（3）F是一种机制，用于构建文档表示，查询及它们之间关系的模型；（4）R(qi,dj)是排序函数，该函数输出一个与查询qi Q和文档表示dj D有关的实数，这样就在文档之间根据查询qi定义了一个顺序。,5,第一节 引言,基于经典布尔模型的信息检索模型中，文档和查询用标引词集合来表示，都是建立在集合理论的基础之上，因此，我们称该类模型为集合理论模型，包括模糊集合论模型、扩展布尔模型和粗糙集模型等。基于经典向量模型的信息检索模型中，文档和

4、查询用t维空间的向量来表示，都是建立在代数理论的基础之上，则称该类模型为代数模型，包括广义向量模型、潜语义标引模型和神经网络模型等。基于经典概率模型的信息检索模型中，用于构建文档和查询模型的机制是基于概率论的，则称该类模型为概率模型，包括推理网络模型和信任度网络模型等。,6,第一节 引言,除经典模型及其改进模式外，较重要的信息检索模型还有结构化模型，主要包括：非重叠链表模型、邻近结点模型、扁平浏览模型、结构导向模型和超文本模型等。在本章中，我们将讨论以上所述的除推理网络模型和信任度网络模型外的各种信息检索模型，推理网络模型和信任度网络模型的知识结构相对较为复杂，有兴趣的同学可利用相关资料进行学

5、习。,7,第二节 经典模型,2.2.3 概率模型,3,8,第二节 经典模型,信息检索的经典模型认为，每篇文档可以用一组有代表性的关键词即标引词集合来描述，标引词(index term)是文档中的词，其语义可以帮助理解文档的主题；因此，标引词常用于编制索引和概括文档的内容。对于文档中的标引词集合来说，在描述文档内容时它们的作用是不尽相同的，因而应当明确标引词与文档内容的密切程度。,9,第二节 经典模型,用ki表示标引词，dj表示文档，wi,j 0为二元组(ki,dj)的权值(weight)，该权值可以用来衡量描述文档语义内容的标引词的重要性。用t表示系统中标引词的数目，K=k1,k2,.,kt是

6、所有标引词的集合，wi,j 0是文档dj中的标引词ki的权值，对于没有出现在文档文本中的标引词，其权值wi,j=0。文档dj可以用标引词向量dj来表示：dj=(w1,j,w2,j,wt,j)。此外，函数gi用以返回任何t维向量中标引词ki的权值，即gi(dj)=wi,j。其中，标引词的权重通常被认为是互相独立的。,10,2.2.1 布尔模型,布尔模型(Boolen Model)是基于集合理论和布尔代数的一种简单的检索模型，它假定标引词在文档中要么出现，要么不出现。因此，标引词的权值全部被设为二值数据，wi,j0,1，查询q由连接词not、and、or连接起来的多个标引词所组成，如“奥运会”、“

7、奥运会”and“中国”、“奥运会”and（“中国”or（not“体操”）等，通过对标引词与用户给出的检索式进行逻辑比较来检索文本。,11,2.2.1 布尔模型,设文本集D中某一文本i,该文本可表示为:Di=(t1,t2,.,tm),其中,t1,t2,tm 为标引词,用以反映i的内容。另设用户某一检索式如下:qj=(t1 and t2)or(t3 not t4)或者qj=(t1 t2)(t3-t4)。对于该检索式,系统响应并输出的一组文本应为:它们都含有标引词t1和t2,或者含有标引词t3,但不含有标引词t4。,12,2.2.1 布尔模型,如果sim(dj,q)=1，则布尔模型表示文档与查询相关

8、（也可能不相关），否则文档dj与查询q不相关。,定义 对于布尔模型而言，标引词权值变量都是二值的，即wi,j0,1，查询q是一个常规的布尔表达式。用qdnf表示查询q的析取范式，qcc表示qdnf的任意合取分量。文档dj和查询q的相似度可以定义为：,13,2.2.1 布尔模型,例如检索式是“图书馆”and“档案馆”，基于表2-1的内容进行检索，那么得到的结果是文档2，假如检索条件是“图书馆”or“档案馆”，则检索结果是文档1、文档2和文档3。,14,2.2.1 布尔模型,布尔检索模型是最早提出的一个信息检索模型，它具有简单、易理解、易实现等优点,故得到广泛的应用。1967年后,布尔检索正式被大

9、型文档检索系统采用,并渐成为各种商业性联机检索系统的标准检索模式，服务信息情报界30多年,直到现在,大多数商用检索系统仍采用布尔检索。尽管布尔模型有着种种的优点,但是它的缺点仍然是明显的,它存在的主要缺陷有以下几点：(1)布尔逻辑式的构造不易全面反映用户的需求。(2)匹配标准存在某些不合理的地方。(3)检索结果不能按照用户定义的重要性排序输出。,15,2.2.2 向量模型,向量模型又叫向量空间模型(Vector Space Model,简称VSM)。由于使用二值权值(binary weight)的布尔检索存在太多的局限，信息检索研究中便提出了一种框架以便能够进行部分匹配，即通过给查询和文档中的

10、标引词分配非二值权值(non-binary weight)来实现这个目标。该权值用于计算存储在系统中的文档和用户查询之间的相似度，向量模型通过对检出文档按相似度降序排列的方式来实现文档与查询的部分匹配。,16,2.2.2 向量模型,一个向量空间是由一组线性无关的基本向量组成，向量维数与向量空间维数一致，并可以通过向量空间进行描述。设文档集D中某一文档i，该文档可表示为：Di=(t1,t2,.,tm)，其中,t1,t2,tm 为标引词,用以反映i的内容。则相应的特征项tn能够代表文档Di能力的大小，体现了特征项在文档中的重要程度，文档Di的向量可以表示为Di(wi,1,wi,2,.,wi,m)，

11、其中wi,1,wi,2,.,wi,m分别代表文档D 特征项t1,t2,.,tm的特征项权重。相似度S指两个文档内容相关程度的大小，当文档以向量来表示时，可以使用向量文档向量间的距离来衡量,一般使用内积或夹角的余弦来计算，两者夹角越小说明相似度越高。,17,2.2.2 向量模型,由于查询也可以在同一空间里表示为一个查询向量，可以通过相似度计算公式计算出每个文档向量与查询向量的相似度，即:,Sim(D1,D2)=,或,Sim(D1,D2)=cos=,排序这个结果后与设立的阈值进行比较,如果大于阈值则页面与查询相关,保留该页面查询结果；如果小于则不相关,过滤此页。这样就可以控制查询结果的数量,加快查

12、询速度,18,2.2.2 向量模型,图2-1 文档VSM及相似度Sim(D1,D2),19,2.2.2 向量模型,从向量空间模型的特点可以看出，在特征项确定的情况下，特征项的权重计算是文档分类的关键，特征项权重计算常用的方法有布尔函数、开根号函数、对数函数、TFIDF函数等，其中TFIDF 函数应用最为广泛，它的主要思想来自于加权技术和聚类技术。可以把信息检索问题看成是一种聚类，可以把文档看成是对象C，把用户查询看成是对象集A的模糊描述。于是，信息检索就可以简化为判断哪篇文档在集合A，哪篇文档不在集合A中。这里先要解决两个问题，第一，需要明确哪些特征用于描述集合A中的对象；第二，需要明确哪些特

13、征把集合A中的对象与集合C中的其他对象区分开来。,20,2.2.2 向量模型,第一个特征集用于内部聚类相似度计算；第二个特征集用于交叉聚类的相异度计算。内部聚类相似度可以通过文档中语词的初始频率来度量，该词的频率称为TF因子。交叉聚类的相异度可以通过文档集中语词的逆频率来度量，这个因子称为逆文档频率IDF。设N表示系统中的文档总数，ni表示包含标引词ki的文档数目，freqi,j表示语词ki在文档dj中的初始频率（如语词ki在文档dj文本中被提及的次数）。则文档dj中语词ki的标准化频率fi,j为：,fi,j=,21,2.2.2 向量模型,最大值是通过计算文档dj文本中出现的所有语词来获得的。

14、如果语词ki不出现在文档dj中，则fi,j=0，语词ki的逆文档频率idfi为：,fi,j=,最著名的语词加权方案为：,wi,j=fi,j,或者是这个公式的一个变形。对于查询语词的权值，Salton和Buckley指出可以采用如下方法，即,wi,q=,22,2.2.2 向量模型,VSM作为基于统计学方法的一个数学模型，充分发挥了计算机量化处理文档的特长，由于它一开始并没有对特征项的权值评价、文档向量与提问向量的相似度计算等问题做出统一的规定，加之它对文本语种的无关性，使它在文本信息处理的研究与应用具有广泛的适应性。30余年来，它在文本信息出来领域一直占据非常重要的地位，近乎成为文本处理领域的经

15、典方法，主要优点在于：（1）标引词加权改进了检索效果；（2）其部分匹配策略允许检出与查询条件相接近的文档；（3）余弦公式根据文档资料与查询之间的相似度对文档进行排序。,23,2.2.2 向量模型,在VSM的应用过程中也逐渐显现出了它的不足（1）由于特征项在文档中的不同位置代表不同的权重，而不同的关键词长度也会影响权重的大小。在传统的TFIDF 函数中，每增加一个文档都要重新计算向量，导致查询速度降低，同时由于使用频率因子，在扩大查询范围时，不可避免地会影响到查询的准确性。（2）查询和文档向量间是依靠链接来判断的，而且判断的依据是两者间相同关键词的简单比较，但实际情况是，大量的关键词具有相同的语

16、义，同一关键词也会有多种语义的解释描述(即产生了语义分歧)。,24,2.2.3 概率模型,概率模型的基本思想为：根据用户的检索q，可以将文档集D中的所有文档分为两类：一类与检索需求q相关（集合R），另一类与检索需求不相关(R)。在同一类文档中，各标引词具有相同或相近的分布；而属于不同类的文档中，标引词应具有不同的分布。因此，通过计算文档中所有标引词的分布，就可以判定该文档与检索的相关度。经典概率模型是由Roberson和Sparck Jones提出的，他对文档与检索相匹配的概率进行估计，估计值作为衡量文档相关性的尺度。,25,2.2.3 概率模型,对于检索q，任意文档dD与其相关和不相关的概率

17、分别表示为：,，根据贝叶斯公式：,上述两式中的后两项只与检索需求q有关，而与每个文档无关，可以不计算，则将计算P(R|d)转化为计算P(d|R)。同理，对 的的计算也将转化为 的计算。,26,2.2.3 概率模型,由于标引词的数目很大，因此常常在计算中引入一些假设，以简化计算。对应不同的假设，就形成了三种不同的经典概率模型，分别是：二元独立模型(binary independent model)、二元一阶相关概率模型(binary first order dependent model)和双Poisson分布概率模型(two Poisson independent model)。,27,2.2

18、.3 概率模型,（一）二元独立模型 二元独立模型对文档中标引词的分布做了如下两个假设：假设1（二元属性取值）任意一个文档d可以表示为d(x1,x2,xi,)，其中二元随机变量xi表示标引词ti是否在该文档中出现，如果出现，则xi=1；否则xi=0。假设2（标引词独立性假设）在一个文档中，任意一个标引词的出现与否不会影响到其它标引词的出现，它们之间相互独立。根据假设1和2有：,28,2.2.3 概率模型,至此，我们可以定义文档d与检索q的相关度排序函数fr(q,d)为：,该值越大，表示文档d与检索q越相关，将第一式与第二式代入第三式，去掉常数并整理后有：,29,2.2.3 概率模型,其中，。对上

19、式右边取对数并整理，就得到相关度排序函数的计算公式为：,上式中需要确定的参数为pi，qi，它们分别表示标引词ti在两类文档R和 R中的出现概率，如果能够预先得到一定数量的带有标记（相关性标记）的文档，则可以通过最大似然估计法来确定参数pi，qi的值。,30,2.2.3 概率模型,假设对给定的文档集的统计结果如表2-2所示：,表2-2 二元独立模型的参数估计表,则,31,2.2.3 概率模型,在实际应用中，一般无法预先给出带有相关性标记的文档集，所以常常通过相关反馈(Relevant Feedback)技术来获取标记文档：即先采用其它检索技术，如全文检索技术等获得一批文档，并有用户对这些文档进行

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

21、Poisson分布模型最先是由Harter在研究文档标引时提出的，该模型的基本思想来源于如下的实验观察：文档中的单词可分为两类：一类单词与表达文档的主题相关，称为内容词(content-bearing words)；另一类只完成一些语法功能，成为功能词(functional words)，统计实验发现：功能词在文档中的分布与内容词不同，前者出现的概率比较稳定，其波动情况可以近为泊松分布，即如果用x表示某个功能词在文档中的出现频率，则：,34,2.2.3 概率模型,其中，u为该分布的均值，表示该功能词的平均出现频率。可见内容词在文档中的出现频率，在一定意义上反映了一个文档的主题。因此Harter

22、假设：根据一个内容词可以将文档从主题上分为两类，同时该内容词在两类文档中的出现频率也会很不相同：一类文档的主题与该内容词相关，那么该内容词在其中的出现频率应该比较高，其波动特征可以用一个Poisson分布表示；而另一类文档的主题与内容词不相关，所以内容词在其中的出现频率应该比较低，其波动特征也可以用一个Poisson分布表示。,35,2.2.3 概率模型,综合起来，一个内容词在文档中的出现频率x可以表示为两个Poisson分布的加权组合：,其中，u，v分别为内容词在两类文档中出现频率的均值，表示了任意一个文档属于第一类的概率，该假设被称为双Poisson分布假设。只要将所有的标引词看作是内容词

23、（其实，在实际的检索中，标引词一般都是内容词），则它们也满足2-Poisson模型，则就形成了双Poisson模型。与二元独立模型相比，2-Poisson模型的不同在于不承认假设1，其余都相同。,36,2.2.3 概率模型,概率模型的主要优点在于：它利用概率论原理，通过赋予索引词某种概率值来表示这些词在相关文档集合和非相关文档集合中的出现概率，然后计算某一给定文档与某一给定用户提问相关的概率并做出检索决策。不同于布尔检索和向量空间模型，概率模型具有一种内在的相关反馈机制，它把检索处理过程看作是一个不断逼近并最终确认命中文档集合特征的过程，并通过运用某种归纳式学习方法实现系统对检索结果的优化与完

24、善，从理论上讲，它吸收了相关反馈原理，将文档根据它们相关的概率按递减的顺序排列。,37,2.2.3 概率模型,概率模型虽然具有坚实的理论基础，仍然存在一些局限，主要表现在：（1）需要最初把文档分成相关的集合和不相关的集合；（2）这种方法并不考虑标引词在文档中出现的频率，即所有的权值都是二值的；（3）假设标引词相互独立。然而如同VSM一样，并不能明确标引词的独立性在实际情况中是否是一个不利假设。,38,第三节 集合理论模型,2.3.3 粗糙集模型,3,39,2.3.1 模糊集合模型,模糊集合理论(Fuzzy set theory)研究的是边界不明确的集合的表示，其中心思想是把隶属函数(membe

25、rship function)和集合中的元素结合在一起。该函数的取值在区间0,1上，0对应于不隶属于该集合，1表示完全隶属于该集合，隶属值在0和1之间表示集合中的边际元素。因此，模糊集合中的隶属关系与在传统布尔逻辑中一样是一个逐步派生出来的固有概念，而不是突然出现的。定义 论域U的一个模糊子集A可以用隶属函数来描述:0,1，为U的每个元素u分配一个数值，该数值在区间0,1上。,40,2.3.1 模糊集合模型,采用叙词表来建立模型是信息检索过程构建模型的一种常用方法，叙词表可以通过定义一个词-词关联矩阵(term-term correlation matrix)C来构建，这个矩阵的行和列分别对应

26、于文档集合中的标引词。在矩阵C中，语词ki和kl之间的标准化关联因子ci,l可以定义为：其中ni表示包含语词ki的文档的数目，nl表示包含语词kl的文档的数目，ni,l表示同时包含语词ki、kl的文档的数目。,41,2.3.1 模糊集合模型,我们可以使用语词关联矩阵C来定义与每个标引词ki相关联的模糊集合，在这个集合中，文档dj的隶属度可以计算如下：即计算文档dj中所有语词的代数和(在此是通过负代数积求补来实现的)。如果文档dj自身的语词与ki有关，则该文档属于语词ki的模糊集合。只要文档dj中至少有一个标引词ki密切相关，则，且标引词ki是文档dj的一个很好的模糊索引；如果文档dj中的所有标

27、引词与ki不是密切相关的，则标引词ki不是文档dj的一个好的索引（如）。,42,2.3.1 模糊集合模型,用户通过一个布尔型的查询表达式来阐述他的信息需求，模糊集合模型将查询转换为析取范式。例如查询q=ka(kb kc)可以写成析取范式的形式：qdnf=(1,1,1)(1,1,0)(1,0,0)，其中的每一个分量都是三元组(ka,kb,kc)的一个二值加权向量，这些二值加权向量是qdnf的合取分量。用cci表示第i个合取分量的参量，则qdnf=cc1cc2ccp 其中p是qdnf的合取分量的数目。计算文档与查询相关的过程类似于采用经典布尔模型进行比较的过程。其区别在于：此处的集合是松散的集合而

28、不是布尔集合。,43,2.3.1 模糊集合模型,重新考虑q=ka(kb kc)，用Da表示与索引ka相关联的文档模糊集合，比如该集合由隶属度大于给定阈值K的文档dj组成；此外，用 表示Da的补集，模糊集合 与 相关联，它是标引词ka的否定。类似地，我们可以分别定义标引词kb的模糊集合Db和标引词kc的模糊集合Dc，因为所有的集合都是模糊的，即使文档dj的文本中并不包含索引ka，该文档dj也有可能属于集合Da。,44,2.3.1 模糊集合模型,查询模糊集合Dq是与qdnf三个合取分量(就cc1、cc2、cc3而言)相关联的模糊集合的并集，模糊结果集合Dq中文档dj的隶属度可以通过以下的公式来计算

29、：，是与ki有关联的模糊集合中文档dj的隶属度。析取模糊集合中的隶属度是用代数和来计算的，而不是最常用的最大值函数。此外，合取模糊集合中的隶属度是用代数积来计算的，而不是常见的最小值函数。采用代数和与代数积得出的隶属度，比用最大值函数和最小值函数计算得出的隶属度数值的变化更小，从而更适合于信息检索系统。,45,2.3.2 扩展布尔模型,扩展布尔检索模型,它是将向量检索模型与布尔检索模型融为一体，克服经典布尔模型的一些缺点。主要原因是向量空间模型简单、快捷，并能产生较好的检索效果。用部分匹配和语词加权功能来扩展布尔模型，可以使布尔查询表达式与向量模型的特征结合在一起。下面我们用矢量的方法来讨论扩

30、展布尔模型。,46,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中某一点表示,同样,用户给出检索式后,也可用四边

31、形OACB 中某一点表示。,47,2.3.2 扩展布尔模型,对于由t1和t2构成的检索式q=t1 t2,在图2-2中有A、B、C三点所代表的各文本是理想的文本,对于某一文本D来说,当D点离A、B、C三点越接近时说明相似度越大,或者说,当D点离O点越远时,相似度越大。因而D与O的距离：,布尔检索矢量表示法,48,2.3.2 扩展布尔模型,可以作为我们衡量一文本与查询q的相关程度的一个尺度,显然,为了使相似度控制在0 与1 之间,将相似度定义为:对于由t1和t2构成的查询q=t1 t2，只有C 点才是最理想的文本,用D与C的距离：作为衡量一文本与查询q的相关程度的一个尺度,于是,把相似度定义为:,

32、49,2.3.2 扩展布尔模型,上述两式还可推广到对检索标引词进行加权的情形,设检索标引词t1、t2的权值分别为a,b,0 a,b 1,则可进一步推广为:扩展模型还给出了把标引词推广到n个时的相似度计算公式。设D=(d1,d2,dn),其中表示第i个标引词ti的权值,0di1。由布尔运算符“”及“”所确定的检索式分别为:,50,2.3.2 扩展布尔模型,其中ai表示第i个检索标引词ti的权值,0 ai 1,这里,p是一个可变的量,1 q,在扩展布尔模型中，以前述推广式作为基本的出发点,在n个标引词生成的n维欧氏空间中应用LP矢量模公式进行欧氏模的计算,将文本和查询的相似度定义为:,51,2.3

33、.2 扩展布尔模型,扩展布尔模型是经典布尔检索模型精确匹配的严格性和向量处理模式提问的无结构性的折中，它用代数距离的方式来解释并放松了布尔操作的要求，因而有效融合了传统的布尔模型、向量空间模型的处理思想，它的主要特点有：与传统布尔检索中的倒排档技术相兼容，支持使用标准布尔检索逻辑表达的提问式结构；允许在文档和提问式中进行词加权处理；支持按相似度的大小排序输出检索结果；通过调整参数p的取值，可以灵活选择并得到不同的检索结果。,52,2.3.3 粗糙集模型,信息检索的关键就是对相关文本进行检索来回答用户的查询。提高检索算法的有效性是一个很重要的研究目标。查询提炼是信息检索中的一个重要部分，它通过修

34、改初始查询产生一个更高效的查询，对于那些查询不完备，还不足以进行有效检索的用户来说，这一步是非常关键的。粗糙集模型在检索和基于词汇的查询提炼之间提供了高度的完整性，因为任何时候考虑到用户的信息需求，必须保证字眼算子关系的完整性。实际上，检索操作是在查询提炼之后进行的，在检索开始之前字眼和关系被自动用来进行查询提炼，粗糙集提供了一个在检索之前对词汇进行自动挖掘的方法。,53,2.3.3 粗糙集模型,粗糙集理论是波兰科学家Pawlak于1982 年提出的一种处理不精确、不相容和不完全数据的新的数学工具，它的独到之处在于不需要先验知识，就可以从数据中获取潜在依赖规律。在粗糙集理论中，一个等价关系将一

35、个非空集合划分成互不相连的等价类，根据这个关系等价类中的对象是不可区分的。全集和等价关系一同定义了一个近似空间，等价类和空集被称为这个近似空间的基本集或原子集。这样一个近似空间可以用来描述全集的任意子集，这要用到两个近似集：上近似集和下近似集，它们是这样定义的：,54,2.3.3 粗糙集模型,设R是划分非空全集U的一个等价关系，近似空间为aprR=(U,R)，一个划分被定义为U/R=C1,C2,Cn)，这里Ci是U/R的一个等价类，对于U的任意一个子集S，上近似集和下近似集近似描述了近似空间(U,R)中的子集S，粗糙集就可以用这两个近似集来描述。,55,2.3.3 粗糙集模型,利用粗糙集在信息

36、检索中可以将词汇建立模型。该模型是将给定范围的单词（单个词汇和段落）当作全集U，表示等价关系R的定义为字眼的相似关系，R对U产生一个划分，这样一个类中的字眼彼此都是同义的，用向量来表示文本和查询，通过近似空间aprR=(U,R)中的上、下近似集进行比较。显然文本和查询是全集的子集，分别求出它们在近似空间aprR=(U,R)中的上、下近似集。下近似集中的属性确定地描述了子集，而上近似集中的属性可能地描述了子集，这些确定性和可能性当然很大程度上是由近似空间决定的，因此，下近似集自动向核心描述靠近，而上近似集在词汇空间允许的范围内扩大了描述。,56,2.3.3 粗糙集模型,当对文本和查询进行比较时，

37、采用非自反的相似度方法，设U的两个子集S1和S2，S2作为中心：这里|-|表示边界差，然后计算：在比较中，保持S2为中心，如果上式为0，表示不匹配；上式为1，表示S2和S1之间的最大匹配。同样：在实际比较中，可以把这两个相似度结合到一个检索状态值中。,57,2.3.3 粗糙集模型,粗糙集模型也有一些局限性，比如它不能使用用权值描述的文本和查询，也不能利用除了同义词之外的字眼关系。为了解决这个问题并且使粗糙集模型在检索中更加灵活，一般将粗糙集和模糊集合理论结合起来进行扩展，使检索模型适用的范围更加广泛，更进一步地提高检索效率。,58,第四节 代数模型,2.4.3 神经网络模型,3,59,2.4.

38、1 广义向量空间模型,如前所述，对VSM而言通常有如下解释：用ki表示标引词ki的一个向量，向量模型中标引词的相互独立意味着向量集合k1,k2,kt是线性独立的，并构成了目标子空间的基。该空间的维数就是集合中标引词的数目t。通常，VSM中标引词之间相互独立性在某种更严格的意义上可以理解为标引词向量两两正交，即kikj=0。然而在实际情况中，标引词之间总存在着一定的相互关系，即不是两两正交的，一个词的出现可能会引起另外一个相关词的出现。因而，标引词向量不能作为向量空间的正交基（在向量模型中常把k1,k2,kt作为目标子空间的基），这就导出了广义向量空间模型。,60,2.4.1 广义向量空间模型,

39、在广义向量空间模型中，标引词向量是线性独立但不是两两正交的，标引词向量由一组更小分量所组成的正交基向量来表示，词与词之间的关系可直接由基向量表示给出较为精确的计算。系统中的标引词集合为k1,k2,kt，其生成的布尔代数表示为。则文档中词出现的所有模式可以用最小项来表示。定义 布尔代数上由x1,x2,xn产生的形如 的布尔表达式称为由x1,x2,xn产生的最小项，其中当=1时=xi；当=0 时。,61,2.4.1 广义向量空间模型,t个标引词生成2t个互不相同的最小项，在每个最小项中，ki和 ki之一出现且只出现一次。最小项不能被进一步简化，他们构成布尔代数的基本元素；其它的任何元素都可以由基本

40、元素的析取范式表示。令 表示B的元素，则每一个基本元素可以由布尔向量 唯一确定，即：标引词也是B中的一个元素，则其可以表示成基本元素的析取式，即ki=m1m2mr。,62,2.4.1 广义向量空间模型,标引词ki的向量是通过把所有最小项mr的向量相加求和得出的：式中的关联因子用于计算文档dj中标引词的权值之和，函数gi(mr)返回最小项mr中标引词的权值（通常为1）。,63,2.4.1 广义向量空间模型,在广义向量空间模型中，把文档和提问表示直接转化成最小项向量的集合，然后利用标准余弦函数来计算文档向量dj和提问向量q之间的相似度，并将文档按相似度的大小以递减顺序排列输出。这种方法既考虑了语词

41、之间的关系，又没有陷入对相似函数的复杂讨论中。,64,2.4.1 广义向量空间模型,向量空间模型和广义向量空间模型都是用标引词来概括文档和提问文本的内容，由于受到同义词、多义词的影响，语义的准确表达不仅取决于对词汇的恰当选择，而且也取决于上下文对语义概念的限定。如果没有上下文的语境而孤立地依赖于标引词的简单组配，可能导致检索效果低下，其准确性、完整性也不够理想：许多不相关的文档也有可能包括在结果集合中，没有用任何关键词进行标引的文档有可能被遗漏掉。因此，文本的思想内容虽然与标引词有关联，但相比之下，它与其中的概念关系更为密切，基于概念匹配而不是标引词匹配的潜语义标引模型较好地解决了这些问题。,

42、65,2.4.2 潜语义标引模型,在传统的向量空间模型中，文档集合中的文档被抽取成若干个标引词，每个文档由标引词构成一个文档向量空间，而每个特征项在文档集合中的各个文档中的权值集合则构成了一个特征项向量空间。两者结合在一起构成了文档集合的向量空间。但是，在检索过程中，用标引词集合来概括文档和查询的内容可能降低检索结果，其最终结果有两种情况：（1）许多不相关的文档可能包含在结果集合中；（2）没有用任何查询关键词进行标引的相关文档也有可能不被检出。产生这两种结果的原因是基于关键词集合的检索过程固有的模糊性。,66,2.4.2 潜语义标引模型,潜语义标引模型(latent semantic inde

43、xing model)是将标引词之间、文档之间的依赖关系以及标引词与文档之间的语义关联都考虑在内，将文档向量和提问向量映射到与语义概念相关联的较低维空间中，从而把文档的标引词空间向量转化为语义概念空间；在降维的语义概念空间中，计算文档向量和提问向量的相似度，然后根据所得的相似度把排列结果返回给用户。,67,2.4.2 潜语义标引模型,设 表示t行n列的关键词-文档矩阵，t表示系统中标引词的数目，n为总的文档数目，则：矩阵中的每一个元素Mi,j为关键词-文档(ki,dj)的权值，如上所示，该权值可以用传统向量空间模型中普遍采用的tf-idf加权方案来确定。潜语义标引模型的思想是用数学方法把关键词

44、-文档矩阵进行奇异值分解。奇异值分解是一种与特征值分解、因子分析紧密相关的矩阵方法。,68,2.4.2 潜语义标引模型,定义 M为tn矩阵，MTM的特征值为：为矩阵M的奇异值。定理 任何矩阵均可以被分解成三个矩阵的乘积。所以，关键词-文档矩阵也可以分解成三个部分：上式称为M的奇异值分解，其中矩阵 是由词-词关联矩阵 导出的tt正交特征向量矩阵(kkt=ktk=E)，称为M的左奇异向量；是由文档-文档关联矩阵 导出的nn正交特征向量矩阵(DDt=DtD=E)，称为M的右奇异向量；,69,2.4.2 潜语义标引模型,是nn奇异值对角矩阵，对角元为，且，此对角为M的奇异值；r=min(t,n)是矩阵

45、M的秩。奇异值分解允许用一个维度较小的矩阵做初始矩阵的最优近似，选定一个合适的x值，保留S中的前x个最大奇异值，并保留K,D中对应的行和列，删去其余的行和列。则矩阵M的秩x近似矩阵Mx为：其中Kx是由K的前x列组成的tt矩阵，Sx是由S的前x行、前x行列组成的xx矩阵，是由Dt前x行组成的xn矩阵。,70,2.4.2 潜语义标引模型,这样，通过M的秩r近似矩阵将文档的关键词向量空间转化为语义概念空间，且语义概念空间的维度xt（t是文档关键词向量空间的纬度，也即系统中所使用的标引词的数量），因而，次要的术语区别就被忽略了，有相似用法的关键词，其向量也就相似，用法不同的关键词，对应的向量也就不相似

46、，从而降低了同义词、多义词的影响，减少了冗余。值x的选择是折中的。首先，x必须足够大，以能包括所有的实数结构；其次，x又必须足够小，以便能忽略掉一些错误和不重要的描述细节。如果k值太小，那么分辨文档或标引词的能力不足；如果k值过高，则接近于传统的向量空间模型，失去了它可以表示词相互关系的能力。,71,2.4.2 潜语义标引模型,在维度为x的降维空间中，两篇文档的相似度等于 的两个相应列向量的点积：矩阵 中的元素(i,j)是矩阵 的第i、j行的点积，它量化了文档di和dj之间的关系。同理，标引词ki与文档dj的相似度是Mx的第(i,j)元素。由于 则Mx的(i,j)元素可以由 的第i行与 的第j

47、行的点积得出。,72,2.4.2 潜语义标引模型,为了对与用户提问相关的文档进行排序，我们通常把用户提问向量Q作为初识词-文档矩阵 的一个伪文档向量（例如，假定查询被构建成数值为0的文档，那么矩阵 的第一行即为关于提问的所有文档的排序）。转化为x维语义概念空间的向量 后，才能在语义概念空间中进行文档相似性的比较；用户提问的转化公式为：。然后计算文档向量与提问向量的相似度，并根据相似度的计算结果，把文档排列起来返回给用户。潜语义标引模型将文档和提问向量从t维关键词向量空间转化为x维语义概念空间，降低了空间的维度，消除了基于标引词表示的描述的噪音，克服了多义词和同义词对检索的影响，提高了检索的精度

48、。,73,2.4.3 神经网络模型,神经网络是大脑中相互连接的神经元网络结构的一种过于简单化的图形表示，图中的结点(node)表示处理单元，边表示突触链接。为了模拟突触链接在大脑中随时间不断变化的强度，为神经网络的每一条边分配一定的权值；起初，结点的状态根据它的活跃值（它是一个关于初状态和接收信号的函数）来定义，依据结点的活跃值，结点A可能向邻近的结点B发送一个信号，结点B信号的强度取决于结点A和结点B之间的边的权值。用于信息检索的神经网络可以用下图来描述，在图中可以看出神经网络由三层所组成：一层表示查询语词，一层表示文档语词，第三层表示文档本身。,74,2.4.3 神经网络模型,用于信息检索

49、的神经网络模型,75,2.4.3 神经网络模型,查询语词结点通过向文档语词结点发出信号来开始推理过程，文档语词结点自身也可以向文档结点发出信号。信号从查询语词结点到文档结点（上图中从左到右）就完成了第一个阶段。神经网络在信号传递的第一个阶段之后并没有停顿下来。实际上，文档结点依次直接向文档语词结点返回新的信号，这是由于文档语词结点和文档结点之间是双向边的原因。一旦接受到这种信号，文档语词结点再次直接向文档结点发出新的信号并重复这一过程。信号在每一次反复中会逐渐衰减，传递激活过程最终会停顿下来。即使文档dl不包含任何的查询语词，它也有可能在这一过程中被激活。因此，这一过程可以解释为内置叙词表的激

50、活。,76,2.4.3 神经网络模型,为查询语词结点分配初始/固定的最大活跃值(activation)，然后查询语词结点向文档语词结点发出信号，而文档语词结点已用规范化的查询语词 权值来衰减：采用查询向量的范数来规范化。,77,2.4.3 神经网络模型,一旦信号到达文档语词结点，这些结点就直接向文档结点发出新的信号，这些信号已用规范化的文档语词结点的权值 来衰减：采用文档向量的范数来规范化。,78,2.4.3 神经网络模型,对到达文档结点的信号进行求和，在信号传播的第一个阶段之后，与文档dj相关联的文档结点的活跃值可以表示为：这是经典向量模型的准确排序。然而，神经网络设计是一个复杂问题。其复杂