主题：[推荐]《An Introduction to Information Retrieval》参考译文之六——向量空间模型

6 向量空间模型
前文主要阐述了支持布尔检索的索引形式，对于一个查询而言，一篇文档要么满足条件，要么不满足条件。但是在处理较大规模文档检索时，通常返回的查询结果文档会远远超过用户可以浏览的数量规模。所以，信息检索系统必须要能对这些海量的查询结果进行某种排序，因此对于每篇查询结果文档而言，就需要计算它与查询的一种分值，可以反映两者的相似程度。

6．1 参量索引和区段索引（Parametric and zone indexes）
虽然可以将文档看成是由词项组成的一个序列，然而事实上，很多文档都具有特定的附加结构。由机器生成的电子文档通常使用元数据来表达这些结构内容，元数据又由很多字段组成，这些字段包含作者或者出版时间等。字段的取值可以看成是有限的，如所有的出版时间组合等。
如查询作者为莎士比亚在1601年的剧作，内容包含“alas poor Yorick”。对于内容的查询而言，还是象以前一样要使用标记列表的交操作来得到含有全部词语的文档，但是还需进一步利用参量索引来过滤。对于每个元数据的字段而言，都有一个参量索引，这也是是个倒排索引，只不过索引内容为字段而不是词项，通过它可以进行特定的字段检索。这些参量索引都可以排序，因此信息检索系统也可以进行范围检索。通常，B树是较好的数据存储结构。
区段和字段很相似，但是它的内容可以是任意内容的文本。由于这个特点，可以把区段的取值看成是无限的。如文档的标题和摘要等就是区段。区段索引就是基于区段制作的倒排索引。下图表达了区段索引的基本情况：

此主题相关图片如下：

这种做法会导致字典规模太大，所以在必要的时候，也可以采用下面的方法来表达区段索引，此时的字典会较小。而且，这种做法还有助于快速计算加权区段分值（weighted zone scoring）。

此主题相关图片如下：

前面已经介绍了基于字段和区段的布尔检索形式。其实，字段和区段不仅可以用于一般的布尔检索中，还可以具有其他的用途。
给定布尔查询q和文档d，可以给两者的组合（q，d）设定一个分值，它的范围为0到1，这个分值由相应的区段分值线形组合计算而来，而每个区段的分值则只有两种布尔值，所以被称为加权区段分值。具体来看，假设一组文档共有L个区段组成，设g1，…，gL都是取值位于0到1的数值，它们的总和为1，对于这些数值的设定可以反映某种人们所期望的检索特点，如标题的权值就可以大于摘要的权值等，甚至可以机器学习算法来得到。对于查询q而言，它在i区段上的布尔值si只有两个，如在该区段上具有全部的查询词语，则si为1，否则为0。事实上，也可以使用其他的计算形式，如只要该区段具有一个查询词语即可等。因此，加权区段分值可以定义为：

此主题相关图片如下：

这种布尔检索方式也被称为有序布尔检索（ranked Boolean retrieval）。
如何计算加权区段分值呢？简单的方法就是依次计算每篇文档不同区段的分值，然后合并为整篇文档的最终分值，并按序排列提供给用户。然而，利用倒排索引完全可以更有效的进行计算。下面的算法假设查询有两个词语q1和q2组成，区段的布尔函数为AND，即只有该区段具有全部的查询词语才为1。

此主题相关图片如下：

这个方法类似于前文所述的标记合并算法，以前只是将满足条件的文档添加到查询结果中，而这里是计算每篇文档的权值。其中的WEIGHTEDZONE函数为计算加权区段分值的函数。有些文献将scores[]数组称之为累加器集合（set of accumulators）。原因在于完全可以使用更为复杂的布尔函数而不是AND函数来计算区段的取值，如即便是区段没有任何查询词语也不被赋予0值。值得说明的是，这些词语也需要进行必要的规范化，如消除词根等。

6．2 词项频率和加权
前文所说的分值主要依据查询词语是否出现在文档的区段中。如果再进一步，如果一篇文档或者某个区段含有的查询词语越多，则它与查询的关系就越密切，相应的加权区段分值就应当越大。这在搜索引擎中非常有用，因为搜索引擎用户一般只使用没有任何布尔操作符的自由文本检索方式，一般也不会指定字段或者区段，查询就完全表现为一些词语的集合。此时就需要一种更为有效的相似程度计算方法。
为了达到这个目标，我们可以为每篇文档的每个词项指定一个权值，该值依赖于词语在文档中的出现频率，并基于此来计算查询与文档的相似程度分值。在这种情况下，通常将文档看成是一个词包模型（bag of words model），也就是说，词语之间的次序是被忽略的，如“Mary is quicker than John”和“John is quicker than Mary”等价。但是词语出现的次数是重要的，而一般的布尔检索并不在意词语出现的次数，因此只需保存词语出现的次数信息即可。

