搜索引擎 ElasticSearch 的分数 (_score) 是怎么计算得出 (2.X & 5.X)

xguox · December 19, 2016 · Last by xguox replied at March 07, 2017 · 19700 hits
Topic has been selected as the excellent topic by the admin.

上次写了关于 Elasticsearch 如何分词索引, 接着继续写 Elasticsearch 怎么计算搜索结果的得分 (_score).

Elasticsearch 默认是按照文档与查询的相关度 (匹配度) 的得分倒序返回结果的。得分 (_score) 就越大,表示相关性越高。

所以,相关度是啥?分数又是怎么计算出来的?(全文检索和结构化的 SQL 查询不太一样,虽然看起来结果比较'飘忽', 但也是可以追根问底的)


在 Elasticsearch 中,标准的算法是 Term Frequency/Inverse Document Frequency, 简写为 TF/IDF, (刚刚发布的 5.0 版本,改为了据说更先进的 BM25 算法)

Term Frequency

某单个关键词 (term) 在某文档的某字段中出现的频率次数,显然,出现频率越高意味着该文档与搜索的相关度也越高

具体计算公式是 tf(q in d) = sqrt(termFreq)

另外,索引的时候可以做一些设置,"index_options": "docs" 的情况下,只考虑 term 是否出现 (命中), 不考虑出现的次数。

PUT /my_index
{
  "mappings": {
    "doc": {
      "properties": {
        "text": {
          "type":          "string",
          "index_options": "docs"
        }
      }
    }
  }
}

Inverse document frequency

某个关键词 (term) 在索引 (单个分片) 之中出现的频次。出现频次越高,这个词的相关度越低。相对的,当某个关键词 (term) 在一大票的文档下面都有出现,那么这个词在计算得分时候所占的比重就要比那些只在少部分文档出现的词所占的得分比重要低。说的那么长一句话,用人话来描述就是 "物以稀为贵", 比如,'的', '得', 'the' 这些一般在一些文档中出现的频次都是非常高的,因此,这些词占的得分比重远比特殊一些的词 (如'Solr', 'Docker', '哈苏') 占比要低,

具体计算公式是 idf = 1 + ln(maxDocs/(docFreq + 1))

Field-length Norm

字段长度,这个字段长度越短,那么字段里的每个词的相关度也就越大。某个关键词 (term) 在一个短的句子出现,其得分比重比在一个长句子中出现要来的高。

具体计算公式是 norm = 1/sqrt(numFieldTerms)

默认每个 analyzed 的 string 都有一个 norm 值,用来存储该字段的长度,

用 "norms": { "enabled": false } 关闭以后,评分时,不管文档的该字段长短如何,得分都一样。

PUT /my_index
{
  "mappings": {
    "doc": {
      "properties": {
        "text": {
          "type": "string",
          "norms": { "enabled": false }
        }
      }
    }
  }
}
最后的得分是三者的乘积 tf * idf * norm

以上描述的是最原始的针对单个关键字 (term)的搜索。如果是有多个搜索关键词 (terms)的时候,还要用到的 Vector Space Model

如果查询复杂些,或者用到一些修改了分数的查询,或者索引时候修改了字段的权重,比如 function_score 之类的,计算方式也就又更复杂一些。

Explain

看上去 TF/IDF 的算法已经一脸懵逼吓跑人了,不过其实,用 Explain 跑一跑也没啥,虽然各种开方,自然对数的,Google 一个科学计算器就是了。

举个例子

/*先删掉索引, 如果有的话*/
curl -XDELETE 'http://localhost:9200/blog'

curl -XPUT 'http://localhost:9200/blog/' -d '
{
  "mappings": {
     "post": {
        "properties": {
           "title": {
              "type": "string",
              "analyzer": "standard",
              "term_vector": "yes"
           }
        }
     }
  }
}'

存入一些文档 (Water 随手加进去测试的.)

curl -s -XPOST localhost:9200/_bulk -d '
{ "create": { "_index": "blog", "_type": "post", "_id": "1" }}
{ "title": "What is the best water temperature, Mr Water" }
{ "create": { "_index": "blog", "_type": "post", "_id": "2" }}
{ "title": "Water no symptoms" }
{ "create": { "_index": "blog", "_type": "post", "_id": "3" }}
{ "title": "Did Vitamin B6 alone work for you? Water?" }
{ "create": { "_index": "blog", "_type": "post", "_id": "4" }}
{ "title": "The ball drifted on the water." }
{ "create": { "_index": "blog", "_type": "post", "_id": "5" }}
{ "title": "No water no food no air" }
'

