中国电信黄页搜索引擎系统的测试和评估

胡运发  陶晓鹏  王政华  杨笑天

（复旦大学信息科学与工程学院  上海200433）

摘  要  本文详细说明了复旦大学开发的黄页搜索系统的评测结果。首先阐述了国内外的相关组织和它们制定的标准，讨论了各种测试模型的特点，提出了本系统采用的评测指标和计算公式。然后，介绍了评测数据的建立方法。最后，给出了复旦大学黄页搜索系统的各项评测结果，并将它们与百度的测试结果进行了对比，说明了本系统是一个优秀的黄页搜索系统。

关键词  系统评测  准确率  召回率  遗失率

1  测试模型的建立

信息检索系统的评测标准一直以来都是非常具有争议性，同时也非常重要的一个课题。当前信息的异构、分散、海量等等特性既对检索技术提出了更高的要求，同时也给系统评测方法增添了很大的难度。显然，基于主观使用感受的评价既不客观也不可靠，有必要发展出一套客观的评测体系，使得评测能够不受个别人主观感觉的影响，同时所做出的评价具有普遍适应性。定性地来说，这种评价应该具有如下特性：明确的形式化研究任务、公开的训练与测试数据以及公开的评测比较。

早期常用的评测指标包括准确率（Precision）、召回率（Recall）、F1值等，可以用一张简单的图（如图1）来表示各种数据的关系：

图  1

其中

文件集合（Collection size） = A+B+C+D

相关文件（Relevant） = A+C

获取文件数（Retrieved） = A+B

各种指标如下所示：

准确率（Precision）= A / (A+B)

召回率（Recall）= A / (A+C)

遗失率（Miss）= C / (A+C)

误识率（False alarm 、fallout) = B ÷ (B+D)

形式化地来讲，

P值：pi=l i/mi，其中mi是经分类系统输出分类结果为第i类的文档个数，li是其分类正确的文档个数；

R值：ri=l i/ni，其中ni为所有测试文档中，属于第i类的文档个数，li是经分类系统输出分类结果为第i类且结果正确的文档个数；

这两个值虽然能够算出大致上的结果，但是各有偏重，前者偏重于结果中有尽量多的有用信息，为此可能不惜牺牲一部分相关数据；而后者则倾向于尽量找出所有相关文件，即便因此而参杂如很多垃圾信息也在所不惜。在这种情况下，引入了将两个数据结合的F值和E值。

F值为召回率R和正确率P的调和平均值，若P=0 或者R=0那么F=0，否则，

（1）鼓励对基于大测试集合的信息检索方法的研究；

（2）提供一个可以用来交流研究思想的论坛，增进工业界、学术界和政府部门之间的互相了解；

（3）示范信息检索理论在解决实际问题方面的重大进步，提高信息检索技术从理论走向商业应用的速度；

（4）为工业界和学术界提高评估技术的可用性，并开发新的更为适用的评估技术。

TREC发展到现在，已经成为备受瞩目的标尺性测试，对信息检索研究领域产生了巨大而深远的影响。现在的众多评测，甚至其他研究领域的评测，如跨语言检索评测会议NTCIR、CLEF，机器翻译评测TC-STAR等，都或多或少受到它的影响。

就国内而言，随着中文信息处理数据规模的膨胀以及国内外学术交流的增加，国内研究者迅速认识到评测对于研究的促进作用，很多研究机构也开始尝试参加TREC等国际评测。不过，由于中英文评测的巨大差别，TREC往往不能够对中文信息处理技术进行有效的检验。为此，国内相继召开了多个面向中文信息处理技术的评测会议，其中比较有影响的863评测、全国搜索引擎和网上信息挖掘会议（SEWM）等。这些测试基本上以MAP、R-Precesion和P(n)为基本指标。

