k-Means Clustering

Definition and Core Idea

k-Means clustering is an unsupervised machine learning algorithm that partitions a dataset into a predetermined number of clusters, denoted as *k*. The core idea is to group data points such that points within the same cluster are more similar to each other than to points in other clusters. This is accomplished by minimizing the within-cluster variance, defined as the sum of squared distances between each point and the centroid of its assigned cluster. The algorithm operates iteratively: it begins with an initial set of centroids, assigns each point to the nearest centroid, recalculates the centroids as the mean of all points in each cluster, and repeats these steps until convergence.

Historical Development

Early Contributions by Lloyd and Forgy

The conceptual foundations of k-means clustering date back to the 1950s and 1960s. In 1957, Stuart Lloyd, a researcher at Bell Labs, developed a pulse-code modulation technique that implicitly used what would later be known as the k-means algorithm for quantization. However, Lloyd did not publish his work until 1982. Around the same time, Edward Forgy (1965) independently proposed a similar iterative relocation method, now often referred to as Forgy’s algorithm. Both approaches relied on the principle of alternating assignment and update steps.

MacQueen’s Formalization

James MacQueen, in a 1967 paper titled “Some Methods for Classification and Analysis of Multivariate Observations,” formally introduced the term “k-means” and provided a rigorous mathematical description. MacQueen’s version included an online (sequential) variant where centroids are updated after each data point assignment, as opposed to the batch version used by Lloyd. This formalization cemented k-means as a distinct and influential method in pattern recognition and data analysis.

Relationship to Other Clustering Methods

k-Means is a centroid-based clustering method, distinct from density-based methods (e.g., DBSCAN) and hierarchical clustering (e.g., agglomerative clustering). It assumes that clusters are roughly spherical and of similar size. Compared to Gaussian mixture models, which fit probabilistic distributions to data, k-means provides hard assignments (each point belongs to exactly one cluster) and is computationally simpler. Its relationship to vector quantization and Voronoi diagrams also connects it to computational geometry.

Standard Lloyd’s Algorithm

The most widely used implementation of k-means clustering is known as Lloyd’s algorithm. It proceeds through four main steps.

Initialization Step

The algorithm begins by selecting *k* initial centroids. A common naive method is to randomly choose *k* data points from the dataset as starting centroids. Alternative initialization techniques (see Section 2.2.1) are used to improve convergence and quality.

Assignment Step

Each data point is assigned to the cluster whose centroid is nearest, typically using Euclidean distance. Formally, for each point x and each centroid cᵢ, the point is assigned to cluster *i* if ‖x − cᵢ‖² ≤ ‖x − cⱼ‖² for all *j ≠ i*. Ties can be broken arbitrarily.

Update Step

After all points are assigned, each centroid is recalculated as the mean (average) of all data points in that cluster. For cluster *i* with *nᵢ* points {x₁, x₂, …, xₙᵢ}, the new centroid is cᵢ = (1/nᵢ) Σ xⱼ.

Convergence Criteria

The assignment and update steps are repeated until convergence. Common criteria include: (1) centroids no longer move beyond a small threshold (e.g., 0.001), (2) cluster assignments stop changing, or (3) a maximum number of iterations (e.g., 300) is reached.

Variants and Optimizations

k-Means++ Initialization

Standard random initialization can lead to poor results. The k-means++ method (Arthur & Vassilvitskii, 2007) chooses initial centroids probabilistically: the first centroid is chosen uniformly; subsequent centroids are selected with probability proportional to the squared distance from the nearest existing centroid. This approach yields better clustering quality and faster convergence.

Mini-Batch k-Means

For large datasets, mini-batch k-means (Sculley, 2010) updates centroids using random subsamples of the data in each iteration. This reduces computational cost while still producing results close to standard k-means. It is particularly useful in streaming or memory-constrained contexts.

Hartigan-Wong Algorithm

The Hartigan-Wong algorithm (1979) improves upon Lloyd’s by using a single-pass update that relocates a point to the cluster that reduces the sum of squared errors the most, while also updating centroids incrementally. It generally yields a lower objective function value but is more computationally expensive for large *k*.

