姚班校友NeurIPS 2021 Spotlight论文：带有缺失坐标聚类问题的核心集

2021 年 11 月 11 日 机器之心

坐标缺失在现实的数据集中是很常见的现象，如何在有缺失坐标的情况下解决聚类问题是一个严峻的挑战。由于缺乏三角不等式，大部分传统的 K-means 算法在带有缺失坐标的数据集无法工作，甚至不是良好定义的。

直到近期，一篇 SODA2021 论文给出该问题的第一个多项式时间近似系统(PTAS)，然而该算法较为复杂，难以实现，且需要至少平方级别的运行时间。

核心集是一个常用的数据压缩工具，利用核心集可以加速近似算法和设计流算法 / 分布式算法。在此之前，对于有缺失坐标的 K-Means 问题，已有的算法最多只能解决每个点有一个缺失坐标的情况。

论文链接：https://arxiv.org/pdf/2106.16112.pdf

在一篇 NeurIPS 2021 Spotlight 论文中，研究者首次构造了允许有多个缺失坐标聚类问题的核心集。他们还进一步设计了一个准线性时间的算法来构造该核心集。该方法结合最新的 SODA2021 结果，可以得到第一个允许多个缺失坐标 K-Means 问题的准线性时间近似方案 (near-linear time approximation scheme)。研究还包含模拟与实验部分，算法易于实现且在各类数据集上的表现都显著优于由均匀抽样(Uniform Sampling) 构造的核心集。

这项研究包含两个主创新点：

利用组合技巧，证明了一种从带缺失坐标的 K-center 问题的核心集，到传统 K-center 问题的核心集的规约。结合已知的 K-center 核心集到 K-means 核心集的规约，证明了该问题核心集的存在性。
为了在准线性时间构造出该核心集，研究设计了一种专门针对传统 K-center 核心集的动态算法。该动态算法能够在 poly(log n)时间完成数据集合的增减后对 K-center 核心集的更新。该动态算法基于随即投影和一个简单的数据结构。

11月15日晚8点，机器之心 NeurIPS 2021 线上系列分享邀请到该论文作者之一、约翰霍普金斯大学 (JHU) 计算机系博士生吴旋为我们解读这项研究。 论文共同作者还包括约翰霍普金斯大学副教授Vladimir Braverman，北京大学助理教授姜少峰和以色列魏茨曼科学研究所教授Robert Krauthgamer。按照理论计算机科学界的习惯，论文作者按照姓氏的首字母排序。

分享主题：带有缺失坐标聚类问题的核心集

分享摘要 ：本工作为带有多个缺失坐标的聚类问题(Clustering)，特别是 K-Means 问题设计第一个有理论保证的核心集(Coreset)，此前的算法最多只能处理有一个缺失坐标的情况。本工作还提供一个准线性时间的算法来构造该核心集。我们的方法结合上最新的 SODA2021 结果，可以得到第一个带缺失坐标 K-Means 问题的准线性近似系统(near-linear time approximation scheme)。本工作还提供相应的实验来证明算法的实用性。

嘉宾介绍：吴旋，约翰霍普金斯大学 (JHU) 计算机系博士第四年在读，导师 Vladimir Braverman。他的研究兴趣主要是理论计算机科学和机器学习。在加入 JHU 之前，吴旋在清华大学理论计算机科学实验班 (姚班) 取得了本科学位，并在清华大学交叉信息研究院取得了硕士学位，指导教师为李健。从 JHU 毕业后，吴旋将加入由陆品燕老师领导的上海华为理论计算机实验室，担任研究员。

分享时间 ：11 月 15 日 20:00-21:00

直播间 ：关注机动组视频号，北京时间 11 月 15 日开播。