基于谱分析的密度峰值快速聚类算法

来源:用户上传      作者:

　　摘 要：针对密度峰值快速聚类（CFSFDP）算法对不同数据集聚类效果的差异，利用谱聚类对密度峰值快速聚类算法加以改进，提出了一种基于谱分析的密度峰值快速聚类算法CFSFDP-SA。首先，将高维非线性的数据集映射到低维子空间上实现降维处理，将聚类问题转化为图的最优划分问题以增强算法对数据全局结构的适应性;然后，利用CFSFDP算法对处理后的数据集进行聚类。结合这两种聚类算法各自的优势，能进一步提升聚类算法的性能。在5个人工合成数据集（2个线性数据集和3个非线性数据集）与4个UCI数据库中真实数据集上的聚类结果显示，相比CFSFDP算法，CFSFDP-SA算法的聚类精度有一定提升，在高维数据集的聚类精度上最多提高了14%，对原始数据集的适应性更强。
　　关键词：数据聚类;适应性;降维;密度峰值快速聚类;谱分析
　　中图分类号： TP301.6
　　文献标志码：A
　　Abstract： For different clustering effects of Clustering by Fast Search and Find of Density Peaks （CFSFDP） on different datasets， an improved CFSFDP algorithm based on spectral clustering was proposed， namely CFSFDP-SA （CFSFDP based on Spectrum Analysis）. Firstly， a high-dimensional non-linear dataset was mapped into a low-dimensional subspace to realize dimension reduction， then the clustering problem was transformed into the optimal partitioning problem of the graph to enhance the algorithm adaptability to the global structure of the data. Secondly， the CFSFDP algorithm was used to cluster the processed dataset. Combining the advantages of these two clustering algorithms， the clustering performance was further improved. The clustering results of two artificial linear datasets， three artificial nonlinear datasets and four real datasets in UCI show that compared with CFSFDP， the CFSFDP-SA algorithm has higher clustering precision， achieving up to 14% improvement in accuracy for high-dimensional dataset， which means CFSFDP-SA is more adaptable to the original datasets.
　　Key words： data clustering; adaptability; dimension reduction; Clustering by Fast Search and Find of Density Peaks （CFSFDP）; spectrum analysis
　　0 引言
　　聚類算法是一种应用极其广泛的数据分析方法，在机器学习及模式识别领域被称为无监督学习，其过程是将数据分组成多个类或簇，在同一类或簇中的数据相似度较高，不同类或簇中的数据相似度较低[1]。随着各种聚类算法不断的发展和完善，至今已被广泛应用于商业选址、计算机视觉、流量识别、图像分割及数据库等领域[2-3]。然而，随着信息时代的飞速发展，随之而来的是数据量呈指数级增长以及数据自身维度的大幅提高，因此聚类分析算法在原始数据的适应性上面临更大的挑战，在聚类精度和聚类时间上往往都难以得到满意的结果[4]。
　　2014年《Science》上发表了一种新型的密度聚类算法——密度峰值快速聚类（Clustering by Fast Search and Find of Density Peaks， CFSFDP）算法，该算法与其他密度算法相似，能处理形状复杂的聚类，并同时具有指定参数少、自动生成聚类中心并且无需迭代的特点。该算法研究小组利用CFSFDP算法处理Olivetti人脸数据库的实验验证了该算法对高维复杂数据的处理能力。
　　然而，通过进一步实验分析可知，CFSFDP算法在拥有上述众多优点之外仍存在一些缺陷：首先，该算法对于线性可分的低维数据集聚类效果比较好，但对于密度不均匀的样本集或线性不可分数据集的聚类效果并不理想，并且相对稀疏的聚类中心往往容易被淹没，有可能出现同一个类被分裂的情况[5];另外，随着数据维度的不断增大，距离计算过程复杂度不断提高，处理时间也随之上升。因此，本文提出了一种基于谱分析的密度峰值聚类算法（CFSFDP based on Spectrum Analysis， CFSFDP-SA）——通过谱聚类将高维非线性的数据映射到几乎线性的子空间上进行降维处理，再利用CFSFDP算法对处理后的数据进行聚类。谱聚类算法建立在谱图理论的基础上，其本质是利用图的最优划分思路来解决聚类问题[6]，该方法首先计算拉氏矩阵特征值，然后选取前K个最大特征值对应的特征向量来构成一个与原始数据相对应的空间， 最后在该空间中进行聚类。谱聚类较传统聚类算法对数据分布的适应性更强，聚类效果更优秀并且计算量也小很多。经谱聚类预处理的CFSFDP算法既能保留CFSFDP算法中参数少、自动生成聚类中心且无需迭代的特点，也能有效弥补原始数据分布所带来的一些奇异性问题。 　　1 CFSFDP聚类算法原理及性能分析
　　1.1 CFSFDP聚类算法
　　CFSFDP算法是一种基于密度峰值的聚类算法，与传统的
　　基于密度的噪声应用空间聚类（Density-Based Spatial Clustering of Applications with Noise， DBSCAN）算法不同[7]，该算法不需要进行复杂的参数设定，并且可以对不同类型的数据集进行聚类分析。CFSFDP算法的基本思路是：1）通过决策图筛选出密度极点即聚类中心;2）依据密度大小排列将数据点归类到距离其最近且密度比它大的数据点所属的类中[8]。在聚类中心的筛选上主要取决于两个重要参数，局部密度ρ 和相邻密度点距离δ， 二者的乘积越大则成为聚类中心的可能性越大。局部密度的定义是以当前数据点为中心，以dc 为半径的圆形区域内所包含的数据点的数量，如式（1）所示：
　　4 结语
　　本文从聚类算法对高维复杂数据样本适应性这一角度出发，利用谱聚类对CFSFDP算法进行了改进。经过谱聚类的处理，将高维非线性的数据映射到几乎线性的子空间上，提升了CFSFDP聚类算法对非测度样本空间分布的适应性，有效提升了聚类的能力。实验结果表明，本文提出的CFSFDP-SA算法不但保留了CFSFDP算法中参数少、自动生成聚类中心且无需迭代的特点，同时也有效弥补了原始数据分布所带来的一些奇异性问题。但本文所选取的数据集具有一定的局限性，还有更多更为复杂和庞大的高维数据集有待进一步验证。所以我们下一步工作将深入研究CFSFDP改进算法对高维复杂数据集的聚类效果。与此同时，由于谱聚类算法对数据样本具有很强的适应性，并且对非凸分布的聚类能力较好，非常适合用于解决很多实际问题，在此基础上结合简便快捷的CFSFDP算法将会应用于实际领域，因此下一步研究工作也将会结合实际问题来进一步研究CFSFDP改进算法的有效性。
　　参考文献：
　　[1] 蔡晓妍，戴冠中，杨黎斌.谱聚类算法综述[J]. 计算机科学，2008，35（7）：14-18. （CAI X Y， DAI G Z， YANG L B. Survey on spectral clustering algorithms [J]. Computer Science， 2008， 35（7）： 14-18.）
　　[2] 申彦.大规模数据集高效数据挖掘算法研究[D].镇江：江苏大学， 2013：1-8. （SHEN Y. The research of high efficient data mining algorithms for massive data sets [D]. Zhenjiang： Jiangsu University， 2013： 1-8.）
　　[3] 唐東明. 聚类分析及其应用研究[D].成都：电子科技大学， 2010： 13-27. （TANG D M. Study on clustering analysis and its applications [D]. Chengdu： University of Electronic Science and Technology of China， 2010： 13-27.）
　　[4] 贺玲，蔡益朝，杨征.高维数据聚类方法综述[J]. 计算机应用研究，2010，27（1）：23-27. （HE L， CAI Y C， YANG Z. Survey of clustering algorithms for high-dimensional data [J]. Application Research of Computers， 2010， 27（1）： 23-27.）
　　[5] 张文开.基于密度的层次聚类算法研究[D]. 合肥：中国科学技术大学， 2015：15-26. （ZHANG W K. Research on density-based hierarchical clustering algorithm [D]. Hefei： University of Science and Technology of China， 2015： 15-26.）
　　[6] 张蓉，彭宏.一种基于超图模式的高维空间数据聚类方法[J]. 计算机工程，2002，28（7）：54-55. （ZHANG R， PENG H. Method for data clustering in a high dimensional space based on a hypergraph model [J]. Computer Engineering， 2002， 28（7）： 54-55.）
　　[7] 冯少荣，肖文俊. DBSCAN聚类算法的研究与改进[J].中国矿业大学学报，2008，37（1）：105-106. （FENG S R， XIAO W J. An improved DBSCAN clustering algorithm [J]. Journal of China University of Mining & Technology， 2008，37（1）：105-106.）
　　[8] 马春来，单洪，马涛，等.一种基于CFSFDP改进算法的重要地点识别方法研究[J].计算机应用研究，2017，34（1）：136-140. （MA C L， SHAN H， MA T， et al. Research on important places identification method based on improved CFSFDP algorithm [J]. Application Research of Computers， 2017， 34（1）： 136-140.） 　　[9] 马春来，单洪，马涛.一种基于簇中心点自动选择策略的密度峰值聚类算法[J].计算机科学，2016，43（7）：255-258. （MA C L， SHAN H， MA T. Improved density peaks based clustering algorithm with strategy choosing cluster center automatically [J]. Computer Science， 2016，43（7）：255-258.）
　　[10] 蒋礼青，张明新，郑金龙.快速搜索与发现密度峰值聚类算法的优化研究[J].计算机应用研究，2016，33（11）：3251-3254. （JIANG L Q， ZHANG M X， ZHENG J L. Optimization of clustering by fast search and find of density peaks [J]. Application Research of Computers， 2016， 33（11）： 3251-3254.）
　　[11] 李金泽，徐喜荣，潘子琦，等.改进的自适应谱聚类NJW算法[J].计算机科学，2017，44（6）：424-427. （LI J Z， XU X R， PAN Z Q， et al. Improved adaptive spectral clustering NJW algorithm [J]. Computer Science， 2017， 44（6）： 424-427.）
　　[12] 李屆家，郭鹏程，韩忠华.在高维数据上的近邻传播聚类降维研究[J]. 控制工程，2016，23（9）：1419-1422. （LI J J， GUO P C， HAN Z H. Research of affinity propagation clustering dimension reduction on high-dimensional data [J]. Control Engineering of China， 2016，23（9）：1419-1422.）
　　[13] 周世兵，徐振源，唐旭清.基于近邻传播算法的最佳聚类数确定方法比较研究[J].计算机科学，2011，38（2）：225-228. （ZHOU S B， XU Z Y， TANG X Q. Comparative study on method for determining optimal number of clusters based on affinity propagation clustering [J]. Computer Science， 2011， 38（2）： 225-228.）
　　[14] 吕宗磊.对聚类及聚类评价若干问题的研究[D].南京：南京航空航天大学，2009：10-24. （LYU Z L. The research on several issues of clustering and clustering validity indexes [D]. Nanjing： Nanjing University of Aeronautics and Astronautics， 2009： 10-24.）
转载注明来源:https://www.xzbu.com/8/view-14941680.htm