（1）平均准确率（Mean Average Precision，即MAP）：单个主题的MAP 是每篇相关文档检索出后的准确率的平均值。主题集合的MAP 是每个主题的MAP 的平均值。MAP 是反映系统在全部相关文档上性能的单值指标；

（2）R-Precision：单个主题的R-Precision 是检索出R 篇文档时的准确率。其中R 是测试集中与主题相关的文档的数目。主题集合的R-Precision 是每个主题的R-Precision 的平均值。

（3）P@X：P@X 是系统对于该主题返回的前X 个结果的准确率。考虑到用户在查看搜索引擎结果时，往往希望在第一个页面（通常为10个结果，在本系统中就是10个）就找到自己所需的信息，因此设置了这样一个拟人化的指标，P@X 常常能比较有效地反映系统在真实应用环境下所表现的性能。

这次测试基本上以TREC的测试样式为基本点，并在此基础上进行了一系列适用于黄页信息检索系统的修改。同时，为了全面、准确、公正地对比结果，本项目从各种角度进行了测试用例的设计，并将多种测试的评判技术加以结合，综合考虑。

（1）在单个测试用例方面，采用通用的用例设计方法，内容除了基本的被测试系统模块名称、版本信息之外，关键的几项有：

①查询条件（Topic）：用来模拟用户的搜索需求，由多个单个关键字组成，少数含有多个关键字；

②查询范围（Scope）：用来指明搜索的对象，这一点在黄页系统中尤其需要注意，因为系统数据库以城市分布，如果搜索双方所用数据库的地域、或者更新日期不一致，则测试结果无效；

③描述（Describe）：用来对查询结果进行描述，需要记录“总结果条数”和“有效记录条数”两个数据，以“有效记录条数/总结果条数”的格式记录，如示例中的1/120；

④引用（Reference）：用截图的方式指明错误；

⑤评述（Comment）：评述有三个部分，两个部分分别对Baidu、黄页搜索结果进行评述，一般用来指明错误的类型，如果没有错误，则指明“正确”，第三部分用来填写对双方对比的一些评述，比如解释为何两种搜索引擎会出现这些不同；

⑥相关文档数目，这里填写所有相关文档的数目，它的值是百度和黄页系统找出的所有正确结果的交集，大部分情况下，它都是两者的正确结果中较大的那个，如下面的例子中，百度的正确结果“利工塑料制品厂”就包含在黄页搜索引擎的结果中。但也有小部分情况两者的交集比双方的正确结果数目都大，这个参数的设置是为进行精确的结果评测，具体解释请参见本文后续内容。

⑦位置（Position）及相关性（Relevant），采用“位置-相关性”的格式。所谓的位置是指搜出的有效结果在所有结果中的位置，这一点是在后续的测试中较为重要，这种结果对于MAP和P@X的结果都会有很大的影响。原因也是显而易见的，毕竟结果在第一位出现和在第100位出现，两者的效果是完全不同的。同时要记录的是在某个位置出现的那个结果所具备的相关性，可能的选值范围为：（0.6，0.8，1.0）。我们将会详细介绍相关性的评定。就直观的理解而言，显然是相关度高的应该排在更前面。这两点是非常难以办到的，很多搜索结果的长达数百项，要一一记录搜索结果、位置，相应的相关度是一件非常乏味的工作，并且很容易出现错误。而在这个方面，采用计算机自动记录的方式又是无法接受的（显然如果能够用程序鉴别，就能够用程序来处理）。

示例请参见图2。

图  2

（2）对于搜索结果正确与否，也需要一个公认的评测标准，要求我们确认搜索结果同搜索对象是否相关，这事实上涉及一个在信息检索中非常常见的问题：信息检索相关性问题。亦即如何用较为公正、准确、可重复的方式来确定搜索结果和搜索目标是否一致。这一点同“匹配（Match）”是大有不同的，后者只是确认搜索中出现了对象，而前者则是属于信息相关的概念。

