搜索引擎中文档聚类方法研究

摘要

随着互联网的发展，Web 上的信息浩如烟海，搜索引擎作为互联网中的基础应用已经成为人们获取信息的重要工具。为了能给用户提供更好的搜索服务，近年来，数据挖掘和机器学习技术被广泛用来改善搜索结果的质量。其中，聚类技术在无任何先验知识的情况下，能将大规模数据按照数据的相似性划分成用户可迅速理解的簇(cluster)，从而使用户更快地了解大量文档中所包含的内容。因此，聚类技术成为搜索引擎中不可或缺的部分和研究热点。
　　 在搜索引擎中，存在着两类数据：一是搜索引擎从互联网抓取的文档即用户搜索的对象，包括普通文本网页、XML 文档和包括Flash、AJAX 在内的超链接信息较少的文档；二是搜索日志即用户使用搜索引擎时产生的行为记录(userbehavior data)，搜索日志提供了一个潜在的知识库来辅助文档聚类分析。不同的文档有不同的特点，不同的应用对聚类分析有不同的要求。因此，数据的表示、数据相似度的定义，以及聚类分组算法是重要研究课题，具有重要的理论和实际意义。
　　 对于文本文档(text document),现有的文本聚类算法忽略了文档是有序的单词序列而将文档视为一系列离散单词的集合。基于带窗口约束的关联规则的聚类算法(FICW)首先用滑动窗口对单词的位置进行约束，挖掘出文本集合中的频繁项目集，然后将得到的频繁项目集用于文本聚类。实验表明，FICW 产生了质量更高的聚类结果，具有更好的效率和伸缩性。
　　 XML 文档是Web 上的重要组成部分，基于公共路径的XML 文档相似度定义因为计算开销小而被应用于XML 聚类，却忽略了公共子路径在XML 树上的分布信息。一种基于启发性策略的合并编辑距离(MED)，利用将两棵XML 树压缩为它们的公共子树所需的编辑代价来捕获公共子路径的分布情况。实验表明，MED 成功表示了XML 树间公共子树的分布情况，基于MED的相似度定义较基于路径的相似度定义更好地衡量了XML 文档间的相似程度。另一方面，为解决XML 文档随意命名标签导致的度量XML 文档相似度困难的问题，根据XML 描述同类对象时，所使用的数据在数据类型的构成上具有一致性的特点，一种基于数据类型树的相似度评估标准被应用于XML 文档聚类中。实验验证了该相似度定义的有效性，得到了较高质量的聚类结果。
　　 搜索日志记录的用户点击情况反映了网页中哪些主题才是真正引起用户兴趣的主题。因此利用搜索日志从用户的角度对网页进行聚类分析成为一种有效的方法。基于用户行为的混合网页表示模型首先从搜索引擎的搜索日志中抽取访问过给定网页的查询，将这些查询作为描述该网页的主题词，然后以主题词为中心从网页中抽取内容生成描述网页的虚拟文档以及相应的向量表示。实验结果表明，该混合表示模型能有效地改善网页分类和聚类的质量。
　　 Web 上的AJAX 应用和PowerPoint 文件等弱链接文档由于缺乏足够的超链接信息，导致搜索该类文档时，排序结果不佳。针对该问题，基于聚类的弱链接文档排序算法利用聚类算法从高质量的网页搜索结果中提取与查询相关的主题，并根据主题的相关网页的排名确定该主题的重要性，最后根据识别的带权重的主题计算弱链接文档的排序值。实验结果表明该算法能够为弱链接文档产生较好的排序结果。