A novel tree structure-based multi-prototype clustering algorithm

Abstract

Density-peak clustering (DPC) is a novel clustering algorithm that has received much attention from researchers. Its principle is to identify the cluster center of the data by density and distance. However, the density-peak clustering algorithm still suffers from poor clustering results due to irrational choices of cluster centers and misallocating samples. To tackle these problems, a novel tree structure-based multi-prototype clustering algorithm (MPCTS) is proposed in this paper. Firstly, a division-merger method is adopted to divide the dataset into multiple peak clusters based on multi-prototype clustering, which could minimize the impact of high-density sample points on the subsequent sample point assignments. Secondly, the KNN nearest-neighbor search strategy is improved to quickly obtain the sub-cluster center in each peak cluster to overcome the defect of irrational selection of initial cluster centers. Afterward, a tree-based decay strategy is designed to evaluate the correlation between sample points, and a tree-based association strategy is designed to achieve the merging of multiple peak clusters to tackle the sample points misallocation problem. Finally, the extensive experiments on clustering task are conducted over several benchmark synthetic and real datasets to verify the efficiency and superiority of the proposed MPCTS.

Keywords

• Density peaks clustering
• Tree structure
• KNN nearest-neighbor search
• Cluster centers