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 finds a Voronoi partition minimizing squared Euclidean distance to centroids. This objective tends to favor compact, convex, similarly dispersed groups; unequal size or density and non-convex shape can bias the partition, but they do not make every result automatically wrong.

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 and Euclidean distances have become uninformative — compare a reduction-first pipeline (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})

Lloyd's algorithm monotonically reduces WCSS until it reaches a local solution (or the stopping tolerance) — not necessarily the global optimum. That is why independent restarts can matter.

Tooling

  • KMeans
  • MiniBatchKMeans for large datasets
  • n_clusters=k
  • init="k-means++" (the scikit-learn default and a strong starting point)
  • n_init — number of runs with different centroid seeds. With scikit-learn's n_init="auto", this is 1 for init="k-means++" and 10 for init="random" or a callable initializer
  • max_iter
  • random_state
  • inertia_ — WCSS after fitting
  • cluster_centers_
  • labels_
  • silhouette_score for cluster quality
  • StandardScaler in a pipeline

See the scikit-learn KMeans API for the version-specific n_init="auto" behavior.

Choosing k

Two honest tools for choosing k:

The elbow method

Run K-Means for k = 1, 2, ..., 10 and plot inertia_ vs. k. The globally minimal achievable inertia cannot increase as k grows, although fitted results can wobble when runs reach different local solutions. Look for where additional clusters bring diminishing reduction. The elbow is a heuristic and may not be 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 useful hygiene moves:

  • scale before K-Means unless the features are already commensurate or their units intentionally encode weighting — otherwise a dollar feature and a percent feature cannot share a meaningful Euclidean distance
  • compare multiple initializations when stability matters — set an explicit integer such as n_init=10; do not assume n_init="auto" performs 10 runs with k-means++

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 makes the initialization reproducible. With random_state=None, runs may converge to different partitions or to the same partition with permuted cluster IDs.

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 ground truth instead of a hypothesis. The algorithm attempts to partition into k clusters (and may return fewer distinct clusters when the data has too few distinct points); whether the partition means anything requires stability checks and 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. Are feature scales comparable or intentionally weighted 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 applying Euclidean K-Means to arbitrary numeric encodings of categorical values can produce meaningless clusters.

Runnable Example

Run the clustering workflow from the repository root:

.venv/bin/python labs/svm-and-advanced-clustering/src/svm_clustering_workflow.py

Inspect cluster stability across seeds and compare K-Means with a method that can represent non-convex structure. A lower inertia alone does not establish that the clusters are useful.

Longer Connection

K-Means sits next to:

K-Means is a hypothesis machine. It proposes a centroid-based Euclidean partition. The next question is whether that geometry is stable and useful for the real task.