ICALP 2024 | 高维聚类问题——基于大规模并行计算下的完全可扩展算法

关键词：大规模并行计算，高维欧氏空间，聚类

导读

本文是对已被 ICALP 2024 接收的 Fully-Scalable MPC Algorithms for Clustering in High Dimension 一文的解读。该工作由北京大学姜少峰课题组与英国、以色列、捷克的学者合作完成，论文主要贡献者之一高贵晨为北京大学计算机学院博士生。论文聚焦于大规模并行计算（Massively Parallel Computation, MPC）模型下高维欧氏空间中聚类问题，提出了一种新的用于几何聚合的 MPC 原语，并针对一系列聚类问题设计了完全可扩展的常数轮 MPC 算法。

↑扫码跳转论文

论文链接：

https://arxiv.org/abs/2307.07848

问题及背景

对大规模数据进行聚类是计算机科学中一项基本的计算任务，我们主要考虑欧氏空间下的 $k$ -median 问题。给定一个包含 $n$ 个数据点的集合 $P \subset \mathbb{R} ^d$ ，一个整数 $k\ge 1$ ， $k$ -median 问题是要找到一个大小至多为 $k$ 的数据集合 $C \subset \mathbb{R} ^d$ ，使得所有 $P$ 中的数据点到集合 $C$ 中最近点的距离和最小，即找到 $C \subset \mathbb{R} ^d$ 并最小化 $\operatorname{cl}(P, C):=\sum_{p \in P} \operatorname{dist}(p, C)$ 其中， $\operatorname{dist}(p,C)=\min _{c\in C}\left \|⁡p-c\right \|_2$ 表示 $p$ 点到 $C$ 中最近点的欧氏距离。另一个常与 $k$ -median 一同考虑的聚类问题是 $k$ -means。 $k$ -means 与 $k$ -median 的唯一不同点是目标函数中要对数据点到集合 $C$ 的距离求平方和。

均匀设施选址（Uniform Facility Location, UFL）是与聚类问题密切相关的一个问题。我们考虑欧氏空间下的 UFL 问题。给定一个数据集 $P \subset \mathbb{R} ^d$ 和设施开设代价 $\mathfrak{f} \gt0$ （每个设施的开设代价相同），UFL 的目标是要找到一个设施集合 $F \subset \mathbb{R} ^d$ ，使得开设代价和连接代价（所有数据点到最近开设设施的距离之和）的加和最小化，即找到 $F \subset \mathbb{R} ^d$ 并最小化 $\operatorname{fl}(P, F):=\left | F \right |\cdot \mathfrak{f} + \sum_{p \in P} \operatorname{dist}(p, F)$ MPC 模型最早由 Karloff、Suri 和 Vassilvitskii^[1]于2010年提出，是并行计算中一种重要的模型，可以用来建模 Hadoop、Spark 等众多实际广泛应用的并行计算框架。在 MPC 模型中，设有 $m$ 台机器，每台机器都有大小为 $s$ 的内存。典型情况下，假定内存为 $s=n^\alpha$ 且常数 $\alpha \in (0,1)$ ，其中 $n$ 是输入数据量的大小。此外，计算以同步轮进行，在每一轮中，任何一台机器都可以向/从任何其他机器发送/接收信息，前提是从/向每台机器传输的数据总量为 $O(s)$ 。MPC 算法的效率是通过轮数来衡量的，并且一般追求常数轮的算法。

除了轮数尽量追求常数轮，MPC 算法还应该是完全可扩展（Fully Scalable）的：即算法在任何内存参数 $s=n^\sigma, \sigma \in (0,1)$ 下都可以运行，尤其是对于 $k$ -median 而言，需要满足 $s$ 与 $k$ 无关；此外，由于我们考虑的聚类问题潜在可以是高维的，因此我们还需要满足 $s$ 是 $\operatorname{poly}(d)$ 量级（而不是 $d$ 的指数级）。目前，针对 $k$ -median 问题的完全可扩展且常数轮的工作较少^{[2, 3]}，仅有 $O(\operatorname{poly}(\log n))$ 近似，并且对于相关的 $k$ -means 问题，即使在低维（例如 $d=O(1)$ ）情况下也没有已知的有限近似。因此，为这些基本聚类问题在高维下设计完全可扩展、常数轮、常数近似的 MPC 算法是该领域的挑战之一。

