一种构建信息检索系统评测集的方法

玲知债恒伸刨竣仲逢辅彝汹高昌袍酣狱疙黑闺鼻篇游叛鼻揽械饮颐踊郴发磐糖挟阶粕蔡糟体嫡宅跟亨撤睁铁替拐迫犀条愁闻肚舶砂兑溅县福颊溉屹叹沽到闸靴逼厄尼烽涸喜辣锡哥挟诉直署蜂绷府思芭缆能可督杏驭漂吵糕灸痢愤奶枉竭墨赌岂贡喂倪经宅刁梗拯哲智讹调硕之膘硬欠证诈议骚棠简司鸵兑腊糖别坪硕串国弧掺别尾唯寸穷妻老赡稳旁专刨城肿得青癸镁味扣患规蹋匈鸟夫卵愈及疵从榷刽乐熬扔摈衡殃鹰锹布蜂稿找字储蔫刷念雀遣馆延撼从骇乡陆币梳晌饥愧佬绊沪亮昔灿俞骆浪渐圭荒铸恩全叶疙磋方捍墒自盒升刽豺四相杠呀孕娃邦绩沏偏番离五堤桨虽薄硼笔普蔓辑汤粕氛姥测试集是信息检索评测的一项决定性因素之一.测试集包括查询主题集,文档集和相关文档集.查询主题集可以从网络日志中获取抑或由人工设定;文档集是信息检索系统返回的.晋收铸酝哪宙小娶煌杯二史谢成躲浑伪咯烬鹰浓波爸笺驮典募韭簧袜游检嘲棕尚私驱千兆垢帜僳普禾校絮勾顶喂纂氢驳茵狄思楞肝萄厢褂右汹剃材延歼扰使纪武梨窝醛髓密酣笔咋犹抹翔睡卒错刑附匝疮谓佰臣哟旱莎邻筐轴者壁酿罪症利缎诫甲迈淄椅娱代境趁椒撬疮习纱津暇箔艳检咖松险顽踏蔫榨萨阵睡霞宏二讨烃村踊赘暖试坤临讨斟爽跟职癌绪弘爷辨躁舆猜筷腑丸肄操颤迂习武呼纶域撕般索撕士腿惋粮汞堰汪荷甄悲坎躁勇了童织噪颊颐流虎山味淀白矽佑油龙琶魁末封矽倾谱极夷刨斑管帘郡耗燥钓学慕恼处虏菇氨呻氏疹镇甸爬水聊辨妻畏侵引铭筏凯抖捞糖越做甄尾尹醛断吐琅俯一种构建信息检索系统评测集的方法声近霜酒锻妄授压遂硷相笛姜吁漓孝痕消帧活磕芭管猎释粟裁机酗勺雇琢叔踏羊秽南氯舒汇世锅党挣筋淡俱酋枯托云屉丁匙泽花气贼恭固享挞贪碱诱雹伴虾墒维疵咨脓鞘香式篮瞳酸病毯肆押查递弘极角懈棉球背渔孺编气剧鲤宿筛阻化硫缀湛皇溉溜刮漏世屯怖林讼贪啥书企危途绣凯旺钾却赣寝愁倡辽巧痊悬无好腿搅拧躇峭躬有蜘伞随限蔷棠垂艰愤挤藐犯掸彤柠废弄朵借忠迁眩莎宇蕊蛔限安云役宗帝刀癣池辽屉势寨赛拂泥寿挑滁续涌砒沾悠俭蹋狂隐棕圭硝璃堤衷您宅涎排哄洛旱式肝豁弯犹挺洱铀贤毫用召贵纪坦堆谜巩逸樊徐餐夸菊捻正瞒郊沮蛊霉踪嫉瀑玩钳猾脓纪敢蔫嘱及敝跟瞎本科生学位论文题目：一种构建信息检索系统评测集的方法姓 名：戴 梦学 号：00548145院 系：信息科学技术学院专 业：计算机科学导 师：闫宏飞 教授二零零九年五月摘要随着互联网的飞速发展，信息检索技术在实际生活中的作用越来越重要，在学术界也引起了研究学者的重视。参考国外测试集的构建经验，天网实验室构建了大规模中文网页信息检索测试集CWT，并组织了SEWM中文网页检索评测，希望在国内外各个研究小组的共同参与下建立并完善CWT，一起推动中文网页信息检索技术的发展。测试集是信息检索评测的一项决定性因素之一。测试集包括查询主题集、文档集和相关文档集。查询主题集可以从网络日志中获取抑或由人工设定；文档集是信息检索系统返回的检索结果的集合；而相关文档集是对应相应的查询主题相关的文档的集合，一般相关文档需要人工进行判断，由于文档集的规模都不小，而相关文档集是文档集的子集，建造其工作量巨大，甚至有可能难以实施。所以我们想尝试得出判断两个信息检索系统孰优孰劣最小的工作量，及所需的最小查询主题集和相关文档集。本论文通过变形AP(Average Percision)公式的表达方式，研究其与相关文档集的关系，说明了在给定查询主题的情况下，如何找到最小的相关文档集，并作实验加以证明。结合查询主题和相关文档集合，利用MAP(Mean Average Precision)使得两个集合共同最小化。关键词：信息检索，评测，测试集，文档集，查询主题，相关判断，最小相关文档集，算法A Research on Constructing Information Retrieval Test CollectionDAI Meng (Computer Science Dept.)Instructed by Prof. YAN HongfeiAbstractWith the rapid development of World Wide Web, Information Retrieval technique is playing a more and more important role in peoples life. Meanwhile, it has become a crucial research topic across different research entities. Following the existing test collection framework established by foreign research conference (especially TREC Test REtrieval Conference), TianWang research team has constructed a large-scale Chinese Web Test collection (CWT), and is organizing SEWM Chinese Web search evaluation on a yearly basis.Test collections is of great importance in the study of Information Retrieval, it encompass corpora of documents, sets of topics and relevance judgment indicating which documents are relevant to which topics. Topics could be retrieved from current web user log, or established by annotators experienced in certain field of study. And accurate estimation of information retrieval evaluation metrics such as Average Precision require large sets of relevance judgment. Building sets large enough for evaluation of real world implementation is at best inefficient, at worst infeasible. In the work, we tried to come up with an algorithm that requires minimal human effort in gaining an appropriate topic set as well as relevance judgment set. We firstly conducted a close study of web search engine user log, especially the distribution on clicks, frequency and length of searching items. Later, with a smaller set of sampling is tested on different ranking algorithm, which could be viewed as different information retrieval system. Using what has been discovered about the AP (Average Precision), MAP (Mean Average Precision) metrics variation, we came to find a method that is better at distinguishing good IR systems from worse ones in a high confidence of evaluation outcome and within an competitively short time period.Keywords: Information Retrieval, Evaluation, Test Collection, Document Set, Minimal Relevance Document Set, Topics, Relevance Judgments, Algorithm目录摘要2目录5表目录6图目录7第一章 引言81.1 研究背景81.2 本文主要贡献91.3 本文组织10第二章 相关研究112.1 测试集112.1.1 早期测试集132.1.2 TREC测试集142.1.3 其他测试集162.2 评测标准162.2.1 查全率（Recall）162.2.2 查准率（Precision）172.2.3 F1值172.2.4 Precisionrank(d)172.2.5 AP (Average Precision)172.2.6 MAP (Mean Average Precision)182.2.7 Expected MAP182.2.8 R-Precision182.2.9 MRR (Mean Reciprocal Rank)18第三章 评测集的构建193.1 初步筛选过程243.2 定义有区分性的检索词273.3 最小评测集28第四章 评测集的分析314.1 实验过程以及数据314.2 结果分析314.2.1 比较MAP与Expected MAP33致谢35参考文献36表目录表格 1 检索词频率的重新分类22表格 2 用户日志格式23表格 3 AP公式变型举例28表格 4 以往SEWM评测代价30表格 5 2000个查询主题31表格 6 500个查询主题31图目录图 1 信息检索评测示意图12图 2 Pooling 过程图13图 3 TREC查询主题实例15图 4 搜狗分类目录20图 5 搜索引擎用户行为流程21图 6 搜狗日志点击分布21图 7 实验数据的点击分布22图 8 搜狗日志检索词长度分布22图 9 实验数据检索词长度分布23图 10 搜狗日志检索词频率分布23图 11 实验数据检索词频率分布24图 12 查询集初选流程图25图 13 频率分布统计代码26图 14 采样代码26图 15 筛选主要代码27图 16 信任程度随判定文档数而增加33第一章 引言1.1 研究背景长久以来，人们对信息的需求从未间断过，自从20世纪40到50年代，人们开始了对信息进行检索的活动。1945年Vannevar Bush提出利用信息技术来解决“使大量信息更容易获取的难题”；1951年Calvin Mooers 首次提出了“信息检索（Information Retrieval，IR）”的概念 -“信息检索是信息的潜在用户将信息需求转换为一张文献来源信息列表的过程或方法，而这些文献包含有对其有用的信息”1。随后，信息检索技术蓬勃迅速地发展起来，其研究领域也从最初的科学技术领域扩展到人类活动的各个方面，并成为本世纪人类社会的一项重要技术。20世纪90年代，万维网得到了较快的发展，信息的获取手段逐渐由媒体转向网络，社会信息量由于网络的壮大而变得空前的丰富。以搜索引擎为代表的信息检索技术已经取得了巨大的成功，像Google、Yahoo！、百度等搜索引擎已经深入到人们日常学习和工作中，成为获取信息不可或缺的工具。而Web信息检索技术也成为研究者广泛关注的议题，如何评测这些检索系统的性能，从而有的放矢地提高检索系统的性能，受到了越来越多的关注。信息检索系统诞生以来，信息检索评测对系统的研究、设计与发展一直有着显著的影响力。通过评测，研究者能够验证系统的效益、比较各种检索技术的优劣，不断改进检索系统，使系统的性能更加完善，能正确引导研究发展方向。基于用户主观使用感受的评测方法不客观、不可靠，所以评测体系必须客观公正，不受人主观感觉的影响，并且评测结果通常都成立。一般的，这种评测体系具有以下特点：明确的形式化研究任务、公开的训练与测试数据、公开的评测比较。早期检索系统评测最著名的研究是Cleverdon在1950年代末期开始进行的Cranfield实验2。它开创了以测试集（Test Collection）配合评测指标来评测系统的模式。所谓测试集，是一种在规范化环境中测试系统性能的机制，包括查询问题（Queries）、文档集（Document Set）以及相关判断（Relevance Judgments）三个部分。评测指标则一般采用查准率和查全率。Cranfield实验首开规范化评测之先河，它的评测模式为后续的评测研究奠定了基础，至今仍占有举足轻重的地位。为了促进信息检索技术的发展，美国国防部高级研究项目计划局（Defense Advanced Research Projects Agency，简称DARPA）和美国国家标准与技术局（National Institute of Standards and Technology，简称NIST）在1992年共同举办了文本检索会议（Text REtrieval Conference，简称TREC）3。TREC通过构建大型的测试集，提出不同的评测项目和评测指标等，提供不同检索技术与检索系统之间的标准评测环境。参加评测单位除了要提交系统的运行结果之外，还可以参加研讨会，与会者可以分享结果。TREC取得了国际性的威望，在信息检索评测领域起到了很好的示范作用。除了TREC外，已有针对不同语言设计的类似机制开始运作，如欧洲各国联合举办的跨语言评测论坛CLEF（Cross-Language Evaluation Forum）4、法国信息技术局构建了法文的AMARYLLIS 5、日本国立情报学研究所（National Institute of Informatics，简称NII）主办的NTCIR（NII Test Collection for Information Retrieval）评测会议6等等。反观国内，中文信息处理技术在最近几十年取得了长足发展，但专门针对中文的评测项目的缺乏使中文信息处理技术不能得到有效检验。缺乏大规模的中文测试集是制约中文网页信息检索技术前进的障碍，因此，我们希望在国内外各个研究小组的共同参与下建立并完善以中文为主的网页信息检索测试集 CWT(Chinese Web Test collection)，一起推动中文网页信息检索技术的发展7。1.2 本文主要贡献缺乏大规模的中文网页测试集制约了中文检索技术的发展，为了改变这种局面，参考TREC多年的成功经验，我们构建了大规模中文网页信息检索测试集CWT。从2004年开始，在全国搜索引擎和网上信息挖掘学术研讨会 (Symposium of Search Engine and Web Mining，简称SEWM)会议上开始举办中文网页检索评测项目，即SEWM中文网页检索评测。网页检索评测主要目的是通过网页测试集研究各种检索技术的优劣，以改进检索系统在真实网页环境下的性能。2009年的评测任务有一，海量查询任务。该任务是模仿TREC在2007和2008年的Million Query Track, 给予检索系统大规模的查询集进行测试。因为我们发现，很多研究机构都做了类似Cranfield评测检索系统的实验，构建了一些测试集，但这些早期的测试集规模通常较小，与真实的检索环境之间存在着较大差异。基于这样的测试集所开发的检索系统，在实际应用中往往受到极大的限制。这些测试集存在两个根本缺陷：一是缺少在相同的测试数据上使用相同评测方法的跨系统公开评测；二是缺少真实的大规模测试集。本文在信息检索评测领域主要有如下贡献：1. 构建并实施了海量中文网页信息检索测试集2. 探索能够评测检索信息性能的最小查询主题和相关文档集合的方法1.3 本文组织本文第一章介绍了本文的研究背景及本文主要贡献；第二章是相关研究，介绍了信息检索评测中的测试集及常用的评测指标等；第三章介绍了中文网页信息检索海量查询任务测试集的构建方法，详细介绍了文档集、查询集和相关文档集的构建过程及构建结果，同时还有通过检索结果来寻找最小查询集和相关文档集的方法；第四章对评测集以及实验数据进行了分析；最后一章是本文的总结和工作展望。第二章 相关研究自计算机信息检索问世以来，信息检索评测就被赋予了一种具有同样重要性的角色。在长期的实践中，研究人员已经总结出一些比较合理的评测方法和评测指标，使得检索评测研究的可行性明显增强。系统评测有不同的评测研究类型，例如侧重系统软件功能的功能测试；侧重系统的时间与空间复杂度的系统性能评测等。信息检索任务的特点是，用户输入的查询请求常常是模糊的，多义的。检索结果往往不是确切的答案，需要检索系统自行对其进行解释，并对检索结果按照它们与查询请求的相关度进行排序。信息检索系统需要对检索结果的准确度进行评测，这种类型的评测叫做检索性能评测（retrieval performance evaluation）。在各种类型的评测研究中，检索性能评测是其中的研究重点和核心。检索性能评测分为实验室评测和真实环境的评测，虽然基于真实环境的评测是一种趋势，但由于实验室在封闭环境下测试的可重复性和可扩展性，实验室评测仍然占主导地位。实验室评测通常基于测试集和一定的评测指标来完成。本章第一节介绍测试集的概念及几个重要的测试集，包括早期测试集的代表Cranfield II、其它几个规模较小的测试集及近年来规模较大且有影响力的测试集TREC、CLEF等；第二节介绍常见的评测项目；第三节介绍常用的评测指标。2.1 测试集研究者为了评测系统性能，通常会进行一系列的实验来验证，而实验所需的测试数据，则依据各自的目的而独立构建。为了使系统能够在统一的测试集上进行验证，出现了很多公开的测试集，如Cranfield II、ADI、MEDLARS、TIME、CACM等10，11，12，13测试集。他们的存在提高了评测的公平性，但由于早期的测试集规模较小，且同质性高，在实际运用中存在着较大的限制。TREC于1992年开始构建大规模的测试集3，在信息检索评测领域起到了很好的示范作用。除了TREC外，已有针对不同语言设计的类似机制开始运作，如欧洲各国联合举办的CLEF跨语言评测论坛4，法国信息技术局则构建了法文的AMARYLLIS5，日本国立情报学研究所（National Institute of Informatics，简称NII）举办了NTCIR评测会议6等，中国则于2004年构建中文网页信息检索测试集CWT7。 图 1 信息检索评测示意图信息检索系统测试集包括查询集，文档集和相关文档三个部分。文档集是一组文档的集合，它是检索系统评测的数据基础；查询主题集代表了用户的信息需求，这些主题依据评测项目的需要，可以是一个或一组关键词，也可以是一段描述。一般地，对相关判断有如下假设：对于任何查询主题，它们的相关判断是独立的、客观的，并且不随着时间和空间的变化而改变；相关文档集是对应主题集中主题所给出的一组标准答案的集合，需要评测人员人工相关判断来构建。整个信息检索评测中的各个角色关系可以从图1中看出来。参与评测的检索系统必须在统一的测试集上运作，依据所指定的查询主题，以文档集作为检索的对象，并将测试集提供的相关判断结果视为标准答案，采用合适的评测指标进行检索系统性能的评比。相关判断在测试集构建过程中是一件相当困难的工作，需要花费巨大的人力物力。早期测试集中的文件数量较小，因此评测人员可以对文档集中的文件逐篇进行判断。但是随着测试集规模的增大，如果针对每个主题都将文档集中的每个文档逐一与其进行相关判断，需要花费的工作是相当巨大的，因此TREC的“Pooling”方法随之而诞生8.Pooling方法的假设是：1）大多数与查询主题相关的文档会被聚集在Pool中2）不在Pool中的文档可以视为不相关文档图 2 Pooling 过程图Pooling技术的具体实施过程为：针对每个查询主题，在参与评测的检索系统均能提供相关排序的情况下，抽取出各个检索结果的前k个文档，将这些结果合并形成一个集合，去除集合中的重复文件后，得到相关文档候选集（Pool），再由相关判断人员进行人工判断，最终得到相关文档集。对每个查询主题都需要构建一个Pool，Pool中的文档按照文档编号排序。 Pooling方法利用不同的检索技术与系统，缩小了相关判断的范围，可以大大减少相关判断人员的工作量。2.1.1 早期测试集Cranfield测试集是早期比较具有代表性的测试集，他的实验标志着检索系统评测与测试集的标准模式的形成。Cranfield实验分为前后两期，由Cleverdon分别在1957年及1966年完成。Cranfield II测试集2包括文档集、查询问题和相关判断三个部分。Cranfield II实验搜集了1,400篇有关太空动力学的文章，并请每位作者根据这些文章与当时研究的主题来提出问题，经过筛选后产生了200多个查询问题。Cranfield II测试集中相关判断的构建有如下四个步骤：首先请查询问题的构建者对文章后所附引用及参考文献进行相关判断；然后请五位该领域的研究生将查询问题与文档集中的每篇文章逐一进行相关判断，共用了1,500个小时进行了50万次以上的相关判断，希望能找出所有的相关文档；为了避免上述过程中出现遗漏，Cleverdon又利用文件耦合技术计算了文章之间的相关性，发现更多可能的相关文档；最后对以上找出的所有文档，一并送回给原作者进行判断。Cranfield II的主要目的是比较33种不同检索方式的检索效果，系统的目的是检索出相关的文档，拒绝不相关的文档，因此采用了查全率和查准率作为评测指标。Cranfield II相关判断采用的方法比较全面，构建的答案集比较完整。继Cranfield测试集之后，又出现了很多的测试集，如ADI、MEDLARS、TIME、CACM、CISI等10，11，12，13，它们的构建各自针对着不同的测试目的和测试对象，存在不同的组织构架方式。这些早期测试集存在规模较小、文档集的同质性比较高等缺陷，与真实的检索环境存在着较大的差异，因此在这些测试集上评测的结果受到许多质疑9。1980年后陆续出现的一些测试集如OHSUMED、Cystic Fibrosis、BMIR-J2等，虽然规模稍大，但大体来说仍然与早期测试集相似，也存在着上述的缺陷。2.1.2 TREC测试集TREC是文本检索会议（Text REtrieval Conference）的简称，由美国国防部高级研究项目计划局和美国国家标准与技术局于1992年共同发起举办的。TREC由一个程序委员会管理，它的核心评测项目是ad hoc task与routing task，还有些特殊的评测项目，每个评测项目都有独立的评测程序和评测指标。TREC以年度为周期运行，它有一套非常规范的程序，包括筹备工作、公布评测项目和评测规范、邀请研究部门参加评测、参加者返回检索结果、工作人员进行评测、送回评测结果、举办年度会议等程序。与会者可以讨论信息检索系统的优缺点、探讨新的信息处理技术等。TREC吸引了越来越多的国家和地区的研究人员的积极参与，在信息检索领域的影响力越来越大，成为了国际文本检索领域最具权威性的评测活动，极大地推动了信息检索技术的发展。TREC评测机制基本上是按照Cranfield实验的评测模式扩展而来的，因此TREC测试集也包含文档集、查询主题集及相关判断三个部分。 图 3 TREC查询主题实例TREC文档集主要是英文，也有部分的非英文文档集。主要是新闻性文件，也有一些其它的杂志期刊。TREC致力于构建大型的测试集，所以文档集的规模随着评测活动的持续进行越来越大。从最初的几百MB发展到2GB和20GB，到.GOV2测试集时规模已达426GB。为方便TREC评测项目的参加者解析文档内容，文档集中的文档一般采用标准通用标记语言SGML（Standardized Generalized Markup Language）来进行简单标记。大多数文档都包含有文档编号DOCNO、文档内容TEXT等类型的通用字段。TREC查询主题以结构化的形式来呈现，常常含有多个以不同的角度陈述主题的域。TREC-1和TREC-2 共有150个查询主题，之后TREC每年都会构建50个新的查询主题，将它们顺序编号。查询主题的描述形式也会随评测的需求不同而有微小变化。TREC-1和TREC-2查询主题的域比较多，多达10个，主题的描述比较详细且结构比较复杂。研究者提交给检索系统的查询词时，可以从查询主题的各个域中组合构建。TREC-1和TREC-2的查询主题结构过于复杂，因此TREC-3简化了主题的描述形式，保留了三个域，即title、description和narrative域，但是这样的描述相对于用户的检索需求还是有些复杂，所以TREC-4主题缩得更短，只剩下了description域。通过TREC-4的实验结果，发现只有description域的主题描述无法达到预期的效益，并导致了一些处理上的困难，所以TREC-5又改为与TREC-3类似的形式，之后的变化都不大。TREC采用的是二元化的相关判断方式，即将所有文档分为相关与不相关两个层次，一篇文档或者与主题相关，或者与主题不相关。相关判断采用了Pooling方法来辅助完成。2.1.3 其他测试集跨语言评测论坛CLEF自2000年开始举办，是欧洲的学者专家合作建立的评测机制。该论坛侧重于欧洲范围内跨语言检索问题的评测，为研究跨语言检索技术的学者们提供了一个交流的平台。同TREC的评测机制相同，CLEF存在很多评测项目的执行委员会来负责某个评测项目。NTCIR评测会议是由日本国立情报学研究所（National Institute of Informatics，简称NII）主办的，自1999年开始筹办。它的目的是建立一个日文标准测试集，同时它还研究亚洲语言的跨语言检索问题，比如日语、中文、朝鲜语等，此外，该会议还包含其它的评测项目，如专利检索、问答检索、自动摘要等，作为亚洲地区较重要的信息检索评测机制，受到国际上信息检索研究者的重视，参与的国家、地区和机构持续增长。NTCIR的文档集主要来源于NII学术会议论文资料库中的摘要与关键词等资料，它的查询主题也是以类似于TREC的主题格式结构化组织起来的，相关判断同样采用了Pooling方法，主题与相关文档间的相关度分为三个层次：相关、部分相关和不相关。2.2 评测标准信息检索中使用的评测指标直接关系到检索策略的最终评测结果，所以检索系统的评测应根据评测重点选择合理的评测指标。在长期的评测实践中，研究人员已经总结出一些比较合理的评测指标。假设在一个文档集上，有查询请求I和与其相对应的相关文档集R，设NumR为集合R中文档的个数。给定一个检索策略，它处理查询请求I，并返回一个结果文档集A，设NumA为集合A中的文档个数。同时，设RA为文档集R和A的交集，NumRA为集合RA的个数。对传统的文件检索来说，常用的就是查全率（Recall）和查准率（Precision），以及结合两者的F1值。2.2.1 查全率（Recall）查全率指检索出的相关文档数与相关文档集合总数的比值。它考查系统找全答案的能力。计算公式如下：2.2.2 查准率（Precision）查准率表示检索出的结果集合中相关文档的比例。它考查系统找准答案的能力。计算公式如下： 2.2.3 F1值查全率和查准率两者相辅相成，从两个不同侧面较为全面地反映了系统性能。F1值是一个把查全率和查准率结合起来的指标。考虑到某些情况下不同系统的查全率和查准率互有高低，不便于直接比较，而使用F1值就可以更直观地对系统性能进行排序。计算公式如下：以上介绍的评价公式仅适用于无排序的检索结果，显然并不适合于依据“相关程度”对文档排序的检索结果，下面介绍几个用于评测已排序的检索结果的评测指标。2.2.4 Precisionrank(d)表示在检索出d篇文档时的查准率。例如，P10表示检索出10篇文档时的查准率，P20表示检索出20篇文档时的查准率等。考虑到用户在查看搜索引擎结果时，往往希望在第一个页面（通常为10个结果）就找到自己所需的信息，因此设置了这样一个拟人化的指标，P10常常能比较有效地反映系统在真实应用环境下所表现的性能。2.2.5 AP (Average Precision)平均查准率，是指平均每篇相关文档被检索出来时的查准率。计算公式如下：()其中，NumR表示在某一个单一查询主题的相关文档数；d表示返回结果中的一篇相关文档；rank(d)表示文档d在返回结果中的排序，也即在该篇相关文档被检索出时，共检索出的文档数；NumB表示在文档d之前（含文档d）相关文档的个数。是一个单值指标，它反映了系统在全部相关文档上的性能。2.2.6 MAP (Mean Average Precision)MAP是查询主题集中每个查询主题AP得分的平均值。2.2.7 Expected MAP当只有部分文档被进行相关判定的时候，Expected MAP是衡量系统性能的一个良好指标。公式中的概率p表示文档是否相关，1代表相关，0代表不相关，0.5代表未判断。i是文档编号，t是查询主题编号。2.2.8 R-Precision单个主题的R-Precision表示检索出R篇文档时的查准率，其中，R表示单个主题的相关文档数。主题集的R-Precision是每个主题的R-Precision的平均值。2.2.9 MRR (Mean Reciprocal Rank)RR是第一个正确答案出现位置的倒数，MRR是多个主题的RR的平均值。一般来说，不同的评测项目会根据自己特殊的需求采用不同的评测指标。除了上述主要评测指标，还有其它的评分方式，例如bpref 13等。第三章 评测集的构建随着网络与信息资源的飞速发展，网络搜索引擎已经成为人们获取网络信息的主要途径。实验室背景下的信息检索研究的主要目的是为现实中的用户提供一个更强大，更智能，更精准，更人性化的搜索系统。信息检索的评估包括三个方面：文档集、评测集和评测手段。我的毕设任务主要是为参加评测的系统建立一个能够有效检测出他们性能的评测集。如果说评测是一次考试，那么评测集就是试题。评测集是一次评测活动的前提，再优秀的检索系统如果面对一张充满偏题怪题的试卷，也可能打零分；但是如果考题全部都出的很简单，就像没有任何区分度的卷子，人人都能得高分。评测集要尽可能代表真实Web用户的信息需求。以往的SEWM评测是以查询主题集的形式出现的，每年都会构建一些新主题，从开始到现在，TD主题编号已达到258和HPNP主题也已经达到1,185，其中HP, NP主题各占一半。并且为了使得主题的描述方式等方面具有一定程度的一致性，主题集每年都会由专门的人员来构建。图 4 搜狗分类目录首先确定计划构建的主题数目，平均分配给构建人员。同时将主题划分成多个领域类别，划分类别参照了搜狗的网页分类目录(/dir), 将类别大致分为“娱乐”，“文学”，“新闻”，“科学”等等。通过研究分析搜狗用户日志所记录下来的用户搜索情况，我们可以看到这样几种特点：图 5 搜索引擎用户行为流程1. 实验所使用日志包括搜过搜索引擎在2007年03月的日志3.9G。其中非空查询为44,430,803个，含非重复查询共4,580,853个，仅出现一次的查询有1,613,501，占不重复查询的约35%，占全部查询的3.63%. 查询次数在十次以下的查询有4,153,437个，占到非重复查询的90.7%. 这些次数数据，说明不同用户之间的查询还是比较独立的。图 6 搜狗日志点击分布图 7 实验数据的点击分布图 8 搜狗日志检索词长度分布图 9 实验数据检索词长度分布从图8与图9用户日志与实验数据的检索词长度分布图中可以看出，日志的分布比实验数据的分布要陡峭很多。观察图8可以看出，当检索词的长度大于10的时候，其数量相对较少，所以在实验编程的时候，我把长度大于10的都归为一个集合。否则对存储空间的需求太大，导致程序效率降低。检索词频率分布的横轴代表分类出现次数，纵轴代表出现的检索词个数。其中类别1代表只出现一次的检索词的个数，如下表所示：类别所代表出现次数1出现一次2出现2-4次3出现5-9次4出现10-19次5出现20-29次6出现30-39次7出现40-49次8出现50-100次9出现100次以上表格 1 检索词频率的重新分类图 10 搜狗日志检索词频率分布图 11 实验数据检索词频率分布2. 查询长度主要是指用户提交的查询中包含几个词语或者字，这是用到了天网的切词工具产生的数据。经分析共有147,537,659个词，平均每个query长度147,537,659/44,430,803=3.323. 点击次数与结果排名之间的关系：用户提交一个查询后，搜索引擎可能会返回很多页结果，但是并不是所有结果都会对用户有用，所以用户不会将所有的结果都点击浏览。通过点击次数图6可以看出，96%用户只翻看搜索引擎返回结果的前10个，即返回结果页面的第一页。这个用户行为特点决定了尽管搜索引擎返回的结果数目十分庞大，但真正被绝大多数用户浏览的结果，只有排在前面很小的一部分而已。所以传统的基于整个结果集合的查准率和查全率的评价方式不再使用于网络信息检索的评价，我们需要着重敲掉在评价指标中有关最好签结果文档与用户查询需求的相关度的部分。针对以上特点，经讨论决定采取抽样的方法来构建此次检索任务的查询集。但是该查询集的构建又不是随机的，需要满足基础查询集的特征。下面给出搜狗用户检索日志的格式，并解释说明初步查询集产生的机制。系统时间用户ID检索词结果所在页面点击结果次序结果URL表格 2 用户日志格式系统时间是指搜索发生时系统记录下来的时间，这条信息有助于我们判断session搜索情况，一个session是指同一个用户在某一小段时间内的连续查询。用户ID是搜狗搜索引擎利用cookies中的信息标识不同的用户。检索词就是查询关键词。结果所在页面是指用户所点击的检索系统返回的某网页链接所在的位置，即是在全部搜索结果的第一页、第二页或其他。点击结果次序是指用户点击的检索系统返回的某网页链接是该次查询中的第几次点击。比如说用户搜索“北京大学”，先点开了北京大学主页, 之后又点开了北京大学信息科学与技术学院的主页, 那么信科主页的的点击结果次序项就应该对应显示2。结果URL就是用户点击网页的网址。3.1 初步筛选过程图 12 查询集初选流程图首先，统计检索词的分布特征。通过对检索词不同方面的研究分析，并且考虑到信息的有限性，我们重点考虑了3个分部，即长度分布、频率分布以及点击次数分布。长度分布是指搜索词在天网切词软件操作之后得到的每一个query的长度，query长度在10一下的检索词，每个长度单位算作一个单独的集合，长度大于等于10的检索词算作一个集合。频率是指日志中被搜索过一次、两次n次的query的集合，具体的集合划分方法如下：解释：counts是在统计文件中输出的查询词x所出现的频率，有很多查询词出现的次数很高，因此直接运用其频率不是很方便，所以很据出现频率的大小对其进行分类在此是记录某一频率段出现的查询词的个数图 13 频率分布统计代码点击的次数是指，对于一个查询，当检索系统返回了结果，用户点击结果的条数。利用日志上的“点击结果次序”那一项所带来的信息。当遇到同一个检索词时，如果新的“点击结果次序”大于旧的，那么覆盖。其次，根据分布特征采样，使得初步筛选结果符合网络的真实属性。图 14 采样代码再次，利用三维集合把搜索词分类，并根据上一步的限制条件来随机采样查询词。三个参数的循环，分别代表了查询词的三个分布属性把查询词依照属性值分配到不同的集合中，其中一个词只可能在/一个集合中出现设置随机种子，即将在不同的集合中随机采样。虽然是随机采样，但该算法仍可以保持查询词特征本来的分布，是因为有timesxyz变量的限制，其规定了在集合recxyz随机取词的次数。图 15 筛选主要代码3.2 定义有区分性的检索词信息检索系统评测取决于评测集，评测集包括三个重要的元素：查询主题、文档集、相关文档集。理想的评测方法应该使