基本空间向量搜索引擎理论(译)

说明

• 文本主要翻译Vidiot的<<Basic Vector Space Search Engine Theory>>原文地址，并且阐述理论的应用。
• 我尽可能还原原文并且减少翻译的生硬，但是由于翻译经验不足，如有些内容翻译不准确还请去阅读原文。

原文翻译

Basic Vector Space Search Engine Theory

LA 2600 — January 2, 2004 - presented by Vidiot

概述

空间向量搜索引擎(Vector Space Search Engine , 简称VSSE)是一种使用非常简单的矩阵代数方法去比较文本词汇相似度的技术。

• 对于VSSE，首先要明确的概念就是项空间(term space)。简单来讲，定义在一份文档集合上的项空间就是所有文档中不相同单词的集合，(项空间的维数就是不同单词的种类数)\(_{译者注}\)。
• 第二个需要知道的概念就是项计数(term counts)。这也可以简单地定义成每一个项在某单个文档中出现的次数。这通常可以用表格来表示，之后会举一些例子。

用项空间作为坐标空间，项计数作为每一项地值，则针对文档集合中的每一份文档都可以在这个坐标空间中生成一个向量。我们来看一个简单的例子，大家应该都非常熟悉笛卡尔坐标系(直角坐标系和斜坐标系的统称)\(_{译者注}\)；在坐标系中用\(X\)，\(Y\)和\(Z\)定义一个点。类似地，如果项空间只包含三个不同项的话，我们就可以用\(term1\)，\(term2\)和\(term3\)作为轴来定义项空间中的点。(在空间向量搜索理论中相空间的轴(axes)通常表示维度(dimensions))。依靠对每项(通常是单词)在单个文档中的计数，并且在坐标空间各个项维度下确定尺度，我们就可以用一个坐标空间中的点来表示一份文档。同时，有了这个点我们也就可以确定一个由原点指向该点的向量。

一旦我们对一份文档计算出了它在项空间中的向量，我们也就可以计算出这个向量的模，可以把这个向量的模当作从项空间原点到文档表示的点的线段长度。有了向量的模，我们就可以通过计算不同向量间夹角的余弦来比较不同文档间的相似度。例如，单个文档关于自己向量的余弦是1，有相似内容的不同文档间具有正的向量余弦值，而没有任何内容相同的文档间向量的余弦值是0。

示例

在这里的示例里我们仅用3个维度去遍历搜索整个文档集合，因为这样的感受比较直观。

首先，假设我们有一个有3份文档的文档集合。每一份文档都包含有这3个词cat，dog和mouse。根据定义，这些词cat，dog和mouse就组成了项空间。因此我们就可以认为每一篇文章都在cat，dog和mouse这三个维度内有坐标。这些坐标是由每个项在不同文档中出现的次数决定的。例如，文档(1)如下，就有一个“cat-dog-mouse 向量”为\((3, 1, 4)\)。

\[ \begin{array}{c|ccc} \text{项空间} & \text{项计数} \\ & \text{文档(1)} & 文档(2) & 文档(3)\\ \hline cat & 3 & 1 & 2\\ dog & 1 & 2 & 3\\ mouse & 4 & 5 & 0 \end{array} \]

在维度为2的条件下我们可以用毕达哥拉斯定理(即勾股定理)\(_{译者注}\)求出向量的模，但在此条件下我们有新的公式： \[ a^2+b^2+c^2=d^2 \]

• $ V_1= = = 5.09901$
• $V_2= = = 5.47722 $
• $ V_3===3.87298$

注意：这里$ V\(表示向量\)V$的模

值得注意的是不论我们在研究多大维度的向量，毕达哥拉斯公式的项数也可以不断增加。

此外，细心的读者也许注意到了不同的文档可能具有相同的空间向量模。例如，两份不同的文档分别具有空间向量(1, 2, 3)和(3, 2, 1)，那么这两个向量的模都是3.74165。这其实并不矛盾，正如我们所见，文档间的相关性是基于查找的项的维度的，即具有相同空间向量模大小的多份文档可能会得到非常不同的查询结果。也就是说，仅仅因为两条线段有同样的长度，并不能说明它们在项空间中指向同一个角度。

