从1957年的 Lloyd 算法算起，k-means 已经用了近70年。现在，Meta 给它做了一次大升级。
Meta FAIR 等团队提出并开源了 e-means：用约十分之一的训练轮次，得到比传统 k-means 更低的聚类误差。
在多类嵌入数据集上，Lloyd 算法跑 25 轮达到的测试误差，e-means 只需 1.4—2.6轮就能超越，对应约 10—45倍 GPU 加速。规模扩大到 100亿条嵌入、约1600万个簇，它也只用了 2.5轮，误差低于基线跑25轮的结果。
方法的核心，是用小批次和指数移动平均更新聚类中心，再用缩放定律自动选择批次大小与更新步长。代码已经进入 Faiss 1.16.0。
论文第一作者 Swann Bessa 介绍了这套方法，演示中也能直接看到两种算法更新中心的差别。
在 DEEP 的百万向量、16,384 个簇上，实验结果如下。蓝线是 e-means，左边按训练轮次比较，右边按 CPU 和 GPU 实际耗时比较。
DEEP百万向量上的轮次与实际耗时
一轮里多更新几次
经典 Lloyd 算法先把所有点分给最近的中心，再用每个簇的均值更新中心。整个数据集看完一遍，中心才挪一次。
e-means 把数据打乱，分成小批次。每处理一批，中心就动一次，下一批立刻用新位置做分配。项目页的一个演示中，同样看完一轮数据，Lloyd 更新一次，e-means 更新了 97 次。
中心怎么挪，也做了调整。常见的小批次方法一直累计历史数据，时间越长，新来一批点对中心的影响越小。e-means 给旧记录加上衰减，让新数据还能推动中心移动。
具体维护的是每个簇的有效点数 N和向量之和 S。每来一批，两份旧统计量都按比例衰减，再混入这一批的统计量，中心的位置仍然用 S÷N 计算。批次中的点多或少，也就有了相应的分量。
论文算法1 小批次EMA更新与最终中心计算
训练前期更新幅度大，方便中心调整位置；后期按余弦曲线逐渐收小，最后降到起始步长的十分之一。
别让中心点闲着
有些中心会逐渐分不到多少点。论文在 DEEP 百万向量、16,384 个簇的实验中发现，关闭复活策略、训练 5 轮后，有 4313 个中心几乎闲置；最终分配给它们的点各自不足 10 个。
e-means 每隔 5 个小批次检查一次。某个中心的有效计数低于平均值的 10%，就从活跃簇里抽取一个来拆分：原中心变成两个略微错开的新中心，计数一分为二。点越多的簇，越容易被选中。
启用这套策略后，同一实验中的失效中心从 4313个降到47个。直接从当前批次随机抽一个点来填空，仍然留下了 2343 个。
论文表14局部 5轮后百万向量上的失效中心数量
误差的变化见下面另一组 3 轮消融实验：取消复活策略，测试 MSE 为 0.3967；使用完整配方后降到 0.3880。
论文表1 3轮消融实验中的聚类误差
训练结束时，e-means 还会利用最后一轮已经记录的分组，重新计算一次均值，得到最终中心。
参数也有缩放规律
小批次不是越小越好。太小，GPU 吞吐吃不满；太大，一轮里中心更新的次数又少了。
作者在 DEEP 数据上做了约 7.5万次优化运行，用这些结果拟合出选参公式。给定数据量 n、簇数量 k 和训练轮次 T，公式就能确定批大小和起始步长。
论文图2 批大小与更新步长对验证误差的影响
左图的低谷对应较合适的更新步长。右图中，批次增大到一定程度后，误差开始明显上升；配方会尽量选择误差还接近最低点、吞吐又足够高的区域。
这套公式随后拿到 SIFT、SPACEV、AG-News 和 arXiv 等数据上检查。自动选出的批大小，相对逐项搜索最优值带来的额外 MSE，中位数约为 0.19%。
快的不只是轮次
实际耗时比较，采用的是同一个目标：达到 Flash-KMeans 跑 25 轮后的测试 MSE。
从百万到十亿向量，e-means 用了 1.4—2.6 轮，GPU 耗时加速约 9.5—45.5倍。例如 DINO 千万向量、65,536 个簇的设置，1.4 轮就达到了目标，实际加速 23.3倍。
论文表4 达到基线二十五轮测试误差所需的轮次与加速
这些实验使用 H100：百万到亿级在单卡上跑，十亿级使用 8 卡；e-means 使用 BF16，Flash-KMeans 使用 FP16。实现也做了优化，将距离计算和最近中心选择融合到 GPU kernel 中，减少中间结果的存储；计数与向量和仍用 FP32 累计。
下面这张图还加入了其他小批次方法。上排是训练误差，下排是测试误差，纵轴的 1.0 对应 Lloyd 跑 25 轮的水平。橙色曲线下降得早，但最后停在较高位置；蓝色的 e-means 下降更快，也能到更低的误差。
论文图3 四个数据集上不同方法的收敛曲线
采用更强的 greedy k-means++ 初始化后，e-means 跑 5 轮，相对 Flash-KMeans 跑 25 轮，在对应表格中仍有约 0.06%—0.33% 的误差改善。
百亿向量怎么跑
DINO10B 包含 100亿条 DINOv3 图像 patch 向量，每条1024维。即使用 INT8 保存，也有约 10TB 数据；聚类中心则有约 1678万个。
论文从 SSD 预取数据，并把数据和中心分给多个 GPU。在精确寻找最近中心的设置下，e-means 跑 2.5轮、779 GPU小时，测试误差略低于 Lloyd 跑 25轮、6784 GPU小时 的结果。
作者又给中心加上 IVF 倒排索引：先把中心分到不同的桶里，处理一个向量时，只在少量候选桶里继续找。中心随训练移动，索引也跟着更新。
结合 SSD 流式读取、分片与 IVF 近似分配，训练降到约 23 GPU小时，在一台 8块H100 的机器上约 3小时 完成，测试 MSE 达到了基线目标。
论文表21 百亿向量实验 GPU hours是累计GPU时间
这些中心可以继续用来构建向量检索索引。附录的 VIBE 实验中，e-means 用更少的索引训练时间，在多数数据集上达到了相近或更高的召回率。
最后
Faiss 里已经能用。e-means 已随 Faiss 1.16.0 发布，CPU、GPU、分布式和中心分片实现，以及论文基准的复现脚本都已公开。
CPU 上的基本接口如下：
from faiss.contrib.e_means import NumpyEmeans
em = NumpyEmeans(x.shape[1], 16384, nepochs=5)
centroids, labels = em.train(x)返回的 labels 来自最后一轮训练。
项目页还提供了可以调节数据分布和簇数量的浏览器演示；准备在真实数据上比较，仓库里有 CPU、单卡和大规模实验入口。
参考链接
-
论文 e-means: outperforming k-means (in one-tenth the epochs)：https://arxiv.org/html/2611.09501v1 -
项目说明与交互演示：https://e-means.github.io/ -
Faiss e-means 代码与使用说明：https://github.com/facebookresearch/faiss/tree/main/contrib/e_means
-
Lloyd方法的历史与研究：https://www.math.uwaterloo.ca/~cswamy/papers/kmeans-journ.pdf