快速识别密度骨架的聚类算法

摘要

针对如何快速寻找密度骨架、提高高维数据聚类准确性的问题,提出一种快速识别高密度骨架的聚类(ECLUB)算法.首先,在定义了对象局部密度的基础上,根据互k近邻一致性及近邻点局部密度关系,快速识别出高密度骨架;然后,对未分配的低密度点依据邻近关系进行划分,得到最终聚类.人工合成数据集及真实数据集上的实验验证了所提算法的有效性,在Olivetti Face数据集上的聚类结果显示,ECLUB算法的调整兰德系数(ARI)和归一化互信息(NMI)分别为0.8779和0.9622.与经典的基于密度的聚类算法(DBSCAN)、密度中心聚类算法(CFDP)以及密度骨架聚类算法(CLUB)相比,所提ECLUB算法效率更高,且对于高维数据聚类准确率更高.%In order to find density backbone quickly and improve the accuracy of high-dimensional data clustering results,a new algorithm for fast recognition of high-density backbone was put forward,which was named Efficient CLUstering based on density Backbone (ECLUB) algorithm.Firstly,on the basis of defining the local density of object,the high-density backbone was identified quickly according to the mutual consistency of k-nearest neighbors and the local density relation of neighbor points.Then,the unassigned low-density points were divided according to the neighborhood relations to obtain the final clustering.The experimental results on synthetic datasets and real datasets show that the proposed algorithm is effective.The clustering results of Olivetti Face dataset show that,the Adjusted Rand Index (ARI) and Normalized Mutual Information (NMI) of the proposed ECLUB algorithm is 0.877 9 and 0.962 2 respectively.Compared with the Density-Based Spatial Clustering of Applications with Noise (DBSCAN) algorithm,Clustering by Fast search and find of Density Peaks (CFDP) algorithm and CLUstering based on Backbone (CLUB) algorithm,the proposed ECLUB algorithm is more efficient and has higher clustering accuracy for high-dimensional data.