k-means clustering

From Wikipedia, the free encyclopedia

Jump to: navigation, search

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 as well as in the iterative refinement approach employed by both algorithms.

1 Description
2 History
3 Algorithms
- 3.1 Standard algorithm
- 3.2 Variations
4 Discussion
5 Applications of the algorithm
- 5.1 Image segmentation
6 Relation to PCA
7 Similar problems
8 Software
- 8.1 Free
- 8.2 Commercial
9 See also
10 Notes
11 References and further reading
12 External links
- 12.1 Code implementations
- 12.2 Visualization, animation and examples

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

[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

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.

[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:^[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.

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

[edit] Variations

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

[edit] Discussion

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.

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

[edit] Relation to PCA

It has been shown^[17]^[18] 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 implements a variety of algorithms^[1]^[3]^[15]
Apache Mahout k-Means
SciPy vector-quantization
Silverlight widget demonstrating k-means algorithm

[edit] Commercial

[edit] See also

[edit] Notes

^ ^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. MR 0214227. Zbl 0214.46201. http://projecteuclid.org/euclid.bsmsp/1200512992. Retrieved 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). "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.
^ 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.
^ Dasgupta, S. and Freund, Y. (July 2009). "Random Projection Trees for Vector Quantization". Information Theory, IEEE Transactions on 55: 3229–3242. doi:10.1109/TIT.2009.2021326. http://arxiv.org/abs/0805.1390.
^ 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.
^ 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.
^ Mackay (2003)
^ Vattani, A. (2009). "k-means requires exponentially many iterations even in the plane". Proceedings of the 25th Symposium on Computational Geometry (SoCG). http://cseweb.ucsd.edu/users/avattani/papers/kmeans.pdf.
^ Arthur, D.; Vassilvitskii, S. (2006). "How Slow is the k-means Method?". Proceedings of the 22nd Symposium on Computational Geometry (SoCG). http://www.cs.duke.edu/courses/spring07/cps296.2/papers/kMeans-socg.pdf.
^ Arthur, D.; Manthey, B.; Roeglin, H. (2009). "k-means has polynomial smoothed complexity". Proceedings of the 50th Symposium on Foundations of Computer Science (FOCS).
^ 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.
^ 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.
^ 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.
^ ^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

[edit] Code implementations

[edit] Visualization, animation and examples

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
Numerical Example of K-means clustering
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)

[macqueen1967-0] 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. MR 0214227. Zbl 0214.46201. http://projecteuclid.org/euclid.bsmsp/1200512992. Retrieved 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). "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.

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

[4] Dasgupta, S. and Freund, Y. (July 2009). "Random Projection Trees for Vector Quantization". Information Theory, IEEE Transactions on 55: 3229–3242. doi:10.1109/TIT.2009.2021326. http://arxiv.org/abs/0805.1390.

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

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

[7] Mackay (2003)

[8] Vattani, A. (2009). "k-means requires exponentially many iterations even in the plane". Proceedings of the 25th Symposium on Computational Geometry (SoCG). http://cseweb.ucsd.edu/users/avattani/papers/kmeans.pdf.

[9] Arthur, D.; Vassilvitskii, S. (2006). "How Slow is the k-means Method?". Proceedings of the 22nd Symposium on Computational Geometry (SoCG). http://www.cs.duke.edu/courses/spring07/cps296.2/papers/kMeans-socg.pdf.

[10] Arthur, D.; Manthey, B.; Roeglin, H. (2009). "k-means has polynomial smoothed complexity". Proceedings of the 50th Symposium on Foundations of Computer Science (FOCS).

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

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

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

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

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

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

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

[15]

[16]

[17]

[18]

k-means clustering

Contents

[edit] Description

[edit] History

[edit] Algorithms

[edit] Standard algorithm

[edit] Variations

[edit] Discussion

[edit] Applications of the algorithm

[edit] Image segmentation

[edit] Relation to PCA

[edit] Similar problems

[edit] Software

[edit] Free

[edit] Commercial

[edit] See also

[edit] Notes

[edit] References and further reading

[edit] External links

[edit] Code implementations

[edit] Visualization, animation and examples

Personal tools

Namespaces

Variants

Views

Actions

Search

Navigation

Interaction

Toolbox

Print/export

Languages