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