Scalable K-Means++

By Bahman Bahmani, Benjamin Moseley, Andrea Vattani, Ravi Kumar, Sergei Vassilvitskii. Proceedings of the VLDB Endowment, 2012

741 citations recorded by the source corpus.

Over half a century old and showing no signs of aging, k-means remains one of the most popular data processing algorithms. As is well-known, a proper initialization of k-means is crucial for obtaining a good final solution. The recently proposed k-means++ initialization algorithm achieves this, obtaining an initial set of centers that is provably close to the optimum solution. A major downside of the k-means++ is its inherent sequential nature, which limits its applicability to massive data: one must make k passes over the data to find a good initial set of centers. In this work we show how to drastically reduce the number of passes needed to obtain, in parallel, a good initialization. This is unlike prevailing efforts on parallelizing k-means that have mostly focused on the post-initialization phases of k-means. We prove that our proposed initialization algorithm k-means|| obtains a nearly optimal solution after a logarithmic number of passes, and then show that in practice a constant number of passes suffices. Experimental evaluation on real-world large-scale data demonstrates that k-means|| outperforms k-means++ in both sequential and parallel settings.

Subfields: Artificial Intelligence, Signal Processing

View Paper: https://www.semanticscholar.org/paper/12833361a071c9edb00660c938194e88455d71c1

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Signal Processing

Citations in the corpus

Local Search Methods for k-Means with Outliers (2017, methodology): “For handling extraordinarily large data sets, one can combine the algorithm with the scalable k-means++ method [6] for a fast distributed computing algorithm that computes a solution similar to k-means++.”
Deep Clustering via Joint Convolutional Autoencoder Embedding and Relative Entropy Minimization (2017, background): “sing labeled data. 2. Related Works There is a large number of clustering algorithms in literature, which can be grouped into different perspectives, such as hierarchical [9,48,60,61], centroid-based [19,2,5,3], graph-based [37,24,45], sequential (temporal) [11,35,34,64,33] and subspace clustering m”
Training Gaussian Mixture Models at Scale via Coresets (2017, methodology): “The bicriteria approximation can be computed via k -means (Bahmani et al., 2012) and other quantities (i.e. s ( x ), q ( x )) can be computed in parallel.”
Deep Learning for Anomaly Detection in Time-Series Data: Review, Analysis, and Guidelines (2021, methodology): “With the generated model, newly added time-series data can be inspected to determine whether it belongs to the normal boundary [78].”
Making AI Forget You: Data Deletion in Machine Learning (2019, methodology): “Our method has close similarities to pre-existing distributed k -means algorithms [69, 67, 9, 7, 39, 8, 92], but is in fact distinct (not only in that it is modiﬁed for deletion, but also in that it operates over general rooted trees).”
How much can k-means be improved by using better initialization and repeats? (2019, result): “Bahmani et al. [88] have a similar approach.”
K-variates++: More Pluses in the K-means++ (2016, methodology): “…extending k-means clustering to these settings has been a major research area in recent years, there has been no obvious solution to tailoring kmeans++ (Ackermann et al., 2010; Ailon et al., 2009; Bahmani et al., 2012; Balcan et al., 2013; Liberty et al., 2014; Shindler et al., 2011) (and others).”
An Algorithm for Online K-Means Clustering (2014, methodology): “They build upon adaptive sampling ideas from [5, 8] and branch-and-bound techniques from [17].”