Press "Enter" to skip to content

Elasticsearch相似度算分TF-IDF BM25

本站内容均来自兴趣收集,如不慎侵害的您的相关权益,请留言告知,我们将尽快删除.谢谢.

控制相关度

 

处理结构化数据(比如:时间、数字、字符串、枚举)的数据库,只需检查文档(或关系数据库里的行)是否与查询匹配。

 

布尔的是/非匹配是全文搜索的基础,但不止如此,我们还要知道每个文档与查询的相关度,在全文搜索引擎中不仅需要找到匹配的文档,还需根据它们相关度的高低进行排序。

 

全文相关的公式或 相似算法(similarity algorithms) 会将多个因素合并起来,为每个文档生成一个相关度评分 _score 。这里,我们会验证各种可变部分,然后讨论如何来控制它们。

 

当然,相关度不只与全文查询有关,也需要将结构化的数据考虑其中。可能我们正在找一个度假屋,需要一些的详细特征(空调、海景、免费 WiFi ),匹配的特征越多相关度越高。可能我们还希望有一些其他的考虑因素,如回头率、价格、受欢迎度或距离,当然也同时考虑全文查询的相关度。

 

所有的这些都可以通过 Elasticsearch 强大的评分基础来实现。

 

先从理论上介绍 Lucene 是如何计算相关度的,然后通过实际例子说明如何控制相关度的计算过程。

 

相关度评分理论

 

Lucene(或 Elasticsearch)使用 布尔模型(Boolean model)查找匹配文档,并用一个名为 实用评分函数(practical scoring function)的公式来计算相关度。这个公式借鉴了 词频/逆向文档频率(term frequency/inverse document frequency) 和 向量空间模型(vector space model)。

 

布尔模型

 

布尔模型(Boolean Model) 只是在查询中使用 ANDORNOT (与、或和非)这样的条件来查找匹配的文档,以下查询:

 

full AND text AND search AND (elasticsearch OR lucene)

 

会将所有包括词 fulltextsearch ,以及 elasticsearchlucene 的文档作为结果集。

 

这个过程简单且快速,它将所有可能不匹配的文档排除在外。

 

词频/逆向文档频率(TF/IDF)

 

当匹配到一组文档后,需要根据相关度排序这些文档,不是所有的文档都包含所有词,有些词比其他的词更重要。一个文档的相关度评分部分取决于每个查询词在文档中的 权重

 

词在文档中出现的频度是多少?频度越高,权重 越高 。 5 次提到同一词的字段比只提到 1 次的更相关。词频的计算方式如下:

 

tf(t in d) = √frequency

 

t 在文档 d 的词频( tf )是该词在文档中出现次数的平方根。

 

如果不在意词在某个字段中出现的频次,而只在意是否出现过,则可以在字段映射中禁用词频统计:

 

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

 

将参数 index_options 设置为 docs 可以禁用词频统计及词频位置,这个映射的字段不会计算词的出现次数,对于短语或近似查询也不可用。要求精确查询的 not_analyzed 字符串字段会默认使用该设置。

 

逆向文档频率

 

词在集合所有文档里出现的频率是多少?频次越高,权重 越低 。常用词如 andthe 对相关度贡献很少,因为它们在多数文档中都会出现,一些不常见词如 elastichippopotamus 可以帮助我们快速缩小范围找到感兴趣的文档。逆向文档频率的计算公式如下:

 

idf(t) = 1 + log ( numDocs / (docFreq + 1))

 

t 的逆向文档频率( idf )是:索引中文档数量除以所有包含该词的文档数,然后求其对数。

 

字段长度归一值

 

字段的长度是多少?字段越短,字段的权重 越高 。如果词出现在类似标题 title 这样的字段,要比它出现在内容 body 这样的字段中的相关度更高。字段长度的归一值公式如下:

 

norm(d) = 1 / √numTerms

 

字段长度归一值( norm )是字段中词数平方根的倒数。

 

字段长度的归一值对全文搜索非常重要,许多其他字段不需要有归一值。无论文档是否包括这个字段,索引中每个文档的每个 string 字段都大约占用 1 个 byte 的空间。对于 not_analyzed 字符串字段的归一值默认是禁用的,而对于 analyzed 字段也可以通过修改字段映射禁用归一值:

 

