Timezone: »

 
Poster
Fast and Accurate $k$-means++ via Rejection Sampling
Vincent Cohen-Addad · Silvio Lattanzi · Ashkan Norouzi-Fard · Christian Sohler · Ola Svensson

Wed Dec 09 09:00 AM -- 11:00 AM (PST) @ Poster Session 3 #1086
in Poster Session 4 »
$k$-means++ \cite{arthur2007k} is a widely used clustering algorithm that is easy to implement, has nice theoretical guarantees and strong empirical performance. Despite its wide adoption, $k$-means++ sometimes suffers from being slow on large data-sets so a natural question has been to obtain more efficient algorithms with similar guarantees. In this paper, we present such a near linear time algorithm for $k$-means++ seeding. Interestingly our algorithm obtains the same theoretical guarantees as $k$-means++ and significantly improves earlier results on fast $k$-means++ seeding. Moreover, we show empirically that our algorithm is significantly faster than $k$-means++ and obtains solutions of equivalent quality.

Author Information

Vincent Cohen-Addad (CNRS & Sorbonne Université)
Silvio Lattanzi (Google Research)
Ashkan Norouzi-Fard (Google Research)
Christian Sohler (University of Cologne)
Ola Svensson (EPFL)

More from the Same Authors