TF-IDF和BM25算法原理及python实现

1. TF-IDF

TF-IDF是英文Term Frequency-Inverse Document Frequency的缩写，中文叫做词频-逆文档频率。

一个用户问题与一个标准问题的TF-IDF相似度，是将用户问题中的每一个词与标准问题计算得到的TF-IDF值求和。计算公式如下：

TF-IDF算法，计算较快，但是存在着缺点，由于它只考虑词频的因素，没有体现出词汇在文中上下文的地位，因此不能很好地突出语义信息。

代码实现

import numpy as np
class TF_IDF_Model(object):
    def __init__(self, documents_list):
        self.documents_list = documents_list
        self.documents_number = len(documents_list)
        self.tf = []
        self.idf = {}
        self.init()
 
    def init(self):
        df = {}
        for document in self.documents_list:
            temp = {}
            for word in document:
                temp[word] = temp.get(word, 0) + 1/len(document)
            self.tf.append(temp)
            for key in temp.keys():
                df[key] = df.get(key, 0) + 1
        for key, value in df.items():
            self.idf[key] = np.log(self.documents_number / (value + 1))
 
    def get_score(self, index, query):
        score = 0.0
        for q in query:
            if q not in self.tf[index]:
                continue
            score += self.tf[index][q] * self.idf[q]
        return score
 
    def get_documents_score(self, query):
        score_list = []
        for i in range(self.documents_number):
            score_list.append(self.get_score(i, query))
        return score_list

2. BM25

BM25是信息信息检索领域用来计算query与文档相似度得分的经典算法。
不同于TF-IDF，BM25的公式主要由三个部分组成：

query中每个单词t与文档d之间的相关性
单词t与query之间的相似性
每个单词的权重

BM25的一般公式:

其中， $Q$ 为用户问题， $d$ 为“标准问”库中的一个标准问题， $n$ 为用户问题中词的个数， $q_i$ 为用户问题中第 $i$ 个词， $W_i$ 为该词的权重， $R(q_i,d)$ 为该词与标准问题的相关性分数。

$W_i$ 相当于TF-IDF中的IDF， $R(q_i,d)$ 相当于是TF-IDF算法中的TF；只不过BM25对这两个指标进行了优化，具体如下：
$W_i = log(\frac{N-df_i+0.5}{df_i+0.5})$
其中， $N$ 表示"标准问"库中标准问题的总个数， $df_i$ 表示包含词汇 $q_i$ 的标准问题的个数。

$R(q_i,d) = \frac{f_i(k_1+1)}{f_i+K} * \frac{qf_i(k_2+1)}{qf_i+k_2}$
$K = k_1*(1-b+b*\frac{dl}{avg\_dl})$
其中， $k_1$ , $k_2$ 和 $b$ 是协调因子，一般分别设为 $2,1,0.75$ ； $f_i$ 表示词汇 $q_i$ 在标准问题中出现的次数， $qf_i$ 表示词汇 $q_i$ 在用户问题中出现的次数； $dl$ 为标准问题的长度； $avg\_dl$ 为“标准问”库中所有标准问题的平均长度。

即同时衡量 $q_i$ 在用户问题中的重要性和在标准问题中的重要性， $k_1$ ， $k_2$ 和 $b$ 用于协调这两者。

代码实现

import numpy as np
from collections import Counter
 
 
class BM25_Model(object):
    def __init__(self, documents_list, k1=2, k2=1, b=0.5):
        self.documents_list = documents_list
        self.documents_number = len(documents_list)
        self.avg_documents_len = sum([len(document) for document in documents_list]) / self.documents_number
        self.f = []
        self.idf = {}
        self.k1 = k1
        self.k2 = k2
        self.b = b
        self.init()
 
    def init(self):
        df = {}
        for document in self.documents_list:
            temp = {}
            for word in document:
                temp[word] = temp.get(word, 0) + 1
            self.f.append(temp)
            for key in temp.keys():
                df[key] = df.get(key, 0) + 1
        for key, value in df.items():
            self.idf[key] = np.log((self.documents_number - value + 0.5) / (value + 0.5))
 
    def get_score(self, index, query):
        score = 0.0
        document_len = len(self.f[index])
        qf = Counter(query)
        for q in query:
            if q not in self.f[index]:
                continue
            score += self.idf[q] * (self.f[index][q] * (self.k1 + 1) / (
                        self.f[index][q] + self.k1 * (1 - self.b + self.b * document_len / self.avg_documents_len))) * (
                                 qf[q] * (self.k2 + 1) / (qf[q] + self.k2))
 
        return score
 
    def get_documents_score(self, query):
        score_list = []
        for i in range(self.documents_number):
            score_list.append(self.get_score(i, query))
        return score_list