论文部分内容阅读
聚类分析是机器学习的经典问题。聚类可以分为无监督聚类和半监督聚类,无监督聚类是通过抽取数据中“潜在”结构,将相似数据组成类或类的层次结构,不需要任何先验和假设。在现有的无监督聚类算法中,K-均值聚类作为一种基于中心的聚类算法,是最简单、使用最普遍的方法之一。它在紧凑的超球形分布的数据集合上有很好的性能,然而当数据结构是非凸的,或数据点彼此交叠严重时,K-均值算法往往会失效,而且算法利用迭代最优化方法寻找最优解,因而不能保证收敛到全局最优解。新近出现的一种无监督聚类算法—谱聚类算法克服了K-均值算法的缺点,具有识别非凸分布聚类的能力,适合于求解实际问题,而且实现简单,不会陷入局部最优解,且能避免数据的过高维数所造成的奇异性问题。本文基于谱聚类算法做了以下两方面的研究。1.提出了一种新的聚类算法--层次谱聚类算法。层次谱聚类算法融合了层次聚类算法较高的聚类正确率的优点,和谱聚类算法避免聚类过程中歪斜划分的优点。实验结果表明提出的层次谱聚类算法的聚类正确率比层次聚类算法、谱聚类算法的聚类正确率都要高,同时层次谱聚类算法与层次聚类算法相比又大大节省了计算时间。2.提出了一种基于最近邻传递的谱聚类算法。利用谱聚类的维数缩减特性获得数据在映射空间的分布,在此基础上利用最近邻传递聚类算法在映射空间中对样本进行聚类。该方法通过谱映射为后续的最近邻传递聚类提供低维而紧致的输入。而最近邻传递聚类算法具有快速收敛到全局最优并且对初始化不敏感的特性。对于MPEG-7图像库及其子图像库的聚类结果验证了最近邻传递谱聚类算法用于图像聚类的有效性。