文档聚类技术在搜索引擎中的应用研究，本文主要内容关键词为：搜索引擎论文,文档论文,技术论文，此文献不代表本站观点，内容供学术参考，文章仅供参考阅读下载。
1 引言
现今，随着Internet的飞速发展，它已经成为了一个包含有多种信息资源并且遍布全球的信息服务网络。Internet中所包含的数据正呈现出海量性、动态性和多样性等特点。如何在这些庞大、分散并且无序的数据中，快速、准确地找到满足用户需要的信息，对于信息检索领域来说是一个巨大的挑战。
目前虽然有了Google、百度等著名的搜索引擎，但实际上，它们的检索结果很难令人满意，主要存在以下一些问题：返回结果太多，经常都是成千上万。这使得用户往往无从下手，不知道该从哪里开始浏览；查准率低。检索结果往往不能很好地满足用户需求，与用户提问的相关度低；一维线性列表的结果显示方式，增加了用户的浏览负担等等①。
为了能很好地解决以上这些问题，对网页文档进行聚类是非常重要的。在搜索引擎中应用文档聚类技术，能使经过处理后的搜索结果以一种超链接的层次类目方式提交给用户②，内容相似的搜索结果被划分为一个类目，这样，搜索结果就被有效地组织起来，用户就可以快速地了解搜索结果的整体分布情况，并快速定位自己需要的结果，大大提高了检索的查全率和查准率。对检索结果进行聚类处理能够缩短检索时间，加快检索过程，提高检索精度，方便用户使用。
所以，研究文档聚类技术在搜索引擎中的应用具有重要而且广泛的现实意义。
2 文档聚类技术概述
文档聚类是一种无指导的文档归类方法，它把一个文档集划分成若干个称为集簇的子集，每个集簇中的文档成员之间具有较大的相似性，而集簇之间的文档具有较小的相似性③，用户可以在自己感兴趣的集簇中查看结果。作为一种无监督的机器学习方法，文档聚类技术把大量的文档划分成用户可以迅速理解的簇，从而使用户可以更快地把握大量文档中所包含的内容，加快分析速度并辅助决策。大规模文档聚类是解决海量文本中数据理解和信息挖掘的有效解决手段之一，已为越来越多的研究人员所关注。
3 文档聚类技术在搜索引擎中的应用
3.1 Web文档聚类
借助于文档聚类技术，可以对已经检索到的Web文档进行聚类。Web文档聚类即是把搜索引擎所返回的检索结果按照一定的依据进行聚类，创建类目体系，同类文档相似性大，异类文档相似性小。然后再把类目呈现给用户，使用户能在更高的主题层次上来浏览结果，从与主题相似的文档形成的类中选择相关的 Web文档。
因为搜索引擎返回的结果量非常大，同时需要支持在线查询，所以所使用的聚类方法必须满足一些基本条件④：（1）聚类一致性，即相关性。聚类要将所有类似的Web文档聚到一类，把与用户查询条件相关的文档与不相关的文档分离开。（2）浏览高效性，即概括性。用户一眼就可以找到自己感兴趣的内容，所以需要对每个类目提供简明精确的聚类描述。（3）重叠性。因为Web文档通常会有多个主题，所以不需要把它们限制在一个单独的类中，可以叠加聚类。（4）快速性。对检索结果的聚类速度快，效率高，将查询结果显示给用户前不能有太大的延迟。
3.2 搜索引擎中的聚类算法
在搜索引擎中使用的网页文档聚类算法主要分为3类：基于网页内容的聚类算法、基于链接分析的聚类算法和基于用户搜索日志的聚类算法⑤。本文主要介绍第一种算法中的STC算法。
基于网页内容的聚类算法是通过分析网页中所包含的文字内容对网页进行聚类的，包括STC算法、模糊聚类法等等。STC（Suffix Tree Clustering）算法，即后缀树算法，最早是由Zamir等人提出的⑥。它是一种线性时间聚类算法，根据待聚类网页中的相似词组或短语来进行聚类。它包括了以下三个步骤⑦：（1）网页文档的清洗。这一步相当于对网页的特征进行抽取。它对代表网页特征的字符串进行过滤，去掉如HTML标记、大部分的标点等不是文字的标记符号和停用词，并标明各句之间的间隔。一些词语被转换成它们的根的形式，如“computer”、“computing”、“compute”、“computers”等词都需要被缩减成“compute”。（2）确定基本聚类串，构造后缀树。基本聚类串是一些具有共同词组的网页的集合。它们是在对网页特征进行抽取的同时使用STC算法进行计算得到的。后缀树上的每一个节点对应一个基本聚类串。（3）合并基本聚类串，形成最后的结果。其主要的依据是同一聚类中的网页在语义上的相关性，也就是一篇网页可以在多个聚类中出现。
STC算法与传统算法相比，最大的优势就在于STC算法是基于词组的聚类方法，克服了传统算法只是基于单个词，而忽略了词间的语义关系的缺陷。STC将词间关系也作为了聚类的重要依据，使用词组或短语而不是单个的词来判断网页的相似性，同时也考虑了这些词组出现的位置和顺序，这样能够更加充分地利用网页上的信息，也能大大提高聚类的准确性。此外，STC算法的聚类速度快，效率高，在搜索引擎返回结果的同时就开始工作，通常情况下在接收到最后一篇网页之后就可以显示出结果，不会产生明显的迟滞现象⑧。但是，这种算法也有缺点，由于它是基于词组来进行聚类的，所以它与基于全文信息来进行聚类的方法相比准确率要低一点。可见，STC算法还有进一步改进的余地。
基于链接分析的聚类算法通过分析网页之间的链接关系对网页进行聚类。这种算法需要对检索结果中的网页进行相似度计算，将相似度大于某个阈值的网页归为一类。
基于用户搜索日志的聚类算法是通过用户对检索结果中网页的访问情况对网页进行聚类的。该算法会对每个用户输入的检索词以及其对检索结果的访问情况进行记录，并且对检索结果进行相似度计算。
通常情况下，这3种聚类算法在搜索引擎中会结合使用。
3.3 实例分析——Vivisimo
Vivisimo(http://www.vivisimo.com)、Mooter (http://www.mooter.com)、bbmao（比比猫，我国开发的，http//www.bbmao.com）等等搜索引擎都使用了文档聚类技术。其中Vivisimo最为著名。
Vivisimo是美国Vivisimo公司开发的一个具有对搜索结果进行自动聚类功能的搜索引擎，它能快速地将不同类型的网页或网站进行分类整理并将结果呈现给用户。它是目前较为成熟的聚类搜索引擎，具有合适的层次型类别组织、快速的响应、友好的用户界面等，实现的是及时的、概念的、层次结构的聚类。它允许将具有多个类别特征的文档放到多个类目中，这与其他一些普通的聚类搜索引擎只将一个文档放到一个类别不同。
从严格意义上讲，Vivisimo不是一个搜索引擎，也不是一个元搜索引擎，它不通过自动索引程序Robot （或人工）来广泛搜集网络信息资源，它只组织其他搜索引擎的输出结果，比如URL地址、标题和简短的描述，它也能组织多个搜索引擎的组合输出结果，所以它更确切地说是一个聚类引擎⑨。
Vivisimo的核心技术就是文档聚类技术。Vivisimo网络搜索的过程如下⑩：（1）查询一个或多个网络搜索引擎；（2）抽取检索结果中文档的标题、URL地址等特征来解析这些页面；（3）根据所抽取的特征对Web文档进行聚类；（4）对每个类目以及其中包含的Web文档排序；（5）显示层次结构目录。整个过程的完成只需要几秒钟。Vivisimo的聚类在用户看到检索结果之前就已经形成了，不需要对文献集合作任何预处理。
从使用Vivisimo搜索关键词“New York”（纽约）所得到的搜索结果得知，在搜索结果页面的左侧是一个已经经过聚类的导航栏，它的作用就是显示对右侧窗口中的所有搜索结果进行聚类后的类目，同时也显示此次搜索后每个类目的总数目。232个结果被分成了New York State、New York City、University、Newspaper等类。点击“More”这个链接，将会显示出被隐藏的类目。如果在右侧页面中没有找到需要的结果，用户可以直接找到与自己需求信息最接近的一个类目并点击“+”展开，然后再点击展开后的某一子目录，这时在右侧窗口中将显示该子目录包含的所有搜索链接。
但是，Vivisimo也存在缺陷，它是利用其他搜索引擎的搜索结果进行再加工的，其速度受到了非常多的限制，不可能在并发用户访问压力大的情况下保持足够快的响应速度。同时，Vivisimo与Mooter相比，也缺少可视化的图形表示。Mooter的结果可视化页面中，一个点代表一个类，点击这些类，将显示出该类目下的所有结果，显示效果与Vivisimo左边是导航栏、右边是结果的方式相同。Mooter的致命缺陷是不能显示出每一类中文档的数量，而且不能查询中文网页。
4 聚类搜索引擎未来的发展趋势
随着文档聚类技术的不断发展、进步和完善，未来的搜索引擎在聚类功能上也必将更加体现出准确、易用、个性化等特点，真正满足用户的需求。
4.1 基于内容的聚类检索
现实的文档中词语之间是有关联的，比如同义词，用词不同但所表述的概念却是一致的，像“计算机”与“电脑”。文档聚类与语义是密切相关的，但是现今的大部分聚类方法仅仅通过统计文档中关键词的出现频率来进行聚类，这样容易忽略网页文档之间的语义联系，造成网页只是在字面上而不是内容上相关(11)，聚类质量差，并不能真正减轻用户的浏览负担。
因此，未来的聚类技术需要更加关注网页文档的结构及其语义联系，并与知识库相结合，从字面聚类走向真正的内容聚类。未来的聚类搜索引擎也必将更加关注从内容的层面上对网页进行聚类，建立合理的知识库结构，对聚类结果进行有效的组织和控制，提高聚类的内在质量。
4.2 聚类结果的可视化
前面提到的Mooter这个搜索引擎虽然使用了图形的方式将各个类目显示出来，但每个类目之间的关系、每个类目中Web文档的数量都看不到，点击类目显示该类的检索结果时，还是以一维的线性列表方式呈现给用户。用户在图形中看到的只是全部的类目，这与Vivisimo这种左边显示所有类目的方式没有什么本质区别。所以我觉得这还算不上是真正的可视化。聚类结果应该朝着真正的可视化方向发展。
目前的聚类搜索引擎采用关键词的目录结构组织聚类结果，以超链接的方式呈现给用户，是线性的、一维的，结果的显示很不直观。如果用户要想知道某一个类目下面的结构就必须点开这个类目，而且搜索结果是以网页方式呈现的，这样就很不利于网速慢的用户使用，因为每打开一个类目，就相当于重新向服务器提交一个请求。而以可视化的方式组织的聚类结果，就可以有效地避免浏览不便这一弊端。同时，可视化方式允许用户对检索结果进行动态的调整和过滤，帮助用户决定自己的检索策略，增加了用户与检索系统之间的交互作用，使用户的信息处理能力和检索能力发挥到最大程度(12)。比如，采用树状展开结构显示聚类结果，用颜色的不同来表示每个类目下面网页数量的多少，并配以图示，这样就可以使聚类结果的情况一目了然，使用户能够很方便地掌握聚类结果的整体情况，大大缩小了用户需要浏览的结果数量，并能根据检索聚类的情况，随时调整检索提问。
4.3 基于个性化的用户模式
聚类搜索引擎应该向个性化用户模式的方向发展。个性化既可以是基于检索历史的，也可以是基于检索结果的。
用户的检索历史记录通常包括用户提交的检索提问式、检索的类型、日期以及检索结果等。当用户使用搜索引擎进行检索时，搜索引擎会自动记录下每个用户的检索历史，并根据用户以前的检索日志动态调整本次的搜索结果，返回适合用户个性的聚类结果。基于检索结果的个性化检索，是指利用用户对检索结果信息内容的定制，获知用户的个性化信息，并依此构建用户个性化检索模型从而实现的个性化检索(13)。
将聚类技术与个性化的用户模式相结合，能够更好地分析用户的信息需求，自动识别用户兴趣，从而对聚类结果进行相应处理，使用户不是在聚类的类目列表中找寻自己需要的结果，而是直接把用户需要的结果集呈现给用户，这样做提高了用户信息检索的准确性和效率。
5 结语
将文档聚类技术应用到搜索引擎中，已经是大势所趋，越来越多的搜索引擎都会集成聚类技术以方便用户的使用。但是现今仍然没有一个比较完美的具有聚类功能的搜索引擎出现，搜索引擎中聚类技术的应用问题还需要进一步地讨论研究。相信在不久的将来，最为熟悉的Google、百度等搜索引擎的聚类功能会让我们眼前一亮。
注释：
① Fang L,Mehlitz M etc.Web Pages Clustering and Concepts Mining:An approach towards Intelligent Information Retrieval.Cybernetics and Intelligent Systems,2006 (6):1－6
② 陶跃华，陈丽萍，王泳．聚类分析在搜索引擎中的应用．计算机工程与应用，2003(21):180－182
③ 王楠．基于聚类的全文检索系统后处理．情报检索，2005(1):112－114
④ 孙建军，成颖．信息检索技术．北京：科学出版社，2004
⑤ 靖培栋，田亮．聚类在搜索引擎中的应用．情报理论与实践，2006(4):493-496
⑥ Zamir O,Etzioni O.Web document clustering:A feasibility demonstration.Proceedings of the 19th International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR98),1998
⑦ Crabtree D,Xiaoying G,Andreae P.Improving Web clustering by cluster selection.Web Intelligence,2005.Proceedings.The 2005 IEEE/WIC/ACM International Conference on 19－22 Sept.2005:172－178
⑧ 韩建福．文档聚类在搜索引擎结果中的应用研究．北京交通大学硕士论文，2006
⑨⑩ 宾锋．信息检索的新方法——检索结果自动聚类．情报杂志，2002(11):31－32
(11) Bo-Yeong K,Dae-Won K,Sang-Jo L.Exploiting concept clusters for content-based information retrieval.Information Sciences,2005 (2):443－462
(12) 曹锦丹，王丽伟，齐艳丽．可视化技术在网络信息检索中的应用．情报杂志，2005(8):113－116
(13) 曹红兵．搜索引擎的个性化检索研究．图书情报工作，2007(3):12－136
标签：搜索引擎论文; 聚类论文; 模糊聚类分析论文; 层次聚类方法论文; 无监督学习论文; web技术论文; web开发论文;