【毕业学位论文】（Word原稿）一种构建信息检索系统评测集的方法

本科生学位论文 题目： 一种构建信息检索系统评测集的方法 姓 名： 学 号： 院 系：信息科学技术学院 专 业：计算机科学 导 师： 教授 二零零九年五月 摘要 随着互联网的飞速发展，信息检索技术在实际生活中的作用越来越重要，在学术界也引起了研究学者 的重视。参考国外测试集的构建经验，天网实验室 构建了大规模中文网页信息检索测试集 组织了 文网页检索评测，希望在国内外各个研究小组的共同参与下建立并完善 起推动中文 网页信息 检索技术的发展。 测试集是信息检索评测的一项决定性因素之一。测试集包括查询主题集、文档集和相关文档集。查询主题集可以从网络日志中获取抑或由人工设定；文档集是信息检索系统返回的检索结果的集合；而相关文档集是对应相应的查询主题相关的文档的集合，一般相关文档需要人工进行判断，由于文档集的规模都不小，而相关文档集是文档集的 子集，建造其工作量巨大，甚至有可能难以实施。所以我们想 尝试得出判断两个信息检索系统孰优孰劣最小的工作量，及所需的最小查询主题集和相关文档集。 本论文通过变形 式的表达方式，研究其与相关文档集的关系，说明了在给定查询主题的情况下，如何找到最小的相关文档集，并作实验加以证明。 结合查询主题和相关文档集合，利用 得两个集合共同最小化。 关键词 ： 信息检索，评测，测试集，文档集，查询主题，相关判断，最小相关文档集，算法 A is a in s it a by a is eb on a is of in it of of to be or by in of of of of is at at In we to up an in an as as We a of on of a of is on be as P ( we to a is at R in a of an 录 摘要 . 2 目录 . 5 表目录 . 6 图目录 . 7 第一章 引言 . 8 究背景 . 8 文主要贡献 . 9 文组织 . 10 第二章 相关研究 . 11 试集 . 11 期测试集 . 13 试集 . 14 他测试集 . 16 测标准 . 16 全率（ . 16 准率（ . 17 1 值 . 17 d) . 17 P (. 17 . 18 . 18 . 18 . 18 第三章 评测集的构建 . 19 步筛选过程 . 24 义有区分性的检索词 . 27 小评测集 . 28 第四章 评测集的分析 . 31 验过程以及数据 . 31 果分析 . 31 较 . 33 致谢 . 35 参考文献 . 36 表目录 表格 1 检索词频率的重新分类 . 22 表格 2 用户日志格式 . 24 表格 3 式变型举例 . 28 表格 4 以往 测代价 . 31 表格 5 2000 个查询主题 . 错误 !未定义书签。 表格 6 500 个查询主题 . 32 图目录 图 1 信息检索评测示意图 . 12 图 2 程图 . 13 图 3 询主题实例 . 15 图 4 搜狗分类目录 . 19 图 5 搜索引擎用户行为流程 . 20 图 6 搜狗日志点击分布 . 21 图 7 实验数据的点击分布 . 21 图 8 搜狗日志检索词长度分布 . 21 图 9 实验数据检索词长度分布 . 22 图 10 搜狗日志检索词频率分布 . 23 图 11 实验数据检索词频率分布 . 23 图 12 查询集初选流程图 . 24 图 13 频率分布统计代码 . 25 图 14 采样代码 . 26 图 15 筛选主要代码 . 27 图 16 信任程度随判定文档数而增加 . 33 第一章 引言 究背景 长久以来，人们对信息的需求从未间断过 ，自从 20 世纪 40 到 50 年代，人们开始了对信息进行检索的活动。 1945 年 出利用信息技术来解决“使大量信息更容易获取的难题”； 1951 年 次提出了“信息检索（ 的概念 息检索是信息的潜在用户将信息需求转换为一张文献 来源信息列表的过程或方法，而这些文献包含有对其有用的信息” 1。随后， 信息检索技术 蓬勃 迅速 地 发展起来，其研究领域也从最初的科学技术领域扩展到人类活动的各个方面 ，并成为本世纪人类社会的一项重要技术 。 20 世纪 90 年代， 万维网得到了较快的 发展， 信息的获取手段 逐渐 由媒体转向网络，社会信息量由于网络的壮大而变得空前的 丰富 。以搜索引擎为代表的信息检索技术已经取得了巨大的成功，像 百度等搜索引擎已经深入到人们日常学习和工作中，成为获取信息不可或缺的工具。而 息检索技术 也 成为研究者广泛关 注的议题， 如何评测这些检索系统的性能 ，从而有的放矢地提高检索系统的性能， 受到了越来越多的 关注。 信息检索系统诞生以来， 信息检索评测对系统的研究、设计与发展一直有着显著的影响力。通过评测，研究者能够验证系统的效益、比较各种检索技术的优劣，不断改进检索系统，使系统的性能更加完善，能正确引导研究发展方向。基于用户主观使用感受的评测方法不客观、不可靠，所以 评测体系必须客观公正， 不受人主观感觉的影响，并且评测结果通常都成立。一般的，这种评测体系具有以下特点：明确的形式化研究任务、公开的训练与测试数据、公开的评测比较。 早期检索系统评测最著名的研究是 1950 年代末期开始进行的 验 2。它开创了以测试集（ 合评测指标 来评测系统的模式。所谓测试集，是一种在规范化环境中测试系统性能的机制，包括查询问题（ 文档集（ 及相关判断（ 个部分。评测指标则一般采用查准率和查全率。 验首开规范化评测之先河，它的评测模式为后续的评测研究奠定了基础，至今仍占有举足轻重的地位 。 为了促进信息检索技术的发展，美国国防部高级研究项目计划局（ 称 美国国家标准与技术局（ 称 1992 年共同举办了文本检索会议（ 称 3。 过构建大型的测试集，提出不同的评测项目和评测指标等，提供不同检索技术与检索系统之间的标准评测环境。 参加评测单位除了要提交系统的运行结果之外，还可以参加研讨会，与会者可以分享结果。 得了国际性的威望，在信息检索评测领域起到了很好的示范作用。除了 有针对不同语言设计的类似机制开始运作，如欧洲各国联合举办的跨语言评测论坛 4、法国信息技术局构建了法文的 5、日本国立情报学研究所（ 称 办的 测会议 6等等。 反观国内，中文信息处理技术在最近几十年取得了长足发展，但专门针对中文的评测项目的缺乏使中文信息处理技术不能得到有效检验。缺乏大规模的中文测试集是制约中文网页信息检索技术前进的障碍，因此，我们希望在国内外各个研究小组的共同参与下建立并完善以中文为主的网页信息检索测试集 一起推动中文网页信息检索技术的发展 7。 文主要贡献 缺乏大规模的 中文网页测试集制约了中文检索技术的发展，为了改变这种局面，参考 年的成功经验，我们构建了大规模中文网页信息检索测试集 2004 年开始， 在全国搜索引擎和网上信息挖掘学术研讨会 (称 议上 开始举办中文网页检索评测项目，即 文网页检索评测。 网页检索评测主要目的是通过网页测试集研究各种检索技术的优劣，以改进检索系统在真实网页环境下的性能。 2009 年的评测任务有一，海量查询任务 。该任务是模仿 2007和 2008 年的 给予检索系统大规模的查询集进行测试。 因为我们发现，很多研究机构都做了类似 测检索系统的实验，构建了一些测试集，但这些早期的测试集规模通常较小，与真实的检索环境之间存在着较大差异。基于这样的测试集所开发的检索系统，在实际应用中往往受到极大的限制。这些测试集存在两个根本缺陷：一是缺少在相同的测试数据上使用相同评测方法的跨系统公开评测；二是缺少真实的大规模测试集。 本文在信息检索评测领域主要有如下贡献： 1. 构建并实施了海量 中文网页信息检索测试集 2. 探索能够评测检索信息性能的最小查询主题和相关文档 集合的方法 文组织 本文第一章介绍了本文的研究背景及本文主要贡献 ；第二章是相关研究，介绍了信息检索评测中的测试集 及 常用的 评测指标等；第三章介绍了中文网页信息检索 海量查询任务测试集的构建方法， 详细介绍了文档集、查询集和相关文档集的构建过程及构建结果 ，同时还有通过检索结果来寻找最小查询集和相关文档集的方法 ；第四章对 评测集以及 实验数据进行了分析 ； 最后一章是本文的总结和工作展望。 第二章 相关研究 自计算机信息检索问世以来 ，信息检索评测就被赋予了一种具有同样重要性的角色。在长期的实践中，研究人员已经总结出一些比较合理的评测方法和评测指标，使得检索评测研究的可行性明显增强。系统评测有不同的评测研究类型，例如侧重系统软件功能的功能测试；侧重系统的时间与空间复杂度的系统性能评测等。 信息检索任务的特点是，用户输入的查询请求常常是模糊的，多义的。检索结果往往不是确切的答案，需要检索系统自行对其进行解释，并对检索结果按照它们与查询请求的相关度进行排序。信息检索系统需要对检索结果的准确度进行评测，这种类型的评测叫做检索性能评测（ 在各种类型的评测研究中，检索性能评测是其中的研究重点和核心。 检索性能评测分为实验室评测和真实环境的评测，虽然基于真实环境的评测是一种趋势，但由于实验室在封闭环境下测试的可重复性和可扩展性，实验室评测仍然占主导地位。实验室评测通常基于测试集和一定的评测指标来完成。 本章第一节介绍测试集的概念及几个重要的测试集，包括早期测试集的代表 I、其它几个规模较小的测试集及近年来规模较大且有影响力的测试集 ；第二节介绍常见 的评测项目；第三节介绍常用的评测指标。 试集 研究者为了评测系统性能，通常会进行一系列的实验来验证，而实验所需的测试数据 ，则依据各自的目的而独立构建。 为了使系统能够在统一的测试集上进行验证，出现了很多公开的测试集，如 I、 10， 11， 12， 13测试集 。他们 的存在提高了评测的公平性，但 由于 早期的 测试集规模较小，且同质性 高，在实际运用中存在着较大的限制。 1992 年开始构建大规模的测试集 3，在信息检索评测领域起到了很好 的示范作用。除了 ，已有针对不同语言设计的类似机制开始运作，如欧洲各国联合举办的 语言评测论坛 4，法国信息技术局则构建了法文的 ，日本国立情报学研究所（ 称 办了 测会议 6等，中国 则 于 2004 年 构建中文网页信息检索测试集 。 查 询 主 题 集文 档 集 相 关 文 档 集信 息 检 索 系 统测 试 集检 索 结 果P o o l i n gP o o 判 断评 分 程 序图 1 信息检索评测示意图 信息检索系统 测试集 包括查询集，文档集和 相关文档三个部分。文档集是一组文档的集合，它是检索系统评测的数据基础；查询主题集代表了用户的信息需求，这些主题依据评测项目的需要，可以是一个或一组关键词，也可以是一段描述。一般地，对相关判断有如下假设：对于任何查询主题，它们的相关判断是独立的、客观的，并且不随着时间和空间的变化而改变；相关文档集是对应主题集中主题所给出的一组标准答案的集合，需要评测人员人工相关判断来构建。 整个信息检索评测中的 各个 角色 关系 可以从图 1 中看出来。 参与评测的检索系统必须在统一的测试集上运作，依 据所指定的查询主题，以文档集作为检索的对象，并将测试集提供的相关判断结果视为标准答案，采用合适的评测指标进行检索系统性能的评比。 相关判断在测试集构建过程中是一件相当困难的工作，需要花费巨大的人力物力。早期测试集中的文件数量较小，因此评测人员可以对文档集中的文件逐篇进行判断。但是随着测试集规模的增大，如果针对每个主题都将文档集中的每个文档逐一与其进行相关判断，需要花费的工作是相当巨大的，因此 “ 法 随之而诞生 8. 法的假设是： 1）大多数与查询主题相关的文档会被聚 集在 2）不在 的文档可以视为不相关文档 . 词r u nr u nr u 结 果 取 前 k 个得 到 结 果 取 前 k 个得 到 结 果 取 前 k 个形 成 P o o 2 程图 术的具体实施过程为：针对每个查询主题，在参与评测的检索系统均能提供相关排序的情况下，抽取出各个检索结果的前 k 个文档，将这些结果合并形成一个集合，去除集合中的重复文件后，得到相关文档候选集（ 再由相关判断人员进行人工判断，最终得到相关文档集。对每个查询主题都需要构建一个 的 文档按照文档编号排序。 法利用不同的检索技术与系统，缩小了相关判断的范围，可以大大减少相关判断人员的工作量。 期测试集 试集是早期比较具有代表性的测试集， 他的实验标志着检索系统评测与测试集的标准模式 的形成 。 验分为前后两期，由 别在 1957 年及 1966 年完成。 I 测试集 2包括文档集、查询问题和相关判断三个部分。I 实验搜集了 1,400 篇有关太空动力学的文章，并请每位作者根据这些 文章与当时研究的主题来提出问题，经过筛选后产生了 200 多个查询问题。 I 测试集中相关判断的构建有如下四个步骤：首先请查询问题的构建者对文章后所附引用及参考文献进行相关判断；然后请五位该领域的研究生将查询问题与文档集中的每篇文章逐一进行相关判断，共用了 1,500 个小时进行了 50 万次以上的相关判断，希望能找出所有的相关文档；为了避免上述过程中出现遗漏， 利用文件耦合技术计算了文章之间的相关性，发现更多可能的相关文档；最后对以上找出的所有文档，一并送回给原作者进行判断。 I 的主要目的是比较 33 种不同检索方式的检索效果，系统的目的是检索出相关的文档，拒绝不相关的文档，因此采用了查全率和查准率作为评测指标。 I 相关判断采用的方法比较全面，构建的答案集比较完整。 继 试集之后，又出现了很多的测试集，如 10， 11， 12， 13，它们的构建各自针对着不同的测试目的和测试对象，存在不同的组织构架方式。这些早期测试集存在规模较小、文档集的同质性比较高等缺陷，与真实的检索环境存 在着较大的差异，因此在这些测试集上评测的结果受到许多质疑 9。 1980 年后陆续出现的一些测试集如 ，虽然 规模稍大，但大体来说仍然与早期测试集相似，也存在着上述的缺陷。 试集 文本检索会议 （ 的简称，由美国国防部高级研究项目计划局和美国国家标准与技术局于 1992 年共同发起举办的 。 一个程序委员会管理，它的核心评测项目 是 ad 还有些特殊的评测项目，每个评测项目都有独立的评测程序和评测指标 。 年度为周期运行，它有一套非常规范的程序，包括筹备工作、公布评测项目和评测规范、邀请研究部门参加评测、参加者返回检索结果、工作人员进行评测、送回评测结果、举办年度会议等程序。与会者可以讨论信息检索系统的优缺点、探讨新的信息处理技术等。 引了越来越多的国家和地区的研究人员的积极参与，在信息检索领域的影响力越来越大，成为了国际文本检索领域最具权威性的评测活动，极大地推动了信息检索技术的发展。 测机制基本上是按照 验的评测模式扩展而来的，因此 试集也包含文档集、查询主题集及相关判断三个部分。 T R E C - 2 0 0 3 查 询 主 题 示 例N u m b e r : 0 8 0S c i e n c eD e s c r i p t i o n :F i n d k e y g o v e r n m e n t w e b s i t e ( r e p r e s e n t e d b u y t h e i r h o m e p a g e ) o n t h e s u b j e c t o f S c i e n c e 图 3 询主题实例 档集主要是英文，也有部分的非英文文档集 。 主要是新闻性文件，也有一些其它的杂志期刊。 力于构建大型的测试集，所以文档集的规模随着评测活动的持续进行越来越大。从最初的几百 20 试集时规模已达 426方便 档集中的文档一般采用标准通用标记语言 进行简单标记。大多数文档都包含有文档编号 档内容 类型的通用字段。 询主题 以结构化的形式来呈现，常常含有多个以 不同的角度陈述主题 的域 。 有 150 个查询主题，之后 0 个新的查询主题，将 它们顺序 编号。查询主题的描述形式也会随评测的需求不同而有微小变化。 询主题的域比较多，多达 10 个，主题的描述比较详细且结构比较复杂。研究者 提交给检索系统的查询词 时，可以从查询主题的各个域中组合构建。 查询主题结构过于复杂，因此 化了主题的描述形式，保留了三个域，即 ， 但是这样的描述相对于用户的检索需求还是有些复杂，所以 题缩得更短，只剩下了 。通过 实验结果，发现只有的主题描述无法达到预期的效益，并导致了一 些处理上的困难，所以 改为与 似的形式，之后的变化都不大。 用的是二元化的相关判断方式，即将所有文档分为相关与不相关两个层次，一篇文档或者与主题相关，或者与主题不相关。相关判断采用了 法来辅助完成。 他测试集 跨语言评测论坛 2000 年开始举办，是欧洲的学者专家合作建立的评测机制。该论坛侧重于欧洲范围内跨语言检索问题的评测，为研究跨语言检索技术的学者们提供了一个交流的平台。同 评测机制相同， 在很多评测项目的执行委员会来负 责某个评测项目。 测会议是由日本国立情报学研究所（ 称 办的，自 1999 年开始筹办。它的目的是建立一个日文标准测试集，同时它还研究亚洲语言的跨语言检索问题，比如日语、中文、朝鲜语等，此外，该会议还包含其它的评测项目，如专利检索、问答检索、自动摘要等，作为亚洲地区较重要的信息检索评测机制，受到国际上信息检索研究者的重视，参与的国家、地区和机构持续增长。 文档集主要来源于 术会议论文资料库中的摘要与关键词等资 料，它的查询主题也是以类似于 主题格式结构化组织起来的，相关判断同样采用了 法，主题与相关文档间的相关度分为三个层次：相关、部分相关和不相关。 测标准 信息检索 中使用的 评测指标直接关系到 检索策略 的最终 评测结果 ， 所以检索系统的评测应根据评测重点选择合理的评测指标。 在长期的评测实践中，研究人员已经总结出一些比较合理的评测指标。 假设在一个文档集上，有查询请求 I 和与其相对应的相关文档集 R， 设集合 R 中文档的个数。给定一个检索策略，它处理查询请求 I，并返回一个结果文档集 A，设 集合 A 中的文档个数。同时，设 文档集 R 和 A 的交集， 集合 个数 。 对传统的文件检索来说，常用的就是查全率 （ 查准率（ ，以及结合两者的 。 全率（ 查全率指检索出的相关文档数与相关文档集合总数的比值。它 考查系统找全答案的能力 。计算公式如下： u u m 准率（ 查准率表示检索出的结果集合中相关文档的比例。它 考查系统找准答案的能力 。计算公式如 下： u mp r e c is io n N u m 1 值 查全 率 和查准 率两者相辅相成，从两个不同侧面较为全面地反映了系统性能。 是一个把 查全 率和 查准 率结合起来的指标。考虑到某些情况下不同系统的 查全 率和 查准 率互有高低，不便于直接比较，而使用 就可以更直观地对系统性能进行排序。 计算公式如下： 2 P r e c is io n R e c a r e c is io n R e c a 以上介绍的评价 公式仅适用于无排序的检索结果，显然并不适合于依据“相关程度”对文档排序的检索结果，下面介绍几个用于评测已 排序的检索结果的评测指标。 d) 表示在检索出 d 篇文档时的查准率。例如， P10 表示检索出 10 篇文档时的查准率， P20 表示检索出 20 篇文档时的查准率等。 考虑到用户在查看搜索引擎结果时，往往希望在第一个页面（通常为 10 个结果）就找到自己所需的信息，因此设置了这样一个拟人化的指标， P10 常常能比较有效地反映系统在真实应用环境下所表现的性能。 P (平均查准率，是指平均每篇相关文档被检索出来时的查准率。计算公式如下： 1 ( ) p r e c i s i o n r a n k dN u m ( ( )()BN u mp r e c i s i o n r a n k d r a n k d) 其中， 示 在某一个单一查询 主题的相关文档数 ； d 表示返回结果中的一篇相关文档； d)表示文档 d 在返回结果中的排序，也即在该篇相关文档被检索出时，共检索出的文档数； 示 在文档 d 之前（含文档 d）相关文档的个数。 是一个单值指标，它反映了系统在全部相关文档上的性能。 查询主题集中每个 查询 主题 分的 平均值。 1 ( )| t i i i i j i jt t i j P A P c p c p 1m a x ( ) , ( ) r a n k i r a n k j当只有部分文档被进行相关判定的时候， 衡量系统性能的一个良好指标。公式中的概率 p 表示文档是否相关， 1 代表相关， 0 代表不相关， 表未判断。 i 是文档编号 ， t 是查询主题编号。 个主题的 示检索出 R 篇文档时的查准率，其中， R 表示单个主题的相关文档数。 主题集的 每个主题的 平均值 。 第一个正确答案出现位置的倒数， 多个主题的 平均值。 一般来说，不同的评测项目会根据自己特殊的需求采用不同的评测指标。除了上 述主要 评测指标， 还有 其它的评分方式 ，例如 13等。 第三章 评测集的构建 随着网络与信息资源的飞速发展，网络搜索引擎已经成为人们获取网络信息的主要途径。实验室背景下的信息检索研究的主要目的是为现实中的用户提供一个更强大，更智能，更精准 ，更人性化的搜索系统。信息检索的评估包括三个方面：文档集、评测集和评测手段。我的毕设任务主要是为参加评测的系统建立一个能够有效检测出他们性能的评测集。如果说评测是一次考试，那么评测集就是试题。评测集是一次评测活动的前提，再优秀的检索系统如果面对一张充满偏题怪题的试卷，也可能打零分；但是如果考题全部都出的很简单，就像没有任何区分度的卷子，人人都能得高分。 评测集要尽可能代表真实 户的信息需求。以往的 测是以查询主题集的形式出现的，每年都会构建一些新主题， 从开始到现在， 题编号已达到 258 和 题 也已经达到 1,185， 其中 题各占一半。并且为了使得主题的描述方式等方面具有一定程度的一致性，主题集每年都会由专门的人员来构建。 图 4 搜狗分类目录 首先确定计划构建的主题数目，平均分配给构建人员。同时将主题划分成多个领域类别，划分类别参照了搜狗的网页分类目录 (), 将类别大致分为“娱乐”，“文学”，“新 闻”，“科学”等等。 通过研究分析搜狗用户日志所记录下来的用户搜索情况，我们可以看到这样几种特点： 信息检索系统用 户建 立 / 修 改 查 询浏 览 查 询 结 果结 果 满 意 ？查 询 结 束5 搜索引擎用户行为流程 1. 实验所使用日志包括搜过搜索引擎在 2007 年 03 月的日志 中非空查询为 44,430,803 个，含非重复查询共 4,580,853 个，仅出现一次的查询有 1,613,501，占不重复查询的约 35%，占全部查询的 查询次数在十次以下的查询有 4,153,437 个，占到 非重复查询的 这些次数数据，说明不同用户之间的查询还是比较独立的。 04000008000001200000160000020000001 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49图 6 搜狗日志点击分布 0500100015002000250030003