搜索引擎结果的好坏与否，Cranfield评价体系ACranfield-likeapproach

　　搜索引擎结果的好坏与否，Cranfield评价体系ACranfield-likeapproach

　　大观数据CEO陈韵文文

　　前言

　　搜索质量评价是搜索技术研究的基础工作，也是核心任务之一。度量在搜索技术的研究和发展中发挥着重要作用，因此任何新方法都与其评价方法相结合。

　　搜索引擎结果的质量反映在业界所谓的相关性上。相关性的定义包括狭义和广义两个方面。狭义的解释是：搜索结果与用户查询的相关程度。从广义上讲，相关性可以理解为用户查询的综合满意度。直观上，从用户进入搜索框的那一刻到满足需求的过程越顺畅、方便，搜索相关性就越好。本文总结了行业常用的相关性评价指标和定量评价方法。供对此感兴趣的朋友参考。

　　克兰菲尔德评估系统

　　A Cranfield-like approach这个名字来源于英国的克兰菲尔德大学，因为该大学在1950年代首先提出了这样一套评价体系：一套完整的查询样本集、正确答案集和评价指标。评价计划从此确立了“评价”在信息检索研究中的核心地位。

　　Cranfield 评价系统由三个环节组成：

　　1.提取代表性查询词，形成合适大小的集合

　　2.查询样本集合，从检索系统的语料库中找到对应的结果并标注（一般是手动）

　　3. 将查询词和带有标注信息的语料输入检索系统，使用预定义的评价计算公式对检索系统结果和系统返回的检索结果标注的理想情况进行评价结果有多接近。

　　查询词集的选择

　　Cranfield 评估系统广泛应用于各大搜索引擎公司。在具体应用中，首先需要解决的问题是构建一组测试查询词。

　　根据Andrei Broder（原在AltaVista/IBM/Yahoo）的研究，查询词可以分为三类：寻址查询（Navigational）、信息查询（Informational）和交易查询（Transactional）。对应的比例为：

　　Navigational ： 12.3%

Informational ： 62.0%

Transactional ： 25.7%

　　为了使评价符合网上的实际情况，通常查询词集也是按比例选取的。通常从在线用户的查询日志文件中自动提取。

　　另外，在查询集的构建中，除了上述查询类型外，还可以考虑查询的频率，热点查询（高频查询）和长尾查询（中和低频）分别占特定的比例。

　　另外，在抽取Query的时候，Query的长度也是经常要考虑的一个因素。因为短查询（单词查询）和长查询（多词查询）排序算法往往不同。

　　形成查询集后，使用这些查询词在不同系统（例如比较百度和谷歌）或不同技术（新旧排名算法的环境）之间进行搜索，并对结果进行评分以确定优劣和缺点。

　　图片：同一个Query：“大观数据”，各大搜索引擎结果*敏*感*词*。下面详细说一下评分的方法。

　　

　　

　　

　　

　　

　　

　　

　　

　　

　　

　　Precision-recall（accuracy-recall法）计算方法

　　信息检索领域最广为人知的评价指标是Precision-Recall（准确率-召回率）方法。这种方法提出了半个世纪，已经被很多搜索引擎公司的效果评估所采用。

　　顾名思义，这种方法由两个相互关联的统计数据组成：准确率和召回率：召回率衡量一个查询搜索所有相关文档的能力，而Precision衡量搜索系统排除相关文档的能力。 （简单解释一下：准确率是计算你从查询中得到的结果有多少是可靠的；召回率是指你检索到的所有可靠结果中有多少）。这两个是评价搜索效果最基本的指标，具体计算方法如下。

　　Precision-recall 方法假设给定的查询对应于检索到的文档集合和不相关文档的集合。这里假设相关性是二元的，用数学形式化方法描述，它是：

　　A 表示相关文档的集合

　　

　　表示不相关的集合

　　B 代表检索到的文档集合

　　

　　表示尚未检索到的文档集合

　　单个查询的准确率和召回率可以用以下公式表示：

　　

　　

　　（运算符∩表示两个集合的交集。|x|符号表示集合x中元素的个数）

　　从上面的定义不难看出召回率和准确率的取值范围在[0,1]之间。那么不难想象，如果系统检索到的相关性越多，召回率就越高。如果所有相关结果都被召回，那么此时召回就等于1.0。

　　

　　

