🤖 machine learning

A Fast and Effective Method for Euclidean Anticlustering: The Assignment-Based-Anticlustering Algorithm

本文介绍了基于分配的反聚类（Assignment-Based Anticlustering, ABA）算法，这是一种用于将大规模欧几里得数据集划分为不相似组的可扩展且高效的方法，在求解质量和计算速度方面均显著优于现有技术。

原作者： Philipp Baumann, Olivier Goldschmidt, Dorit S. Hochbaum, Jason Yang

发布于 2026-06-24

📖 1 分钟阅读☕ 轻松阅读

原作者： Philipp Baumann, Olivier Goldschmidt, Dorit S. Hochbaum, Jason Yang

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你正在组织一场拥有数千名宾客的大型派对。你的目标是将他们分成若干小组，但有一个非常特殊的规则：你希望每个小组中的人彼此之间尽可能地不同。

在数据科学领域，这被称为反聚类（Anticlustering）。通常，聚类旨在将相似的事物聚集在一起（比如把红色的弹珠和蓝色的弹珠分开），而反聚类则恰恰相反：它试图确保每个小组都是整个人群的完美“微缩代表”，既包含高个子也包含矮个子，既有吵闹的人也有安静的人。

这篇论文介绍了一种全新的、超快速的方法来实现这一目标，叫做 ABA（基于分配的反聚类，Assignment-Based Anticlustering）。以下是它的工作原理，我将使用简单的类比来解释：

问题所在：“随机洗牌”陷阱

想象你有100万名宾客，需要将他们分成10万个小组。

旧方法（随机划分）： 你把所有人的名字扔进一个帽子里，然后随机抽取并分配到各个小组中。
- 缺陷： 如果小组数量较少，这样做效果还可以。但如果小组数量非常多，你最终会得到一些全是“吵闹”的人的小组，以及另一些全是“安静”的人的小组。小组之间是不平衡的。
现有的高科技方法（交换法）： 这些算法从随机洗牌开始，然后花费数小时不断在小组之间交换人员，试图来修复这种平衡。
- 缺陷： 这就像是通过一次移动一件物品来试图整理乱糟糟的房间。对于100万名宾客来说，这可能需要几天甚至几周的时间。对于现代需求（如训练AI模型）来说，这太慢了。

新的解决方案：ABA 算法

作者提出了一种既快速又聪明的组织派对的方法。把它想象成一条“智能分拣线”。

第一步：“中心性”队列
首先，算法会衡量每位宾客相对于整个人群的“中心性”或“平均程度”。

想象有一条线，其中最“平庸”（处于人群特征正中间）的宾客站在一端，而最“极端”或“独特”的宾客站在另一端。
算法将所有人按照从最极端到最平均的顺序排列在这条线上。

第二步：“批次”发放
算法不是一个接一个地发放宾客，而是以**批次（Batches）**的形式进行抓取。

它取出线上的前100人（最极端的那些），并给每个小组分发一人。
然后它取出接下来的100人（稍微没那么极端的），再给每个小组分发一人。
它不断重复这个过程，直到所有人都被分配完毕。

为什么这很神奇？
因为每一个小组都恰好获得了一个来自“极端”端的人，一个来自“中间”的人，以及一个来自“平均”端的人。

结果： 每个小组在多样性方面看起来都与其它小组完全相同。它们都是整个人群的完美微缩版本。
速度： 因为它只需沿着这条线走一遍并分发批次，所以它不需要花费数小时去交换人员。它可以几秒钟或几分钟内组织好数百万人。

论文中提到的现实世界用途

论文强调，这种速度对于以下场景至关重要：

机器学习： 在训练人工智能时，你需要向它喂入小规模的“小批量（mini-batches）”数据。如果这些批次缺乏多样性，AI的学习效果就会很差。ABA可以瞬间创建这些批次。
社会研究与心理学： 创建完美平衡的测试组，以便研究人员可以公平地比较结果。
医学研究： 对患者样本进行分组，从而最大限度地减少“批次效应”（由不同时间处理样本引起的误差）。

处理海量数据的“作弊码”

论文还提到了一种针对数据量极其庞大（例如600万人）时的“层级化”技巧。

与其试图一次性将600万人分成10万个小组，ABA将问题分解。
它首先将这些人分为100个大组，然后将每个大组再细分为1,000个小组。
这就像组织图书馆：先按类别对书籍进行分类，然后在每个类别内按作者进行排序，而不是试图一次性为整个图书馆进行字母排序。这使得过程更快，且不会损失质量。

