空间向量模型--相似度计算举例

2.1.1　相似度计算举例

下面我们考虑一个固定的查询和文档集，包含一个查询Q和三篇文档组成的文档集：

Q："gold silver truck"

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"

在这个文档集中，有三篇文档，所以d = 3。如果一个词项仅在三篇文档中的一篇中出现，那么该词项的IDF就是lg(d/dfi) = lg(3/1) = 0.477。类似地，如果一个词项在三篇文档中的两篇中出现，那么该词项的IDF就是lg(d/dfi) = lg(3/2) = 0.176。如果一个词项在三篇文档中都出现了，那么该词项的IDF就是lg(d/dfi) = lg(3/3) = 0。

三篇文档的每个词项的IDF值如下所示：

498)this.width=498;" border=0>

现在就可以构造文档向量了。因为文档集中出现了11个词项，所以我们构造一个11维的文档向量。我们可以用上文给出的按字母顺序排列的词项来构建文档向量，所以t1对应第一个词项"a"，t2对应"arrived"，依次类推。向量j中词项i的权重计算方式为idfi×tfij。文档向量如表2-1所示。

 

表2-1　文档向量

 

 

 

docid	a	arrived	damaged	delivery	fire	gold	in	of	shipment	silver	truck
D1	0	0	0.477	0	0.477	0.176	0	0	0.176	0	0
D2	0	0.176	0	0.477	0	0	0	0	0	0.954	0.176
D3	0	0.176	0	0	0	0.176	0	0	0.176	0	0.176
Q	0	0	0	0	0	0.176	0	0	0	0.477	0.176

498)this.width=498;" border=0>

在实现向量空间模型或其他检索模型时，我们通常使用倒排索引（inverted index）来避免在每篇文档中使用冗长的顺序查找来查找查询词。因此，在用户提交查询之前，我们首先构造倒排索引表。从图2-3中我们可以看到倒排索引表的结构。n个词项中的每一项都被存储在称为索引的结构中。对于每一个词项，指向的逻辑链接表被称作倒排表（posting list）。倒排表记录每篇包含该词项的文档。在图2-3中，倒排表中记录了文档标识符和词频等信息。（实际上，人们往往使用比链接表更有效的结构，但从概念上讲都是为了同一目的。）图中的倒排表表明词项t1在文档1中出现了一次，在文档10中出现了两次。对于一个任意的词项t1的条目，表明该词项在文档j中出现了tf次。倒排索引的的具体构造细节和用法将在第5章中介绍，不过知道倒排索引通常在各种检索模型中用来提高运行效率是非常有用的。

498)this.width=498;" border=0>

图2-3　倒排索引

在20世纪60年代后期的文献[Salton和Lesk，1968]中就有关于向量空间模型的早期研究。该模型在20世纪70年代中期使用非常普遍[Salton等人，1975]，并且现在仍然是计算查询和文档相似度最广泛使用的方法之一[TREC，2003]。这种方法非常重要，因为检索系统可以据此决定最终将哪些文档展示给用户。通常用户只需要最前面的n篇文档，并且这些文档按相似度进行排序。

接下来，科研人员研究了提升基本的tf-idf权重的词项权重计算方式 [Salton和Buckley，1988]。人们研究了许多不同的方法，并且认为用下面的公式计算文档i中词项j的权重效果出色：

498)this.width=498;" border=0>

这样计算权重的出发点是：在已知的查询和文档中，词频很高的匹配词项淹没了其他匹配词项的效果。为了避免这种现象，科研人员提出使用lg(tf) + 1来缩小词频的范围。基于该思想的修订版本是在查询和文档中的词项使用不同的权重。

一种被称作lnc.ltc的词项权重计算模式非常有效。文档中使用1+lg(tf)×idf计算权重，查询中使用1+lg(tf)计算权重。标签lnc.ltc是如下形式：qqq.ddd，其中qqq指查询权重，ddd指文档权重。这三个字母：qqq或ddd是xyz的形式。

第一个字母x可以是n、l或a。n表示原始词频或指tf。l表示通过取对数来降低权重，所以可以使用1+lg(tf)。a表示加强权重，所以权重为

第二个字母y表示是否使用idf。n表示不使用idf，t表示使用idf。

第三个字母z表示是否使用文档长度归一化。通过归一化文档长度，我们试着减小检索中文档长度的影响（见公式2-1）。在文献[Singhal, 1997]中，n表示不使用归一化，c表示使用标准的余弦归一化，u表示使用临界点长度（pivoted length）归一化。