计算机科学
聚类分析
人工智能
模式识别(心理学)
骨架(计算机编程)
数据挖掘
计算机视觉
特征提取
图像分割
特征(语言学)
模糊聚类
算法设计
算法
数据建模
图像处理
信号处理
作者
Yewang Chen,Junfeng Li,Shuyin Xia,Qinghong Lai,Xinbo Gao,Guoyin Wang,Dongdong Cheng,Yi Liu,Yi Wang
标识
DOI:10.1109/tpami.2026.3719825
摘要
To overcome the computational bottlenecks of traditional density-based clustering, we propose Granular-Ball SKeleton clustering (GBSK), a scalable algorithm that achieves near-linear time complexity while preserving topological accuracy. GBSK introduces a strategic shift from full density estimation to the sketching of geometric density skeleton-recover a graph connecting high-density modes that captures essential cluster connectivity. Theoretically, we find that granular-ball density statistics can serve as a computationally efficient, asymptotically approximate local proxy for kernel density estimation (KDE), providing a statistical support for discrete mode extraction within the well-established KDE framework. Methodologically, GBSK integrates three key components: adaptive granular-ball construction for efficient local data approximation, multi-stage sampling for rapid density estimation, and a secondary refinement process that aggregates candidate modes from all sample sets to produce a robust final density skeleton. To enhance usability, we introduce an adaptive variant, AGBSK, which reduces hyperparameters to just the cluster count. Extensive experiments on datasets scaling up to 100 million instances and 3072 dimensions demonstrate that GBSK and AGBSK maintain competitive accuracy while achieving orders-of-magnitude speedup over state-of-the-art methods.
科研通智能强力驱动
Strongly Powered by AbleSci AI