一种截断距离和聚类中心自适应的聚类算法

A Clustering Algorithm with Adaptive Cut-off Distance and Cluster Centers

【目的】研究一种新的聚类算法,以改进密度峰值聚类算法无法自动计算截断距离以及需要人工参与选择聚类中心的不足。【方法】首先提出一种基于信息熵的截断距离自适应算法,实现了DPC算法截断距离的自适应;然后根据排序图中权值的斜率变化趋势确定拐点,自动划分出聚类中心与非聚类中心的界限,实现聚类中心的自动选择。【结果】通过在UCI数据集与人工数据集上的仿真实验,对DBSCAN算法、DPC算法、DGCCD算法、ACP算法与ADPC算法进行聚类性能的比较,结果表明ADPC算法不仅能够自动选择截断距离与聚类中心,在准确率、标准互信息(NMI)、F-measure值等性能上也有较大的提升,同时证明了改进算法在处理移动终端定位数据上的有效性。【局限】主要针对低维度数据集,面对高维度数据集略显乏力,同时未能兼顾处理大数据集时的效率问题。【结论】ADPC算法能够准确选择聚类中心和截断距离,对于低维度、任意形状簇的处理效果良好。

[Objective] This paper develops a new clustering algorithm, aiming to automatically calculate the cut-off distance and select the cluster centers. [Methods] First, we proposed a new adaptive algorithm based on information entropy and the cut-off distance. Then, we extracted the cluster centers, with the help of inflection points determined by the slope trend of the weight in the sorting chart. Finally, we evaluated the performance of the ADPC algorithm to those of the DBSCAN, DPC, DGCCD, and ACP algorithms using UCI and manmade datasets. [Results] The ADPC algorithm automatically identified the cluster centers and significantly improved the precision, F-measure, normalized mutual information measurement and runtime. [Limitations] The proposed algorithm＇s performance with high-dimension data as well as its efficiency to process large data sets need to be improved. [Conclusions] The proposed ADPC algorithm could effectively identify clustering centers and the cut-off distance with low-dimension or arbitrary data sets.