论文部分内容阅读
谱聚类(Spectral Clustering)算法是基于谱图划分的一种聚类算法,其本质是将聚类问题转化为图的最优分割问题。对给定的数据集聚类,可以先构造一个无向加权图,其中图的顶点表示数据样本,顶点用边建立连接,图的每条边都有一个权值,用来描述顶点之间的相似性。把数据样本点聚成多个类相当于将图划分成若干个子图,使划分后每个子图内部的连接权值最大即相似度最大,而子图之间的连接权值最小即相似度最小。如今,随着计算机以及信息技术的迅速发展,数据已经成为了一种有价值的资源,谱聚类作为数据分析中的一种有效方法,可以挖掘不同数据之间的内在联系,为决策者提供有价值的信息。由于谱聚类算法具有能在任意形状的样本空间上聚类且收敛于全局最优的优点,在很多领域得到了很好的应用。尽管谱聚类有很多优点,但在构造相似矩阵时对尺度参数敏感以及对多尺度数据集聚类效果不太理想,以及处理大规模复杂数据时,仍面临时间和空间复杂度过高的难题。目前为止,谱聚类还是处于发展得阶段,仍然面临诸多的问题需要进一步的研究和改进。本文主要从尺度参数、复杂度和大规模数据几个方面,深入分析了现有谱聚类算法的一些不足,并提出了相应的解决办法。本文研究的具体的内容如下:(1)针对谱聚类算法在构造相似矩阵时对尺度参数敏感以及对多尺度数据集聚类效果不太理想的问题,提出了基于密度敏感的改进自适应谱聚类算法。首先利用密度差来调整簇类样本点之间的相似度构造新的相似矩阵函数,然后利用新的相似矩阵构造拉氏矩阵,选取拉氏矩阵的前k个最大特征值对应的特征向量组成新的向量空间,新的向量空间中的点与原始数据一一对应,最后引入K-means聚类算法对数据点进行聚类,该算法在降低对尺度参数的敏感性的同时又改善了对多尺度数据集的处理,通过在人工数据集以及UCI数据集仿真实验结果表明,提出的算法具有较优的聚类效果。(2)谱聚类算法通常是采用高斯核作为相似性度量,并利用所有可用的特征来构建具有欧氏距离的相似度矩阵,数据集复杂度会影响其谱聚类性能,因此提出了一种基于AFS的改进谱聚类算法。首先结合AFS算法,利用识别特征来衡量更合适的数据成对相似性,生成更强大的相似度矩阵;再有效地利用Nystro?m采样算法,计算采样点间以及采样点和剩余点间的相似度矩阵去降低计算的复杂度;最后通过在不同数据集以及图像分割上进行实验,说明了提出算法的有效性。(3)谱聚类是一种具有优越聚类性能的聚类算法,其能在任意形状的数据样本上进行聚类且收敛于全局最优,尽管谱聚类算法在规模较小的数据集上聚类性能良好,但数据集总数N足够大时,谱聚类算法在存储器使用和计算时间就存在可扩展性的问题,针对上述问题,提出了一种基于大数据的快速核谱聚类(FKSC)算法。该算法首先通过Nystro?m算法采样m(m(28)N)个点构成一个子集,这m个子集构成样本子矩阵,然后用样本子矩阵的特征向量逼近原始矩阵的特征空间,再通过改进加权核PCA结合k-means算法对数据集进行聚类分析,因为避免了拉普拉斯矩阵的构造及其特征分解,使得计算复杂度以及算法的执行时间降低。通过在不同数据集上使用不同聚类算法进行对比实验,验证了所提算法的有效性和快速性。