Skip to content

K-Means

What This Is

K-Means partitions n points into k clusters by alternating two steps:

  1. assign each point to the nearest cluster center
  2. recompute each cluster center as the mean of its assigned points

The objective being minimized is the within-cluster sum of squares (WCSS, also called inertia): Σ_i ||x_i - μ_{c(i)}||².

The practical lesson is that K-Means answers "which k compact, roughly equal-sized, spherical clusters does this data look like?" — and only that question. The moment the clusters are not spherical, not equal-sized, or not compact in Euclidean distance, K-Means imposes its assumptions anyway and gives you a confidently wrong answer.

When You Use It

  • fast exploratory clustering of tabular data with continuous scaled features
  • quantization — producing a small codebook of prototype vectors
  • initializing more expensive unsupervised methods
  • a structure-check before hand-labeling — if K-Means and your intended labels disagree, one of them is worth questioning

Do Not Use It When

  • clusters have very different sizes or densities
  • clusters are elongated, curved, or non-convex — use DBSCAN or spectral clustering instead; see Advanced Clustering and Dimensionality Reduction
  • features are unscaled or categorical — the Euclidean objective is meaningless
  • you need a probabilistic cluster membership — a Gaussian Mixture Model is the right tool
  • the data is very high-dimensional — reduce first (see PCA)

The Algorithm

1. initialize k centers (k-means++ is the standard initializer)
2. repeat until centers stop moving:
   a. for each point x_i: c(i) = argmin_k ||x_i - μ_k||^2
   b. for each cluster k:  μ_k = mean({x_i : c(i) = k})

Convergence is guaranteed to a local minimum of WCSS — not the global minimum. That is why n_init (number of independent restarts) matters.

Tooling

  • KMeans
  • MiniBatchKMeans for large datasets
  • n_clusters=k
  • init="k-means++" (default; almost always the right choice)
  • n_init — number of random restarts (scikit-learn default is n_init="auto", typically 10)
  • max_iter
  • random_state
  • inertia_ — WCSS after fitting
  • cluster_centers_
  • labels_
  • silhouette_score for cluster quality
  • StandardScaler in a pipeline

Choosing k

Two honest tools for choosing k:

The elbow method

Run K-Means for k = 1, 2, ..., 10 and plot inertia_ vs. k. Inertia always decreases — but the rate of decrease usually flattens after the "right" k. The elbow is where extra clusters stop being worth it. The elbow is a heuristic, not a theorem; it often shows but is not always sharp.

Silhouette score

For each point, silhouette = (b - a) / max(a, b) where a is mean distance to other points in the same cluster and b is mean distance to the nearest other cluster. Average over all points. Higher is better; negative values indicate points that would be better in a different cluster.

Combine both. Run the elbow for a fast first guess, confirm with silhouette at the elbow and one k on either side.

Scaling And Initialization

Two non-negotiable hygiene moves:

  • always scale before K-Means — a dollar feature and a percent feature cannot share a Euclidean distance
  • always run multiple initializations — a single restart can land on a bad local minimum; n_init=10 is the standard default

Minimal Example

from sklearn.pipeline import make_pipeline
from sklearn.preprocessing import StandardScaler
from sklearn.cluster import KMeans

model = make_pipeline(StandardScaler(), KMeans(n_clusters=4, n_init=10, random_state=0))
model.fit(X)
labels = model.predict(X)

The random_state gives you a reproducible answer. K-Means with a floating seed produces different cluster IDs on every run (though usually the same partitions).

What To Inspect

  • the elbow curve — where does inertia stop dropping meaningfully
  • the silhouette score at the chosen k
  • cluster sizes — are any clusters tiny or huge
  • a 2D projection (PCA or UMAP) colored by cluster — do the clusters look separable there
  • cluster centers on the original feature scale — what do they actually mean
  • whether the partition changes across random_state values — if yes, the clustering is unstable

Failure Pattern

Running K-Means on unscaled features and reporting the clusters as a finding. The biggest-variance feature is almost certainly doing all the work of distance.

A second failure pattern is treating K-Means output as a ground truth instead of a hypothesis. K-Means will always give you k clusters; whether those k clusters mean anything is a separate question you have to answer with silhouette, cluster stability, or domain interpretation.

A third failure pattern is mistaking "K-Means converged" for "K-Means found the right answer." Convergence to a local optimum is a convergence to some optimum, not the best one.

Quick Checks

  1. Is the data scaled before K-Means?
  2. Is n_init at least 10?
  3. Is random_state fixed?
  4. Did you look at the elbow or silhouette score, not just pick k=3 by habit?
  5. Do the clusters survive a different random_state?

Practice

  1. Generate three isotropic Gaussian blobs and confirm K-Means recovers them.
  2. Generate two elongated blobs along a diagonal axis and watch K-Means fail. Explain why.
  3. Sweep k from 2 to 10 and plot inertia. Identify the elbow.
  4. Compute silhouette scores for k = 2, 3, 4, 5 on the same data and compare to the elbow.
  5. Run K-Means twice with different random_state values. Are the clusters stable?
  6. Use MiniBatchKMeans on a dataset with 100k rows and compare timing and result quality to full K-Means.
  7. Explain why scaling matters and why k-means++ is a better initializer than random.
  8. Describe one case where DBSCAN or a Gaussian mixture model would be a better fit.
  9. State the relationship between K-Means and the Gaussian mixture model with shared identity covariance.
  10. Explain why K-Means always has a well-defined but often useless answer on categorical data.

Longer Connection

K-Means sits next to:

K-Means is a hypothesis machine. It tells you what the data looks like if the clusters are spherical, equal-sized, and compact. The next question is always whether that assumption matches reality.