Fast density peak clustering for large scale data based on kNN

• DOI: 10.1016/j.knosys.2019.06.032
• Publication Date: 2019-07-03T13:17:19Z
• Authors: Yewang Chen; Xiaoliang Hu; Wentao Fan; Lianlian Shen; Zheng Zhang; Xin Liu; Jixiang Du; Haibo Li; Yi Chen; Hailin Li
• Keywords: 0202 electrical engineering, electronic engineering, information engineering; 02 engineering and technology

Abstract Density Peak (DPeak) clustering algorithm is not applicable for large scale data, due to two quantities, i.e, ρ and δ , are both obtained by brute force algorithm with complexity O ( n 2 ) . Thus, a simple but fast DPeak, namely FastDPeak, 1 is proposed, which runs in about O ( n l o g ( n ) ) expected time in the intrinsic dimensionality. It replaces density with kNN-density, which is computed by fast kNN algorithm such as cover tree, yielding huge improvement for density computations. Based on kNN-density, local density peaks and non-local density peaks are identified, and a fast algorithm, which uses two different strategies to compute δ for them, is also proposed with complexity O ( n ) . Experimental results show that FastDPeak is effective and outperforms other variants of DPeak.