【贝壳网】ElasticSearch 相关性计算原理及实践



转载请注明 AIQ - 最专业的机器学习大数据社区  http://www.6aiq.com

AIQ 机器学习大数据 知乎专栏 点击关注

0 前言

在贝壳找房,房源、小区、看点等涉及到文本搜索的应用都是以 ES 作为底层搜索和召回组件,经 ES 相关性计算后粗筛出结果,再对粗筛结果做二次排序。所以,ES 的相关性计算好坏对这些应用的用户体验有直接或间接影响,对 ES 相关性调优是很有必要。本文结合 ES 在贝壳找房这些应用的实践经验,介绍 ES 的相关性计算原理,以及如何对相关性调优。

1 ES 相关性计算方式

ES 的打分机制是基于 tf-idf 算法进行改进得到的。本节分成三个部分,第一部分简单介绍 tf-idf 算法,第二部分介绍 ES 早期基于 tf-idf 的简单改进,第三部分介绍现阶段使用的打分算法 BM25。

1.1 tf-idf 算法

tf-idf 算法可以分成 tf 和 idf 两部分,通过将两部分乘积完成相关性计算。词频(term frequency,tf)指的是某一个给定的词语在该文件中出现的频率。tf 是对词数(term count)的归一化,防止偏向长文档(对于同一个词,通常长文档出现的次数会更多)。通过公式 1.1 计算得到 tf,freq 表示词 W 出现次数,fieldLength 表示该文档总词数。

词频能够在一定程度上衡量一个词语的重要性,但是如果简单的用词频衡量相关度是不准确的,对于助词等一些无实际意义的词汇,在每篇文档中出现的次数可能都很多,但是他们和文档的主题并不相关。所以,不能简单用词频来唯一衡量这个词语跟文档的相关度。因此有了逆向文档频率 (Inverse Dcument Frequency, 缩写为 IDF),利用公式 1.2 计算得到 idf,其中 numDocs 表示全部文档数,docFreq 表示包含词语 W 的文档数。逆向文档频率表示越多的文档包含这个词,这个词就越不重要。

1.2 ES 的 tf-idf 计算方式

ES 的打分过程是以 TF-IDF 为基础,做了简单调整作为默认相似度计算方式,计算公式为 1.3:

docCount:索引中文档数量;docFreq: 包含关键字的文档数量。在 idf 中,
ES 对 docFreq 进行加 1 是为了避免分母为 0;在 tf 中,进行了开根号,是为了减小 tf 的增速;限制 tf 的增速,主要是针对多个词进行检索可能出现的问题进行的优化。

一个 query 分完词后得到 ab…n 个词语,利用公式 1.3 以及 1.4 可以计算得到每个文档针对这个 query 的相关性。

1.3 BM25 计算方式

ES 新的相关性计算方式(BM25),利用了 tf-idf 的思想,但具体计算过程和 tf-idf 有了很大的差异。

BM25 在计算 tf 中增加了一个常量 k(默认取 1.2),这个参数控制着词频结果在词频饱和度中的上升速度,过快的上升速度会导致什么问题呢?例如有一个搜索 query,分词为 abcd,过快的增长速度可能会导致包含较少词的文档相关性比同时包含更多词的相关性更大,这是不符合预期的。

BM25 在计算 tf 过程中里除了引入 k 外,引入另外两个参数:L 和 b。avgFieldLength 表示文档的平均文档长度,单个文档长度对相关性的影响力与它和平均长度的比值有关系。L 是文档长度与平均长度的比值。b 是一个常数,这个参数控制着文档长度归一化粒度, 0 禁用归一化, 1.0 启用完全归一化,默认值为 0.75。最终公式为 1.6:

在实践中,k 和 b 的默认值适用于绝大多数文档集合,但最优值还是会因为文档集不同而有所区别,为了找到某个文档集合的最优值,就必须对参数进行反复修改验证。

在 BM25 中,idf 也进行了调整,转换成公式 1.7。

2 相关性调优

2.1 multi_match 检索

multi_match 打分方式会对每个字段进行单独打分,待每个字段打分完成后,将结果进行合并,计算方式主要有 most_fields、best_fields 以及 cross_fields 三种。

在搜索过程中会对 query 进行分词,再将分词结果分别和每个字段进行匹配。例如用户输入 query“贝壳找房大平台”,分词结果为“贝壳”,“找房”,“大平台”,每个词都对应一个 should 查询语句。

