e-means: 通过指数移动平均实现 10 倍速的 K-Means 聚类

核心创新：用于 K-Means 的指数移动平均

e-means 是一种针对 K-means 问题的现代优化方法，它用基于指数移动平均 (EMA) 的小批量更新取代了传统的 Lloyd 算法更新规则。通过跟踪最近的分配情况而非完整的历史均值，e-means 仅需 1.2 到 3 个 epoch 即可达到测试损失目标，而 Lloyd 算法通常需要 25 个以上的 epoch。这使得 GPU 上的实际运行速度提升了 10–45 倍，CPU 上提升了 8–15 倍。

为什么 EMA 优于传统更新方式

传统的 K-means (Lloyd) 使用全批量更新，计算成本高昂且容易陷入局部最小值。虽然存在像 MacQueen 更新这样的小批量变体，但它们往往存在不稳定性或收敛性差的问题。e-means 使用 EMA 更新规则：

• $S_j \leftarrow (1-\alpha)S_j + \alpha s_j$
• $N_j \leftarrow (1-\alpha)N_j + \alpha n_j$

这种方法确保了质心能够跟踪最近的数据分布，同时遗忘过时的分配。与基于梯度下降的更新（可能会越过分配点的凸包）不同，EMA 更新本质上是稳定的。这种稳定性允许使用更高的学习率并实现更快的收敛，而无需手动调整超参数。

自动超参数缩放

e-means 的一个主要优势是消除了手动调整超参数的需求。研究人员推导出了缩放定律，可以根据数据集大小 ($n$)、聚类数量 ($k$) 和目标 epoch 数 ($T$) 自动确定最佳批量大小 ($B$) 和步长 ($\alpha_0$)。这些定律使算法能够在不同的问题规模上有效泛化，而无需用户进行网格搜索。

改进的鲁棒性和死聚类复活

与 Lloyd 算法相比，e-means 展示了更强的逃离局部最小值的潜力。通过利用噪声小批量更新，该算法能更有效地探索优化空间。此外，e-means 实现了用于死聚类复活的“比例分割”策略，即通过分割大型活跃聚类来复活点数不足的聚类。这种方法明显优于简单的重采样方法，确保了码本的全部容量得到利用。

实际考量与局限性

虽然 e-means 为大规模聚类任务提供了显著的速度提升，但其性能取决于具体的使用场景。社区反馈强调，该算法最适合涉及大规模数据集的场景，在这些场景中，小批量采样能提供全局分布的代表性近似。对于几何任务（例如在球面上松弛网格，其中质心可以通过解析计算得出），小批量采样的开销可能无法提供优于直接几何计算的优势。

"e-means 的胜出在于它对海量数据集的遍历次数更少，但球面上网格的松弛并不涉及数据集：每个 Voronoi 单元的质心可以直接从其几何形状计算得出。小批量采样只是将其替换为对同一事物的噪声采样估计。" — Hacker News 用户 jlhawn

此外，批评者指出，在极端规模下，并行更新的通信开销可能成为瓶颈。该算法的有效性依赖于平衡本地计算与跨工作节点同步部分更新的成本。

实现

e-means 的实现已作为贡献集成到 Faiss library 中。它提供了基于 NumPy 和 PyTorch 的接口，可以无缝集成到现有的机器学习工作流中。