检索评价 第三章

检索评测基础 检索评测基础: 建立在测试参考集和一定的评价测度基础之上。 检索策略的评价 检索评测基础: 建立在测试参考集和一定的评价测度基础之上。 测试集由一个文档集、一组信息查询实例、对应于每个信息查询实例的一组相关文档（由专家提供）所组成。  检索策略的评价 对一个给定检索策略S，对每个信息查询实例，评测由S检出的结果集合与由专家提供的相关文档集之间的相似性，量化这一指标。

检索性能评价 评价的类型 实验室评价和真实环境评价，两者不同。有时，结果出入也较大。 由于在实验室封闭环境下的评价具有可重复性，目前仍是主流。 还有对交互查询进行评测，需要考查界面的设计、系统引导、会话持续时间等因素。

测度1：查全率和查准率 对某个测试参考集,信息查询实例为I，I对应的相关文档集合为R。假设用某个检索策略对I进行处理后，得到一个结果集合A。令Ra表示R与A的交集。 Ra 查全率(Recall)：检出的相关文档个数与相关文档集合总数的比值，即R=|Ra| / |R| 查准率(Precision)：检出的相关文档个数 与检出文档总数的比值，即P=|Ra| / |A| R A

测度2： F1 值 F1 标准则综合了精度和查全率，将两者赋予同样的重要性来考虑。F1的计算由下面的公式决定

F1 值的其他说法 调和平均值 调和平均数定义为：数值倒数的平均数的倒数。其数值恒小于算术平均数。 计算查准率p和查全率r的调和平均数作为度量指标。F的取值在[0,1]。

测度3：查准率/查全率曲线 由于用户的查看是逐条进行相关性检查。故此，常用查准率/查全率曲线作为评价指标。   11点标准查全率下的查准率曲线，计算查全率分别为(0%,10%, 20%,…, 100%)下的查准率。即利用查全率，限制一下文档数，以此计算查准率。这种方法实质上考虑了输出元素的顺序。

Example Ranking for query q: d123* d84 d56* d6 d8 d9* d511 d129 d187 d25* d38 d48 d250 d113 d3* 对查询q,专家判定的相关文档集合为 Rq = {d3,d5,d9,d25, d39,d44,d56,d71, d89,d123}. |Rq|=10. 假设某一检索算法对查询q，输出如右列的检索结果 此时,查全率Recall=5/10， 查准率 Precision=5/15。  还可以看到：对应查全率为10%时的查准率为100%；对应查全率为20%时的查准率为66%；。。。。。对应查全率为60%时的查准率降为0。图示如下

Ranking for query q: d123* d84 d56* d6 d8 d9* d511 d129 d187 d25* d38

多个查询下的查准率/查全率曲线，可通过计算其平均查准率得到，公式如下(Nq为查询的数量) P(r) 是指查全率为r时的平均查准率, pi(r)指查全率为r时的第i个查询的查准率 .

由于每个查询的查全率值不一定就是这11个标准查全率，因此需要对查准率进行插补。 如上例中，若Rq只含有3个文档 Rq = {d3, d56, d129}. 此时，如何计算11点标准查全率呢？(查全率1/3,2/3,1} 设rj{j=0,1,2,…,10}为第j个标准查全率的一个参量 （如r3是查全率为30%的参量），则： 即第j个标准查全率水平的查准率是介于第j个和第j+1个查全率之间任意一个查全率所对应的查准率的最大值。

Rq = {d3, d56, d129} Ranking for query q: d123* d84 d56* d6 d8 d9* 检出d56, |A| = 3, 0.33, 检出2个， |A| = 8，2/8= 0.25， 检出d3, |A| = 15; 3/15= 0.2

多个查询下进行检索算法的比较 对多个查询，进行平均，有时该曲线也称为：查准率/查全率的值。 如下为两个检索算法在多个查询下的查准率/查全率的值。 第一个检索算法在低查全率下，其查准率较高。 另一个检索算法在高查全率下，其查准率较高 两个不同算法的平均查全率/查准率

