Fast hierarchical clustering of local density peaks via an association degree transfer method

• DOI: 10.1016/j.neucom.2021.05.071
• Publication Date: 2021-05-25T16:19:30Z
• Authors: Junyi Guan; Sheng Li; Xiongxiong He; Jinhui Zhu; Jiajia Chen
• Keywords: Degree (music); Association (psychology); Hierarchical clustering

Abstract Density Peak clustering (DPC) as a novel algorithm can fast identify density peaks. But it comes along with two drawbacks: its allocation strategy may produce some non-adjacent associations that may lead to poor clustering results and even cause the malfunction of its cluster center selection method to mistakenly identify cluster centers; it may perform poorly with its high complex O ( n 2 ) when comes to large-scale data. Herein, a fast hierarchical clustering of local density peaks via an association degree transfer method (FHC-LDP) is proposed. To avoid DPC’s drawbacks caused by non-adjacent associations, FHC-LDP only considers the association between neighbors and design an association degree transfer method to evaluate the association between points that are not neighbors. FHC-LDP can fast identify local density peaks as sub-cluster centers to generate sub-clusters automatically and evaluate the similarity between sub-clusters. Then, by analyzing the similarity of sub-cluster centers, a hierarchical structure of sub-clusters is built. FHC-LDP replaces DPC’s cluster center selection method with a bottom-up hierarchical approach to ensure sub-clusters in each cluster are most similar. In FHC-LDP, only neighbor information of data is required, so by using a fast KNN algorithm, FHC-LDP can run about O ( nlog ( n ) ) . Experimental results demonstrate FHC-LDP is remarkably superior to traditional clustering algorithms and other variants of DPC in recognizing cluster structure and running speed.