A Graph Adaptive Density Peaks Clustering algorithm for automatic centroid selection and effective aggregation

As a clustering approach based on density, Density Peaks Clustering algorithm (DPC) has conspicuous superiorities in searching and finding density peaks. Nevertheless, DPC has obvious deficiencies in centroid selection and aggregation process affected by differences in data shape and density distribution, which can easily cause problems in centroid selection and trigger domino effect. Therefore, a Graph Adaptive Density Peaks Clustering algorithm based on Graph Theory (called GADPC) is proposed to automatically select centroid and aggregate more effectively. The improvement of GADPC can be subdivided into the two steps. First, the clustering centroids are automatically selected based on the turning angle θ and the graph connectivity of centroids. Second, the remaining points are aggregated towards the corresponding clustering centroid. According to the improved principle, they belong to the closer point which has stronger graph connectivity and higher density. Theoretical analyses and experimental data indicate that GADPC, compared with DBSCAN, K-means and DPC, is more feasible and effective in processing some data sets with varying density and non-spherical distribution such as Jain and Spiral.