跳到主要内容
返回时间线
arXiv来源发表:

小簇不再一律清除:给 e-means 的复活规则加一道距离检验,孤立小簇的测试误差降一到八成

核心概要

FAISS 中的 e-means 每五个小批次按簇大小清除小簇并复用其中心,但小簇可能只是覆盖了远离其他点的稀有群体,清除代价很高。新规则在大小检验之外增加一道距离检验:只有当小簇中心与最近另一中心的平方距离不超过当前均方误差估计的若干倍时才清除。在开发阶段未使用的含孤立小簇数据集上,两轮后的测试误差相对按数量复活降低约 10% 到 80%,而在 e-means 论文的嵌入基准上结果与库实现完全一致。

Source-provided article image: Small Is Not Dead: Distance-Aware Cluster Revival for e-means
arXiv

深度剖析

e-means 的复活规则现在多了一个判断依据:一个小簇是否被清除,不再只看它有多小,还要看它的中心离最近的另一个中心有多近。 原规则每五个小批次把计数低于平均计数十分之一的簇判为候选并清除,只依据簇大小,无法区分冗余小簇与覆盖稀有孤立点群的小簇。 在 UCI Covertype 标准化特征上,使用原规则的 e-means 两轮后测试误差比 25 次迭代的 Lloyd 算法高 58%,关闭复活则低 24%,说明差距来自清除规则而非移动平均更新。

做法是保留原有的大小候选集,再为每个簇维护一个批次失真的移动平均,用候选中心到最近另一中心的平方距离与全局均方误差估计之比作为门槛。 这个比值在中心等于其点均值时,是清除该中心后每点平方误差平均增幅的上界,因此门槛把清除限制在代价不超过当前误差尺度若干倍的情形。 在 e-means 论文的三个嵌入数据集、最多一千万点和中心的四种配置上,距离检验从未阻止任何一次清除,全部运行与库实现逐位一致。

在含孤立小簇的留出数据集上,新规则保住了按数量规则会反复清除的中心,测试误差明显下降。 按数量复活在这些数据上会把稀有群体的中心移走,把点并入远处中心,误差反而上升。 两轮后相对按数量复活,测试误差在 KDD Cup 99 上降低约 25% 到 80%、Shuttle 上约 20% 到 75%、GeoNames 上约 10% 到 25%,具体取决于中心数;在其他评估数据集上则与开启或关闭复活中较好者相差约 1% 以内。

启示与展望

结果来自 FAISS 1.16 中 e-means 的 NumPy CPU 实现,表格数据最多两百万点,嵌入评估覆盖论文中最多一千万点和中心的配置,其中一千万点配置只用于核对与库实现的一致性。规则不需要新的 GPU 内核,但 GPU 与多 GPU 实现及更大规模数据未运行。

分析预测的两处失效已被报告:检验忽略替换被清除簇的拆分所带来的误差下降,且在 YearPredictionMSD 上相对按数量复活的测试误差最多高出约 3%;检验用单一的全局误差尺度,在宽窄簇尺度差异大的二维混合数据上,随机初始化下相对按数量复活的均方误差中位数上升约 7%。放弃条款在实验中很少触发,去掉它对结果影响可忽略;阈值在 2 到 8 之间结果接近,更大取值会放弃部分收益。