Meta FAIR 的研究人员发布了 e-means，它是 Lloyd's k-means 算法的即插即用替代方案。e-means 聚类算法在 1.4 到 2.6 个 epoch 内即可达到 Lloyd's k-means 在 25 个 epoch 后达到的损失。它随 FAISS 1.16.0 发布，位于 faiss.contrib.e_means 下。对于任何构建向量索引、量化器或数据整理流水线的人来说，聚类往往是最慢的离线步骤。e-means 正是针对这一步骤。
TL;DR
规模：它是一种算法。测试范围从 10 万个点到 100 亿个点，最多 1670 万个簇。
运行于：CPU 或 GPU，支持 PyTorch 张量或 NumPy。论文中的 GPU 运行使用 H100。
性能：在 24 种数据集配置下（自报数据），以大约十分之一的 epoch 数达到比 Lloyd's k-means 更低的损失。
最佳：在相同损失下，相比 Flash-KMeans 获得 10-45 倍的 GPU 实际耗时加速。
最差：1600 万质心的运行需要 64 GiB 的 float32 累加器，因此质心必须跨 GPU 分片。
什么是 e-means？
e-means 是来自 Meta FAIR 的一种小批量 k-means 算法，它使用指数移动平均来更新质心。
e-means 如何工作？
每种 k-means 变体都为每个簇维护一个和 S 和一个计数 N。质心是 S 除以 N。各方法的区别仅在于 S 和 N 如何变化。
Lloyd 每次迭代都从完整数据集重新计算 S 和 N。
MacQueen（1967）会一直累加批次统计量，因此过时的分配永远不会被移除。
e-means 以速率 α 衰减旧统计量：S ← (1−α)S + αs，N 同理。
较旧的分配会逐渐淡出，因此质心会跟踪最近的数据。研究团队解释说，Lloyd 是一个特例：α = 1 的完整批次。在 DEEP 上，该特例比最佳损失高 1.8%。
团队测试了普通梯度下降作为替代方案。在其最佳设置下，它在 DEEP 上比 EMA 高 1.6%，在 SIFT 上高 0.4%。作者怀疑 EMA 胜出是因为质心始终保持在分配给它们的点的凸包内。
什么取代了超参数调优？
两个拟合的缩放定律根据数据集大小 n、簇数 k 和 epoch 数 T 来设置批次大小 B 和初始步长 α0。在留出数据集上，步长定律的中位遗憾为 0.07%。随后步长从 α0 到 0.1α0 遵循余弦调度。
还有什么变化？
死簇复活：低于大小阈值的簇通过拆分一个大簇来复活。
收尾：训练在每个集群精确的最后一个 epoch 均值上结束。
融合 GPU 内核：最近质心分配被融合，因此节省的 epoch 变成节省的秒数。
[EMBED: e-means 交互式讲解器]
e-means 在基准测试中有多快？
以下所有数字均由作者自行报告。
Epoch 数：e-means 在 1.4 到 2.6 个 epoch 内就超过了 Lloyd 25 个 epoch 的损失。
GPU：相比 Flash-KMeans 实现 10-45 倍的实际耗时加速。
CPU：相比 Faiss k-means 实现 8-15 倍加速。
VIBE 基准测试：全部 11 个嵌入数据集都只需 1.6 到 2.4 个 epoch。
十亿规模：DINO10B，100 亿个 1,024 维嵌入，在 2.5 个 epoch 内分成 1,670 万个集群。
发布帖展示了一个单 CPU 线程的演示。Lloyd 跑 25 个 epoch 用了 4.39 s。e-means 跑 2.2 个 epoch 用了 0.43 s。Lloyd 的一步触及 100,000 个点（0.176 s）。e-means 的一步触及 512 个点（0.001 s）。
小批量噪声也有助于逃离糟糕的局部极小值。在一个 5 团簇玩具数据上，Lloyd 在 200 次启动中有 46% 卡住。e-means 卡住的比例为 0%。
复活机制在大 k 下很重要。在具有 16,384 个集群的 DEEP 上，按比例分裂留下了 47 个死集群（0.3%）。关闭复活机制后，有 4,313 个集群（26.3%）死亡。
e-means 与其他 k-means 方案相比如何？
特性e-meansLloyd k-means (Faiss)Flash-KMeansscikit-learn MiniBatchKMeans更新规则EMA 小批量（博客）全批量 Lloyd全批量 Lloyd，精确（论文）小批量，Sculley 风格（文档）每次更新数据量来自缩放定律的批量 B全数据集全数据集1,024 个点（默认）除 k 之外的调参无（epoch 默认 5）迭代次数迭代次数batch_size、max_iter、reassignment_ratio、tol硬件CPU、GPU（已测试 H100）CPU、GPUNVIDIA GPU（已测试 H200）CPU达到 Lloyd 25 个 epoch 损失所需的 epoch 数1.4 到 2.6（论文）25（参考）与 Lloyd 相同（精确）未披露头条速度声明GPU 10-45 倍，CPU 8-15 倍（自行报告）基线相比最佳基线最高 17.9 倍（自行报告）未披露许可证MIT，通过 FAISS（维基百科）MIT未披露BSD-3-Clause（Debian）
关键要点
e-means 将 Lloyd 的全批量更新换成了 EMA 小批量。
在 1.4 到 2.6 个 epoch 内达到 25 个 Lloyd epoch 的效果。
GPU 上快 10-45 倍，CPU 上快 8-15 倍（自行报告）。
无需调参：缩放定律设定批量和步长。
现已在 FAISS 1.16.0 中提供。
查看论文、博客文章和 FAISS 代码。另外，欢迎在 Twitter 上关注我们，别忘了加入我们拥有 15 万+ 成员的 ML SubReddit 并订阅我们的新闻通讯。等等！你在用 Telegram 吗？现在你也可以在 Telegram 上加入我们。
需要与我们合作推广你的 GitHub 仓库、Hugging Face 页面、产品发布或网络研讨会等？联系我们
文章《Meta FAIR 发布 e-means：一种在少 10 倍轮次内击败 k-means 的算法》首发于 MarkTechPost。