基于主动学习的半监督谱聚类算法研究

摘要

聚类技术是用于数据分析的最常应用的技术之一，其应用领域涉及统计学、计算机科学、生物学以及社会学等。传统的聚类算法如常见的K-means算法，EM算法等都是建立在凸状分布的样本空间上，当样本空间分布不为凸时，算法就会陷入局部最优，因而此类算法不适合在任意形状分布的样本空间上解决聚类问题。近些年来，谱聚类算法作为一种新颖的聚类方法受到广泛的关注，并成为了机器学习、模式识别等领域的研究热点。谱方法建立在谱图划分理论基础上。与其他传统聚类技术相比，它能够在任意分布形状的样本空间上进行聚类，并且最终能够收敛于全局最优解。谱聚类算法在聚类过程中，通过特征向量构建更加简化的样本数据空间，这样不仅降低了样本数据的维数，而且还使得样本数据的分布结构在子空间内更为清晰和明显。
　　半监督聚类是指在聚类过程中，利用样本先验信息去指导聚类过程以获得更好的聚类效果。与无监督聚类相比，半监督聚类利用少量的监督信息去指导聚类过程。而半监督聚类算法的性能取决于监督信息。因此，监督信息的选取非常关键。本文首先介绍本课题的研究背景和意义，以及当前谱聚类的研究状况，接着具体介绍了数据挖掘和聚类分析的相关理论，然后着重介绍了谱聚类的相关理论，并对其优势和面临的问题做出分析，最后介绍了本文的研究内容及贡献：
　　①针对半监督聚类的性能取决于所提供的监督信息这个问题，本文构建了一种新的选取成对约束信息的主动学习策略，该策略在聚类过程中主动的选取信息含量丰富的成对约束信息。其主要思想就是：找出同一类中距离远的数据对象对，记为Must-link；找出不同类中距离近的数据对象对，记为Cannot-link。
　　②构造了一种基于主动学习的半监督谱聚类算法，就是在聚类过程中，利用主动学习策略选取得到的成对约束信息，来调整数据对象之间的距离矩阵，使得同一类中各个数据对象分布尽可能紧凑，不同类之间的数据对象分布尽可能分散。通过在UCI数据集上的实验可以证明本文算法的有效性。

目录

封面

中文摘要

英文摘要

目录

1 绪 论

1.1 研究背景和意义

1.2 谱聚类相关研究现状

1.3 本文的研究内容与组织结构

2 数据挖掘与聚类分析

2.1 数据挖掘

2.2 聚类分析

2.3 常用的聚类算法

2.4 本章小结

3 谱聚类理论及算法

3.1 谱图理论

3.2 图的矩阵表示

3.3 图的划分准则

3.4 谱聚类算法分类

3.5 谱聚类算法面临的问题

3.6 本章小结

4 基于主动学习的半监督谱聚类

4.1 引言

4.2 半监督聚类介绍

4.3 主动学习策略

4.4 基于主动学习的半监督谱聚类算法

4.5 本章小结

5 实验与结果分析

5.1 实验环境

5.2 在人工数据集上对比谱聚类算法和K均值算法

5.3 本文算法的实验及结果分析

5.4 本章小结

6 总结与展望

6.1 本文总结

6.2 未来工作展望

致谢

参考文献

附 录