K-Means ClusteringOpen in Colab
ML project loop
Data·Hypothesis space·Objective·Optimization·Evaluation·Deployment feedback

K-Means Clustering

K-Means is the simplest and most popular clustering algorithm. It partitions nn data points into KK 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.

Deep dive
The ML Project Loop
Includes runnable notebook

Real-world examples: Customer segmentation, document clustering, image compression, anomaly detection, gene expression analysis.

The algorithm

  1. Initialize KK centroids randomly (or use K-Means++)
  2. Assign each point to the nearest centroid
  3. Update each centroid as the mean of its assigned points
  4. Repeat steps 2-3 until convergence
J=∑k=1K∑xi∈Ck∥xi−μk∥2J = \sum_{k=1}^{K} \sum_{\mathbf{x}_i \in C_k} \|\mathbf{x}_i - \boldsymbol{\mu}_k\|^2

where CkC_k is the set of points in cluster kk and μk\boldsymbol{\mu}_k is its centroid.

Intuition

Imagine hanging KK 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 JJ: 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 JJ 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 JJ decrease verified numerically), see:

Deep dive
K-Means: Full Algorithm
Includes runnable notebook
Python
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)

feature x₁feature x₂
iter0
nextassign

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 KK — its objective JJ always decreases as KK grows, all the way to the trivial K=nK = n. Picking KK 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:

  1. Pick first centroid randomly
  2. For each remaining centroid, pick a point with probability proportional to its distance from the nearest existing centroid
  3. Repeat until KK centroids are placed
Python
# 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

  1. Assumes spherical clusters: Fails with elongated, crescent, or irregular shapes
  2. Sensitive to outliers: A single outlier can pull a centroid far away
  3. Requires K in advance: Must know or estimate the number of clusters
  4. Sensitive to initialization: Can converge to poor local optima
When K-Means works wellWhen it fails
Spherical, equally-sized clustersCrescent shapes
Clear separation between clustersOverlapping clusters
Low-dimensional dataHigh-dimensional data
No outliersOutliers 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

  1. Not standardizing features: The #1 K-Means mistake. Always use StandardScaler.
  2. Using K=1 or K=n: Trivial solutions. Use the elbow method or silhouette score (next-next lesson).
  3. 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 KK with the elbow or silhouette; use K-Means++ and n_init>1.
  • Always standardize — K-Means uses Euclidean distance.

Related concepts

Concept neighbourhood

How this concept connects — click any node to jump there, or explore the whole concept map.

Builds onRelatedGo deeper
K-Means ClusteringLinear & Logistic Regress…K-Nearest NeighborsEvaluating Clusters & Cho…Hierarchical Clustering &…Gaussian Mixture ModelsPrincipal Component Analy…Topic Modeling with BERTo…The ML Project LoopK-Means: Full AlgorithmHierarchical Clustering L…HNSW: Hierarchical Naviga…Vector Databases & ANN In…