1 Introduction
1.1 Definition and purpose
k-means is a centroid-based unsupervised learning algorithm that partitions a dataset of \( n \) observations into \( k \) distinct clusters. Each observation is assigned to the cluster whose mean (centroid) is nearest, using a distance metric—typically Euclidean distance. The algorithm’s primary goal is to minimize the within-cluster sum of squares (WCSS), a measure of intra-cluster variance. By grouping similar data points, k-means serves as a tool for exploratory data analysis, pattern recognition, and data compression.
1.2 Historical context
The k-means concept was independently proposed in the 1950s and 1960s. The term "k-means" was first used by James MacQueen in 1967, though earlier formulations (e.g., Lloyd’s algorithm in 1957 for pulse-code modulation) laid the groundwork. The algorithm became widely used in statistics and computer science due to its simplicity and speed, later spawning numerous variants to address its inherent limitations.
2 Algorithm details
2.1 Steps of the standard algorithm
2.1.1 Initialization
The algorithm begins by selecting \( k \) initial centroids, one per cluster. The choice of initial centroids significantly affects the final clustering.
2.1.1.1 Random initialization
A straightforward approach is to randomly pick \( k \) distinct observations from the dataset as initial centroids. This method is simple but can lead to suboptimal results if the selected points are close together or lie in low-density regions.
2.1.1.2 Forgy method and MacQueen method
- Forgy method (1965): Randomly selects \( k \) observations as centroids, ensuring they are often distinct and spread across the data space.
- MacQueen method (1967): Assigns each observation to one of \( k \) initially random centroids, then updates centroids incrementally after each assignment. This approach is more dynamic but can be sensitive to the order of points.
2.1.2 Assignment step
Each observation is assigned to the cluster whose centroid is nearest, based on the chosen distance metric (commonly Euclidean distance). Formally, for each point \( x_i \), the cluster label \( c_i \) is set to \(\arg\min_{j} \|x_i - \mu_j\|^2\).
2.1.3 Update step
After all points are assigned, each centroid \( \mu_j \) is recalculated as the mean of all points belonging to that cluster: \( \mu_j = \frac{1}{|C_j|} \sum_{x_i \in C_j} x_i \).
2.1.4 Convergence criteria
The assignment and update steps repeat until convergence. Common stopping criteria include:
- No change in cluster assignments between iterations.
- Centroid positions (or the objective function value) change by less than a predefined threshold.
- A maximum number of iterations is reached.
2.2 Pseudocode
``` Initialize k centroids μ₁, μ₂, …, μₖ (e.g., randomly) Repeat until convergence:
for i = 1 to n: cᵢ := argminⱼ ||xᵢ – μⱼ||²
for j = 1 to k: μⱼ := (1/|Cⱼ|) Σ xᵢ over all xᵢ in Cⱼ ```
3 Mathematical formulation
3.1 Objective function (sum of squared errors)
The k-means objective is to minimize the sum of squared Euclidean distances between each point and its assigned centroid:
\[ \text{SSE} = \sum_{j=1}^{k} \sum_{x_i \in C_j} \|x_i - \mu_j\|^2 \]
where \( C_j \) is the set of points in cluster \( j \) and \( \mu_j \) is its centroid. Minimizing SSE is equivalent to maximizing intra-cluster cohesion.
3.2 Distance metrics
3.2.1 Euclidean distance
The most common metric in k-means, defined as \( \|x_i - \mu_j\| = \sqrt{\sum_{d=1}^{D} (x_{id} - \mu_{jd})^2} \). It assumes isotropic clusters and is sensitive to feature scale.
3.2.2 Other metrics (Manhattan, cosine)
- Manhattan distance: \( \sum_{d=1}^{D} |x_{id} - \mu_{jd}| \). Used when data has high-dimensional sparsity or when clusters are expected in a grid-like pattern.
- Cosine similarity (or distance): \( 1 - \cos(x_i, \mu_j) \). Applied in text or document clustering where magnitude is less important than direction.
4 Properties and limitations
4.1 Computational complexity
Standard k-means has a time complexity of \( O(n \cdot k \cdot I \cdot D) \), where \( n \) is the number of observations, \( k \) the number of clusters, \( I \) the number of iterations, and \( D \) the dimensionality. For each iteration, distances are computed between every point and every centroid. The algorithm scales linearly with \( n \) and is efficient for moderate \( k \) and \( D \).
4.2 Sensitivity to initial centroids
Poor initial centroid selection may lead to convergence to a local minimum (see §4.4) or produce empty clusters. Multiple restarts with different seeds can mitigate this issue, but it does not guarantee a globally optimal solution.
4.3 Assumptions about cluster shape and size
k-means assumes clusters are:
- Spherical: It favors round, convex clusters due to Euclidean distance.
- Equal size/variance: The algorithm implicitly assumes clusters have roughly the same number of points and variance; otherwise, large clusters may split or small clusters may be absorbed.
4.4 Local optima problem
The objective function (SSE) is non-convex, and k-means is a hill-climbing procedure that can stop at a local optimum. Different initializations often produce different results. Advanced initialization methods (e.g., k-means++) aim to reduce this problem.
5 Variants and extensions
5.1 k-means++
A seeding method that chooses initial centroids with probabilities proportional to their squared distance from the nearest already-chosen centroid. This yields better coverage and often leads to faster convergence and higher-quality clusters.
5.2 Mini-batch k-means
Uses random subsets (mini-batches) of data to update centroids incrementally. It dramatically reduces computational cost for large datasets, though at a slight cost in cluster quality.
5.3 Bisecting k-means
A hierarchical approach: start with one cluster containing all points, then repeatedly split the largest cluster using standard k-means (k=2) until the desired \( k \) is reached. This produces a tree of clusters and can help with the local optima issue.
5.4 Fuzzy c-means
Also known as soft k-means. Each point has a degree of membership (0 to 1) to each cluster, rather than a hard assignment. The algorithm iteratively updates centroids and membership values using a fuzziness parameter \( m \).
5.5 X-means and G-means
- X-means: Automatically determines the number of clusters \( k \) by splitting clusters and using a model selection criterion (e.g., Bayesian Information Criterion).
- G-means: Tests whether each cluster follows a Gaussian distribution; if not, it splits that cluster. This relaxes the fixed-\( k \) assumption.
6 Applications
6.1 Image segmentation
k-means groups pixels by color or intensity in feature space (e.g., RGB values). Each cluster corresponds to a region of the image, enabling tasks like object detection and background removal.
6.2 Document clustering
Each document is represented as a vector of term frequencies (TF-IDF). k-means groups similar documents (e.g., news articles), enabling topic discovery or information retrieval.
6.3 Customer segmentation
In marketing, customers are clustered based on purchasing behavior, demographics, or browsing history. Members of the same cluster receive targeted campaigns.
6.4 Anomaly detection
Data points far from all centroids (or in very small clusters) can be flagged as anomalies. This is common in network intrusion detection and fraud analysis.
7 Evaluation and selection of k
7.1 Elbow method
Plot the objective function (SSE) against increasing \( k \). The "elbow" point—where the rate of decrease sharply slows—suggests an appropriate \( k \). This method is intuitive but subjective.
7.2 Silhouette coefficient
For each point, compute its average distance to points in its own cluster (\( a \)) and to the nearest other cluster (\( b \)). The silhouette coefficient for a point is \( (b-a)/\max(a,b) \). The average over all points ranges from -1 to 1; higher values indicate better-defined clusters.
7.3 Gap statistic
Compares the within-cluster dispersion of the data to that expected under a null reference distribution (e.g., uniform). The optimal \( k \) is where the gap between the observed and expected dispersion is largest.
8 Implementation considerations
8.1 Handling missing data
k-means cannot handle missing values directly. Common strategies include:
- Removing observations with missing entries.
- Imputing missing values (e.g., with feature means).
- Using distance metrics robust to missing values (e.g., ignoring missing dimensions).
8.2 Feature scaling
Since k-means relies on Euclidean distance, features with larger magnitudes dominate the distance calculation. Standardization (zero mean, unit variance) or min-max scaling is essential to give all features equal weight.
8.3 Choosing initialization seeds
Given sensitivity to initial centroids, practitioners often run k-means multiple times with different random seeds and select the run with the lowest SSE. Deterministic seeds (e.g., from k-means++) are recommended for reproducibility and quality.