bulk insert 以后先用 Kopf 插件输出看一下,5 个文档并不是平均分配在 5 个分片的,其中,编号为 2 的这个分片里边有两个文档,其中编号为 0 的那个分片是没有分配文档在里面的。

接下来,搜索的同时 explain

原本输出的 json 即使加了 pretty 也很难看,换成 yaml 会好不少

curl -XGET "http://127.0.0.1:9200/blog/post/_search?explain&format=yaml" -d '
{
  "query": {
    "term": {
      "title": "water"
    }
  }
}'

输出如图 (json)

可以看到五个文档都命中了这个查询,注意看每个文档的 _shard

整个输出 yml 太长了,丢到最后面,只截取了其中一部分,如图,

返回排名第一的分数是 _score: 0.2972674, _shard(2),

"weight(title:water in 0) [PerFieldSimilarity], result of:" 这里的 0 不是 _id, 只是 Lucene 的一个内部文档 ID, 可以忽略。

排名第一和第二的两个文档刚好是在同一个分片的,所以跟另外三个的返回结果有些许不一样,主要就是多了一个 queryWeight, 里面的 queryNorm 只要在同一分片下,都是一样的,总而言之,这个可以忽略 (至少目前这个例子可以忽略)

只关注 fieldWeight, 排名第一和第二的的 tf 都是 1,

idf(docFreq=2, maxDocs=2) 中,docFreq 和 maxDocs 都是针对单个分片而言,2 号分片一共有 2 个文档 (maxDocs), 然后命中的文档也是两个 (docFreq).

所以 idf 的得分,根据公式,1 + ln(maxDocs/(docFreq + 1)) 是 0.59453489189

最后 fieldNorm, 这个 field 有三个词,所以是 1/sqrt(3), 但是按官方给的这个公式怎么算都不对,不管哪个文档。后来查了一下,说是 Lucene 存这个 lengthNorm 数据时候都是用的 1 byte 来存,所以不管怎么着都会丢掉一些精度。呵呵哒了 = . =

最后的最后,总得分 = 1 * 0.5945349 * 0.5 = 0.2972674.

同理其他的几个文档也可以算出这个得分,只是都要被 fieldNorm 的精度问题蛋疼一把。

完整结果太长了,贴个 gist
https://gist.github.com/xguox/077e18afe24f52f6e2b45efb0b4e304f


Elasticsearch 5 (Lucene 6) 的 BM25 算法

Elasticsearch 前不久发布了 5.0 版本, 基于 Lucene 6, 默认使用了 BM25 评分算法。

BM25BM 是缩写自 Best Match, 25 貌似是经过 25 次迭代调整之后得出的算法。它也是基于 TF/IDF 进化来的。Wikipedia 那个公式看起来很吓唬人,尤其是那个求和符号,不过分解开来也是比较好理解的。

总体而言,主要还是分三部分,TF - IDF - Document Length

IDF 还是和之前的一样. 公式 IDF(q) = 1 + ln(maxDocs/(docFreq + 1))

f(q, D) 是 tf(term frequency)

|d| 是文档的长度,avgdl 是平均文档长度。

先不看 IDF 和 Document Length 的部分,变成 tf * (k + 1) / (tf + k),

相比传统的 TF/IDF (tf(q in d) = sqrt(termFreq)) 而言, BM25 抑制了 tf 对整体评分的影响程度, 虽然同样都是增函数,但是,BM25 中,tf 越大,带来的影响无限趋近于 (k + 1), 这里 k 值通常取 [1.2, 2], 而传统的 TF/IDF 则会没有临界点的无限增长。

文档长度的影响, 同样的,可以看到,命中搜索词的情况下,文档越短,相关性越高,具体影响程度又可以由公式中的 b 来调整,当设值为 0 的时候,就跟之前 'TF/IDF' 那篇提到的 "norms": { "enabled": false } 一样,忽略文档长度的影响。

综合起来,

k = 1.2

b = 0.75

idf * (tf * (k + 1)) / (tf + k * (1 - b + b * (|d|/avgdl)))

最后再对所有的 terms 求和。就是 Elasticsearch 5 中一般查询的得分了。


