原文地址

上次寫了關于 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 的精度問題蛋疼一把.
完整結果太長了, 貼個 gisthttps://gist.github.com/xguox/077e18afe24f52f6e2b45efb0b4e304f
Elasticsearch 5 (Lucene 6) 的 BM25 算法
Elasticsearch 前不久發布了 5.0 版本, 基于 Lucene 6, 默認使用了 BM25 評分算法.
BM25 的 BM 是縮寫自 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 相關度算法