Distributed Density Peaks Clustering Revisited
Jing Lu, Yuhai Zhao, Kian‐Lee Tan, Zhengkui Wang
Abstract
Density Peaks (DP) Clustering organizes data into clusters by finding peaks in dense regions. This involves computing density ( <inline-formula><tex-math notation="LaTeX">$\rho$</tex-math></inline-formula> ) and distance ( <inline-formula><tex-math notation="LaTeX">$\delta$</tex-math></inline-formula> ) of every point. As such, though DP has been very effective in producing high quality clusters, their complexity is O( <inline-formula><tex-math notation="LaTeX">$N^2$</tex-math></inline-formula> ) where <inline-formula><tex-math notation="LaTeX">$N$</tex-math></inline-formula> is the number of data points. In this paper, we propose a fast distributed density peaks clustering algorithm, FDDP, based on the z-value index. In FDDP, we first employ the z-value index to map multi-dimensional data points into one dimensional space, and then range-partition the data according to the z-value to balance the load across the processing nodes. We ensure minimal overlapping range to handle computations at the boundary points. We also propose FC, an efficient algorithm that employs a forward computing strategy to calculate <inline-formula><tex-math notation="LaTeX">$\rho$</tex-math></inline-formula> linearly. Additionally, we propose another algorithm, CB, which uses a caching and efficient searching strategy to compute <inline-formula><tex-math notation="LaTeX">$\delta$</tex-math></inline-formula> . Moreover, FDDP is able to reduce the time complexity from <inline-formula><tex-math notation="LaTeX">$O(N^2)$</tex-math></inline-formula> to <inline-formula><tex-math notation="LaTeX">$O(N\cdot log(N))$</tex-math></inline-formula> . We provide a theoretical analysis of FDDP and evaluated FDDP empirically. Our experimental results show that FDDP outperforms the state-of-the-art algorithms significantly.