An improved density peaks clustering algorithm based on natural neighbor with a merging strategy

Density peaks clustering (DPC) is a novel density-based clustering algorithm that identifies center points quickly through a decision graph and assigns corresponding labels to remaining non-center points. Although DPC can identify clusters with any shape, its clustering performance is still restricted by some aspects. Firstly, DPC works poorly on manifold datasets with different densities. Secondly, DPC is sensitive to the cutoff parameter dc. For the sake of addressing these issues and improving the performance of DPC, an improved density peaks clustering algorithm based on natural neighbor with a merging strategy (IDPC-NNMS) is proposed. IDPC-NNMS identifies a natural neighbor set of each data to obtain its local density adaptively, which can effectively eliminate the impact of the cutoff parameter on final results. Then, sub-clusters are formed after selecting as many center points as possible and allocating labels to remaining non-center points. These sub-clusters are merged by a novel merging strategy until the end conditions are satisfied. The performance of IDPC-NNMS is evaluated on both synthetic and real-world datasets, which fully proves the effectiveness and superiority of the proposed IDPC-NNMS algorithm.