近日，华侨大学计算机学院陈叶旺教授团队、重庆邮电大学夏书银教授团队及蚂蚁消金研究团队在人工智能领域CCF A类权威期刊IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE（TPAMI，近5年影响因子22.6）上发表了题为“GBSK: Skeleton Clustering via Granular-ball Computing and Multi-Sampling for Large-Scale Data”的研究论文，提出了一种名为GBSK的大规模数据聚类算法，将密度聚类的时间复杂度从平方级降至近线性级。
聚类是无监督学习的基础任务，传统密度聚类算法时间复杂度高，无法有效处理大规模数据。针对这一问题，研究团队从模态聚类理论出发，发现簇的核心由模点（局部密度峰值）决定，而聚类所需的拓扑信息实际上浓缩在密度峰值点及其连接关系构成的稀疏结构中——称之为“几何密度骨架”。该工作基于模态聚类理论，在标准正则条件下证明：由核密度估计（KDE）方法得到的模点在真实密度峰值周围呈渐近正态分布，且对充分分离的多模密度同样成立。然而，逐点的KDE计算在大规模数据上代价高昂。
为绕过这一瓶颈，GBSK引入了粒球密度统计量pi=ni/ri作为KDE的轻量级局部序关系代理。理论上表明，在粒球平衡约束（各粒球包含近似相等数量的样本）下，粒球密度统计量与KDE估计值之间存在着近似的单调等价关系。因而，这项工作提出了一个猜想：通过粒球密度峰值识别模点与通过KDE梯度上升识别模点，在渐近意义下具有结构一致性，两者均依概率收敛到相同的真实模点集。
基于这一理论支撑，GBSK采用分治策略，通过对原始数据进行多次随机采样，在每个小规模子样本上独立识别模点候选，再聚合这些候选模点进行二次模点估计，用以勾勒出数据分布骨架，进而通过骨架完成快速聚类，避免对庞大总体数据的直接计算。
实验验证方面，研究团队在九个大规模数据集上进行了系统性评估，涵盖从数十万到上亿样本、从低维到高维的多种数据场景。结果表明，GBSK及其自适应版本AGBSK在保持竞争性聚类精度的同时，实现了数量级的加速。以MNIST8M（810万样本，784维）以及更具挑战性的AGC100M数据集上（1亿样本、256维）为例，GBSK在单台普通不到万元的标准工作站上即可在数分钟内完成聚类，而传统密度聚类方法以及k-means算法会因内存溢出或运行时间过长而无法执行。
简单二维数据上的骨架抽取样例（左为简单二维数据 ，右为数据骨架）
复杂高维密集数据上的骨架抽取样例（左为复杂高维密集数据二维投影，右为数据骨架）
在AGC100M数据集上的实验结果
该工作已开源，原始论文、补充材料、代码、实验数据及实验记录可在https://github.com/XFastDataLab/GBSK/获取。
（编辑：林雅婷 责任编辑：张罗应）
