K-Means Clustering
K-Means is the simplest and most popular clustering algorithm. It partitions data points into clusters by minimizing the within-cluster sum of squares. Even with no labels, the ML project loop still applies: that sum of squares is the objective, and the alternating assign-then-update procedure is the optimization that minimizes it.
Real-world examples: Customer segmentation, document clustering, image compression, anomaly detection, gene expression analysis.
The algorithm
- Initialize centroids randomly (or use K-Means++)
- Assign each point to the nearest centroid
- Update each centroid as the mean of its assigned points
- Repeat steps 2-3 until convergence
where is the set of points in cluster and is its centroid.
Intuition
Imagine hanging magnets on a whiteboard and placing nails near each. Each nail jumps to the nearest magnet, then each magnet moves to the center of its nails. Repeat until nothing moves.
Both steps provably decrease the objective : the assign step picks the nearest centroid for each point; the update step sets each centroid to the mean of its cluster, which is the unique minimizer of within-cluster squared distance (shown by setting the gradient to zero). Since can only decrease and there are finitely many assignments, K-Means must converge — to a local optimum.
For the gradient derivation and a complete 5-point 2-cluster worked iteration (all distance calculations, centroid updates, and the decrease verified numerically), see:
import numpy as np
from sklearn.cluster import KMeans
X = np.array([[1,1], [1.5,2], [3,4], [5,7], [3.5,5]])
kmeans = KMeans(n_clusters=2, random_state=42, n_init=10)
kmeans.fit(X)
print(f"Labels: {kmeans.labels_}")
print(f"Centroids:\n{kmeans.cluster_centers_}")
print(f"Inertia: {kmeans.inertia_:.2f}")
K-Means clustering (K = 3)
Two alternating moves: assign points to the nearest centroid (✕), then move each centroid to the mean of its cluster. Repeat until nothing changes.
Choosing K
K-Means never complains about a bad — its objective always decreases as grows, all the way to the trivial . Picking therefore needs evidence from outside the objective: the elbow method (where does adding a cluster stop paying?) and the silhouette score (is each point closer to its own cluster than to the next one?). Both — with a worked silhouette calculation, the metric's blind spots, and the stability check — are the subject of Evaluating Clusters & Choosing k.
K-Means++ initialization
Standard K-Means can get stuck in bad local optima. K-Means++ spreads initial centroids far apart:
- Pick first centroid randomly
- For each remaining centroid, pick a point with probability proportional to its distance from the nearest existing centroid
- Repeat until centroids are placed
# KMeans++ is the default in scikit-learn (init='k-means++')
kmeans = KMeans(n_clusters=3, init='k-means++', n_init=10, random_state=42)
Always run multiple times
K-Means converges to a local optimum — different runs can give different results. Always use n_init=10 (default) or higher to try multiple initializations and keep the best.
Limitations
- Assumes spherical clusters: Fails with elongated, crescent, or irregular shapes
- Sensitive to outliers: A single outlier can pull a centroid far away
- Requires K in advance: Must know or estimate the number of clusters
- Sensitive to initialization: Can converge to poor local optima
| When K-Means works well | When it fails |
|---|---|
| Spherical, equally-sized clusters | Crescent shapes |
| Clear separation between clusters | Overlapping clusters |
| Low-dimensional data | High-dimensional data |
| No outliers | Outliers present |
Standardize your features
K-Means uses Euclidean distance. If features have different scales (e.g., age in years vs. income in dollars), the larger-scale feature will dominate. Always standardize before clustering.
Exercise
In K-Means, which step is guaranteed to decrease the inertia at each iteration?
Need a hint?
One step is assignment, the other is updating centroids.
Exercise
Why must you standardize features before K-Means?
Need a hint?
K-Means uses Euclidean distance.
Common mistakes
- Not standardizing features: The #1 K-Means mistake. Always use
StandardScaler. - Using K=1 or K=n: Trivial solutions. Use the elbow method or silhouette score (next-next lesson).
- Ignoring the initialization: Always use K-Means++ and
n_init ≥ 10.
Key takeaways
- K-Means alternates assign to nearest centroid and move centroid to the mean until stable.
- It minimizes within-cluster variance but assumes spherical, similar-size clusters.
- Pick with the elbow or silhouette; use K-Means++ and
n_init>1. - Always standardize — K-Means uses Euclidean distance.
Related concepts
- Hierarchical & DBSCAN: clustering without choosing K, and arbitrary shapes
- Evaluating Clusters & Choosing k: elbow, silhouette, and stability
- Gaussian Mixture Models: the soft, probabilistic version of K-Means
- Principal Component Analysis: reducing dimensions before clustering