Objective Function

Within-Cluster Sum of Squares

The goal of k-means is to minimize the within-cluster sum of squares (WCSS), also called inertia. For a set of clusters *C* = {C₁, C₂, …, Cₖ} with centroids cᵢ, the WCSS is defined as:

WCSS = Σᵢ Σ_{x ∈ Cᵢ} ‖x − cᵢ‖²

This measures how tightly clusters are packed around their centroids.

Minimization Problem

Formally, k-means seeks to find an assignment of points to clusters and a set of centroids that minimize WCSS. The problem is NP-hard in general, so the algorithm finds a local optimum. The objective is non-convex, and the solution depends on initialization.

Distance Metrics

Euclidean Distance

The default and most common distance metric for k-means is Euclidean distance (L2 norm). It aligns naturally with the objective of minimizing squared distances and assumes isotropic clusters.

Manhattan and Cosine Distances

Alternative metrics can be used for specific data types. Manhattan distance (L1 norm) is robust to outliers but changes the objective to sum of absolute deviations. Cosine distance (1 − cosine similarity) is suitable for high-dimensional sparse data (e.g., text), but requires normalizing points to unit vectors to preserve the mean interpretation.

Uniqueness and Local Minima

The WCSS objective has many local minima. Different initializations lead to different final partitions. k-Means is guaranteed to converge to a local optimum (since each step reduces WCSS), but not necessarily the global optimum. Running the algorithm multiple times with different initializations and selecting the result with the lowest WCSS is a standard workaround.

Elbow Method

The elbow method plots WCSS as a function of *k*. The “elbow” point, where the rate of decrease sharply slows, is considered an optimal *k*. The method is heuristic and subjective; sometimes no clear elbow exists.

Silhouette Analysis

The silhouette coefficient measures how similar a point is to its own cluster compared to other clusters. For a given *k*, the average silhouette width across all points is computed. Higher values indicate better-defined clusters. The *k* that maximizes the average silhouette width is often chosen.

Gap Statistic

The gap statistic (Tibshirani et al., 2001) compares the observed WCSS to its expected value under a null reference distribution (e.g., uniform data). The optimal *k* is the smallest value for which the gap between observed and expected WCSS is maximized. It is more computationally intensive but more principled than the elbow method.

Information-Theoretic Approaches

Methods such as the Akaike Information Criterion (AIC) and Bayesian Information Criterion (BIC) are sometimes adapted for k-means by treating it as a Gaussian mixture model with equal covariance. The optimal *k* minimizes a penalized version of the log-likelihood. These methods are less common but provide a formal model selection framework.

Data Preprocessing

Scaling and Normalization

Since k-means relies on distance calculations, features with larger scales dominate the result. Standardizing each feature to zero mean and unit variance (z-score normalization) or min-max scaling to [0,1] is essential when features have different units.

Handling Outliers

Outliers can disproportionately affect centroid positions and cluster assignments. Techniques include removing extreme points, using robust scaling (e.g., median and IQR), or reducing outlier influence by transforming the data (e.g., log transformation). In some cases, alternative algorithms (e.g., k-medoids) are more appropriate.

Computational Complexity and Scalability

Time Complexity of Lloyd’s Algorithm

Each iteration of Lloyd’s algorithm has a time complexity of O(*n* × *k* × *d*), where *n* is the number of data points, *k* is the number of clusters, and *d* is the number of dimensions. The total number of iterations is typically small (e.g., tens to a few hundred), making the algorithm efficient for moderate-sized datasets.

Memory Usage Considerations

Standard k-means stores the full dataset (O(*n* × *d*)) plus the centroids (O(*k* × *d*)). Memory requirements are thus linear in the number of points. For very large datasets that do not fit in memory, mini-batch or online variants can be used.

Choosing Initial Centroids

Beyond k-means++, other strategies include random initialization repeated multiple times, using the centroids from a small random subsample, or employing hierarchical clustering on a subset. The choice of initialization significantly affects both speed and final cluster quality.

Dealing with Empty Clusters

