针对搜索结果的位图表示及聚类算法改进研究

摘要

网络科技和搜索技术的迅猛发展使得人们越来越多地通过互联网和搜索引擎获取信息，搜索结果种类多、排列乱是影响用户快速获取有效信息的重要因素。为提高用户获取有效信息的速度、改善用户的搜索体验，聚类分析技术被广泛应用到搜索结果中。目前，针对搜索结果聚类的大部分研究集中于聚类方式，忽略了搜索结果的表示方法对聚类效果和收敛速率的影响；此外，常用于搜索结果聚类的K-means算法的聚类效果和收敛速率受初始聚类中心影响较大，而当前关于初始聚类中心的研究仍然存在一些不足。基于此，本文从搜索结果的表示方法和初始聚类中心的选择两个方面展开研究，具体完成了以下几项工作： (1)针对向量空间模型存在文本相似度计算耗时以及存储空间需求较大的问题，本文结合向量空间模型和布尔模型各自的优点提出了基于位图的文本表示方法表示搜索结果。该方法先用向量空间模型将搜索结果表示成特征向量，然后将特征权重转换为对应的布尔值，最后以位为单位存储布尔值形成位图特征向量。实验结果表明，本文提出的位图文本表示方法可以有效的提高搜索结果的文本相似度计算速率，同时减少特征矩阵所需的存储空间。 (2)针对K-means算法随机选择初始聚类中心导致算法不可重复实现，同时可能使算法陷入局部最优解、减缓算法收敛速率的问题，本文提出了基于悲观准则和近邻算法的初始聚类中心选择算法。通过悲观准则选择K个相距最远的数据作为备选初始聚类中心，然后寻找各个备选初始聚类中心的近邻簇，最后以各个近邻簇的中心作为初始聚类中心。实验结果表明，本文提出的基于悲观准则和近邻算法的初始聚类中心选择算法可以有效的提高K-means算法的聚类效果和收敛速率，同时保证了算法的稳定性。 (3)针对现有聚类搜索引擎产品存在的问题，本文设计并实现了一个基于本文研究成果的聚类搜索引擎原型系统。该原型系统实现了搜索结果获取、预处理、特征表示、初始聚类中心选择、聚类以及搜索结果展示等功能。其运行效果表明，将本文研究成果应用到搜索结果聚类中，能够有效地提高用户获取信息的效率，改善用户的使用体验，同时为将来类似的聚类搜索引擎系统的研发提供了借鉴参考。

目录

声明

第1章 绪论

1.1研究背景与意义

1.2研究现状

1.2.1搜索结果表示方法的研究现状

1.2.2 K-means初始聚类中心的研究现状

1.3研究内容

1.4本文组织结构

第2章 基于位图的文本表示方法研究

2.1 向量空间模型及其存在的问题

2.1.1 向量空间模型思想

2.1.2 向量空间模型存在的问题

2.2 基于位图的文本表示方法

2.2.1 位图文本表示方法的提出

2.2.2 基于位图的文本特征表示

2.2.3 基于位图的文本相似度计算

2.3 实验结果与分析

2.3.1 实验环境

2.3.2 实验数据集和评价指标

2.3.3 实验设置

2.3.4 实验1不同的实验参数对K-means算法聚类效果的影响

2.3.5 实验2不同文本表示方法的聚类效果对比实验

2.3.6 实验3不同文本表示方法的聚类耗时对比实验

2.3.7 实验4不同文本表示方法占用的存储空间对比

2.4 本章小结

第3章 基于悲观准则和近邻算法的初始聚类中心选择算法

3.1 K-means算法存在的问题

3.2 PC算法

3.2.1 悲观准则

3.2.2 PC算法的提出

3.2.3 PC算法满足初始聚类中心第一准则证明

3.2.4 PC算法过程

3.3 PC-KNN初始聚类中心选择算法

3.3.1 PC-KNN算法的提出

3.3.2 PC-KNN算法同时满足初始聚类中心两个准则证明

3.3.3 PC-KNN算法过程

3.4 实验结果与分析

3.4.1 实验环境

3.4.2 实验数据集和评价指标

3.4.3 实验设置

3.4.4 实验1近邻数k对PC-KNN算法的影响

3.4.5 实验2不同初始聚类中心选择算法的聚类效果对比

3.4.6 实验3不同初始聚类中心选择算法的聚类收敛速率对比

3.4.7 实验4不同初始聚类中心选择算法在公开数据集上的聚类效果

3.5 本章小结

第4章 聚类搜索引擎原型系统的设计与实现

4.1 原型系统构建的目的与意义

4.2 原型系统的设计

4.2.1 系统的框架设计

4.2.2 系统的功能模块设计

4.3 原型系统的实现

4.3.1 系统开发环境

4.3.2 数据采集模块实现

4.3.3 数据预处理模块实现

4.3.4 特征表示模块实现

4.3.5 聚类模块实现

4.4 原型系统的运行效果及对比

4.4.1 后端运行效果

4.4.2 前端运行效果及对比

4.5 本章小结

第5章 总结与展望

5.1 工作总结

5.2 展望

致谢

参考文献

攻读学位期间获得与学位论文相关的科研成果目录