第2章-信息检索模型课件.ppt

1、第2章 信息检索模型第2章 信息检索模型2.1 检索模型定义2.2 布尔模型2.3 向量模型2.4 概率模型2.5 扩展的布尔模型2.6 扩展的向量模型2.7 扩展的概率模型2.8 小结思考题第2章 信息检索模型在现实生活中，社会成员的信息需求千差万别，获取信息的方式与途径也各式各样，但通过信息检索来获取信息是最基本的手段。基于不同信息检索系统的检索，其基本原理是相同的，它们都是对用户信息需求与系统存储的信息资源所进行的某种匹配与选择。如何进一步严密地表述和论证信息检索过程，就需要从统计规律里抽象出数学模型，以便科学地进行研究，这个过程就是建模。第2章 信息检索模型所谓数学模型，是指为了某种特

2、定目的，通过对现实世界的某一特定对象做出一些必要的简化与假设，运用适当的数学工具得到的一种数学结构。数学模型可以在对对象属性的学习中获得，它具有保留本质、抑制细节的作用，它或者能解释特定现象的状态和性质，或者能预测它的未来状况，或者能提供对处理对象的最优决策或控制。信息检索中的数学模型，就是运用数学语言和工具，对信息检索系统中的信息及其处理过程加以抽象和描述，表述为某种数学公式，再进行演绎、推断、解释和检验。为了提高信息检索的效果，研究信息检索新技术新方法，建立数学模型是一种非常科学的方法。第2章 信息检索模型信息检索模型是对真实的检索过程的抽象概括。信息检索的基本任务是找出与用户需求匹配的相

3、关文档。因此信息检索的核心问题包括如何准确地表示文档与用户查询，以及预测哪些文档与用户查询相关，哪些文档不相关。图2-1是信息检索过程的一个示意图，从图中我们可以看出，检索模型要解决的三个关键问题是：查询的表示方法、文档的表示方法、查询与文档的匹配比较方法，概括成一句话就是“两个表示，一个比较”。第2章 信息检索模型图2-1 信息检索过程示意图第2章 信息检索模型查询与文档的匹配比较方法通常取决于所采用的排序算法，排序算法可以对检出的文档进行排序，排在最前面的文档被认为最相关，因此，排序算法是信息检索系统的核心。排序算法是根据“相关度”(relevance)来计算的。关于相关度的不同假设形成了

4、不同的信息检索模型，而所采用的信息检索模型又决定了哪些文档是相关的，哪些是不相关的。人们已经在集合论、代数论、概率论三个领域分别提出了布尔模型、向量模型、概率模型这三种经典模型。经典布尔模型的框架是由一组文档集和该集合上的标准布尔运算组成的；经典向量模型的框架是由一个n维矢量空间和矢量之上的标准线性代数运算组成的；经典概率模型的框架则是集合、标准概率运算和贝叶斯(Bayes)理论。第2章 信息检索模型基于这些经典模型，人们又提出了各种不同的改进模式，称为扩展模型。这些扩展模型包括扩展的布尔模型(如模糊集合论模型和扩展布尔模型)、扩展的向量模型(如广义向量模型、潜语义标引模型和神经网络模型)、扩

5、展的概率模型(如推理网络模型、信任度网络模型和语言模型)等。图2-2是信息检索模型的分类，本章将重点介绍这些基本的检索模型和扩展模型的原理以及应用。第2章 信息检索模型图2-2 信息检索模型分类示意图第2章 信息检索模型2.1 检索模型定义检索模型定义信息检索模型需要描述清楚以下关键问题：(1)如何表示查询和文档，即从什么样的视角去看待查询和文档；(2)基于什么样的理论和机制去看待查询和文档的关系；(3)如何计算查询和文档之间的相似度。因此一个信息检索模型应该包含几个重要因素，即文档和查询的表示、文档和查询的关系，以及相关程度的排序方法。下面是信息检索模型的形式化定义1。第2章 信息检索模型定

