开发者生态
morning
SuperEMeans:使 e-means 速度提高 3 倍
2026-11-19
1 阅读
约8分钟阅读
lkuffo2
字号:
TL;DR:我们融合了 SuperKMeans 和 e-means,使高维向量的聚类速度提高了 3 倍,而无需牺牲质量。现已在 https://github.com/cwida/SuperKMeans 提供。最近,围绕向量嵌入的聚类有很多讨论:EVōC、SuperKMeans、QGKmeans,以及上周的 e-means、o-means 和 s-means。其中,e-means 是一件大事:它只需要 2 个 epoch 就能保证与 Lloyd's 相同的质量。为什么这对于矢量搜索来说很重要?嗯,聚类是大规模向量索引(例如 IVF、ScANN)的关键构建块,这恰恰是用户在发出相似性搜索查询之前必须等待的瓶颈。一年前,我们发布了 SuperKMeans 。 SuperKMeans 通过避免在聚类时扫描向量维度,将 Lloyd 的 k 均值加速 2-10 倍,且不会影响聚类质量。 SuperKMeans 已迅速被业界(ParadeDB、Zilliz、FAISS)采用,这表明提高高维向量的聚类性能是多么及时。然而,e-means 也令人兴奋,因为它通过运行更少的 epoch 来解决工作量问题。传统上,向量嵌入的聚类被标准化为 10 epoch。 e-means 承诺只需 2 个 epoch 即可实现相同(或更好)的聚类质量。我建议您查看 e-means 作者制作的精彩网站:https://e-means.github.io/ 有趣的是,在他们的论文中,作者提出 SuperKMeans 的修剪维度的想法与 e-means 是正交的。我们一致认为:这两种观点并不存在任何对立之处。自然,这让我们开始工作!设置 我们扩展了我们的聚类库来实现 e-means 和 SuperEMeans(开源于 https://github.com/cwida/SuperKMeans),并测量了它们的好处。数据集:我们将使用两个数据集:i) 来自 VectorDBBench 基准的 5M 1536 维 OpenAI 嵌入:https://huggingface.co/datasets/makneeee/openai_large_5m。 (27 GB)。 ii) 第一个嵌入 Cohere Embed V3 模型的 10M MS MARCO 段落(1024 维向量):https://huggingface.co/datasets/Cohere/msmarco-v2.1-embed-english-v3 (40 GB)。索引:我们将构建一个每簇点比为 1:256 的 IVF 索引,为 OpenAI 生成约 20,000 个质心,为 Cohere 数据集生成约 40,000 个质心。设置:对于本实验,我将使用一台具有 16 个内核和 128 GB RAM 的 Zen 5 机器( r8a.4xlarge | $1.278/小时)。然而,我们的 SuperKMeans 库适用于任何 CPU(例如 Intel、Graviton、Zen)。结果 下图比较了 Lloyd’s(10 次迭代)、SuperKMeans(10 次迭代)、e-means(2 epoch)和 SuperEMeans(2 epoch)的端到端聚类运行时间。 SuperEMeans 大幅加速了 e-means,速度提高了 1.8 倍。但是……这是一个高质量的索引吗?让我们比较一下每种方法获得的质心在矢量搜索任务上的表现。对于此分析,我们向 IVF 索引发出 1000 个查询。然后,我们在扫描 1% 的可用集群 (recall@100) 时测量前 100 个检索结果在真实前 100 个结果中的比例。我们还通过计算扫描这些簇时执行的距离计算的数量来比较簇的平衡。 OpenAI 的结果总结在下表中: 算法运行时间(秒)平均。在 1% 的探测质心平均处召回@100。在探测质心 1% 处扫描的向量 Lloyd’s k-means (10 iters) 985 0.962 52 053 SuperKMeans (10 iters) 232 0.962 51 993 e-means (2 epoch) 203 0.967 58 184 SuperEMeans (2 epoch) 128 0.967 58 198 e-means(2 epoch,作者的实现) 333 0.967 58 111 Recall@100 在 e-means 中略高。然而,我们最终在搜索过程中扫描了大约 10% 左右的向量。为了匹配扫描的向量数量,我们必须在 e-means 中探测稍少的簇,大约占总簇的 0.90%。这导致在扫描 51,962 个向量时,recall@100 = 0.964,从而最终获得比传统 k 均值更好的权衡。 Cohere: Algorithm Runtime (s) Avg 的情况也是如此。在 1% 的探测质心平均处召回@100。在探测质心 1% 处扫描的向量 Lloyds k-means (10 iters) 2504.4 0.919 112 714 SuperKMeans (10 iters) 623.3 0.919 112 547 e-means (2 epoch) 525.8 0.923 135 380 SuperEmeans (2 epochs) 295.3 0.923 135 463 e-means (2 epochs, 作者的实现) 927.1 0.925 136 185 同样,我们必须探测 e-means 中稍少的簇,大约占总簇的 0.90%。扫描 121,511 个向量时,recall@100 = 0.918。在这里,这种差距对 e-means 不利,因为 e-means 会为相同的召回扫描多 8% 的向量。为什么 e-means 扫描更多向量?在 e-means 中,在最常查询的向量空间区域中,簇比 Lloyd's k-means 中的簇更加膨胀。然而,e-means 达到的 WCSS (MSE) 较低,因为该目标不会奖励平衡的集群,而矢量搜索则为其扫描的每个点付费。注意
这篇文章对您有帮助吗?
订阅66必读
每日精选科技资讯,直达你的邮箱