MSGB: Adaptive granular ball clustering via mean shift optimization and graph-based density connectivity

To address the issues of high computational overhead and the inability to capture hierarchical structures when DBSCAN processes data with uneven density distributions, this paper proposes a density-driven clustering framework, namely MSGB based on granular balls (GBs). This method uses the GB as the basic operational unit. First, it automatically determines the initial number of partitions using mean drift and initializes cluster centers based on local density peaks to avoid the sensitivity to initial values inherent in traditional -means. Second, it designs a radius calculation strategy based on the coefficient of variation-weighted median distance, allowing the GB scale to dynamically adjust according to local density variations, thereby preserving structural information while suppressing noise. Furthermore, by constructing a granular ball topological similarity graph, it transforms the density reachability determination into a search for connected components among granular balls, effectively handling scenarios with multi-density clusters and weak connections. To validate the effectiveness of the proposed method, this paper conducts comparative experiments on 10 synthetic datasets and 10 real-world datasets using ACC, NMI, and ARI as evaluation metrics. Specifically, on the synthetic datasets, MSGB improves ACC by 3.81%, NMI by 2.82%, and ARI by 4.49% compared to DBSCAN. On real-world datasets, it also achieves consistent improvements. The results show that MSGB outperforms several mainstream comparison algorithms on average across all datasets, demonstrating outstanding robustness and consistent advantages, particularly in noisy and non-uniform density scenarios, thereby validating the framework’s strong adaptability to data with complex density structures. The source code of the MSGB algorithm is available via the following network link https://github.com/Z-Lucky-M/MSGB .