Timezone: »

 
Poster
Fast and Provably Good Seedings for k-Means
Olivier Bachem · Mario Lucic · Hamed Hassani · Andreas Krause

Tue Dec 06 09:00 AM -- 12:30 PM (PST) @ Area 5+6+7+8 #175
in Tuesday Posters »

Seeding - the task of finding initial cluster centers - is critical in obtaining high-quality clusterings for k-Means. However, k-means++ seeding, the state of the art algorithm, does not scale well to massive datasets as it is inherently sequential and requires k full passes through the data. It was recently shown that Markov chain Monte Carlo sampling can be used to efficiently approximate the seeding step of k-means++. However, this result requires assumptions on the data generating distribution. We propose a simple yet fast seeding algorithm that produces provably good clusterings even without assumptions on the data. Our analysis shows that the algorithm allows for a favourable trade-off between solution quality and computational cost, speeding up k-means++ seeding by up to several orders of magnitude. We validate our theoretical results in extensive experiments on a variety of real-world data sets.

Keywords: Clustering · MCMC · Large Scale Learning and Big Data

Author Information

Olivier Bachem (ETH Zurich)
Mario Lucic (ETH Zurich)
Hamed Hassani (ETH Zurich)
Andreas Krause (ETH Zurich)

More from the Same Authors