An Adaptive Clustering Algorithm by Finding Density Peaks

摘要

Clustering by fast search and find of density peaks (shorted as DPC) is a powerful clustering algorithm. However it has a fatal problem that once a point is assigned erroneously, then there may be many more points will be assigned to error clusters. Furthermore, its density peaks need to be selected manually, so as to the clustering may be poor. Lastly it cannot find density peaks from sparse cluster when the data set comprises dense and sparse clusters simultaneously. This paper proposed a new clustering algorithm to overcome the aforementioned weaknesses of DPC by adaptively finding density peaks and assigning points to their most proper clusters. The new density p_i of point i was defined. The adjusting strategy for γ_i, and the assignment strategy for remaining points, and the merging strategy for erroneously partitioned clusters were proposed. Many challengeable synthetic datasets were used to test the power of the proposed algorithm. The experimental results demonstrate that the proposed algorithm can correctly detect clusters with any arbitrary shapes. Its performance is superior to DPC and its variants in terms of bench mark metrics, such as clustering accuracy (Acc), adjusted mutual information (AMI) and adjusted rand index (ARI).