资讯专栏INFORMATION COLUMN

上云采购季！| 爆款云服务器低至4.6元/月，首单享0.9折

免费试用
首页/文章专栏/Elasticsearch搜索相关性排序算法详解

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

MSchumi / 2384人阅读

摘要：接下来我们具体的看一下搜索时，是如何计算文档相关性得分并用于排序的。系列文章搜索引擎源码编译和环境搭建搜索引擎的启动过程创建索引流程搜索过程详解搜索相关性排序算法详解中的倒排索引参考资料

前言

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

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

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

TF-IDF

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

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

TF-IDF算法原理

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

词频（Term Frequency，TF）

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

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

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

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

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

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

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

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

其中

|D|：表示文档集合中的文件总数

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

最后

$$ tfidf_i=tf_i imes idf_i $$

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

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 imes idf_i = 0.05 imes 3= 0.15 $$

OKapi BM25算法原理

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 { ext{score}}(D,Q)=sum _{i=1}^{n}{ ext{IDF}}(q_{i})cdot {frac {f(q_{i},D)cdot (k_{1}+1)}{f(q_{i},D)+k_{1}cdot left(1-b+bcdot {frac {|D|}{ ext{avgdl}}} ight)}}} $$

其中:

Q：文档集合

D：具体的文档

${ ext{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$：文本平均长度

Lucene相关性算法 
注：ES版本6.2.4所用的Lucene jar包版本是：7.2.1

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

Lucene中，相关性算法如下：

$$ score(t, q, d)={sum olimits_{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 { ext{tfNorm}}(t,d)={frac {f(t, d)cdot (k_{1}+1)}{f(t, d)+k_{1}cdot left(1-b+bcdot {frac {|D|}{ ext{avgdl}}} ight)}}} $$

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 elasticsearch 搜索 elasticsearch 搜索延时 elasticsearch 搜索时延 elasticsearch搜索延时

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/34525.html

相关文章

  • Elasticsearch搜索过程详解

    摘要：所以在具体的应用中，需要在二者之间选择平衡计算文档权重得分，每搜索一次，都会根据搜索条件重新计算一次，对搜索性能影响很大系列文章搜索引擎源码编译和环境搭建搜索引擎的启动过程创建索引流程搜索过程详解搜索相关性排序算法详解中的倒排索引 前言 说明：本文章使用的ES版本是：6.7.0 在上一篇文章Elasticsearch如何创建索引?中，介绍了ES写入文档的过程。 接下来我们具体的看一下E...

    Reducto 评论0 收藏0

  • Elasticsearch中的倒排索引

    摘要：本篇文章主要介绍中的索引倒排索引分词在创建索引之前，会对文档中的字符串进行分词。简单来说，索引就是实现单词文档矩阵的具体数据结构，而倒排索引则是实现了这种数据结构的具体方式。 前言 再Elasticsearch创建索引流程一文中，介绍了ES创建索引的流程。再流程中是调用Lucene的接口来创建索引的。本篇文章主要介绍ES中的索引——倒排索引 分词 在创建索引之前，会对文档中的字符串进行...

    frank_fun 评论0 收藏0

  • 搜索引擎ElasticSearch源码编译安装和Debug环境搭建

    摘要：本地代码使用在本地调试，有两种方式，一种是直接在上运行进行调试，但需要很多繁杂得配置。系列文章搜索引擎源码编译和环境搭建搜索引擎的启动过程创建索引流程搜索过程详解搜索相关性排序算法详解中的倒排索引 环境准备 说明：本文章使用的ES版本是：6.7.0 JDK Elastisearch 6.7.0编译需要JDK版本10.0及以上，我直接安装了JDK12.JDK下载地址：https://ww...

    Blackjun 评论0 收藏0

  • Elasticsearch创建索引流程

    摘要：前言说明本文章使用的版本是在上一篇文章搜索引擎的启动过程中，介绍了的启动过程。由此可知，在启动过程中，创建对象时，初始化了，由其名字可以知道这是用来处理请求的。主分片写入后，即可搜索。 前言 说明：本文章使用的ES版本是：6.7.0 在上一篇文章搜索引擎ElasticSearch的启动过程中，介绍了ES的启动过程。 由此可知，在ES启动过程中，创建Node对象（new Node(env...

    mudiyouyou 评论0 收藏0

  • Elasticsearch 索引的映射配置详解

    摘要：本文就从的索引映射如何配置开始讲起。信息格式的配置支持为每个字段指定信息格式，以满足通过改变字段被索引的方式来提高性能的条件。 showImg(https://segmentfault.com/img/remote/1460000015981864?w=1280&h=719); 概述 Elasticsearch 与传统的 SQL数据库的一个明显的不同点是，Elasticsearch ...

    voidking 评论0 收藏0

发表评论

登陆后可评论

0条评论

MSchumi

男|高级讲师
我要私信

TA的文章

阅读更多

云社区相关服务

提问 提问 学习 学习 认证 认证 产品 产品 技术服务 技术服务 售前咨询 售前咨询
最新活动
阅读需要支付1元查看
<