Journal: Information Sciences

Key Words: Clustering Density peaks Spectral clustering Local density Similarity between trees

Abstract: Clustering by fast search and find of density peaks (DPC) is a widely used and studied clustering algorithm. In this article, we notice that DPC can achieve highly accurate clustering results when restricted to local neighborhoods. Therefore, by investigating density information in local neighborhoods, we propose to capture latent structures in data with family trees, which can reflect density dominations among nearest neighbors of data. A data set will then be partitioned into multiple family trees. In order to obtain the final clustering result, instead of exploiting the error-prone allocation strategy of DPC, we first elaborately design a novel similarity measure for family trees, characterizing not only the distance between data points, but also the structure of trees. Then, we adapt graph cut for the corresponding connection graph to also take global structural information into account. Extensive experiments on both real-world and synthetic data sets show that the proposed algorithm can outperform several prominent clustering algorithms for most of the cases, including the DPC and spectral clustering algorithms and some of their latest variants. We also analyze the robustness of the proposed algorithm w.r.t. hyper-parameters and its time complexity, as well as the necessity of its components through ablation study.

Note: Code available at: https://github.com/ZhiguoLong/LDP-SC_code

Co-author: Yang Gao,Yuqin Yao,Tianrui Li

First Author: Zhiguo Long

Indexed by: 期刊论文

Correspondence Author: Hua Meng

Discipline: Engineering

Document Type: J

Volume: 600

Page Number: 263-286 (Click to view details and code link)

Translation or Not: no

Date of Publication: 2022-04-04

Included Journals: SCI

Links to published journals: https://doi.org/10.1016/j.ins.2022.03.091