当前位置：首页 > article >正文

【Lucene】搜索引擎和文档相关性评分 BM25 算法的工作原理

article 2024/11/22 11:41:17

BM25 算法的工作原理：

什么是 BM25 算法？

BM25 是一种流行的文本检索算法，广泛用于搜索引擎和文档相关性评分。它基于概率检索模型，旨在评估查询和文档之间的相关性。

核心公式

BM25 的公式如下：

$\text{score}(D, Q) = \sum_{t \in Q} IDF(t) \cdot \frac{f(t, D) \cdot (k_1 + 1)}{f(t, D) + k_1 \cdot (1 - b + b \cdot \frac{|D|}{\text{avgdl}})}$

$I D F (t)$ ：词项 ( t ) 的逆文档频率。
$f (t, D)$ ：词项 ( t ) 在文档 ( D ) 中的频率。
$∣ D ∣$ ：文档 ( D ) 的长度。
$\text{avgdl}$ ：所有文档的平均长度。
$k_1$ ：控制词项饱和度的参数，通常取 ( 1.2 )。
$b$ ：长度归一化参数，通常取 ( 0.75 )。

IDF 的计算

$\log \frac{N - n_t + 0.5}{n_t + 0.5} + 1$

( N )：文档总数。
( n_t )：包含词 ( t ) 的文档数量。

代码实现

以下是 BM25 的简单 Python 实现：

import math

class BM25:
    def __init__(self, documents, k1=1.2, b=0.75):
        self.documents = documents
        self.k1 = k1
        self.b = b
        self.doc_lengths = [len(doc) for doc in documents]
        self.avgdl = sum(self.doc_lengths) / len(self.doc_lengths)
        self.inverted_index = self._build_inverted_index()

    def _build_inverted_index(self):
        index = {}
        for i, doc in enumerate(self.documents):
            for word in set(doc):
                index.setdefault(word, []).append(i)
        return index

    def idf(self, term):
        n_t = len(self.inverted_index.get(term, []))
        return math.log((len(self.documents) - n_t + 0.5) / (n_t + 0.5) + 1)

    def score(self, query, doc_index):
        doc = self.documents[doc_index]
        score = 0
        for term in query:
            if term in doc:
                f = doc.count(term)
                idf = self.idf(term)
                score += idf * ((f * (self.k1 + 1)) / (f + self.k1 * (1 - self.b + self.b * len(doc) / self.avgdl)))
        return score

# 示例文档
documents = [
    ["hello", "world", "search", "engine"],
    ["hello", "search", "bm25", "algorithm"],
]
bm25 = BM25(documents)

# 查询得分
query = ["hello", "bm25"]
print(bm25.score(query, 0))  # 文档 0 的相关性得分
print(bm25.score(query, 1))  # 文档 1 的相关性得分

图示

词频与文档长度归一化
- 用柱状图表示不同文档中词频和长度的对比，展示 BM25 如何平衡短文档和长文档。
IDF 权重
- 用折线图展示常见词和稀有词的 IDF 值，突出稀有词对相关性的重要贡献。

为细化 BM25 相关图表，以下是具体建议和生成方式：

图表 1: 词频与文档长度归一化

目标：展示 BM25 如何平衡短文档和长文档的评分。

图类型：条形图。
数据结构：每个文档的总词频与长度。
关键点：对比文档长度对评分的影响。

示例生成代码（使用 Matplotlib）：

import matplotlib.pyplot as plt

# 示例文档数据
doc_lengths = [4, 4, 6, 10]  # 文档长度
term_frequencies = [2, 3, 4, 5]  # 查询词的频率

# 绘图
plt.bar(range(len(doc_lengths)), doc_lengths, label="Document Lengths", alpha=0.6)
plt.bar(range(len(term_frequencies)), term_frequencies, label="Term Frequencies", alpha=0.6)
plt.xlabel("Documents")
plt.ylabel("Values")
plt.legend()
plt.title("Term Frequency vs Document Length")
plt.show()

图表 2: 逆文档频率 (IDF) 权重

目标：展示 IDF 在常见词与稀有词上的差异。

图类型：折线图。
数据结构：不同词项的文档频率与其对应的 IDF。
关键点：稀有词拥有更高权重，帮助区分相关性。

示例生成代码：

import numpy as np

# 示例词项数据
doc_count = 100  # 总文档数
term_doc_freq = np.array([1, 5, 20, 50, 90])  # 包含查询词的文档数
idf_values = np.log((doc_count - term_doc_freq + 0.5) / (term_doc_freq + 0.5) + 1)

# 绘图
plt.plot(term_doc_freq, idf_values, marker='o')
plt.xlabel("Term Document Frequency")
plt.ylabel("IDF Value")
plt.title("IDF Curve")
plt.grid()
plt.show()

图表 3: BM25 综合评分变化

目标：展示 BM25 参数 (k_1) 和 (b) 的调整对评分的影响。

图类型：3D 表面图或热图。
数据结构：BM25 分数在不同 (k_1) 和 (b) 参数组合下的变化。
关键点：参数对相关性评分的微调作用。

在这里插入图片描述

示例生成代码：

from mpl_toolkits.mplot3d import Axes3D
import matplotlib.pyplot as plt
import numpy as np

# 参数网格
k1 = np.linspace(0.5, 2.0, 50)
b = np.linspace(0.0, 1.0, 50)
k1, b = np.meshgrid(k1, b)
scores = (k1 + 1) / (k1 * (1 - b + b * 0.5) + 1)

# 绘制 3D 图
fig = plt.figure()
ax = fig.add_subplot(111, projection='3d')
ax.plot_surface(k1, b, scores, cmap='viridis')
ax.set_xlabel("k1")
ax.set_ylabel("b")
ax.set_zlabel("Score")
ax.set_title("BM25 Scoring Surface")
plt.show()