BM25算法浅析

BM25算法浅析2011-02-1013:38:00bydeepblueBM25算法，通常用来作搜索相关性平分。一句话概况其主要思想：对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=0.75；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是二元独立模型的扩展，其得分函数有很多形式，最普通的形式如下：∑其中，k1,k2,K均为经验设置的参数，fi是词项在文档中的频率，qfi是词项在查询中的频率。K1通常为1.2，通常为0-1000K的形式较为复杂K=上式中，dl表示文档的长度，avdl表示文档的平均长度，b通常取0.752.BM25具体实现由于在典型的情况下，没有相关信息，即r和R都是0，而通常的查询中，不会有某个词项出现的次数大于1。因此打分的公式score变为∑3.使用Lucene实现BM25Lucene本身的打分函数集中体现在tf·idf为了简化实现过程，直接将代码中tf和idf函数的返回值修改为BM25打分公式的两部分。文档的平均长度在索引建立的时候取得，同时在建立索引的过程中，将每个文档的docID与其长度，保存在一个hashMap中。具体的函数实现如下（DefaulSimilarity类）：其中TermScore.temp为公式中K+fi的值Temp的计算在TermScore类中进行计算：publicfloatscore(){assertdoc!=-1;intf=freqs[pointer];temp=(float)(1.2*(0.25+0.75*FileSearch.docToken.get(doc))+f);System.out.println(weightValue:+weightValue);floatraw=getSimilarity().tf(f)*weightValue;//computetf(f)*weight//fSCORE_CACHE_SIZE//checkcache//?scoreCache[f]*temp//cachehit//:getSimilarity().tf(f)*weightValue*temp;//cachemissSystem.out.println(scorefuncdocid:+doc++temp++f++getSimilarity().tf(f));System.out.println(rawvalueis+raw);returnnorms==null?raw:raw*SIM_NORM_DECODER[norms[doc]&0xFF];}值得注意的是：在lucene的得分计算中，使用explain函数可以看出，除了tf、idf的乘积之外，还有一个fieldNorm值，这个值的计算是基于索引的建立过程，与文档以及field的长度有关，综合考虑，这个值对于查询的过程还是比较有效的，因此在具体实现中，依然保存了fieldNorm的值。1什么是BM25摘录一段wikiBM25isabag-of-wordsretrievalfunctionthatranksasetofdocumentsbasedonthequerytermsappearingineachdocument,regardlessoftheinter-relationshipbetweenthequerytermswithinadocument(e.g.,theirrelativeproximity).Itisnotasinglefunction,butactuallyawholefamilyofscoringfunctions,withslightlydifferentcomponentsandparameters.Oneofthemostprominentinstantiationsofthefunctionisasfollows.文档搜索中，并没有例如pr（google）这样的权威的评分作为排序的依据，所以有各种各样评分标准来评价我们搜索的相关度，而BM25就是其中比较著名的一种。2怎么用BM25到底BM25评分还是个数学方法，我们先来看看它的数学表达式大概解释一下公式的意思对于公式1score（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的功能，详见以下链接就不细说了。现在我们做一个简单的demo，加入附件中的jar包Java代码1.publicstaticvoidmain(String[]args)throwsParseException,IOException{2.//建立索引3.IndexSearchersearcher=newIndexSearcher(/doc);4.//计算平均长度avgdl5.BM25Parameters.load(avgLengthPath);6.BM25BooleanQueryquery=newBM25BooleanQuery(ThisismyQuery,7.Search-Field,newMMAnalyzer());8.//开始进行检索9.Hitshits=searcher.search(query);10.//输出结果11.for(inti=0;i10;i++){12.System.out.println(hits.id(i)+:+hits.score(i));13.}14.}publicstaticvoidmain(String[]args)throwsParseException,IOException{//建立索引IndexSearchersearcher=newIndexSearcher(/doc);//计算平均长度avgdlBM25Parameters.load(avgLengthPath);BM25BooleanQueryquery=newBM25BooleanQuery(ThisismyQuery,Search-Field,newMMAnalyzer());//开始进行检索Hitshits=searcher.search(query);//输出结果for(inti=0;i10;i++){System.out.println(hits.id(i)+:+hits.score(i));}}我们即可计算BM25,模仿baidu硬盘搜索做一个简单的玩意也可以很快上手了。补充：除了lucene以外，mg4j也可以进行bm25的计算，甚至于比lucene更优秀的在于利用mg4j可以直接计算bm25。不过在中文分词方面，利用mg4j就远没有lucene方便，所以略去不谈。3BM25怎么样简单分析一下bm25的算法我们可以知道这套评分方法还是基于在文档中出现频率，也就是说给定查询语句中的词素至少要有一个在给定文档中出现，不然计算结果会为0。而由不愿意透露身份的王博士所介绍的基于以下两个公式的转移概率模型的评分则不需要有如此硬性的要求，譬如你在搜索“中国首都”时，会得到一篇含有“北京”字样的文档。我们衡量一套搜索方法的原则无外乎准确度和量：基于转移概率的搜索方法虽然得到的量会更多一些，的那是我们认为准确度会有所不足，并不是每组高转移概率的词汇对都会如“中国首都”和“北京”这样同义，可能会有很多无意义的转移词汇对或者根本不相关的词汇对，这将大大降低搜索的效率。基于BM25的搜索方法在准确度上会更胜一筹，它的结果至少保证了是含有【给定搜索语句】的语素，事实上大部分实用的全文搜索也保证了这一原则。由此对比，我们认为虽然基于转移概率模型的评分在理论上是一套更好的评分方法，但是实际操作用问题很多，在没有一个相对而言准确且大量的转移词汇对数据库前，基于BM25评分的搜索算法应该是更实用的。Lucene的Ranking算法修改：BM25算法BM25算法BM25是二元独立模型的扩展，其得分函数有很多形式，最普通的形式如下：∑其中，k1,k2,K均为经验设置的参数，fi是词项在文档中的频率，qfi是词项在查询中的频率。K1通常为1.2，通常为0-1000K的形式较为复杂K=上式中，dl表示文档的长度，avdl表示文档的平均长度，b通常取0.752.BM25具体实现由于在典型的情况下，没有相关信息，即r和R都是0，而通常的查询中，不会有某个词项出现的次数大于1。因此打分的公式score变为∑3.使用Lucene实现BM25Lucene本身的打分函数集中体现在tfidf为了简化实现过程，直接将代码中tf和idf函数的返回值修改为BM25打分公式的两部分。文档的平均长度在索引建立的时候取得，同时在建立索引的过程中，将每个文档的docID与其长度，保存在一个hashMap中。具体的函数实现如下（DefaulSimilarity类）：其中TermScore.temp为公式中K+fi的值Temp的计算在TermScore类中进行计算：publicfloatscore(){assertdoc!=-1;intf=freqs[pointer];temp=(float)(1.2*(0.25+0.75*FileSearch.