Abstract
DBSCAN, a well-known density-based clustering algorithm, has gainedwidespread popularity and usage due to its effectiveness in identifyingclusters of arbitrary shapes and handling noisy data. However, it encounterschallenges in producing satisfactory cluster results when confronted withdatasets of varying density scales, a common scenario in real-worldapplications. In this paper, we propose a novel Adaptive and Robust DBSCAN withMulti-agent Reinforcement Learning cluster framework, namely AR-DBSCAN. First,we model the initial dataset as a two-level encoding tree and categorize thedata vertices into distinct density partitions according to the informationuncertainty determined in the encoding tree. Each partition is then assigned toan agent to find the best clustering parameters without manual assistance. Theallocation is density-adaptive, enabling AR-DBSCAN to effectively handlediverse density distributions within the dataset by utilizing distinct agentsfor different partitions. Second, a multi-agent deep reinforcement learningguided automatic parameter searching process is designed. The process ofadjusting the parameter search direction by perceiving the clusteringenvironment is modeled as a Markov decision process. Using a weakly-supervisedreward training policy network, each agent adaptively learns the optimalclustering parameters by interacting with the clusters. Third, a recursivesearch mechanism adaptable to the data's scale is presented, enabling efficientand controlled exploration of large parameter spaces. Extensive experiments areconducted on nine artificial datasets and a real-world dataset. The results ofoffline and online tasks show that AR-DBSCAN not only improves clusteringaccuracy by up to 144.1% and 175.3% in the NMI and ARI metrics, respectively,but also is capable of robustly finding dominant parameters.