检索系统评价指标

Attention!

我的Dr.Sure项目正式上线了，主旨在分享学习Tensorflow以及DeepLearning中的一些想法。期间随时更新我的论文心得以及想法。

Github地址：https://github.com/wangqingbaidu/Dr.Sure

CSDN地址：http://blog.csdn.net/wangqingbaidu

个人博客地址：http://www.wangqingbaidu.cn/

信息检索评价指标

信息检索的指标包括两大类，一个是位置无关的指标：Precision，Recall,F-score，以及位置相关的指标，包括MAP,NDCG,ERR。

一、位置无关的指标

位置无关的评价指标，指的是对检索结果按照集合进行评价，忽略掉返回的顺序，例如要在一个检索系统中寻找人这样的标签，最后只要把所有的人更准，更多地返回即可。

1. Precision

准确率，指的是检索结果集合中，真正符合Query的结果的个数，除以检索结果的个数。

Precision=|S_relevant∩S_retrieval||S_retrieval| $$Precision=\frac{|S\mathrm{\_}relevant\cap S\mathrm{\_}retrieval|}{|S\mathrm{\_}retrieval|}$$

2. Recall

召回率，指的是检索结果集合中，真正符合Query的结果的个数，除以全部相关结果的个数。

Precision=|Srelevant∩Sretrieval||Srelevant| $$Precision=\frac{|S_{relevant}\cap S_{retrieval}|}{|S_{relevant}|}$$

3. Fn-score

F值是同时考虑到了准确率和召回率，相当于是准确率和召回率的一种加权。

Fn=(1+β2)×(precision×recall)β2×(presicion+recall) $$Fn=\frac{(1+{\beta }^2)\times (precision\times recall)}{{\beta }^2\times (presicion+recall)}$$

β的值既是n，一般情况下使用的是F1值，即准确率和召回率同等重要。

Fn=2×(precision×recall)presicion+recall $$Fn=\frac{2\times (precision\times recall)}{presicion+recall}$$

还有两种常用的值是F2以及F0.5，前者中recall重要程度是precision的两倍，后者则相反，precision重要程度是recall的两倍。

二、位置相关的指标

位置相关的评价指标，指的是对检索结果按照列表进行评价，不能忽略掉返回的顺序，例如要在一个检索系统中寻找美人这样的标签，最后不仅要把所有的人更准，更多地返回，而且要让返回美的人尽量地靠前。

1. MAP

准确率和召回率都只能衡量检索性能的一个方面，大多数情况下用户其实很关心搜索结果的排序。最理想的情况肯定是准确率和召回率都比较高。当我们想提高召回率的时候，肯定会影响准确率。所以可以把准确率看成是召回率的一种函数，Precision=f(Recall)，在R上进行积分，可以求P的期望均值。公式如下：

AveP=∫10P(r)dr=∑_k=1nP(k)Δ(k)=∑_k=1n(P(k)×rel(k))|S_relevant| $$AveP={\int }_0^{1}P(r)dr=\sum \mathrm{\_}{k=1}^{n}P(k)\mathrm{\Delta }(k)=\frac{\sum \mathrm{\_}{k=1}^n(P(k)\times rel(k))}{|S\mathrm{\_}relevant|}$$

其中rel(k)表示第k个文档是否相关，若相关则为1，否则为0，P(k)表示前k个文档的准确率。 AveP的计算方式可以简单的认为是：

AveP=1R×∑r=1Rrposition(r) $$AveP=\frac{1}{R}\times \underset{r=1}{\overset{R}{\sum }}\frac{r}{position(r)}$$

position(r)为返回结果列表中的位置，例如一个返回列表，长度为10， 只有1，2，5是相关的结果，则:

AveP=110×(11+22+35)=0.26 $$AveP=\frac{1}{10}\times (\frac{1}{1}+\frac{2}{2}+\frac{3}{5})=0.26$$

对于一个检索系统，其Query不止一个，所以对于所有的Query的AveP的均值即为MAP。

2. NDCG

MAP虽然把结果的位置引入到评价标准，但是其中对结果的评价只有相关和不相关两种，大多数情况下搜索结果与评价标准是非二值的。例如，结果和Query之间可以使非常相关， 相关， 无关， 垃圾。所以我们需要计算每个位置的收益。

1. Cumulative Gain(CG)：

前p个结果的累计收益为：

CG_p=∑_i=1prel_i $$CG\mathrm{\_}p=\sum \mathrm{\_}{i=1}^{p}rel\mathrm{\_}i$$

以上面的例子为例，rel可以表示为[2,1,0,-1]。

2. Discounted cumulative gain(DCG)：

可以看到，CG的评价标注是位置不敏感的，也就是对于一个检索的结果，两个检索系统，分别返回三个结果的相关性，如果是{2,2,-1}和{-1,2,2}。虽然他们的CG是一样的，但是显然前面的检索系统要好于后面的检索系统。

