K-means in one sentence

K-means partitions data into K clusters by minimizing within-cluster variance.

The algorithm (intuition)

1. choose K
2. initialize K centroids
3. assign each point to nearest centroid
4. recompute centroids as the mean of assigned points
5. repeat until convergence

  flowchart TD
  A[Choose K] --> B[Initialize centroids]
  B --> C[Assign points to nearest centroid]
  C --> D[Update centroid = mean of cluster]
  D --> E{Converged?}
  E -->|no| C
  E -->|yes| F[Final clusters]

What K-means assumes

K-means works best when clusters are:

• roughly spherical (ball-shaped)
• similar size
• separable by distance

It struggles when clusters are:

• non-spherical
• different densities
• contain lots of outliers

Measuring quality: inertia

K-Means minimizes inertia — the mean squared distance between each instance and its closest centroid. Lower inertia means tighter clusters, but inertia alone can’t tell you how many clusters (kk) to use: it keeps getting smaller as kk grows, even when you’re carving a perfectly good cluster into useless slivers.

Choosing k: the elbow method and the silhouette score

Two ways to pick kk:

• Elbow method — plot inertia against kk. Inertia drops fast at first, then flattens out; the “elbow” of that curve is usually a good kk.
• Silhouette score — for each instance, compare aa (mean distance to its own cluster) and bb (mean distance to the next closest cluster): (b - a) / max(a, b)(b - a) / max(a, b). Values near +1+1 mean a great fit, near 00 mean the instance sits on a cluster boundary, and negative values mean it’s probably in the wrong cluster.

from sklearn.datasets import make_blobs
from sklearn.cluster import KMeans
from sklearn.metrics import silhouette_score
 
X, _ = make_blobs(n_samples=500, centers=5, cluster_std=0.7, random_state=42)
 
for k in range(2, 8):
    km = KMeans(n_clusters=k, n_init=10, random_state=42).fit(X)
    sil = silhouette_score(X, km.labels_)
    print(f"k={k}: inertia={km.inertia_:.1f}, silhouette={sil:.3f}")

from sklearn.datasets import make_blobs
from sklearn.cluster import KMeans
from sklearn.metrics import silhouette_score
 
X, _ = make_blobs(n_samples=500, centers=5, cluster_std=0.7, random_state=42)
 
for k in range(2, 8):
    km = KMeans(n_clusters=k, n_init=10, random_state=42).fit(X)
    sil = silhouette_score(X, km.labels_)
    print(f"k={k}: inertia={km.inertia_:.1f}, silhouette={sil:.3f}")

Scikit-learn example

from sklearn.cluster import KMeans
from sklearn.preprocessing import StandardScaler
from sklearn.pipeline import Pipeline
 
kmeans = Pipeline(
    steps=[
        ("scaler", StandardScaler()),
        ("model", KMeans(n_clusters=3, n_init=10, random_state=42)),
    ]
)

from sklearn.cluster import KMeans
from sklearn.preprocessing import StandardScaler
from sklearn.pipeline import Pipeline
 
kmeans = Pipeline(
    steps=[
        ("scaler", StandardScaler()),
        ("model", KMeans(n_clusters=3, n_init=10, random_state=42)),
    ]
)

Scaling up: MiniBatchKMeans

When a dataset is too big to comfortably re-scan every centroid update, MiniBatchKMeansMiniBatchKMeans updates centroids using small random batches instead of the whole dataset each step:

from sklearn.cluster import MiniBatchKMeans, KMeans
from sklearn.datasets import make_blobs
 
X, _ = make_blobs(n_samples=5000, centers=6, cluster_std=0.7, random_state=42)
 
km = KMeans(n_clusters=6, n_init=10, random_state=42).fit(X)
mbk = MiniBatchKMeans(n_clusters=6, n_init=10, random_state=42, batch_size=256).fit(X)
 
print(f"KMeans inertia:          {km.inertia_:.1f}")
print(f"MiniBatchKMeans inertia: {mbk.inertia_:.1f}")

from sklearn.cluster import MiniBatchKMeans, KMeans
from sklearn.datasets import make_blobs
 
X, _ = make_blobs(n_samples=5000, centers=6, cluster_std=0.7, random_state=42)
 
km = KMeans(n_clusters=6, n_init=10, random_state=42).fit(X)
mbk = MiniBatchKMeans(n_clusters=6, n_init=10, random_state=42, batch_size=256).fit(X)
 
print(f"KMeans inertia:          {km.inertia_:.1f}")
print(f"MiniBatchKMeans inertia: {mbk.inertia_:.1f}")

KMeans inertia:          4774.3
MiniBatchKMeans inertia: 4789.1

KMeans inertia:          4774.3
MiniBatchKMeans inertia: 4789.1

Notice the inertia is barely worse — but on a large dataset MiniBatchKMeansMiniBatchKMeans runs several times faster because it never needs the whole dataset in memory at once for a single centroid update.

Mini-checkpoint

K-means always assigns every point to a cluster.

• If you have outliers, what happens?

(Outliers still get assigned and can distort centroids.)

Visualize it

K-means repeats two steps until things stop moving: assign every point to its nearest centroid (colouring it), then move each centroid to the average position of the points that chose it. Watch the squares (centroids) drift into the middle of their clusters — click to scatter fresh data:

🧪 Try It Yourself

Exercise 1 – Fit KMeans and Inspect Centroids

Exercise 2 – Read the Inertia

Exercise 3 – Pick k with the Silhouette Score

Next

Continue to Hierarchical Clustering (Dendrograms) — build a tree of clusters instead of committing to a single value of kk up front.