前几天介绍的超越 k-means 的 e-means,又有后续了。
70年经典算法大升级,Meta e-means 用1/10轮次超越 k-means
两名高中生沿着 Meta 的这套开源算法,继续改出了 s-means。
Şuayp Talha Kocabay 和 Kerem Yalçın 都来自土耳其 TÜBİTAK Science High School,这次与 Feedzai 的 Kamer Ali Yüksel 共同署名发布了技术文章和代码。
团队在 T4、L4 和 A100 上分别跑了9组测试,相比 e-means,s-means 的测试集聚类误差平均下降约 54%—55%。其中一组 A100 实验里,s-means 训练1轮,误差就低于 e-means 训练8轮的结果。
s-means 已经做成独立的开源库,支持 PyTorch、Triton GPU 内核和 scikit-learn 接口。
项目在三类GPU上的测试 纵轴为相对e-means的测试MSE降幅
把算法交给进化搜索
上篇的 e-means,把 k-means 从“读完整批数据再移动中心”,改成了小批次更新,再用指数移动平均、闲置簇复活和自动选参,减少训练轮次。
s-means 保留了这个基本框架,但继续追问:同样只训练一到几轮,聚类中心能不能放得更好?
他们没有只盯着学习率调参,而是把算法拆成初始化、更新、复活、收尾等7个可替换模块,交给 EvoForest 做进化搜索。
EvoForest 会改写候选计算结构,再用评测结果决定哪些改法值得留下。这次搜索在 CPU 上进行,设了4个“岛屿”,运行9轮进化。候选算法拿到相同的训练轮次预算,在8组数据上比较训练误差和留出集误差,耗时与内存开销也会影响得分。
把中心用在更需要的地方
先改起点。随机抽一些数据点作为中心,在分布不均匀的数据里,可能把多个中心放进同一片密集区域,少数区域却没有照顾到。训练只有一两轮,后面未必来得及挪过去。
s-means 先抽一个小样本池,用4轮按距离加权的抽样选初始中心。离已有中心越远的点,越有机会被选中。 这一步在小样本上做,避免为了初始化就对全量数据反复计算。
更大的改动,是闲置中心应该从哪里“复活”。
e-means 会把一个活跃簇拆成两个略微错开的中心,让闲置中心重新参与分组,点数多的簇更容易被选中。但一个簇里点多,并不一定意味着它分得差:密集的一团点,可能已经被一个中心照顾得很好;另一团数据虽然点少,却铺得很散。
s-means 因此多记了一份统计量:每个簇还剩多少平方距离误差。 挑选拆分对象时,误差成为主要依据,点数继续参与加权。
拆开时也不再简单把中心坐标乘上一个微小扰动。那样一来,中心靠近零点就几乎挪不动,坐标整体平移后,扰动又可能突然变大。新办法根据簇内误差决定分开的距离,再结合各个特征方向的尺度调整方向。
最后一轮的收尾也做了调整:后处理的批次权重稍高,样本很少的簇则把最后一轮均值与之前的平滑中心混合,减少少量样本带来的摆动。
作者的 CPU 消融实验里,拿掉“误差加权与按方向调整的复活策略”,平均测试误差改善会从约 19.9% 缩到7.1%。拿掉新的初始化,改善也会减少约2.6个百分点。主要收益集中在前面两处,收尾调整的影响小得多。
项目消融结果 移除误差与方向相关的复活策略影响最大
一轮赢过八轮
在 A100 上,作者把20万条128维向量分成1024个簇,比较不同训练预算下的结果。测试 MSE 越低,表示数据点到分组中心的平均平方距离越小。
|
|
|
|
|
|---|---|---|---|
|
|
|
|
|
|
|
|
|
|
|
|
|
32.21 | 33.5毫秒 |
s-means 这1轮的误差,已经不到 e-means 8轮的一半,实际耗时还略少。 但同样只跑1轮,e-means 用时更短,新增的初始化和统计并非没有成本。
下面原图左边按训练轮次比较,右边按实际耗时比较。红色是 e-means,绿色是 s-means;右图还加入了 L4 的结果。
项目原图 左为轮次与误差 右为实际耗时与误差
这9组 GPU 测试包含高斯混合、长尾分布、不同方向尺度的数据,也包含真实的 Covertype 数据。
不同任务的收益差别很大。A100 上,高斯混合任务的误差下降约77.5%,Covertype 则约为3.1%。
团队还把算法固定下来,在没有参与前面搜索的12组 CPU 数据上测试,每组运行5个随机种子。相对 e-means,平均测试 MSE 下降 19.67%,耗时中位数约为其 0.98倍,整体接近;相同训练轮次下,相对 scikit-learn 的 MiniBatchKMeans,速度中位数约为 2.24倍。
项目CPU测试 左为误差改善 右为耗时与内存比较
速度还得看具体任务
s-means 用 Triton 融合距离计算和最近中心选择,不把整个“批大小×簇数量”的距离矩阵写进显存;更新中心、统计误差和最后一轮累计等操作,也尽量合并。CPU 版本则把距离计算分成适合缓存的小块。
在 A100 的百万条128维向量、2048个簇实验中,s-means 的额外工作区显存约为 71.2MB,e-means Triton 版本约为 84.6MB。对应耗时却是 61.1毫秒对43.1毫秒:这一组选择的是更低误差和更少工作区,速度没有赢过优化后的 e-means。
项目GPU实现比较 左为耗时 右为额外工作区显存
低维任务也有明显的慢例子。20万条8维数据、512个簇的设置里,s-means 会用小批次跑很多步;目前它还在逐步执行 Python 循环,而 e-means 已经用上 CUDA Graph。s-means 的误差更低,但完成得更慢。
T4 则是另一种情况:它不支持 BF16/TF32 Tensor Core,强行走某些 Triton 路径并不划算。s-means 的自动模式在这类卡上选择原生 FP32 实现,在 A100、L4 上才优先走 BF16 Triton。
最后
项目目前是独立 Python 包,安装后就能接到已有的 scikit-learn 流程里:
git clone https://github.com/suayptalha/s-means.git
cd s-means
pip install -e .
CPU 上可以这样用:
from smeans import SMeans
model = SMeans(
n_clusters=256,
nepochs=3.0,
device="cpu",
random_state=0,
)
labels = model.fit_predict(X)
GPU 版本可以安装 pip install -e ".[triton]",再把 device 设为 "cuda"。
参考链接
-
s-means 技术文章:https://suayptalha.github.io/s-means-blog/ -
s-means 项目:https://github.com/suayptalha/s-means
-
e-means 论文:https://arxiv.org/abs/2611.09501 -
EvoForest 论文:https://arxiv.org/abs/2604.19761

