基于聚类分析的搜索引擎自动性能评价

吴世勇，王明文

(江西师范大学 计算机信息工程学院，江西 南昌 330022)

1 引言

搜索引擎的评价是信息检索研究中的核心课题之一，客观可靠的检索性能评价方式是任何一项信息检索研究中均需要考虑和设计的内容。Saracevic指出[1]：“评价问题在信息检索研发过程中处于如此重要的地位，以至于任何一种新方法与他们的评价方式是融为一体的”。

目前采用较多的评价是基于Cleverdon提出文献[1]的Cranfield 评价框架。Cranfield 框架涉及到的组成部分包括标准评测语料库、查询样例集合、标准答案集合和相应的评价指标等[2]。Cranfield方法指出[1-2]，信息检索系统的评价由如下几个步骤组成：首先，确定查询样例集合，抽取最能表示用户信息需求的一部分查询样例构建一个规模恰当的集合；其次，针对查询样例集合，在检索系统需要检索的语料库中寻找对应的答案，即进行标准答案集合的标注；最后，将查询样例集合和语料库输入检索系统，系统反馈检索结果，再利用检索评价指标对检索结果和标准答案的接近程度进行评价，给出最终的用数值表示的评价结果。

随着万维网的不断发展与互联网信息量的增加，进行网络信息检索系统的性能评价时，Cranfield方法遇到了巨大的障碍。困难主要反映在针对查询样例集合的标准答案标注上，利用手工标注答案的方式进行网络信息检索系统的评价是一个既耗费人力、又耗费时间的过程。考虑到当前搜索引擎涉及到的索引页面都在成百上千亿页面以上(2008年Google在官方网站中透露，他们索引的页面数量在一万亿左右)，再利用手工标注答案的方式进行网络信息检索系统的评价是十分不现实的事情，因此提高搜索引擎性能评价的自动化水平是当前检索系统评价研究中的热点。本文应用聚类方法分析搜索引擎检索返回文档的质量，用类内距和类间距等聚类指标来定义检索性能指标，实现检索系统的自动性能评价。

2 相关研究工作

为了解决Cranfield方法在网络信息检索系统评价中所面临的困境，近年来提出了一些自动进行搜索引擎性能评估的方案，一种是基于Cranfield框架，只是使用自动化方法进行答案自动标注，另一种是在Cranfield框架之外采用一些新的评价方法进行自动化评价。

第一种方案中，研究者尝试使用检索系统反馈的结果信息进行自动标注。Soboroff[3]提出可以在检索系统结果池中，随机挑选一定数量的结果作为答案集合进行评价。Nuray[4]提出对Soboroff方法的修正方案。但这种方案对检索系统性能排序的影响较难以投入使用。部分研究人员基于已有的网页目录资源进行结果的自动标注，如Chowdhury[5]和Beitzel[6]提出的利用开放目录计划所整理的网页目录和对应的网页摘要资源进行性能评测的工作，但使用摘要信息作为用户查询是不合理的假设，也未能得到普及应用。

第二种方案中，有IBM Haifa研究院研发的“相关词集合评价方法”[7]，减少了评价反馈时间，但手工标注与查询相关联的词项也需要大量的人力。Joachims、刘奕群等提出的基于用户点击行为的评价方法[2，8]，更适合导航类查询的评价。在查询性能预测研究中，Kwok和Vinay等人提出的对检索结果同质性进行分析的方法[9-10]，Cronen-Townsend等人提出的对检索结果突显性分析的clarity score方法[11-12]，为利用检索结果质量的好坏程度来实现检索系统的性能自动评价提供了思路。但他们的方法没有考虑查询词的覆盖范围，只是利用返回文档之间的相似度来评价检索结果，而检索结果的好坏与查询本身的质量也有很大关系[13]，多义性、歧义性的查询一般覆盖范围大难以检索到相关文档，Charles Clarke等人[14]针对查询歧义性和结果多样性提出的评价指标能够更好地反映用户查询需求。本文将针对信息类查询结果多样性的特点，根据查询的覆盖度对检索结果进行聚类分析，从这一角度开展评价工作。

3 信息类查询评价与查询覆盖度

3.1 信息类查询

在网络信息检索中，用户的信息查询需求存在很大差异，有的用户希望寻找指定名称的站点或主页，而有的用户希望寻找与查询主题相关的文档页面。这些查询类型的不同对于检索系统是十分重要的，因为不同的查询需求可以设计不同的检索算法从而获得更佳的检索结果，对检索系统的评价也同样如此，不同的查询需求应采用不同的评价方法。

对用户查询有不同的分类方法。Broder把用户的查询信息需求分为三类：导航类，信息类和事务类[15]。导航类查询是寻找知道名称的站点或主页，比如“江西高招网”、“某某市政府网站”等查询，对应于TREC评估的homepage/named page任务；信息类查询是寻找与查询主题相关的文档页面，目标可能位于多个网页，比如“电影”、“知识产权保护”等查询，对应于TREC评估的ad-hoc任务；而事务类查询是指用户希望找到一个服务入口，需要进一步进行服务访问，如火车路线查询、歌曲下载等。