6．2．1 倒文档频率（Inverse document frequency）
词项频率方法只是假设所有的词语都具有一样的重要性。但是事实上，文档中的所有词语都是一样重要吗？显然不是，特别是诸如停用词之类的词语。其实，问题还不止这些，即便不是同义词，有些词语的重要性也并不高。如对于汽车公司的文档集合而言，auto这个词语几乎出现在任何一篇文档中。所以，应当降低在整个文档集合中出现频率较高的词语对查询相关度的影响程度。
直观的想法就是集合频率（collection frequency），它为词语在整个文档集合中的出现次数综合。更为常见的情况是使用文档频率（document frequency），它是指包含该词语的文档总数。之所以文档频率优于集合频率，其中的原因在于文档频率是文档层次的统计指标，而集合频率是集合层次的统计指标，前者的计算复杂度要小于后者。更为重要的是，有时集合频率并不准确，如：

此主题相关图片如下：

显然，产生上述现象的原因在于有些词语过度集中于很少的文档当中。事实上，查询insurance会得到较少的高权重文档，而查询try就会得到较多的高权重文档。
那么，文档频率如何影响查询词语的权重呢？假设集合中的文档数量为N，我们可以得到查询词语t的倒文档频率idf：

此主题相关图片如下：

显然，文档频率较低的词语会有较大的倒文档频率。下图给出了路透社文档集合一些词语的倒文档频率指标（N为806791，对数的底数为10）：

此主题相关图片如下：

6．2．2 tf－idf权值
现在可以将词语频率和倒文档频率结合起来，对每篇文档的每个词语给出最终的复合权重值，即tf－idf权值：

此主题相关图片如下：

这个权值有以下特点：
1）如果词语t出现在较少的文档当中（具有较高的区分度），则权重值最高。
2）如果词语t在一篇文档中出现的频率较低（具有较低的相关表征性），则权重值较低。
3）如果词语t出现在几乎所有的文档中，则权重值最低。
按照tf－idf权值，我们可以将文档看成是一个向量，每个元素都是字典中的一个词项，每个元素值都为相应的tf－idf权值。如果该词语没有出现在文档中，对应的向量元素值为0。这个向量对于计算查询分值和查询结果排序都非常重要。
直觉可以看出，利用所有查询词语在文档中的出现次数总和可以得到查询和文档的相似程度，所以可以对所有查询词语的tf－idf权值计算总和来得到最终的查询分值：

此主题相关图片如下：

6．3 用于计算查询分值的向量空间模型
前文所提出的向量空间模型，可以广泛的应用于诸如查询结果排序、文档聚类和文档分类中。这里主要说明查询结果排序的问题。
假设V（d）表示文档d的向量，因此整个文档集合可以看成是一个向量空间中很多向量的集合，每个词语构成了这个向量空间的一个轴。显然，该模型无法反映不同词语的次序关系。同时，整个集合中的所有N篇文献可以构成一个M×N矩阵，M为词语的数量，其中每行代表每篇文档的向量。
计算两篇文档的相似程度可以简单的利用文档向量的量级差距来完成，但是由于相似的文档也因为具有不同的长度而导致文档向量的量级并不一样，也就是说，两篇文档中具有相似的词语分布情况，但是它们的绝对值并不完全一样。
为了克服文档长度带来的影响，计算文档向量相似度的标准做法就是计算向量的余弦相似度：

此主题相关图片如下：

换个表述方法，也可以将上述公式写成：

此主题相关图片如下：


此主题相关图片如下：


此主题相关图片如下：

上述文档向量相似度的计算其实就是向量夹角的余弦。另外，这种运算所产生的效率问题也值得关注。
利用它不仅可以计算查询和文档的相似程度，还可以计算不同文档间的相似程度，如在搜索引擎中广泛使用的“more like this”功能就可以基于这个功能来做。
下面的例子为：

此主题相关图片如下：


此主题相关图片如下：


此主题相关图片如下：


此主题相关图片如下：

对于查询和文档的相似度比较问题而言，利用文档向量模型的计算方法也非常简单。如上述例子，查询为“jealous gossip”，则相应的查询向量为v(q)=(0,0.707,0.707)。结果可以发现，WH具有最高的分值，为0.509，PaP为0.085，而SaS则为0.074。
这样处理查询，将其看成词包（bag of words），也就把查询当成了一个短小的文档来看待。仍然可以使用向量的余弦夹角来得到相似度。
值得注意的是，此时即便是一篇没有含有全部查询词语的文档，也有可能具有较高的权重。所以，在实际的信息检索系统中，综合多种加权模式才能取得更为优良的效果。

6．4 其他的tf-idf函数
对于每篇文档每个词语所赋予的权重，也可以使用一些其他的方式来得到。

