Fast density peak clustering for large scale data based on kNN

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.