所以需要引入位置权重。即不同位置，产生的效益是不同的。

rel_i×1log_2(i+1)=rel_ilog_2(i+1) $$rel\mathrm{\_}i\times \frac{1}{log\mathrm{\_}2(i+1)}=\frac{rel\mathrm{\_}i}{log\mathrm{\_}2(i+1)}$$

公式如下：

DCGp=∑i=1prelilog2(i+1)=rel1+∑i=2prelilog2(i+1) $$DC{G}_p=\underset{i=1}{\overset{p}{\sum }}\frac{re{l}_i}{lo{g}_2(i+1)}=re{l}_1+\underset{i=2}{\overset{p}{\sum }}\frac{re{l}_i}{lo{g}_2(i+1)}$$

另一种常见的形式：

DCGp=∑i=1p2reli−1log2(i+1) $$DC{G}_p=\underset{i=1}{\overset{p}{\sum }}\frac{2^{re{l}_i}-1}{lo{g}_2(i+1)}$$

3. Ideal DCG(IDCG)

IDCG是理想情况下的DCG，即对于一个查询语句和p来说，DCG的最大值。公式如下：

IDCGp=∑i=1|REL|2reli−1log2(i+1) $$IDC{G}_p=\underset{i=1}{\overset{|REL|}{\sum }}\frac{2^{re{l}_i}-1}{lo{g}_2(i+1)}$$

其中|REL|表示，文档按照相关性从大到小的顺序排序，取前p个文档组成的集合。也就是按照最优的方式对文档进行排序。

4. Normalize DCG(NDCG)

由于每个查询语句所能检索到的结果文档集合长度不一，p值的不同会对DCG的计算有较大的影响。所以不能对不同查询语句的DCG进行求平均，需要进行归一化处理。nDCG就是用IDCG进行归一化处理，表示当前DCG比IDCG还差多大的距离。公式如下：

nDCGp=DCGpIDCGp $$nDC{G}_p=\frac{DC{G}_p}{IDC{G}_p}$$

3. ERR

这个指标充分考虑到了用户在使用检索系统时候的具体场景，一个很常见的事实是：一个用户通过检索系统找到一个他想要的结果之后，极有可能不再看其它的搜索结果，但是其它的结果并不代表不相关。所以有的时候第一个正确答案的位置在哪里也很重要。

1. Mean reciprocal rank (MRR):

reciprocal rank是指，第一个正确答案的排名的倒数。MRR是指多个查询语句的排名倒数的均值。公式如下：

MRR=1|Q|∑i=1|Q|1ranki $$MRR=\frac{1}{|Q|}\underset{i=1}{\overset{|Q|}{\sum }}\frac{1}{ran{k}_i}$$

Ranki是出现第一个正确答案的位置。

2. Cascade Models

虽然之前的评价模型都考虑到了结果本身的信息以及结果位置的信息，但是却忽略了文档之间的相关性。就像MRR评价函数那样，我们需要考虑到用户的行为，最优化用户获取信息的时间。

Cascade Models假设用户从排名由高到底依次查看文档，一旦文档满足了用户的需求，则停止查看后续的文档。用Ri表示用户只看在位置i上的文档后就不在需要查看其它文档的概率，显然文档的相关度越高，Ri越大。那么用户在位置i停止的概率公式如下：

PPr=∏i=1r−1(1−Ri)Rr $$P{P}_r=\underset{i=1}{\overset{r-1}{\prod }}(1-R_i)R_r$$

3. Expected reciprocal rank (ERR):

区别RR是计算第一个相关文档的位置的倒数，ERR表示用户的需求被满足时停止的位置的倒数的期望。

其中Ri是关于文档相关度等级的函数，可以选取如下的函数：

Ri=R(gi)=2g−12gmax,g∈{0,1,…⋯,gmax} $$R_i=R(g_i)=\frac{2^g-1}{2^{g_{max}}},g\in \{0,1,\dots \cdots ,g_{max}\}$$

所以ERR的计算公式如下：

ERR=∑r=1nφ(r)PPr=∑r=1n1rPPr=∑r=1n1r∏i=1r−1(1−Ri)Rr $$ERR=\underset{r=1}{\overset{n}{\sum }}\phi (r)P{P}_r=\underset{r=1}{\overset{n}{\sum }}\frac{1}{r}P{P}_r=\underset{r=1}{\overset{n}{\sum }}\frac{1}{r}\underset{i=1}{\overset{r-1}{\prod }}(1-R_i)R_r$$

更通用一点，ERR不一定计算用户需求满足时停止的位置的倒数的期望，可以是其它基于位置的函数φ(r)，只要满足φ(0)=1，且φ(r)→0随着r→∞。

三、参考文献

参考: http://blog.csdn.net/u010138758/article/details/69936041