信息检索(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)

    • 定义:词频是指某个词在文档中出现的次数。
    • 公式
  2. 逆文档频率 (IDF)

    • 定义:逆文档频率反映了词的普遍重要性。如果一个词在很多文档中都出现,则它的 IDF 值较低;如果一个词只在少数文档中出现,则它的 IDF 值较高。
    • 公式其中,加 1 是为了避免分母为 0 的情况。
  3. TF-IDF

    • 定义:TF-IDF 是词频和逆文档频率的乘积,用于评估一个词在文档中的重要性。
    • 公式

BM25

基本思想

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

计算公式

BM25 的具体计算公式如下:

其中:

  • $ 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 算法的例子:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
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 是文档集合。
    • k1b 是调整参数。
    • 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 得分,并按得分从高到低排序。