e-means 加速大规模 k-means 聚类
作者提出 e-means,一种基于指数移动平均的迷你批量 k-means 算法,并利用标度律为不同问题规模和嵌入数据集设置衰减率与批量大小。作者报告,e-means 在 1.2–3 轮内达到低于 Lloyd k-means 的损失,GPU 端到端耗时较 Flash-KMeans 降低 10–45 倍,CPU 较 Faiss 降低 8–15 倍;代码已进入 Faiss 的 contrib 目录。
e-means 试图用自动调参的迷你批量更新降低大规模嵌入聚类和向量量化的计算成本,但这些性能数字目前主要由作者实验报告。
An order of magnitude less epochs
Across a large range of scales and datasets, e-means reaches a test loss below Lloyd's at 25 epochs, in 1.2 to 3 epochs. Measured end to end, that is a 10–45× wall-clock reduction on GPU against the state-of-the-art Lloyd implementation (Flash-KMeans[2]), and 8–15× on CPU against Faiss[1]. Speed and quality usually trade against each other in k-means, while e-means achieves both better speed and loss.

The k-means problem
Given a fixed dataset of n points X = {x 1, ..., x n} ⊂ R d and an integer k, the k-means problem is to find k centroids C = (c 1, ..., c k) minimizing the mean squared distance between each point and its nearest centroid:
$$ M S E \left(\right. X , C \left.\right) = \frac{1}{n} \sum_{i = 1}^{n} \parallel x_{i} - c_{a \left(\right. i \left.\right)} \parallel^{2} , a \left(\right. i \left.\right) = arg \underset{j \in \left{\right. 1 , \ldots , k \left.\right}}{min } \parallel x_{i} - c_{j} \parallel^{2} $$
#e-means#Faiss#Flash-KMeans#DINO10B#VIBE#Lloyd k-means#k-means++