Fast density estimation for density-based clustering methods

Density-based clustering algorithms are widely used for discovering clusters in pattern recognition and machine learning. They can deal with non-hyperspherical clusters and are robust to outliers. However, the runtime of density-based algorithms is heavily dominated by neighborhood finding and density esti-mation which is time-consuming. Meanwhile, the traditional acceleration methods using indexing tech-niques such as KD-tree may not be effective when the dimension of the data increases. To address these issues, this paper proposes a fast range query algorithm, called Fast Principal Component Analysis Pruning (FPCAP), with the help of the fast principal component analysis technique in conjunction with geometric information provided by the principal attributes of the data. Based on FPCAP, a framework for accelerating density-based clustering algorithms is developed and successfully applied to accelerate the Density Based Spatial Clustering of Applications with Noise (DBSCAN) algorithm and the BLOCK-DBSCAN algorithm, and improved DBSCAN (called IDBSCAN) and improved BLOCK-DBSCAN (called BLOCK-IDBSCAN) are then obtained, respectively. IDBSCAN and BLOCK-IDBSCAN preserve the advantage of DBSCAN and BLOCK-DBSCAN, respectively, while greatly reducing the computation of redundant dis-tances. Experiments on seven benchmark datasets demonstrate that the proposed algorithm improves the computational efficiency significantly.(c) 2023 Elsevier B.V. All rights reserved.

Automated summary

Density-based clustering algorithms are widely used in pattern recognition and machine learning to handle non-hyperspherical clusters and outliers. However, runtime is often dominated by time-consuming neighborhood finding and density estimation processes. This paper proposes a fast range query algorithm, FPCAP, which leverages fast principal component analysis and geometric information to accelerate density-based clustering algorithms like DBSCAN and BLOCK-DBSCAN. The proposed algorithm, shown through experiments on benchmark datasets, significantly improves computational efficiency while preserving the advantages of the original algorithms.