Adaptive and Robust DBSCAN with Multi-agent Reinforcement Learning

Submited IEEE TPAMI in 2023.5

Hao Peng	Xiang Huang	Shuo Sun	Ruitong Zhang	Xizhao Wang	Philip S. Yu
School of Cyber Science and Technology, Beihang University	School of Cyber Science and Technology, Beihang University	School of Cyber Science and Technology, Beihang University	School of Cyber Science and Technology, Beihang University	College of Computer Science and Software Engineering, Shenzhen University	Department of Computer Science, University of Illinois at Chicago

TL;DR This paper proposes a new adaptive robust DBSCAN clustering framework based on multi-agent reinforcement learning, namely AR-DBSCAN, which does not need to define hyperparameter in advance. This framework achieves adaptive robust clustering for datasets with different densities.

Paper | Code

Abstract This article proposes a new adaptive robust DBSCAN clustering framework based on multi-agent reinforcement learning, namely AR-DBSCAN. The framework uses two-level coding trees to divide data into different density regions, and uses agents to adaptively process data with different density distributions. At the same time, multi-agent deep reinforcement learning is utilized to automatically search for the best clustering parameters, and efficient and controllable exploration is achieved through a recursive search mechanism that adapts to the size of the data. The experimental results show that the clustering accuracy of AR-DBSCAN has been significantly improved and has robustness.

Approach The above image describes the overall framework of AR-DBSCAN.AR-DBSCAN is an improved DBSCAN algorithm that includes three steps: structuring, agent allocation, and parameter search. Firstly, in the structured step, the original dataset is transformed into a structured k-NN graph G to capture neighborhood structure information. Next, an optimized two-level encoding tree is generated based on the minimization of two-dimensional structural entropy, and the dataset is divided using proxy allocation method based on the information uncertainty distribution of the encoding tree. Each partition is assigned a corresponding proxy. Finally, in each agent and corresponding data partition, a separation parameter search process based on deep reinforcement learning is applied to find the optimal parameter combination. In order to improve search efficiency, a recursive mechanism was adopted.

Experiments We compared AR-DBSCAN with traditional optimization algorithms and existing DBSCAN parameter search methods. The baselines are:Rand, BO-TPE, Anneal, PSO, GA, DE, KDist, BDE. The results are shown in the following figure.

Offline Evaluation:

Offline evaluation of NMI performance:

Offline evaluation of ARI performance:

Offline clustering efficiency comparison:

Online Evaluation:

Online evaluation of NMI performance:

Online evaluation of ARI performance:

Conclusion This paper proposes an adaptive robust DBSCAN algorithm based on multi-agent reinforcement learning, called AR-DBSCAN. The algorithm is divided into two parts: an intelligent agent allocation method based on clustering density and a parameter search method based on deep reinforcement learning. The intelligent agent allocation method pre partitions data based on clustering density to alleviate parameter search problems in clustering with different densities. The parameter search method is applied to each agent, perceiving the clustering environment through weak supervision and attention mechanisms, and searching for the optimal parameters. The recursive search mechanism avoids the degradation of search performance caused by excessive parameter space. The experimental results show that the algorithm has high accuracy, efficiency, and stability. In future work, other concepts of interaction between multi-agent systems will be explored to avoid the impact of misclassification on agent allocation.