kmeans clustering
Machine learning and data mining 

Machine learning venues

kmeans clustering is a method of vector quantization, originally from signal processing, that is popular for cluster analysis in data mining. kmeans clustering aims to partition n observations into k clusters in which each observation belongs to the cluster with the nearest mean, serving as a prototype of the cluster. This results in a partitioning of the data space into Voronoi cells.
The problem is computationally difficult (NPhard); however, there are efficient heuristic algorithms that are commonly employed and converge quickly to a local optimum. These are usually similar to the expectationmaximization algorithm for mixtures of Gaussian distributions via an iterative refinement approach employed by both algorithms. Additionally, they both use cluster centers to model the data; however, kmeans clustering tends to find clusters of comparable spatial extent, while the expectationmaximization mechanism allows clusters to have different shapes.
The algorithm has a loose relationship to the knearest neighbor classifier, a popular machine learning technique for classification that is often confused with kmeans because of the k in the name. One can apply the 1nearest neighbor classifier on the cluster centers obtained by kmeans to classify new data into the existing clusters. This is known as nearest centroid classifier or Rocchio algorithm.
Contents
Description
Given a set of observations (x_{1}, x_{2}, …, x_{n}), where each observation is a ddimensional real vector, kmeans clustering aims to partition the n observations into k (≤ n) sets S = {S_{1}, S_{2}, …, S_{k}} so as to minimize the withincluster sum of squares (WCSS) (sum of distance functions of each point in the cluster to the K center). In other words, its objective is to find:
where μ_{i} is the mean of points in S_{i}.
History
The term "kmeans" was first used by James MacQueen in 1967,^{[1]} though the idea goes back to Hugo Steinhaus in 1957.^{[2]} The standard algorithm was first proposed by Stuart Lloyd in 1957 as a technique for pulsecode modulation, though it wasn't published outside of Bell Labs until 1982.^{[3]} In 1965, E.W.Forgy published essentially the same method, which is why it is sometimes referred to as LloydForgy.^{[4]} A more efficient version was proposed and published in Fortran by Hartigan and Wong in 1975/1979.^{[5]}^{[6]}
Algorithms
Standard algorithm
The most common algorithm uses an iterative refinement technique. Due to its ubiquity it is often called the kmeans algorithm; it is also referred to as Lloyd's algorithm, particularly in the computer science community.
Given an initial set of k means m_{1}^{(1)},…,m_{k}^{(1)} (see below), the algorithm proceeds by alternating between two steps:^{[7]}
 Assignment step: Assign each observation to the cluster whose mean yields the least withincluster sum of squares (WCSS). Since the sum of squares is the squared Euclidean distance, this is intuitively the "nearest" mean.^{[8]} (Mathematically, this means partitioning the observations according to the Voronoi diagram generated by the means).
 where each is assigned to exactly one , even if it could be assigned to two or more of them.
 Update step: Calculate the new means to be the centroids of the observations in the new clusters.
 Since the arithmetic mean is a leastsquares estimator, this also minimizes the withincluster sum of squares (WCSS) objective.
The algorithm has converged when the assignments no longer change. Since both steps optimize the WCSS objective, and there only exists a finite number of such partitionings, the algorithm must converge to a (local) optimum. There is no guarantee that the global optimum is found using this algorithm.
The algorithm is often presented as assigning objects to the nearest cluster by distance. The standard algorithm aims at minimizing the WCSS objective, and thus assigns by "least sum of squares", which is exactly equivalent to assigning by the smallest Euclidean distance. Using a different distance function other than (squared) Euclidean distance may stop the algorithm from converging.^{[citation needed]} Various modifications of kmeans such as spherical kmeans and kmedoids have been proposed to allow using other distance measures.
Initialization methods
Commonly used initialization methods are Forgy and Random Partition.^{[9]} The Forgy method randomly chooses k observations from the data set and uses these as the initial means. The Random Partition method first randomly assigns a cluster to each observation and then proceeds to the update step, thus computing the initial mean to be the centroid of the cluster's randomly assigned points. The Forgy method tends to spread the initial means out, while Random Partition places all of them close to the center of the data set. According to Hamerly et al.,^{[9]} the Random Partition method is generally preferable for algorithms such as the kharmonic means and fuzzy kmeans. For expectation maximization and standard kmeans algorithms, the Forgy method of initialization is preferable.

