CWYAlpha

Just another WordPress.com site

Thought this was cool: 信息检索IR的评价指标综述

leave a comment »


信息检索评价是对信息检索系统性能(主要满足用户信息需求的能力)进行评估的活动。通过评估可以评价不同技术的优劣,不同因素对系统的影响,从而促进本领域研究水平的不断提高。信息检索系统的目标是较少消耗情况下尽快、全面返回准确的结果。

IR的评价指标,通常分为三个方面:
(1)效率(Efficiency)—可以采用通常的评价方法:时间开销、空间开销、响应速度。
(2)效果(Effectiveness):返回的文档中有多少相关文档、所有相关文档中返回了多少、返回得靠不靠前。
(3)其他指标:覆盖率(Coverage)、访问量、数据更新速度。

如何评价不同检索系统的效果呢?一般是针对相同的文档集合,相同的查询主题集合,相同的评价指标,不同的检索系统进行比较。相关的评测系统有:

(1)The Cranfield Experiments, Cyril W. Cleverdon, 1957 –1968
(上百篇文档集合)
(2)SMART System,Gerald Salton, 1964-1988 (数千篇文档集合)
(3)TREC(Text Retrieval Conference), Donna Harman, 美国标准技术研究所, 1992
-(上百万篇文档),信息检索的“奥运会”

信息检索的评价指标可以分为两类:
(1)对单个查询进行评估的指标:对单个查询得到一个结果
(2)对多个查询进行评估的指标(通常用于对系统的评价):求平均

 

一、单个查询的评价指标
P&R
召回率(Recall)=检出的相关文档数/相关文档数,也称为查全率,R∈[0,1]
准确率(Precision)=检出的相关文档数/检出文档数,也称为查准率,P∈[0,1]
假设:文本集中所有文献已进行了检查

关于召回率的计算
(1)对于大规模语料集合,列举每个查询的所有相关文档是不可能的事情,因此,不可能准确地计算召回率
(2)缓冲池(Pooling)方法:对多个检索系统的Top
N个结果组成的集合进行标注,标注出的相关文档集合作为整个相关文档集合。这种做法被验证是可行的,在TREC会议中被广泛采用。

虽然Precision和Recall都很重要,但是不同的应用、不用的用户可能会对两者的要求不一样。因此,实际应用中应该考虑这点。

(1)垃圾邮件过滤:宁愿漏掉一些垃圾邮件,但是尽量少将正常邮件判定成垃圾邮件。
(2)有些用户希望返回的结果全一点,他有时间挑选;有些用户希望返回结果准一点,他不需要结果很全就能完成任务。

F值和E值
(1)F值:召回率R和正确率P的调和平均值,if P=0 or R=0,
then F=0, else 采用下式计算:

或者公式:

F值也被称为F1值(F1 measure),因为recall和precision的权重一样。
更通用的公式如下:

其中F2值(更重视召回率)和F0.5值(更重视准确率)也是非常常用的指标值。

(2)E值:召回率R和正确率P的加权平均值,b>1表示更重视P

或者公式:

F和E的关系如下:

引入序的作用

R-Precision:计算序列中前R个位置文献的准确率。R指与当前查询相关的文献总数。

P-R曲线
P-R曲线是正确率-召回率曲线(precision versus recall
curve)。检索结果以排序方式排列,用户不可能马上看到全部文档,因此,在用户观察的过程中,正确率和召回率在不断变化(vary)。可以求出在召回率分别为:0%,10%,20%,30%,…,
90%,100%上对应的正确率,然后描出图像。
某个查询q的标准答案集合为:Rq={d3,d5,d9,d25,d39,d44,d56,d71,d89,d123}
某个IR系统对q的检索结果如下:

绘成曲线图如下:

P-R曲线的插值问题,对于前面的例子,假设Rq={d3,d56,d129}
(1)3. d56 R=0.33,P=0.33;8. d129 R=0.66, P=0.25; 15. d3
R=1,P=0.2
(2)不存在10%, 20%,…,90%的召回率点,而只存在33.3%, 66.7%, 100%三个召回率点
(3)在这种情况下,需要利用存在的召回率点对不存在的召回率点进行插值(interpolate)
(4)对于t%,如果不存在该召回率点,则定义t%为从t%到(t+10)%中最大的正确率值。
(5)对于上例,0%,10%,20%,30%上正确率为0.33,40%~60%对应0.25,70%以上对应0.2

P-R曲线的优点:简单直观;既考虑了检索结果的覆盖度,又考虑了检索结果的排序情况
P-R曲线的缺点:单个查询的P-R曲线虽然直观,但是难以明确表示两个查询的检索结果的优劣。

