Adaptive and Robust DBSCAN with Multi-agent Reinforcement Learning
Hao Peng, Xiang Huang, Shuo Sun, Ruitong Zhang, Philip S. Yu · 2025
Read Adaptive and Robust DBSCAN with Multi-agent Reinforcement Learning by Hao Peng, Xiang Huang, Shuo Sun, Ruitong Zhang, Philip S. Yu (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-04339.txt.
Introduction
Hao Peng and co-authors rebuilt in 2025 a classic clustering algorithm so it can tune itself across datasets whose density swings wildly. DBSCAN finds groups of any shape and shrugs off noise, but one setting rarely fits a whole dataset. Their framework first builds a two-level encoding tree that splits the data into density zones.
Each zone gets its own learning agent. Guided by reinforcement learning with a weak supervision signal, the agents hunt for the best local settings, adjusting direction as the clusters respond. A recursive search keeps the exploration affordable at scale. Across nine synthetic datasets and one real one, accuracy jumped by well over double on standard scores. The authors say self-tuning makes density clustering practical again.
Catalog record
| CREATOR | Hao Peng, Xiang Huang, Shuo Sun, Ruitong Zhang, Philip S. Yu |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 85 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-04339
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Adaptive and Robust DBSCAN with Multi-agent Reinforcement Learning Hao Peng, Xiang Huang, Shuo Sun, Ruitong Zhang, Philip S. Yu Abstract DBSCAN, a well-known density-based clustering algorithm, has gained widespread popularity and usage due to its effectiveness in identifying clusters of arbitrary shapes and handling noisy data. However, it encounters challenges in producing satisfactory cluster results when confronted with datasets of varying density scales, a common scenario in real-world applications. In this paper, we propose a novel A daptive and R obust DBSCAN with Multi-agent Reinforcement Learning cluster framework, namely AR-DBSCAN . First, we model the initial dataset as a two-level encoding tree and categorize the data vertices into distinct density partitions according to the information uncertainty determined in the encoding tree. Each partition is then assigned to an agent to find the best clustering parameters without manual assistance. The allocation is density-adaptive, enabling AR-DBSCAN to effectively handle diverse density distributions within the dataset by utilizing distinct agents for different partitions. Second, a multi-agent deep reinforcement learning guided automatic parameter searching process is designed. The process of adjusting the parameter search direction by perceiving the clustering environment is modeled as a Markov decision process. Using a weakly-supervised reward training policy network, each agent adaptively learns the optimal clustering parameters by interacting with the clusters. Third, a recursive search mechanism adaptable to the data’s scale is presented, enabling efficient and controlled exploration of large parameter spaces. Extensive experiments are conducted on nine artificial datasets and a real-world dataset. The results of offline and online tasks show that AR-DBSCAN not only improves clustering accuracy by up to 144.1% and 175.3% in the NMI and ARI metrics, respectively, but also is capable of robustly finding dominant parameters. Journal: Artificial Intelligence 1 Introduction Clustering serves as a fundamental technology for advancing machine intelligence [ 1 , 2 , 3 ] . It reveals the intrinsic structure of data and aids machine intelligence systems in organizing and comprehending information. Clustering algorithms aim to divide data into multiple clusters based on specific rules. By grouping similar samples (defined by similar distance measurement) into the same cluster and allocating dissimilar samples into different ones, these algorithms reveal the differences between samples and the underlying patterns connecting them. As a typical density-based clustering method, Density-Based Spatial Clustering of Applications with Noise (DBSCAN) [ 4 ] defines clusters as the maximal set of density-connected points. It partitions regions of sufficient density into different clusters and identifies clusters with arbitrary shapes in spatial datasets with noise. Due to its simplicity and practicality, DBSCAN has gained widespread recognition and is extensively used in various scientific and engineering fields, such as image segmentation [ 5 ] , commercial research [ 6 ] , biological analysis [ 7 ] , neuroscience [ 8 ] , target recognition [ 9 ] , and more [ 10 ] . Figure 1: The challenge of parameter searching through a single agent. Finding the optimal parameter combination of Eps and MinPts in complex situations characterized by disparate density in the data is difficult. The gray vertices depict unclustered noise points. However, the two predefined parameters of DBSCAN, i.e., the distance of the cluster formation Eps and the minimum data objects required inside the cluster MinPts , which typically need to be determined manually, pose four challenges to the clustering process. First, density variety challenge. When the data density distribution is not uniform, and the intra-cluster distance varies significantly, DBSCAN with only one parameter combination can hardly perform well. In the scenario depicted in Figure 1 , certain intra-cluster distances are small while others are large, eg., Cluster 1 and Cluster 2 in the upper left subfigure of Figure 1 . When determining the value of Eps based on a smaller cluster scale, points with slightly larger distances may be classified as noise points incorrectly (the upper half of Figure 1 ). Conversely, if Eps is set too high, different clusters may be erroneously merged into a single cluster (the bottom half of Figure 1 ). Some researchers have attempted to address this issue [ 11 , 12 , 13 ] by defining parameters for different groups based on varying densities, but they require introducing specific prior information, such as the total number of clusters or the value of MinPts . Therefore, the first challenge lies in devising a method to achieve accurate clustering when clusters have varying densities. Second, parameters free challenge. The clustering results are greatly subject to the two parameters Eps and MinPts , but they must be determined beforehand based on practical experience. Existing methods [ 14 , 15 , 13 ] based on the k -distance estimate the possible values of the Eps through significant changes in the curve of the k-dist plot, but it still requires manual determination of the MinPts parameter beforehand. Although some improved DBSCAN methods avoid the simultaneous adjustment of Eps and MinPts to varying degrees, they also need to pre-determine the cutoff distance parameter [ 16 ] , grid parameter [ 17 ] , Gaussian distribution parameter [ 18 ] , fixed MinPts parameter [ 19 , 5 ] , or k -NN parameter and relative density threshold parameter [ 20 ] . Therefore, the second challenge is to automatically find optimal cluster parameters for DBSCAN without the need for manual tuning based on expert knowledge. Third, adaptive policy challenge. Traditional parameter search methods for DBSCAN, which rely on fixed patterns [ 15 , 14 , 21 ] , often face bottlenecks when dealing with unconventional data problems. This is due to the varying data distributions and cluster characteristics in clustering tasks. Even some hyperparameter optimization methods [ 22 , 23 , 24 ] that utilize an external clustering evaluation index based on label information as the objective function are ineffective when data label information is absent. On the other hand, approaches [ 25 , 26 ] that only use the internal clustering evaluation index as the objective function are limited by accuracy issues, even though they do not require label information. Therefore, considering the absence of label information, the third challenge is effectively and adaptively adjusting the parameter search policy for the data in each process. Fourth, search efficiency challenge. The parameter space expands as the data scale increases. However, an excessively large search space hinders search efficiency [ 27 ] and introduces noise that affects clustering accuracy [ 28 ] . Thus, the fourth challenge lies in enhancing search efficiency while upholding high clustering accuracy. In recent years, the theory of structural entropy [ 29 ] has demonstrated significant advantages in graph-structured data analysis [ 30 , 31 , 32 , 33 , 34 ] . An abstracting partitioning tree, also named encoding tree , is generated from a graph by minimizing structural entropy, where each node in the encoding tree has its corresponding node structural entropy. The structural entropy of the whole graph is calculated by summing up all non-root nodes’ structural entropy in the encoding tree 1 1 1 Vertices are defined in the graph, and nodes are in the tree. . Meanwhile, by aggregating the structural entropy of the leaf nodes to the intermediate nodes within the encoding tree, it becomes feasible to quantify