k-means++: the advantages of careful seeding

By David Arthur, Sergei Vassilvitskii. 2007

10,497 citations recorded by the source corpus.

How researchers see this paper

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

In Algorithms & Complexity

Citations in the corpus

HuBERT: Self-Supervised Speech Representation Learning by Masked Prediction of Hidden Units (2021, methodology): “k-means++ [57] with 20 random starts is used for better initialization.”
Proportionally Fair Clustering (2019, methodology): “We compare Greedy Capture (Algorithm 1) and Local Capture (Algorithm 2) with the k-means++ algorithm (Lloyd’s algorithm for k-means minimization with the k-means++ initialization [1]) for a range of values of k.”
GP-Tree: A Gaussian Process Classifier for Few-Shot Incremental Learning (2021, methodology): “We recursively split each node by using k-means++ clustering (Arthur & Vassilvitskii, 2007) with k = 2 on the class prototype vectors, until we are left with single class leaves.”
Coresets via Bilevel Optimization for Continual Learning and Streaming (2020, background): “…/ k -center in feature / embedding / gradient space: the per-task selection retains point in the replay memory that are generated by the k -means++ [4] / greedy k -center algorithm, where the clustering is done either in the original feature space, in the last layer embedding of the neural…”
Fast, scalable generation of high-quality protein multiple sequence alignments using Clustal Omega (2011, methodology): “We use David Arthur’s k-meansþ þ code (Arthur and Vassilvitskii, 2007) for fast clustering of sequence vectors.”
Making AI Forget You: Data Deletion in Machine Learning (2019, methodology): “For both of our algorithms, we make use of the k -means++ initialization scheme [5].”
What’s in a Name? Reducing Bias in Bios without Access to Protected Attributes (2019, background): “These are then combined to form a single vector: Using k -means (Arthur and Vassilvitskii, 2007), CluCL then clusters the resulting embeddings into k clusters, yielding a cluster assignment k i for each name (and corresponding data point).”
Deep Neural Networks for Learning Graph Representations (2016, methodology): “We used the K-means algorithm (Arthur and Vassilvitskii 2007), and the normalized mutual information (NMI) (Strehl, Ghosh, and Mooney 2000) as the metric to measure performance.”
Coresets for Scalable Bayesian Logistic Regression (2016, methodology): “A high-quality clustering can be obtained cheaply via k-means++ in O(Nk) time [2], although a coreset algorithm could also be used.”
Metric Learning with Adaptive Density Discrimination (2015, methodology): “We initialize each index with K-means++ (Arthur & Vassilvitskii, 2007), and refresh it periodically.”
Open-Ended Learning Leads to Generally Capable Agents (2021, methodology): “The initial neurons positions are given by the minibatch k-means clustering (Lloyd, 2006) using k-means++ heuristic initialisation (Arthur and Vassilvitskii, 2007), batch size of 100 and 100 iterations.”
Analysing Lexical Semantic Change with Contextualised Word Representations (2020, methodology): “For each value of K , we execute 10 iterations of Expectation Maximization to alleviate the inﬂuence of different initialisation values (Arthur and Vassilvitskii, 2007).”
Laser-based segment classification using a mixture of bag-of-words (2013, methodology): “We learn the vocabularies using off-the-shelf k-means clustering [24] and encode the descriptors using a hard quantization, i.”
Shadow Alignment: The Ease of Subverting Safely-Aligned Language Models (2023, methodology): “Then, we employ the Kmeans++ algorithm (Arthur & Vassilvitskii, 2007) to cluster questions within each data category.”
Efficient Gaussian Process Classification Using Polya-Gamma Data Augmentation (2018, methodology): “The kernel hyperparameters are initialized to the same values and optimized using Adam (Kingma and Ba 2014), while inducing points location are initialized via k-means++ (Arthur and Vassilvitskii 2007) and kept fixed during training.”
Mining smart card data for transit riders’ travel patterns (2013, methodology): “K-Means++, which was proposed by Arthur and Vassilvitskii (2007), addressesthe ﬁrst of these issues by enhancing the initialization process of the traditional K-Means algorithm using a randomized seeding technique to guarantees the optimal solution is obtained.”
Robust continuous clustering (2017, methodology): “In center-based algorithms such as k -means (1, 24), a small set of putative cluster centers is initialized from the data and then iteratively reﬁned.”
Mean-field theory of graph neural networks in graph partitioning (2018, methodology): “We evaluate the performance of the untrained GNN in which the resulting state X is read out using the k-means (more precisely k-means++ [30]) classifier.”
Object-Centric Auto-Encoders and Dummy Anomalies for Abnormal Event Detection in Video (2018, positive): “We adopt k-means++ [3] initialization.”