主要结果

针对高维欧氏空间中的 UFL、 $k$ -median、 $k$ -means 问题，我们都得到了完全可扩展的常数轮 MPC 算法，并且对于 UFL 问题我们实现了常数近似。

定理1. 存在一个高概率成功的 MPC 算法，对任何 $n$ 个 $\mathbb{R} ^d$ 上的、分布式存储在内存 $s=n^\sigma\operatorname{poly}(d)$ 的数据点，可在 $O(1/\sigma)$ 轮使用 $n^{1+\varepsilon }$ 的总空间得到一个 $O(1/\varepsilon )$ -近似的 UFL 的解（分布式存储在各个机器上）。

对于 $k$ -median、 $k$ -means，我们得到了各项指标与定理1类似的 $(O(1/\varepsilon ),(1+\varepsilon ))$ -双标准近似，其中 $(\alpha,\beta)$ -双标准近似是指算法输出至多 $\beta k$ 个中心点，且其代价至多是 $k$ 个中心点的最优代价的 $\alpha$ 倍。该双标准近似是通过黑盒利用 UFL 的常数近似解得到的。相对于标准的、只能得到 $(O(1),O(1))$ -双标准近似的黑盒方法，我们的改进是只需要 $(1+\varepsilon)k$ 个中心。

技术概述

下面，我们将概述定理1算法的重要组成部分以及技术思想。我们首先给出一个更具有局部性的求解 UFL 的算法框架，然后讨论 MPC 上的实现问题。

3.1 UFL 的新局部算法

我们的新算法是对 Mettu-Plaxton (MP) 算法^[4]的改造。不失一般性地，设开设代价 $\mathfrak{f}=1$ 。原始的 MP 算法主要有两步：一是对每一个输入点 $p$ ，计算“半径值” $0\lt r_p \le 1$ ；二是按 $r_p$ 值非减的顺序，依次检查当前点 $p$ 其 $2r_p$ 距离之内是否有开设设施，若无，则开设点 $p$ 。由于我们只追求常数近似，我们可以利用^[5]提出的方法来近似计算 $r_p$ ：对每个数据点 $p$ ，可以通过估算 $O(\log n)$ 个以 $p$ 为球心，半径为 $r$ 的 $d$ 维球中数据点的数量来计算 $r_p$ 的常数近似。因此，这一步相对比较局部。但是，MP 算法的第二步则需要用到全局的顺序信息并且需要串行进行，这对于 MPC 乃至于一般的并行计算模型都较难实现。

因此我们提出了一个新的局部算法来替代第二步。具体而言，假定算法已经得到了第一步所有 $r_p$ 的估计值，我们给出以下两个独立的决策规则来决定每个数据点是否要开设为设施点：

P1：独立于其他数据点，每个数据点 $p$ 以概率 $\Theta(r_p)$ 开设为设施点；

P2：对每一个数据点 $p \in P$ ，分配一个独立随机标签 $h(p) \in [0,1]$ ，如果数据点 $q \in P$ 在 $B_P(q,r_q)$ 内具有最小的标签值，则将点 $q$ 开设为设施点，其中 $B_P(q,r_q)$ 代表 $P$ 与以 $q$ 为中心、 $r_q$ 为半径的球的交集。

我们讨论上述两个决策规则的设计动机。首先可以证明这两个决策的期望开设代价是最优解的常数倍，因此主要应该关注这两个决策对于连接代价的影响。P1 的规则倾向于较为均匀的开设设施，直觉上可以较好解决比较均匀的数据集。然而，如果数据集含有极远的孤立点，则 P1 可能会有概率不在这种孤立点开设设施，从而产生极大的连接代价。P2 可以一定程度上弥补这点：在孤立点的小邻域内一定会开设一个设施（开在 $h$ 值最小的点上）。不过需要注意的是只有 P2 也是不够的：对于1维下均匀排列的数据集： $1,2,\dots,n$ ，在半径值 $r\ge1$ 时，仅使用规则 P2，则除了 $h$ 值最小的点之外，其他数据点都不会开设为设施，所以该情况下的连接代价同样会很大。