PUT /my_index
{
  "mappings": {
    "doc": {
      "properties": {
        "text": {
          "type": "string",
          "norms": { "enabled": false } 
        }
      }
    }
  }
}

 

这个字段不会将字段长度归一值考虑在内,长字段和短字段会以相同长度计算评分。

 

对于有些应用场景如日志,归一值不是很有用,要关心的只是字段是否包含特殊的错误码或者特定的浏览器唯一标识符。字段的长度对结果没有影响,禁用归一值可以节省大量内存空间。

 

综合使用

 

以下三个因素——词频(term frequency)、逆向文档频率(inverse document frequency)和字段长度归一值(field-length norm)——是在索引时计算并存储的。最后将它们结合在一起计算单个词在特定文档中的 权重

 

前面公式中提到的 文档 实际上是指文档里的某个字段,每个字段都有它自己的倒排索引,因此字段的 TF/IDF 值就是文档的 TF/IDF 值。

 

向量空间模型

 

向量空间模型(vector space model) 提供一种比较多词查询的方式,单个评分代表文档与查询的匹配程度,为了做到这点,这个模型将文档和查询都以 向量(vectors) 的形式表示:

 

向量实际上就是包含多个数的一维数组,例如:

 

[1,2,5,22,3,8]

 

在向量空间模型里,向量空间模型里的每个数字都代表一个词的 权重 ,与词频/逆向文档频率计算方式类似。

 

尽管 TF/IDF 是向量空间模型计算词权重的默认方式,但不是唯一方式。Elasticsearch 还有其他模型如 Okapi-BM25 。TF/IDF 是默认的因为它是个经检验过的简单又高效的算法,可以提供高质量的搜索结果。

 

设想如果查询 “happy hippopotamus” ,常见词 happy 的权重较低,不常见词 hippopotamus 权重较高,假设 happy 的权重是 2 , hippopotamus 的权重是 5 ,可以将这个二维向量—— [2,5] ——在坐标系下作条直线,线的起点是 (0,0) 终点是 (2,5) ,如下:

 

 

现在,设想我们有三个文档:

 

 

I am happy in summer 。

 

After Christmas I’m a hippopotamus

 

The happy hippopotamus helped Harry 。

 

 

可以为每个文档都创建包括每个查询词—— happyhippopotamus ——权重的向量,然后将这些向量置入同一个坐标系中,如下:

 

 

向量之间是可以比较的,只要测量查询向量和文档向量之间的角度就可以得到每个文档的相关度,文档 1 与查询之间的角度最大,所以相关度低;文档 2 与查询间的角度较小,所以更相关;文档 3 与查询的角度正好吻合,完全匹配。

 

在实际中,只有二维向量(两个词的查询)可以在平面上表示,幸运的是, 线性代数 ——作为数学中处理向量的一个分支——为我们提供了计算两个多维向量间角度工具,这意味着可以使用如上同样的方式来解释多个词的查询。

 

忽略TF/IDF

 

有时候我们根本不关心 TF/IDF ,只想知道一个词是否在某个字段中出现过。可能搜索一个度假屋并希望它能尽可能有以下设施:

WiFi
Garden(花园)
Pool(游泳池)

这个度假屋的文档如下:

 

{ "description": "A delightful four-bedroomed house with ... " }

 

可以用简单的 match 查询进行匹配:

 

GET /_search
{
  "query": {
    "match": {
      "description": "wifi garden pool"
    }
  }
}

 

但这并不是真正的 全文搜索 ,此种情况下,TF/IDF 并无用处。我们既不关心 wifi 是否为一个普通词,也不关心它在文档中出现是否频繁,关心的只是它是否曾出现过。实际上,我们希望根据房屋不同设施的数量对其排名——设施越多越好。如果设施出现,则记 1 分,不出现记 0 分。

 

constant_score查询

 

constant_score 查询中,它可以包含查询或过滤,为任意一个匹配的文档指定评分 1 ,忽略 TF/IDF 信息:

 

GET /_search
{
  "query": {
    "bool": {
      "should": [
        { "constant_score": {
          "query": { "match": { "description": "wifi" }}
        }},
        { "constant_score": {
          "query": { "match": { "description": "garden" }}
        }},
        { "constant_score": {
          "query": { "match": { "description": "pool" }}
        }}
      ]
    }
  }
}

 

或许不是所有的设施都同等重要——对某些用户来说有些设施更有价值。如果最重要的设施是游泳池,那我们可以为更重要的设施增加权重:

 

