Adaptive and Robust DBSCAN with Multi-agent Reinforcement Learning

📄 arXiv: 2505.04339v1 📥 PDF

作者: Hao Peng, Xiang Huang, Shuo Sun, Ruitong Zhang, Philip S. Yu

分类: cs.LG, cs.AI

发布日期: 2025-05-07

💡 一句话要点

提出AR-DBSCAN，利用多智能体强化学习自适应解决DBSCAN在多密度数据集上的聚类问题。

🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture)

关键词: DBSCAN 聚类算法 多智能体强化学习 密度自适应 深度强化学习

📋 核心要点

  1. DBSCAN在处理密度不均匀的数据集时，难以找到合适的全局参数，导致聚类效果不佳。
  2. AR-DBSCAN将数据集划分为多个密度分区，并为每个分区分配一个智能体，独立学习最佳聚类参数。
  3. 实验表明，AR-DBSCAN在多个数据集上显著提高了聚类精度，NMI和ARI指标分别提升高达144.1%和175.3%。

📝 摘要（中文）

DBSCAN是一种著名的基于密度的聚类算法，因其在识别任意形状的聚类和处理噪声数据方面的有效性而得到广泛应用。然而，当面对具有不同密度尺度的数据集时，它在产生令人满意的聚类结果方面面临挑战，这在实际应用中很常见。本文提出了一种新的自适应和鲁棒的DBSCAN与多智能体强化学习聚类框架，即AR-DBSCAN。首先，我们将初始数据集建模为两级编码树，并根据编码树中确定的信息不确定性将数据顶点分类为不同的密度分区。然后，将每个分区分配给一个智能体，以找到最佳聚类参数，而无需人工协助。该分配是密度自适应的，使AR-DBSCAN能够通过为不同的分区使用不同的智能体来有效地处理数据集内不同的密度分布。其次，设计了一个多智能体深度强化学习引导的自动参数搜索过程。通过感知聚类环境来调整参数搜索方向的过程被建模为马尔可夫决策过程。使用弱监督奖励训练策略网络，每个智能体通过与聚类交互来自适应地学习最佳聚类参数。第三，提出了一种适应数据规模的递归搜索机制，能够高效且可控地探索大型参数空间。在九个人工数据集和一个真实世界数据集上进行了大量实验。离线和在线任务的结果表明，AR-DBSCAN不仅将NMI和ARI指标的聚类精度分别提高了高达144.1%和175.3%，而且能够稳健地找到主导参数。

🔬 方法详解

问题定义：DBSCAN算法在处理密度分布不均匀的数据集时，需要手动调整全局参数，难以达到理想的聚类效果。现有方法无法自适应地处理不同密度区域，导致聚类精度下降，鲁棒性不足。

核心思路：AR-DBSCAN的核心思想是将数据集分解为多个密度分区，并为每个分区分配一个独立的智能体。每个智能体通过强化学习，根据自身分区的特点，自适应地学习最佳的聚类参数。这种方法能够有效地处理不同密度区域，提高聚类精度和鲁棒性。

技术框架：AR-DBSCAN的整体框架包括以下几个主要阶段：1) 数据预处理：将原始数据集建模为两级编码树，用于评估数据点的信息不确定性。2) 密度分区：根据编码树的信息不确定性，将数据点划分为不同的密度分区。3) 智能体分配：为每个密度分区分配一个独立的智能体。4) 强化学习参数搜索：每个智能体通过与聚类环境交互，利用深度强化学习算法学习最佳的聚类参数。5) 递归搜索机制：采用递归搜索机制，自适应地调整参数搜索范围，提高搜索效率。

关键创新：AR-DBSCAN的关键创新在于：1) 密度自适应分区：根据数据的信息不确定性，自适应地将数据集划分为不同的密度分区。2) 多智能体强化学习：利用多智能体强化学习框架，为每个分区独立学习最佳聚类参数。3) 递归搜索机制：采用递归搜索机制，高效地探索大型参数空间。与传统DBSCAN相比，AR-DBSCAN能够自适应地处理不同密度区域，无需手动调整全局参数。

关键设计：AR-DBSCAN的关键设计包括：1) 奖励函数：使用弱监督奖励函数，鼓励智能体找到能够产生高质量聚类的参数。2) 策略网络：采用深度神经网络作为策略网络，用于学习智能体的行为策略。3) 递归搜索策略：递归地缩小参数搜索范围，直到找到满足要求的参数组合。具体参数设置和网络结构在论文中有详细描述。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果表明，AR-DBSCAN在人工数据集和真实数据集上均取得了显著的性能提升。在NMI和ARI指标上，AR-DBSCAN分别提升了高达144.1%和175.3%。此外，AR-DBSCAN还表现出良好的鲁棒性，能够稳定地找到最优参数，优于传统的DBSCAN算法。

🎯 应用场景

AR-DBSCAN可应用于各种需要聚类的场景，尤其适用于数据密度分布不均匀的情况，例如：社交网络分析、城市交通流量分析、生物信息学数据分析等。该方法能够自动寻找最优参数，降低人工干预，提高聚类效率和准确性，具有广泛的应用前景。

📄 摘要（原文）

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 Adaptive and Robust 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.