　　精度-召回曲线

　　召回率和准确率反映了检索系统最重要的两个方面，这两个方面相互制约。因为在*敏*感*词*的数据采集中，如果期望检索到更多的相关文档，搜索条件必须“放宽”，这会导致一些不相关的结果混入，影响准确率。同样，当你想提高准确率，尽可能去除不相关的文档时，你必须实施更“严格”的检索策略，这也会排除一些相关的文档，降低召回率。

　　所以为了更清楚地描述两者之间的关系，我们通常用曲线来绘制Precision-Recall，可以简称为P-R图。常见的形式如下图所示。 （通常曲线是逐渐下降的趋势，即随着Recall的增加，Precision逐渐降低）

　　

　　

　　其他形式的 P-R

　　某些特定的搜索应用程序会更加关注搜索结果中的错误结果。例如，搜索引擎的反垃圾邮件系统会更加关注搜索结果中混入了多少作弊结果。学术界将这些错误结果称为假阳性结果。对于这些应用，他们通常选择使用误报率（Fallout）来统计：

　　

　　

　　Fallout 和 Presion 本质上是一样的。它只是从利弊计算出来的。它实际上是 P-R 的变体。

　　回到上图，Presion-Recall是一条曲线。比较两种方法的效果通常不够直观。你能不能把两者结合起来，直接反映到一个单一的值上？为此，IR学术界提出了F-Measure方法。 F-Measure由Presion和Recall的调和平均计算得出，公式为：

　　

　　

　　参数λε(0,1)调整系统在Precision和Recall之间的平衡。(通常λ=0.5，此时

　　

　　

　　)

　　这里使用调和平均代替通常的几何平均或算术平均。原因是调和平均强调小数的重要性，能灵敏地反映小数的变化，更适合反映搜索效果。

　　使用F Measure的好处是只需要一个数字就可以概括系统的搜索效果，方便比较不同搜索系统的整体效果。

　　P@N 方法点击因素

　　传统的Precision-Recall并不完全适用于搜索引擎的评价，因为搜索引擎用户的点击方式是独一无二的，包括：

　　A 60-65%的查询点击了名列搜索结果前10条的网页；

B 20-25%的人会考虑点击名列11到20的网页；

C 仅有3-4%的会点击名列搜索结果中列第21到第30名的网页

　　换句话说，大多数用户不愿意翻页看到搜索引擎给出的后续结果。

　　即使在搜索结果的第一页（通常会列出前 10 个结果），用户的点击行为也很有趣。我们使用下面的谷歌热图来观察（这张热图在第二个维度搜索结果页面上，可以通过光谱直观地表达用户在不同位置的点击兴趣。颜色越接近红色表示点击率越高强度）：

　　

　　

　　从图中可以看出，前3个搜索结果吸引了大量点击，属于最受欢迎的部分。也就是说，对于搜索引擎来说，前几个结果是最关键的，决定了用户的满意度。

　　

　　

　　康奈尔大学的研究人员通过眼动追踪实验对 Google 搜索结果中的用户行为进行了更准确的分析。从这张图可以看出，第一个结果已经获得了56.38%的搜索流量，第二、第三个结果的排名依次下降，但远低于第一的结果。前三个结果的点击率约为 11:3:2。前三个结果的总点击量转移了近 80% 的搜索流量。

　　其他一些有趣的结论是点击次数不会按顺序减少。第七名获得的点击次数最少。原因可能是用户在浏览过程中将页面下拉到底部。这时候只显示了网站的最后三名排名，第七名很容易被忽略。而第一屏最后一个结果获得的注意力（2.55）大于倒数第二个（1.45)），因为用户在转屏之前对最后一个结果的印象比较深page 搜索结果页第二页第一页（也就是第11个结果）只获得了第10个首页网站的40%的点击量，比首页第一个结果还要多其 1/60 到 1/100 的点击量。

　　因此，在定量评估搜索引擎的效果时，往往需要根据上述搜索用户的行为特征进行针对性的设计。

　　P@N 计算方法

　　P@N本身是Precision@N的缩写，指的是在考虑位置因素的情况下，针对特定查询检测前N个结果的准确率。比如单次搜索的前5个结果，如果其中4个是相关文档，则P@5 = 4/5 = 0.8。