most_fields 和 best_fields 是一种以字段为中心的检索方式,计算过程如图 1 所示,fn() 分别为 sum 和 max。

图 1

而 cross_fields 是一种类似于以词为中心的搜索分值计算方式。cross_fields 的计算过程是把所有字段合并成一个大的字段进行计算。

2.1.1 most_fields 计分方式

对于一个文档有 title,overview,content 等多个字段,在利用 most_fields(多字段匹配)进行检索时,es 会单独计算每个字段的得分,然后将结果合并,得分为公式 2.1,其中 coord 为匹配的子条件和总的子条件比值。

2.1.2 best_fields 计分方式

best_fields(最佳字段匹配)的计算方式和 most_fields 不同,它侧重考虑分值最高的字段,计算过程见公式 2.2:

公式 2.2 中可以指定协调因子(tie_breaker),当 tie_breaker 的值为 0 时(默认为 0),只考虑得分最高的字段,当值为 1 时和 most_fields 计算方式一样。

2.1.3 cross_fields 计分方式

cross_fields 类型采用了一种类似于以词条为中心 (Term-centric) 的方法,它将所有的字段视为一个大的字段,然后在这个大字段中搜索每个词条。计算过程可以简化为公式 2.3。

以字段为中心的检索可能会导致白象化,而以词为中心的搜索方式能比较好的解决这个问题。接下来我们用一个例子简单介绍下白象化现象,我们在索引中添加两篇文档,如图 2 所示:

图 2

利用 query“albino elepahant”进行检索,按照我们的认知,文档 2 应该更相关,理应排在文档 1 之前,但是结果却不然,在以字段为中心的检索过程中,两者的得分是一致的,es 没有对“albino elepahant”整个词语进行额外的加分,而使用以词为中心的搜索就能解决这个问题。

以字段为中心的检索过程是把 query 放到每个字段进行匹配的过程,而以词为中心的检索过程则是将检索词逐词和每个字段进行匹配计算,而非整个字符串在每个字段当中进行搜索。

2.1.4 使用

全文搜索是一场查全率 (Recall) 以及查准率(Precision) 之间的战斗。三种打分类型的选择上,我们可以根据具体使用场景进行抉择。best_fields 侧重于查准率;most_fields 有利于提升查全率;cross_fields 能解决白象化现象(cross_fields 只是找到尽可能多的 field 匹配的文档,而不是某个 field 完全匹配的文档)。

在 es 中的使用方式参考代码 1。

1.  `   {`

2.  `     "query":  {`

3.  `       "multi_match":  {`

4.  `         "query":  "贝壳找房大平台",`

5.  `         "fields":  ["title","content"],`

6.  `         "type":  "most_fields",`

7.  `         "tie_breaker":  0`

8.  `       }`

9.  `     }`

10.  `   }`

代码 1

2.2 query_string 检索

利用 TF-IDF 衡量词的权重时,倾向于给不常见的词赋予高权重。有两个索引字段: first_name、last_name。假设有一篇文档的内容是:“Smith Jones”,其中 Smith 在索引的 first_name 字段,Jones 在索引的 last_name 字段。而根据人类起名字的习惯,很少有人把 词 Smith 作为 first_name,当词“Smith”出现在 first_name 字段时,相应的文档得分就会异常的高。而现在刚好有个名字 “Smith Jones”,用户查询的是:“Will Smith”,但是返回的最佳匹配文档是:“Smith Jones”,而不是 "Will Smith" 这个词。这也是一个未给整词进行额外加分造成的白象化现象。

前文介绍到 cross_fields 是一种类似于以词为中心的检索方式,可以比较好的解决白象化问题,但是 cross_fields 只是把多个字段拼成一个大的字段,并不是真正意义上的以词为中心的计算方式,接下来介绍 query_string 打分方式,一种真正意义上的以词为中心的计算过程。具体计算过程如图 3 所示:

图 3

以词为中心的搜索方式是计算每个词在对应字段中的分值,侧重于最大值,这一点与 best_fields 很像,可以通过设定 tie_breaker(新的版本用 tie_breaker,一些版本上用 dismax 字段设置),把其他字段得分纳入考虑,tie_breaker 取值为 0-1,默认为 0。以词为中心的搜索相比于 multi_match 更灵活,可以在 query 中拼写条件,query_string 默认使用所有字段,也可以在 query 中指定每个词条对应字段,同时还支持通过 analyze_wildcard 开启使用通配符功能,在 es 中的使用方式见代码 2:

