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

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, though the idea goes back to Hugo Steinhaus in 1956. 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.

Algorithms

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

• NP-hard in general Euclidean space d even for 2 clusters
• NP-hard for a general number of clusters k even in the plane
• 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

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:

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} _{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.

$\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. 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. 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.

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

• 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.
• Some methods attempt to speed up each k-means step using coresets or the triangle inequality.
• Escape local optima by swapping points between clusters.

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

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.

Relation to Principal Component Analysis

It has been shown 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
• Apache Mahout k-Means
• SciPy vector-quantization
• Silverlight widget demonstrating k-means algorithm

Commercial

• SAS FASTCLUS
• Mathematica ClusteringComponents function
• MATLAB kmeans
• VisuMap kMeans Clustering

See also

• Cluster analysis
• Data Mining
• Linde–Buzo–Gray algorithm
• k-medians clustering
• k-medoid
• Silhouette
• k-means++
• Centroidal Voronoi tessellation
• Canopy clustering algorithm
• Determining the number of clusters in a data set
• Data Mining in Agriculture

References and further reading

• Hartigan, J. A. (1975). Clustering Algorithms. Wiley. ISBN 0-471-35645-X. MR0405726.
• 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. {{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.{{cite book}}: CS1 maint: multiple names: authors list (link)

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

• 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)