Elasticsearch搜索相关性排序算法详解

jiezi

5 年前

说明：本文章使用的 ES 版本是：6.2.4

在上一篇文章 Elasticsearch 搜索过程详解中，介绍了 ES 的搜索过程。

接下来我们具体的看一下 ES 搜索时，是如何计算文档相关性得分并用于排序的。

在介绍 ES 计算文档得分之前，先来看一下 TF-IDF 算法。

TF-IDF（Term Frequency–Inverse Document Frequency）是一种用于信息检索与文本挖掘的常用加权算法。它是一种统计方法，用以评估一字词对于一个文件集或一个语料库中的其中一份文件的重要程度。字词的重要性随着它在文件中出现的次数成正比增加，但同时会随着它在语料库中出现的频率成反比下降。

TF-IDF实际上是两个算法 TF 和IDF的乘积。

词频的所在对象是一个具体的文档，是指一个文档中出现某个单词（Term）的频率（Frequency）。这里用的是频率而不是次数，是为了防止文档内容过长从而导致某些单词出现过多。为了正确评价一个单词在一个文档中的重要程度，需要将出现次数归一化，其算法如下：

$$
tf_i=\frac{n_i}{\sum\nolimits_{k=1}^nn_k}
$$

上面式子中 n_i 是该词在文件中的出现次数，而分母

$$
\sum _{k=1}^nn_k
$$

则是在文件中所有字词的出现次数之和。

逆向文件频率描述的对象是一个文档集合中，包含某个单词的文档数量。它表示的是一个单词在一个文档集合中的普遍重要程度。将其归一化的算法入下：

$$
{idf_{i}} =\lg {\frac {|D|}{1+|\{j:t_{i}\in d_{j}\}|}}
$$

其中

|D|：表示文档集合中的文件总数
|{$j:t_i\in d_j$}|：包含词语 t_i 的文件数目（即 n_i≠0 的文件数目）如果词语不在数据中，就导致分母为零，因此一般情况下使用分母加了一个 1

最后

$$
tfidf_i=tf_i\times idf_i
$$

某一特定文件内的高词语频率，以及该词语在整个文件集合中的低文件频率，可以产生出高权重的 tf-idf。因此，tf-idf 倾向于过滤掉常见的词语，保留重要的词语。

TF 表示的是一个单词在一段文本中的重要程度，随着单词的增加而增加
IDF 表示的是一个单词在一个文档集合中的重要程度，越稀有权重越高，所以它随着单词的增加而降低

用上面的公式，计算一个例子。

假如一篇文件的总词语数是 100 个，而词语“学校”出现了 5 次，那么“学校”一词在该文件中的词频（tf）就是

$$
tf_i=5/100=0.05
$$

“学校”一词在 1,000 份文件出现过，而文件总数是 1,000,000 份的话，其逆向文件频率就是

$$
idf_i = lg（1,000,000 / 1,000）=3
$$

最后的 tf-idf 的分数为

$$
tfidf_i = tf_i\times idf_i = 0.05 \times 3= 0.15
$$

BM25（Best Match25）是在信息检索系统中根据提出的 query 对 document 进行评分的算法。

TF-IDF算法是一个可用的算法，但并不太完美。它给出了一个基于统计学的相关分数算法，而 BM25 算法则是在此之上做出改进之后的算法。（为什么要改进呢？TF-IDF不完美的地方在哪里？）

当两篇描述“人工智能”的文档 A 和 B，其中 A 出现“人工智能”100 次，B 出现“人工智能”200 次。两篇文章的单词数量都是 10000，那么按照 TF-IDF 算法，A 的 tf 得分是：0.01，B 的 tf 得分是 0.02。得分上 B 比 A 多了一倍，但是两篇文章都是再说人工智能，tf分数不应该相差这么多。可见单纯统计的 tf 算法在文本内容多的时候是不可靠的
多篇文档内容的长度长短不同，对 tf 算法的结果也影响很大，所以需要将文本的长度也考虑到算法当中去

基于上面两点，BM25 算法做出了改进，最终该算法公式如下：

