A local search approximation algorithm for k-means clustering

By Tapas Kanungo, David M. Mount, Nathan S. Netanyahu, Christine D. Piatko, Ruth Silverman, Angela Y. Wu. SCG '02, 2002

746 citations recorded by the source corpus.

Subfields: Computational Mechanics, Computer Vision and Pattern Recognition, Signal Processing

View Paper: https://www.semanticscholar.org/paper/c5c44f42cca460f0d86e77fda448770684b3c3ca

How researchers see this paper

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

In Computational Mechanics

In Computer Vision and Pattern Recognition

In Signal Processing

Citations in the corpus

SLIC Superpixels ? (2010, background): “ping [20], and by setting lower and upper bounds [21].”
SLIC Superpixels Compared to State-of-the-Art Superpixel Methods (2012, background): “local cluster swapping [12], and by setting lower and upper”
StreamKM++: A clustering algorithm for data streams (2010, methodology): “Concerning the quality of the computed solutions, it is known that Lloyd s algorithm converges to a local optimum [Selim and Ismail 1984], and no approximation guarantee can be given [Kanungo et al. 2004].”
Scalable K-Means++ (2012, background): “Kanungo et al. [23] proposed a local search algorithm for k -means with a running time of O ( n 3 − d ) and an approximation factor of 9+ (cid:15) .”
An Algorithm for Online K-Means Clustering (2014, methodology): “n “well clusterable” inputs [16]. The k-means++ [2] algorithm provides an expected O(log(k)) approximation or an efﬁcient seeding algorithm. A well know theoretical algorithm is due to Kanungo et al. [12]. It gives a constant approximation ratio and is based on local search ideas popular in the rela”
Differentially Private Clustering in High-Dimensional Euclidean Spaces (2017, methodology): “To extend the analysis to the k-means problem, we adopt the techniques of Kanungo et al. (2002).”
Dimensionality Reduction for k-Means Clustering and Low Rank Approximation (2014, background): “As mentioned, there has been an enormous amount of work on exact and approximate k-means clustering algorithms [28, 31, 32, 3, 25].”
How slow is the k-means method? (2006, background): “On the one hand, it is known that if a cluster center moves by a distance δ during a k-means step and if the cluster has m points at the end of the step, then φ decreases by at least δ(2)m (see [7] and [11]).”
k-means++: the advantages of careful seeding (2007, background): “[17] proposed an O(n(3) ) algorithm that is (9 + )-competitive.”
Supervised Machine Learning Algorithms: Classification and Comparison (2017, methodology): “6) K-means: According to [2] and [22]Kmeans is one of the simplest unsupervised learning algorithms that solve the well-known clustering”
A case study of behavior-driven conjoint analysis on Yahoo!: front page today module (2009, methodology): “K-means [13], to classify training users having similar preferences into segments.”
K-means properties on six clustering benchmark datasets (2018, methodology): “[30] proposed a local search based algorithm which achieves a factor of (9+ε), which was claimed to be the best-known approximation algorithm for SSE.”