BM25-文本相似度算法
BM25 文本相似度算法
BM25, 下一代的TF-IDF
新版的lucence不再把TF-IDF作为默认的相关性算法，而是采用了BM25(BM是Best Matching的意思)。BM25是基于TF-IDF并做了改进的算法。
BM25算法，通常用来作搜索相关性评分。
一句话概况其主要思想：对Query进行语素解析，生成语素qi；然后，对于每个搜索结果D，计算每个语素qi与D的相关性得分，最后，将qi相对于D的相关性得分进行加权求和，从而得到Query与D的相关性得分。
传统TF-IDF vs. BM25
传统的TF-IDF是自然语言搜索的一个基础理论，它符合信息论中的熵的计算原理，虽然作者在刚提出它时并不知道与信息熵有什么关系，但你观察IDF公式会发现，它与熵的公式是类似的。实际上IDF就是一个特定条件下关键词概率分布的交叉熵。
BM25在传统TF-IDF的基础上增加了几个可调节的参数，使得它在应用上更佳灵活和强大，具有较高的实用性。
BM25同样使用词频，逆文档频率以及字段长度归一化，但是每个因子的定义都有细微差别
TF-IDF没有考虑词频上限的问题，因为高频停用词已经被移除了）
BM25 有一个上限，文档里出现5-10次的词会比那些只出现一两次的对相关度有显著影响），参见词频饱和度图：
BM25算法的一般性公式如下：
- Q表示Query
- qi表示Q解析之后的一个语素（对中文而言，我们可以把对Query的分词作为语素分析，每个词看成语素qi。）
- d表示一个搜索结果文档；
- Wi表示语素qi的权重；
- R(qi，d)表示语素qi与文档d的相关性得分。
Wi
下面我们来看如何定义Wi。判断一个词与一个文档的相关性的权重，方法有多种，较常用的是
IDF
。这里以IDF为例，公式如下：
N为索引中的全部文档数(可以理解为一篇文章的所有句子数)
n(qi)为包含了qi的文档数(可以理解为word出现在了几个句子中的句子数量)
hanlp中代码实现：
Map<String, Double> idf = new TreeMap<String, Double>();
idf.put(word, Math.log(D - freq + 0.5) - Math.log(freq + 0.5));根据IDF的定义可以看出，对于给定的文档集合，
包含了qi的文档数越多，qi的权重则越低
。也就是说，当很多文档都包含了qi时，qi的区分度就不高，因此使用qi来判断相关性时的重要度就较低。
R（qi，d）
语素qi与文档d的相关性得分R（qi，d）。首先来看BM25中相关性得分的一般形式：
- k1，k2，b为调节因子，通常根据经验设置，一般k1=2，b=0.75；
- fi为qi在d中的出现频率；（可以理解为每个word在文章中的词频）
- qfi为qi在Query中的出现频率;（可以理解为每个word在那句话中的词频）
- dl为文档d的长度;
- avgdl为所有文档的平均长度。
不像 TF/IDF ，BM25 有一个比较好的特性就是它提供了两个可调参数：
k1
这个参数控制着词频结果在词频饱和度中的上升速度。默认值为 1.2 。值越小饱和度变化越快，值越大饱和度变化越慢。
b
这个参数控制着字段长归一值所起的作用， 0.0 会禁用归一化， 1.0 会启用完全归一化。默认值为 0.75 。
由于绝大部分情况下，qi在Query中只会出现一次，即qfi=1，因此公式可以简化为：
从K的定义中可以看到，参数b的作用是调整文档长度对相关性影响的大小。
b越大，K值越小，文档长度的对相关性得分的影响越大，反之越小。而文档的相对长度越长，K值将越大，则相关性得分会越小
。这可以理解为，当文档较长时，包含qi的机会越大，因此，同等fi的情况下，长文档与qi的相关性应该比短文档与qi的相关性弱。
综上，BM25算法的相关性得分公式可总结为：
hanlp中的计算代码：
score = (idf.get(word) * tf * (k1 + 1) / (tf + k1 * (1 - b + b * d / avgdl)))附录HanLP的BM25 算法的java实现代码 ：
public class BM25
{
/**
* 文档句子的个数
*/
int D;
/**
* 文档句子的平均长度
*/
double avgdl;
/**
* 拆分为[句子[单词]]形式的文档
*/
List<List<String>> docs;
/**
* 文档中每个句子中的每个词与词频
*/
Map<String, Integer>[] f;
/**
* 文档中全部词语与出现在几个句子中
*/
Map<String, Integer> df;
/**
* IDF
*/
Map<String, Double> idf;
/**
* 调节因子
*/
final static float k1 = 1.5f;
/**
* 调节因子
*/
final static float b = 0.75f;
public BM25(List<List<String>> docs)
{
this.docs = docs;
D = docs.size();
for (List<String> sentence : docs)
{
avgdl += sentence.size();
}
avgdl /= D;
f = new Map[D];
df = new TreeMap<String, Integer>();
idf = new TreeMap<String, Double>();
init();
}
/**
* 在构造时初始化自己的所有参数
*/
private void init()
{
int index = 0;
for (List<String> sentence : docs)
{
Map<String, Integer> tf = new TreeMap<String, Integer>();
for (String word : sentence)
{
Integer freq = tf.get(word);
freq = (freq == null ? 0 : freq) + 1;
tf.put(word, freq);
}
f[index] = tf;
for (Map.Entry<String, Integer> entry : tf.entrySet())
{
String word = entry.getKey();
Integer freq = df.get(word);
freq = (freq == null ? 0 : freq) + 1;
df.put(word, freq);
}
++index;
}
for (Map.Entry<String, Integer> entry : df.entrySet())
{
String word = entry.getKey();
Integer freq = entry.getValue();
idf.put(word, Math.log(D - freq + 0.5) - Math.log(freq + 0.5));
}
}
/**
* 计算一个句子与一个文档的BM25相似度
*
* @param sentence 句子（查询语句）
* @param index 文档（用语料库中的下标表示）
* @return BM25 score
*/
public double sim(List<String> sentence, int index)
{
double score = 0;
for (String word : sentence)
{
if (!f[index].containsKey(word)) continue;
int d = docs.get(index).size();
Integer tf = f[index].get(word);
score += (idf.get(word) * tf * (k1 + 1)
/ (tf + k1 * (1 - b + b * d
/ avgdl)));
}
return score;
}
public double[] simAll(List<String> sentence)
{
double[] scores = new double[D];
for (int i = 0; i < D; ++i)
{
scores[i] = sim(sentence, i);
}
return scores;
}
}