如查询“锁店”，我们基本上可以确认用户的意图是要搜索“经营与锁相关的公司”，而“连锁店”虽然出现了搜索目标，但是信息相关度很低，可以认为是一个错误的结果。但如果搜索的结果是“电信”，则很难说用户想要查询的是“电信公司”抑或“电信大楼”。这就是前文所说的“组合歧义”问题。虽然依据最优化的查询方式，用户应当选择高级搜索，并在“地址”中选择“电信”，但是根据TREC的标准，进行主观上的相关度评价是不公平的。查询发起人在背景（Context），论域（Scope）、情境（Situation），意图（Focus）等方面的差异往往造成对相关性判断的极大不同。

事实上，当前学术界对相关性的确认仍然停留在“直觉概念”的层次，很难归纳出一个量化的标准来，即便是公认较好的理论框架仍然只能进行一些定性的帮助，而难以量化为程序。在本次测试中，我们以Saracevic在1996年提出的相关性概念为基础，加上了Mizzaro在1998年对该概念的一些改进。同时，因为本系统针对的是比较固定的内容――公司信息，因此，在测试的信息相关性检验标准中，做了适当的修改，最后得出了以下几条可用来确定相关性存在的指导性规则：

①算法相关（或者叫系统相关System pertinence），系统以逻辑或统计原则对文档及查询进行相似性比较得出的，因此属系统角度相关。基本上以切词为原则，简单说来就是依据同样的切词原则的单个词中包含搜索目标，这是最高的一种相关度，在测试中，我们定义这种相关度值为“1”。

②主题相关（Topicality pertinence），是在文档和查询各自的主题之间的比较一致，比如说查询“宠物医院”，如果搜索出来“动物诊所”，这属于基于普遍理解的相关性，虽然没有关键词，相关度没有第一种高，但是仍然属于高相关性，应该提供给用户，在测试中，我们定义这种相关度值为“0.8”；

③认知相关（Cognitive pertinence），代表信息课题符合用户的认知需求。目标是否具有相关性，很大程度上取决于用户的知识状态，这一点很难确定，但是基本上，如果用户查询“轧钢厂”，结果为“钢铁公司”，我们就认为这是一种认知相关，这是较弱的一种相关，需要专业的知识才有可能理解这种相关，从蛛丝马迹中找出两者的联系，相关度较低，在测试中，我们定义这种相关度值为“0.6”；

④动机相关（Focus pertinence），相关性判断的直接意义是被检索出的文档是否“满足需求”；判断的结果往往以是否“成功”、“满足需要”、“完成检索任务”为标准。这一点同样是难以确定，如在本次测试中，查询“美味”，出现了“美味饭店”、“美味食品”无疑是准确结果，但是“锦江饭店”算不算一个命中则有待商榷，在本次测试中忽略这种相关，因此定义这种相关度值为“0”；

⑤时间相关（Time pertinence）和情境相关（Situation pertinence），这两种相关分别代表用户某次查询中是否于当前时间、情境吻合，如查询“枪击事件”，用户若在2007-4-22查询，则最大的可能是需要获取热点的韩国籍男子在弗吉尼亚大学枪杀32名学生的新闻，这一点同黄页系统关系不大，故此没有列入参考范围，而相关度同样设置为“0”。

这种基于分类的定义相关度的方法具有一定的局限性，但是，在黄页系统这个较为特殊的信息检索领域，应该是比较适合的。传统的相关度检测模型基本上都是基于统计的。如清华大学2005年、北大2006年的863信息评测都采用了这种模型：如下面的这个模式就是清华大学在2005年参加863评测时所采用的，最后的评测显示该算法具有相当不错的结果。

（其中k1, k3, b都是常数，默认值可设为：k1=1.2, k3=1000, b=0.75；df：出现该term的文档总数；N：集合中文档总数；len：文档的长度；avg_len：整个集合的平均文档长度，即，文档总长/文档总个数；tf：term出现在某一个文档中的词频TF值，wp下标表示词对出现的词频；qtf：该term出现在查询中的频度值）。

