12月25日论文推荐

论文标题：

calable k-Means Clustering via Lightweight Coresets

作者：

Olivier Bachem (Google Brain & ETH Zurich)

Mario Lucic (Google Brain)

Andreas Krause (ETH Zurich)

推荐理由：

“Scalable k-Means Clustering via Lightweight Coresets”是Google Brain团队在KDD Research Track上的一篇文章，这是Google在瑞士的团队作品，瑞士这帮人还是比较喜欢理论的，这篇文章也是和社会网络中比较喜欢理论研究的、瑞士理工的Andreas Krause教授合作的文章。

基本思想就是做一个快速k-means算法或者说适用于大规模数据的k-means算法，具体思路是利用抽样的方法从原始数据中抽样出一个足够小的子集（称为Coresets），然后在这个Coresets上进行训练，最后得到的结果和在大规模数据上的结果相当。文章理论证明了保证精度的情况下Coreset大小和数据集的特征个数d以及聚类个数据k的乘积成正比

由于是篇理论文章，所以文章的实验相对比较简单，对比了两种方法，一种是随机抽样（Uniform），还有一种是Lucic等人提出的经典算法CS。几个数据集还行，都相对比较小，看来作者真的不想做实验室。最后的结果也表明作者提出的方法LWCS可以把误差降低到16%，并且同时保持两个数量级的加速度。

下表给出了在这几个数据集（KDD—KDD CUP2004里面的一个匹配蛋白质序列的竞赛、CSN—手机加速传感器的数据、Song—预测音乐的年份、RNA—预测RNA的序列对）上的实验结果。

摘要：

Coresets are compact representations of data sets such that models trained on a coreset are provably competitive with models trained on the full data set. As such, they have been successfully used to scale up clustering models to massive data sets.

While existing approaches generally only allow for multiplicative approximation errors, we propose a novel notion of lightweight coresets that allows for both multiplicative and additive errors.

We provide a single algorithm to construct lightweight coresets for k-means clustering as well as soft and hard Bregman clustering.The algorithm is substantially faster than existing constructions, embarrassingly parallel, and the resulting coresets are smaller.

We further show that the proposed approach naturally generalizes to statistical k-means clustering and that, compared to existing results, it can be used to compute smaller summariesfor empirical risk minimization. In extensive experiments, we demonstrate that the proposed algorithm outperforms existing data summarization strategies in practice.