原创

Elasticsearch基础(十四)——相关度分数算法

在使用Elasticsearch检索的过程中,结果都会包含一个相关度分数(relevance score),本章我们就来看看Elasticsearch到底是如何计算这个分数的。

Elasticsearch进行相关度分数计算时,核心步骤就包含三点:

  1. 利用boolean model进行document过滤;
  2. 利用TF/IDF算法计算单个term的分数;
  3. 利用vector space model整合最终的相关度分数。

一、bool model

所谓bool model,就是Elasticsearch中的各种doc过滤语法,比如bool命令中的must/should/must not等等。核心目的就是过滤出包含检索关键字的document,提升后续分数计算的性能。

这一过程仅仅是过滤,不进行分数计算。

二、TF/IDF算法

TF/IDF(term frequency/inverse document frequency)算法,是Elasticsearch计算相关度分数的基础,用于计算单个term在document中的分数

单个term是什么意思?

比如,我们的检索关键字是”hello world“,index中包含如下的document:

# doc1
hello you, and world is very good

那么TF/IDF算法会对"hello"这个term计算出一个doc1分数,对”world“再计算出一个doc1分数。至于”hello world“这整个关键字在doc1中的综合分数,TF/IDF是不管的。

TF/IDF算法的核心思想就三点:

  • term frequency:表示检索的term,在单个document中的各个词条中出现的频次,出现的次数越多,该document相关度越高;

  • inverse document frequency:表示检索的term,在该索引的所有document中出现的频次,出现的次数越少,包含该term的document相关度越高;

  • Field-length norm:表示document的field内容长度越短,相关度越高。

2.1 term frequency

还是通过示例来理解,假设我们有一个搜索请求,关键字是“hello world”,索引中包含下面两条document:

# doc1
hello you, and world is very good
# doc2
hello, how are you

“hello world”进行分词后,拆成两个term——“hello”和“world”,显然doc1既包含“hello”又包含“world”,doc2只包含“hello”,所以doc1更相关。

2.2 inverse document frequency

再来看下inverse document frequency,检索请求还是“hello world”,假设索引中一共包含1000条document,我们只列出其中两条:

# doc1
hello, today is very good
# doc2
hi world, how are you

如果根据term frequency规则,doc1和doc2的相关度应该是相同的,但是如果‘hello“在该索引的1000条document中,有800条document都包含它,而‘world“只有200条document包含,那么doc2的相关度就比doc1更高。

这里好好思考下,为什么term在整个document列表中出现的次数越多,包含它的doc相关度反而越低。因为出现的次数越少,说明包含那个term的doc的区分度越高。

2.3 Field-length norm

举个例子,检索请求还是“hello world”,假设索引中一共包含2条document:

# doc1
{ "title": "hello article", "content": "babaaba 1万个单词" }
# doc2
{ "title": "my article", "content": "blablabala 1万个单词,hi world" }

doc1中,”hello“出现在title字段,doc2中,”world“出现在content字段,显然title字段的内容长度远小于content字段的内容长度,所以doc1的相关度比doc2更高。

2.4 示例

我们可以通过explain命令,查看Elasticsearch对某个query的评分到底是如何计算的:

GET /test_index/_search?explain
{
  "query": {
    "match": {
      "test_field": "test hello"
    }
  }
}

也可以通过如下命令查看某个document是如何被一个query匹配上,比如下面是查看id为6的document是如何被匹配上的:

GET /test_index/6/_explain
{
  "query": {
    "match": {
      "test_field": "test hello"
    }
  }
}

三、向量空间模型算法

TF/IDF算法只能计算单个term在document中的分数。那么,如何计算整个搜索关键词在各个doc中的综合分数呢?这就要靠vector space model了。

vector space model的核心思想其实就是计算两个向量,然后相乘得到最终分:

  1. 每个term在所有document的分数——query vector;
  2. 每个term在各个document的分数——doc vector;
  3. 计算doc vector对于query vector的弧度(其实就是线性代数中的向量运算)。

3.1 query vector

vector space model算法,会首先根据TF/IDF算法的结果,计算出一个query vector,这个query vector就是每一个term对所有document的综合评分。

举个例子,假设index中包含3条document,搜索关键字是”hello world“:

# doc1
hello, today is very good
# doc2
hi world, how are you
# doc3
hello world

那么,对于hello这个term,vector space model算法会算出它对所有doc的评分,比如等于2;world这个term,基于所有doc的评分是5,那么query vector = [2, 5]

query vector的计算过程不用去深究,底层涉及线性代数之类的高等数学知识,我们只要知道vector space model会计算出这样一个vector,vector包含了每个term对所有document的评分就行了。

3.2 doc vector

doc vector,就是每个term在各个document中的分数组成的一个向量。

比如,”hello“在doc1中的分数是2,doc2中是0,doc3中是2;"world"在doc1中的分数是0,doc2中是5,doc3中是5,那么最终计算出的doc vector是下面这样的:

[2 , 0]
[0 , 5]
[2 , 5]

3.3 弧度计算

所谓弧度计算,就是根据doc vector和query vector进行向量运算,最终得到每个doc对多个term的总分数。涉及大量数学知识,此处就不再展开了。

四、Lucene的相关度分数函数

最后,我们来看下Lucene计算相关度分数的算法,Lucene中有一个叫做practical scoring的函数,综合了上面我们讲的TF/IDF算法和vector space model:

score(q,d)  =  
            queryNorm(q)  
          · coord(q,d)    
          · ∑ (           
                tf(t in d)   
              · idf(t)2      
              · t.getBoost() 
              · norm(t,d)    
            ) (t in q)

这个公式的最终结果,就是一个query(入参q),对一个doc(入参d)的最终总评分,也就是搜索关键字对某个document的相关度分数:

  • queryNorm(q):用来让一个doc的分数处于一个合理的区间内,不要太离谱;
  • coord(q,d): 对更加匹配的doc,进行一些分数上的成倍奖励;
  • tf(t in d):计算每个term对doc的分数,就是TF/IDF算法中的term frequency步骤;
  • idf(t)2:计算每个term对doc的分数,就是TF/IDF算法中的inverse document frequency步骤;
  • t.getBoost():计入字段权重;
  • norm(t,d):计算每个term对doc的分数,就是TF/IDF算法中的Field-length norm步骤。

五、总结

本章,我讲解了Elasticsearch进行相关度分数计算的核心原理,相关度分数算法基于TF/IDF和vector space model实现。Elasticsearch的底层其实调用了Lucene的practical scoring函数来完成分数的计算。

正文到此结束
本文目录