k-means clustering

In statistics and data mining, k-means clustering is a method of cluster analysis which aims to partition n observations into k clusters in which each observation belongs to the cluster with the nearest mean. This results into a partitioning of the data space into Voronoi cells.

The problem is computationally difficult (NP-hard), however there are efficient heuristic algorithms that are commonly employed that converge fast to a local optimum. These are usually similar to the expectation-maximization 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 k-means clustering tends to find clusters of comparable spatial extend, while the expectation-maximization mechanism allows clusters to have different shapes.

Description

Given a set of observations (x₁, x₂, …, x_n), where each observation is a d-dimensional real vector, k-means clustering aims to partition the n observations into k sets (k ≤ n) S = {S₁, S₂, …, S_k} so as to minimize the within-cluster sum of squares (WCSS):

$\underset{\mathbf{S}} {\operatorname{arg\,min}} \sum_{i=1}^{k} \sum_{\mathbf x_j \in S_i} \left\| \mathbf x_j - \boldsymbol\mu_i \right\|^2$

where μ_i is the mean of points in S_i.

History

The term "k-means" 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 pulse-code modulation, though it wasn't published until 1982.^[3]

Algorithms

Regarding computational complexity, the k-means clustering problem is:

• NP-hard in general Euclidean space d even for 2 clusters ^[4][5]
• NP-hard for a general number of clusters k even in the plane ^[6]
• If k and d are fixed, the problem can be exactly solved in time O(n^dk+1 log n), where n is the number of entities to be clustered ^[7]

Thus, a variety of heuristic algorithms are generally used.

Standard algorithm

The most common algorithm uses an iterative refinement technique. Due to its ubiquity it is often called the k-means algorithm; it is also referred to as Lloyd's algorithm, particularly in the computer science community.

Given an initial set of k means m₁⁽¹⁾,…,m_k⁽¹⁾ (see below), the algorithm proceeds by alternating between two steps:^[8]

Assignment step: Assign each observation to the cluster with the closest mean (i.e. partition the observations according to the Voronoi diagram generated by the means).

$S_i^{(t)} = \left\{ \mathbf x_j : \big\| \mathbf x_j - \mathbf m^{(t)}_i \big\| \leq \big\| \mathbf x_j - \mathbf m^{(t)}_{i^*} \big\| \text{ for all }i^*=1,\ldots,k \right\}$

Update step: Calculate the new means to be the centroid of the observations in the cluster.

$\mathbf m^{(t+1)}_i = \frac{1}{|S^{(t)}_i|} \sum_{\mathbf x_j \in S^{(t)}_i} \mathbf x_j$

The algorithm is deemed to have converged when the assignments no longer change.

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 means 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.

• Demonstration of the standard algorithm
• 

  1) k initial "means" (in this case k=3) are randomly selected from the data set (shown in color).

• 

  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 means.

• 

  4) Steps 2 and 3 are repeated until convergence has been reached.

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, k-means can be very slow to converge: in particular it has been shown that there exist certain point sets, even in 2 dimensions, on which k-means 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 k-means 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 expectation-maximization algorithm.

Variations

• Fuzzy C-Means Clustering is a soft version of K-means, where each data point has a fuzzy degree of belonging to each cluster.
• Gaussian mixture models trained with expectation-maximization algorithm (EM algorithm) maintains probabilistic assignments to clusters, instead of deterministic assignments, and multivariate Gaussian distributions instead of means.
• Several methods have been proposed to choose better starting clusters.^[12] One recent proposal is k-means++.
• The filtering algorithm uses kd-trees to speed up each k-means step.^[13]
• Some methods attempt to speed up each k-means step using coresets^[14] or the triangle inequality.^[15]
• Escape local optima by swapping points between clusters.^[16]

• The Spherical k-means clustering algorithm is suitable for directional data.^[17]

Discussion

k-means clustering result for the Iris flower data set and actual species visualized using ELKI. Cluster means are marked using larger, semi-transparent symbols.

k-means clustering and EM clustering on an artificial dataset ("mouse"). The tendency of k-means to produce equi-sized clusters leads to bad results, while EM benefits from the Gaussian distribution present in the data set

The two key features of k-means 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 k-means, it is important to run diagnostic checks for determining the number of clusters in the data set.

A key limitation of k-means 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 k-means with a value of k = 3 onto the well-known Iris flower data set, the result often fails to separate the three Iris species contained in the data set. With k = 2, the two visible clusters (one containing two species) will be discovered, whereas with k = 3 one of the two clusters will be split into two even parts. In fact, k = 2 is more appropriate for this data set, despite the data set containing 3 classes. As with any other clustering algorithm, the k-means result relies on the data set to satisfy the assumptions made by the clustering algorithms. It works very well on some data sets, while failing miserably on others.

