Lucene相关性算法TF-IDF、BM25算法先容

       判定网页内容是否与用户査询相关,这依赖于搜索引擎所来用的检索模子。检索模子是搜索引擎的理论基本,为量化相关性提供了一种数学模子,是对查询词和文档之间举办相似度计较的框架和要领。其本质就是相关度建模。如图所示,检索模子地址搜索引擎系统架构位置:

搜索功效排序时搜索引擎最焦点的部门,很洪流平度上抉择了搜索引擎的质量优劣及用户满足度。实际搜索功效排序的因子有许多,但最主要的两个因素是用户查询和网页内容的相关度,以及网页链接环境。这里我们主要总结网页内容和用户查询相关的内容。

       判定网页内容是否与用户査询相关,这依赖于搜索引擎所来用的检索模子。检索模子是搜索引擎的理论基本,为量化相关性提供了一种数学模子,是对查询词和文档之间举办相似度计较的框架和要领。其本质就是相关度建模。如图所示,检索模子地址搜索引擎系统架构位置:

    

    虽然检索模子理论研究存在抱负化的隐含假设,及即假设用户需求已经通过查询很是清晰明晰地表达出来了,所以检索模子的任务不涉及到对用户需求建模。但实际上这个和实际相差较远,纵然沟通的查询词,差异用户的需求目标大概差别很大,而检索模子对此无能为力。

推荐参考文章:

英文版: https://opensourceconnections.com/blog/2015/10/16/bm25-the-next-generation-of-lucene-relevation/

中文版: BM25下一代Lucene相关性算法

一、 TF*IDF

TF*IDF :检索词和文档相关性的评分计较公式:  tf * idf

IDF * TF = log(numDocs / docFreq) * tf

  • 第一步,计较词频 tf:  即检索词,如'dog'在文档中呈现的频次。
  • 第二步,计较逆文档频率 idf: 即检索词呈此刻几多文档中。假如在险些所有文档中都呈现,那就是一个非经常见的词,说明寄义并不非凡,那么它在计较单词和文档相关性时的权重就不该该很高。 idf = log(numDocs/ docFreq)
  • 第三步,思量文档的长度field length 。检索词'dog'在一个有500个单词的文档中呈现两次,文档是有关dog的大概性较量低;假如'dog'在一个很短的文档中呈现两次,那它跟dog有关的大概性就较大。所以,这里引入一个观念,fieldNorms。在匹配段文档和长文档时,fieldNorms孝敬了一个倾向随笔档的偏置。

二、 Fudging TF*IDF

信息检索尝试中发明原始的TF-IDF 值并不能很好的拟合相关性。单词与文档中的相关性并不是跟着呈现频次的增加而线性增长的。一篇文章中提到6次dog,就意味着它比另一篇提到dog3次的文档的相关性高两倍吗?

所以,对TF*IDF举办了修改,修改后的计较公式为:

IDF score * TF score * fieldNorms = log(numDocs / docFreq +1) * sqrt(tf) * (1/sqrt(length))

较量公式可以发明,这里对三个数值TF, IDF, field length的利用都举办了修改,不再是直接。

那么这么修改的寄义是什么呢?对付相关性计较都有什么改变和晋升呢?

  1、从原始TF到TF Score,  TF Score = sqrt(TF)

词term在文档中呈现的频次与文档的相关性不再是线性干系,而是趋于越发滑腻的干系。查询单词在一个文档中呈现了 16次,在另一个文档中呈现了4次,前面文档的相关性比后头的高2倍,而不是4倍.

Raw TF/原始词频

TF Score

1

1.0

2

1.141

4

2.0

8

2.828

16

4.0

    2、从原始DF到IDF score,  IDF score = log(numDocs / docFreq +1)

    numDocs 暗示语料库中的所有文档数。假设 numDocs=1000,对应的原始DF到IDF Score的调动如下。 log函数比反函数更滑腻一些。一个单词呈此刻4个文档中比呈此刻64个文档中的非凡性差不多高两倍(6.298/3.733)

Raw DF

IDF Score

1

7.214

2

6.809

4

6.298

64

3.733

128

3.048

256

2.359

     3、从文档长度length到Field Norm  score,  Field Norm score = 1 / sqrt(length)

