What is K-Means Clustering?
K-Means Clustering is a partitioning algorithm that assigns each vector to one of `k` centroids and updates each centroid to its members' mean to reduce within-cluster squared Euclidean distance.
Quick Facts
| Created | 1967 by James MacQueen; Lloyd's method published in 1982 |
|---|---|
| Specification | Official Specification |
How It Works
Match the objective to Euclidean mean geometry
K-Means minimizes squared Euclidean distance to arithmetic means. This favors roughly convex, isotropic groups of comparable scale. Replacing squared Euclidean distance with an arbitrary metric while retaining the mean update no longer optimizes the same objective; use a compatible medoid, spherical, or other clustering method instead.
Control initialization, empty clusters, and stopping
Lloyd's published quantization method supplies the alternating assignment and update structure. Practical runs need a declared initializer, multiple restarts, deterministic seeds, maximum iterations, tolerance, and an empty-cluster policy. Current scikit-learn documentation also warns that early stopping can leave reported centers inconsistent with the last assignments.
Select k and validate on evidence beyond inertia
Inertia always weakly decreases as k grows, so minimizing it alone favors excessive fragmentation. Compare candidate values with held-out or resampled stability, Silhouette and related diagnostics, cluster-size distributions, expert review, and downstream outcomes. Freeze the feature model, normalization, weighting, seed policy, and cluster-label mapping before production comparison.
Key Characteristics
- Produces exactly k non-overlapping hard clusters
- Optimizes within-cluster squared Euclidean distance
- Alternates nearest-centroid assignment and arithmetic-mean updates
- Converges to a local fixed point that depends on initialization
- Supports efficient nearest-centroid assignment for new vectors
- Is sensitive to scaling, outliers, empty clusters, and non-convex geometry
Common Use Cases
- Creating a fast baseline for document or embedding segmentation
- Vector quantization and codebook construction
- Grouping customers or items when compact Euclidean clusters are plausible
- Compressing a large sample into representative centroids
- Comparing stable candidate partitions before human topic naming
Example
Loading code...Frequently Asked Questions
What objective does K-Means minimize?
It minimizes the sum of squared Euclidean distances from each sample to the mean of its assigned cluster, also called within-cluster sum of squares or inertia. This objective is not the sum of ordinary distances and does not support arbitrary metrics.
Does K-Means always find the global optimum?
No. Lloyd's alternating updates monotonically reduce or preserve inertia until a local fixed point, but different initial centroids can reach different solutions. Use a declared initializer, multiple restarts, fixed seeds, and stability reporting.
How should the number of clusters k be selected?
Treat `k` as a model-selection parameter. Compare a prespecified range with several diagnostics and resampling stability, then verify interpretability and downstream value on untouched evidence. Inertia alone always favors more clusters.
Why does K-Means struggle with outliers or unequal clusters?
Arithmetic means and squared distances give distant points large influence and imply Voronoi-shaped, roughly isotropic groups. Outliers, elongated shapes, different densities, and severe size imbalance can move centroids or split the wrong structure.
Can K-Means assign new records after training?
Yes. A frozen model can assign a new compatible vector to its nearest centroid. The vectorizer, dimensions, scaling, centroid version, distance convention, and rejection policy must remain fixed; retraining can also permute cluster IDs.