BM25算法 实现原理

BM25算法是一种用于评估搜索词和文档之间相关性的算法，它是一种基于概率检索模型提出算法。其实现原理如下：

1. 对查询进行分词，得到单词 $q_i$。

2. 对于每个文档 $D$，计算BM25分数，该分数由3部分组成：

a. query中每个单词和文档D之的相关性

b. 单词和query之间的相关性

c. 每个单词的权重

3. 计算每个单词的权重，使用公式 $w_i = \frac{(k_1 + 1) * f_i}{k_1 * ((1 - b) + b * \frac{L_D}{L_{ave}}) + f_i}$，其中 $f_i$ 是单词在文档中出现的频率，$L_D$ 是文档的长度，$L_{ave}$ 是所有文档的平均长度，$k_1$ 和 $b$ 是调节参数。

4. 计算每个单词和查询之间的相关性，使用公式 $IDF_i = \log{\frac{N - n_i + 0.5}{n_i + 0.5}}$，其中 $N$ 是文档总数，$n_i$ 是包含单词 $i$ 的文档数。

5. 计算每个单词和文档之间的相关性，使用公式 $score(D, Q) = \sum_{i=1}^{n} IDF_i * \frac{(k_1 + 1) * f_i}{k_1 * ((1 - b) + b * \frac{L_D}{L_{ave}}) + f_i}$，其中 $n$ 是查询中单词的数量。

6. 对于每个文档，按照相关性分数进行排序，返回排名前 $k$ 的文档。

# 以下是一个使用Python实现BM25算法的示例
import numpy as np

class BM25_Model(object):
    def __init__(self, k1=1.5, b=0.75):
        self.k1 = k1
        self.b = b

    def fit(self, docs):
        self.N = len(docs)
        self.avgdl = sum([len(doc) for doc in docs]) / self.N
        self.docs = docs
        self.f = []
        self.df = {}
        self.idf = {}
        self.doc_len = []
        for doc in docs:
            tmp = {}
            self.doc_len.append(len(doc))
            for word in doc:
                if word not in tmp:
                    tmp[word] = 0
                tmp[word] += 1
            self.f.append(tmp)
            for k in tmp.keys():
                if k not in self.df:
                    self.df[k] = 0
                self.df[k] += 1
        for k, v in self.df.items():
            self.idf[k] = np.log((self.N - v + 0.5) / (v + 0.5))

    def get_score(self, query):
        score = np.zeros(self.N)
        for q in query:
            if q not in self.f[0]:
                continue
            idf = self.idf[q]
            for i in range(self.N):
                f = self.f[i].get(q, 0)
                score[i] += idf * (f * (self.k1 + 1) / (f + self.k1 * (1 - self.b + self.b * self.doc_len[i] / self.avgdl)))
        return score

# 示例
docs = [['hello', 'world'], ['hello', 'python'], ['python', 'world']]
bm25 = BM25_Model()
bm25.fit(docs)
query = ['hello']
score = bm25.get_score(query)
print(score)