6、义定义2-1 信息检索模型是一个四元组(D，Q，F，R(qi，dj)，其中：(1)D是表示文档集中的文档的一组文档逻辑视图；(2)Q是表示用户需求的一组逻辑视图，叫做查询；(3)F是一种机制，用来模拟文档表示、查询和它们之间的关系；(4)R(qi，dj)是排序函数，该函数输出一个表示查询qiQ和文档djD相关程度的实数，可用来对查询结果排序。第2章 信息检索模型一般而言，“相关度”是一个很难定义的概念，因为用户的需求往往是模糊的、不断变化的，另外，语言的复杂度也加深了信息检索的匹配难度。为了解决这个问题，检索模型通常需要对文档和查询的表示方法进行简化。首先假设句子中的词与词之间是相互独立的，没

7、有任何语义联系，词与词之间的顺序也无关紧要，这就是通常所说的“词袋模型”(bagofwords)。词袋方法把每个文档看做一个装满词的词袋，它认为信息检索完全是文档中的词与查询中的词的匹配，“词袋共享”假设则认为，所有查询和文档的词都来源于同一个词库，如果查询和文档共享了一些词，则它们是相关的。第2章 信息检索模型基于词袋假设，我们可以用一组有代表性的关键词，称为索引项(index term)或称索引词，来表示查询和文档。这些索引项或索引词是最能够表述文档或查询的主题的词语。定义定义2-2 索引项是从列表、文件或词典中提取的关键性的字(word)或词(phrase)，可以反映对材料内容的主要或次

8、要层次上的描述。第2章 信息检索模型索引项通常从控制词汇(controlled vocabulary)中选取，以保证相同的词具有相同的含义。索引项的选择还与具体的检索应用相关，不同的检索应用选择索引项的标准是不相同的。例如全文检索把所有词都囊括进索引项的范围之内，而一般的普通检索则选择名词为索引项，因为名词本身具有语义，人们能够比较容易理解它的意思，形容词、副词、连词很少做索引项，因为它们主要起补充作用，不能单独表示语义。这说明不同的索引项的表达作用并不是完全相同的，即不同的索引项对查询或文档的贡献不一样，有些索引项比其他的词语更重要。例如一个数百篇文档的集合，若一个词出现在每一篇文档中，则这

9、样的词通常是不能作为索引项的，因为它不能叙述文档内容；若某个词仅出现在某几篇文档中，则它可能就非常有用，因为它更能有效区别这几篇文档和其他大量文档。显然，在描述文档内容时，不同索引项具有不同的能力，因此在描述一篇文档时，可以给每个索引项赋予一个权重(term weight)，不同的权重决定了一个索引项对文档内容描述的贡献程度。如何确定权重也是检索模型要解决的问题。第2章 信息检索模型定义2-3给出了索引项的权重的形式化定义。定义定义2-3 用t表示系统中索引项的数目，ki表示第i个索引项，K=k1，k2，kt是所有索引项的集合，wi，j是文档dj中的索引项ki的权值，为非负实数，当ki没有出现

10、在文档dj中时，其对应的权值wi，j=0。文档dj可以用所有索引项对该文档的权值向量来表示：dj=(w1，j，w2，j，wt，j)。此外，函数gi用来表示索引项ki和文档dj之间的关系，即gi(dj)=wi，j。第2章 信息检索模型2.2 布尔模型布尔模型布尔模型是基于集合理论和布尔代数的一种简单的检索模型。在布尔模型中，一个文档被表示为索引项的集合，而查询则被表示为索引项的布尔组合，用“与(AND)、或(OR)、非(NOT)”连接起来，并可用括弧指示优先次序，称为布尔查询式。匹配过程则是：一个文档当且仅当它能够满足布尔查询式时，才被检索出来。布尔模型是早期信息检索系统最常用的检索模型，这是因

11、为它的概念直观，查询简单，容易理解。另外，通过使用复杂的布尔表达式，还可以方便地控制查询结果。第2章 信息检索模型布尔模型假定索引项在文档中要么出现，要么不出现，因此，索引项的权值全部被设定为二值数据，即wi，j0，1，查询q可由连接词not、and、or连接起来的多个索引项组成。因此查询q本质上是一个常规的布尔表达式，它可以表示为多个合取向量的析取，即析取范式(Disjunction Normal Form，DNF)2。例如，查询q=ka(kbkc)可以写成析取范式qdnf=(1，1，1)(1，1，0)(1，0，0)的形式，其中的每个分量都是三元组(ka，kb，kc)的二值加权向量，这些二值

12、加权向量称为qdnf的合取分量。图2-3列举了查询q的三个合取分量。第2章 信息检索模型图2-3 查询式q=ka(kbkc)的三个合取分量第2章 信息检索模型【例【例2-1】将查询式q=ka(kb kc)改写成析取范式。解：解：推演过程如下：)0,0,1()0,1,1()1,1,1()()()()()()()()()()()(cbacbacbacbabbcaccbacabacbakkkkkkkkkkkkkkkkkkkkkkkkkkkq布尔模型的文档与查询的相似度定义如下：定义定义2-4 用qdnf表示查询q的析取范式，qcc表示qdnf的任意合取分量，gi(dj)和gi(qcc)分别表示索引项

13、ki在文档dj和查询q中的权重，文档dj和查询q的相似度可以定义为：第2章 信息检索模型如果sim(dj，q)=1，则布尔模型表示文档dj与查询q相关，否则不相关。即只要查询析取范式中的任一合取分量是某一文档的布尔向量表示，则这个文档和查询相关。因此，用布尔模型进行检索的主要步骤如下所述。其他 0，|如果 1),(simccdnfcccc）且（)(qg)(dgkqqqqdijiij(2-1)第2章 信息检索模型(1)将文档集中的每个文档表示为索引项的布尔向量；(2)将查询表示为析取范式；(3)根据相似度计算公式(2-1)计算各文档与查询的相似度；(4)如果相似度为1，表示匹配，可将该文档作为结

14、果输出；如果相似度为0，表示不匹配，认为该文档不满足用户的需求。第2章 信息检索模型【例【例2-2】有一个由4个文档(d1，d2，d3，d4)组成的文档集，其中：d1=“computer information retrieval”；d2=“computer retrieval”；d3=“information”；d4=“computer information”。现在有两个查询分别为：q1=“informationretrieval”，q2=“information computer”，如果采用布尔检索模型，则这两个查询q1和q2在该文档集中分别可以检索出哪些文档？解：解：首先注意到，该文档

15、集的索引项K=k1，k2，k3=computer，information，retrieval。第一步：文档表示，根据这些索引项是否出现在该文档中，4个文档分别表示为如下布尔向量：d1=1,1,1；d2=1,0,1；d3=0,1,0；d4=1,1,0第2章 信息检索模型第二步：查询表示，两个查询分别可以表示为如下的析取范式：q1=0，1，11，1，1；q2=0，1，0 0，1，1第三步：计算各文档与查询的相似度：sim(d1,q1)=1，sim(d2,q1)=0，sim(d3,q1)=0，sim(d4,q1)=0;sim(d1,q2)=0，sim(d2,q2)=0，sim(d3,q2)=1，si

16、m(d4,q2)=0第四步，输出检索结果：对查询q1，检索结果是d1；对于查询q2，检索结果是d3。第2章 信息检索模型一般认为，布尔模型具有计算简单(simplicity)、容易理解(easy understanding)、简洁的形式化(clean formalism)等突出优点。所以早期的信息检索系统很多采用布尔模型，但是布尔模型存在一些问题，如：(1)不支持部分匹配(partial match)，检索结果都是完全匹配的，要么相关，要么不相关。而完全匹配可能导致返回太多或者太少的结果文档。(2)文档和查询表示采用布尔权重，是高度的概括，无法真实客观地反映文档和查询。(3)采用布尔模型的输出

17、结果无法进行排序，如果输出结果多，将导致用户无法选择。第2章 信息检索模型2.3 向量模型向量模型向量模型3-5又叫向量空间模型(Vector Space Model，VSM)，是基于代数的一种常用模型。向量模型试图克服布尔模型的缺陷，它采用非布尔向量来表示文档和查询，采用非二值实数表示相似度，这样输出结果就可以按照文档和查询的相似程度来进行排序了，客观上实现了部分匹配。采用向量空间模型最明显的效果就是能提供排序的结果集，这个结果集比通过布尔模型得到的结果集要合理得多，从某种意义上说，能更好地匹配用户的信息需求。第2章 信息检索模型定义定义2-5 对于向量模型，文档向量和查询向量可以分别表示如

18、下：dj=(w1，j，w2，j，wt，j)q=(w1，q，w2，q，wt，q)上面的定义中，t是系统中索引项(关键词)的数目；wi，j是二元组(ki，dj)的权值，表示索引项ki在文档dj中的权重，wi，j0；wi，q表示二元组(ki，q)的权值，表示索引项ki在查询q中的权重，wi，q0。第2章 信息检索模型按照上述向量模型的定义，信息检索系统中如果包含n个索引项，则可以建立一个n维的向量空间，每一维都代表不同的索引项，例如：(中国，广东，华南，理工，大学，)。文档向量是一个n元组，其中的每个坐标都通过对应索引项的权重来表示。权重越大，则相应索引项对该文档来说越重要。例如：(中国：0.12，

19、广东：0.8，华南：1.6，理工：3.6，大学：2.9，)。查询向量与文档向量类似，只不过查询向量中的索引项的权重表示该索引项对于用户而言的重要程度。一般说来，如果以0，1表示权重的取值范围，权重1则表示期望在文档中出现的词条，而0表示不希望出现的词条。第2章 信息检索模型2.3.1 索引项权重索引项权重向量空间模型的关键是采用索引项权重将文档或查询表示成向量。索引项的权重代表着索引项的表述能力、相关度和重要性，它的取值直接影响检索的结果。向量模型本身没有规定采用什么方法计算索引项的权重，下面介绍一些比较常用的计算权重的方法：(1)二元法。索引项在文档中出现，其权重值计为1；索引项在文档中不出

20、现，其权重值计为0。即采用布尔向量来表征文档或查询，这时，向量模型退化为布尔模型。第2章 信息检索模型(2)TF法。权重值等于索引项在文档中出现的频率，即词频(Term Frequency，TF)。设ki表示给定的索引项，dj表示文档，则TF公式如下所示：的出现次数中出现次数最多的单词在文档中出现的次数在文档jjijiddk,tf(2-2)采用词频作为权重，在一定程度上客观地反映了这样一个事实，即在某个文档中出现次数越多的索引项对该文档描述的内容贡献越大。但需要注意到，一些介词、量词、语气词如“的”、“呢”和“呀”等大量重复出现于文档中，而这些词对内容的描述性不强，因此需要考虑去除这些词的影响

21、。第2章 信息检索模型(3)TFIDF法。只采用词频来计算权重值，有时并不能很好地在文档之间进行区分。比如一个索引项在一个文档里经常出现，其TF值很高，但如果它在所有文档中都频繁出现，则它并不能很好地代表这个文档，不具有很好的区别能力。所以常常采用TFIDF来计算权重。IDF称为逆文档频率(Inverse Document Frequency)，它表示索引项的辨别能力，即这个索引项将某个文档区别于其他文档的能力。将TF和IDF结合起来表示文档和查询向量是目前最常用的方法。下面是IDF和TFIDF权重的定义：(2-3)iinNlogidf(2-4)iijjiwidftf,第2章 信息检索模型公式

22、(2-3)中：N表示文档集中文档的个数;ni表示包含索引项ki的文档个数。从上面的定义可以看到，如果wi在很多文档中普遍出现，则ni值将会很大，而idfi值则相应很小，这反映了普遍出现的单词的区分能力低的事实。如果索引项只出现于一个文档中，很有可能是这个文档的代表词，此时该索引项的idf值达到最大值，而wi的权重值wi，j也相应很大，反映了该索引项的重要程度。可以对公式(2-4)进行适当的变形。比如，tfi，j采用标准化频率fi，j代替：第2章 信息检索模型(2-5)ijijifwidf,jlljijif,freqmaxfreq(2-6)iqllqiqinNwlog)freqmaxfreq5.

