GAS-DBSCAN: A Grid-Based Adaptive Sampling Method for DBSCAN Clustering Under Skewed Data Distribution

Clustering is one of the important methods for knowledge acquisition, which is the process of analyzing data by grouping instances based on their similarities and dissimilarities. DBSCAN is a notable density-based clustering algorithm, but its reliance on implicit neighborhood queries causes significant computational overhead, particularly in challenging scenarios. While there have been proposals to alleviate this overhead through sampling techniques, traditional sampling approaches tend to be random. Randomness in sampling can overlook smaller, less dense clusters in skewed distributions, ultimately compromising clustering precision and reliability. However, more sophisticated sampling methods, while introducing additional computation, may not always enhance efficiency. We propose Grid-based Adaptive Sampling for DBSCAN, named GAS-DBSCAN, a method specifically designed to address sampling imbalance in density-based clustering. Through grid-based adaptive mechanisms, our approach significantly improves the detection of smaller clusters. Experimental results on various datasets demonstrate a threefold improvement in sampling accuracy and 267% in clustering accuracy compared to existing methods under skewed distributions, with theoretical analysis further validating its efficiency.