1.  `GET test/_search?explain=true`

2.  `{`

3.  ` "query":  {`

4.  `   "query_string":  {`

5.  `     "query":  "贝壳 OR 找房 OR 大平台",`

6.  `     "tie_breaker":  0.1,`

7.  `     "analyze_wildcard":  false`

8.  `   }`

9.  ` }`

10.  `}`

代码 2

相比于 multi_match,query_string 强大了太多,但是在使用的时候需要谨慎,功能的强大同时也意味着更耗性能。同时,支持自定义操作逻辑也意味着可能造成信号冲突,ES 是没办法判断输入的 OR 的一个操作符还是一个词条的。

2.3. 字段值放大

在检索的时候,我们可以指定对哪些字段进行检索,ES 就会对其中的每一个字段进行打分。标题和摘要相对于内容来说更能体现一篇文档的主题,通常我们希望标题和摘要能给更大的权重。

我们可以通过 ES 的放大机制针对不同字段赋予不同的权重进行提权。通过前文介绍的计算方式得到某个字段得分,然后乘以 boost 权重,得到这个字段的最终得分,实现放大的目的。在一次搜索中,检索字段为 "title" 和 "content" 搜索 query 分词完得到 A、B 两个词,我们对 "content" 字段进行了放大处理,权重为 "boost",用 2.4 表示词 A 在字段 "content" 的相关性得分,则最终得分可以用公式 2.5 表示。

在 es 中可以使用代码 3 实现对 title 的放大。

1.  `   {`

2.  `       "query":  {`

3.  `           "multi_match":  {`

4.  `               "query":  "贝壳找房大平台",`

5.  `               "fields":  [`

6.  `                   "title^100",`

7.  `                   "content"`

8.  `               ]`

9.  `           }`

10.  `       }`

11.  `   }`

3 ES 打分过程解释信息解读

在经过一系列的优化处理后,可能结果还是不符合预期,这时候查看 es 的打分过程有助于优化相关性。es 通过向外提供 explain 参数来获取具体打分过程,
便于分析。我们就拿白化象的例子简单介绍下怎么看 es 的打分日志,我们在 "test" 索引中插入图 2 的两篇文档。

1.  `GET test/_search?explain=true`

2.  `{`

3.  ` "size":  1,`

4.  ` "query":  {`

5.  `   "multi_match":  {`

6.  `     "query":  "albino elepahant",`

7.  `     "fields":  ["titele",  "content^5"],`

8.  `     "type":  "best_fields",`

9.  `     "tie_breaker":  0.2`

10.  `   }`

11.  ` }`

12.  `}`

便于了解,我们在代码 4 中利用 multi_match 的方式进行打分,并且检索 query 为 "albino elepahant",检索的字段为 "titele", “content”,并且把 content 的权重设为 5,利用代码 4 进行请求,得到结果如代码 5(篇幅原因,精简部分不必要信息)。

1.  `{`

2.  `   "_source":  {`

3.  `       "titele":  "albino",`

4.  `       "content":  "elepahant"`

5.  `   },`

6.  `   "_explanation":  {`

7.  `       "value":  1.4959468,  ❶`

8.  `       "description":  "max plus 0.2 times others of:",  ❷`

9.  `       "details":  [  ❸`

10.  `           {`

11.  `               "value":  1.4384104,`

12.  `               "description":  "sum of:",`

13.  `               "details":  [`

14.  `                   {`

15.  `                       "value":  1.4384104,`

16.  `                       "description":  "weight(content:elepahant in 0) [PerFieldSimilarity], result of:",❹`

17.  `                       "details":  [`

18.  `                           {`

19.  `                               "value":  1.4384104,`

20.  `                               "description":  "score(doc=0,freq=1.0 = termFreq=1.0\n), product of:",❺`

21.  `                               "details":  [`

22.  `                                   {`

23.  `                                       "value":  5.0,`

24.  `                                       "description":  "boost",  ❻`

25.  `                                       "details":  [`

27.  `                                       ]`

28.  `                                   },`

29.  `                                   {`

30.  `                                       "value":  0.2876821,`

31.  `                                       "description":  "idf, computed as log(1 + (docCount - docFreq + 0.5) / (docFreq + 0.5)) from:",  ❼`

32.  `                                       "details":  [`

33.  `                                           ❽`

34.  `                                       ]`

35.  `                                   },`

