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

论文摘要

随着互联网的发展，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文件等弱链接文档由于缺乏足够的超链接信息，导致搜索该类文档时，排序结果不佳。针对该问题，基于聚类的弱链接文档排序算法利用聚类算法从高质量的网页搜索结果中提取与查询相关的主题，并根据主题的相关网页的排名确定该主题的重要性，最后根据识别的带权重的主题计算弱链接文档的排序值。实验结果表明该算法能够为弱链接文档产生较好的排序结果。

论文目录

• 摘要
• Abstract
• 目录
• 1 绪论
• 1.1 搜索引擎
• 1.2 聚类分析
• 1.3 聚类分析在搜索引擎的应用
• 1.4 论文研究工作内容与研究成果
• 1.5 论文组织
• 2 基于带窗口约束的频繁项集的文本聚类算法
• 2.1 频繁项集
• 2.2 带窗口约束的频繁项集的定义
• 2.3 带窗口约束的频繁项集的挖掘算法
• 2.4 基于频繁项集的聚类算法
• 2.5 算法性能评估
• 2.6 小结
• 3 XML文档聚类方法
• 3.1 基于数据类型树的XML文档聚类
• 3.2 基于合并编辑距离的XML文档相似度定义
• 3.3 小结
• 4 一种基于搜索日志的网页表示模型
• 4.1 相关工作
• 4.2 混合向量空间模型HVSM
• 4.3 实验结果和分析
• 4.4 小结
• 5 弱链接文档搜索引擎及一种排序算法
• 5.1 相关工作
• 5.2 弱链接文档搜索
• 5.3 弱链接文档状态的排序
• 5.4 弱链接文档的排序
• 5.5 实验评估
• 5.6 小结
• 6 总结与展望
• 致谢
• 参考文献
• 附录1 攻读学位期间发表的学术论文
• 附录2 攻读学位期间参与的研究项目