文本相似度 — TF-IDF和BM25算法

文本相似度 — TF-IDF和BM25算法

1，$TF-IDF$算法

　　$TF$是指归一化后的词频，$IDF$是指逆文档频率。

给定一个文档集合$D$，有$d_1, d_2, d_3, ......, d_n \in D$。

文档集合总共包含$m$个词（注：一般在计算$TF-IDF$时会去除如“的”这一类的停用词），有$w_1, w_2, w_3, ......, w_m \in W$。

我们现在以计算词$w_i$在文档$d_j$中的$TF-IDF$指为例。

$TF$的计算公式为：

　　　　$ TF = \frac{freq(i, j)} {max_{len}(j)} $

　　在这里$freq(i, j)$ 为$w_i$在$d_j$中出现的频率，$max_{len}(j)$为$d_j$长度。

　　$TF$只能时描述词在文档中的频率，但假设现在有个词为”我们“，这个词可能在文档集$D$中每篇文档中都会出现，并且有较高的频率。

那么这一类词就不具有很好的区分文档的能力，为了降低这种通用词的作用，引入了$IDF$。

　　$IDF$的表达式如下：

　　　　$IDF = \log (\frac {len(D)} {n(i)})$

　　在这里$len(D)$表示文档集合$D$中文档的总数，$n(i)$表示含有$w_i$这个词的文档的数量。

　　得到$TF$和$IDF$之后，我们将这两个值相乘得到$TF-IDF$的值：

　　　　$TF-IDF = TF * IDF$　

　　$TF$可以计算在一篇文档中词出现的频率，而$IDF$可以降低一些通用词的作用。

因此对于一篇文档我们可以用文档中每个词的$TF-IDF$组成的向量来表示该文档，再根据余弦相似度这类的方法来计算文档之间的相关性。

2，$BM25$算法

　　$BM25$算法通常用来做搜索相关性评分的，也是ES中的搜索算法，通常用来计算$query$和文本集合$D$中每篇文本之间的相关性。

我们用$Q$表示$query$，在这里$Q$一般是一个句子。

在这里我们要对$Q$进行语素解析（一般是分词），在这里以分词为例，我们对$Q$进行分词，得到$q_1, q_2,......, q_t$这样一个词序列。

给定文本$d \in D$，现在以计算$Q$和$d$之间的分数（相关性），其表达式如下：

　　　　$Score(Q, d) = \sum_{i = 1}^t w_i * R(q_i, d)$

　   上面式子中$w_i$表示$q_i$的权重，$R(q_i, d)$为$q_i$和$d$的相关性，$Score(Q, d)$就是每个语素$q_i$和$d$的相关性的加权和。

　　$w_i$的计算方法有很多，一般是用$IDF$来表示的，但这里的$IDF$计算和上面的有所不同，具体的表达式如下：

　　　　$w_i = IDF(q_i) = \log \frac {N - n(q_i) + 0.5} {n(q_i) + 0.5}$

　　上面式子中$N$表示文本集合中文本的总数量，$n(q_i)$表示包含$q_i$这个词的文本的数量，$0.5$主要是做平滑处理。

　　$R(q_i, d)$的计算公式如下：

　　　　$R(q_i, d) = \frac {f_i * (k_1 + 1)} {f_i + K} * \frac {qf_i * (k_2 + 1)} {qf_i + k_2}$

　　其中

　　　　$K = k_1 * (1 - b + b * \frac {dl} {avg dl})$

　　上面式子中$f_i$为$q_i$在文本$d$中出现的频率，$qf_i$为$q_i$在$Q$中出现的频率，$k_1, k_2, b$都是可调节的参数，$dl, avg dl$分别为文本$d$的长度和文本集$D$中所有文本的平均长度。

　　一般$qf_i = 1$，取$k_2 = 0$，则可以去除后一项，将上面式子改写成：

　　　　$R(q_i, d) = \frac {f_i * (k_1 + 1)} {f_i + K}$

　　通常设置$k_1 = 2, b = 0.75$。

参数$b$的作用主要是调节文本长度对相关性的影响。