博主头像

Meta 改写 K-Means,训练轮次降到十分之一​ | K-Means | e-means |

外来客 • 2026-11-16 20:46:18

分享
𝕏 f ◉
声明:本文为对公开内容的摘要整理, 未经本站独立核实,可能与原内容存在出入,不代表本站立场、观点或建议; 观点与版权归原作者及原平台所有。 如涉及版权问题,请联系我们,核实后立即删除。 [ 免责声明 ]

🎯 核心观点

  • Meta FAIR 团队提出 e-means 算法,通过重写聚类中心更新方式,将 K-Means 达到同等质量所需的训练轮次压缩至原来的 1% 左右。
  • 该方案未改变目标函数,而是利用指数移动平均(EMA)替代传统的累加统计量,解决了小批量更新中参数难以确定及收敛误差较高的问题。

📊 关键事实与论据

  • 性能提升:在 DINO10B 数据集实验中,实际耗时加速 45.5 倍;相比 FlashK-Means 跑 25 轮,e-means 仅需 1.4 至 2.6 轮即可达到同等误差。
  • 算法机制:采用 EMA 维护中心统计量,赋予早期分配记录衰减权重;引入死簇复活机制,当某中心样本数低于阈值时从大簇拆分补充,避免容量浪费。
  • 参数自动化:通过拟合样本规模、簇数量与训练轮次的关系,自动推导批次大小和更新步长,消除了手动调参需求,在未见数据集上误差增幅仅约 0.19%。
  • 工程实现:结合低精度计算(BF16/Int8)与核函数优化,减少显存读写;支持倒排文件索引近似加速,使 100 亿向量聚类可在单台 8 卡 H100 机器上运行约 3 小时。
  • 局部最优规避:小批量带来的随机波动有助于跳出局部最优解,实验中陷入不理想分组的概率从 Lloyd 算法的 26% 降至 3.5%。

💡 结论

  • e-means 显著降低了大规模向量检索中聚类步骤的计算成本,使索引重建频率得以提高。
  • 该算法在训练和测试误差上均优于传统 Lloyd 算法及 K-Means++ 初始化方案,且代码已集成至 Faiss 仓库(模块名 e_means),为高维数据聚类提供了高效、低门槛的解决方案。

博主头像 👤 同一博主

查看该博主全部 198 篇

🧭 类似博主

0 条评论

发表评论

请先 登录 后参与讨论。