结论

作者测试了 ABA 与现有的最佳方法（包括一个著名的工具 METIS）的对比。

速度： ABA 通常比其他方法快了数千倍。在其他方法需要数小时或数天时，ABA 仅需数秒。
质量： ABA 产生的分组比随机洗牌更平衡，且通常优于那些缓慢、复杂的算法。
可扩展性： 它是第一个能够高效处理拥有数百万项数据和数十万个小组的数据集的算法。

简而言之，这篇论文展示了一种新的数据“流水线”，它能确保每个小组都具有完美的差异性，而且完成时间仅为以往所需时间的零头。

技术摘要：一种快速且有效的欧几里得反聚类方法

问题定义

本文研究的是欧几里得反聚类（Euclidean Anticlustering）问题，这是一个 NP-hard 的组合优化任务。其目标是将 $N$ 个对象（表示为 $D$ 维欧几里得空间中的特征向量）划分为 $K$ 个大小近似相等的组（即反聚类）。与旨在最小化组内距离的传统聚类不同，反聚类旨在最大化同一反聚类内对象之间的两两平方欧几里得距离之和。

其目标是创建成员之间尽可能不相似的组，从而确保每个反聚类都能代表整个数据集。该问题广泛应用于各个领域，包括社会科学（创建具有可比性的参与者组）、生物医学研究（限制测序中的批次效应）以及机器学习（为随机梯度下降生成小批量数据，以及为交叉验证创建具有代表性的折叠/folds）。

文中还考虑了一个特定的变体——带类别的欧几里得反聚类（Euclidean Anticlustering with Categories），其中对象属于特定类别，且每个反聚类必须包含来自每个类别相等（或接近相等）数量的对象。此外，该问题还与**平衡 K-切分（Balanced K-cut）**问题相关联，即旨在最小化切分代价（组间边权之和），这在完全图中以欧几里得权重为基础时，在数学上等同于最大化组内平方距离之和。

现有方法面临显著的可扩展性挑战。精确方法（如混合整数规划）仅限于处理小规模实例（通常 $N \le 100$ ）。基于交换的方法（如 fast-anticlustering）等启发式方法往往需要计算所有的两两距离或进行昂贵的最近邻搜索，这使得它们在处理百万级规模的数据集和较大的 $K$ 值时，计算成本高得难以承受。

方法论：基于分配的反聚类（ABA）算法

作者提出了一种名为**基于分配的反聚类（Assignment-Based Anticlustering, ABA）**的新型构造启发式算法。其核心创新在于避免计算完整的 $N \times N$ 距离矩阵，而是利用欧几里得平方和度量的特性来解决一系列分配问题。

核心机制

全局质心与排序： 算法首先计算数据集的全局质心。然后，所有对象根据其到该全局质心的平方欧几里得距离进行降序排列。
分批（Batching）： 排好序的列表被分为 $B = \lceil N/K \rceil$ 个批次。第一个批次包含距离最远的 $K$ 个对象，第二个批次包含接下来的 $K$ 个，依此类推。
迭代分配：
- 第一个批次初始化 $K$ 个反聚类（每个对象成为一个单元素反聚类）。
- 对于后续的每个批次，算法解决一个最大权重分配问题（具体为线性分配问题），将当前批次中的 $K$ 个对象分配到现有的 $K$ 个反聚类中。
- 该分配的代价矩阵由当前批次中的对象与反聚类当前质心之间的平方欧几里得距离定义。
- 至关重要的是，算法依赖于事实 1，该事实确立了：最大化反聚类内的平方距离之和，等同于最大化对象与其反聚类质心之间的平方距离之和。这使得算法可以计算到质心的距离（复杂度 $O(K)$ ），而不是所有的两两距离（复杂度 $O(K^2)$ ）。
- 分配完成后，更新反聚类的质心。
终止： 该过程重复进行，直到所有批次都被分配完毕。算法的运行时间为 $O(NK^2)$ ，主要受分配步骤支配。

变体

