姚班校友NeurIPS 2021 Spotlight论文：带有缺失坐标聚类问题的核心集 坐标缺失在现实的数据集中是很常见的现象，如何在有缺失坐标的情况下解决聚类问题是一个严峻的挑战。由于缺乏三角不等式，大部分传统的 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 日开播。 交流群：本次直播设有 QA 环节，欢迎加入本次直播交流群探讨交流。 如群已超出人数限制，请添加机器之心小助手：syncedai2、syncedai3、syncedai4 或 syncedai5，备注「NeurIPS」即可加入。 机器之心 · 机动组 机动组是机器之心发起的人工智能技术社区，聚焦于学术研究与技术实践主题内容，为社区用户带来技术线上公开课、学术分享、技术实践、走近顶尖实验室等系列内容。机动组也将不定期举办线下学术交流会与组织人才服务、产业技术对接等活动，欢迎所有 AI 领域技术从业者加入。 点击阅读原文，访问机动组官网，观看往期回顾； 关注机动组服务号，获取每周直播预告。 阅读原文