　　该测试通常使用一个查询集（根据上述方法构建），其中收录几个不同的查询词。在使用P@N的实际评估中，通常使用所有查询的P@N数据计算算术平均值，用于判断系统整体搜索结果的质量。

　　N 的选择

　　对于用户来说，他们通常只关注搜索结果的前几个结果。因此，搜索引擎的性能评估通常只关注前5、或前3个结果，所以我们常用的N取值为P@3或P@5等。

　　对于一些特定类型的查询应用，比如导航搜索，因为目标结果很明确，所以N=1（即在评估中使用P@1）。例如，如果你搜索“新浪网”或“新浪首页”，如果第一个结果不是新浪网(url:)，则直接判断查询的准确度不符合要求，即P@1 =0

　　MRR

　　上面提到的P@N方法很容易计算和理解。但是细心的读者肯定会发现问题，就是在前N个结果中，第一个和第N个位置的结果对准确率的影响是一样的。但实际情况是，搜索引擎的评价与排名位置有着极大的关系。也就是说，第一个结果错误与第 10 个结果错误非常不同。因此，评价体系中需要引入区位因素。

　　MRR 是 Mean Reciprocal Rank 的缩写。 MRR 方法主要用于导航搜索或问答。这些检索方法只需要一个相关文档，这对召回率非常重要。不敏感，但更关心搜索引擎检索到的相关文档是否排在结果列表的前面。 MRR 方法首先计算每个查询的第一个相关文档位置的倒数，然后对所有倒数取平均值。比如一个收录三个查询词的测试集，前5个结果是：

　　查询一结果：1.AN 2.AR 3.AN 4.AN 5.AR

查询二结果：1.AN 2.AR 3.AR 4.AR 5.AN

查询三结果：1.AR 2.AN 3.AN 4.AN 5.AR

