TF-IDF和BM25

2019-04-18 本文已影响0人 KhaosYang

搜索引擎总是会把相关性高的内容显示在前面，相关性低的内容显示在后面。那么，搜索引擎是如何计算关键字和内容的相关性呢？这里介绍2种重要的权重度量方法：TF-IDF和BM25。

TF-IDF

词频 TF(Term Frequency)

TF越大，相关性越高

 TF Score = 某个词在文档中出现的次数 ／ 文档的长度

举例：某文档D，长度为200，其中“Lucene”出现了2次，“的”出现了20次，“原理”出现了3次，那么:

TF(Lucene|D) = 2/200 = 0.01
TF(的|D) = 20/200 = 0.1
TF(原理|D) = 3/200 = 0.015

“Lucene的原理”这个短语与文档D的相关性就是三个词的相关性之和。

“的”词为停词，权重不考虑。
“原理”是个很通用的词，而“Lucene”是个专业词。
“Lucene”这个词对我们的搜索比“原理”更重要。
抽象一下，可以理解为一个词预测主题的能力越强，就越重要，权重也应该越大。反之，权重越小。

TF(Lucene的原理|D) = 0.01 + 0.015 = 0.025

逆文本频率指数 IDF(Inverse Dcument Frequency)

IDF = log(N/n)

N表示全部文档数。假如世界上文档总数位100亿，"Lucene"在1万个文档中出现过，“原理”在2亿个文档中出现过，那么它们的IDF值分别为：

IDF(Lucene) = log(100亿/1万) = 19.93
IDF(原理) ＝ log(100亿/2亿) ＝ 5.64

“Lucene”重要性相当于“原理”的3.5倍。停用词“的”在所有的文档里出现过，它的IDF=log(1)=0。短语与文档的最终相关性就是TF和IDF的加权求和：

simlarity = TF1*IDF1 + TF2*IDF2 + ... + TFn*IDFn

现在可以计算出上文中提到的“Lucene的原理”与文档D的相关性:

simlarity(Lucence的原理|D) = 0.01*19.93 + 0 + 5.64*0.015 ＝ 0.2839

其中，“Lucene”占了70%的权重，“原理”仅占30%的权重。

BM25

BM25是基于TF-IDF并做了改进的算法
源于概率相关模型，而非向量空间模型
搜索相关性评分

BM25中的TF

传统的TF值理论上是可以无限大的。而BM25与之不同，它在TF计算方法中增加了一个常量k，用来限制TF值的增长极限。下面是两者的公式：

传统 TF Score = sqrt(tf)
BM25的 TF Score = ((k + 1) * tf) / (k + tf)

下面是两种计算方法中，词频对TF Score影响的走势图。从图中可以看到，当tf增加时，TF Score跟着增加，但是BM25的TF Score会被限制在0~k+1之间。它可以无限逼近k+1，但永远无法触达它。这在业务上可以理解为某一个因素的影响强度不能是无限的，而是有个最大值，这也符合我们对文本相关性逻辑的理解。在Lucence的默认设置里，k＝1.2，使用者可以修改它。

TF Score & BM25 TF Score

BM25如何对待文档长度

BM25还引入了平均文档长度的概念，单个文档长度对相关性的影响力与它和平均长度的比值有关系。BM25的TF公式里，除了k外，引入另外两个参数：L和b。L是文档长度与平均长度的比值。如果文档长度是平均长度的2倍，则L＝2。b是一个常数，它的作用是规定L对评分的影响有多大。加了L和b的公式变为：

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

下面是不同L的条件下，词频对TFScore影响的走势图：

L 对 TF Score的影响

从图上可以看到，文档越短，它逼近上限的速度越快，反之则越慢。这是可以理解的，对于只有几个词的内容，比如文章“标题”，只需要匹配很少的几个词，就可以确定相关性。而对于大篇幅的内容，比如一本书的内容，需要匹配很多词才能知道它的重点是讲什么。
上文说到，参数b的作用是设定L对评分的影响有多大。如果把b设置为0，则L完全失去对评分的影响力。b的值越大，L对总评分的影响力越大。此时，相似度最终的完整公式为：

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

传统TF-IDF vs. BM25

传统的TF-IDF是自然语言搜索的一个基础理论，它符合信息论中的熵的计算原理，虽然作者在刚提出它时并不知道与信息熵有什么关系，但你观察IDF公式会发现，它与熵的公式是类似的。实际上IDF就是一个特定条件下关键词概率分布的交叉熵。
BM25在传统TF-IDF的基础上增加了几个可调节的参数，使得它在应用上更佳灵活和强大，具有较高的实用性。