Mini-batch kernel k-means¶
会议: NeurIPS 2026
arXiv: 2410.05902
领域: 学习理论
关键词: 核聚类, Mini-batch, k-means, 早停收敛保证, 近似算法
一句话总结¶
提出了首个 mini-batch 核 \(k\)-means 算法，利用滑动窗口稀疏截断将单步迭代时间降至 \(\widetilde{O}(k b^2)\)，并在早停准则下严格证明了与空间维度无关的 \(O(\gamma^2/\epsilon)\) 步收敛性与 \(O(\log k)\) 期望近似比。
研究背景与动机¶
\(k\)-means 聚类因实现简单、执行高效而在现代机器学习与海量数据处理中得到广泛应用。然而标准 Lloyd 算法隐式要求数据在原始特征空间中具备线性可分性，面对流形、环状或高度非线性的复杂真实分布时往往表现欠佳。为了突破线性表征瓶颈，核 \(k\)-means（Kernel \(k\)-means）借助再生核希尔伯特空间（RKHS）的隐式非线性映射 \(\phi(x)\)，将数据投影至高维甚至无限维特征空间 \(\mathcal{H}\) 中，从而大幅改善聚类划分质量。
但核技巧带来的显著代价是计算复杂度爆炸。由于无法显式存储无限维空间中的聚类中心，全批量核 \(k\)-means 在每次迭代中分配样本与更新中心时都需要评估全体样本之间的核内积，单步迭代的时间复杂度高达 \(O(n^2)\)。面对数万甚至数百万样本规模，全批量算法几乎无法在可接受的时间内运行完成。虽然标准空间下的 mini-batch \(k\)-means 凭借随机子集采样和自适应中心滑动平均成功将算力开销降到可扩展水平，但由于 mini-batch 下的聚类中心演化成了历次批次历史样本的多层嵌套凸组合，不再简单对应于确定性静态子集的均值中心，导致核技巧无法直接沿用。
以往加速核聚类的手段（如 Nyström 采样、随机傅里叶特征或 Coreset）多集中在预先做低秩近似或数据压缩，而在算法优化层面探索 mini-batch 核 \(k\)-means 此前仍属空白。本文的核心切入点在于：既然历史批次对当前中心的影响力随迭代学习率以指数速率衰减，就可以在保证数值误差有界的前提下对历史支撑集进行稀疏截断。核心 idea：通过引入滑动窗口历史点截断技术维持稀疏中心表征，并配合非衰减自适应学习率与早停准则，构建首个无维度依赖且单步开销仅 \(\widetilde{O}(k b^2)\) 的 mini-batch 核 \(k\)-means 算法。
方法详解¶
整体框架¶
算法的目标是在由核函数 \(K(x,y)=\langle \phi(x),\phi(y)\rangle\) 定义的特征空间 \(\mathcal{H}\) 中找到 \(k\) 个隐式中心集合 \(\mathcal{C}\)，最小化目标函数 \(f_X(\mathcal{C}) = \frac{1}{n} \sum_{x \in X} \min_{c \in \mathcal{C}} \|\phi(x) - c\|^2\)。整体流程从标准的核 \(k\)-means++ 凸组合初始化开始，每轮迭代从数据集 \(X\) 中均匀有放回采样大小为 \(b\) 的 mini-batch \(B_i\)。算法依次完成样本与中心核距离评估、最近中心分配、基于截断窗口的历史样本更新，并在批次目标函数下降量低于早停阈值 \(\epsilon\) 时终止。
%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
A["输入数据 X 与核函数 K<br/>核 k-means++ 凸组合初始化中心"] --> B["批次均匀随机采样 Bi<br/>大小为 b 且有放回"]
B --> C["递归核距离与内积计算<br/>动态规划推导样本中心距离"]
C --> D["滑动窗口稀疏中心截断<br/>保留近期约 τ 个样本支撑项"]
D --> E["非衰减学习率中心平滑更新<br/>权重系数按簇内样本规模设定"]
E -->|目标降幅 >= ε| B
E -->|目标降幅 < ε| F["早停终止并输出最终聚类划分"]关键设计¶
1. 递归核距离与内积计算：突破无限维中心无法显式存储的计算瓶颈 在 RKHS 中无法直接写出聚类中心的显式向量坐标，样本到中心的欧氏距离只能通过内积展开： $$ |\phi(x) - \mathcal{C}{i+1}^j|^2 = K(x,x) - 2\langle \phi(x), \mathcal{C}}^j \rangle + \langle \mathcal{C{i+1}^j, \mathcal{C}^j \rangle $$ 若采用 mini-batch 步进，第 \(i+1\) 步中心是旧中心与当前批次子簇均值 \(cm(B_i^j)\) 的加权组合：\(\mathcal{C}_{i+1}^j = (1-\alpha_i^j)\mathcal{C}_i^j + \alpha_i^j cm(B_i^j)\)。作者推导出关键的递推关系： $$ \langle \phi(x), \mathcal{C}{i+1}^j \rangle = (1-\alpha_i^j)\langle \phi(x), \mathcal{C}i^j \rangle + \alpha_i^j \langle \phi(x), cm(B_i^j) \rangle $$ $$ \langle \mathcal{C}}^j, \mathcal{C_i^j, cm(B_i^j) \rangle + (\alpha_i^j)^2 \langle cm(B_i^j), cm(B_i^j) \rangle $$ 通过维护上一迭代的所有数据内积缓存，可以在每步以 }^j \rangle = (1-\alpha_i^j)^2 \langle \mathcal{C}_i^j, \mathcal{C}_i^j \rangle + 2\alpha_i^j(1-\alpha_i^j)\langle \mathcal{C\(O(n(b+k))\) 时间与 \(O(nk)\) 空间完成完全无截断的中心递归维护，相比全批量核算法的 \(O(n^2)\) 取得初阶加速。
2. 滑动窗口稀疏中心截断：将单步复杂度彻底解耦全集样本量 为了使单步迭代时间完全摆脱对总样本量 \(n\) 的依赖，作者进一步分析了递归展开式中的历史衰减结构。由于中心展开式中早期历史项带有连乘因子 \(\prod_{z=i-\ell+1}^i (1-\alpha_z^j)\)，当历史累积样本数达到阈值 \(\tau\) 时，乘积因子的范数将呈指数衰减。算法定义活动索引集 \(Q_i^j\)，仅保留距当前最近且所包含点数满足 \(\sum_{\ell \in Q_i^j} b_\ell^j \ge \tau\) 的批次，构造截断中心： $$ \widehat{\mathcal{C}}{i+1}^j = \sum (1-\alpha_z^j) $$ 作者证明，只要设置截断阈值 } \alpha_\ell^j cm(B_\ell^j) \prod_{z \in Q_i^j \setminus {\ell}\(\tau = \lceil b \ln^2(28\gamma/\epsilon) \rceil\)（其中 \(\gamma = \max_{x \in X} \|\phi(x)\|\)），截断中心与真实理论中心之间的几何漂移满足 \(\|\widehat{\mathcal{C}}_{i+1}^j - \mathcal{C}_{i+1}^j\| \le \epsilon/28\)。由此，每轮只需为批次内 \(b\) 个点与大小至多为 \(\tau+b\) 的稀疏支撑项计算核内积，单步时间直接从 \(O(n(b+k))\) 大幅削减至 \(\widetilde{O}(k b^2)\)，空间开销仅为 \(\widetilde{O}(kb)\)。
3. 非衰减自适应学习率与早停收敛分析：建立无维度依赖的有限步收敛理论 传统 sklearn 实现中的 mini-batch 学习率随总样本计数单调趋近于 0，容易导致中心过早冻结；而本文借鉴并推广了 Schwartzman (2023) 的学习率设定 \(\alpha_i^j = \sqrt{b_i^j / b}\)。该学习率不随全局步数递减，不仅能促使早期误差项以几何级数被遗忘，而且在理论上构建了 Hilbert 空间值鞅（Martingale）的浓度边界。结合泛化到 Hilbert 空间的 Azuma 不等式与 Hoeffding 不等式，引入虚拟全量中心 \(\overline{\mathcal{C}}_{i+1}^j = (1-\alpha_i^j)\mathcal{C}_i^j + \alpha_i^j cm(X_i^j)\) 作为桥梁，证明了当采样批次大小满足 \(b = \Omega(\max\{\gamma^4, \gamma^2\}\epsilon^{-2} \log^2(\gamma n/\epsilon))\) 时，算法以高概率在 \(O(\gamma^2/\epsilon)\) 次迭代内触发早停条件 \(f_{B_i}(\widehat{\mathcal{C}}_{i+1}) - f_{B_i}(\widehat{\mathcal{C}}_i) < \epsilon\)。针对高斯核与拉普拉斯核等归一化核，恒有 \(\gamma=1\)，从而使收敛界与输入空间的维度 \(d\) 完全解耦。
损失函数 / 训练策略¶
算法以聚类误差的平方和为优化准则，批次损失评估函数为： $$ f_{B_i}(\mathcal{C}) = \frac{1}{b} \sum_{x \in B_i} \min_{c \in \mathcal{C}} |\phi(x) - c|^2 $$ 中心初始化严格采用核 \(k\)-means++ 机制，确保初始中心为原始数据的凸组合（Convex Combination）。通过引理保证，算法运行过程中所有中心及截断中心恒处于数据凸包之内，范数始终满足 \(\|\mathcal{C}\| \le \gamma\)。当算法停止时，期望近似比保持在 \(O(\log k)\)，与全批量 \(k\)-means++ 基线理论一致。
实验关键数据¶
主实验¶
论文在 MNIST (70k 样本, 784维)、PenDigits (10,992 样本, 16维)、Letters (20,000 样本, 16维) 与 HAR (10,299 样本, 561维) 四个公开数据集上全面评估算法。实验采用高斯核 \(K(x,y)=\exp(-\|x-y\|^2/\kappa)\)、固定运行 200 轮迭代，并在 AMD Ryzen 9 7950X + RTX 4090 环境下对比 ARI、NMI 及运行耗时（批次大小 \(b=1024\)，截断阈值 \(\tau=200\)）：
| 数据集 | 算法配置 | ARI 平均分 | NMI 平均分 | 核心运行耗时比 / 特征 |
|---|---|---|---|---|
| MNIST | Full-batch Kernel \(k\)-means | 0.42 | 0.54 | 基准运行耗时（含极高核矩阵计算瓶颈） |
| MNIST | Truncated MB Kernel \(k\)-means (\(\beta\)) | 0.43 | 0.54 | 获得 10–100× 端到端加速，质量与全批量持平 |
| MNIST | Standard MB \(k\)-means (线性空间) | 0.36 | 0.43 | 线性空间无法分离非凸流形，精度显著落后 |
| PenDigits | Full-batch Kernel \(k\)-means | 0.69 | 0.77 | 基准质量 |
| PenDigits | Truncated MB Kernel \(k\)-means (\(\beta\)) | 0.68 | 0.76 | 精度损失可忽略，耗时减少 1–2 个数量级 |
| Letters | Truncated MB Kernel \(k\)-means (\(\beta\)) | 0.28 | 0.43 | 26 类复杂字母聚类显著优于线性 mini-batch |
| HAR | Truncated MB Kernel \(k\)-means (\(\beta\)) | 0.55 | 0.68 | 传感器高维特征下保持高质量与秒级完成度 |
消融实验：不同核函数下的特征空间范数界 \(\gamma\) 对比¶
定理收敛界关键依赖于 \(\gamma = \max_{x \in X} \|\phi(x)\|\)。作者在全量附录实验中对比了高斯核（Gaussian）、\(k\)-近邻核（k-nn, \(D^{-1}AD^{-1}\)）与热核（Heat kernel, \(\exp(-t D^{-1/2} A D^{-1/2})\)）实测 \(\gamma\) 上界：
| 数据集 | 核函数类型 (Kernel Type) | 实测 \(\gamma\) 范数值 | 对批量大小界 \(\Omega(\max\{\gamma^4,\gamma^2\}\epsilon^{-2})\) 的理论影响 |
|---|---|---|---|
| PenDigits | k-nn | 0.00100 | \(\gamma \ll 1\)，大幅缩减批次采样大小要求 |
| PenDigits | Heat | 0.0477 | 远小于 1，参数更易调优 |
| PenDigits | Gaussian | 1.000 | 严格等于 1，完全无输入维度 \(d\) 依赖 |
| HAR | k-nn | 0.00050 | 范数极小，理论批次下界更松弛 |
| HAR | Heat | 0.0468 | 明显优于单位界 |
| HAR | Gaussian | 1.000 | 保持 \(\gamma=1\) |
| MNIST | k-nn | 0.00220 | 稀疏图核结构范数压缩极强 |
| MNIST | Heat | 0.0612 | 数值表现稳健 |
| MNIST | Gaussian | 1.000 | 消除 784 维原始维度平方因子的影响 |
| Letters | k-nn | 0.00100 | 图拉普拉斯类核矩阵范数严格受限 |
| Letters | Heat | 0.0399 | 实测表现出色 |
| Letters | Gaussian | 1.000 | 基准归一化核 |
关键发现¶
- 加速与质量兼得：截断式 mini-batch 核 \(k\)-means 在 4 个基准数据集上均取得了 10 到 100 倍的运行时间加速，而聚类指标（ARI / NMI）与全批量核 \(k\)-means 差距在误差范围内，彻底打破了核 \(k\)-means 无法处理超万级样本的算力桎梏。
- \(\tau\) 阈值极度鲁棒：在超参敏感性实验中，即使将 \(\tau\) 降低至远低于理论保证的极端值（例如 \(\tau=50\)，此时 \(\tau \ll b\)），聚类效果依然几乎没有退化，说明实际数据中历史样本在短短数十个代表点之后即可充分遗忘。
- 学习率设计优势：采用 Schwartzman (2023) 的非衰减学习率 \(\beta\) 无论在核化还是非核化 mini-batch 中均一致超越了 scikit-learn 的默认学习率，避免了后期由于步长衰减为零导致的陷入局部次优停滞。
亮点与洞察¶
- 稀疏滑动窗口截断机制：通过严格分析历史项连乘衰减率，证明了仅保留最新滑动窗口内的样本支持集即可控制近似误差在 \(\epsilon/28\) 内，使核更新开销降至与全局样本量 \(n\) 无关的 \(\widetilde{O}(k b^2)\)。
- 无维度依赖的收敛保证：借助 Hilbert 空间值鞅的 Azuma 浓度不等式，将有限步早停收敛理论扩展至无限维 RKHS，对于高斯等常见归一化核完全消除了 \(O((d/\epsilon)^2)\) 中维度 \(d\) 的影响。
- 可组合性设计：该算法专注于优化轨迹与迭代效率，与现有的数据端采样（如 Coreset）和矩阵端近似（如 Nyström、随机傅里叶特征）正交，可作为即插即用的组件直接叠加使用。
局限与展望¶
- 推理与分配仍需计算核内积：单步迭代虽然与 \(n\) 解耦，但复杂度中仍存在 \(b^2\) 与 \(\tau^2\) 的二次依赖，当批次或保留点数设置极大时计算负担依旧明显。
- 超参数敏感度：高斯核宽度 \(\kappa\) 与早停参数 \(\epsilon\) 对收敛质量与终止轮数有显著影响，缺乏端到端的核参数自适应选择机制。
- 未来方向：将滑动窗口稀疏表示与流式核密度估计（KDE）或谱稀疏化方法深度融合，进一步探索非凸流形无监督表征学习的在线化扩展。
相关工作与启发¶
- vs Schwartzman (2023)：Schwartzman 证明了欧氏空间 mini-batch \(k\)-means 在 \(O(d/\epsilon)\) 步内早停终止，但批次大小依赖空间维度 \(d^2\) 且仅支持线性可分数据。本文通过引入 \(\gamma\) 范数界与截断技巧，将分析推向无限维 Hilbert 空间，并在归一化核下完全消除了对 \(d\) 的依赖。
- vs Jiang et al. (2021) / Coreset：核 Coreset 方法通过近线性时间构建大小为 \(\text{poly}(k\epsilon^{-1})\) 的加权核心子集来压缩输入。本文属于优化迭代机制创新，两者互补，可在 Coreset 压缩后的子集上继续运行 mini-batch 加速。
- vs Chitta et al. (2011)：Chitta 等人通过先采样 \(m\) 个点将中心限制在这组点的线性组合空间中进行优化，缺乏最坏情况下的收敛速度与理论近似比保证。本文给出了严格的有限步迭代上界和 \(O(\log k)\) 近似比证明。
评分¶
- 新颖性: ⭐⭐⭐⭐⭐ 首次系统性提出并理论证明了 mini-batch 核 \(k\)-means 算法，解决了长期存在的历史支持集无限累积难题。
- 实验充分度: ⭐⭐⭐⭐☆ 在四个经典基准数据集和三种代表性核函数上验证了 10–100× 的加速比与聚类质量。
- 写作质量: ⭐⭐⭐⭐⭐ 数学推导严密紧凑，符号规范统一，从递归表征到截断误差控制的论证一气呵成。
- 价值: ⭐⭐⭐⭐⭐ 为超大规模非线性聚类提供了兼具理论保证与工程可用性的经典基础工具。