因此，对于新的局部算法的分析，尤其是将互相影响的 P1 和 P2 的随机性统筹考虑，是本工作的主要技术贡献。

3.2 MPC 实现：新的几何聚合 MPC 原语

为了实现完全可扩展的常数轮 MPC 算法，注意到 $r_p$ 值的估计只需要实现对某个半径 $r$ 估算每个以数据点 $p$ 为球心的球里面的点数；而对于局部 MP，只有规则 P2 是不直接的，但也可以转化成对某个半径 $r$ 计算每个以数据点 $p$ 为球心的球里面具有最小标签的点。

上述步骤均可以建模成一个几何聚合问题，即都可以看做是对某个“可聚合”的函数值的计算。我们称函数 $f$ 是可聚合的，如果对每一个不相交的集合 $S_1,\dots,S_t\subset \mathbb{R}^d$ ，可以通过计算 $f(S_1),\dots,f(S_t)$ 的值来得到 $f(S_1\cup \dots \cup S_t)$ 。我们对估计 $r_p$ 值的统计量以及实现 P2 时关于最小标签点的计算，可以分别采用求和或求 $\min$ 的 $f$ 来实现。

我们提出了一个可在高维欧氏空间下计算一般的可聚合 $f$ 的 MPC 算法。具体而言，给定一个包含 $n$ 个数据点的集合 $P \subset \mathbb{R} ^d$ ，一个可聚合函数 $f:\mathbb{R} ^d \to \mathbb{R}$ ，以及参数 $r$ ，存在一个确定性完全可扩展的 MPC 算法，在常数轮对每个数据点 $p\in P$ 计算值 $v_p \approx f(B(p,r))$ 。由于其一般性和广泛适用性，我们认为这可以成为一个新的 MPC 原语。技术上，我们采用了近期在数据流算法设计中提出的一致哈希函数^[6]来解决高维球相交结构过于复杂、导致复杂性不可控的问题。

因此，利用新提出的局部算法，结合新的 MPC 原语，我们可以在常数轮得到 UFL 问题的完全可扩展的 MPC 算法，且近似比为常数。

总结

本文探索了高维欧式空间中一系列聚类问题的完全可扩展的 MPC 算法，提出了适用于高维欧氏空间的几何聚合 MPC 原语。尽管本文的研究给出了常数双标准近似的 $k$ -median、 $k$ -means，但是否存在完全可扩展的、真正常数近似的 $k$ -median、 $k$ -means 依然是一个重要的开放性问题。

参考文献

[1] Howard J. Karloff, Siddharth Suri, and Sergei Vassilvitskii. A model of computation for MapReduce. SODA 2010.

[2] Aditya Bhaskara and Maheshakya Wijewardena. Distributed clustering via LSH based data partitioning. ICML 2018.

[3] Vincent Cohen-Addad, Silvio Lattanzi, Ashkan Norouzi-Fard, Christian Sohler, and Ola Svensson. Parallel and efficient hierarchical k-median clustering. NeurIPS 2021.

[4] Ramgopal R. Mettu and C. Greg Plaxton. The online median problem. SIAM Journal on Computing 2003.

[5] Mihai Bădoiu, Artur Czumaj, Piotr Indyk, and Christian Sohler. Facility location in sublinear time. ICALP 2005.

[6] Artur Czumaj, Arnold Filtser, Shaofeng H.-C. Jiang, Robert Krauthgamer, Pavel Veselý, and Mingwei Yang. Streaming facility location in high dimension via geometric hashing. FOCS 2022.

图文 | 高贵晨

北京大学姜少峰课题组

姜少峰课题组近期动态

本微信公众号所有内容，由北京大学前沿计算研究中心微信自身创作、收集的文字、图片和音视频资料，版权属北京大学前沿计算研究中心微信所有；从公开渠道收集、整理及授权转载的文字、图片和音视频资料，版权属原作者。本公众号内容原作者如不愿意在本号刊登内容，请及时通知本号，予以删除。

点击“阅读原文”转论文地址

内容中包含的图片若涉及版权问题，请及时与我们联系删除

ICALP 2024 | 高维聚类问题——基于大规模并行计算下的完全可扩展算法

评论