爱华网
第2章 检索模型与算法
检索模型提供了一种度量查询和文档之间相似度的方法。这些模型基于一种共同的理念：文档和查询共有的词项（term）越多，则认为这篇文档和该查询越相关。语言本身就客观存在着诸多的不确定性，现实中一个相同的概念可能会用多种不同的词项来表达（如new york和the big apple可能指的是同一含义 ）。另外，相同的词项也可能有很多种语义（比如bark和 duck，它们的名词形式和动词形式的意思迥然不同 。我们介绍的一些检索算法采用了相应措施来解决这些语言中的不确定性问题。
检索模型就是一种算法，该算法的处理对象是查询Q和文档集合{D1, D2,…, Dn}，处理过程就是计算每篇文档Di (1≤i≤n)和这个查询的相似度SC(Q, Di)。[注：SC是Similarity Coefficient（相似度）的缩写，有时记作RSV（Retrieval Status Value），用来表示检索状态值]。
常用的检索模型有如下几种。
向量空间模型--我们将查询和文档都表示为词项空间中的向量，进而可以计算这两个向量之间的相似度。
概率模型--基于文档集中每个词项在相关文档中出现的可能性计算出概率。对文档和查询匹配的所有词项计算联合概率，从而得出文档与查询的相似度。
语言模型--针对每一篇文档，建立一个语言模型，并且计算出各文档"生成"查询的概率。
推理网络--我们采用贝叶斯网络来推断文档和查询间的相关性。推理过程基于文档中的"证据"，这种"证据"是文档中可以作出文档相关性推断的依据。推理的可信度即为文档查询的相似度。
布尔检索--在原始的布尔查询结果中，我们对每篇文档都赋予一个得分，这样就可以进行查询结果排序。具体的做法是：将每个查询词项赋予一个权重，进而使用这个权重计算文档与查询的相似度。
LSI（隐性语义检索）--我们使用词项-文档矩阵来表示文档集中出现的词项。这个矩阵通过奇异值分解（Singular Value Decomposition，SVD）来降维，奇异值分解可以过滤掉文档中的噪声，这样两篇有相同语义的文档在多维空间中距离会比较接近。
神经网络方法--网络中包含一系列神经元（或者称作节点），这些神经元在激活查询到文档的触发链接的过程中进行传导。网络中每个链接的权重被传到文档，这些权重汇集起来作为查询和文档之间的相似度。人们往往会预先定义好一批相关文档集和不相关文档集，然后再调整神经网络链接上的权重，以达到"训练"神经网络的目的。
遗传算法--我们可以通过进化的方法来得到查找相关文档的最优查询过程。初始的查询可以使用随机的权重，也可以使用估计值。通过修改这些权重来产生新的查询。接近已知相关文档的新查询得以幸存，而 "适应度"较小的查询在随后的过程中被淘汰。
模糊集检索--每篇文档被映射到一个模糊集[这种集合不仅包含元素，还包含与每个元素相关的权重，用来表示该元素的隶属度（membership）]。该模型将布尔查询映射为模糊集的相交、合并和补集等操作，这样我们就可以计算出每篇文档与查询相关的隶属度。隶属度即为相似度。
对于一个已知的检索模型，我们可以使用许多不同的实用策略（utility）来提高检索模型的性能。我们将在第3章中详细介绍这些实用策略。需要注意的是，一些检索模型和实用策略基于完全不同的数学思想。例如，概率检索模型理论上不能与向量空间模型的同义词表（thesaurus）联合使用，然而，这种结合很有可能提高最终的检索效果。不过，当混合搭配使用基于不同数学模型的检索模型和实用策略时，我们还是要特别谨慎。
我们竭尽所能来优化查询，大多数方法是在初始查询中增加或者删除一些词项，其他的方法则仅仅是把重点放在查询的计算范围上（比如，使用子文档或者片段来代替整篇文档）。关键在于每种策略是即插即用的，且可以应用于任意一个检索模型（虽然这种情况很少出现）。
在深入研究每种检索模型的细节之前，我们希望提醒读者注意一点。在力图展现算法的原始形式时，我们有意留下不一致的形式。例如，在实现一个缓慢增长函数时，一些算法的提出者使用ln(x)而其他人则使用lg(x)。显然，我们都知道这些函数之间严格来说不过是常量积的关系。虽然它确实会带来些许误解，但是我们感觉展现原始的描述仍然有其优越性。为了清晰起见，我们尽量在不同策略中使用通用符号，并且提供一个可以运行的例子。这些例子都采用相同的查询和文档集，其具体用法与检索模型无关。
2.1 向量空间模型
向量空间模型通过向量的方式来计算相似度，其中每一篇文档用一个向量来表示，而查询同样用一个向量来表示 [Salon等人，1975]。该模型基于以下思想：大致来说，文章的语义通过所使用的词语来表达。如果可以将文档中的词语表示成一个向量，那就有可能将文档和查询进行比较，从而判定它们内容相似的程度。如果将查询也看做文档，就可以计算出文档和查询的相似度。通过文档中使用的词项进行衡量，我们认为最接近查询内容的文档是最相关文档。图2-1说明了向量空间模型的基本理念，其中包含一个查询向量和三个文档向量。
该模型主要涉及两方面工作：一是如何构建一个向量来表示文档中的词项；二是如何构建另一个向量来表示查询中的词项。接下来，我们必须选择一种方法来度量任意文档向量和查询向量的相似度。一种方法是可以比较两个向量的差值向量大小，然而由于查询一般比较短小，这会导致较大的向量看起来往往和大多数查询都不相关。判断两个向量相近性的传统方法是计算这两个向量之间夹角的大小。两个向量的夹角可以通过内积（或称点积）计算出来，然而我们并没有必要真正计算出角度的实际值--任何计算夹角的单调函数都可以达到实用的要求。我们通常使用"相似度"来代替夹角。计算相似度有多种方法，通常来说，内积效果最佳。通过以上的讨论，我们可以得到以下共识：只有文档向量和查询向量指向的方向大体一致，它们才相似。
[TR]
[TD][I]498)this.width=498;' onmousewheel = 'javascript:return big(this)' height=263 alt="" src="http://pic.aIhUaU.com/201602/15/0939250.jpg" width=291 border=0>[/TD][/TR]
[TR]
[TD]图2-1 向量空间模型[/TD][/TR]
对于文档集中每一个不同的词项（或概念），我们在向量中只记录一个分量。接下来，我们考虑在文档集中只有两个不同词项[I]498)this.width=498;' onmousewheel = 'javascript:return big(this)' height=18 alt="" src="http://pic.aIhUaU.com/201602/15/0939251.jpg" width=18 border=0> 和[I]498)this.width=498;' onmousewheel = 'javascript:return big(this)' height=20 alt="" src="http://pic.aIhUaU.com/201602/15/0939252.jpg" width=22 border=0> 的情况。所有的向量只包含两个分量：第一个分量表示词项 的出现情况，第二个分量表示词项[I]498)this.width=498;' onmousewheel = 'javascript:return big(this)' height=20 alt="" src="http://pic.aIhUaU.com/201602/15/0939252.jpg" width=22 border=0>的出现情况。构造向量最简单的方法是：当词项出现时，就在对应向量的分量处记1；如果词项未出现，就在对应的分量处记0。下面我们看一篇实际的文档，比如文档D1，其中词项[I]498)this.width=498;' onmousewheel = 'javascript:return big(this)' height=20 alt="" src="http://pic.aIhUaU.com/201602/15/0939252.jpg" width=22 border=0>出现了两次，词项[I]498)this.width=498;' onmousewheel = 'javascript:return big(this)' height=20 alt="" src="http://pic.aIhUaU.com/201602/15/0939252.jpg" width=22 border=0>出现了零次。这个文档使用二值表示方法时，对应的向量为。二值表示方法可以用来计算相似度，但是并没有考虑一个词项在文档中出现的次数。通过扩展这种表示形式，我们将词项在文档中出现的频率作为向量中各个分量的值。在这个例子中，向量可以表示为。
图2-2给出了一个简单的例子。对于文档集中每个独立的词项，我们需要在向量中定义一个分量。使用一个简单的例子，在一个只包含两个词语的语言中（只有A和I是有效的词项），所有的查询和文档都可以采用二维空间向量来表示。图2-2给出了一个查询和三篇文档，并且给出了它们的向量形式及其图形表示。查询和文档的相似度可以通过计算两个向量的距离得出。在这个例子中，可以认为文档1和查询的向量相同，从而文档1在查询结果列表中排在第一位。
[TR]
[TD][I]498)this.width=498;' onmousewheel = 'javascript:return big(this)' height=344 alt="" src="http://pic.aIhUaU.com/201602/15/0939256.jpg" width=348 border=0>[/TD][/TR]
[TR]
[TD]图2-2 只有两个词项的向量空间模型[/TD][/TR]
除了简单地给出查询词列表外，用户通常还会给出权重，该权重表示一个词项比另外一个词项更重要。这是通过在初始查询中用户人工指定词项权重来实现的。另外一种方法是自动指定权重--通过基于词项在整个文档集中出现的频率。基本思想是：不频繁出现的词的权重应该比频繁出现的词的权重更高。文献[Salton，1969；Salton，1970b]分别采用权重自动赋值与人工赋值方法计算相似度，然后进行查询比较。实验结果表明：自动赋值在查询性能上并不比和人工赋值差[Salton，1969，Salton，1970b]。遗憾的是，这些结果并没有引入词项在整个文档集中的相对权重。
在20世纪70年代，研究者深入研究了不同文档集的权重。研究结论是：如果引入不同文档集的权重，能够提升相关度排序的效果。尽管在实验中使用了相对较小的文档集，作者仍然得出一个结论："迄今为止，信息检索研究中不少事情都可以称为结论确凿，这就是其中之一。"[Robertson和Sparck Jones，1976]
我们采用更加形式化的定义，并采用稍大一些的例子来展示如何使用基于数据集频率的权重。对应于一个给定的词项，其权重使用IDF（逆文档频率）来计算。
为了给每篇文档建立一个对应的向量，可以考虑如下定义。
[TR]
[TD][I]498)this.width=498;' onmousewheel = 'javascript:return big(this)' height=138 alt="" src="http://pic.aIhUaU.com/201602/15/0939257.jpg" width=553 border=0>[/TD][/TR]
对于每一篇文档向量，都有n个分量，并且对于整个文档集中每个不同的词项，都包含一个词条。向量中的每个分量为在整个文档集中计算出来的每个词项的权重。在每篇文档中，词项权重基于词项在整个文档集中出现的频率情况以及词项在某一个特定文档中出现的频率自动赋值。词项在一篇文档中出现的频率越高，则权重越大；相反，如果词项在所有文档中出现的频率越高，则权重越小。
仅当词项在文档中出现时，文档向量中词项的权重才为非零值。对于一个包含许多小文档的大文档集，文档向量可能会包含大量的零元素。例如，一篇文档集包含10 000个不同的词项，也就是每个文档中要用10 000维的向量来表示。一个给定的只有100个不同词项的文档向量则包含9 900个零分量。
对于文档中词项的权重因素，主要综合考虑词频和逆文档频率。也就是说，我们使用下面的公式计算文档i对应的向量中第j个词条的值：
[I]498)this.width=498;' onmousewheel = 'javascript:return big(this)' height=35 alt="" src="http://pic.aIhUaU.com/201602/15/0939258.jpg" width=128 border=0>
下面我们来考虑一个包含D1和D2两篇文档的文档集，在文档D1中词"绿色"出现了十次，而在D2中"绿色"仅出现了5次。如果仅仅查询"绿色"，那么在结果中文档D1排在文档D2前面。
当我们在一篇文档检索系统中用文档集中t个不同的词项来查询时，系统将为每个文档计算维度为t的向量D(di1, di2,…,dit)。向量值使用前文所述的词项权重填充。类似地，查询中的词项构建的向量为Q(wq1, wq2,…,wqt)。
查询Q和文档Di的相似度可以简单地定义为两个向量的内积。因为查询向量和和文档向量在长度上是相似的，这种策略也常常被用来计算两篇文档的相似度。我们将在3.2节中讨论将SC应用到文档聚类中。
[I]498)this.width=498;' onmousewheel = 'javascript:return big(this)' height=50 alt="" src="http://pic.aIhUaU.com/201602/15/0939259.jpg" width=172 border=0>