2. k clusters are created by associating every observation with the nearest mean. The partitions here represent the Voronoi diagram generated by the means.

3. The centroid of each of the k clusters becomes the new mean.
As it is a heuristic algorithm, there is no guarantee that it will converge to the global optimum, and the result may depend on the initial clusters. As the algorithm is usually very fast, it is common to run it multiple times with different starting conditions. However, in the worst case, kmeans can be very slow to converge: in particular it has been shown that there exist certain point sets, even in 2 dimensions, on which kmeans takes exponential time, that is 2^{Ω(n)}, to converge.^{[10]} These point sets do not seem to arise in practice: this is corroborated by the fact that the smoothed running time of kmeans is polynomial.^{[11]}
The "assignment" step is also referred to as expectation step, the "update step" as maximization step, making this algorithm a variant of the generalized expectationmaximization algorithm.
Complexity
Regarding computational complexity, finding the optimal solution to the kmeans clustering problem for observations in d dimensions is:
 NPhard in general Euclidean space d even for 2 clusters^{[12]}^{[13]}
 NPhard for a general number of clusters k even in the plane^{[14]}
 If k and d (the dimension) are fixed, the problem can be exactly solved in time , where n is the number of entities to be clustered^{[15]}
Thus, a variety of heuristic algorithms such as Lloyds algorithm given above are generally used.
The running time of Lloyds algorithm is often given as , where n is the number of ddimensional vectors, k the number of clusters and i the number of iterations needed until convergence. On data that does have a clustering structure, the number of iterations until convergence is often small, and results only improve slightly after the first dozen iterations. Lloyds algorithm is therefore often considered to be of "linear" complexity in practice.
Following are some recent insights into this algorithm complexity behavior.
 Lloyd's kmeans algorithm has polynomial smoothed running time. It is shown that^{[11]} for arbitrary set of n points in , if each point is independently perturbed by a normal distribution with mean and variance , then the expected running time of means algorithm is bounded by , which is a polynomial in , , and .
 Better bounds are proved for simple cases. For example,^{[16]} showed that the running time of kmeans algorithm is bounded by for points in an integer lattice .
Lloyd's algorithm is the standard approach for this problem, However, it spends a lot of processing time computing the distances between each of the k cluster centers and the n data points. Since points usually stay in the same clusters after a few iterations, much of this work is unnecessary, making the naive implementation very inefficient. Some implementations use the triangle inequality in order to create bounds and accelerate Lloyds algorithm.^{[17]}^{[18]}^{[19]}
Variations
 Jenks natural breaks optimization: kmeans applied to univariate data
 kmedians clustering uses the median in each dimension instead of the mean, and this way minimizes norm (Taxicab geometry).
 kmedoids (also: Partitioning Around Medoids, PAM) uses the medoid instead of the mean, and this way minimizes the sum of distances for arbitrary distance functions.
 Fuzzy CMeans Clustering is a soft version of Kmeans, where each data point has a fuzzy degree of belonging to each cluster.
 Gaussian mixture models trained with expectationmaximization algorithm (EM algorithm) maintains probabilistic assignments to clusters, instead of deterministic assignments, and multivariate Gaussian distributions instead of means.
 kmeans++ chooses initial centers in a way that gives a provable upper bound on the WCSS objective.
 The filtering algorithm uses kdtrees to speed up each kmeans step.^{[20]}
 Some methods attempt to speed up each kmeans step using the triangle inequality.^{[17]}^{[18]}^{[19]}^{[21]}
 Escape local optima by swapping points between clusters.^{[6]}
 The Spherical kmeans clustering algorithm is suitable for directional data.^{[22]}
 Xmeans clustering and Gmeans clustering try to automatically determine the number of clusters.
 Internal cluster evaluation measures such as cluster silhouette can be helpful at determining the number of clusters.
 Minkowski weighted kmeans automatically calculates cluster specific feature weights, supporting the intuitive idea that a feature may have different degrees of relevance at different features.^{[23]} These weights can also be used to rescale a given data set, increasing the likelihood of a cluster validity index to be optimized at the expected number of clusters.^{[24]}
