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.
BibTeX
@article{lu2022distributed,
  author = {Jing Lu and Yuhai Zhao and Kian-Lee Tan and Zhengkui Wang},
  title = {{Distributed Density Peaks Clustering Revisited}},
  journal = {IEEE Trans. Knowl. Data Eng.},
  year = {2022},
  url = {https://openreview.net/forum?id=9e_XnAkXuOv},
}

Loading related content...

Figure