1）次线性tf缩放方法（Sublinear tf scaling）
很难说具有在一篇文档中出现20次的词语就一定比出现1次的词语具有20倍的重要性，事实上，随着次数的逐渐增多，重要性的增加幅度会越来越少。次线形tf缩放方法就是采用这种思想实现的，如：

此主题相关图片如下：

相应的最终词语权重为：

此主题相关图片如下：

2）最大tf规范化方法（Maximum tf normalization）
利用一篇文档中tf的最大值来规范该文档所有词语的tf值，已经受到人们的广泛研究。方法为：

此主题相关图片如下：

为0到1范围内的值，一般取0.4，早期为0.5。它被称为平滑因子，以减少第二部分对总值的影响程度。
这种方法的主要思想在于设法消除这样一种异常，那就是完全是因为文档的长度造成词语重复数量增加而导致长文档具有较高的词语频率。可以假设一种极端的情况，那就是将文档拷贝一份追加到原有文档的后面，就会在不改变文档与任何查询相关性的情况下，将该文档的所有词语tf值增加一倍。
但是，这种方法也有问题：一是不稳定，如一旦停用词列表的词语发生了改变，就会对现有的词语权重产生影响；二是如果某个文档含有一个过多数量的词语，也会对该文档整体词语的权重产生影响；三是如果某个文档中最频繁出现的词语次数与其他词语的出现次数相差不大，也会产生较明显的倾斜分值分布。

3）文档和查询权重的模式
虽然利用余弦夹角是各种信息检索系统中计算向量相似度的基本方法，但是向量元素权重的不同选择会导致不同的计算结果。
这些方法可以组合使用。为了表示，人们采用SMART书写方法，这个方法名称来自于早期的一个信息检索系统作者，通常表示为ddd.qqq，前面一个三元组表示文档向量的词语权重计算方法，而后一个三元组表示查询向量的词语权重计算方法。其中每个三元组中的三个元素分别表示词语频率权重计算方法、文档频率计算方法和规范化方法。如lnc.ltc表示文档向量采用对数权重词语频率、没有使用倒文档频率（因为性能和效率等因素）和余弦规范化方法，而查询向量则使用对数词语频率、倒文档频率和余弦规范化方法。

4）转动规范化文档长度（Pivoted normalized document length）
前文对文档向量通过欧几里得（Euclidean）长度进行了规范化处理，变成了单位向量。为此，文档原有的长度信息被消除了。但是这也掩盖了各种长文档的细微区别。首先，由于含有的词语数量多，所以长文档通常具有较高的tf值。其次，长文档含有更多的不同词语。这些因素都导致提升长文档的分值，这显然并不正常。但是情况也有变化。从总体来看，长文档存在以下两种情况：一是对相同内容的重复说明，也就是说，文档的长度并不改变不同词语的相对权重；二是文档所包含的内容覆盖了多个不同的主题，查询词语只是命中文档中的一小部分内容而非全部内容，此时和单一的短小文档相比，词语的相对权重肯定较低。为了解决这个问题，可以采用一种独立于词语和文档频率的文档长度规范方法，这些方法所操作的文档不一定具有相同的单位长度，只是在计算查询向量和文档向量的点积时，将分值的设定结合考虑文档长度。这种方法被称为转动规范化文档长度方法。
考虑一个文档集合和相应的查询集合，假设对于每个文档和查询，都存在一个唯一的二值布尔判断，即相关还是不相关。利用这种相关度判断，我们可以将相关的概率看成是文档长度的函数，而且还要综合平均所有的查询来考虑。结果如图中的粗线：

此主题相关图片如下：

这个线是这样计算得到的：将文档集合按照不同文档长度划分为若干块，对每块计算与查询相关的文档数量比重，并使用这个块中文档长度的中数来作为整个块的长度。注意，这条线并非连续的线，它是由很多独立的点构成的。
图中的细线也是利用相同的文档和查询集合，只不过对于相关性的计算却采用标准的余弦方法。由此看出，余弦方法对长文档易产生更为明显的偏好现象。
两条线的交叉点被称为支点（pivot）。支点所对应的文档长度能够说明余弦方法的计算结果和真实的结果是相同的。于是，在规范化的时候以这个长度来对文档向量进行处理可以更为有效，所以此时对于短文档而言，它的文档向量就要和更大的文档长度进行计算，而对长文档而言，它的文档向量就要和更小的文档长度进行计算。这也是转动规范化文档长度方法的思路，以图中的p点为轴，旋转余弦方法的结果曲线，使之尽可能的趋近于粗线。
具体的计算方法还可以使用其他一些线形表达结果，如：

此主题相关图片如下：

或者

此主题相关图片如下：

Ud为文档含有不同词语的个数，该方法是上式的近似表达，但是实践效果不错。
当然，这种方法并不适用于所有情况，如对于FAQ的问答集合而言，相关度和长度的关系并不密切。在有些情况中，相关度与文档长度的关系远非线形关系这么简单。