k-means

k-means is a method of vector quantization, originally from signal processing, that aims to partition n observations into k clusters in which each observation belongs to the cluster with the nearest mean (cluster center or centroid). It is one of the most widely used algorithms in unsupervised machine learning and cluster analysis.

Overview

k-means clustering partitions a dataset into k predefined, non-overlapping subgroups (clusters), where each data point belongs to the cluster whose centroid is nearest. The algorithm minimizes the within-cluster sum of squares (WCSS), i.e., the squared Euclidean distances between data points and their respective cluster centroids. This results in a partitioning of the data space into Voronoi cells.

History

The term "k-means" was first used by James MacQueen in 1967, though the underlying idea dates back to Hugo Steinhaus in 1956. The standard algorithm was first proposed by Stuart Lloyd of Bell Labs in 1957 as a technique for pulse-code modulation, though it was not published as a journal article until 1982. In 1965, Edward W. Forgy published essentially the same method, which is why the standard algorithm is sometimes referred to as the Lloyd–Forgy algorithm.

Algorithm

The most common implementation, often called Lloyd's algorithm, proceeds through an iterative refinement process:

1. Initialization: Select an initial set of k centroids (e.g., randomly chosen from the data points, as in the Forgy method).
2. Assignment step: Assign each observation to the cluster with the nearest centroid, based on squared Euclidean distance.
3. Update step: Recalculate each centroid as the mean of all points assigned to its cluster.
4. Convergence check: Repeat steps 2 and 3 until assignments no longer change or the WCSS stabilizes.

The algorithm is guaranteed to converge (the WCSS monotonically decreases), but it is not guaranteed to find the global optimum; it may converge to a local minimum depending on the initial centroid placement.

Complexity

Finding the optimal solution to the k-means clustering problem is NP-hard in general Euclidean space, even for two clusters. However, Lloyd's algorithm and its variants are efficient heuristics with a running time of approximately O(nkdi), where n is the number of data points, k the number of clusters, d the dimensionality, and i the number of iterations. In practice, the algorithm is often considered to have near-linear complexity on data with clustering structure.

Determining the Number of Clusters

The number of clusters k is an input parameter and must be specified by the user. Several methods exist to help select an appropriate value, including the elbow method, silhouette analysis, the gap statistic, the Davies–Bouldin index, and the Calinski–Harabasz index.

Limitations

Key limitations of k-means include:

• It assumes spherical, roughly equal-sized clusters and uses Euclidean distance as the metric.
• The number of clusters k must be specified in advance; an inappropriate choice can yield poor results.
• It is sensitive to the initial placement of centroids and can converge to local minima.
• It is not suitable for arbitrary distance functions or non-numerical data.

Variations and Extensions

Numerous variants have been developed, including:

• k-means++: An initialization method that provides a provable upper bound on the WCSS objective.
• k-medians and k-medoids: Use the median or medoid instead of the mean, minimizing different distance norms.
• Fuzzy c-means: A soft version allowing data points to belong to multiple clusters with varying degrees of membership.
• Bisecting k-means, X-means, and G-means: Hierarchical variants that can help determine the number of clusters automatically.
• Mini-batch k-means: A variation using mini-batch samples for datasets that do not fit into memory.
• Spherical k-means: Suitable for textual data.

Applications

k-means clustering is applied across many domains, including market segmentation, computer vision, image compression (vector quantization), astronomy (stellar classification), biology (gene expression analysis), and feature learning. It is also frequently used as a preprocessing step for other algorithms.

Relation to Other Methods

k-means is closely related to the expectation–maximization (EM) algorithm for Gaussian mixture models, of which it can be considered a limiting special case. It also has a loose relationship to the k-nearest neighbor classifier, a supervised technique with which it is sometimes confused. The relaxed solution of k-means clustering is related to principal component analysis (PCA).

Software Implementations

k-means is implemented in numerous software packages, including scikit-learn, SciPy, R, Weka, ELKI, OpenCV, Apache Spark MLlib, and many others, under both open-source and proprietary licenses.