论文部分内容阅读
摘 要： 随着互联网的普及和web上网页数量的迅猛增长，搜索引擎已经成为从网上获取信息的首选工具。然而，目前主流的搜索引擎利用关键词建立索引，根据检索结果和查询词的相关性从高到低排成一个很长的线性列表，而且检索结果中包含了大量的无用信息，因此对检索结果进行重新组织和挖掘成为了研究热点。本文介绍了检索结果聚类的应用背景，然后介绍了检索结果聚类的算法，最后介绍了检索结果聚类质量评测标准。
关键词：检索结果，；聚类，；簇，；标签
中图分类号：TP391
1. 引言
目前的搜索引擎的检索器是用关键词建立索引，查询含有关键词的网页的链接。检索器根据检索结果和查询词的相关性从高到低排成一个线性列表。但是一个检索结果往往包含成千上万的网页信息，所以搜索引擎的检索结果的线性列表很长。同时其检索的结果仍然包含了很多与用户无关的信息，其比例高达75%以上[1]，用户不得不逐个浏览，这导致要找到自己真正需要的信息很困难。目前有很多算法在改进检索的排序算法，但是光改进算法是不够的。因为很多时候用户在输入的查询词根本就不能完全表达用户的需要，查询的效果就比较差。
针对查询结果不能令人满意的情况下，很多研究学者开始在搜索结果的基础上进行了聚类的研究。将文档分成若干个簇（cluster），使同一簇类文档相关度尽可能大，不同簇之间文档相关度尽可能小，而用户在自己感兴趣的簇内查看检索结果，就可以缩小用户浏览的结果，方便用户的查询。对检索结果的网页摘要（Snippet）聚类，实质是根据摘要的主题相似性划分成不同的簇。每一个簇的主题可以看成是查询的子主题，这样整个检索结果集就可以以层次的形式呈现给用户，最顶层为用户查询词，下层为聚类得到的子主题和标签及每个子主题下的对应的网页摘要。
检索结果聚类不同于传统的文本聚类和网页聚类，主要体现在[22]：
（1）检索结果聚类既要得到高质量的簇，同时还需要确定每个簇的主题描述，或称簇标签，而传统的聚类一般无需得到簇的标签。簇的描述标签非常重要，不仅需要完整的包含一定意义的短语，同时还需要能够对该簇进行主题描述， 并且有较强的可读性；
（2）检索结果的聚类对象为网页片断，信息有限，而传统的聚类对象为文本或网页的全文，包含了丰富的信息；
（3）检索结果聚类属于在线聚类（Online Clustering），检索对象动态变化，实时性要求高。而传统的聚类对象一般比较稳定，对算法的效率没有实时性要求。根据上述特点传统的聚类不能直接适用于检索结果聚类。
2.1 检索结果聚类算法
从上世纪九十年代中期开始，Pedersen[2，3] 等人提出基于结果的聚类算法。目前，很多研究者已经研究并提出了一系列的基于检索结果聚类算法，也出现了几个投入运营的、具有聚类功能的搜索引擎。然而，聚类的效果还远未达到令人满意的程度，聚类质量还有待提高，尤其是簇标签的可读性还有必要进行大的改进。否则，聚类功能不但对用户的帮助有限，而且还会误导用户。但是由于聚类是具有实时性的，所以对采用算法的复杂性也提出了要求。例如，元搜索引擎Metacrawler利用后缀树聚类算法，过滤了由多个搜索引擎返回的不相关的重复的检索结果，然后对返回结果的片段进行聚类，但是它并不支持中文查询词。国内最著名的基于聚类的中文元搜索引擎比比猫www.bbmao.com，遗憾的是它只存在了非常短暂的时间。
目前基于检索结果摘要聚类的算法主要分为两大类[4]。第一类是先对检索结果集进行聚类，然后再针对每个簇提取簇标签，这种方法称为基于文档（Document-based）的聚类方法；第二类是先提取簇的标签，再根据标签在网页片断中的出现情况，利用聚类算法进行聚类，这种方法被称为基于标签（Label-based）的聚类方法。尽管研究者们为了提高检索结果的聚类质量进行了卓有成效的努力，然而，在目前搜索引擎的应用背景下，如果没有好的簇标签，用户仍然难以快速准确地找到自己感兴趣的信息，差的标签甚至对用户具有误导作用。因此，近年来，基于标签的检索结果聚类逐渐成为研究的主流和热点，这类方法更加强调标签的可读性和对簇的概括性，不太注重每个簇的连贯性（Coherence）。
21.1 基于文档的聚类算法
基于文档的聚类算法主要的目标是提高检索结果聚类的质量，在聚类完成以后再提取对应类别的标签。Steven Schockaert[5]提出基于模糊蚁群算法对检索结果进行聚类的基本思想，然后提取簇的标签，其目的主要是为解决传统聚类需要指定簇个数且质量不高的问题，而标签的提取不是重点，重点在于聚类的质量。
Fatih Gelgi [6]为了准确提取文档特征和对特征进行加权，使用关系图表示特征词与查询词之间的关联，再用Term Rank进行关联度分析，根据关联度分析结果将特征词划分为区分性词项、歧义性词项和公共词项，并对三种不同类型的词项采用不同的加权方式。在文档聚类的时候采用K-Means和SCuBa两种算法，但文中未涉及标签的提取问题，主要目标是通过新的特征提取和加权方法提高检索结果的聚类质量。
Ngo，C.L.[7]针对向量空间模型用于网页片断聚类的缺陷，提出了基于容错粗糙集模型（Tolerance Rough Set Model）的算法，聚类后再提取簇标签。
国内为提高检索结果的聚类质量也开展了一系列的研究工作，也提出了若干比较有效的算法。沙芸在文献[8]提出了的是一种线聚类再提出簇描述标签的算法。该算法根据词间的语义相关度进行聚类，把词看作是聚类的核心，词所在的文档作为词的属性，根据词在文档中的共现的情况来划分簇，最后给簇确定其标签。
李红梅等在文献[9]中提出了提出了基于概念分组的聚类算法。根据概念分组技术找出特征词之间的语义关联并形成概念类，再计算文档与概念类的距离以此进行聚类。最后根据特征词在文档中的重要性提取簇描述标签。 Hua-Jun Zeng在文献[10]中将检索结果聚类看成是显著短语排序（Salience Phrase Ranking）问题。首先对候选短语进行综合评估并排序，得到潜在簇的标签。将包含潜在标签的文档即被认为属于相应的簇，最后经过合并等后处理得到最后的输出结果。
黄健斌在文献[11]提出了一种在格的拓扑序列上进行概念聚类的快速聚类算法。该方法利用格理论解决了概念聚类中概念间的多重继承关系的问题，并应用在Web搜索结果聚类上，取得了较好的结果。
张辉等在文献[12]提出基于关键特征的聚类算法（KFC）。首先从检索结果的关键词中选择重要的词作为关键特征，然后通过分析关键特征之间的关系，并对特征聚类，最后通过对特征的聚类达到对检索结果聚类的目的。
21.2 基于标签的聚类算法
最近两年，国内出现了很多基于标签的聚类算法研究。骆雄武等在文献[9]将搜索引擎返回的结果建立后缀树，然后计算后缀树中各个短语的得分，将得分最高的短语作为候选标签。将包含标签的文档分配到标签所对应的类中，最后形成聚类结果。
陈毅恒在文献[13]对检索结果中的句子进行依存句法分析，利用同义词词林为Ontology提取与查询词强关联的短语作为候选标签和簇的质心，通过K-均值算法对检索结果进行聚类。该算法存在的缺点是大量使用了外部资源，需要句法知识和概念语义方面的知识作为支撑，对检索结果进行句法分析的时候效率比较低，而且无法保证句法分析的正确。张云在文献[14]中提出了一种对检索结果层次化的聚类方法。根据词之间的共现特性找出频繁的2元短语，再以此进行扩展成多元短语产生候选标签。最后，将文档分配到标签对应的簇，形成层次化聚类结果。陈永超等在文献[15]提出一种基于命名实体的搜索结果聚类算法NEC。该算法将命名实体作为类的候选标签，再根据标签确定聚类内容的方法，有效地保证了标签的可读性及标签与内容之间的主题相关性。张刚在文[16]提出基于文档频率（DF）、查询日志、查询词上下文来抽取标签，在此基础上利用基于图的聚类算法对检索结果进行聚类。肖欣延在文[17]考虑了标签与查询词之间的相关性，查询词出现的位置，将共现足够频繁的候选短语抽取出来作为潜在标签，利用知网计算的词汇之间的语义距离来实现聚类和簇的合并等后处理。
通过很多研究者的努力，目前基于标签的聚类算法在标签和聚类质量方面都有明显的改善。然而绝大多数都使用了大量的外部信息资源，如Ontology[18]，知网的信息[19]，词性的信息，句法知识，外部的锚文本信息等。这些信息的使用虽然可以提高质量，但也会增加聚类的负担，加大聚类的时间和空间消耗，特别对于实时的在线聚类，将非常影响查询效率。
3.2 度量指标
关于搜索引擎聚类浏览技术，由于缺乏标准评价数据集和性能衡量标准，评价一直是一个难题，尤其是对聚类标签的评价，主观性很强。因此，本章对标签的评价主要是和其他中文聚类搜索引擎进行对比。
文献[21]采用了文档聚类中的F 值评分作为搜索结果聚类的评价标准，该方法需要采用聚类基准，但是对于检索结果来说，基准往往是未知的。针对搜索结果聚类的特点，人们提出了一些新的评价方法。
Wang[20]提出使用平均信息熵的评价方法。信息熵用来衡量聚类的纯度，旨在判定同类中的网页是否真正是关于同一个主题的，而本章的实验主要采用该评价方法对簇的质量进行评估。聚类后形成的任一类别j的信息熵定义如式1所示[20]：
E（j）=-∑Pijlog（Pij）
（1）
其中，pij是类别j属于给定类i的概率。
聚类集的平均信息熵定义如式2所示[20]：
（2）
其中，nj是类别j的大小，m是聚类的类别总数，n是聚类的网页总数。
4. 用户评价的方法包括系统日志分析和用户主观两种评价方式。Grouper通过对系统的日志进行分析，根据日志的统计结果对聚类的性能做出评价。LINGO则采用了用户主观评价的法，即通过问卷调查的方式，根据对测试用户的反馈结果，对聚类系统性能进行评价。这种人工评测的方法也是目前聚类系统评测中采用较多的一种评价方法。
3 结束语总结
本文论述了对检索结果聚类的重要意思，同时对基于文档的聚类算法以及基于标签的聚类算法进行了综述，并且介绍了检索结果聚类质量的评价问题。随着web服务的广泛应用，检索结果聚类将越来越多的被应用在搜索引擎中，以此帮助用户快速查找所需要的信息。
参考文献：
[1]M.W.Berry，Z.Drrmac，E.R.Jessup.Matrices，Vector Spaces，and Information Retrieval[J].SIAM Review，2004（41）：335-362.
[2] 黄健斌，姬红兵.基于模糊概念格的Web搜索结果聚类算法[J]. 西安电子科技大学学报（自然科学版）， 2005.
[3] 陈永超， 刘贵全. 一种基于命名实体的搜索结果聚类算法[J]. 计算机工程， 2009.
[4] 张刚， 刘悦， 郭嘉丰. 一种层次化的检索结果聚类方法[J]. 计算机研究与发展， 2008.
作者简介：卢仁猛（1980-），男，高级工程师，研究方向：数据库及网络安全。
作者单位：贵州电网公司，贵阳 550002
关键词：检索结果，；聚类，；簇，；标签
中图分类号：TP391
1. 引言
目前的搜索引擎的检索器是用关键词建立索引，查询含有关键词的网页的链接。检索器根据检索结果和查询词的相关性从高到低排成一个线性列表。但是一个检索结果往往包含成千上万的网页信息，所以搜索引擎的检索结果的线性列表很长。同时其检索的结果仍然包含了很多与用户无关的信息，其比例高达75%以上[1]，用户不得不逐个浏览，这导致要找到自己真正需要的信息很困难。目前有很多算法在改进检索的排序算法，但是光改进算法是不够的。因为很多时候用户在输入的查询词根本就不能完全表达用户的需要，查询的效果就比较差。
针对查询结果不能令人满意的情况下，很多研究学者开始在搜索结果的基础上进行了聚类的研究。将文档分成若干个簇（cluster），使同一簇类文档相关度尽可能大，不同簇之间文档相关度尽可能小，而用户在自己感兴趣的簇内查看检索结果，就可以缩小用户浏览的结果，方便用户的查询。对检索结果的网页摘要（Snippet）聚类，实质是根据摘要的主题相似性划分成不同的簇。每一个簇的主题可以看成是查询的子主题，这样整个检索结果集就可以以层次的形式呈现给用户，最顶层为用户查询词，下层为聚类得到的子主题和标签及每个子主题下的对应的网页摘要。
检索结果聚类不同于传统的文本聚类和网页聚类，主要体现在[22]：
（1）检索结果聚类既要得到高质量的簇，同时还需要确定每个簇的主题描述，或称簇标签，而传统的聚类一般无需得到簇的标签。簇的描述标签非常重要，不仅需要完整的包含一定意义的短语，同时还需要能够对该簇进行主题描述， 并且有较强的可读性；
（2）检索结果的聚类对象为网页片断，信息有限，而传统的聚类对象为文本或网页的全文，包含了丰富的信息；
（3）检索结果聚类属于在线聚类（Online Clustering），检索对象动态变化，实时性要求高。而传统的聚类对象一般比较稳定，对算法的效率没有实时性要求。根据上述特点传统的聚类不能直接适用于检索结果聚类。
2.1 检索结果聚类算法
从上世纪九十年代中期开始，Pedersen[2，3] 等人提出基于结果的聚类算法。目前，很多研究者已经研究并提出了一系列的基于检索结果聚类算法，也出现了几个投入运营的、具有聚类功能的搜索引擎。然而，聚类的效果还远未达到令人满意的程度，聚类质量还有待提高，尤其是簇标签的可读性还有必要进行大的改进。否则，聚类功能不但对用户的帮助有限，而且还会误导用户。但是由于聚类是具有实时性的，所以对采用算法的复杂性也提出了要求。例如，元搜索引擎Metacrawler利用后缀树聚类算法，过滤了由多个搜索引擎返回的不相关的重复的检索结果，然后对返回结果的片段进行聚类，但是它并不支持中文查询词。国内最著名的基于聚类的中文元搜索引擎比比猫www.bbmao.com，遗憾的是它只存在了非常短暂的时间。
目前基于检索结果摘要聚类的算法主要分为两大类[4]。第一类是先对检索结果集进行聚类，然后再针对每个簇提取簇标签，这种方法称为基于文档（Document-based）的聚类方法；第二类是先提取簇的标签，再根据标签在网页片断中的出现情况，利用聚类算法进行聚类，这种方法被称为基于标签（Label-based）的聚类方法。尽管研究者们为了提高检索结果的聚类质量进行了卓有成效的努力，然而，在目前搜索引擎的应用背景下，如果没有好的簇标签，用户仍然难以快速准确地找到自己感兴趣的信息，差的标签甚至对用户具有误导作用。因此，近年来，基于标签的检索结果聚类逐渐成为研究的主流和热点，这类方法更加强调标签的可读性和对簇的概括性，不太注重每个簇的连贯性（Coherence）。
21.1 基于文档的聚类算法
基于文档的聚类算法主要的目标是提高检索结果聚类的质量，在聚类完成以后再提取对应类别的标签。Steven Schockaert[5]提出基于模糊蚁群算法对检索结果进行聚类的基本思想，然后提取簇的标签，其目的主要是为解决传统聚类需要指定簇个数且质量不高的问题，而标签的提取不是重点，重点在于聚类的质量。
Fatih Gelgi [6]为了准确提取文档特征和对特征进行加权，使用关系图表示特征词与查询词之间的关联，再用Term Rank进行关联度分析，根据关联度分析结果将特征词划分为区分性词项、歧义性词项和公共词项，并对三种不同类型的词项采用不同的加权方式。在文档聚类的时候采用K-Means和SCuBa两种算法，但文中未涉及标签的提取问题，主要目标是通过新的特征提取和加权方法提高检索结果的聚类质量。
Ngo，C.L.[7]针对向量空间模型用于网页片断聚类的缺陷，提出了基于容错粗糙集模型（Tolerance Rough Set Model）的算法，聚类后再提取簇标签。
国内为提高检索结果的聚类质量也开展了一系列的研究工作，也提出了若干比较有效的算法。沙芸在文献[8]提出了的是一种线聚类再提出簇描述标签的算法。该算法根据词间的语义相关度进行聚类，把词看作是聚类的核心，词所在的文档作为词的属性，根据词在文档中的共现的情况来划分簇，最后给簇确定其标签。
李红梅等在文献[9]中提出了提出了基于概念分组的聚类算法。根据概念分组技术找出特征词之间的语义关联并形成概念类，再计算文档与概念类的距离以此进行聚类。最后根据特征词在文档中的重要性提取簇描述标签。 Hua-Jun Zeng在文献[10]中将检索结果聚类看成是显著短语排序（Salience Phrase Ranking）问题。首先对候选短语进行综合评估并排序，得到潜在簇的标签。将包含潜在标签的文档即被认为属于相应的簇，最后经过合并等后处理得到最后的输出结果。
黄健斌在文献[11]提出了一种在格的拓扑序列上进行概念聚类的快速聚类算法。该方法利用格理论解决了概念聚类中概念间的多重继承关系的问题，并应用在Web搜索结果聚类上，取得了较好的结果。
张辉等在文献[12]提出基于关键特征的聚类算法（KFC）。首先从检索结果的关键词中选择重要的词作为关键特征，然后通过分析关键特征之间的关系，并对特征聚类，最后通过对特征的聚类达到对检索结果聚类的目的。
21.2 基于标签的聚类算法
最近两年，国内出现了很多基于标签的聚类算法研究。骆雄武等在文献[9]将搜索引擎返回的结果建立后缀树，然后计算后缀树中各个短语的得分，将得分最高的短语作为候选标签。将包含标签的文档分配到标签所对应的类中，最后形成聚类结果。
陈毅恒在文献[13]对检索结果中的句子进行依存句法分析，利用同义词词林为Ontology提取与查询词强关联的短语作为候选标签和簇的质心，通过K-均值算法对检索结果进行聚类。该算法存在的缺点是大量使用了外部资源，需要句法知识和概念语义方面的知识作为支撑，对检索结果进行句法分析的时候效率比较低，而且无法保证句法分析的正确。张云在文献[14]中提出了一种对检索结果层次化的聚类方法。根据词之间的共现特性找出频繁的2元短语，再以此进行扩展成多元短语产生候选标签。最后，将文档分配到标签对应的簇，形成层次化聚类结果。陈永超等在文献[15]提出一种基于命名实体的搜索结果聚类算法NEC。该算法将命名实体作为类的候选标签，再根据标签确定聚类内容的方法，有效地保证了标签的可读性及标签与内容之间的主题相关性。张刚在文[16]提出基于文档频率（DF）、查询日志、查询词上下文来抽取标签，在此基础上利用基于图的聚类算法对检索结果进行聚类。肖欣延在文[17]考虑了标签与查询词之间的相关性，查询词出现的位置，将共现足够频繁的候选短语抽取出来作为潜在标签，利用知网计算的词汇之间的语义距离来实现聚类和簇的合并等后处理。
通过很多研究者的努力，目前基于标签的聚类算法在标签和聚类质量方面都有明显的改善。然而绝大多数都使用了大量的外部信息资源，如Ontology[18]，知网的信息[19]，词性的信息，句法知识，外部的锚文本信息等。这些信息的使用虽然可以提高质量，但也会增加聚类的负担，加大聚类的时间和空间消耗，特别对于实时的在线聚类，将非常影响查询效率。
3.2 度量指标
关于搜索引擎聚类浏览技术，由于缺乏标准评价数据集和性能衡量标准，评价一直是一个难题，尤其是对聚类标签的评价，主观性很强。因此，本章对标签的评价主要是和其他中文聚类搜索引擎进行对比。
文献[21]采用了文档聚类中的F 值评分作为搜索结果聚类的评价标准，该方法需要采用聚类基准，但是对于检索结果来说，基准往往是未知的。针对搜索结果聚类的特点，人们提出了一些新的评价方法。
Wang[20]提出使用平均信息熵的评价方法。信息熵用来衡量聚类的纯度，旨在判定同类中的网页是否真正是关于同一个主题的，而本章的实验主要采用该评价方法对簇的质量进行评估。聚类后形成的任一类别j的信息熵定义如式1所示[20]：
E（j）=-∑Pijlog（Pij）
（1）
其中，pij是类别j属于给定类i的概率。
聚类集的平均信息熵定义如式2所示[20]：
（2）
其中，nj是类别j的大小，m是聚类的类别总数，n是聚类的网页总数。
4. 用户评价的方法包括系统日志分析和用户主观两种评价方式。Grouper通过对系统的日志进行分析，根据日志的统计结果对聚类的性能做出评价。LINGO则采用了用户主观评价的法，即通过问卷调查的方式，根据对测试用户的反馈结果，对聚类系统性能进行评价。这种人工评测的方法也是目前聚类系统评测中采用较多的一种评价方法。
3 结束语总结
本文论述了对检索结果聚类的重要意思，同时对基于文档的聚类算法以及基于标签的聚类算法进行了综述，并且介绍了检索结果聚类质量的评价问题。随着web服务的广泛应用，检索结果聚类将越来越多的被应用在搜索引擎中，以此帮助用户快速查找所需要的信息。
参考文献：
[1]M.W.Berry，Z.Drrmac，E.R.Jessup.Matrices，Vector Spaces，and Information Retrieval[J].SIAM Review，2004（41）：335-362.
[2] 黄健斌，姬红兵.基于模糊概念格的Web搜索结果聚类算法[J]. 西安电子科技大学学报（自然科学版）， 2005.
[3] 陈永超， 刘贵全. 一种基于命名实体的搜索结果聚类算法[J]. 计算机工程， 2009.
[4] 张刚， 刘悦， 郭嘉丰. 一种层次化的检索结果聚类方法[J]. 计算机研究与发展， 2008.
作者简介：卢仁猛（1980-），男，高级工程师，研究方向：数据库及网络安全。
作者单位：贵州电网公司，贵阳 550002