文档介绍：基于谱分析的密度峰值快速聚类算法
摘 要:针对密度峰值快速聚类(CFSFDP)算法对不同数据集聚类效果的差异,利用谱聚类对密度峰值快速聚类算法加以改进,提出了一种基于谱分析的密度峰值快速聚类算法CFSFDP-SA。首先,将高维ty Peaks, CFSFDP)算法,该算法与其他密度算法相似,能处理形状复杂的聚类,并同时具有指定参数少、自动生成聚类中心并且无需迭代的特点。该算法研究小组利用CFSFDP算法处理Olivetti人脸数据库的实验验证了该算法对高维复杂数据的处理能力。
然而,通过进一步实验分析可知,CFSFDP算法在拥有上述众多优点之外仍存在一些缺陷:首先,该算法对于线性可分的低维数据集聚类效果比较好,但对于密度不均匀的样本集或线性不可分数据集的聚类效果并不理想,并且相对稀疏的聚类中心往往容易被淹没,有可能出现同一个类被分裂的情况[5];另外,随着数据维度的不断增大,距离计算过程复杂度不断提高,处理时间也随之上升。因此,本文提出了一种基于谱分析的密度峰值聚类算法(CFSFDP based on Spectrum Analysis, CFSFDP-SA)——通过谱聚类将高维非线性的数据映射到几乎线性的子空间上进行降维处理,再利用CFSFDP算法对处理后的数据进行聚类。谱聚类算法建立在谱图理论的基础上,其本质是利用图的最优划分思路来解决聚类问题[6],该方法首先计算拉氏矩阵特征值,然后选取前K个最大特征值对应的特征向量来构成一个与原始数据相对应的空间, 最后在该空间中进行聚类。谱聚类较传统聚类算法对数据分布的适应性更强,聚类效果更优秀并且计算量也小很多。经谱聚类预处理的CFSFDP算法既能保留CFSFDP算法中参数少、自动生成聚类中心且无需迭代的特点,也能有效弥补原始数据分布所带来的一些奇异性问题。 1 CFSFDP聚类算法原理及性能分析
CFSFDP聚类算法
CFSFDP算法是一种基于密度峰值的聚类算法,与传统的
基于密度的噪声应用空间聚类(Density-Based Spatial Clustering of Applications with Noise, DBSCAN)算法不同[7],该算法不需要进行复杂的参数设定,并且可以对不同类型的数据集进行聚类分析。CFSFDP算法的基本思路是:1)通过决策图筛选出密度极点即聚类中心;2)依据密度大小排列将数据点归类到距离其最近且密度比它大的数据点所属的类中[8]。在聚类中心的筛选上主要取决于两个重要参数,局部密度ρ 和相邻密度点距离δ, 二者的乘积越大则成为聚类中心的可能性越大。局部密度的定义是以当前数据点为中心,以dc 为半径的圆形区域内所包含的数据点的数量,如式(1)所示:
4 结语
本文从聚类算法对高维复杂数据样本适应性这一角度出发,利用谱聚类对CFSFDP算法进行了改进。经过谱聚类的处理,将高维非线性的数据映射到几乎线性的子空间上,提升了CFSFDP聚类算法对非测度样本空间分布的适应性,有效提升了聚类的能力。实验结果表明,本文提出的CFSFDP-SA算法不但保留了CFSFDP算法中参数少、自动生成聚类中心且无需迭代的特点,同时也有效弥补了原始数据分布所带来的一些奇异性问题。但本文所选取的数据集具有一定的局限性,还