对于大量的用户查询，如何识别其类型呢？在刘奕群的工作[2]中，利用Sogou实验室提供的用户查询日志中的点击信息实现了用户查询信息需求的分类，并且针对导航类查询，提出了基于用户行为分析的搜索引擎自动性能评价方法。因为对于导航类查询而言，其正确答案唯一，而不需考虑答案全面性的问题；其对应的搜索引擎检索性能也较高，因此用户点击行为的可靠性也比较容易保证。即：用户在进行导航类查询时，较容易发现并点击结果列表中对应的答案，只要将用户点击行为中反映出的答案挑选出来就能实现答案的自动标注，从而达到不需要人工标注实现自动性能评价的目的。

对于信息类或事务类查询而言，情况则要复杂的多，其正确答案不唯一，用户期望的正确答案可能有多个，必须考虑答案全面性的问题；而其对应的搜索引擎检索性能相对较低，用户能否点击到正确的答案也较难保证。因此，使用某个搜索引擎的用户行为信息去评价其他搜索引擎信息类、事务类查询的性能是不合理的。

3.2 信息类查询的评价思路

如何实现针对信息类查询的搜索引擎自动性能评价呢？网络搜索引擎处理的数据是整个Web，同时Web数据还在不断动态变化，不同的搜索引擎索引的数据也不尽相同，为了对不同数据集上检索系统的质量进行评估，我们考虑从搜索引擎检索返回文档的整体质量来考查检索系统的性能。根据聚团性假设[10]，与一个查询相关的文档，彼此之间会具有一定的潜在关系，与那些不相关的文档相比，与查询相关的文档会具有一定的相似性或者称为同质性，相关文档会形成一个团，并与那些不相关文档区分开来。考虑到信息类查询的目的是为了查找与查询主题相关的多个文档页面，如果检索返回的文档间比较相似，即具有比较高的同质性，我们就认为返回的文档集合与查询主题比较相关；反之，如果检索返回的文档间相似度很小，我们就认为返回文档集合中可能存在很多不相关的文档，返回文档的整体质量较差。

因此，我们通过对检索返回文档进行聚类分析来考查检索返回的文档质量，达到评估搜索引擎性能的目的。考虑到信息类查询的主题一般可以划分为几个子主题，我们可以根据查询子主题的个数确定返回文档聚类的数目，也就是说查询子主题的个数越多，相应的聚类数目也就越多。确定聚类数目后对检索返回文档进行聚类，如果一个类当中的文档间比较相似、紧密程度较高，我们就认为这个类中的文档与查询中相应的一个查询子主题比较相关；如果几个类中心的距离比较大，侧面反映查询子主题的内聚性比较好，不相关文档(噪声因子)较少。即固定聚类数量后，通过比较类内距和类间距等聚类指标对检索性能进行评价，如果类内距越小、类间距越大则检索返回文档的质量越好。

在对检索返回结果进行聚类分析之前，我们首先要计算查询的覆盖度，即得到对该查询的检索结果进行聚类的数目，下一小节我们将具体介绍查询覆盖度的计算方法。

3.3 查询覆盖度

根据信息检索研究中的独立性假设原则，出现在文档和查询中的词都被看作是相互独立的，所以某个查询的覆盖度可以通过计算查询中所有查询词的覆盖度来得到。

要计算查询词的覆盖范围，我们需要考查查询词本身的性质，查询词具有一般性和特指性之分，一般性查询往往是比较抽象的概念，其覆盖范围比较广泛；而特指性查询往往是比较具体的概念，其覆盖范围较小。比如：“体育”——>“篮球”——>“NBA”——>“火箭队”，其中“体育”这个查询词属于一般性查询，覆盖范围很广，包括了篮球、足球、乒乓球等子主题；而“NBA”属于体育当中的一项篮球赛事，查询的覆盖范围就要小很多。

现在，我们把每个查询词看作是一个查询子主题，那么该查询的覆盖度(CS)可以通过公式(1)计算得到：

(1)

其中q是查询Q中的一个查询词。

文献[16]提出的预测查询性能的CTS方法中，给出了两种计算查询主题重要度的方法，我们发现查询主题越重要的查询，其查询的范围应该更小，即查询覆盖度更小，因而可以将其方法应用到查询覆盖度的计算。在本文中，我们同样可以用两种方法来计算查询词的覆盖度CS(q)，其中一种方法称为CS1，使用查询词的逆文档频率(IDF)来计算查询词的覆盖度，计算方法比较简单。IDF是信息检索中常用到的一个因子，它是词项所出现的文档数目的倒数，常用于反映该词项的区分能力，查询词的IDF越小，其区分能力越低，但覆盖范围就越大。所以，CS1方法定义如下：

(2)

(3)

另外一种方法称为CS2，是基于下面两条准则而设计的[16]。第一，覆盖范围小的词项在文档集中的出现概率(词频)要比其他的词小；第二，覆盖范围小的词项在不同文档中的词频往往存在很大变化。也就是说覆盖范围大的词项在文档集中的分布是比较稳定的，覆盖范围小的词项在文档集中的分布变化比较大。故定义两个变量MP(q)和VP(q)来计算覆盖度CS2(q)。

(4)

上述两种方法都是使用查询词在文档集中的词频信息和文档频率等静态信息，因此我们可以在检索前计算得到查询的查询覆盖度。由于我们无法得到商业搜索引擎的整个文档集，本文计算查询覆盖度使用的文档集是北京大学网络实验室提供的CWT200G数据集与本实验中搜索引擎检索返回的近10G检索结果的合集，共37 662 913篇文档。我们首先对网页预处理，包括对200G网页的解压，采用htmlparser分析html标签，提取网页中的标题和正文，即标签