DPC-DNG: Graph-based label propagation of k-nearest higher-density neighbors for density peaks clustering

Density peaks clustering (DPC) algorithm is a novel density-based clustering approach that effectively determines cluster centers from a decision graph and groups objects by assigning non-center objects to the same cluster as their nearest higher-density neighbor. Although DPC can allocate clusters of arbitrary shapes, its single-chain label propagation mechanism has the risk of "chain error", where an object assigned an incorrect label causes its subordinates to also be assigned the same incorrect label. Hence, DPC is unable to effectively group objects that are located in overlapping areas between clusters, which leads to unsatisfactory clustering results. To address this issue, this study proposes the graph-based label propagation of k-nearest higher-density neighbor for density peaks clustering (DPC-DNG). DPC-DNG extends the single-chain label propagation of DPC to a graph-based multi-chain label propagation that assigns labels to objects from their k-nearest higher-density neighbors. First, based on k-nearest higher-density neighbors and the selected cluster centers, a symmetric density-based neighbor graph (DNG) is constructed. Second, to assign labels to objects, a classic graph-based label propagation mechanism is utilized in conjunction with DNG. To validate our method, we carry out comprehensive experiments on 6 synthetic and 12 real datasets. Statistically speaking, the results show that our method has improved the clustering performance of DPC and exhibits promising performance over other state-of-the-art DPC-related methods.