During the assignment step, a cluster may receive no points (empty cluster). Common remedies include: (1) reinitializing that centroid with a random point, (2) splitting a large cluster, or (3) removing the empty cluster and reducing *k*. Most implementations handle this automatically.

Internal Validation Metrics

Davies-Bouldin Index

The Davies-Bouldin index computes the average similarity between each cluster and its most similar neighbor, where similarity is defined as the ratio of within-cluster scatter to between-cluster separation. Lower values indicate better clustering.

Dunn Index

The Dunn index is the ratio of the minimum inter-cluster distance (between different clusters) to the maximum intra-cluster distance (diameter of the largest cluster). Higher values are desirable.

External Validation Metrics

Adjusted Rand Index

The adjusted Rand index (ARI) measures the similarity between two clusterings (e.g., algorithm output vs. ground truth) while correcting for chance. It ranges from −1 to 1, with 1 indicating perfect agreement.

Normalized Mutual Information

Normalized mutual information (NMI) quantifies the amount of information shared between cluster assignments and true labels, normalized to [0,1]. It is less sensitive to cluster sizes than ARI.

Stability Tests

Stability analysis checks whether clustering results are robust to small perturbations in the data (e.g., subsampling, adding noise). If the results change drastically, the clustering is likely unreliable. Methods include the average Jaccard index across subsamples or the Clustering Stability index.

Common Use Cases

Customer Segmentation

Marketers use k-means to group customers based on purchasing behavior, demographics, or browsing history. Clusters enable targeted advertising and personalized recommendations.

Image Compression

k-Means reduces the number of colors in an image by treating pixels as points in RGB space. Each color is replaced by the nearest centroid, allowing efficient storage (e.g., from 256 colors down to 16). This is akin to vector quantization.

Document Clustering

In natural language processing, k-means clusters documents based on term-frequency vectors (e.g., TF-IDF). It aids topic discovery and information retrieval, though cosine distance is often preferred over Euclidean.

Assumptions and Weaknesses

Sensitivity to Initial Conditions

As noted, the algorithm’s output depends heavily on initial centroid placement. Multiple runs with different seeds are often necessary to find a good solution.

Assumption of Spherical Clusters

k-Means implicitly assumes that clusters are isotropic (spherical) and of roughly equal size. Elongated, irregularly shaped, or overlapping clusters are poorly captured. Preprocessing techniques like PCA or spectral embedding can sometimes mitigate this.

Effect of Noise and Outliers

Noise and outliers can distort centroids and cause misassignments. The algorithm has no built-in noise handling; preprocessing or robust variants (e.g., k-medians) are recommended.

In R (stats package)

The kmeans() function from the stats package implements Lloyd’s algorithm with options for initialization (random or Forgy). Additional packages like factoextra provide visualization tools for cluster validation.

In Python (scikit-learn)

The KMeans class in sklearn.cluster offers Lloyd’s, k-means++, and mini-batch variants. It includes parameters for n_init (number of initializations), max_iter, and tolerance. The MiniBatchKMeans class handles large-scale settings.

In MATLAB and Other Languages

MATLAB’s kmeans() function supports the same core algorithm with options for distance metrics and initialization. Implementations also exist in Julia (Clustering.jl), Apache Spark MLlib, and TensorFlow, reflecting the algorithm’s widespread adoption.

Fuzzy C-Means Clustering

Fuzzy c-means (FCM) relaxes the hard assignment constraint, allowing points to belong to multiple clusters with membership degrees between 0 and 1. It is useful when cluster boundaries are ambiguous.

Hierarchical Clustering

Hierarchical clustering builds a tree of clusters without requiring a predefined *k*. Agglomerative (bottom-up) and divisive (top-down) approaches offer greater flexibility but are less scalable than k-means.

Gaussian Mixture Models

Gaussian mixture models (GMMs) are a probabilistic generalization of k-means. They model clusters as Gaussian distributions with parameters estimated via expectation-maximization (EM). GMMs allow elliptical clusters and soft assignments.

Spectral Clustering

Spectral clustering uses the eigenvectors of a similarity matrix (e.g., a graph Laplacian) to project data into a lower-dimensional space before applying k-means. It excels at detecting non-convex clusters and arbitrary shapes.