Constrained Density-Based Spatial Clustering of Applications with Noise (DBSCAN) using hyperparameter optimization
Jong-Won Kim, Hyeseon Lee, Young Myoung Ko
Abstract
This article proposes a hyperparameter optimization method for density-based spatial clustering of applications with noise (DBSCAN) with constraints, termed HC-DBSCAN. While DBSCAN is effective at creating non-convex clusters, it cannot limit the number of clusters. This limitation is difficult to address with simple adjustments or heuristic methods . We approach constrained DBSCAN as an optimization problem and solve it using a customized alternating direction method of multipliers Bayesian optimization (ADMMBO). Our custom ADMMBO enables HC-DBSCAN to reuse clustering results for enhanced computational efficiency, handle integer-valued parameters, and incorporate constraint functions that account for the degree of violations to improve clustering performance. Furthermore, we propose an evaluation metric, penalized Davies–Bouldin score , with a computational cost of O ( N ) . This metric aims to mitigate the high computational cost associated with existing metrics and efficiently manage noise instances in DBSCAN. Numerical experiments demonstrate that HC-DBSCAN, equipped with the proposed metric, generates high-quality non-convex clusters and outperforms benchmark methods on both simulated and real datasets.