23、05.0(,(2-7)式中：freqi，j表示索引项ki在文档dj中的出现频率，即索引项ki在文档dj中被提及的次数。式(2-4)、(2-6)和公式的一些变形6，是最常用的索引项加权方案，称为TF-IDF方案(TF-IDF schema)。查询中的索引项的权重可以用类似的方法计算6：第2章 信息检索模型2.3.2 相似度量相似度量 前面已经介绍过，在向量空间模型中，查询和文档都可用向量来表示，因此，在向量模型中，查询和文档的相似度计算就是比较查询向量和文档向量之间的相似程度，如图2-4所示。通过计算查询和文档之间的相似度，检索系统可以根据相似度大小对文档进行排序，作为该查询的检索输出；也可以通

24、过设定阈值，控制被检索出来的文档的数量，把相似度低于阈值的文档忽略，不输出给用户；还可用于相关反馈中，以便对原始的查询式进行修正，这将在第5章讲述。第2章 信息检索模型图2-4 余弦相似度的一个例子第2章 信息检索模型向量相似度的计算方法有很多，比较常用的方法有内积和余弦方法。(1)内积(Inner Product)法。文档向量d和查询向量q之间的相似度通过内积进行计算：(2-8)(),sim(,1qkdktkwwqd其中，wk，d是文档d中的词项k的权重，wk，q是查询q中索引项k的权重。对于二值向量，内积是查询中的索引项和文档中的索引项相互匹配的数量，对于加权向量，内积是查询式和文档中相互

25、匹配的索引项的权重乘积之和。下面是内积计算的两个例子：第2章 信息检索模型【例【例2-3】如果用二元法表示的文档d和查询向量q如下所示：d=(1,1,1,0,1,1,0)，q=(1,0,1,0,0,1,1)试用内积法计算d和q之间的相似度。解：解：根据公式(2-8)，可得：sim(d,q)=11+10+11+00+10+11+01=3得到的相似度结果说明，有3个索引项(第1、第3和第6个)既出现在查询中，又出现在文档中。【例【例2-4】如果用加权向量表示的文档d1、d2和查询q如下所示：d1=(2，3，5)，d2=(3，7，1)，q=(0，0，2)试用内积法计算相似度，并说明哪个文档和查询q更

26、相似。第2章 信息检索模型解：解：根据公式(2-8)计算，分别得到d1和查询q及d2和查询q的相似度：10250302)(),sim(,3111qkdkkwwqd2210703)(),sim(,3122qkdkkwwqd得到的相似度结果表明，d1更接近查询q，更符合用户的查询需求。要注意到，用内积计算出来的相似度几乎是没有上限的。用内积来计算相似度，相对来说，对长文档较有利，因为它可用于计算的索引项更多。同时，如果索引项多次出现，用于计算的权值更大，导致计算结果增加，更容易被检索出来。第2章 信息检索模型(2)余弦(Cosine)法是计算相似度时经常采用的一种方法，事实上，余弦相似度是利用向量

27、长度对内积进行归一化的结果，它代表两个向量之间的夹角的余弦，夹角较小的向量比较相近，因此夹角较小的查询向量和文档向量之间的相似度(余弦值)较大。余弦法相似度公式如下：(2-9)tkqktkiktkqkikiwwwwqd12,12,1,)(),sim(其中，wk，i表示文档di中的索引项k的权重，wk，q表示查询式q中索引项k的权重，t是文档集中词项的个数。第2章 信息检索模型【例【例2-5】如果用加权向量表示的文档d1、d2和查询q如下所示：d1=(2，3，5)，d2=(3，7，1)，q=(0，0，2)试用余弦法计算相似度，并说明哪个文档和查询q更相似。解：解：如果使用余弦法计算相似度，则根据

28、公式(2-9)，可得到：81.03854382),sim(1qd13.05914592),sim(2qd得到的相似度结果表明，d1更接近查询q，更符合用户的查询。第2章 信息检索模型余弦法对内积进行了规范化处理，相似度结果值被控制在0，1区间。另外，从例2-4和例2-5可看出，用余弦计算相似度，d1和查询q的相似度是d2和查询q的相似度的6倍多，而用内积计算，d1和查询q的相似度是d2和查询q的相似度的5倍，因此，余弦法提高了区分能力。同时，可以看出，内积相似度比较偏向于长文档。为了降低文档长度对相关度的影响，采用余弦相似度更合适。第2章 信息检索模型2.3.3 计算方法计算方法前面介绍了基于

29、索引项权重构造文档和查询向量，以及文档向量和查询向量的相似度的计算方法，在此基础上就可以实现基于向量模型的信息检索了。用向量模型进行检索的主要步骤如下所述。(1)根据公式(2-4)或(2-6)计算文档的索引项权重，用索引项向量表示文档。(2)根据公式(2-7)计算查询的索引项权重，用索引项向量表示查询。(3)基于公式(2-8)或(2-9)计算每个文档向量和查询向量的相似度。(4)按照文档向量和查询向量的相似度，排序输出检索结果。第2章 信息检索模型下面举例说明如何利用向量模型进行检索。【例【例2-6】文档集中有4个文档如下所示：d1=“computer information retrieva

30、l”，d2=“computer retrieval”，d3=“information”，d4=“computer information”；对下述两个查询，使用向量模型进行检索，排序输出结果是什么？q1=“informationretrieval”，q2=“informationcomputer”。解：解：文档集中的索引项K=k1，k2，k3=computer，information，retrieval，索引项个数t为3，文档数N为4。第一步：采用TF-IDF式(2-4)分别表示4个文档，得到文档的向量表示为第2章 信息检索模型计算过程如表2-1所示。0,34lg,34lg ,0,34lg,0

31、24lg,0,34lg ,24lg,34lg,34lg4321dddd第2章 信息检索模型第2章 信息检索模型第二步：采用 来表示两个查询。iqllqiqinNwlog)freqmaxfreq5.05.0(,24lg5.0,34lg,34lg5.024lg,34lg,34lg5.021qq计算过程如表2-2所示。第2章 信息检索模型第2章 信息检索模型第三步：采用余弦法计算相似度。sim(d1，q1)=0.9946 sim(d1，q2)=0.9794 sim(d2，q1)=0.9205 sim(d2，q2)=0.8156 sim(d3，q1)=0.3636 sim(d3，q2)=0.6 sim

32、(d4，q1)=0.3850 sim(d4，q2)=0.6353第四步：排序输出检索结果，对于查询q1，排序检索结果为d1，d2，d4，d3；对于查询q2，排序检索结果为d1，d2，d4，d3。通过上面的例子，可以看出向量模型的主要优点有：(1)一般来说，权重算法提高了检索的性能。很多文档用向量模型描述比用布尔模型能够得到更加正确的结果；第2章 信息检索模型(2)部分匹配的策略使得检索的结果文档集更接近用户的检索需求；(3)可以根据相似度，对文档进行排序，把排序后的结果输出给用户。向量模型也存在缺点，主要表现在：在向量模型中，关键词是被假设为相互独立的，而实际上一个文档中的索引项之间可能存在着

33、一定的联系；在查询中，不能像布尔模型一样使用逻辑关系来表示查询请求。尽管向量模型结构简单，但其适应性很强，还可以通过查询扩展和相关反馈(见第5章)，改善结果集合，重新排序输出给用户，以更接近用户的真实需求。因此，向量模型的性能相当好，向量模型已经成为目前流行的检索模型。第2章 信息检索模型2.4 概率模型概率模型与布尔模型、向量空间模型不同，概率模型7试图在一个概率框架中处理信息检索问题。其基本的思路如下：给定一个用户的查询，存在一个理想结果集(ideal answer set)，这个集合里面包含完全相关的文档，不包含任何不相关的文档。检索的过程，实际上就是追求理想结果集的过程。理想结果集具有

34、哪些属性，检索开始的时候并不清楚。所以，需要利用索引项的语义来刻画这些属性，在查询开始的时候要对理想结果集的属性作猜测。运用这个初始猜测产生一个初步的对理想结果集的概率描述，用于检索出初始的文档集。然后引入用户的交互，改善理想结果集的概率描述，以更接近用户的信息检索需求。第2章 信息检索模型用户的交互过程如下：用户浏览检出的文档，并决定哪些文本是相关的，哪些是无关的。然后，系统利用这个信息，修改理想结果集的描述。通过多次重复这个过程，使得这个描述逐步接近理想结果集。经典的概率模型是基于以下的概率原则的基本假设：给定一个用户查询q和文档集中的一个文档dj，概率模型试图估计用户查询q和文档dj相关

35、的概率，概率模型认为该相关概率只依赖于查询和文档的表示；同时，模型假设在文档集中存在一个子集，它是查询q的结果集。理想结果集记为R，它使得总体的相关概率最大。集合R中的文档被认为是与查询相关的，不在集合R中的文档则被认为是不相关的。第2章 信息检索模型对于概率模型，索引项的权重变量都是二值(Binary)的，即wi,j0，1，wi,q0，1。查询q是索引项的一个子集。设R是已知的相关文档集，是R的补集，即非相关文档集。设P(R|dj)是文档dj与查询q相关的概率，P(|dj)是文档dj与查询q不相关的概率。文档dj与查询q的相似度sim(dj，q)可用这两个概率定义如下：RR(2-10)(2-

36、11)()|()()|(),sim(RPRdPRPRdPqdjjj)|()|(),sim(jjjdRPdRPqd根据贝叶斯定理，公式(2-10)变换成：第2章 信息检索模型式中：P(dj|R)表示从相关文档集R中随机选择文档dj的概率；P(R)代表从整个文档集中随机选择一个文档是相关的概率；P(dj|)代表从中选择文档dj的概率;P()表示从整个文档集中随机选择一个文档是不相关的概率。因为对文档集中的每一个文档来说，P(R)和P()都是一样的，于是相似度可改写成：RRRR(2-12)|()|(),sim(RdPRdPqdjjj假设索引项ki是独立的，则得到：(2-13)|()|()|()|()

37、,sim(1)(1)(1)(1)(RkPRkPRkPRkPqdidgidgidgidgjjijijiji第2章 信息检索模型式中：P(ki|R)为索引项ki在R文档集的某个文档中随机出现的概率，P(|R)为索引项ki不在R文档集的某个文档中随机出现的概率；P(ki|)为索引项ki在文档集的某个文档中随机出现的概率；P(|)为索引项ki不在文档集的某个文档中随机出现的概率。显然，这几个概率之间存在如下的关系：ikRRikRR(2-14)1)|()|(1)|()|(RkPRkPRkPRkPiiii(2-15)应用公式(2-14)和(2-15)，且对式(2-13)取对数，不计常数因子，得到：)|()

38、|(1log)|(1)|(log),sim(,1RkPRkPRkPRkPwwqdiiiijiqitij(2-16)第2章 信息检索模型公式(2-16)就是概率模型中用于排序计算的表达式。但在式(2-16)中，需要计算概率P(ki|R)和P(ki|)的值。概率模型一般采取估计的方法获得概率初值，然后采用相关反馈，不断调整概率估计值，直至得到一个满意的结果集。估计P(ki|R)和P(ki|)概率初值的方法基于以下简单假设：(1)假定P(ki|R)对于所有索引项ki是一定的，通常取值0.5。(2)假定不相关的文档中索引项的分布可以通过文档集中的所有文档的索引项分布来估计。根据以上假设，则可以得到P(

39、ki|R)和P(ki|)：RRRNnRkPRkPiii)|(5.0)|(2-17)第2章 信息检索模型式中：ni表示包含索引项ki的文档的数目；N表示集合中的文档总数。在得到概率初值后，就可以利用公式(2-16)计算查询和文档的相似度，并得到一个初始排序结果集，这个结果集也许还相当粗糙，是个不准确的集合。接下来的工作就是不断调整概率，不断逼近理想结果集和用户的真正需求。将检索出的初始排序结果集记为V，它是文档集的一个子集，用Vi表示V中包含索引项ki的子集，而|Vi|和|V|分别表示相应集合中的文档个数，用以下公式改进对P(ki|R)和P(ki|)的估计。R|)|(VVRkPii(2-18)第

40、2章 信息检索模型公式(2-18)将已检出文档中索引项的分布作为P(ki|R)的概率估计；未检出的文档都是不相关的，且根据包含索引项的未检出文档在未检出文档集上的分布来估计P(ki|)，现在可以再次计算相似度了。这个过程可以重复递归进行，直至得到用户满意的效果。在利用公式(2-18)和(2-19)时，如果|V|和|Vi|的值较小，如|V|=1和|Vi|=0时，可能会引起一些计算问题。为了避免这种问题的发生，可以对这两个公式作不同的变形，式(2-20)式(2-23)是4个常用的变形公式。|)|(VNVnRkPiii(2-19)R第2章 信息检索模型(2-20)21)|(1|5.0|)|(NnRk

41、PVVRkPiiii(2-21)1|5.0|)|(1|5.0|)|(VNVnRkPVVRkPiiiii(2-22)11)|(5.0|5.0|)|(iiiiiinNnRkPVVVRkP(2-23)5.0|)|(|)(5.0|)|(5.0|5.0|)|(iiiiiiiiVVnNVnRkPVRVRkP第2章 信息检索模型综上所述，用概率模型进行检索的主要步骤如下所述：(1)用布尔向量表示文档和查询；(2)根据公式(2-17)设定概率初值，根据公式(2-16)计算每个文档向量和查询向量的相似度；(3)按照文档向量和查询向量的相似度，排序输出初始排序结果集；(4)在初始结果集，用户指定或按缺省约定选择相

42、关文档，形成相关文档集合；(5)根据公式(2-18)和(2-19)或其变形公式，计算初始概率分布；(6)重新计算各文档与查询的相似度，排序输出最终结果集。第2章 信息检索模型【例【例2-7】文档集中有3个文档d1、d2、d3，还有一个查询q，分别表示如下：d1：“Shipment of gold damaged in a fire”d2：“Delivery of silver arrived in a silver truck”d3：“Shipment of gold arrived in a truck”q：“gold silver truck”问，利用概率模型，查询q的检索结果是什么？解：

43、解：先计算文档中的所有索引项的逆文档频率(IDF)，显然N=3，则文档集中词项的IDF如下：索引项a、in和of在3个文档均有出现，其ni=3，则其idf=lg(3/3)=0。第2章 信息检索模型索引项arrived、gold、shipment和truck只在两个文档中出现，则其idf=lg(3/2)=0.176。索引项damaged、delivery、fire和silver只在一个文档中出现，则其idf=lg(3/1)=0.477。可见，a、in和of在文档集中的文档分辨能力为零，将它们去掉，只选择其他8个词项作为索引项。为了叙述方便，这些索引项被赋予一个序号，即括号内的数：arrived(

44、1)，damaged(2)，delivery(3)，fire(4)，gold(5)，silver(6)，shipment(7)，truck(8)第一步：分别用布尔向量表示文档和查询，向量中的“0”表示该索引项不在该文档中出现，向量中的“1”表示该索引项在该文档中出现，向量元素的位置就是索引项序号。则各文档和查询可表示为：第2章 信息检索模型 d1=0，1，0，1，1，0，1，0 d2=1，0，1，0，0，1，0，1 d3=1，0，0，0，1，0，1，1 q=0，0，0，0，1，1，0，1。第二步：计算相似度。初始假设如下：p(ki|R)=0.5)3()|(NNnRkpiitiiiiiijijt

45、RkPRkPRkPRkPgdgqd1)8)()|(1()|()|(1()|(log()q()(),sim(因此计算得：第2章 信息检索模型第三步：利用相关反馈，修正概率，不断逼近理想结果。相关反馈可以没有用户参加，也可以有用户参加，下面分两种情形来讨论检索的结果。(1)考虑没有用户参与，即与用户无交互。如果缺省假设检出的首个文档是相关的，其他是不相关的，则文档d2是相关的，根据以下公式及表2-3：),sim(),sim(),sim(60206.02lg2),sim(0),sim(30103.02lg21lg5.032/315.0lg),sim(312321qdqdqdqdqdqd第2章 信息检

46、索模型tiiiiiijijiiiiitRkPRkPRkPRkPqgdgqdNVNVnRkPVVRkPNV1)8()|(1()|()|(1()|(log)()(),sim()3(15.0)|(15.0)|(3&1第2章 信息检索模型第2章 信息检索模型计算得：),sim(),sim(),sim(69897.05lg),sim(65321.15lg3lg2),sim(17609.1)3log5(log25.135.235.025.0log),sim(132321qdqdqdqdqdqd在这种情形下，系统向用户输出排序结果集：d2、d3、d1。(2)考虑有用户参与，即和用户有交互的情形，例如用户认为

47、检出的两个文档d2和d1均相关，则可计算得到下列表2-4。第2章 信息检索模型第2章 信息检索模型重新计算各文档与查询的相似度：),sim(),sim(),sim(35218.094lg35.0535235.1lg35.1535235.0lg),sim(95424.09lg35.0535235.1lg35.0525335.1lg),sim(65321.092lg35.1535235.0lg),sim(132321qdqdqdqdqdqd在这种情形下，系统向用户输出排序结果集：d2、d3、d1。第2章 信息检索模型根据上面的介绍，将概率模型的主要优点总结如下：结果集可以排序输出，效果要明显优于布

48、尔模型；可以将用户的意愿加入到检索过程中，更加逼近用户的真实需求。概率模型也有如下缺点：(1)与向量模型一样，假设关键词之间相互独立；(2)需要最初把文档分为相关和不相关的集合，这是一种粗略的估计，可能存在较大的偏差；(3)在对文档和查询进行表示时，采用的是布尔值，不考虑索引项在文档中出现的次数，即所有的权重都是二值的。第2章 信息检索模型2.5 扩展的布尔模型扩展的布尔模型由于布尔模型存在一些固有缺陷，历年来，研究人员对它作了很多改进和扩展，本节主要介绍两个扩展模型：模糊集合模型和扩展布尔模型。2.5.1 模糊集合模型模糊集合模型布尔模型中，文档和查询都是用布尔值来表示的，相似度也是二值化的

49、，这样虽然简化了操作，是一种高度的抽象，但实际上完全不符合客观事实。模糊集合模型8试图用隶属度来取代布尔量，以更贴近所表示的客观事实。其主要思想是：将每一个查询词语(查询的索引项)定义为一个模糊集合，每个文档在这个集合中都有一个隶属度。第2章 信息检索模型隶属度是模糊集合理论(Fuzzy Set Theory)9中的基本概念。模糊集合理论研究的是边界不明确的集合的表示，其中心思想是把隶属函数(membership function)和集合中的元素结合在一起。该函数的取值在区间0，1上，0表示不隶属于该集合，1表示完全隶属于该集合，隶属值在0和1之间表示集合中的边界元素。定义定义2-6 论域U的

50、一个模糊子集A可以用隶属函数A来描述，A 0，1，为U的每个元素u分配一个数值A(u)，该数值在区间0，1上。模糊集合中最常用的三种运算分别为：模糊集合的补运算、两个或多个集合的并运算、两个或多个模糊集合的交运算。其定义如下：第2章 信息检索模型定义定义2-7 U表示论域，A和B分别表示U的两个模糊子集，是A关于U的补集，u表示U的元素，则有：A(2-24)(),(min()()(),(max()()(1)(uuuuuuuuBABABABAAA把系统中的所有索引项定义成一个词-词关联矩阵(term-term correlation matrix)C，该矩阵的行和列分别对应文档集中的索引项，矩阵