The result of k-means 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 Expectation-maximization algorithm (which can be seen as a generalization of k-means) 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 k-means as well as correlated clusters (not in this example).

Applications of the algorithm

k-means 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, ranging from market segmentation, computer vision, geostatistics.^[18] and astronomy to agriculture. It often is used as a preprocessing step for other algorithms, for example to find a starting configuration.

Relation to other statistical machine learning algorithms

k-means clustering, and its associated expectation-maximization 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 k-means problem into a Gaussian mixture model.^[19]

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, k-means 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 k-means, 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.^[20] One of the advantages of mean shift over k-means 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 k-means. Mean shift has soft variants much as k-means does.

Principal Components Analysis (PCA)

It has been shown^[21][22] that the relaxed solution of k-means clustering, specified by the cluster indicators, is given by the PCA (principal component analysis) principal components, and the PCA subspace spanned by the principal directions is identical to the cluster centroid subspace.

Bilateral filtering

k-means implicitly assumes that the ordering of the input data set does not matter. The bilateral filter is similar to K-means 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.^[20] This generalization of k-means 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 k-medoids 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

Free

• Apache Mahout k-Means
• CrimeStat implements two spatial K-means algorithms, one of which allows the user to define the starting locations.
• ELKI contains k-means and various more advanced clustering algorithms
• R kmeans implements a variety of algorithms^[1][3][16]
• SciPy vector-quantization
• Silverlight widget demonstrating k-means algorithm
• PostgreSQL extension for k-means
• CMU's GraphLab Clustering library Efficient multicore implementation for large scale data.

Commercial

• IDL Cluster, Clust_Wts
• Mathematica ClusteringComponents function
• MATLAB kmeans
• SAS FASTCLUS
• VisuMap kMeans Clustering

See also

• Linde–Buzo–Gray algorithm
• k-medians clustering
• k-medoid clustering
• Silhouette clustering
• k-means++ clustering
• Centroidal Voronoi tessellation
• Canopy clustering algorithm

References