带类别的 ABA： 为了处理类别约束，初始排序进行了修改。对象按到全局质心的距离进行排序，但随后进行重新排列，以确保相同类别的对象在各批次中均匀分布。在分配过程中，如果分配某个对象会违反类别平衡约束，则将对应的代价矩阵项设为一个极大的负值（实际上是禁止该分配）。
层次化分解： 对于极大的 $K$ 值（例如 $K=100,000$ ），解决 $K \times K$ 的分配问题会成为瓶颈。作者提出了一种层次化策略，将问题分解为多个层级（例如，先创建 $K_1$ 个组，然后将每个组进一步细分为 $K_2$ 个组）。这把复杂度从 $O(NK^2)$ 降低到了 $O(N \sum K_\ell^2)$ ，在对解质量影响极小的情况下显著提高了执行速度。

核心贡献

可扩展性： 引入了 ABA 算法，该算法可以扩展到拥有数百万个对象和数十万个反聚类的实例，并在秒级或分钟级内完成求解。这超越了现有基于交换的启发式方法和精确求解器的能力。
解的质量： 该算法在目标函数值（多样性）方面始终优于最先进的方法（特别是 R 包 anticlust 中的 fast-anticlustering 启发式方法和 METIS 图划分工具）。
反聚类相似性： 除了最大化多样性外，ABA 本身就能产生具有高**反聚类相似性（anticluster similarity）**的解。由于算法将每个距离范围（批次）的对象都分配给每个反聚类，因此生成的组具有相似的统计特性（内部距离的均值和方差），这是交换式方法经常忽略的一个理想特征。
处理类别与大规模 $K$ ： 论文提供了针对带类别约束的反聚类以及针对超大规模 $K$ 值的层次化分解的具体变体，展示了优于现有方法的性能。
全面的评估： 作者在 16 个多样化的数据集（从表格数据到像 ImageNet 这样高维的图像数据）上进行了广泛的计算研究，并与包括随机划分、精确求解器（针对小规模实例）和领先的启发式算法在内的多个基准进行了对比。

实验结果

实验研究从三个主要维度验证了该算法的性能：

与领先启发式方法的比较： 在源自 16 个数据集的 111 个问题实例中，ABA 始终比 fast-anticlustering 算法（P-N5, P-R5, P-R50, P-R500）获得更高的目标函数值。对于较大的 $K$ （例如 $K=5,000$ ），ABA 的解平均比 P-N5 高出 16% 以上，比随机划分高出 30% 以上。
运行时间： ABA 的速度高出几个数量级。当竞争对手的启发式方法在两小时的时间限制内无法找到解时，ABA 仍能在秒级解决大型实例。例如，在 ImageNet32 数据集（ $N \approx 1.28$ 百万）上，ABA 在 500 秒内解决了 $K=640,000$ 的实例，而随机划分是唯一能在时限内完成的方法，但其质量显著较低。
反聚类相似性： 诸如反聚类多样性的标准差和范围等指标表明，ABA 产生的组比交换式方法更加平衡。交换式方法倾向于产生具有高度差异化多样性水平的反聚类，而 ABA 的多样性分布则紧凑且一致。
平衡 K-切分： 在应用平衡 K-切分问题时，ABA 在解质量和运行时间方面均优于最先进的 METIS 算法，尤其是在较大的 $K$ 值情况下。
层次化分解： 在 ImageNet32 数据集上的实验表明，层次化分解可以将 $K=5,000$ 时的运行时间从超过 3,900 秒缩短至约 44 秒，且解质量损失微乎其微（<0.02%）。

意义与主张

本文声称，ABA 通过解决限制此类方法应用于大规模数据集的可扩展性瓶颈，代表了欧几里得反聚类领域的重大进展。作者强调，虽然随机划分在 $K$ 较小时通常足够，但随着 $K$ 的增加，其质量会迅速下降，因此需要像 ABA 这样的算法。

ABA 的意义在于两个方面：

实际效用： 它使得将反聚类应用于机器学习（如小批量生成）及其他领域中百万级规模的数据集成为可能，而在这些领域，以往的方法要么太慢，要么产生的解质量过低。
统计稳健性： 它独特地解决了第二个目标——反聚类相似性，确保生成的组不仅具有多样性，而且在统计上是可比的，这对于交叉验证和实验设计等应用至关重要。

作者总结道，ABA 的设计依赖于预排序和批次分配，提供了一个稳健的框架，该框架可以潜在地推广到其他多样性问题，如最大多样性问题（Maximum Diversity Problem）或带复杂约束的反聚类问题。