从算法中可以看出来，最终结果的统计依赖于词频、文档长度、词对出现频率等值。而在黄页系统中，在公司名称、地址等结构化字段，这些数据至多只可能出现一次，意义不大，而在公司简介、经营范围字段，内容同样是精简为主，不太可能出现大段的描述，你很难想象一个公司的简介中连续几次声称自己是“五金店”。所以，这种同统计紧密挂钩的算法在本系统中很难有施展的余地。事实上，一般而言，一篇文章越长基于统计的相关度确认就越准确。反之，像黄页系统中公司信息这种短小精悍的文章，则很难保证其准确性。

（3）前文所述的各种检测标准都是根据TREC或者863评测所给出的标准数据集所作的。这些集合在设计的时候已经给出了被索引内容，某个主题检索的正确结果数目等重要内容，是一个已经标准化的检测集合。若单独作为一个搜索引擎，互关联后继树系统也可以采用这种标准化的检测方式来进行，但是，作为一个专门行业适用的黄页信息检索系统，若采用这种系统则显然无法体现对这个行业的特点所作的各种优化工作。

在这种情况下，必须要适用黄页公司本身自带的数据才能够真实的反映问题。然而，黄页公司信息系统作为一种行业搜索，在国内刚刚起步，并没有相应的、已经被组织好的标准检索库，我们手上只有黄页公司给出的标准数据,也就是说，在上文中“A + C”的数目是不可知的。这样，为了能够较好地进行同Baidu的比较，有必要修改前文中的评测公式。

其中，对于准确率（P值）、召回率（R值），最重要的一个值就是确切的正确值数目，对于一个项目组而言，遍历数据库来找出所有正确值是不可想象的。在这里，我们设置Baidu和黄页系统搜出的所有正确值的集合为其正确集合。我们在上面的测试用例中可以看到这一项“相关文档数”，就是为了这个目的。我们在所有值的前面加“B”代表百度结果，加上“H”代表黄页结果，则上文中的测试公式就变成：

BR = BA / (BA ∪ HA)

HR = HA / (BA ∪ HA)

同时，在某些情况下，很可能根本无法搜索出有效结果，这时候，如果仍然采用这个算法，则会出现0除以0的尴尬场景。这时候，有必要定义：

如果 | BA ∪ HA | = 0，则BR、HR都等于0（这个时候，显然BA、HA都等于0）

同样，对于更为复杂的MAP，也有必要做相应的修改。首先，有必要详细描述MAP的原始算法。MAP是AP（Average Precision）的算术平均值。

对于某一个查询Qi，其平均查准率计算公式为：

其中j表示排序的数字，M是检索到的文档总数目，Precision(j)是前j 个检索到的文档的查准率，pos(j)是一个0-1 函数，如果排在第j 个文档是相关的，其值为1，否则为0。这样平均查准率的均值MAP 的计算公式为：

这种算法最大的特点是将不像准确率和召回率一样仅仅局限于某一个数据，而是既考虑了检索结果的覆盖度，同时也对检索结果的排序情况进行考虑。当然，这里也有一个缺点，就是在该测试标准中，我们只考虑搜索的结果是否相关，至于相关度是多少则不予考虑（Pos（j）的值只有0、1）两种可能。当然，也可以对这种算法重新组合，加入相关度的元素，将公式改成为：

其中relevant(j)是一个相关度函数，表示第j个结果的相关度，取值范围从0到1。然而，如果利用了这个函数，则又出现了上文中所说的“相关度”量化问题。在本实验中，将上文所述的第一类相关度，算法相关（系统相关）的相关度设置为1；第二类相关，主题相关的相关度设置为0.8；而最后一种相关的相关度设置为0.6；其他内容的相关度则一概设置为0。这种设置虽然仅仅是基于分类的简单相关度评判，但是对提高最后的结果毕竟有一定的效果，而relevant(j)函数的取值范围变成为：0、0.6、0.8、1这四种。