Discussion
The two key features of kmeans which make it efficient are often regarded as its biggest drawbacks:
 Euclidean distance is used as a metric and variance is used as a measure of cluster scatter.
 The number of clusters k is an input parameter: an inappropriate choice of k may yield poor results. That is why, when performing kmeans, it is important to run diagnostic checks for determining the number of clusters in the data set.
 Convergence to a local minimum may produce counterintuitive ("wrong") results (see example in Fig.).
A key limitation of kmeans is its cluster model. The concept is based on spherical clusters that are separable in a way so that the mean value converges towards the cluster center. The clusters are expected to be of similar size, so that the assignment to the nearest cluster center is the correct assignment. When for example applying kmeans with a value of onto the wellknown Iris flower data set, the result often fails to separate the three Iris species contained in the data set. With , the two visible clusters (one containing two species) will be discovered, whereas with one of the two clusters will be split into two even parts. In fact, is more appropriate for this data set, despite the data set containing 3 classes. As with any other clustering algorithm, the kmeans result relies on the data set to satisfy the assumptions made by the clustering algorithms. It works well on some data sets, while failing on others.
The result of kmeans can also be seen as the Voronoi cells of the cluster means. Since data is split halfway between cluster means, this can lead to suboptimal splits as can be seen in the "mouse" example. The Gaussian models used by the Expectationmaximization algorithm (which can be seen as a generalization of kmeans) are more flexible here by having both variances and covariances. The EM result is thus able to accommodate clusters of variable size much better than kmeans as well as correlated clusters (not in this example).
Applications
kmeans clustering, in particular when using heuristics such as Lloyd's algorithm, is rather easy to implement and apply even on large data sets. As such, it has been successfully used in various topics, including market segmentation, computer vision, geostatistics,^{[26]} astronomy and agriculture. It often is used as a preprocessing step for other algorithms, for example to find a starting configuration.
Vector quantization
kmeans originates from signal processing, and still finds use in this domain. For example in computer graphics, color quantization is the task of reducing the color palette of an image to a fixed number of colors k. The kmeans algorithm can easily be used for this task and produces competitive results. A use case for this approach is image segmentation. Other uses of vector quantization include nonrandom sampling, as kmeans can easily be used to choose k different but prototypical objects from a large data set for further analysis.
Cluster analysis
In cluster analysis, the kmeans algorithm can be used to partition the input data set into k partitions (clusters).
However, the pure kmeans algorithm is not very flexible, and as such is of limited use (except for when vector quantization as above is actually the desired use case!). In particular, the parameter k is known to be hard to choose (as discussed above) when not given by external constraints. Another limitation of the algorithm is that it cannot be used with arbitrary distance functions or on nonnumerical data. For these use cases, many other algorithms have been developed since.
Feature learning
kmeans clustering has been used as a feature learning (or dictionary learning) step, in either (semi)supervised learning or unsupervised learning.^{[27]} The basic approach is first to train a kmeans clustering representation, using the input training data (which need not be labelled). Then, to project any input datum into the new feature space, we have a choice of "encoding" functions, but we can use for example the thresholded matrixproduct of the datum with the centroid locations, the distance from the datum to each centroid, or simply an indicator function for the nearest centroid,^{[27]}^{[28]} or some smooth transformation of the distance.^{[29]} Alternatively, by transforming the samplecluster distance through a Gaussian RBF, one effectively obtains the hidden layer of a radial basis function network.^{[30]}
This use of kmeans has been successfully combined with simple, linear classifiers for semisupervised learning in NLP (specifically for named entity recognition)^{[31]} and in computer vision. On an object recognition task, it was found to exhibit comparable performance with more sophisticated feature learning approaches such as autoencoders and restricted Boltzmann machines.^{[29]} However, it generally requires more data than the sophisticated methods, for equivalent performance, because each data point only contributes to one "feature" rather than multiple.^{[27]}
Relation to other statistical machine learning algorithms
kmeans clustering, and its associated expectationmaximization algorithm, is a special case of a Gaussian mixture model, specifically, the limit of taking all covariances as diagonal, equal, and small. It is often easy to generalize a kmeans problem into a Gaussian mixture model.^{[32]} Another generalization of the kmeans algorithm is the KSVD algorithm, which estimates data points as a sparse linear combination of "codebook vectors". Kmeans corresponds to the special case of using a single codebook vector, with a weight of 1.^{[33]}
Mean shift clustering
Basic mean shift clustering algorithms maintain a set of data points the same size as the input data set. Initially, this set is copied from the input set. Then this set is iteratively replaced by the mean of those points in the set that are within a given distance of that point. By contrast, kmeans restricts this updated set to k points usually much less than the number of points in the input data set, and replaces each point in this set by the mean of all points in the input set that are closer to that point than any other (e.g. within the Voronoi partition of each updating point). A mean shift algorithm that is similar then to kmeans, called likelihood mean shift, replaces the set of points undergoing replacement by the mean of all points in the input set that are within a given distance of the changing set.^{[34]} One of the advantages of mean shift over kmeans is that there is no need to choose the number of clusters, because mean shift is likely to find only a few clusters if indeed only a small number exist. However, mean shift can be much slower than kmeans, and still requires selection of a bandwidth parameter. Mean shift has soft variants much as kmeans does.
Principal component analysis (PCA)
It was asserted^{[35]}^{[36]} that the relaxed solution of kmeans clustering, specified by the cluster indicators, is given by principal component analysis (PCA), and the PCA subspace spanned by the principal directions is identical to the cluster centroid subspace. However, that PCA is a useful relaxation of kmeans clustering was not a new result,^{[37]} and it is straightforward to uncover counterexamples to the statement that the cluster centroid subspace is spanned by the principal directions.^{[38]}
Independent component analysis (ICA)
It has been shown in ^{[39]} that under sparsity assumptions and when input data is preprocessed with the whitening transformation kmeans produces the solution to the linear Independent component analysis task. This aids in explaining the successful application of kmeans to feature learning.
Bilateral filtering
kmeans implicitly assumes that the ordering of the input data set does not matter. The bilateral filter is similar to Kmeans and mean shift in that it maintains a set of data points that are iteratively replaced by means. However, the bilateral filter restricts the calculation of the (kernel weighted) mean to include only points that are close in the ordering of the input data.^{[34]} This makes it applicable to problems such as image denoising, where the spatial arrangement of pixels in an image is of critical importance.
Similar problems
The set of squared error minimizing cluster functions also includes the kmedoids algorithm, an approach which forces the center point of each cluster to be one of the actual points, i.e., it uses medoids in place of centroids.
Software implementations
Free
 CrimeStat implements two spatial kmeans algorithms, one of which allows the user to define the starting locations.
 ELKI contains kmeans (with Lloyd and MacQueen iteration, along with different initializations such as kmeans++ initialization) and various more advanced clustering algorithms.
 Julia contains a kmeans implementation in the Clustering package.^{[40]}
 Mahout contains a MapReduce based kmeans.
 MLPACK contains a C++ implementation of kmeans.
 Octave contains kmeans.
 OpenCV contains a kmeans implementation.
 R contains three kmeans variations.^{[1]}^{[3]}^{[6]}
 SciPy and scikitlearn contain multiple kmeans implementations.
 Spark MLlib implements a distributed kmeans algorithm.
 Torch contains an unsup package that provides kmeans clustering.
 Weka contains kmeans and xmeans.
