Distributed Density Peaks Clustering Revisited
Lists
Only you see this
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...