GET /_search
{
  "query": {
    "bool": {
      "should": [
        { "constant_score": {
          "query": { "match": { "description": "wifi" }}
        }},
        { "constant_score": {
          "query": { "match": { "description": "garden" }}
        }},
        { "constant_score": {
          "boost":   2 
          "query": { "match": { "description": "pool" }}
        }}
      ]
    }
  }
}

 

pool 语句的权重提升值为 2 ,而其他的语句为 1

 

最终的评分并不是所有匹配语句的简单求和, 协调因子(coordination factor) 和 查询归一化因子(query normalization factor) 仍然会被考虑在内。

 

我们可以给 features 字段加上 not_analyzed 类型来提升度假屋文档的匹配能力:

 

{ "features": [ "wifi", "pool", "garden" ] }

 

默认情况下,一个 not_analyzed 字段会禁用 字段长度归一值(field-length norms) 的功能,并将 index_options 设为 docs 选项,禁用 词频 ,但还是存在问题:每个词的 倒排文档频率 仍然会被考虑。

 

可插拔的相似度算法

 

可插拔的相似度算法(Pluggable Similarity Algorithms)。

 

Okapi BM25

 

能与 TF/IDF 和向量空间模型媲美的就是 Okapi BM25 ,它被认为是 当今最先进的 排序函数。 BM25 源自 概率相关模型(probabilistic relevance model),而不是向量空间模型,但这个算法也和 Lucene 的实用评分函数有很多共通之处。

 

BM25 同样使用词频、逆向文档频率以及字段长归一化,但是每个因子的定义都有细微区别。与其详细解释 BM25 公式,倒不如将关注点放在 BM25 所能带来的实际好处上。

 

词频饱和度

 

TF/IDF 和 BM25 同样使用 逆向文档频率 来区分普通词(不重要)和非普通词(重要),同样认为文档里的某个词出现次数越频繁,文档与这个词就越相关。

 

不幸的是,普通词随处可见,实际上一个普通词在同一个文档中大量出现的作用会由于该词在 所有 文档中的大量出现而被抵消掉。

 

曾经有个时期,将 普通的词(或 停用词 ,参见 停用词从索引中移除被认为是一种标准实践,TF/IDF 正是在这种背景下诞生的。TF/IDF 没有考虑词频上限的问题,因为高频停用词已经被移除了。

 

Elasticsearch 的 standard 标准分析器( string 字段默认使用)不会移除停用词,因为尽管这些词的重要性很低,但也不是毫无用处。这导致:在一个相当长的文档中,像 theand 这样词出现的数量会高得离谱,以致它们的权重被人为放大。

 

另一方面,BM25 有一个上限,文档里出现 5 到 10 次的词会比那些只出现一两次的对相关度有着显着影响。但是如图 TF/IDF 与 BM25 的词频饱和度 所见,文档中出现 20 次的词几乎与那些出现上千次的词有着相同的影响。

 

这就是 非线性词频饱和度(nonlinear term-frequency saturation)

 

 

字段长度归一化

 

在字段长归一化 中,我们提到过 Lucene 会认为较短字段比较长字段更重要:字段某个词的频度所带来的重要性会被这个字段长度抵消,但是实际的评分函数会将所有字段以同等方式对待。它认为所有较短的 title 字段比所有较长的 body 字段更重要。

 

BM25 当然也认为较短字段应该有更多的权重,但是它会分别考虑每个字段内容的平均长度,这样就能区分短 title 字段和 title 字段。

 

BM25 调优

 

不像 TF/IDF ,BM25 有一个比较好的特性就是它提供了两个可调参数:

 

k1

 

这个参数控制着词频结果在词频饱和度中的上升速度。默认值为 1.2 。值越小饱和度变化越快,值越大饱和度变化越慢。

 

b

 

这个参数控制着字段长归一值所起的作用, 0.0 会禁用归一化, 1.0 会启用完全归一化。默认值为 0.75

 

在实践中,调试 BM25 是另外一回事, k1b 的默认值适用于绝大多数文档集合,但最优值还是会因为文档集不同而有所区别,为了找到文档集合的最优值,就必须对参数进行反复修改验证。

 

参考资料:

 

https://www.elastic.co/guide/cn/elasticsearch/guide/current/index.html

Be First to Comment

发表评论

您的电子邮箱地址不会被公开。