SODA 2026 | 近线性时间的聚类局部搜索算法

欧式空间中的 -Means 聚类是组合优化领域的核心问题之一。给定一个   维欧氏空间中的数据集 ，该问题旨在寻找一个包含  个中心点的集合 ，以最小化所有数据点到  中最近中心的欧氏距离平方和，即最小化目标函数针对这一问题，若聚类中心数  较小或数据维度   较低，已有算法可在几乎线性的  时间内计算出  近似解，其中  为任意常数^{[CFS21, DSS24]}。然而，在一般参数设定下（即  与  可任意取值），  -Means 问题的最优运行时间与近似比之间的关系依然是一个开放问题。目前，已有一些基础的理论下界被证明：当数据维度  时（ 为数据点个数），-Means 问题被证明是 APX-hard 的^[ACKS15]，因此我们只能期望得到常数近似算法；另一方面，在一般度量空间中，任意常数近似算法的运行时间存在一个下界 ^[MP04]。因此，若要突破平方时间瓶颈，我们必须充分利用欧氏空间的结构特性。

在欧氏空间中，一个自然的目标是实现 LSH 权衡，即在  时间内计算 -近似解，其中  是任意常数。这一结果与“在欧氏空间中计算最近点对”这一基本任务的当前最优效率一致（事实上，当  时 -Means 等价于该问题）；由于该结果依赖的核心技术是局部敏感哈希（Locality Sensitive Hashing, LSH），因此这种时间复杂度与近似比之间的权衡被称为 LSH 权衡。值得一提的是，对于相关的聚类问题，如设施选址问题（Facility Location）、-Median 以及 -Center，已有实现了 LSH 权衡的高效算法。然而，如何在 -Means 问题中同样实现 LSH 权衡，仍然是一个尚未解决的重要开放问题。目前，最接近这一目标的结果来自于 la Tour 和 Saulpic 的最新工作 ^[lTS25]，他们在  时间内实现了 -近似。

本文设计了一种新颖的局部搜索算法变体，在欧氏空间的  -Means 问题中完全实现了 LSH 权衡。

定理 1 对于任意常数  ，存在一个欧氏空间  -Means 问题的  -近似算法，运行时间为   。

除 -Means 问题之外，该算法能够应用到更广泛的 -Clustering 问题（ 时为 -Median,  时为 -Means），且同样实现 LSH 权衡。除了在  为任意参数的最坏情况以外，当 （）时，亦即针对中等大小的 ，我们可以将该结果与聚类问题的核心集（Coreset）技术 ^[HM04] 相结合，得到  时间复杂度的  -近似算法。

我们的主要技术结果是一个针对图最短路径度量空间的快速聚类算法，如 定理 2 所示。定理 1 则是通过将 定理 2 直接应用于已有工作^[HIS13]所构造的 spanner（即数据集的稀疏图表示）而得到的结果。

定理 2 存在一个针对图最短路度量空间的  -Means 问题的常数近似算法，其在具有  条边的图上运行时间为  。

该算法是首个针对图上   -Means 问题的近线性时间算法，且同样适用于更一般的  -Clustering 问题。此前，仅存在针对图上  -Median（  ）问题的近线性时间算法^[Tho04]。与这一结果相比，我们的算法在近似比上取得了改进（由 9 提升至 6）。

利用 spanner 技术，我们的算法可应用于多种度量空间，包括存在 LSH 的度量空间（如  度量空间与 Jaccard 度量空间），以及有限倍增维度的度量空间（Doubling Metric Spaces）。

我们的算法是一种针对聚类问题的局部搜索（Local Search）算法的变体。局部搜索算法通常遵循如下的基本框架：从一个粗糙的初始解  开始，算法不断选取一个中心交换对    并执行更新  来改进当前解，直至得到一个常数近似解。

不难发现，中心交换对的选取策略是影响局部搜索算法的时间复杂度的关键因素之一。先前的局部搜索算法均采用贪心策略，即选择能够最大幅度提升解质量的交换对   。在这种贪心策略下，虽然可以证明算法在  次迭代后即可收敛到常数近似，但每次迭代的计算开销仍然是高次多项式级，从而整体运行时间依旧偏大。一些工作（例如^[LS19]）尝试通过随机采样来加速对  的选取，但对  的选择仍然沿用贪心方式；这种加速虽然将总运行时间降到了  ，但距离近线性时间仍有显著差距。

我们提出了一种新的中心交换对选取策略，该策略在选择过程中显式地将执行交换的时间代价纳入考量，从而成功突破了传统局部搜索算法的平方时间瓶颈。 

