ICML 2023 | k-median问题可以只用均匀采样解决吗？
关键词：聚类，均匀采样，数据摘要
导 读
本文是 ICML 2023 入选论文 The Power of Uniform Sampling for -Median 的解读。该论文由北京大学前沿计算研究中心姜少峰课题组与南京大学计算机软件新技术国家重点实验室的黄棱潇副教授合作完成。按照理论计算机科学领域惯例，作者按姓名首字母排序。
文章针对 -median 聚类问题，探索使用多少个随机采样样本足以计算出原数据集上的 -近似最优聚类中心。论文主要解决了 的情况并且能够推广至不同的度量空间。
论文链接：
https://arxiv.org/abs/2302.11339
01
问题介绍
-median 问题是一个经典的聚类问题，旨在寻找一个大小为 的点集作为聚类中心，使得所有数据点到聚类中心的距离和最小化。我们称一个聚类中心 是一个 -近似最优解，当且仅当
其中， 为最优聚类中心。
近年来，如何使用数据摘要（data reduction）方法解决聚类问题成为了研究焦点。其中一种被广泛研究的数据摘要方法为核心集（coresets）。简单来说，一个 -核心集是一个极小数据摘要，使得对于所有的聚类中心 ，在核心集上计算得到的目标函数的值与在原数据集上计算得到的值的相对误差不超过 。通过在核心集上运行近似算法，我们可以得到原数据集上的一个近似最优解。
然而目前已有的所有核心集构造算法在查询复杂度（query complexity）上不够高效。特别地，这些算法必须访问数据集 次（ 为数据集大小），而这是因为核心集构造算法依赖于非均匀采样，需要访问整个数据集以计算复杂的采样分布。另外，这种复杂的采样过程也使得算法通常在实践中难以实现。
为了得到具有亚线性询问复杂度（即， 复杂度）的数据摘要算法，我们考虑一种非常自然的方法——均匀采样。尽管先前工作已经证明均匀采样无法在亚线性询问复杂度内得到核心集，但是均匀采样依然凭借着其简单的算法流程在实践中被广泛运用，并且通常能取得不错的实际效果。本文旨在从理论上分析均匀采样作为数据摘要方法的询问复杂度。
02
主要结果
在实践中，我们通常希望得到的聚类是平衡的，即希望每个类都包含几乎相同数量的数据点。
因此，我们尝试在询问复杂度与数据平衡性之间建立联系。定义数据集 的平衡系数 为最大的在 之间的实数满足：存在 的一组最优 -median 聚类方案使得每个类包含的点数至少为 。本文首先证明了一个理论下限：任何一个可以计算 -近似最优解的算法必然有询问复杂度 ，其中 为数据的平衡系数。在极端情况下， 可以等于 ，即存在一个类只包含一个点，此时询问复杂度的理论下界为 。因此该结论同样否定了在没有任何假设的情况下，亚线性询问复杂度算法的存在性。
另一方面，我们证明了如果假设数据集的平衡系数 ，那么均匀采样算法足以用于设计亚线性询问复杂度算法。具体来说，我们证明了：对于一个欧氏空间中的数据集 ，若它的平衡系数为 ，假设我们从 中均匀采样 个样本得到集合 ，那么我们可以利用 计算出在原数据集 上的 -近似最优解。我们的算法同样非常简单，只需要在 上计算一个带有平衡系数限制的 -median 问题的 -近似最优解即可。我们通过证明这个解就是在原数据集上的 -近似最优解，从而证明了该结论。
值得注意的是，该结论在关于 的相关性上已经接近了理论极限，并且做到了与数据集规模 以及欧氏空间维度 无关。对比先前的工作，[MOP04] 同样考虑了平衡假设，但是只得到了一个具有常数近似比的算法；[MS18, CSS21, Dan21] 考虑了 的情况（在这个情况下， ），但是在他们的结果中，询问复杂度或者与 有关，或者具有一个较差的 的因子。
除此之外，本文的结果还可以拓展到其他度量空间，比如加倍空间（doubling metric space）和有限树宽的图的最短路度量（shortest-path metrics of graphs with bounded treewidth）。
最后，本文在多个数据集上测试了均匀采样的效果。我们对数据集进行采样，在采样样本上运行了一个针对 -median 问题的局部搜索算法（不带平衡系数限制），并估计解在原数据集中的近似比。实验结果表明，均匀采样具有出色的数据摘要能力。此外，通过比较数据集的平衡系数（ ）和计算得到的聚类的平衡系数（ ），我们发现在样本集上使用不带平衡系数限制的聚类算法通常可以计算出平衡的解。结合我们的理论结果，这解释了为什么在实践中，通常只需要在样本集上运行聚类算法即可得到不错的解。
参考文献
[CSS21] Vincent Cohen-Addad, David Saulpic, and Chris Schwiegelshohn. Improved coresets and sublinear algorithms for power means in Euclidean spaces. In NeurIPS, pages 21085–21098, 2021.
[Dan21] Matan Danos. Coresets for clustering by uniform sampling and generalized rank aggregation. Master’s thesis, Weizmann Institute of Science, 2021.
[MOP04] Adam Meyerson, Liadan O'Callaghan, and Serge A. Plotkin. A -median algorithm with running time independent of data size. Mach. Learn., 56(1-3):61–87, 2004.
[MS18] Alexander Munteanu and Chris Schwiegelshohn. Coresets-methods and history: A theoreticians design pattern for approximation and streaming algorithms. Künstliche Intell., 32(1):37–53, 2018.
图文 | 楼家宁
北京大学姜少峰课题组
姜少峰课题组近期动态
— 版权声明 —
本微信公众号所有内容，由北京大学前沿计算研究中心微信自身创作、收集的文字、图片和音视频资料，版权属北京大学前沿计算研究中心微信所有；从公开渠道收集、整理及授权转载的文字、图片和音视频资料，版权属原作者。本公众号内容原作者如不愿意在本号刊登内容，请及时通知本号，予以删除。
点击“阅读原文”转论文链接