大数跨境

两名高中生改进 Meta e-means,聚类误差再降55%

两名高中生改进 Meta e-means,聚类误差再降55% AINLP
2026-11-17
0
导读:好算法还能接着改

前几天介绍的超越 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 越低,表示数据点到分组中心的平均平方距离越小。

方法
训练轮次
测试MSE
耗时
e-means
1
92.44
15.2毫秒
e-means
8
65.68
36.1毫秒
s-means
1
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

【声明】内容源于网络
0
0
AINLP
一个有趣有AI的自然语言处理公众号:关注AI、NLP、大模型LLM、机器学习、推荐系统、计算广告等相关技术。公众号可直接对话双语聊天机器人,尝试对对联、作诗机、藏头诗生成器、自动写作等,查询相似词,测试NLP相关工具包。
内容 6131
粉丝 0
AINLP 一个有趣有AI的自然语言处理公众号:关注AI、NLP、大模型LLM、机器学习、推荐系统、计算广告等相关技术。公众号可直接对话双语聊天机器人,尝试对对联、作诗机、藏头诗生成器、自动写作等,查询相似词,测试NLP相关工具包。
总阅读41.1k
粉丝0
内容6.1k