谈谈BM25评分

1 什么是BM25

    摘录一段wiki

 

BM25 is a bag-of-words retrieval function that ranks a set of documents based on the query terms appearing in each document, regardless of the inter-relationship between the query terms within a document (e.g., their relative proximity). It is not a single function, but actually a whole family of scoring functions, with slightly different components and parameters. One of the most prominent instantiations of the function is as follows.

 

    文档搜索中，并没有例如pr（google）这样的权威的评分作为排序的依据，所以有各种各样评分标准来评价我们搜索的相关度，而BM25就是其中比较著名的一种。

 

2 怎么用BM25

    到底BM25评分还是个数学方法，我们先来看看它的数学表达式

 

 

 

 

 

大概解释一下公式的意思
对于公式1
score（D，Q）：就是我们所要计算的评分，即为【给定搜索内容】Q在【给定文档】D中的相关程度，分数越高表示相关度越高。
q：【给定搜索内容】Q中的语素，英文的话就是单词，中文的话需要先进行简单的切词操作。
f（qi,D）：在【给定文档】D中，某一个语素qi出现的频率。
|D|：【给定文档】D长度。
avgdl:索引中所有文档长度。
另外两个参数K1和b用来调整精准度，一般情况下我们取K1=2，b=0.75。

公式2是用来计算公式1中IDF（qi）的值
N：索引中文档的总数目。
n（qi）：索引中包含语素qi的文档的总书目。

至此，公式所有变量、常量意义明确，我们就可以开始计算了。
--------------------------------------------------------------
由于公式并不难以理解，纯计算部分coder的事就没必要列出来了，这里我想说的是如何把这套评分体系和lucene结合起来。

众所皆知，lucene有score的功能，详见以下链接
http://lucene.apache.org/java/2_4_0/scoring.html
就不细说了。

现在我们做一个简单的demo，加入附件中的jar包

Java代码

1. public static void main(String[] args) throws ParseException, IOException {   
2.     //建立索引   
3.     IndexSearcher searcher = new IndexSearcher("/doc");   
4.     //计算平均长度avgdl   
5.     BM25Parameters.load("avgLengthPath");   
6.     BM25BooleanQuery query = new BM25BooleanQuery("This is my Query",   
7.             "Search-Field", new MMAnalyzer());   
8.     //开始进行检索   
9.     Hits hits = searcher.search(query);   
10.     //输出结果   
11.     for (int i = 0; i < 10; i++) {   
12.         System.out.println(hits.id(i) + ":" + hits.score(i));   
13.     }   
14. }  

  public static void main(String[] args) throws ParseException, IOException {

   //建立索引

   IndexSearcher searcher = new IndexSearcher("/doc");

   //计算平均长度avgdl

   BM25Parameters.load("avgLengthPath");

   BM25BooleanQuery query = new BM25BooleanQuery("This is my Query",

      "Search-Field", new MMAnalyzer());

   //开始进行检索

   Hits hits = searcher.search(query);

   //输出结果

   for (int i = 0; i < 10; i++) {

     System.out.println(hits.id(i) + ":" + hits.score(i));

   }

  }

我们即可计算BM25,模仿baidu硬盘搜索做一个简单的玩意也可以很快上手了。

补充：除了lucene以外，mg4j也可以进行bm25的计算，甚至于比lucene更优秀的在于利用mg4j可以直接计算bm25。不过在中文分词方面，利用mg4j就远没有lucene方便，所以略去不谈。


3 BM25怎么样
简单分析一下bm25的算法我们可以知道这套评分方法还是基于在文档中出现频率，也就是说给定查询语句中的词素至少要有一个在给定文档中出现，不然计算结果会为0。

而由不愿意透露身份的王博士所介绍的基于以下两个公式的转移概率模型的评分则不需要有如此硬性的要求，譬如你在搜索“中国首都”时，会得到一篇含有“北京”字样的文档。



 

 


我们衡量一套搜索方法的原则无外乎准确度和量：
基于转移概率的搜索方法虽然得到的量会更多一些，的那是我们认为准确度会有所不足，并不是每组高转移概率的词汇对都会如“中国首都”和“北京”这样同义，可能会有很多无意义的转移词汇对或者根本不相关的词汇对，这将大大降低搜索的效率。

基于BM25的搜索方法在准确度上会更胜一筹，它的结果至少保证了是含有【给定搜索语句】的语素，事实上大部分实用的全文搜索也保证了这一原则。

由此对比，我们认为虽然基于转移概率模型的评分在理论上是一套更好的评分方法，但是实际操作用问题很多，在没有一个相对而言准确且大量的转移词汇对数据库前，基于BM25评分的搜索算法应该是更实用的。

 

评论

1 楼 zexunlee 2009-08-14  

此算法已经被Chengxiang Zhai的Risk Minimization Framework超越了。BM25是Robertson老先生的独门绝技，我一大学同学跟老Rob做1.5年博后，现在自己也是博导了，坐飞机似地，羡慕之极。下次我要跟随Zhai，死缠烂打也要跟着Zhai做访问学者（博后没指望了，已经毕业4年了，过了期限）。