查询

为了查询文档集合中的元素，我们把查询向量(query vector)在文档集合的项空间中建模，之后计算查询向量与文档集合中所有文档对应向量的夹角余弦值。也就是说，把查询向量放到项空间里，然后看看哪些文档对应的向量在该查询向量附近。

例如，如果查询项为“mouse”，那么“cat-dog-mouse向量”就是\((0, 0, 1)\)。那么我们的查询向量的模就是：

\[ \mid \mid Q \mid \mid = \sqrt{(0^2) + (0^2) + (1^2)} = \sqrt{0+0+1} = \sqrt{1}= 1 \] > 注意：该计算过程在写程序的时候可以进行简单的简化，即检查该查询项是否在项空间中，如果在则\(\mid \mid Q \mid \mid\) 总为1，但这仅仅适用于单个查询项的情况。针对多个查询项的时候，只需统计有多少项是属于项空间的，并对计数取平方根即可。因为查询项的表示不会小于1，\(\mid \mid Q\mid\mid\)的值总是某个整数的平方根。但是这些都是基于每组查询中的查询元素仅出现一次的假设，这并不是一个有力的假设，因为这涉及到词干提取(word stemming)的问题，我会在后面讨论。

为了计算每个查询向量和文档所表示的向量间夹角的余弦值，我们要用查询项两和文档向量间的点积(Dot Product)除以查询向量的模与文档向量的模的乘积。

\[ \frac{Q \ast V_1}{\mid \mid Q\mid \mid \times \mid \mid V_1\mid\mid} \]

点积就是每一个文档的所有项计数与查询向量中对应的项计数的乘积的和。例如，如果我们要查询的项是"mouse"，查询向量就是\((0,0,1)\)，因为词"cat"和"dog"都没有出现，且"mouse"出现了一次，正好对应了项空间的第三个维度。在我们的示例中，文档1基于上面表格对应的项计数得到的向量为\((3,1,4)\)。如果我们要计算查询向量与文档1向量的点积，我们要做一下计算：

\[ \left. \begin{array}{l} \mathrm{Query\ vector:\quad \quad \quad } (0, \quad \quad 0,\quad \quad 1) \\[2ex] \mathrm{Document\ 1\ vector:\ } (3,\quad\quad 1,\quad \quad 4) \\[2ex] \mathrm{Dot\ Product:\quad \quad \ \ \ \ } (0\times 3)+(0 \times 1) + (1 \times 4) = 4 \end{array} \right. \]

现在我们用点积\(4\)除以查询向量和文档向量模的乘积，用以得到余弦值。我们之前计算过文档1的向量模是\(5.09901\)，查询向量的模为\(1\)，因此余弦值为\(4\)除以\(5.09901\)。

让我们来尝试一下，查询向量"mouse"和文档1向量之间的夹角的余弦值可以被这样计算：

\[ \frac{Q \ast V_1}{\mid \mid Q \mid\mid \times \mid\mid V_1 \mid\mid} = \frac{(0 \times 3) + (0 \times 1) + (1 \times 4)}{1 \times 5.09901} = \frac{4}{5.09901} = 0.78446 \]

注意：如果一个文档中不包含任何与搜索项相关的项，则点积为0。由于0除以任何数都为0，因此余弦值也为0。特判这种情况将使写出的代码更高效。

如果我们对其他两份文档进行同样的计算，我们就会得到以下余弦值：

\[ \mathrm{Doc\ 1} = 0.78446 \\[1ex] \mathrm{Doc \ 2} = 0.91287 \\[1ex] \mathrm{Doc\ 3} = 0.00000 \]

再将这些余弦值按降序排序后，得到：

\[ \mathrm{Doc \ 2} = 0.91287 \\[1ex] \mathrm{Doc\ 1} = 0.78446 \\[1ex] \mathrm{Doc\ 3} = 0.00000 \]

未完待续