NeurIPS 2016oral216 citations
Fast and Provably Good Seedings for k-Means
Olivier Bachem, Mario Lucic, Hamed Hassani, Andreas Krause
Abstract
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
BibTeX
@inproceedings{NIPS2016_d67d8ab4,
author = {Bachem, Olivier and Lucic, Mario and Hassani, Hamed and Krause, Andreas},
booktitle = {Advances in Neural Information Processing Systems},
editor = {D. Lee and M. Sugiyama and U. Luxburg and I. Guyon and R. Garnett},
pages = {},
publisher = {Curran Associates, Inc.},
title = {Fast and Provably Good Seedings for k-Means},
url = {https://proceedings.neurips.cc/paper_files/paper/2016/file/d67d8ab4f4c10bf22aa353e27879133c-Paper.pdf},
volume = {29},
year = {2016}
}