BM25 文本相似度算法

刺骨的言语ヽ痛彻心扉 2021-12-12 11:57 363阅读 0赞

#### 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次的词会比那些只出现一两次的对相关度有显著影响），参见词频饱和度图：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIwOTg5MTA1_size_16_color_FFFFFF_t_70]

BM25算法的一般性公式如下：  
![在这里插入图片描述][20190711130313693.png]

*  Q表示Query
 *  qi表示Q解析之后的一个语素（对中文而言，我们可以把对Query的分词作为语素分析，每个词看成语素qi。）
 *  d表示一个搜索结果文档；
 *  Wi表示语素qi的权重；
 *  R(qi，d)表示语素qi与文档d的相关性得分。

##### Wi #####

下面我们来看如何定义Wi。判断一个词与一个文档的相关性的权重，方法有多种，较常用的是`IDF`。这里以IDF为例，公式如下：  
![在这里插入图片描述][20190711130427130.png]

*  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中相关性得分的一般形式：  
![在这里插入图片描述][20190711131318177.png]

*  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，因此公式可以简化为：  
![在这里插入图片描述][20190711131547605.png]  
从K的定义中可以看到，参数b的作用是调整文档长度对相关性影响的大小。`b越大，K值越小，文档长度的对相关性得分的影响越大，反之越小。而文档的相对长度越长，K值将越大，则相关性得分会越小`。这可以理解为，当文档较长时，包含qi的机会越大，因此，同等fi的情况下，长文档与qi的相关性应该比短文档与qi的相关性弱。

综上，BM25算法的相关性得分公式可总结为：  
![在这里插入图片描述][20190711132822704.png]  
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;
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIwOTg5MTA1_size_16_color_FFFFFF_t_70]: /images/20211211/4954915792164549a9df1c2e3d37c87e.png
[20190711130313693.png]: /images/20211211/7e31a832033d43ccb4220eeead5242fa.png
[20190711130427130.png]: /images/20211211/788b2d2399a842a8bbe340818b9c2c5d.png
[20190711131318177.png]: /images/20211211/73dad439e256418c97aca592823f1999.png
[20190711131547605.png]: /images/20211211/741517658c7d4bc784e4d6ca179c5360.png
[20190711132822704.png]: /images/20211211/30296612ed2c4aabb6d4569f1e8f441e.png