P-R曲线如何可以转化为单一指标呢?一般有两种方法:
(1)Break Point:P-R曲线上P=R的那个点。这样可以直接进行单值比较
(2)11点平均正确率(11 point average
precision):在召回率分别为0,0.1,0.2,…,1.0的十一个点上的正确率求平均,等价于插值的AP。

AP
平均正确率(Average Precision, AP):对不同召回率点上的正确率进行平均。
(1)未插值的AP:
某个查询Q共有6个相关结果,某系统排序返回了5篇相关文档,其位置分别是第1,第2,第5,第10,第20位,则AP=(1/1+2/2+3/5+4/10+5/20+0)/6

(2)插值的AP:在召回率分别为0,0.1,0.2,…,1.0的十一个点上的正确率求平均,等价于11点平均
(3)只对返回的相关文档进行计算的AP,
AP=(1/1+2/2+3/5+4/10+5/20)/5,倾向那些快速返回结果的系统,没有考虑召回率。

不考虑召回率情况下,单个查询评价指标还有:
(1)Precision@N:在第N个位置上的正确率,对于搜索引擎,考虑到大部分作者只关注前一、两页的结果,P@10,
P@20对大规模搜索引擎非常有效
(2)NDCG:后面详细介绍。
(3)Bpref:Binary preference,2005年首次引入到TREC的Terabyte任务中。

NDCG
每个文档不仅仅只有相关和不相关两种情况,而是有相关度级别,比如0,1,2,3。我们可以假设,对于返回结果:相关度级别越高的结果越多越好;相关度级别越高的结果越靠前越好。

NDCG(Normalized Discounted Cumulative
Gain):计算相对复杂。对于排在结位置n处的NDCG的计算公式如下图所示:

在MAP中,四个文档和query要么相关,要么不相关,也就是相关度非0即1。NDCG中改进了下,相关度分成从0到r的r+1的等级(r可设定)。当取r=5时,等级设定如下图所示:(应该还有r=1那一级,原文档有误,不过这里不影响理解。当然注意Value这一项,咱们也可以直接定义分值,如0-3分值。求了2方实际上把Value的差异变大了,便于对比评测)

例如现在有一个query={abc},返回下图左列的Ranked
List(URL),当假设用户的选择与排序结果无关(即每一级都等概率被选中),则生成的累计增益值(从1到n的所有的位置上的贡献值都被加起来作为最终的评价结果,这样,一个一定长度的文档序列被转换成了一个相关分值的序列)。如下图最右列所示:

考虑到一般情况下用户会优先点选排在前面的搜索结果,所以应该引入一个折算因子(discounting factor):
log(2)/log(1+rank)。(也就是1/log2(1+rank))。这时将获得DCG值(Discounted
Cumulative Gain)如下如所示:

最后,为了使不同等级上的搜索结果的得分值容易比较,需要将DCG值归一化的到NDCG值。操作如下图所示,首先计算理想返回结果List的DCG值:

然后用DCG/MaxDCG就得到NDCG值,如下图所示:

画出图如下:

NDCG优点:图形直观,易解释;支持非二值的相关度定义,比P-R曲线更精确;能够反映用户的行为特征(如:用户的持续性persistence)

NDCG缺点:相关度的定义难以一致;需要参数设定。

Bpref
Bpref(Binary
preference),2005年首次引入到TREC的Terabyte任务中。只考虑对返回结果列表中的经过判断后的文档进行评价。在相关性判断完整的情况下,bpref具有与MAP相一致的评价结果。在测试集相关性判断不完全的情况下,bpref依然具有很好的应用(比MAP更好)。这个评价指标主要关心不相关文档在相关文档之前出现的次数。具体公式为:

其中,对每个Topic,已判定结果中有R个相关结果。r 是相关文档,n是Top R篇不相关文档集合的子集。(n ranked
higher than r是指当前相关结果项之前有n个不相关的结果)

下面举个例子来说明bpref的性能,假设检索结果集S为:
S ={D1 ,D2 •,D3 * ,D4 * ,D5 •,D6 ,D7 •,D8 ,D9 ,D10 }
其中D2、D5 和D7是相关文档,D3 和D4为未经判断的文档。
对这个例子来说,R=3; bpref= 1/3 [(1 -1/3) + (1 -1/3) + (1 -2/3)]。

二、多个查询的评价指标
多个查询的评价指标,一般就是对单个查询的评价进行求平均。平均的求法一般有两种:
(1)宏平均(Macro Average):对每个查询求出某个指标,然后对这些指标进行算术平均
(2)微平均(Micro Average):将所有查询视为一个查询,将各种情况的文档总数求和,然后进行指标的计算
例如:Micro Precision=(对所有查询检出的相关文档总数)/(对所有查询检出的文档总数)
宏平均对所有查询一视同仁,微平均受返回相关文档数目比较大的查询影响。
宏平均和微平均的例子:
两个查询q1、q2的标准答案数目分别为100个和50个,某系统对q1检索出80个结果,其中正确数目为40,系统对q2检索出30个结果,其中正确数目为24,则:

P1=40/80=0.5, R1=40/100=0.4
P2=24/30=0.8, R2=24/50=0.48
MacroP=(P1+P2)/2=0.65
MacroR=(R1+R2)/2=0.44
MicroP=(40+24)/(80+30)=0.58
MicroR=(40+24)/(100+50)=0.43

 

MAP
MAP(MeanAP:Mean Average
Precision):对所有查询的AP求宏平均。具体而言,单个主题的平均准确率是每篇相关文档检索出后的准确率的平均值。主集合的平均准确率(MAP)是每个主题的平均准确率的平均值。MAP
是反映系统在全部相关文档上性能的单值指标。系统检索出来的相关文档越靠前(rank
越高),MAP就可能越高。如果系统没有返回相关文档,则准确率默认为0。
多个查询下的查准率/查全率曲线,可通过计算其平均查准率得到,公式如下(Nq为查询的数量) :

P(r) 是指查全率为r时的平均查准率, Pi(r)指查全率为r时的第i个查询的查准率 .

例如:假设有两个主题,主题1有4个相关网页,主题2有5个相关网页。某系统对于主题1检索出4个相关网页,其rank分别为1, 2,
4,
7;对于主题2检索出3个相关网页,其rank分别为1,3,5。对于主题1,平均准确率为(1/1+2/2+3/4+4/7)/4=0.83。对于主题2,平均准确率为(1/1+2/3+3/5+0+0)/5=0.45。则MAP=
(0.83+0.45)/2=0.64。”

MRR
MRR(Mean Reciprocal Rank)
:对于某些IR系统(如问答系统或主页发现系统),只关心第一个标准答案返回的位置(Rank),越前越好,这个位置的倒数称为RR,对问题集合求平均,则得到MRR。(把标准答案在被评价系统给出结果中的排序取倒数作为它的准确度,再对所有的问题取平均)

例子:两个问题,系统对第一个问题返回的标准答案的Rank是2,对第二个问题返回的标准答案的Rank是4,则系统的MRR为(1/2+1/4)/2=3/8

再举个例子:有3个query如下图所示:(黑体为返回结果中最匹配的一项)

可计算这个系统的MRR值为:(1/3 + 1/2 + 1)/3 = 11/18=0.61。

GMAP
GMAP(Geometric MAP):TREC2004 Robust 任务引进。
先看一个例子:从MAP(宏平均)来看,系统A好于系统B,但是从每个查询来看,3个查询中有2个Topic
B比A有提高,其中一个提高的幅度达到300%。

因此,我们计算几何平均值:

例子中:GMAPa=0.056,GMAPb=0.086。GMAPa<GMAPb
GMAP和MAP各有利弊,可以配合使用,如果存在难Topic时,GMAP更能体现细微差别。

 

三、面向用户的评价指标
前面的指标都没有考虑用户因素。而相关不相关由用户判定。假定用户已知的相关文档集合为U,检索结果和U的交集为Ru,则可以定义覆盖率(Coverage)
C=|Ru|/|U|,表示系统找到的用户已知的相关文档比例。假定检索结果中返回一些用户以前未知的相关文档Rk,则可以定义出新颖率(Novelty
Ratio)N=|Rk|/(|Ru|+|Rk|),表示系统返回的新相关文档的比例。
相对查全率:检索系统检索出的相关文档数量与用户期望得到的相关文档的数量的比例。
查全努力:用户期望得到的相关文档与为了得到这些相关文档而在检索结果中审查文档数量的比率。

图示覆盖率和新颖率

四、评价指标总结
最基本的评价指标:召回率、准确率
不足:
1、一些评价指标,如R-Precision,MAP,P@10等,都只考虑经过Pooling技术之后判断的相关文档的排序。
2、对判断不相关文档与未经判断的文档的差别并没有考虑。
3、测试集越来越大,由于相关性判断还基本上是人工判断,因此建立完整的相关性判断变得越来越难。

参考资料:
http://wenku.baidu.com/view/1c6fb7d7b9f3f90f76c61b74.html
http://en.wikipedia.org/wiki/Precision_and_recall
http://www.cnblogs.com/eyeszjwang/articles/2368087.html

转载请注明出处:互联网旁观者~黄言之 http://blog.sina.com.cn/netreview/

 

from 互联网旁观者: http://blog.sina.com.cn/s/blog_72995dcc01013oo9.html

Written by cwyalpha

五月 11, 2012 在 2:39 下午

发表在 Uncategorized

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s

%d 博主赞过: