大数据K-means聚类的数据原生全局优化

# 面向大数据K-means聚类的数据原生全局优化 来源：https://arxiv.org/html/2607.15835 ###### 摘要 大数据聚类仍具挑战性：K-means背后的最小平方和聚类（MSSC）问题是NP难的，现有方法要么陷入不良局部最小值，要么需要计算成本过高的元启发式混合方法。我们针对任意高数据：固定特征空间中可能包含任意多（甚至无限多）观测值，而算法仅能访问有限随机样本。我们提出Big-means++，一种简单算法，通过系统性地策展MSSC优化在大型数据上的输入，实现可扩展性和全局搜索质量。它将局部K-means优化编排为面向大数据聚类的数据原生全局搜索。Big-means++并非优化全数据MSSC目标，而是遍历样本诱导的代理景观。每个样本定义一个廉价、不同的经验MSSC近似，具有扰动的局部最优结构，将样本间的变异性转化为全局搜索机制。与原始Big-means不同，流动当前解策略通过在新样本上运行K-means优化（无需回滚到最佳已知解）来跨经验景观传播质心状态。这增加了移动性，并在全数据结构的多个近似中偏好稳定、高质量的配置。此外，一种新的扰动机制以几何序列变化样本大小，拓宽了跨多个分辨率尺度探索的代理景观，考虑了簇不平衡性，并提高了解的质量。竞争性多智能体系统异步探索独立采样的景观，将多样化的随机轨迹转化为集体搜索智能。自动收敛检测在每个智能体获得高质量解后停止搜索，但在进一步搜索有退化风险之前，同时提供通用的速度-质量控制。在22个数据集上与11种竞争算法的实验证明了Big-means++的有效性、效率和鲁棒性。 ###### 关键词：大数据聚类，最小平方和，全局优化，K-means，输入策展模态，可变景观搜索 ††期刊：Pattern Recognition \affiliation [aff1] 机构=AI研究实验室，Satybayev大学，城市=阿拉木图，邮编=050000，国家=哈萨克斯坦 \affiliation [aff2] 机构=信息处理分析与建模实验室，信息与计算技术研究所，城市=阿拉木图，邮编=050010，国家=哈萨克斯坦 ## 1 引言 聚类分析是一种基础的无监督学习工具，用于发现不同领域的结构模式[Ezugwu et al., 2022 (https://arxiv.org/html/2607.15835#bib.bib6)]。虽然广泛的综述强调了聚类在现代机器学习应用中的作用，但最近一项专注于K-means的综述表明，K-means变体仍然是大规模和聚类的核心[Ikotun et al., 2023 (https://arxiv.org/html/2607.15835#bib.bib30)]。这一领域的核心是最小平方和聚类（MSSC）问题，通常通过标准K-means算法解决[Forgy, 1965 (https://arxiv.org/html/2607.15835#bib.bib10)]。虽然K-means快速且被广泛采用，但MSSC已知是非凸的[Cuong et al., 2020 (https://arxiv.org/html/2607.15835#bib.bib9)]且NP难的[Aloise et al., 2009 (https://arxiv.org/html/2607.15835#bib.bib2)]。在大数据时代，数据集通常包含数百万高维记录，这些挑战被显著放大[Mussabayev et al., 2023 (https://arxiv.org/html/2607.15835#bib.bib5)]。因此，标准迭代算法极易陷入次优局部最小值[Jain, 2010 (https://arxiv.org/html/2607.15835#bib.bib18)]。此外，现有方法通常需要对数据进行完整遍历，即使少量迭代也会耗尽可用计算预算，同时仍未能接近全局最优解[Sculley, 2010 (https://arxiv.org/html/2607.15835#bib.bib19)]。传统的逃离局部最优的方法是将K-means与复杂的全局优化元启发式方法集成，例如差分进化[Mansueto and Schoen, 2021 (https://arxiv.org/html/2607.15835#bib.bib13)]、遗传算法[Gribel and Vidal, 2019 (https://arxiv.org/html/2607.15835#bib.bib3)]或非光滑优化[Karmitsa et al., 2025 (https://arxiv.org/html/2607.15835#bib.bib15)]。然而，这些混合方法难以理解和实现，阻碍了广泛采用[Mladenovic et al., 2022 (https://arxiv.org/html/2607.15835#bib.bib11)]；此外，其过高的计算开销使其不适用于大规模聚类。矛盾的是，这些复杂方法在聚类精度上常常无法匹敌更简单的数据驱动替代方案[Mussabayev et al., 2023 (https://arxiv.org/html/2607.15835#bib.bib5), Mussabayev and Mussabayev, 2024a (https://arxiv.org/html/2607.15835#bib.bib12)]。

形式化地，给定一个包含m个点的数据集X={x1,...,xm}⊂Rn，MSSC[Lloyd, 1982 (https://arxiv.org/html/2607.15835#bib.bib8)]寻求k个质心C=(c1,...,ck)∈Rn×k，以最小化总簇内方差：
minC f(C,X) = Σ_{i=1}^m min_{j=1,...,k} ‖xi−cj‖^2, (1)
其中‖·‖表示欧几里得范数。质心C唯一诱导一个划分X = X1 ∪ ... ∪ Xk，其中簇Xj包含所有以cj为最近质心的点；因此，最小化(1)同时最大化簇内凝聚力和簇间分离度。MSSC始终具有有限全局解，并且在数据扰动下具有稳定、可预测的行为[Cuong et al., 2020 (https://arxiv.org/html/2607.15835#bib.bib9)]，并且已知全局最小化器能产生底层簇结构的最忠实表示[Gribel and Vidal, 2019 (https://arxiv.org/html/2607.15835#bib.bib3)]，然而高度非凸的景观使得它们极难获得。

当数据流实际上是无限的，即m→∞时，公式(1)扩展为无限高数据的最小平方和聚类（MSSC-ITD）问题[Mussabayev and Mussabayev, 2024b (https://arxiv.org/html/2607.15835#bib.bib4)]，这额外要求算法能够在无需将完整数据集加载到内存的情况下进行全局搜索。

Big-means[Mussabayev et al., 2023 (https://arxiv.org/html/2607.15835#bib.bib5)]通过将经典的“在完整数据集上优化”范式替换为一系列在随机采样子问题上进行的快速、完整的局部K-means优化，重新定义了大尺度聚类。它不是在整个数据集上迭代，而是将其视为廉价数据样本的无限来源。在每次迭代中，无放回地抽取一个大小为s << m的小随机子集S，并从迄今为止达到的最佳质心状态开始（使用K-means++进行初始化和动态修复退化中心），运行K-means直到收敛。此过程重复直到时间或迭代预算耗尽。由于随机样本S是完整数据集的统计代表性快照，其目标景观f(·,S)提供了真实局部最优的略微扰动分布。迭代优化这些子问题将驱使中心朝向在多个随机视图中保持稳定的解，同时使算法能够绕过不良局部最小值（无论是全数据目标还是单个样本的）。由此产生的轨迹可以看作是通过样本诱导的MSSC景观的局部最优的下行行走，其中景观变异性自然防止了停滞。每次迭代的成本从O(m·k·n·τ)（标准K-means的复杂度）降低到O(s·k·n·τ)（其中τ是K-means扫描次数），将计算复杂度与m解耦。这允许单位时间内进行更多改进尝试，极大地增强了探索-利用权衡。

Big-means中最深刻的思想是样本同时扮演两个角色。首先，它是一个*分解设备*，使K-means在大数据上足够廉价。其次，它是一个*景观变异设备*：每个新样本都会略微改变局部最优的分布及其吸引力。在这里，样本间的变异性不是需要消除的噪声；它是自然的全局搜索算子。遵循“少即是多”的哲学[Mladenovic et al., 2022 (https://arxiv.org/html/2607.15835#bib.bib11)]，该算法几乎免费获得了稳健的邻域变异性，而不是添加一个笨重的全局搜索机制。这与基于重启的K-means改进不同，后者通过仔细的初始化和重复运行可以显著提高解质量[Franti and Sieranoja, 2019 (https://arxiv.org/html/2607.15835#bib.bib31)]，但不会改变底层的全数据局部搜索范式。此外，与小批量方法[Sculley, 2010 (https://arxiv.org/html/2607.15835#bib.bib19)]（进行微小的随机更新）不同，Big-means++中的每一步都是*强*的：在每个样本上运行完整的、真实的局部K-means过程确保每次更新都是在样本目标景观上的实质性优化步骤，而不仅仅是噪声增量校正。

尽管有其前景，Big-means有两个根本局限性。首先，它需要对每个数据集手动调节关键参数——最显著的是样本大小和时间或迭代预算——这严重阻碍了其适应性和实际采用[Karmitsa et al., 2025 (https://arxiv.org/html/2607.15835#bib.bib15)]。其次，它采用精英接受规则：任何未能改善迄今为止最佳解的精化结果都被丢弃。正如我们通过实验证明的，这严重限制了当前质心的移动性，浪费了非改进（但仍基于数据）精化中蕴含的方向信号。

此后，在Big-means框架内提出了几种衍生方法[Mussabayev and Mussabayev, 2024c (https://arxiv.org/html/2607.15835#bib.bib20), b (https://arxiv.org/html/2607.15835#bib.bib4), 2025a (https://arxiv.org/html/2607.15835#bib.bib22)]，每种方法在特定方面都有改进，但都继承了这两个局限性。值得注意的是，Mussabayev and Mussabayev [2024c (https://arxiv.org/html/2607.15835#bib.bib20)]的结果表明，在搜索过程中改变样本大小可以提高解质量和计算效率，甚至优于使用手动优化的固定大小的重复运行，同时减少调节工作。这表明样本大小不仅是一个需要选择的超参数，而且是扰动样本诱导景观的一个额外自由度，这激发了对框架的原则性重新设计。

下面，我们总结主要贡献——无论是广义上还是相对于我们之前的工作：
1. **数据原生优化概念**：我们证明了可变景观搜索（VLS）[Mussabayev and Mussabayev, 2025b (https://arxiv.org/html/2607.15835#bib.bib1)]和“少即是多”[Mladenovic et al., 2022 (https://arxiv.org/html/2607.15835#bib.bib11)]原则成立：仅将优化限制在输入策展模态上，无需任何元启发式混合，就足以在NP难问题上胜过显著更复杂的竞争方法。
2. **用于更深入探索的流动当前解**：我们通过移除贪婪接受规则简化了全局搜索过程。无条件的当前解更新允许算法动态地适应变化的样本诱导景观，导致更深入的探索和更低的最终目标值。
3. **通过样本大小变化进行扰动**：我们引入了几何序列的样本大小——一个“阶梯”——在搜索过程中导航多个分辨率尺度，考虑簇不平衡性，并引导多样化与强化之间的平衡。本质上，这为MSSC全局搜索提供了一种新的扰动形式，其中样本大小的几何变化将搜索暴露给定性质不同的代理景观，并最终产生更好的解。
4. **集体多智能体搜索**：我们将搜索组织为竞争性的自治智能体种群，这些智能体独立遍历采样景观并保留互补的随机轨迹。最终的共同景观评估将这些分散的多样性转化为集体决策，使得全局探索比任何单一轨迹都更广泛。
5. **即插即用的自适应性**：自适应性不仅仅是外部超参数调节的工具，而是优化本身的一个原则。在流动当前解策略下，数据自适应的每个智能体收敛检测器会在连续景观扰动不再产生有意义进展时停止每条轨迹，限制了不必要的搜索降低已强解的风险。因此，它调节了有用的搜索努力，根据轨迹难度分配计算，并消除了数据集特定的预算调节，同时保留通用的速度-质量控制。
6. **标准化基准框架**：我们开发了一个可重复的基准测试套件，配备严格的统计分析工具（可按要求提供）。为确保在相同且高度变化的条件下进行公平、低层次的性能比较，我们用C++重新实现了11种竞争算法——仅对依赖大量原生代码库的非光滑方法保留Fortran——并在22个跨不同尺度的真实世界数据集上全面评估了Big-means++。

## 2 相关工作

关于大数据MSSC的研究主要遵循三个方向。第一个方向主要通过更廉价的经典K-means流水线近似来寻求可扩展性。这包括随机或在线更新，例如MiniBatchKMeans [Sculley, 2010 (https://arxiv.org/html/2607.15835#bib.bib19)]；可扩展的初始化方案，例如K-means——[Bahmani et al., 2012 (https://arxiv.org/html/2607.15835#bib.bib25)]；分而治之的K-means变体，例如BDCSM [Alguliyev et al., 2020 (https://arxiv.org/html/2607.15835#bib.bib29)]；以及基于加权摘要或核心集的数据缩减技术[Bachem et al., 2018a (https://arxiv.org/html/2607.15835#bib.bib26), b (https://arxiv.org/html/2607.15835#bib.bib27)]。Capo等人[Capo et al., 2020 (https://arxiv.org/html/2607.15835#bib.bib34)]专门针对高数据通过递归并行逼近K-means，但该方法主要是一种加速策略，而非遍历样本诱导目标景观的机制。可扩展初始化方向也在理论上得到加强：Makarychev等人[Makarychev et al., 2020 (https://arxiv.org/html/2607.15835#bib.bib38)]改进了K-means++及其并行变体的逼近保证。这些方法减少了数据遍历次数、通信、内存占用或初始化成本，但它们通常保留了K-means在基本固定的目标景观上的局部搜索特性，因此更强调吞吐量而非更深入的全局解。