`

怎样量化评价搜索引擎的结果质量

阅读更多

 

 

怎样量化评价搜索引擎的结果质量


  来源:InfoQ
  作者:陈运文


  前言

 

 

  搜索质量评估 是搜索技术研究的基础性工作,也是核心工作之一。评价(Metrics) 在搜索技术研发中扮演着重要角色,以至于任何一种新方法与他们的评价方式是融为一体的。


  搜索引擎结果的好坏 与否,体现在业界所称的在相关性(Relevance) 上。相关性的定义包括狭义广义 两方面,狭义的解释是:检索结果和用户查询的相关程度 。而从广义的层面,相关性可以理解为为用户查询的综合满意度 。直观的来看,从用户进入搜索框的那一刻起,到需求获得满足为止,这之间经历的过程越顺畅,越便捷,搜索相关性就越好。本文总结业界常用的相关性评价指标量化评价方法 。供对此感兴趣的朋友参考。


  Cranfield评价体系


  A Cranfield-like approach 这个名称来源于英国Cranfield University ,因为在二十世纪五十年代 该大学首先提出了这样一套评价系统 :由查询样例集、正确答案集、评测指标构成的完整评测方案 ,并从此确立了“评价”在信息检索研究中的核心地位。


  Cranfield评价体系 由三个环节组成:

 

  1. 抽取代表性的查询词 ,组成一个规模适当的集合
  2. 针对查询样例集合,从检索系统的语料库中寻找对应的结果 ,进行标注(通常人工进行)
  3. 将查询词和带有标注信息的语料库输入检索系统,对系统反馈的检索结果,使用预定义好的评价计算公式,用数值化的方法来评价检索系统结果和标注的理想结果的接近程度


  查询词集合的选取


  Cranfield评价系统 在各大搜索引擎公司 内有广泛的应用。具体应用时,首先需要解决的问题是构造一个测试用查询词集合。


  按照Andrei Broder (曾在AltaVista/IBM/Yahoo任职)的研究,查询词可分为3类寻址类查询(Navigational)、信息类查询(Informational)、事务类查询(Transactional) 。对应的比例分别为

 

  • Navigational : 12.3%
  • Informational : 62.0%
  • Transactional : 25.7%


  为了使得评估符合线上实际情况,通常查询词集合 也会按比例 进行选取。通常从线上用户的Query Log文 自动抽取


  另外查询集合的构造时,除了上述查询类型 外,还可以考虑Query的频次 ,对热门Query(高频查询)、长尾query(中低频) 分别占特定的比例


  另外,在抽取Query时,往 Query的长短 也是一个待考虑的因素。因为短query(单term的查询)和长Query(多Term的查询)排序算法往往会有一些不同。


  构成查询集合后,使用这些查询词,在不同系统(例如对比百度和Google)或不同技术间(新旧两套Ranking算法的环境)进行搜索,并对结果进行评分,以决定优劣。


  附图:对同一Query:“社会保险法 ”,各大搜索引擎的结果示意图。下面具体谈谈评分的方法。

 

  



  Precision-recall(准确率-召回率方法)

 

  计算方法


  信息检索领域 最广为人知的评价指标Precision-Recall(准确率-召回率) 方法 。该方法从提出至今已经历半个世纪,至今在很多搜索引擎公司的效果评估中使用。


  顾名思义,这个方法由准确率召回率 这两个相互关联的统计量构成:召回率(Recall) 衡量一个查询搜索到所有相关文档的能力 ,而准确率(Precision) 衡量搜索系统排除不相关文档的能力 。(通俗的解释一下:准确率就是算一算你查询得到的结果中有多少是靠谱的;而召回率表示所有靠谱的结果中,有多少被你给找回来了)。这两项是评价搜索效果的最基础指标,其具体的计算方法如下。


  Precision-recall方法 假定对一个给定的查询,对应一个被检索的文档集合和一个不相关的文档集合。这里相关性被假设为二元的,用数学形式化方法来描述,则是:


  A表示相关文档集合

  A 表示不相关集合

  B表示被检索到的文档集合

  B 表示未被检索到的文档集合


  则单次查询的准确率和召回率 可以用下述公式来表达:

 

   

  

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


  从上面的定义不难看出,召回率准确率取值范围 均在[0,1] 之间。那么不难想象,如果这个系统找回的相关越多,那么召回率越高,如果相关结果全部都给召回了,那么recall此时就等于1.0。

 

  


  Precision-Recall曲线


  召回率准确率 分别反映了检索系统的两个最重要的侧面 ,而这两个侧面又相互制约 。因为大规模数据集合中,如果期望检索到更多相关的文档,必然需要“放宽”检索标准,因此会导致一些不相关结果混进来,从而使准确率受到影响。类似的,期望提高准确率,将不相关文档尽量去除时,务必要执行更“严格”的检索策略,这样也会使一些相关的文档被排除在外,使召回率下降。


  所以为了更清晰的描述两者间的关系,通常我们将Precison-Recall 用曲线的方式绘制出来,可以简称为P-R diagram 。常见的形式如下图所示。(通常曲线是一个逐步向下的走势,即随着Recall的提高,Precision逐步降低)

 

  


  P-R的其它形态


  一些特定搜索应用,会更关注搜索结果中错误的结果 。例如,搜索引擎的反作 弊系统(Anti-Spam System) 会更关注检索结果中混入了多少条作 弊结果。学术界把这些错误结果称作假阳性(False Positive) 结果,对这些应用,通常选择用虚报率(Fallout) 来统计:

 

  

 

  Fallout和Presion本质是完全相同的。只是分别从正反两方面来计算。实际上是P-R的一个变种。


  再回到上图,Presion-Recall是一个曲线,用来比较两个方法的效果往往不够直观,能不能对两者进行综合,直接反映到一个数值上呢?为此IR学术界提出了F值度量(F -Measure) 的方法。F-Measure通过Precision和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条结果),用户的点击行为 也很有意思,我们通过下面的Google点击热图(Heat Map) 来观察(这个热图在二维搜索结果页上通过光谱来形象的表达不同位置用户的点击热度。颜色约靠近红色 表示点击强度越高 ):

 

  

 

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

 

  

 

  康乃尔大学 的研究人员通过 eye tracking实验 获得了更为精确的Google搜索结果的用户行为分析图 。从这张图中可以看出,第一条结果获得了56.38%的搜索流量第二条和第三条结果的排名依次降低 ,但远低于排名第一的结果前三条结果的点击比例大约为11:3:2 。而前三条结果的总点击几乎分流了搜索流量的80%


  另外的一些有趣的结论是,点击量并不是按照顺序依次递减的排名第七位获得的点击是最少的 ,原因可能在于用户在浏览过程中下拉页面到底部 ,这时候就只显示最后三位排名网站,第七名便容易被忽略 。而首屏最后一个结果获得的注意力(2.55)是大于倒数第二位的(1.45),原因是用户在翻页前,对最后一条结果印象相对较深。搜索结果页面第二页排名第一的网页(即总排名11位的结果)所获得的点击只有首页排名第十网站的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@3P@5 等。


  对一些特定类型的查询应用,如寻址类的查询(Navigational Search),由于目标结果极为明确,因此在评估时,会选择N=1(即使用 P@1 。举个例子来说,搜索“新浪网”、或“新浪首页”,如果首条结果不是新浪网(url:www.sina.com.cn ),则直接判该次查询精度不满足需求,即P@1=0


  MRR


  上述的P@N 方法,易于计算和理解。但细心的读者一定会发现问题,就是在前N结果中,排序第1位和第N位的结果,对准确率的影响是一样的。但实际情况是,搜索引擎的评价是和排序位置极为相关的。即排第一的结果错误,和第10位的结果错误,其严重程度有天壤之别。因此在评价系统中,需要引入位置这个因素。


  MRR平均排序倒数(Mean Reciprocal Rank) 的简称,MRR方法主要用于寻址类检索(Navigational Search)或问答类检索(Question Answering) ,这些检索方法只需要一个相关文档,对召回率不敏感 ,而是更关注搜索引擎检索到的相关文档是否排在结果列表的前面 。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)RR1 = 1/2=0.5 ;第二个结果RR2 = 1/2 = 0.5 ;注意倒数的值不变,即使查询二获得的相关结果更多。同理,RR3= 1/1 = 1。对于这个测试集合,最终MRR=(RR1+RR2+RR3)/ 3 = 0.67


  然而对大部分检索应用来说,只有一条结果无法满足需求,对这种情况,需要更合适的方法来计算效果,其中最常用的是下述MAP方法。


  MAP


  MAP方法Mean Average Precison ,即平均准确率法 的简称。其定义是求每个相关文档检索出后的准确率的平均值(即Average Precision)的算术平均值(Mean) 。这里对准确率求了两次平均,因此称为Mean Average Precision 。(注:没叫Average Average Precision一是因为难听,二是因为无法区分两次平均的意义)


  MAP 是反映系统在全部相关文档上性能的单值指标。系统检索出来的相关文档越靠前(rank 越高),MAP就应该越高。如果系统没有返回相关文档,则准确率默认为0


  例如:假设有两个主题:


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


  某系统对于主题1检索出4个相关网页,其rank分别为1, 2, 4, 7;


  对于主题2检索出3个相关网页,其rank分别为1,3,5。


  对于主题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 是英文Discounted cumulative gain 的简称,中文可翻译为“折扣增益值 ”。DCG方法的基本思想是:

 

  1. 每条结果的相关性分等级来衡量
  2. 考虑结果所在的位置,位置越靠前的则重要程度越高
  3. 等级高(即好结果)的结果位置越靠前则值应该越高,否则给予惩罚


  我们首先来看第一条:相关性分级。这里比计算Precision时简单统计“准确”或“不准确”要更为精细。我们可以将结果细分为多个等级。比如常用的3级Good(好)、Fair(一般)、Bad(差)对应的分值rel为:Good:3 / Fair:2 / Bad:1 。一些更为细致的评估使用5级分类法Very Good(明显好)、Good(好)、Fair(一般)、Bad(差)、Very Bad(明显差),可以将对应分值rel设置为:Very Good:2 / Good:1 / Fair:0 / Bad:-1 / Very Bad: -2


  评判结果的标准可以根据具体的应用来确定,Very Good通常是指结果的主题完全相关,并且网页内容丰富、质量很高。而具体到每条

 

  

 
  DCG的计算公式并不唯一 ,理论上只要求对数折扣因子的平滑性。我个人认为下面的DCG公式更合理,强调了相关性,第1、2条结果的折扣系数也更合理:

 

  

  


  此时DCG前4个位置上结果的折扣因子(Discount factor) 数值为:

 

  


  取以2为底的log值也来自于经验公式,并不存在理论上的依据。实际上,Log的基数可以根据平滑的需求进行修改,当加大数值时(例如使用log5 代替log2),折扣因子降低更为迅速,此时强调了前面结果的权重。


  为了便于不同类型的query结果之间横向比较,以DCG为基础,一些评价系统还对DCG进行了归一,这些方法统称为nDCG(即 normalize DCG)。最常用的计算方法是通过除以每一个查询的理想值iDCG(ideal DCG)来进行归一,公式为:

 

  


 

  求nDCG需要标定出理想情况的iDCG,实际操作的时候是异常困难的,因为每个人对“最好的结果”理解往往各不相同,从海量数据里选出最优结果是很困难的任务,但是比较两组结果哪个更好通常更容易,所以实践应用中,通常选择结果对比的方法进行评估。


  怎样实现自动化的评估?


  以上所介绍的搜索引擎量化评估指标,在Cranfield评估框架(Cranfield Evaluation Framework) 中被广泛使用。业界知名的TREC(文本信息检索会议) 就一直基于此类方法组织信息检索评测和技术交流。除了TREC外,一些针对不同应用设计的Cranfield评测论坛 也在进行(如 NTCIR、IREX等)。


  但Cranfield评估框架存在的问题查询样例集合的标注 上。利用手工标注答案 的方式进行网络信息检索的评价是一个既耗费人力、又耗费时间的过程 ,只有少数大公司能够使用。并且由于搜索引擎算法改进、运营维护的需要,检索效果评价反馈的时间需要尽量缩短,因此自动化的评测方法 对提高评估效率十分重要。最常用的自动评估方法是A/B testing系统


  A/B Testing

 

 

  


 
 
                  A/B Testing系统


  A/B testing系统在用户搜索时,由系统来自动决定用户的分组号(Bucket id),通过自动抽取流量导入不同分支,使得相应分组的用户看到的是不同产品版本(或不同搜索引擎)提供的结果。用户在不同版本产品下的行为将被记录下来,这些行为数据通过数据分析形成一系列指标,而通过这些指标的比较,最后就形成了各版本之间孰优孰劣的结论。


  在指标计算 时,又可细分为两种方法,一种是基于专家评分的方法 ;一种是基于点击统计的方法


  专家评分的方法通常由搜索核心技术研发和产品人员来进行,根据预先设定的标准对A、B两套环境的结果给予评分,获取每个Query的结果对比,并根据nDCG 等方法计算整体质量。


  点击评分更高的自动化程度 ,这里使用了一个假设同样的排序位置,点击数量多的结果质量优于点击数量少的结果 。(即A2表示A测试环境第2条结果,如果A2 > B2,则表示A2质量更好)。通俗的说,相信群众(因为群众的眼睛是雪亮的 )。在这个假设前提下,我们可以将A/B环境前N条结果的点击率自动映射为评分 ,通过统计大量的Query点击结果,可以获得可靠的评分对比。


  Interleaving Testing


  另外2003年Thorsten Joachims 等人提出的Interleaving testing 方法也被广泛使用。该方法设计了一个元搜索引擎 ,用户输入查询词后,将查询词在几个著名搜索引擎中的查询结果随机混合反馈给用户,并收集随后用户的结果点击行为信息.根据用户不同的点击倾向性,就可以判断搜索引擎返回结果的优劣


  如下图所示,将算法A和B的结果交叉放置,并分流量进行测试,记录用户点击信息。根据点击分布来判断A和B环境的优劣。

 

 

  

 
     Interleaving Testing评估方法


  Joachims 同时证明了Interleaving Testing评价方法传统Cranfield评价方法 的结果具有较高的相关性。由于记录用户选择检索结果的行为是一个不耗费人力的过程,因此可以便捷的实现自动化的搜索效果评估。


  总结


  没有评估就没有进步 ——对搜索效果的量化评测,目的是准确的找出现有搜索系统的不足(没有哪个搜索系统是完美的),进而一步一个脚印对算法、系统进行改进。本文为大家总结了常用的评价框架和评价指标。这些技术像一把把尺子,度量着搜索技术每一次前进的距离。

 

  • 大小: 37.3 KB
  • 大小: 202.4 KB
  • 大小: 16.4 KB
  • 大小: 2.5 KB
  • 大小: 71.5 KB
  • 大小: 6.6 KB
  • 大小: 13.3 KB
  • 大小: 12.1 KB
  • 大小: 321.5 KB
  • 大小: 141.1 KB
  • 大小: 3.4 KB
  • 大小: 6 KB
  • 大小: 91.2 KB
  • 大小: 51.2 KB
  • 大小: 9.1 KB
  • 大小: 10.1 KB
  • 大小: 3.4 KB
  • 大小: 6 KB
分享到:
评论
1 楼 bluky999 2014-08-20  
@Mark 

相关推荐

    怎样量化评价搜索引擎的结果质量.pdf

    怎样量化评价搜索引擎的结果质量.pdf

    信息检索作业-搜索引擎性能评估

    这个作业的核心在于通过一系列标准指标来量化搜索引擎的性能,以帮助优化搜索结果并改进用户体验。下面,我们将详细讨论相关知识点。 首先,我们来看“信息检索”。信息检索是指在大量数据中寻找与特定查询相关的...

    搜索引擎优化(SEO)知识完全手册

    - **元搜索引擎**:不直接抓取网页内容,而是调用多个搜索引擎的结果,并对其进行整合。 - **目录搜索**:依赖于人工编写的目录,如早期的雅虎。 - **集成搜索**:结合了多种搜索方式,提供更全面的搜索结果。 **...

    电信设备-一种基于非点击操作信息的评价搜索结果的方法与设备.zip

    标题中的“电信设备-一种基于非点击操作信息的评价搜索结果的方法与设备”指的是在电信行业中,使用非点击操作信息来评估搜索引擎返回的结果质量和相关性的技术。这种方法关注的是用户未直接点击的搜索结果数据,...

    一种基于用户路径模型的搜索引擎检索性能度量方法

    2. **以任务为中心的度量**:着重考察搜索引擎在完成具体任务时的表现,如特定领域或类型的查询结果质量。 3. **以用户为中心的度量**:强调用户的实际体验和满意度,这是最贴近用户需求的评估方式。 #### 三、基于...

    <论文>搜索引擎安全功能和安全保证的研究及应用

    2. **缺乏评估标准**:行业内缺乏统一的安全评估标准,这使得相关产品的质量和对搜索引擎的保护程度难以量化评价。 3. **技术与产品开发不透明**:尽管已有不少针对搜索引擎安全的研究与开发工作,但相关技术和产品...

    信息检索:第九章 搜索引擎工作原理.ppt

    评价问题则是评估搜索引擎性能的关键,通常采用如TREC(Text REtrieval Conference)等基准测试,通过人工评估或离线评估来量化其效果。 用户信息需求的多样性要求搜索引擎不断进化,以适应各种查询场景,例如通过...

    google搜索引擎pagerank算法ppt

    总的来说,PageRank算法通过链接分析和随机浏览模型,提供了一种评估网页重要性的量化方法,为搜索引擎提供了一种有效的方法来排序搜索结果,从而提升用户体验。尽管随着搜索引擎技术的发展,PageRank不再是唯一的...

    系统评价、Meta-分析方法提要及结果解释.ppt

    3. 文献检索:使用多数据库和搜索引擎进行全面检索。 4. 纳入标准:根据预设的标准筛选相关研究。 5. 质量评估:对纳入研究的质量进行评估。 6. 数据提取:收集关键数据,如样本量、干预措施、结果等。 7. 统计分析...

    搜索行为评估与用户行为分析

    在搜索引擎的人工评价阶段,研发人员提出新排序策略后,会通过对比实验版本和线上基准版本的搜索结果,从而做出评估。人工评估工作往往耗时且无法大规模实施,因此评估效率和结果的代表性是该阶段所面临的主要问题。...

    PageRank技术分析与搜索引擎检索效率研究 (2003年)

    基于Robot的搜索引擎能够较全面地收集网页信息,基于分类目录的搜索引擎则依赖于人工分类,更易于提供有价值的检索结果,元搜索引擎则综合多个搜索引擎的结果,以提供更为合理的搜索结果。 PageRank算法的核心思想...

    2021年SEO权重站最新玩法.rar

    在SEO(搜索引擎优化)领域,权重站是一种策略性的网站构建和优化方法,旨在提升网站在搜索引擎结果页(SERP)的排名。2021年的SEO权重站最新玩法结合了过去的经验与新兴的趋势,旨在更好地适应搜索引擎算法的变化,...

    基于模糊综合评价的油菜网络信息可信度研究

    页面收录数则直接关系到网站内容被搜索引擎索引的广泛程度。 研究中还将网站的专业性作为一个重要指标进行了考量,这一指标在农业专业型网站的可信度评估中尤为关键。专业性指标考量的是网站内容是否具有针对性的...

    pagerank算法的论文1

    网页排序是对网页质量的量化评价,主要受网站组织与布局、网页信息数量和独特性等因素影响。在具体实施时,需考虑查询词在网页中的位置与频率,以及网页相对于其他网页的重要性。链接分析技术通过分析页面间的链接...

    分布式多主题网络爬虫系统的研究与实现

    其中,主题爬虫作为主题搜索引擎的基础,其网页抓取速度和质量成为评价搜索引擎优劣的重要标准。然而,主题爬虫的设计与实现面临着诸多挑战,如如何准确建模主题、如何评估页面与主题的相关性,以及如何在同一系统中...

    网站推广方案

    - **网站策划建设阶段**:此阶段应考虑SEO(搜索引擎优化),确保网站结构清晰,内容质量高,有利于搜索引擎抓取和用户的浏览体验。 - **网站发布初期**:通过登录搜索引擎和分类目录,建立合作伙伴链接,配合线下...

    使用翻译模型进行搜索成功评估

    这为搜索引擎优化提供了新的思路和方法,即可以通过评估搜索结果的“翻译质量”来间接评估搜索引擎的性能。 在论文中,作者进一步探讨了如何通过自动化方法减少评估工作量。这些方法通常涉及对用户的交互行为进行...

    网站运营标准文档.doc

    包括每日独立访客(IP)数量的增长、Alexa排名及其变化趋势、核心关键词在搜索引擎的排名、访问量、注册会员数以及入驻商家的数量。这些数据的变化直接影响着网站的吸引力和商业价值。 二、推广 1. 日常推广:有效...

    优质课件 北京大学研究生课程文本挖掘 文本数据挖掘全套PPT教程(共58页)TextMining09-文档自动摘要技术.pptx

    此外,NeATS(南加利福尼亚大学信息科学研究所)以及Vivisimo和infonetware公司的产品则在文档聚类和搜索引擎优化上有所贡献。这些系统通常包括预处理(如分词、去除停用词)、特征提取、重要性评分和摘要生成等步骤...

Global site tag (gtag.js) - Google Analytics