有了这一点还不够，对于一个搜索结果而言，在第一页的显示结果同第100页的显示效果显然是不同的。所以，如果前10页的相关度都只有0.1，而最后10页结果的相关度却都是1，这个结果远远没有同反过来的效果那么好，这样，公式的相关度又必须同该检索结果的位置相结合。公式于是成了：

Position（j）就是检索结果j的位置，而P则是一个关于“显著程度”的递减值，不妨设置为20，这样，前20条数据的显著程度为1，20到39条的显著程度为0.5，以此类推。

再加上前面解释的关于全部相关文档的数目问题，则最后“同Qi相关的文档数目”用(BA ∪ HA)表示，则公式最终变为：

（4）需要注意的是，对大多数用户而言，搜索的结果也只有前30个有作用，如果是按照10条结果每页的显示格式的话，用户一般只看到前3页就失去了耐心，即使后面包含正确的结果，用户也不太可能去进行检测了，这就有必要提供一个检测标准，来展示用户所注意的那一部分数据的准确率。从TREC标准来看，这就是前文所描述的P@X检测指标。也就是说，相关的数据都采用前X条作为基础，超过X条的记录一概不论。这一点对于黄页系统这样的信息检索系统更是重要。显然，对于一个急于搜索商机的顾客来说，前三页已经是他耐心的极限，超过这个界限，他一般就没有耐心再继续往下查看了。

同时，后文中将会提到，因为本次测试是以手工分析数据为主，因此，很多反馈项目较多的搜索结果无法依据普通的MAP方式构架，只能够采用P@X的方式加以测试。

2  搜索的测试结果

本次测试的文本数据库为黄页公司所提供的上海地区公司信息数据，原始数据存于关系数据库中，大小约为10G，条目总数约为一千六百余万条，测试环境如下表1所示。

表  1

该部分是较为常见的随机测试，在测试对象的选择方面，该测试用例采用随机加人工的方式从主题词库中抽取。先由程序随机地从数据库中的公司名称、简介、地址、经营范围等字段中抽取出字符。然后用人工的方式进行筛选，而筛选的唯一标准就是“是否具有成为实词的可能性”，而对于所选字符的内容则不加任何条件。比如抽取出“所以”，则将它删除，因为“所以”明显是一个虚词；而抽取出了“利工”则虽然词的含义不知所云，但是它具有成为一个实词的可能（比如是一个公司名），就要予以保留。这样的好处是保持了最大程度的公平性，缺点是，有些词搜索出来的结果太多，难以逐个确定。如搜索“公司”，结果可能达到数百万条，这一方面给测试结果的统计带来了极大的困扰，另一方面，这种测试的结果意义不大，因此，一般对于这种词，都采取删除的方法。而有些虽然结果较多，但是仍然有较重大的意义，则将这些词放入测试二：前三十名搜索测试中，详见本小节后面部分。

随机测试共有用例189例，试验结果参见图3：其中灰色线条代表了本系统的正确率，而黑色线条则代表了原有Baidu系统的正确率。直观上讲，可以清楚看出黄页系统在平均数据上超过了Baidu。统计下来，黄页公司现有系统（亦即Baidu）的平均正确率为52.21%，而黄页搜索引擎定制(一期)平均正确率：83.01%。具体数据见表2。

表  2

测试二：随机测试数据

本次实验仍然采用随机数据的方式。所不同的是，本次测试以测试一中删除的长回复数据为主。上文已经说明，囿于人力成本太高，对于一些回复超过300的搜索对象，测试一不予以考虑。这些数据被保存下来放到测试二中。