另一种方法是：计算给定文档临界值处的平均查准率。如检出相关文档数为:5、10、15、20、30、50、100时的平均查准率。   目前平均查准/查全率的值已经成为信息检索系统的一项标准评价指标。 它能对整个结果集的质量和检索算法的适用范围进行量化评价，因此非常有效。

测度4： R-查准率 R-查准率 p@10 （目前Web信息检索中最常用的测度）,最常用语检查网页排序算法的好坏。 R=10, R-查准率=4/10; R=3, R-查准率=1/3, R-查准率显示了对检索结果排序的重要性.

测度5： 查准率直方图 用于快速比较两个检索算法的性能。 方法：在多个查询下，分别计算每一查询下的R-查准率，计算其差值，并用直方图表示。 具体地： 用RPA(i)和RPB(i) 分别表示使用检索算法A和检索算法B检索第i个查询时得到的R-查准率，它们之间的差值： RPA-B(i)=RPA(i)-RPB(i)

查准率直方图 假设10个查询的查准率直方图。（在8个查询中检索算法A好于算法B的性能） 假设十个查询的查询直方图.

意义: RPA/B(i) >0 时, 算法A(对第i个查询)比算法B好,反之B (对第i个查询)好.

测度6： E测度指标 思想：允许用户指出他更关心查准率或查全率 b=1, E= F； b>1表明用户对更查全率感兴趣（由于r/b2的值更小，相对地，P的值变大） b <1, 用户对查全率更感

其他测度 MPOS (n个查询对应的第1个相关结果的平均出现位置，Mean Position of the first relevant result)：所有查询的第一个相关结果位置的平均； MRR (第1个相关结果位置的倒数平均，Mean Reciprocal Ranking)：所有查询的第一个相关结果位置倒数的平均；MRR=0.5,意味着检索列表中前2项有相关文档。 Ranki 第i个查询所排的位置。

测度7：NDCG (Normalized discounted cumulative gain)

两个假设 应该把按相关度由小到大的顺序排序 相关度大的文档比相关度小的文档对用户来说应该更重要）,相关度大小可以 >1,如取0-7.

Cumulative Gain Cumulative Gain (CG) ：位于位置1 到p 的检索结果的相关度之和。 reli 表示第 i 个文档与查询语句的相关度。 特点：未考虑位置，即前p项中两文档交换不影响计算结果。 DCG 则希望改变这个特性。

Discounted Cumulative Gain 基本思想，若搜索算法把相关度高的文档排在后面，则应该给予惩罚。一般用log 函数表示这种惩罚。DCG 的计算如下：

另一种计算公式为：更强调前面的文档重要性。 The function is equivalent to the previous DCG function when the relevance values of documents are binary, i.e., reli {0,1}.

Normalizing DCG 显然，检索结果和具体查询有关，和序列的长度有关。为了规范化，我们把检索结果进行从大到小排序得到理想的输出序列。在这个理想的序列上计算DCG, 得到在位置p 的ideal DCG（IDCG) 。具体计算为：

Example Presented with a list of documents in response to a search query. Each document is to be judged on a scale of 0-3 with 0 meaning irrelevant, 3 meaning completely relevant, and 1 and 2 meaning "somewhere in between". For the documents ordered by the ranking algorithm as D1,D2,D3,D4,D5,D6 the IR system provides the following order list with relevance scores: 3,2,3,0,1,2 That is: document 1 has a relevance of 3, document 2 has a relevance of 2, etc. The Cumulative Gain of this search result listing is:

= 3 +(2+1.887+0+0.431+0.772) = 8.09

To normalize DCG values, an ideal ordering for the given query is: 3,3,2,2,1,0 The DCG of this ideal ordering, or IDCG, is then: IDCG6 = 8.693 And so the nDCG for this query is given as: nDCG6 = DCG6 / IDCG6 = 8.09/8.693= 0.9306

