Scalable k-Means Clustering via Lightweight Coresets

Understand

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.