测试二的最大目的是查看在长搜索结果中，如果有正确结果，是否能够将正确的结果保存到前面几页中。从这个角度来说，本文中的准确率是不正确的，因为显然这种测试方式下，相关文档总数目最多只能够达到30，但是，这种测试方式下的P@X效果则非常有效，基本上可以体现出系统在相关度排序方面的能力。图示与具体的测试结果请看图4和表3。

图  4

表  3

本次测试显示同上图类似，同样是以灰线代表互关联后继树（IRST）的正确率，黑线代表原有系统百度的正确率。

通过测试一和测试二，我们发现本系统无论在单个测试项目，如准确率和召回率上，都胜过原有的百度系统，而且在整体的测试，如MAP和P@X上也有相当大的领先，国际一般信息检索系统的MAP值为14.02%，2005年863检测的最高值为37%。而本系统的MAP值则高达42.35%，显示了极强的能力。但也要注意到，这两个数据之间还是有很大差别：

首先，黄页系统的数据较为特殊，参加863检测的信息检索系统所采用的都是信息检索组织提供的语料库，大小一般为20G左右，平均文章的长度更是远远超过黄页信息系统，搜索的难度显然也比黄页系统更大；

其次，本系统的检索评测算法仍然有缺陷，如测试中采用百度检索结果和黄页系统检索结果取并集的方式作为正确集合，但事实上，如果发生百度和本系统都没有搜索到某些结果的情况，则正确结果数目就会偏小，准确率提高，并随之提高MAP的测试结果；

最后，用分类的方式来进行文本相关度的评测虽然比之采用概率统计的方式要合理，但是这毕竟是一种基于经验归类的方式，如果可能的话，有必要更新这种算法，采用更能够用数学语言表示的方法，比如用自然语言处理的语法分析方式。这些都是需要注意的。

测试三：构造数据的测试

测试三的数据不像前面两者是采用随机的方式获取，测试三的数据是由人工构造的。原因是本次测试的目的同前面两个不同，不是为了获取一般性的测试结果，而是为了测试用户的测试条件比较容易产生歧义的情况下，系统有什么样的反应。

以“金店”为例，就是很容易让系统产生“误会”的搜索。下图是百度搜索中截出的一些结果，如“春林五金店”、“北万新餐饮合作公司瑞金店”（这是代表这分店名）、“马可孛罗面包房黄金店”（表示该店是连锁店中比较重要的一家）等等，都是明显的错误结果。

这种能够产生各种歧义的结果如果通过随机的方式从数据库中提取的话，则首先需要进行大规模的提取，其次尚需要进行人工检索。所以，测试三采用了一种半人工的方式。测试人员从两个渠道获取数据，一方面，通过日常生活的经验，自己想出一些有可能会出错的数据；另一方面，通过肉眼扫描，在数据库中找出一些较长的公司名称等词，人工的进行一些错误的切分，然后作为检索项测试，如“丽水电力局”，就可以切出“水电”来检测搜索结果。

最后得到的搜索结果如图5和表4所示。

图 5

表  4

我们同前几次测试一样，我们可以明显发现复旦结果曲线对百度是一种包含关系，它表明百度正确时，复旦也是正确的，复旦正确时，百度不一定正确。因此同百度的结果相比，复旦的黄页系统仍然具有较大的优势。同时，对比测试一和测试二的随机数据，可以发现准确率仍然有所下降，可见前文中关于消除歧义的算法仍然谈不上完美。

胡运发  男，1940年生，复旦大学信息科学与工程学院教授，博士生导师，主要研究方向是程序设计语言、知识工程与知识库、专家系统与机器学习。

陶晓鹏  男，1970年生，复旦大学信息科学与工程学院副教授，主要研究方向是自然语言处理、文本管理、信息检索。

王政华  男，1980年生，复旦大学信息科学与工程学院硕士生，主要研究方向是全文检索、文本管理、信息检索。

杨笑天  男，1980年生，复旦大学信息科学与工程学院硕士生，主要研究方向是全文检索、文本管理、信息检索。