36.  `                                   {`

37.  `                                       "value":  1.0,`

38.  `                                       "description":  "tfNorm, computed as (freq * (k1 + 1)) / (freq + k1 * (1 - b + b * fieldLength / avgFieldLength)) from:",  ❾`

39.  `                                       "details":  [`

41.  `                                       ]`

42.  `                                   }`

43.  `                               ]`

44.  `                           }`

45.  `                       ]`

46.  `                   }`

47.  `               ]`

48.  `           },`

49.  `           {`

50.  `               "value":  0.2876821,`

51.  `               "description":  "sum of:",`

52.  `               "details":  [`

53.  `                   {`

54.  `                       "value":  0.2876821,`

55.  `                       "description":  "weight(titele:albino in 0) [PerFieldSimilarity], result of:",`

56.  `                       "details":  [`

57.  `                           {`

58.  `                               "value":  0.2876821,`

59.  `                               "description":  "score(doc=0,freq=1.0 = termFreq=1.0\n), product of:",`

60.  `                               "details":  [`

61.  `                                   {`

62.  `                                       "value":  0.2876821,`

63.  `                                       "description":  "idf, computed as log(1 + (docCount - docFreq + 0.5) / (docFreq + 0.5)) from:",`

64.  `                                       "details":  [`

66.  `                                       ]`

67.  `                                   },`

68.  `                                   {`

69.  `                                       "value":  1.0,`

70.  `                                       "description":  "tfNorm, computed as (freq * (k1 + 1)) / (freq + k1 * (1 - b + b * fieldLength / avgFieldLength)) from:",`

71.  `                                       "details":  [`

73.  `                                       ]`

74.  `                                   }`

75.  `                               ]`

76.  `                           }`

77.  `                       ]`

78.  `                   }`

79.  `               ]`

80.  `           }`

81.  `       ]`

82.  `   }`

83.  `}`

在结果中,展示了搜索结果中第一条结果的打分过程,主要有两部分:“_source"和”_explanation",“_source"为源文档信息,”_explanation" 为具体的解析信息,在解析信息中每一部分都是由 "value","description" 和 "details" 三部分组成。"value" 为这个阶段的得分结果;"description" 这个过程的介绍信息;"details" 是详细过程。

在 "_explanation" 中 ❶为最终打分结果;从 ❷可以看出因为用的是 "best_fields",分档最后在各个字段的计算方式为 "max of:“, 但因为使用了"tie_breaker”,非最大分值也会乘以 "tie_breaker",加入总得分中;❸这部分就是详细的计算过程,“details"是一个数组,这里包含了每个字段的详细打分过程;从❹可以看出这部分是对"content"这个字段的计算过程,因为只有一个词在"content"中出现,所以这里的"details"只有一个值;❺这部分包含一些计算过程的统计信息,这部分的得分是通过"product of"计算得到; 因为对"content"加了”^5" 所以,这里会有一个 "boost";❼ 这部分是描述了 idf 的计算过程,并且公式中的参数值由❽给出(篇幅原因,❽省略);❾是 tf 计算过程,与❽类似。

4 可能碰到的问题

4.1 相同请求,主分片和副本之间排序不一样

在使用 Elasticsearch 搜索的时候很容易碰到:对于同一个搜索请求,多次请求会出现 top50 返回结果排序不一致的问题,并且翻页后,可能存在重复的问题。那么为什么会出现这样的问题?

这是由 Elastcisearch 的分布式搜索特性导致的。Elasticsearch 在做检索时,会循环的选择主分片和其副本中的一个来计算和返回搜索结果。但是主分片和副本中相关统计信息的不同,导致了同一个搜索串的评分的不一致,从而导致排序不一样。而造成这种主分片和副本统计信息不一致的具体原因,主要是因为在文档删除时造成的。ES 删除数据的时候,不会马上删除数据,只是标记了删除,并且只会在下次这个 segment 被合并的时候才会被删除(这意味着只有在下一次 segment 合并的时候才会被删除,而在执行合并的时候,并不是所有 segment 都会被合并,只有在 segmengts 满足特定条件才会被合并),而实际上,这些已经被删除的文档,也会包含在算分的统计里面。

解决方法:

  1. 每个请求有一个唯一标识值,相同请求打到同一个 shard,但是这样可能会存在一个问题,对于贝壳找房这样的网站来说,默认列表页的请求量是最大的,这样就会造成副本和主分片的负载不是均衡的。

  2. 用一个字符串标识一个用户,这样每个用户的请求都会打到同一个 shard,保证同一个用户看到的排序是不变的。

