文档介绍：? BM25 算法浅析 2011-02-10 13:38:00 by deepblue BM25 算法,通常用来作搜索相关性平分。一句话概况其主要思想:对 Query 进行语素解析,生成语素 qi;然后,对于每个搜索结果 D,计算每个语素 qi与D的相关性得分,最后,将 qi相对于D的相关性得分进行加权求和,从而得到 Query 与D的相关性得分。 BM25 算法的一般性公式如下: 其中,Q表示 Query , qi表示 Q解析之后的一个语素(对中文而言,我们可以把对 Query 的分词作为语素分析,每个词看成语素 qi。); d表示一个搜索结果文档; Wi 表示语素 qi的权重; R(qi , d) 表示语素 qi与文档 d的相关性得分。下面我们来看如何定义 Wi 。判断一个词与一个文档的相关性的权重,方法有多种,较常用的是 IDF 。这里以 IDF 为例,公式如下: 其中, N为索引中的全部文档数, n(qi) 为包含了 qi的文档数。根据 IDF 的定义可以看出,对于给定的文档集合,包含了 qi的文档数越多, qi的权重则越低。也就是说,当很多文档都包含了 qi时, qi的区分度就不高,因此使用 qi来判断相关性时的重要度就较低。我们再来看语素 qi与文档 d的相关性得分 R( qi,d)。首先来看 BM25 中相关性得分的一般形式: 其中, k1 , k2 ,b为调节因子,通常根据经验设置,一般 k1=2 , b= ; fi为 qi在d中的出现频率, qfi 为 qi在 Query 中的出现频率。 dl为文档 d的长度, avgdl 为所有文档的平均长度。由于绝大部分情况下, qi在 Query 中只会出现一次,即 qfi=1 ,因此公式可以简化为: 从K的定义中可以看到,参数 b的作用是调整文档长度对相关性影响的大小。b越大,文档长度的对相关性得分的影响越大,反之越小。而文档的相对长度越长, K值将越大,则相关性得分会越小。这可以理解为,当文档较长时,包含 qi的机会越大,因此,同等 fi的情况下,长文档与 qi的相关性应该比短文档与 qi的相关性弱。综上, BM25 算法的相关性得分公式可总结为: 从 BM25 的公式可以看到,通过使用不同的语素分析方法、语素权重判定方法,以及语素与文档的相关性判定方法,我们可以衍生出不同的搜索相关性得分计算方法,这就为我们设计算法提供了较大的灵活性。 1. BM25 算法 BM25 是二元独立模型的扩展,其得分函数有很多形式,最普通的形式如下: ∑其中, k 1 ,k 2 ,K均为经验设置的参数, f i是词项在文档中的频率, qf i是词项在查询中的频率。 K 1通常为 ,通常为 0-1000 K的形式较为复杂 K= 上式中, dl表示文档的长度, avdl 表示文档的平均长度, b通常取 2. BM25 具体实现由于在典型的情况下,没有相关信息,即r和R都是 0,而通常的查询中, 不会有某个词项出现的次数大于 1。因此打分的公式 score 变为∑ Lucene 实现 BM25 Lucene 本身的打分函数集中体现在 tf·idf 为了简化实现过程,直接将代码中 tf和idf 函数的返回值修改为 BM25 打分公式的两部分。文档的平均长度在索引建立的时候取得,同时