搜索之空间向量模型
空间向量模型:
将文档看作空间中的一个向量,用词的特征来表示某个文档在空间中的坐标。然后计算文档与文档之间的相似度。
通过计算各个向量之间的夹角来表示各个文档之间的相似度。
下面给出一个例子进行说明: 表格中的数字表示某个词在某个文档中出现的次数
term | $d_1$ | $d_2$ | $d_3$ | $d_4$ | $d_5$ |
---|---|---|---|---|---|
car | 2 | 1 | 1 | 1 | 0 |
motorcycle | 0 | 0 | 0 | 2 | 1 |
racing | 1 | 0 | 0 | 0 | 0 |
riding | 0 | 0 | 0 | 1 | 1 |
speed | 0 | 0 | 2 | 0 | 1 |
sport | 0 | 1 | 1 | 0 | 0 |
street | 0 | 0 | 0 | 1 | 1 |
track | 0 | 1 | 0 | 0 | 1 |
training | 2 | 0 | 0 | 1 | 1 |
根据表格中的数据可以得到 $d_1$ 跟 $d_2$、$d_2$ 跟 $d_3$ 之间的相似度:
\[s_c(d_1,d_2) = \frac{d_1d_2}{\mid d_1 \mid \mid d_2 \mid} = \frac{(2,0,1,0,0,0,0,0,2)(1,0,0,0,0,1,0,1,0)}{\sqrt{2^2 + 1^2 + 2^2} \sqrt{1^2 + 1^2 + 1^2}} = \frac {2}{3 \sqrt{3}} \approx 0.385\] \[s_c(d_2,d_3) = \frac{d_2d_3}{\mid d_2 \mid \mid d_3 \mid} = \frac{(1,0,0,0,0,1,0,1,0)(1,0,0,0,2,1,0,0,0)}{\sqrt{1^2 + 1^2 + 1^2} \sqrt{1^2 + 2^2 + 1^2}} = \frac {2}{\sqrt{3} \sqrt{6}} \approx 0.471\]在基于余弦计算相似度的情况下,我们可以看到第二个文档跟第三个文档的相似度高于第一个文档跟第二个文档。从表 2.1 可以看出来 d2 跟 d3 有两个相同的词 {car,sport}
,而 d1 跟 d2 只有一个相同的词 {car}
词频:term frequency - tf
一个词在某个文档中出现的次数越多,那么它与某个文档的相关性越高,越能表达这篇文章的意思。但是在一篇长文档里面,一个词的词频会比在一篇短文档里面要高,这并不能说明长文档与查询更加相关。为了解决这种情况,用某个词的词频去除以文档中出现次数最高的词,采用这种绝对的方式就消除了长文档的影响。
所以词频的计算公式为: \(tf(t_i,d) = \frac {tf_r(t_i,d)}{max_{t \in d}(tf_r(t))}\)
$tf_r(t_i,d)$ 表示在文档 $d$ 中 $t_i$ 出现的次数 $max_{t \in d}(tf_r(t))$ 表示文档 $d$ 中出现次数最多的词
逆文档频率:inverse document frequency - idf
如果一个词出现在大部分的文档中,那么它就不能用来区分各个文档之间的差别,也就是说这个词的重要性越低。
其计算公式如下: \(idf(t_i) = log \frac {\mid D \mid}{df(t_i)}\)
$df(t_i)$ 表示词 $t_i$ 在多少个文档中出现 $D$ 表示文档总数
tf-idf
算法就是结合词频跟逆文档频率来表示相关性。即:
\(w_{i,j} = tf(t_i,d_j) \cdot idf(t_i) = \frac{tf_r(t_i,d_j)}{max_{t \in d_j}(tf_r(t))}log \frac {\lvert D \rvert }{df(t_i)}\)
下面通过 tf-idf
计算文档的相似度:
Term | $tf(t,d_1)$ | $tf(t,d_2)$ | $tf(t,d_3)$ | $tf(t,d_4)$ | $tf(t,d_5)$ | $df$ | $idf$ |
---|---|---|---|---|---|---|---|
car | 1 | 1 | 0.5 | 0.5 | 0 | 4 | 0.097 |
motorcycle | 0 | 0 | 0 | 1 | 1 | 2 | 0.398 |
racing | 0.5 | 0 | 0 | 0 | 0 | 1 | 0.699 |
riding | 0 | 0 | 0 | 0.5 | 1 | 2 | 0.398 |
speed | 0 | 0 | 1 | 0 | 1 | 2 | 0.398 |
sport | 0 | 1 | 0.5 | 0 | 0 | 2 | 0.398 |
street | 0 | 0 | 0 | 0.5 | 1 | 2 | 0.398 |
track | 0 | 1 | 0 | 0 | 1 | 2 | 0.398 |
training | 1 | 0 | 0 | 0.5 | 1 | 3 | 0.222 |
文档 $d_1$,$d_2$ 与 $d_2$,$d_3$ 之间的相似度得分为:
\[S_{tfidf}(d_1,d_2) = \frac {(0.097,0,0.349,0,0,0,0,0,0.222)(0.097,0,0,0,0,0.398,0,0.398,0)}{\sqrt{0.181} \sqrt{0.326}} \approx 0.038\] \[S_{tfidf}(d_2,d_3) = \frac {(0.097,0,0,0,0,0.398,0,0.398,0)(0.048,0,0,0,0.398,0.199,0,0,0)}{\sqrt {0.326} \sqrt{0.2}} \approx 0.328\]可以看到,文档 $d_2$ 跟 $d_3$ 之间的相似度还是要高于 $d_1$ 跟 $d_2$。相比之前通过余弦方式计算出来的相关度,$d_2$ 跟 $d_3$ 的相似度得分是 $d_1$ 跟 $d_2$ 的 8 倍多。$d_1$ 跟 $d_2$ 的相似度得分趋近于 0,因为有一个词 car
出现在大部分的文档中,所以它的 idf
的值很低,也就拉低了文档的得分。
在实际的搜索场景中,用户输入的查询词也被当作一个文档处理,然后通过 tf-idf
算法计算与文档库中各个文档之间的相似度,然后按照相似度的大小排序返回给用户。
下面给一个实际当中的例子。 文档库中的文档如下:
$d_1$:快8个月宝宝夜里发烧了,早上宝宝又拉肚子,宝宝发烧会导致拉肚子吗? $d_2$:满月大的婴儿发烧,该怎么治疗才好呢?真着急呀,孩子刚刚摆过满 月酒就发烧了,谢谢各位。 $d_3$:8个月宝宝发烧38.5,但是手脚冰凉,有没有不用去医院的治疗办法
当用户输入 宝宝发烧
进行搜索时,具体的计算方式如下:
注:虽然把用户输入的查询词也当作一个文档,但是在实际应用中,文档数很大,因此可以忽略。即:文档总数依然是 3
词 | $tf(t,d_1)$ | $tf(t,d_2)$ | $tf(t,d_3)$ | $tf(t,q)$ | $df$ | $idf$ | |
---|---|---|---|---|---|---|---|
快 | 0.3 | 0 | 0 | 0 | 1 | 0.477 | |
8 | 0.3 | 0 | 1 | 0 | 2 | 0.176 | |
个月 | 0.3 | 0 | 1 | 0 | 2 | 0.176 | |
宝宝 | 1 | 0 | 1 | 1 | 2 | 0.176 | |
夜里 | 0.3 | 0 | 0 | 0 | 1 | 0.176 | |
发烧 | 0.7 | 1 | 1 | 1 | 3 | 0 | |
早上 | 0.3 | 0 | 0 | 0 | 1 | 0.477 | |
拉肚子 | 0.7 | 0 | 0 | 0 | 1 | 0.477 | |
导致 | 0.3 | 0 | 0 | 0 | 1 | 0.477 | |
满月 | 0 | 0.5 | 0 | 0 | 1 | 0.477 | |
大 | 0 | 0.5 | 0 | 0 | 1 | 0.477 | |
婴儿 | 0 | 0.5 | 0 | 0 | 1 | 0.477 | |
该 | 0 | 0.5 | 0 | 0 | 1 | 0.477 | |
怎么 | 0 | 0.5 | 0 | 0 | 1 | 0.477 | |
治疗 | 0 | 0.5 | 0 | 0 | 1 | 0.477 | |
才 | 0 | 0.5 | 0 | 0 | 1 | 0.477 | |
好呢 | 0 | 0.5 | 0 | 0 | 1 | 0.477 | |
真 | 0 | 0.5 | 0 | 0 | 1 | 0.477 | |
着急 | 0 | 0.5 | 0 | 0 | 1 | 0.477 | |
孩子 | 0 | 0.5 | 0 | 0 | 1 | 0.477 | |
刚刚 | 0 | 0.5 | 0 | 0 | 1 | 0.477 | |
摆过 | 0 | 0.5 | 0 | 0 | 1 | 0.477 | |
满月酒 | 0 | 0.5 | 0 | 0 | 1 | 0.477 | |
就 | 0 | 0.5 | 0 | 0 | 1 | 0.477 | |
谢谢 | 0 | 0.5 | 0 | 0 | 1 | 0.477 | |
各位 | 0 | 0.5 | 0 | 0 | 1 | 0.477 | |
38.5 | 0 | 0 | 1 | 0 | 1 | 0.477 | |
但是 | 0 | 0 | 1 | 0 | 1 | 0.477 | |
手脚冰凉 | 0 | 0 | 1 | 0 | 1 | 0.477 | |
没有 | 0 | 0 | 1 | 0 | 1 | 0.477 | |
不用 | 0 | 0 | 1 | 0 | 1 | 0.477 | |
去 | 0 | 0 | 1 | 0 | 1 | 0.477 | |
医院 | 0 | 0 | 1 | 0 | 1 | 0.477 | |
治疗 | 0 | 0 | 1 | 0 | 1 | 0.477 | |
办法 | 0 | 0 | 1 | 0 | 1 | 0.477 |
具体的计算方式如下: \(S(q, d_1) = \frac{0.716^2}{\sqrt{0.716^2}} = 1\) \(S(q, d_2) = 0\) \(S(q, d_3) = 1\) 可以看到,文档 $d_1$、$d_3$ 更加匹配。