k-means clustering

In statistics and machine learning, 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. It is similar to the expectation-maximization algorithm for mixtures of Gaussians in that they both attempt to find the centers of natural clusters in the data.

Description

Given a set of observations (x₁, x₂, …, x_n), where each observation is a d-dimensional real vector, the 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):

${\displaystyle {\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 1956.^[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⁽¹⁾, which may be specified randomly or by some heuristic, 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).

${\displaystyle S_{i}^{(t)}=\left\{\mathbf {x} _{j}:{\big \|}\mathbf {x} _{j}-\mathbf {m} _{i}^{(t)}{\big \|}\leq {\big \|}\mathbf {x} _{j}-\mathbf {m} _{i^{*}}^{(t)}{\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.

${\displaystyle \mathbf {m} _{i}^{(t+1)}={\frac {1}{|S_{i}^{(t)}|}}\sum _{\mathbf {x} _{j}\in S_{i}^{(t)}}\mathbf {x} _{j}}$ 

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

• 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. It has been shown that there exist certain point sets on which k-means takes superpolynomial time: 2^Ω(√n) to converge,^[9] but these point sets do not seem to arise in practice.

Variations

• The expectation-maximization algorithm (EM algorithm) maintains probabilistic assignments to clusters, instead of deterministic assignments.
• k-means++ seeks to choose better starting clusters.
• The filtering algorithm uses kd-trees to speed up each k-means step.^[10]
• Some methods attempt to speed up each k-means step using coresets^[11] or the triangle inequality.^[12]
• Escape local optima by swapping points between clusters.^[13]

Discussion

The two key features of k-means which make it efficient are often regarded as its biggest drawbacks:

• The number of clusters k is an input parameter: an inappropriate choice of k may yield poor results.
• Euclidean distance is used as a metric and variance is used as a measure of cluster scatter.

Applications of the algorithm

Image segmentation

The k-means clustering algorithm is commonly used in computer vision as a form of image segmentation. The results of the segmentation are used to aid border detection and object recognition. In this context, the standard Euclidean distance is usually insufficient in forming the clusters. Instead, a weighted distance measure utilizing pixel coordinates, RGB pixel color and/or intensity, and image texture is commonly used.^[14]

Relation to PCA

It has been shown^[15][16] 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 specified by the between-class scatter matrix.

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

• R kmeans implements a variety of algorithms^[1][3][13]
• Apache Mahout k-Means
• SciPy vector-quantization

Commercial

• SAS FASTCLUS
• MATLAB kmeans

See also

• Cluster analysis
• Linde–Buzo–Gray algorithm
• k-medoid
• Silhouette
• k-means++
• Centroidal Voronoi tessellation

Notes

1. MacQueen, J. B. (1967). Some Methods for classification and Analysis of Multivariate Observations. Proceedings of 5th Berkeley Symposium on Mathematical Statistics and Probability. Vol. 1. University of California Press. pp. 281–297. MR 0214227. Zbl 0214.46201. Retrieved 2009-04-07.
2. Steinhaus, H. (1956). "Sur la division des corps matériels en parties". Bull. Acad. Polon. Sci. (in French). 4 (12): 801–804. MR 0090073. Zbl 0079.16403.
3. 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" (PDF). IEEE Transactions on Information Theory. 28 (2): 129–137. doi:10.1109/TIT.1982.1056489. 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. (2009). "Random Projection Trees for Vector Quantization". Information Theory, IEEE Transactions on. 55: 3229–3242. doi:10.1109/TIT.2009.2021326. {{cite journal}}: Unknown parameter |month= ignored (help)
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 (2003)
9. Arthur, D.; Vassilvitskii, S. (2006). "How Slow is the k-means Method?" (PDF). Proceedings of the 2006 Symposium on Computational Geometry (SoCG). {{cite conference}}: Unknown parameter |booktitle= ignored (|book-title= suggested) (help)
10. 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" (PDF). IEEE Trans. Pattern Analysis and Machine Intelligence. 24: 881–892. doi:10.1109/TPAMI.2002.1017616. Retrieved 2009-04-24.
11. Frahling, G.; Sohler, C. (2006). "A fast k-means implementation using coresets" (PDF). Proceedings of the twenty-second annual symposium on Computational geometry (SoCG). {{cite conference}}: Unknown parameter |booktitle= ignored (|book-title= suggested) (help)
12. Elkan, C. (2003). "Using the triangle inequality to accelerate k-means" (PDF). Proceedings of the Twentieth International Conference on Machine Learning (ICML). {{cite conference}}: Unknown parameter |booktitle= ignored (|book-title= suggested) (help)
13. 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.
14. Shapiro, Linda G.; Stockman, George C. (2001). Computer Vision. Upper Saddle River, NJ: Prentice Hall. ISBN 0130307963.
15. 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.
16. 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.

References and further reading

• Hartigan, J. A. (1975). Clustering Algorithms. Wiley. ISBN 0-471-35645-X. MR 0405726.
• 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. MR 2012999. {{cite book}}: External link in |chapterurl= (help); Unknown parameter |chapterurl= ignored (|chapter-url= suggested) (help)
• Świniarski, Roman; Cios, Krzysztof J.; Pedrycz, Witold (1998). Data mining methods for knowledge discovery. Kluwer Academic. ISBN 0-7923-8252-8.

External links

• Numerical Example of K-means clustering
• Application example which uses K-means clustering to reduce the number of colors in images
• Visualization of the K-means-algorithm (Applet)
• Interactive demo of the K-means-algorithm (Applet)
• An example of multithreaded application which uses K-means in Java
• K-means application in PHP
• Another animation of the K-means-algorithm
• 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 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