E-means: Outperforming k-means in one-tenth the epochs
514 points
• 3 days ago
• Article
Link
e-means 算法代表了聚类领域的一项重大进展，由 Meta FAIR 开发，旨在弥补传统 Lloyd's 算法的不足。尽管 Lloyd's 仍是全批次 k-means 的标准，但它往往运行缓慢，而且容易陷入次优的局部极小值。 e-means 通过采用基于指数移动平均的现代小批次方案，实现了在 epoch 计数和挂钟时间上的约 10 倍加速，同时还能提升最终的聚类质量。
e-means 的核心更新规则使用指数移动平均来跟踪各个聚类质心。对于静态数据集而言，这种方法比标准的梯度下降更稳定、更高效。通过调整每个聚类的总和与计数统计量的更新方式，算法能够"忘记"更早期、可能较差的分配，使模型把注意力放在更近期的数据模式上。该方法高度可并行，并通过专门的 GPU kernels 进一步优化，从而把理论效率真正转化为实际的性能收益。
e-means 的一个突出优势是不需要手动调参。借助推导出的特定缩放定律，算法会根据数据集特征自动确定最优的批次大小和步长，减轻了使用者的负担，并确保模型在不同规模的数据上都能保持高水平性能。此外，算法还加入了一套可靠的 dead-cluster 复活策略：当某些聚类数据不足时，会通过对大型活跃聚类进行拆分来替换它们，从而避免计算资源被浪费，并提升整体覆盖度。
该算法在逃离局部极小值方面也展现出更强能力，这是 Lloyd's 常见的问题。由于 e-means 采用小批次，其更新天然更具噪声，从而促进对优化空间的更充分探索。对包括合成任务与复杂嵌入任务在内的数十个数据集进行实验验证表明：e-means 在仅 1.2 到 3 个 epoch 的训练内，就能达到 Lloyd's 经过 25 个 epoch 后取得的测试损失。与此同时，算法还配有一个最终的质心微调阶段，在几乎不增加额外运行时间的情况下，进一步保证结果质量。
总的来说，e-means 为传统聚类方法提供了一种现代、稳健且更易用的替代方案。它现已集成到 Faiss 库中，便于用户将该技术轻松融入现有工作流程。通过用经过智能调优的小批次更新替代全批次优化，e-means 给出了一个切实可行的方案，能够在机器学习应用中同时兼顾通常相互矛盾的速度与聚类精度需求。
The e-means algorithm represents a significant advancement in clustering, developed at Meta FAIR to address the limitations of the traditional Lloyd's algorithm. While Lloyd's remains a standard for full-batch k-means, it is often slow and prone to getting stuck in suboptimal local minima. By transitioning to a modern, mini-batch approach that utilizes exponential moving averages, e-means achieves a speedup of roughly 10 times in both epoch count and wall-clock time, while simultaneously improving the final clustering quality.
The core of the e-means update rule relies on exponential moving averages to track cluster centroids, a technique that proves more stable and efficient for static datasets than standard gradient descent methods. By adjusting how sum and count statistics are updated for each cluster, the algorithm ensures that older, potentially poor assignments are forgotten, allowing the model to focus on recent data patterns. This approach is highly parallelizable and further optimized through specialized GPU kernels, which effectively translate the theoretical efficiency into real-world performance gains.
A standout feature of e-means is its ability to operate without the need for manual hyperparameter tuning. Through the derivation of specific scaling laws, the algorithm automatically determines the optimal batch size and step size based on the dataset's characteristics. This removes the burden from the practitioner, ensuring that the model maintains peak performance across various scales of data. Additionally, the algorithm incorporates a robust dead-cluster revival strategy, where clusters with insufficient data are replaced by splitting large, active clusters, thereby preventing the waste of computational capacity and improving overall coverage.
The algorithm also demonstrates a superior ability to escape local minima, a common pitfall for Lloyd's. Because e-means uses mini-batches, the updates are inherently noisier, which encourages better exploration of the optimization landscape. Experimental validation across dozens of datasets, including synthetic and complex embedding tasks, confirms that e-means consistently reaches the test loss achieved by Lloyd's after 25 epochs in just 1.2 to 3 epochs. This efficiency is complemented by a finalization stage that fine-tunes the centroids, ensuring high-quality results with minimal extra runtime.
Ultimately, e-means provides a modern, robust, and user-friendly alternative to legacy clustering methods. It is now available as part of the Faiss library, allowing users to easily integrate the technique into existing workflows. By replacing full-batch optimization with intelligently tuned mini-batch updates, e-means offers a practical solution that reconciles the usually opposing requirements of speed and clustering accuracy in machine learning applications.
81 comments • Comments Link
• 层次式增量聚类（Hierarchical incremental clustering）可以显著减少 shard splits 等操作期间的重索引时间；与标准方法相比，批量构建（bulk builds）的性能最高可提升 2.5 倍。
• 尽管该算法为常规聚类带来了性能改进，但它并非 Lloyd's algorithm 的通用替代方案。尤其是在网格松弛（mesh relaxation）等几何任务中，直接计算往往优于带噪声的 minibatch 估计。
• 将该方法适配到 GPU 上的 IVF indexing 能带来巨大的加速效果，其中一项实现报告称处理效率提高了 146 倍。
• 该更新规则可以理解为期望最大化（expectation maximization）与摩擦项（friction term）的结合，从而使 centroids 始终位于凸包（convex hull）内——这是聚类中非常关键的稳定性特征。
• 该方法表明：NP-hard 问题的近似解往往比理论上的最优解更有价值。于是研究重点从"追求完美结果"转向"追求高效、可落地的近似"。
• 该领域仍可能受益于更有组织的研究方向，例如提供概率保证的算法，或利用低维流形（low-dimensional manifolds）的算法，类似于 Bloom filters 或 compressive sensing 。
• 一些批评者认为，这项贡献更多体现为实证验证而非算法创新。他们指出，在分布式环境中，扩展性能最终会被通信成本限制，而不只是计算效率。
• 在实践中，这项技术擅长把大规模、高维数据（例如数十亿条 email messages）分成有意义的聚类，其速度比传统 K-means 快得多。
• 除了速度之外，该技术还表现出更强的鲁棒性，能避免一些常见伪影（artifacts），例如 split centroids 或冗余分组。原因在于 minibatches 的噪声特性有助于算法跳出局部极小值（local minima）。
• 对所提出的超参数定律（hyperparameter laws）仍存在质疑。有观察者认为这些定律更像是事后拟合（post-hoc），而非来自对优化地形（optimization landscape）的第一性原理理解。
讨论普遍体现出对这类实用、高性能聚类技术的赞赏：它们在理论最优性之外，更强调速度与可落地性。尽管部分参与者对这些方法在高度分布式场景中的可扩展性持谨慎态度，但总体共识认为，该算法为向量索引（vector indexing）和大规模数据分组带来了切实的现实改进。最终，这段对话凸显了计算机科学中的一个反复出现的主题：与其执着于难以实现的精确最优，不如完善那些能够带来巨大效率提升的近似、鲁棒启发式算法。 • Hierarchical incremental clustering can significantly reduce reindexing times during operations like shard splits, with bulk builds seeing performance gains of up to 2.5x compared to standard methods.
• While the algorithm offers performance improvements for general clustering, it is not a universal replacement for Lloyd's algorithm; specifically, for geometric tasks like mesh relaxation, direct calculation remains superior to noisy minibatch estimates.
• Adapting the method for IVF indexing on GPUs can yield massive speedups, with one implementation reporting a 146x increase in processing efficiency.
• The update rule can be interpreted as expectation maximization combined with a friction term, which maintains centroids within the convex hull—a crucial stability property for clustering.
• This approach demonstrates that approximate solutions to NP-hard problems are often more valuable than theoretically optimal ones, shifting the focus from perfect results to efficient, high-utility approximations.
• The field could benefit from more organized study of algorithms that provide probabilistic guarantees or exploit low-dimensional manifolds, similar to Bloom filters or compressive sensing.
• Some critics argue the contribution is less about algorithmic novelty and more about empirical validation, noting that scaling performance is ultimately constrained by communication costs in distributed environments rather than just compute efficiency.
• In practice, the technique excels at grouping large-scale, high-dimensional data—such as billions of email messages—into meaningful clusters significantly faster than traditional K-means.
• Beyond raw speed, the technique exhibits improved robustness by avoiding common artifacts like split centroids or redundant groupings, as the noisy nature of minibatches helps the process escape local minima.
• Skepticism remains regarding the provided hyperparameter laws, with some observers suggesting they appear to be fitted post-hoc rather than derived from a first-principles understanding of the optimization landscape.
The discussion reflects a broad appreciation for practical, high-performance clustering techniques that favor speed and utility over theoretical optimality. While some participants express caution regarding the scalability of these methods in highly distributed settings, the consensus acknowledges that the algorithm offers tangible, real-world improvements for vector indexing and large-scale data grouping. Ultimately, the conversation highlights a recurring theme in computer science where the focus shifts from pursuing intractable exact solutions to refining approximate, robust heuristics that provide massive gains in efficiency.