一个长度128 的文档的相关性差不多是一个长度为1 的文档的十分之一。这也和我们的直觉更相切合,匹配到的只有一个单词的文档就是关于这个搜索主题的,而长度128的文档,搜索单词只是个中一个单词,其主题是否相关就不那么确定了。 

Raw Length

Field Norm Score

1

1.0

2

0.707

4

0.5

64

0.125

128

0.088

256

0.0625

三、 BM25: 下一代 TF*IDF

BM25 是在 TF*IDF基本上成长起来的,是 “Best Match 25” 的缩写,颁发于1994年, 是调解相关性计较的第 25次迭代。 基本理论来自概率信息检索。

BM25相关性计较公式:

IDF * ((k + 1) * tf) / (k * (1.0 - b + b * (|d|/avgDl)) + tf)

这个中对TF、IDF、length 的利用 做了许多窜改,我们依次说明下:

1、从经典TF-score 到BM25中的TF-score

BM25中的term频率比传统的TF*IDF更能抑制term频率的影响,频率的影响老是在增加,但徐徐地靠近一个值。

我们先不思量计较公式中的 文档长度 length部门,即把 (1.0 - b + b * (|d|/avgDl)) 看成1, 那么词频在相关性公式中的影响可以简化看作: 个中k是需要进修的一个参数

((k + 1) * tf) / (k + tf)

较量 经典TF-score = sqrt(tf) 和 BM25中的TF-score,获得下图的比拟:(这里k=1.2)

图中可以看出来,BM25中的TF-score曲线渐近靠近(k+1)。什么意思呢?

寄义是更多的tf意味着更多的相关性,可是你很快就到达了收益递减。你永远不会高出k,但你老是靠近它!

而经典的Lucene tf不绝增加,但从未到达饱和点。

这个k值是几多?对付BM25,k凡是配置为1.2。大大都人不去管k。改变k是一种有用的调解要领来修改TF的影响。修改k会导致渐近线移动。然而更重要的是,较高的k会导致TF需要更长的时间才气到达饱和。通过扩展饱和点,可以扩展高频和低频率文档之间的相关性差别!

2、从经典 IDF-score 到BM25中的 IDF-score

 IDF score = log(numDocs / (docFreq + 1))

从图上看BM25’s IDF 与经典 Lucene IDF很相似,并没有什么大的区别。?????并没有讲清楚相似在那边

2、从经典 文档length-score 到BM25中的 length-score

相似性分数还受文档是否高于或低于语料库中文档平均长度的影响。

((k + 1) * tf) / (k * (1.0 - b + b * L) + tf)

计较公式中引入了两个变量,常数b,长度L,用 (1.0 - b + b * L) 与 k 相乘,作为分母中的一个加项。 

L 是文档长度length=|d|对比于平均文档长度avgDl的比值 ,L= |d|/avgDl。

假如文档长度是语料库中平均文档长度的两倍, L =2 ;假如文档长度是平均文档长度的十分之一,L = 0.1 

如图中所示,差异L值的最终功效是,较短的文档达到渐近线的速度更快。他们险些顿时饱和到最好的TF分数。这是有原理的,随笔档的term较少。在这些简短的文档中匹配的越多,就越确信其相关性。所以这个数字上升得更快。另一方面,一本长篇的书需要更多的匹配才气到达我们自信的水平。所以到达“最大相关性”需要更长的时间。

常数b将答允我们微调L值对得分的影响。留意,在上面的公式中,b为0时,完全消除了L的影响,等价于经典的TF公式。b越高,文档长度对评分的影响越大。

BM25的合用范畴:

对焦点文档搜索问题是庞大的改造。但在数字、图像和其他被搜索实体的边沿,利用并不清朗。

跟着BM25成为默认值,我们将直接看到当理论与实践相结适时会产生什么。相关性从来不是一个牢靠稳定的,它是你经心打造的用户体验。现实世界大概会大不沟通。文档不只仅是文档,还包罗餐厅、产物、新闻文章、推特、大夫办公室和其他很多对象。也许你的“相似性”的正确谜底是常常提起伴侣在微博上的微博,在四周有着相似的乐趣。淘汰文内情似度,更多存眷用户需要找到的重要内容。换言之,搜索和其他任何对象一样,都是在打造用户体验。


本文链接地址:https://www.0471seo.com/baimaoSEO/4943.html


官方运营-Sean丶♥

688 SEO文章 文章

评论