　　其中，AN代表无关结果，AR代表相关结果。那么第一次查询的Reciprocal Rank（Reciprocal Rank）RR1= 1/2=0.5；第二个结果 RR2 = 1/2 = 0.5;注意，倒数的值不会改变，即使得到了第二个结果更相关的结果。同理，RR3 = 1/1 = 1，对于这个测试集，最终的MRR=(RR1+RR2+RR3）/ 3 = 0.67

　　然而，对于大多数搜索应用来说，只有一个结果不能满足需求。在这种情况下，需要更合适的方法来计算效果。最常用的方法是下面的MAP方法。

　　地图

　　MAP方法是Mean Average Precison，是平均准确度法的缩写。它的定义是求检索到的每个相关文档的平均准确率（即Average Precision）的算术平均值（Mean）。在这里，准确度取了两次平均值，因此称为平均平均精度。 （注意：它不叫Average Average Precision，因为它丑陋，而且因为无法区分两个平均值的含义）

　　MAP 是一个单值指标，反映系统在所有相关文档上的表现。系统检索到的相关文档越高（等级越高），MAP就应该越高。如果系统没有返回相关文档，则准确率默认为0。

　　例如：假设有两个主题：

　　主题 1 有 4 个相关网页，主题 2 有 5 个相关网页。

　　系统检索到主题1的4个相关网页，排名分别为1、2、4、7；

　　主题 2 检索到 3 个相关网页，排名分别为 1、3、5。

　　对于topic 1，平均准确率MAP计算公式为：

　　(1/1+2/2+3/4+4/7)/4=0.83。

　　对于主题2，平均准确率MAP计算公式为：

　　(1/1+2/3+3/5+0+0)/5=0.45。

　　然后 MAP= (0.83+0.45)/2=0.64。"

　　DCG 方法

　　DCG是英文Discountedcumulative gain的缩写，中文可译为“折扣累积收益”。 DCG方法的基本思想是：

　　1.对每个结果的相关性进行分级衡量

　　2.考虑结果的位置，位置越高，重要性越高

　　3.排名越高（即好成绩），成绩排名越高，数值应该越高，否则会被处罚。

　　我们先来看第一个：相关性分级。在计算 Precision 时，这比简单地计算“准确”或“不准确”更精细。我们可以将结果细分为多个级别。比如常用的3个等级：Good、Fair、Bad。对应的分数rel为：Good:3/Fair:2/Bad:1。一些更详细的评估使用5级分类：非常好、好、一般、差、非常差，对应的分数rel可以设置为：非常好：2 / 好：1 / 一般：0 / 差：-1 /非常糟糕：-2

　　判断结果的标准可以根据具体的应用来确定。非常好通常意味着结果的主题完全相关，网页内容丰富，质量高。并且具体到每一位

　　

　　

　　DCG的计算公式不是唯一的。理论上，它只需要对数贴现因子的平滑度。我个人认为下面的DCG公式更合理，强调相关性，1、2的结果的折扣因子也更合理：

　　

　　

　　此时DCG前4个位置结果的折扣因子值为：

　　

　　

　　基于2的log值也来自经验公式，没有理论依据。实际上，可以根据平滑要求修改Log的基数。当值增大时（例如用log5代替log2），折现因子下降得更快，强调了前面结果的权重。

　　为了方便不同类型查询结果的横向比较，基于DCG，一些评价系统也对DCG进行了归一化。这些方法统称为nDCG（即归一化DCG）。最常用的计算方法是除以每个查询的理想值iDCG（ideal DCG）进行归一化，公式为：

　　

　　

　　对于nDCG，需要校准理想的iDCG。在实际操作中，难度极大，因为每个人对“最佳结果”的理解往往各不相同，从海量数据中选出最佳结果非常困难。但是，通常比较容易比较两组结果，因此在实践中通常选择比较结果的方法进行评估。

　　如何实现自动化评估？

　　上面介绍的搜索引擎量化评价指标在克兰菲尔德评价框架中得到了广泛的应用。业界知名的TREC（Text Information Retrieval Conference）一直在基于这样的方法组织信息检索评估和技术交流。除了TREC，一些针对不同应用设计的Cranfield评测论坛也在进行中（如NTCIR、IREX等）。

　　但是 Cranfield 评估框架的问题在于查询样本集合的标记。通过人工标注答案来评价网络信息检索是一个费时费力的过程，只有少数大公司可以使用。并且由于搜索引擎算法改进和运维的需要，需要尽可能缩短检索效果评价和反馈的时间，因此自动化评价方法对于提高评价效率非常重要。最常用的自动评估方法是 A/B 测试系统。

　　A/B 测试

　　

　　

　　A/B 测试系统

　　A/B 测试系统在搜索用户时自动判断用户的bucket id，并自动抽取流量导入不同的分支，让对应组内的用户看到不同的产品版本（或不同版本）。搜索引擎）。将记录用户在不同版本产品中的行为。这些行为数据通过数据分析形成一系列的指标，通过这些指标的比较，得出哪个版本好坏的结论。

　　在指标的计算上，可以进一步分为两种方法，一种是基于专家评级；另一种是基于点击统计。

　　专家评分的方法通常由搜索核心技术研发和产品人员进行。两种环境A和B的结果按照预先设定的标准进行评分，比较每个查询的结果，并根据nDCG等方法计算整体质量。

　　点击评分的自动化程度更高。这里有一个假设：同样的排序位置，点击次数多的结果质量要好于点击次数少的结果。 （即A2代表A测试环境的第二个结果，如果A2>B2，说明A2质量较好）。通俗的说就是相信群众（因为群众的眼睛是有眼光的）。在这个假设下，我们可以自动将 A/B 环境中前 N 个结果的点击率映射到分数上。通过统计大量的Query点击结果，可以获得可靠的分数对比。

　　交错测试

　　此外，Thorsten Joachims 等人提出的 Interleaving 测试方法。在2003年也被广泛使用。这种方法设计了一个元搜索引擎。用户输入查询后，将查询在多个知名搜索引擎中的查询结果随机混合反馈给用户，进而采集用户的结果点击行为信息。根据用户不同的点击倾向，我们可以判断搜索引擎返回结果的优劣。

　　如下图，算法A和B的结果横放，按流量划分测试，记录用户点击信息。根据点击分布判断A、B环境的优劣。

　　

　　

　　交错测试评价方法

　　Joachims 还证明了 Interleaving Testing 评估方法和传统 Cranfield 评估方法的结果高度相关。由于记录用户对搜索结果的选择是一个省力的过程，便于实现自动搜索效果评估。

　　总结

　　没有评价就没有进步。对搜索结果进行定量评价的目的是准确找出现有搜索系统的不足（没有搜索系统是完美的），然后逐步改进算法和系统。本文为大家总结了常用的评价框架和评价指标。这些技术就像一把尺子，每次搜索技术进步时都会测量距离。