使用方式:

  1. 对于 java API,可以指定 SearchRequest 的 preference,进而指定访问的分片。

  2. 如果直接访问 es 可以通过参数 preference 指定: “get YOUINDEX/search?preference=xyzabc123”, 其中 xyzabc123 可以是用户 id 等字符串。

preference 可以指定的值有:

  1. _primary。搜索只在主分片执行搜索请求,副本不参与搜索;性能会打折扣,不能起到通过扩展节点增加 qps。

  2. primaryfirst。优先在主分片执行,如果主分片挂掉,会在副本执行请求。

  3. _local。搜索请求优先于在本地执行。

  4. onlynode:xyz。只在 xyz 节点执行搜索。

  5. prefernode:xyz。搜索请求优先在节点 xyz 执行。

  6. shards:2,3。搜索只在分片 2、3 执行,可以与 primary 参数一起使用如:shards:2,3;primary。

  7. xyz。指定一个随机字符串,可以保证同样的请求,被分配到同样的副本上面,从而保证同一请求结果的稳定性。

除了统计信息可能导致的排序不一致之外,相关性一致的文档,排序可能也会不一样。这是因为对于相关性一样的文档排序,ES 是会根据内部的 id 进行排序的。但是如果有副本的话,就可能会导致翻页后文档重复的问题,这是因为两个得分相同的文档,在不同副本 id 是不同的。因此,在检索的时候指定 prefrence 是很有必要的。

4.2 相同文本内容,不同 shard 相关性得分不一样

相同文本内容,不同 shard 相关性得分不一样,或者明明更相关的文本却没有排在更前面。这是因为在检索的时候,每个 shard 各自负责自己的打分,也就是说,打分的时候统计信息是局部的,是每个 shard 自己的统计信息,而索引的统计数值对打分影响结果至关重要,通常每个 shard 各自的统计数值都是不一样的。只有在每个 shard 的统计数值都一样的情况下,不同 shard 的对相同内容打分才会一致。特别是在 route 的时候以索引时间作为 routing,查询多个索引或者数据量小的时候特别明显。

ES 默认使用 query_then_fetch 的方式进行检索,第一步,先向所有的 shard 发出请求,各分片只返回排序和排名相关的信息(注意,不包括文档 document),然后按照各分片返回的分数进行重新排序和排名,取前 size 个文档。然后进行第二步,去相关的 shard 取 document。这种方式返回的 document 与用户要求的 size 是相等的。

解决方法:

  1. 如果数据量小的话,只用一个索引,并且这个索引只有一个 shard。

  2. 利用 route。如果你的数据集可以精确的按照某个字段划分,并且检索的时候,只检索某个类,比如搜索贝壳找房,在特定城市情况下,都是按照城市来检索,那么就可以利用城市作为 route,这样每个城市的数据就会都在一个 shard 上,也就是这个城市的所有房源用相同的统计数据。

  3. 利用 dfsquerythenfetch 的检索方式。这个检索分三个阶段,比 querythenfetch 多一个阶段,会先把各个 shard 和这个 query 相关的统计数据收集起来;之后根据收集的信息按照 querythen_fetch 进行检索。

使用方式:

  1. 直接访问 ES 可以通过参数 searchtype: GET YOUINDEX/search?searchtype=dfsquerythen_fetch

  2. JAVA API 通过指定 SearchRequest 的 searchType 为 DFSQUERYTHEN_FETCH。

5. 小结

ES 是一个基于 Lucene 功能强大的搜索引擎包,包含了众多开箱即用的优秀功能。本文从 ES 相关性计算出发,结合贝壳找房在相关性调优中的一些实践,简单介绍了 ES 相关性计算过程,几种相关性调优方式以及调优过程中可能发现的问题。要用好 ES 相关性调优还得结合实际场景,从需求出发,多次尝试,优化参数,才能得到一个比较好的相关性。

本文作者

徐鹏程,2018 年 1 月毕业于北京科技大学计算机与通信工程学院,研究方向为自然语言处理。2017 年 5 月加入贝壳,目前主要负责贝壳搜索召回排序以及特征工程相关工作。


更多高质资源 尽在AIQ 机器学习大数据 知乎专栏 点击关注

转载请注明 AIQ - 最专业的机器学习大数据社区  http://www.6aiq.com