面向用户的测度方法  前述方法，相关文档集合是固定，并且独立于用户。而相关性是一个主观的概念，不同的用户有不同的看法。为此，可以采用面向用户的测度方法。 覆盖率(coverage)：实际检出的相关文档中，用户已知的相关文档所占的比例。原理如同查全率。区别是分母是用户自己的估计，而不是公认的数据。 新颖率(novelty)： 检出的相关文档中，用户未知的相关文档所占的比例。

Relevant Docs previously unknown to the user which were retrieved |Ru| Relevant Docs |R| Result set A Relevant Docs known to the user |U| The retrieved new docs unknown to users， Ru Relevant Docs known to the user which were retrieved |Rk|

检索结果的多样性（diversity）

续 目前约有17%的文档是语义上非常相似或近似copy. 目前信息检索的相似性只考虑query 与document之间的相似性，而没有考虑收集到文档之间的相似度。使得近似copy的文档输出在一起。 如何使得输出的结果能覆盖多个相关的文档簇，改善检索的覆盖率

图像检索的rerank 首先基于关键词得到输出（可能语义相关文档） 然后再根据图像特征，尽量使得图像统计特征太相似的图像只保存一个

对文本文档检索的多样性 是否可以把文档按不同的主题分簇组织，输出结果从每簇当中均选； 按文档的元数据特征，如时间、长短，地域等进行选择 对收集的文档集合进行clean，去除太相似或copy的文档

测试平台  检索性能的评价指标 测试集 检索性能评价的平台 TREC 中文Web测试集 CWT100g

TREC文献集合（测试集、语料库） 测试文档集合、检索问题集合、答案集合 测试文档集合的语料来源:  Wall Street Journal (华尔街时报) Associated Press（联合通讯社(简称美联社)） US Patents computer Selects, Ziff-Davis Federal Register US DOC Publications (abstracts) …

文档存放格式 <doc> <docno>WSJ880406-0090</docno> <h1>AT&T Unreils Services to Upgrade Phone Networks Under Global Plan</h1> <author>Janet Guyon(WSJ Staff)</author> <text American Telephone & Telegraph Co. introduced the first of a new generation of phone services with broad… </text> </doc>

CWT100g的Web文档存放格式 version: 1.0 // 版本号 url: http://www.pku.edu.cn/ // URL origin: http://www.somewhere.cn/ // 原来的URL date: Tue, 15 Apr 2003 08:13:06 GMT // 抓取时间 ip: 162.105.129.12 // IP地址 unzip-length: 30233 // 如果数据经过压缩，则需有此属性 length: 18133 // 数据长度 // 空行 XXXXXXXX // 以下为数据 XXXXXXXX ⋯. XXXXXXXX // 数据结束 // 最后再插入一个空行

信息查询实例（主题） 信息查询实例用自然语言描述 <top>  信息查询实例用自然语言描述  <top> <num> Number: 168</num> <title>Topic: Financing MATRAK <desc> Description>: A document will address the role of the Federal Government in financing the operation of the National Railroad Transportation Corporation (AMTRAK) <narr> Narrative: A relevant document must provide information on the government’s … </top>

各信息查询实例的相关文档集合 采用一种称为 pooling的技术来得到每一信息查询实例的相关文档集合。 pooling技术：针对某一信息查询实例，所有参与检索的系统分别给出各自检索结果中的前k个文档（如k=100），将这些结果文档汇集起来，得到一个可能相关的文档“池”（pool），然后由检索评价专家进行人工判断，最终评判每一文档的相关性。 已有的TREC评价实践表明，该方法产生的结果是准确的。

TREC的评价测度 11点标准查全率下的查准率（曲线或图） 计算给定文档临界值处的平均查准率， 如检出相关文档数为5、10、15、20、30、50、100时的平均查准率。 查准率直方图 概括表统计