信息检索（1）- BM25

BM25（Best Matching 25）是一种广泛应用于信息检索和文本挖掘的算法，它改进了传统的TF-IDF（Term Frequency-Inverse Document Frequency）方法，考虑了文档长度等因素，使得搜索结果更加准确。

TF-IDF

TF-IDF（Term Frequency-Inverse Document Frequency）是一种用于信息检索和文本挖掘的常用加权技术。它通过评估一个词在文档中的重要性来帮助识别文档的关键内容。TF-IDF 的主要思想是：如果某个词在文档中出现的频率高，并且在其他文档中出现的频率低，则该词对于该文档具有很高的区分能力。

基本概念

1. 词频 (TF)：

   • 定义：词频是指某个词在文档中出现的次数。
   • 公式： $$\text{TF}(t, d) = \frac{\text{词 } t \text{ 在文档 } d \text{ 中出现的次数}}{\text{文档 } d \text{ 中所有词的总数}}$$

2. 逆文档频率 (IDF)：

   • 定义：逆文档频率反映了词的普遍重要性。如果一个词在很多文档中都出现，则它的 IDF 值较低；如果一个词只在少数文档中出现，则它的 IDF 值较高。
   • 公式： $$\text{IDF}(t, D) = \log \left( \frac{\text{文档总数}}{\text{包含词 } t \text{ 的文档数} + 1} \right)$$ 其中，加 1 是为了避免分母为 0 的情况。

3. TF-IDF：

   • 定义：TF-IDF 是词频和逆文档频率的乘积，用于评估一个词在文档中的重要性。
   • 公式： $$\text{TF-IDF}(t, d, D) = \text{TF}(t, d) \times \text{IDF}(t, D)$$

BM25

基本思想

1. TF-IDF 的改进：
   • 饱和函数：BM25 引入了一个饱和函数来调整词项的出现次数（TF），防止某个词项在文档中出现次数过多导致权重过大。
   • 文档长度因子：BM25 考虑了文档的长度，引入了文档长度因子，使得文档长度对权重的影响不是线性的，这样可以更好地适应不同长度的文档。

计算公式

BM25 的具体计算公式如下：

$$\text{BM25}(D, Q) = \sum_{i=1}^{n} \text{IDF}(q_i) \cdot \frac{f(q_i, D) \cdot (k_1 + 1)}{f(q_i, D) + k_1 \cdot (1 - b + b \cdot \frac{\text{len}(D)}{\text{avg\_len}})}$$

其中：

• $ n $ 是查询中的词项数。
• $ q_i $ 是查询中的第 $ i $ 个词项。
• $ \text{IDF}(q_i) $ 是逆文档频率，计算方式通常是 $ \log \frac{N - n(q_i) + 0.5}{n(q_i) + 0.5} $，其中 $ N $ 是文档总数，$ n(q_i) $ 是包含词项 $ q_i $ 的文档数。
• $ f(q_i, D) $ 是词项 $ q_i $ 在文档 $ D $ 中的出现次数（TF）。
• $ \text{len}(D) $ 是文档 $ D $ 的长度。
• $ \text{avg_len} $ 是所有文档的平均长度。
• $ k_1 $ 和 $ b $ 是调整参数，通常设置为 $ k_1 = 1.5 $ 和 $ b = 0.75 $。

Python 实现

以下是一个简单的 Python 实现 BM25 算法的例子：

import math
from collections import Counter

class BM25:
    def __init__(self, corpus, k1=1.5, b=0.75):
        self.k1 = k1
        self.b = b
        self.corpus = corpus
        self.doc_lengths = [len(doc) for doc in corpus]
        self.avg_doc_length = sum(self.doc_lengths) / len(self.doc_lengths)
        self.doc_count = len(corpus)
        self.doc_term_freqs = [Counter(doc) for doc in corpus]
        self.inverted_index = self.build_inverted_index()
    
    def build_inverted_index(self):
        inverted_index = {}
        for doc_id, doc_term_freq in enumerate(self.doc_term_freqs):
            for term, freq in doc_term_freq.items():
                if term not in inverted_index:
                    inverted_index[term] = []
                inverted_index[term].append((doc_id, freq))
        return inverted_index
    
    def idf(self, term):
        doc_freq = len(self.inverted_index.get(term, []))
        if doc_freq == 0:
            return 0
        return math.log((self.doc_count - doc_freq + 0.5) / (doc_freq + 0.5) + 1.0)
    
    def bm25_score(self, query_terms, doc_id):
        score = 0
        doc_length = self.doc_lengths[doc_id]
        for term in query_terms:
            tf = self.doc_term_freqs[doc_id].get(term, 0)
            idf = self.idf(term)
            numerator = tf * (self.k1 + 1)
            denominator = tf + self.k1 * (1 - self.b + self.b * (doc_length / self.avg_doc_length))
            score += idf * (numerator / denominator)
        return score
    
    def rank_documents(self, query):
        query_terms = query.split()
        scores = [(doc_id, self.bm25_score(query_terms, doc_id)) for doc_id in range(self.doc_count)]
        sorted_scores = sorted(scores, key=lambda x: x[1], reverse=True)
        return sorted_scores

# Example usage
corpus = [
    "The quick brown fox jumps over the lazy dog",
    "A quick brown dog outpaces a swift fox",
    "The dog is lazy but the fox is swift",
    "Lazy dogs and swift foxes"
]

bm25 = BM25(corpus)
query = "quick brown dog"
result = bm25.rank_documents(query)
print(f"BM25 Scores for the query '{query}':")
for doc_id, score in result:
    print(f"Document {doc_id}: {score}")

解释

1. 初始化：

   • corpus 是文档集合。
   • k1 和 b 是调整参数。
   • doc_lengths 存储每个文档的长度。
   • avg_doc_length 是所有文档的平均长度。
   • doc_term_freqs 存储每个文档中每个词项的出现次数。
   • inverted_index 是倒排索引，用于快速查找词项在哪些文档中出现。

2. 构建倒排索引：

   • build_inverted_index 方法构建倒排索引，记录每个词项出现在哪些文档中及其频率。

3. 计算逆文档频率：

   • idf 方法计算词项的逆文档频率。

4. 计算 BM25 得分：

   • bm25_score 方法计算查询中每个词项在指定文档中的 BM25 得分。

5. 排序文档：

   • rank_documents 方法计算查询与每个文档的 BM25 得分，并按得分从高到低排序。

测试用例

• 查询："quick brown dog"
• 结果：输出每个文档的 BM25 得分，并按得分从高到低排序。