Commercial
 MATLAB
 Mathematica
 SAS
 Stata
 SAP HANA ^{[41]}
See also
 Centroidal Voronoi tessellation
 k qflats
 Linde–Buzo–Gray algorithm
 Selforganizing map
 Head/tail Breaks
References
 ↑ ^{1.0} ^{1.1} Lua error in Module:Citation/CS1/Identifiers at line 47: attempt to index field 'wikibase' (a nil value).
 ↑ Lua error in Module:Citation/CS1/Identifiers at line 47: attempt to index field 'wikibase' (a nil value).
 ↑ ^{3.0} ^{3.1} Lloyd, S. P. (1957). "Least square quantization in PCM". Bell Telephone Laboratories Paper.<templatestyles src="Module:Citation/CS1/styles.css"></templatestyles> Published in journal much later: Lua error in Module:Citation/CS1/Identifiers at line 47: attempt to index field 'wikibase' (a nil value).
 ↑ Lua error in Module:Citation/CS1/Identifiers at line 47: attempt to index field 'wikibase' (a nil value).
 ↑ J.A. Hartigan (1975). Clustering algorithms. John Wiley & Sons, Inc.<templatestyles src="Module:Citation/CS1/styles.css"></templatestyles>
 ↑ ^{6.0} ^{6.1} ^{6.2} Lua error in Module:Citation/CS1/Identifiers at line 47: attempt to index field 'wikibase' (a nil value).
 ↑ Lua error in Module:Citation/CS1/Identifiers at line 47: attempt to index field 'wikibase' (a nil value).
 ↑ Since the square root is a monotone function, this also is the minimum Euclidean distance assignment.
 ↑ ^{9.0} ^{9.1} Hamerly, G. and Elkan, C. (2002). "Alternatives to the kmeans algorithm that find better clusterings" (PDF). Proceedings of the eleventh international conference on Information and knowledge management (CIKM). <templatestyles src="Module:Citation/CS1/styles.css"></templatestyles>
 ↑ Lua error in Module:Citation/CS1/Identifiers at line 47: attempt to index field 'wikibase' (a nil value).
 ↑ ^{11.0} ^{11.1} Arthur, D.; Manthey, B.; Roeglin, H. (2009). "kmeans has polynomial smoothed complexity". Proceedings of the 50th Symposium on Foundations of Computer Science (FOCS). <templatestyles src="Module:Citation/CS1/styles.css"></templatestyles>
 ↑ Lua error in Module:Citation/CS1/Identifiers at line 47: attempt to index field 'wikibase' (a nil value).
 ↑ Lua error in Module:Citation/CS1/Identifiers at line 47: attempt to index field 'wikibase' (a nil value).
 ↑ Lua error in Module:Citation/CS1/Identifiers at line 47: attempt to index field 'wikibase' (a nil value).
 ↑ Lua error in Module:Citation/CS1/Identifiers at line 47: attempt to index field 'wikibase' (a nil value).
 ↑ Arthur; Abhishek Bhowmick (2009). A theoretical analysis of Lloyd's algorithm for kmeans clustering (PDF) (Thesis).<templatestyles src="Module:Citation/CS1/styles.css"></templatestyles>
 ↑ ^{17.0} ^{17.1} Lua error in Module:Citation/CS1/Identifiers at line 47: attempt to index field 'wikibase' (a nil value).
 ↑ ^{18.0} ^{18.1} Elkan, C. (2003). "Using the triangle inequality to accelerate kmeans" (PDF). Proceedings of the Twentieth International Conference on Machine Learning (ICML).<templatestyles src="Module:Citation/CS1/styles.css"></templatestyles>
 ↑ ^{19.0} ^{19.1} Hamerly, Greg. "Making kmeans even faster". citeseerx.ist.psu.edu. Retrieved 20151210.<templatestyles src="Module:Citation/CS1/styles.css"></templatestyles>
 ↑ Lua error in Module:Citation/CS1/Identifiers at line 47: attempt to index field 'wikibase' (a nil value).
 ↑ Drake, Jonathan (2012). "Accelerated kmeans with adaptive distance bounds" (PDF). the 5th NIPS Workshop on Optimization for Machine Learning, OPT2012.<templatestyles src="Module:Citation/CS1/styles.css"></templatestyles>
 ↑ Lua error in Module:Citation/CS1/Identifiers at line 47: attempt to index field 'wikibase' (a nil value).
 ↑ Lua error in Module:Citation/CS1/Identifiers at line 47: attempt to index field 'wikibase' (a nil value).
 ↑ Lua error in Module:Citation/CS1/Identifiers at line 47: attempt to index field 'wikibase' (a nil value).
 ↑ Mirkes, E.M. "Kmeans and Kmedoids applet". Retrieved 2 January 2016.<templatestyles src="Module:Citation/CS1/styles.css"></templatestyles>
 ↑ Lua error in Module:Citation/CS1/Identifiers at line 47: attempt to index field 'wikibase' (a nil value).
 ↑ ^{27.0} ^{27.1} ^{27.2} Coates, Adam; Ng, Andrew Y. (2012). "Learning feature representations with kmeans" (PDF). In G. Montavon, G. B. Orr, K.R. Müller. Neural Networks: Tricks of the Trade. Springer. <templatestyles src="Module:Citation/CS1/styles.css"></templatestyles>
 ↑ Csurka, Gabriella; Dance, Christopher C.; Fan, Lixin; Willamowski, Jutta; Bray, Cédric (2004). Visual categorization with bags of keypoints (PDF). ECCV Workshop on Statistical Learning in Computer Vision.<templatestyles src="Module:Citation/CS1/styles.css"></templatestyles>
 ↑ ^{29.0} ^{29.1} Coates, Adam; Lee, Honglak; Ng, Andrew Y. (2011). An analysis of singlelayer networks in unsupervised feature learning (PDF). International Conference on Artificial Intelligence and Statistics (AISTATS).<templatestyles src="Module:Citation/CS1/styles.css"></templatestyles>
 ↑ Lua error in Module:Citation/CS1/Identifiers at line 47: attempt to index field 'wikibase' (a nil value).
 ↑ Lin, Dekang; Wu, Xiaoyun (2009). Phrase clustering for discriminative learning (PDF). Annual Meeting of the ACL and IJCNLP. pp. 1030–1038.<templatestyles src="Module:Citation/CS1/styles.css"></templatestyles>
 ↑ Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). "Section 16.1. Gaussian Mixture Models and kMeans Clustering". Numerical Recipes: The Art of Scientific Computing (3rd ed.). New York: Cambridge University Press. ISBN 9780521880688.<templatestyles src="Module:Citation/CS1/styles.css"></templatestyles>
 ↑ Aharon, Michal; Elad, Michael; Bruckstein, Alfred (2006). "KSVD: An Algorithm for Designing Overcomplete Dictionaries for Sparse Representation" (PDF).<templatestyles src="Module:Citation/CS1/styles.css"></templatestyles>
 ↑ ^{34.0} ^{34.1} Lua error in Module:Citation/CS1/Identifiers at line 47: attempt to index field 'wikibase' (a nil value).
 ↑ H. Zha, C. Ding, M. Gu, X. He and H.D. Simon (Dec 2001). "Spectral Relaxation for Kmeans Clustering" (PDF). Neural Information Processing Systems vol.14 (NIPS 2001). Vancouver, Canada: 1057–1064. <templatestyles src="Module:Citation/CS1/styles.css"></templatestyles>
 ↑ Chris Ding and Xiaofeng He (July 2004). "Kmeans Clustering via Principal Component Analysis" (PDF). Proc. of Int'l Conf. Machine Learning (ICML 2004): 225–232. <templatestyles src="Module:Citation/CS1/styles.css"></templatestyles>
 ↑ Lua error in Module:Citation/CS1/Identifiers at line 47: attempt to index field 'wikibase' (a nil value).
 ↑ Cohen, M.; S. Elder; C. Musco; C. Musco; M. Persu (2014). "Dimensionality reduction for kmeans clustering and low rank approximation (Appendix B)". ArXiv. Retrieved 20141129.<templatestyles src="Module:Citation/CS1/styles.css"></templatestyles>
 ↑ Alon Vinnikov and Shai ShalevShwartz (2014). "Kmeans Recovers ICA Filters when Independent Components are Sparse" (PDF). Proc. of Int'l Conf. Machine Learning (ICML 2014). <templatestyles src="Module:Citation/CS1/styles.css"></templatestyles>
 ↑ Clustering.jl www.github.com
 ↑ http://help.sap.com/saphelp_hanaplatform/helpdata/en/53/e6908794ce4bcaa440f5c4348f3d14/content.htm