$$
{\displaystyle {\text{score}}(D,Q)=\sum _{i=1}^{n}{\text{IDF}}(q_{i})\cdot {\frac {f(q_{i},D)\cdot (k_{1}+1)}{f(q_{i},D)+k_{1}\cdot \left(1-b+b\cdot {\frac {|D|}{\text{avgdl}}}\right)}}}
$$

其中:

Q：文档集合
D：具体的文档
${\text{IDF}}(q_{i})$：就是 TF-IDF 中的 IDF，表示单词 q_{i} 在文档集合 Q 的 IDF 值
$f(q_{i},D)$：就是 TF-IDF 中的 TF，表示单词 q_{i} 在文档 D 中的 TF 值
$k_{1}$：词语频率饱和度（term frequency saturation）它用于调节饱和度变化的速率。它的值一般介于 1.2 到 2.0 之间。数值越低则饱和的过程越快速。（意味着两个上面 A、B 两个文档有相同的分数，因为他们都包含大量的“人工智能”这个词语）。在 ES 应用中为 1.2
$b$：字段长度归约，将文档的长度归约化到全部文档的平均长度，它的值在 0 和 1 之间，1 意味着全部归约化，0 则不进行归约化。在 ES 的应用中为 0.75
$\|D\|$：文本长度
$avgdl$：文本平均长度

注：ES 版本 6.2.4 所用的 Lucene jar 包版本是：7.2.1

在了解了 TF-IDF 算法之后，再来了解 Lucene 中的相关性算法就很好理解了。

Lucene 中，相关性算法如下：

$$
score(t, q, d)={\sum\nolimits_{t}^n (idf(t) * boost(t) * tfNorm(t, d))}
$$

其中：

q：文档集合
d：具体的文档
t：单词
score(t, q, d)：表示包含查询词 t 的文档 d 在文档集合 q 中的相关性得分
idf(t)：逆向文件频率，ES 中，逆向文件频率的算法是：

$$
{idf_{t}} =\ln {(1 + \frac {docCount-docFreq+0.5}{docFreq+0.5})}
$$

    docCount：表示文档总数，docFreq：表示包含单词 t 的文档数量。

boost(t)：查询时，指定的单词的权重，不指定时为 1
tfNorm(t, d)：单词频率权重，它用 BM25 替代了简单的 TF 算法，ES 中，其算法如下：

$$
{\displaystyle {\text{tfNorm}}(t,d)={\frac {f(t, d)\cdot (k_{1}+1)}{f(t, d)+k_{1}\cdot \left(1-b+b\cdot {\frac {|D|}{\text{avgdl}}}\right)}}}
$$

tfNorm(t, d)：单词 t 在文档 d 中的频率权重
f(t, d)：单词 t 在文档 d 中的出现次数
$k_{1}$：词语频率饱和度，用于控制词频对结果的影响，数值越低则单词数量影响越小。它的值一般介于 1.2 到 2.0 之间。。在 ES 应用中为 1.2
$b$：字段长度归约，用于控制文本长度对结果的影响，数值越大文本长度影响越小。它的值在 0 和 1 之间，在 ES 的应用中为 0.75
$\|D\|$：文档 d 中查询该字段的文本长度
$avgdl$：文档集合中，所有查询该字段的平均长度

ES 在搜索过程中，拿到文档 ID 之后，就会根据搜索词，计算每篇文档的相关性得分，用其进行排序。

搜索引擎 ElasticSearch 源码编译和 Debug 环境搭建
搜索引擎 ElasticSearch 的启动过程
Elasticsearch 创建索引流程
Elasticsearch 搜索过程详解
Elasticsearch 搜索相关性排序算法详解
Elasticsearch 中的倒排索引

参考资料：

https://lucene.apache.org/core/7_2_1/core/org/apache/lucene/search/similarities/TFIDFSimilarity.html
https://en.wikipedia.org/wiki/Tf%E2%80%93idf
https://en.wikipedia.org/wiki/Okapi_BM25
https://github.crookster.org/Adding-MathJAX-LaTeX-MathML-to-Jekyll/

Elasticsearch搜索相关性排序算法详解

前言

TF-IDF

TF-IDF 算法原理

词频（Term Frequency，TF）

逆向文件频率（Inverse Document Frequency，IDF）

TF—IDF 总结

TF-IDF 算法举例

OKapi BM25 算法原理

Lucene 相关性算法

系列文章