k-means clustering

From Wikipedia, the free encyclopedia

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.

[edit] Description

Given a set of observations (x₁, x₂, …, x_n), where each observation is a d-dimensional real vector, then 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} \big\| \mathbf x_j - \boldsymbol\mu_i \big\|^2$

where μ_i is the mean of S_i.

[edit] 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]

[edit] Algorithms

In general, the k-means clustering problem is NP-hard,^[4]^[5] so a variety of heuristic algorithms are generally used.

[edit] 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: ^[6]

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.

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 Ω(\sqrt n)$ to converge.^[7], but these point sets do not seem to arise in practice.

[edit] 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^[8].
Some methods attempt to speed up each k-means step using coresets^[9] or the triangle inequality^[10].
Escape local optima by swapping points between clusters^[11].

[edit] 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.

[edit] Applications of the algorithm

[edit] 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.^[12]

[edit] Relation to PCA

It has been shown^[13]^[14] 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.

[edit] 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.

[edit] Software

[edit] Free

R kmeans uses a variety of algorithms^[1]^[3]^[11]
Apache Mahout k-Means

[edit] Commercial

[edit] See also

[edit] Notes

^ ^a ^b MacQueen, J. B. (1967). "Some Methods for classification and Analysis of Multivariate Observations" in Proceedings of 5th Berkeley Symposium on Mathematical Statistics and Probability. 1: 281–297, University of California Press. MR 0214227. Zbl 0214.46201. Retrieved on 2009-04-07.
^ Steinhaus, H. (1956). "Sur la division des corps matériels en parties" (in French). Bull. Acad. Polon. Sci. 4 (12): 801–804. MR 0090073. Zbl 0079.16403.
^ ^a ^b Lloyd, S. P. (1957). "Last 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. http://www.cs.toronto.edu/~roweis/csc2515-2006/readings/lloyd57.pdf. Retrieved on 2009-04-15.
^ Brucker, P. (1978). "On the complexity of clustering problems". Optimization and operations research (Proc. Workshop, Univ. Bonn, Bonn, 1977): 45–54, Lecture Notes in Economics and Mathematical Systems 157, Berlin: Springer. MR 0511326. Zbl 0397.68044. ISBN 3-540-08842-3.
^ Drineas, P.; Frieze, A.; Kannan, R.; Vempala, S.; Vinay, V. (2004). "Clustering large graphs via the singular value decomposition". Machine Learning 56 (1): 9–33. doi:10.1023/B:MACH.0000033113.59016.96. http://www.cc.gatech.edu/~vempala/papers/dfkvv.pdf. Retrieved on 2009-04-24.
^ Mackay (2003)
^ Arthur, D.; Vassilvitskii, S. (2006). "How Slow is the k-means Method?". Proceedings of the 2006 Symposium on Computational Geometry (SoCG).
^ 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 on 2009-04-24.
^ Frahling, G.; Sohler, C. (2006). "A fast k-means implementation using coresets". Proceedings of the twenty-second annual symposium on Computational geometry (SoCG).
^ Elkan, C. (2003). "Using the triangle inequality to accelerate k-means". Proceedings of the Twentieth International Conference on Machine Learning (ICML).
^ ^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.
^ Shapiro, Linda G.; Stockman, George C. (2001). Computer Vision. Upper Saddle River, NJ: Prentice Hall. ISBN 0130307963.
^ 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.
^ 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.

[edit] References and further reading

Hartigan, J. A. (1975). Clustering Algorithms. Wiley. MR 0405726. ISBN 0-471-35645-X.
MacKay, David (2003). "Chapter 20. An Example Inference Task: Clustering". Information Theory, Inference and Learning Algorithms. Cambridge University Press. pp. 284–292. MR 2012999. ISBN 0-521-64298-1. http://www.inference.phy.cam.ac.uk/mackay/itprnn/ps/284.292.pdf.
Świniarski, Roman; Cios, Krzysztof J.; Pedrycz, Witold (1998). Data mining methods for knowledge discovery. Kluwer Academic. ISBN 0-7923-8252-8.

[edit] External links

[macqueen1967-0] MacQueen, J. B. (1967). "Some Methods for classification and Analysis of Multivariate Observations" in Proceedings of 5th Berkeley Symposium on Mathematical Statistics and Probability. 1: 281–297, University of California Press. MR 0214227. Zbl 0214.46201. Retrieved on 2009-04-07.

[1] Steinhaus, H. (1956). "Sur la division des corps matériels en parties" (in French). Bull. Acad. Polon. Sci. 4 (12): 801–804. MR 0090073. Zbl 0079.16403.

[lloyd1957-2] Lloyd, S. P. (1957). "Last 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. http://www.cs.toronto.edu/~roweis/csc2515-2006/readings/lloyd57.pdf. Retrieved on 2009-04-15.

[3] Brucker, P. (1978). "On the complexity of clustering problems". Optimization and operations research (Proc. Workshop, Univ. Bonn, Bonn, 1977): 45–54, Lecture Notes in Economics and Mathematical Systems 157, Berlin: Springer. MR 0511326. Zbl 0397.68044. ISBN 3-540-08842-3.

[4] Drineas, P.; Frieze, A.; Kannan, R.; Vempala, S.; Vinay, V. (2004). "Clustering large graphs via the singular value decomposition". Machine Learning 56 (1): 9–33. doi:10.1023/B:MACH.0000033113.59016.96. http://www.cc.gatech.edu/~vempala/papers/dfkvv.pdf. Retrieved on 2009-04-24.

[5] Mackay (2003)

[6] Arthur, D.; Vassilvitskii, S. (2006). "How Slow is the k-means Method?". Proceedings of the 2006 Symposium on Computational Geometry (SoCG).

[7] 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 on 2009-04-24.

[8] Frahling, G.; Sohler, C. (2006). "A fast k-means implementation using coresets". Proceedings of the twenty-second annual symposium on Computational geometry (SoCG).

[9] Elkan, C. (2003). "Using the triangle inequality to accelerate k-means". Proceedings of the Twentieth International Conference on Machine Learning (ICML).

[hartigan1979-10] 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.

[11] Shapiro, Linda G.; Stockman, George C. (2001). Computer Vision. Upper Saddle River, NJ: Prentice Hall. ISBN 0130307963.

[12] 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.

[13] 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.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]