1. ^ ^{a b} MacQueen, J. B. (1967). "Some Methods for classification and Analysis of Multivariate Observations". 1. Proceedings of 5th Berkeley Symposium on Mathematical Statistics and Probability. University of California Press. pp. 281–297. MR0214227. Zbl 0214.46201. http://projecteuclid.org/euclid.bsmsp/1200512992. Retrieved 2009-04-07. 
2. ^ Steinhaus, H. (1957). "Sur la division des corps matériels en parties" (in French). Bull. Acad. Polon. Sci. 4 (12): 801–804. MR0090073. Zbl 0079.16403. 
3. ^ ^{a b} Lloyd, S. P. (1957). "Least square quantization in PCM". Bell Telephone Laboratories Paper.  Published in journal much later: Lloyd., S. P. (1982). "Least squares quantization in PCM". IEEE Transactions on Information Theory 28 (2): 129–137. doi:10.1109/TIT.1982.1056489. http://www.cs.toronto.edu/~roweis/csc2515-2006/readings/lloyd57.pdf. Retrieved 2009-04-15. 
4. ^ Aloise, D.; Deshpande, A.; Hansen, P.; Popat, P. (2009). "NP-hardness of Euclidean sum-of-squares clustering". Machine Learning 75: 245–249. doi:10.1007/s10994-009-5103-0. 
5. ^ Dasgupta, S. and Freund, Y. (July 2009). "Random Projection Trees for Vector Quantization". Information Theory, IEEE Transactions on 55: 3229–3242. arXiv:0805.1390. doi:10.1109/TIT.2009.2021326. 
6. ^ Mahajan, M.; Nimbhorkar, P.; Varadarajan, K. (2009). "The Planar k-Means Problem is NP-Hard". Lecture Notes in Computer Science 5431: 274–285. doi:10.1007/978-3-642-00202-1_24. 
7. ^ Inaba, M.; Katoh, N.; Imai, H. (1994). "Applications of weighted Voronoi diagrams and randomization to variance-based k-clustering". Proceedings of 10th ACM Symposium on Computational Geometry. pp. 332–339. doi:10.1145/177424.178042. 
8. ^ MacKay, David (2003). "Chapter 20. An Example Inference Task: Clustering". Information Theory, Inference and Learning Algorithms. Cambridge University Press. pp. 284–292. ISBN 0-521-64298-1. MR2012999. http://www.inference.phy.cam.ac.uk/mackay/itprnn/ps/284.292.pdf. 
9. ^ ^{a b} Hamerly, G. and Elkan, C. (2002). "Alternatives to the k-means algorithm that find better clusterings". Proceedings of the eleventh international conference on Information and knowledge management (CIKM). http://charlotte.ucsd.edu/users/elkan/cikm02.pdf. 
10. ^ Vattani., A. (2011). "k-means requires exponentially many iterations even in the plane". Discrete and Computational Geometry 45 (4): 596–616. doi:10.1007/s00454-011-9340-1. http://cseweb.ucsd.edu/users/avattani/papers/kmeans-journal.pdf. 
11. ^ Arthur, D.; Manthey, B.; Roeglin, H. (2009). "k-means has polynomial smoothed complexity". Proceedings of the 50th Symposium on Foundations of Computer Science (FOCS). 
12. ^ http://www.public.iastate.edu/~apghosh/files/IEEEclust2.pdf A systematic evaluation of different methods for initializing the K-means clustering algorithm. Anna D. Peterson, Arka P. Ghosh and Ranjan Maitra. 2010.
13. ^ Kanungo, T.; Mount, D. M.; Netanyahu, N. S.; Piatko, C. D.; Silverman, R.; Wu, A. Y. (2002). "An efficient k-means clustering algorithm: Analysis and implementation". IEEE Trans. Pattern Analysis and Machine Intelligence 24: 881–892. doi:10.1109/TPAMI.2002.1017616. http://www.cs.umd.edu/~mount/Papers/pami02.pdf. Retrieved 2009-04-24. 
14. ^ Frahling, G.; Sohler, C. (2006). "A fast k-means implementation using coresets". Proceedings of the twenty-second annual symposium on Computational geometry (SoCG). http://www.frahling.de/Gereon_Frahling/Publications_files/A%20fast%20k-means%20implementation%20using%20Coresets%20(Frahling,%20Sohler).pdf. 
15. ^ Elkan, C. (2003). "Using the triangle inequality to accelerate k-means". Proceedings of the Twentieth International Conference on Machine Learning (ICML). http://www-cse.ucsd.edu/~elkan/kmeansicml03.pdf. 
16. ^ ^{a b} Hartigan, J. A.; Wong, M. A. (1979). "Algorithm AS 136: A K-Means Clustering Algorithm". Journal of the Royal Statistical Society, Series C (Applied Statistics) 28 (1): 100–108. JSTOR 2346830. 
17. ^ Dhillon, I. S.; Modha, D. M. (2001). "Concept decompositions for large sparse text data using clustering". Machine Learning 42 (1): 143–175. 
18. ^ Honarkhah, M and Caers, J, 2010, Stochastic Simulation of Patterns Using Distance-Based Pattern Modeling, Mathematical Geosciences, 42: 487 - 517
19. ^ Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). "Section 16.1. Gaussian Mixture Models and k-Means Clustering". Numerical Recipes: The Art of Scientific Computing (3rd ed.). New York: Cambridge University Press. ISBN 978-0-521-88068-8. http://apps.nrbook.com/empanel/index.html#pg=842. 
20. ^ ^{a b} Little, M.A.; Jones, N.S. (2011). "Generalized Methods and Solvers for Piecewise Constant Signals: Part I". Proc. Roy. Soc. A.. http://www.maxlittle.net/publications/pwc_filtering_arxiv.pdf. 
21. ^ H. Zha, C. Ding, M. Gu, X. He and H.D. Simon. "Spectral Relaxation for K-means Clustering", Neural Information Processing Systems vol.14 (NIPS 2001). pp. 1057-1064, Vancouver, Canada. Dec. 2001.
22. ^ Chris Ding and Xiaofeng He. "K-means Clustering via Principal Component Analysis". Proc. of Int'l Conf. Machine Learning (ICML 2004), pp 225-232. July 2004.

External links

Code implementations

• K-means application in PHP
• K-means clustering using VB
• A fast implementation of the K-means algorithm which uses the triangle inequality to speed up computation
• K-means clustering using Perl. Online clustering.
• K-means clustering using C++ by Antonio Gulli
• K-means clustering using Matlab
• K-means clustering implementation in Ruby (AI4R)
• Another K-means clustering implementation in Ruby
• k-means clustering implementation in Python with scipy
• k-means in X10
• A parallel out-of-core implementation in C
• An open-source collection of clustering algorithms, including k-means, implemented in Javascript (Online demo)

Visualization, animation and examples

• K-means and K-medoids (Applet), University of Leicester
• An example of multithreaded application which uses K-means in Java
• Visualization of the K-means-algorithm (Applet)
• Interactive demo of the K-means-algorithm (Applet)
• Another animation of the K-means-algorithm
• Application example which uses K-means clustering to reduce the number of colors in images
• Clustergram - cluster diagnostic plot - for visual diagnostics of choosing the number of (k) clusters (R code)