Fast density peak clustering for large scale data based on kNN

Density Peak (DPeak) clustering algorithm is not applicable for large scale data, due to two quantities, i.e, rho and delta, 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(nlog(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 delta for them, is also proposed with complexity O(n). Experimental results show that FastDPeak is effective and outperforms other variants of DPeak. (C) 2019 Elsevier B.V. All rights reserved.