Related:

http://opensourceconnections.com/blog/2015/10/16/bm25-the-next-generation-of-lucene-relevation/

What Is Relevance?

From:

Elasticsearch 的分数 (_score) 是怎么计算得出
Elasticsearch 5.X(Lucene 6) 的 BM25 相关度算法

Nice, 谢谢总结~ ES 也可以自己写 scorer, 前几天因为业务需要写了个感觉挺不错的

看上去 TF/IDF 的算法已经一脸懵逼吓跑人了

信息处理中基础中的基础。。。

jasl mark as excellent topic. 20 Dec 00:48

#1 楼 @jiazhen 自己写 scorer? 是指 function score 伐?

#2 楼 @gyorou 各种对数函数什么的高中以后几乎就再也没怎么接触过了 ╮(╯_╰)╭

#4 楼 @xguox 当年也是被数学日的厉害所以半路出家做 web 了,现在真是后悔莫及。。。

6 Floor has deleted
这是企业的maping  document_type: 'ent'
mapping dynamic: false do
    indexes :name, type: 'text', analyzer: 'smartcn'
   ...
end

品牌document_type 'brand'
mapping _parent: { type: 'ent' }, _routing: { required: true } do
    indexes :name, type: 'text', analyzer: 'smartcn'
    ...
end

产品document_type 'product'
mapping _parent: { type: 'brand' }, _routing: { required: true } do
    indexes :name, type: 'text', analyzer: 'smartcn'
    ...
end

三个 document 在同一个 index 中,现在创建对应的 ent, brand 和 product 之后,执行搜索,发现经常命中不了产品层级,如果把 es 的 index 删除重新创建数据的话,有时会命中产品层级,这是为啥呢?难道是产品的 maping 里面的_routing 设置有问题然后 ent-brand-product 不在同一个分片上?brand 层级的东西每次都能命中,product 层级的想要命中就得看心情了

搜索时执行的 query 如下:

def self.search(query)
    __elasticsearch__.search(
      {
        query: {
          bool: {
            "filter": {
                "term": {
                   "verified": "true"
                }
            },
            should: [
              {
                multi_match: {
                  query: query,
                  fields: ['name^3', 'short_name^4', 'vision^2', 'introduction']
                }
              },
              {
                has_child: {
                  type: 'brand',
                  query: {
                    bool: {
                      "filter": {
                          "term": {
                             "verified": "true"
                          }
                      },
                      should: [
                        {
                          multi_match: {
                            query: query,
                            fields: ['name^3', 'connotation^2', 'story']
                          }
                        },
                        {
                          has_child: {
                            type: 'product',
                            query: {
                              bool: {
                                "filter": {
                                    "term": {
                                       "is_published": "true"
                                    }
                                },
                                should: [
                                  {
                                    multi_match: {
                                      query: query,
                                      fields: ['name^3', 'description^2', 'introduction']
                                    }
                                  }
                                ]
                              }
                            },
                            inner_hits: {
                              size: 3,
                              _source: true
                            }
                          }
                        }
                      ]
                    }
                  },
                  inner_hits: {
                      size: 1,
                      _source: true
                  }
                }
              }
            ]
          }
        } 
      }
    )
  end

很难通过你贴的这些得出结果,因为没有对应的数据长什么样,分词分出来的结果是什么样的也看不出。可以用 termvector 看看, 辣么长的一串查询 没命中的话,如果结果集较少,可以尝试删减一些查询条件,逐个分析哪里导致的吧。 ╮(╯_╰)╭

Reply to xguox

找到问题了,在 index 的时候没有指定路由,现在这个问题暂时解决了 多谢

12 Floor has deleted

关于搜索结果排序及分页的问题,response.records 这种写法可以对搜索结果进行分页,但是排序是按照 record 的主键排的而不是按照得分排序,response.records.to_a 这种写法的排序是按照得分排的,但是又不能用 kaminari 或者 will_pagenation 对搜索结果分页了,现在又想分页还想排序是按照得分大小来排,这个该怎么解决 @xguox 😂 😂

Pagination

You can implement pagination with the from and size search parameters. However, search results can be automatically paginated with the kaminari or will_paginate gems. (The pagination gems must be added before the Elasticsearch gems in your Gemfile, or loaded first in your application.)

response.page(2).results
response.page(2).records
You need to Sign in before reply, if you don't have an account, please Sign up first.