Scalable k-Means Clustering via Lightweight Coresets

研究的问题

核心集是数据的紧凑表示，成功应用于海量数据的聚类问题。本文提出一种新的轻量级核心集构造方法，通过并行得到更小的核心集，来更好的推广到K-Means算法中。

研究动机

大数据时代下的海量数据集给聚类问题带来巨大困难，核心集应用而生。现有的核心集方法通常指允许乘法误差。因此本文的研究重点是提出一种针对于K-Means算法的核心集构建方法，该方法不仅具有现有核心集的优点，允许乘法误差和加法误差，而且所需的成本大大减少。

先进性与贡献

本文提出了一种新的轻量级核心集构建方法，允许加法和乘法误差。通过并行算法构建轻量级核心集，成本低。该方法可进一步扩展到布雷格曼分歧的软硬聚类。通过实验，证实了该方法的实用性。

具体方法

1. 首先准备数据： n x d的数据集X（n个样本、d个属性），核心集规格大小m
2. 计算X的均值𝜇
3. 循环计算重要性采样分布概率q(x)： 对于每个x∈X，q(x) =1/(2|X|) + d(x, 𝜇)^2/(2∑x’∈X d(x’, 𝜇)^2)
4. 得到轻量级核心集C：m个加权点来自于X，每个点的权重为1/(mq(x))，以概率q(x)来采样得到。

优缺点及思考：

本文提出的新的轻量级核心集构造方法以采样足够多的点为保证，其在维数d中是线性的并且在聚类k的数量中接近线性。本文提出的轻量级核心集构建算法很容易并行化实施，并且可以在两轮分布式程序中实现，而且该方法可以进一步扩展到布雷格曼分歧的软硬聚类。

对于统计k均值问题的目标是在Rd中找到k个聚类中心，使预期量化误差最小。本文提出的方法可用于在经验风险最小化的背景下进一步总结任何样本X，通常需要尽可能大的样本X以保证较好的近似质量，但轻量级核心集的尺寸远小于X。

2018.10.5