为了更清晰地揭示贪心策略所面临的瓶颈，并说明我们新策略背后的核心思想，我们引入一个用于衡量局部搜索算法效率的中间指标，称为“聚类调整代价”（Clustering Recourse）。假设局部搜索算法除了维护当前解  外，还同时维护由  所诱导的聚类结构，记为  ，其中每个数据点都被分配到其在  中的（近似）最近中心（一般而言，这样的聚类结构需要由某个数据结构来维护；在此，我们暂且假设该数据结构已经存在并给定）。当执行更新  后，原有的聚类结构不可避免地发生变化，某些数据点需要重新分配，以确保它们始终被指派到相应的（近似）最近中心。局部搜索算法的聚类调整代价被定义为算法过程中数据点重新分配的总次数。

维护一个聚类结构是合理且必要的：局部搜索算法需要依赖这一结构来判断每一次对解  的更新是否能够带来改进。因此，聚类调整代价在直觉上刻画了该聚类结构在整个过程中需要被更新的次数，从而给出了局部搜索算法运行时间的一个下界。

先前的贪心选择策略无法控制聚类结构的更新次数。理论上，每次对  的更新在最坏情况下可能导致  个数据点被重新分配。因此，整个局部搜索过程的聚类调整代价只能被保证为  。如前所述，这正是以往局部搜索算法无法突破平方运行时间瓶颈的根本原因所在。

为了突破传统贪心策略所面临的  时间瓶颈，我们提出一个新的强高效准则（Super-effective Rule）来选取中心交换对。在每一步迭代中，我们识别那些强高效的交换对 ，其满足其中， 表示当前聚类  中被分配给中心  的数据点集合。直观上，这一条件要求：如果一次交换带来的聚类调整越多，那么它对聚类质量的提升也必须相应地足够大。需要强调的是，这里的条件仅考虑了删除  所引发的调整代价 ，而刻意忽略了插入  的代价。这是因为插入  的代价可以通过一种对聚类的“延迟更新”技巧在均摊意义上得到很好的控制；相对地，删除  所产生的调整代价才是真正的瓶颈，这也正是促使我们提出上述强高效准则的动机所在。

可以证明，若局部搜索的每轮迭代都依据该强高效准则选取  ，则整个算法过程中所有由删除引发的聚类调整代价之和可以被严格控制在  。结合我们对插入操作采用的延迟更新策略，我们最终得到一个总聚类调整代价为  的局部搜索算法。

上述讨论主要集中在“聚类调整代价”这一中间指标。要想在整体运行时间上真正突破平方级瓶颈，我们必须进一步构造一个能够高效维护聚类  的数据结构，并设计算法在每一轮迭代中快速找出满足强高效准则的交换对。为此，我们利用图的一些良好性质，在最短路度量空间上成功构造了一个满足所有技术要求的数据结构，使得整个局部搜索过程能够在  时间内完成，从而得到 定理 2 的结果。

[ACKS15] Pranjal Awasthi, Moses Charikar, Ravishankar Krishnaswamy, and Ali Kemal Sinop. The hardness of approximation of euclidean k-means. In SoCG, volume 34 of LIPIcs, pages 754–767. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2015.

[CFS21] Vincent Cohen-Addad, Andreas Emil Feldmann, and David Saulpic. Near-linear time approximation schemes for clustering in doubling metrics. J. ACM, 68(6):44:1–44:34, 2021.

[DSS24] Andrew Draganov, David Saulpic, and Chris Schwiegelshohn. Settling time vs. accuracy tradeoffs for clustering big data. Proc. ACM Manag. Data, 2(3):173, 2024.

[HIS13] Sariel Har-Peled, Piotr Indyk, and Anastasios Sidiropoulos. Euclidean spanners in high dimensions. In SODA, pages 804–809. SIAM, 2013.

[HM04] Sariel Har-Peled and Soham Mazumdar. On coresets for k-means and k-median clustering. In STOC, pages 291–300. ACM, 2004.

[LS19] Silvio Lattanzi and Christian Sohler. A better k-means++ algorithm via local search. In ICML, volume 97 of Proceedings of Machine Learning Research, pages 3662–3671. PMLR, 2019.

[lTS25] Max Dupré la Tour and David Saulpic. Faster and Simpler Greedy Algorithm for k-Median and k-Means. CoRR, abs/2407.11217, 2025.

[MP04] Ramgopal R. Mettu and C. Greg Plaxton. Optimal time bounds for approximate clustering. Mach. Learn., 56(1-3):35–60, 2004.

[Tho04] Mikkel Thorup. Quick k-median, k-center, and facility location for sparse graphs. SIAM J. Comput., 34(2):405–432, 2004.

图文 | 楼家宁

PKU 姜少峰Lab