🎯

K-Means Clustering

The most-used clustering algorithm on Earth — place K centroids, assign every point to its nearest one, recentre, and repeat until the groups stop moving. Simple, fast, and everywhere.

Centroids Lloyd's Iteration Elbow Method K-Means++

Press Next → or use ← → arrow keys

Section 01

The Intuition — Party Tables

🎉 REAL-WORLD ANALOGY

Seating a party with no guest list

You're hosting a big party and want K tables where each guest sits near people they'll get along with — but you have no idea who knows whom. So you place K empty tables at random, ask every guest to walk to the nearest table, then slide each table to the middle of whoever showed up. Some guests move; you slide the tables again. After a few rounds, everyone's settled and the tables stop moving.

That's K-Means: place K centroids, assign each point to the closest one, move each centroid to its group's centre, and repeat until nothing changes.

💡

The Goal In One Line

K-Means partitions data into K groups so that points within a group are as close as possible to their centroid — it minimizes the total within-cluster distance, no labels required.

Section 02 · Algorithm

Lloyd's Algorithm — Five Steps

🔁 Assign · Update · Repeat

1Choose K and initialize K centroids (ideally with K-Means++).

2Assign every point to its nearest centroid by Euclidean distance.

3Update each centroid to the mean of the points assigned to it.

4Repeat steps 2–3 until assignments stop changing (convergence).

5Return the final centroids and cluster labels.

🔄

Expectation–Maximization In Miniature

The two-step dance — assign points, then move centroids — is a special case of EM. Each round can only lower (or hold) the total within-cluster distance, so K-Means is guaranteed to converge — though possibly to a local optimum, which is why initialization matters.

Section 02 · Diagram

Watch It Converge, Step By Step

🎬

Two Steps, Looped To Stillness

Assign points to the nearest centroid, move each centroid to its cluster's mean — and repeat. The centroids drift a little less each round until, at convergence, no point changes cluster and the centroids sit dead-centre in their groups.

Section 03 · Maths

The Objective — Minimize WCSS

Objective (within-cluster sum of squares)

J = Σₖ Σ_{x∈Cₖ} ‖ x − μₖ ‖²

Total squared distance from every point to its centroid — K-Means minimizes J, also called inertia.

Assignment step

cᵢ = argminₖ ‖ xᵢ − μₖ ‖²

Each point joins the cluster whose centroid is closest.

Update step

μₖ = (1/|Cₖ|) Σ_{x∈Cₖ} x

Each centroid becomes the mean of its assigned points.

Why the mean?

mean minimizes Σ‖x−μ‖²

For squared Euclidean distance, the centre that minimizes spread is exactly the average.

📉

Every Step Lowers J

The assignment step reduces J (points move to closer centroids) and the update step reduces J (the mean is the optimal centre). Since J can't rise and is bounded below, the algorithm must converge — its whole engine is this monotone descent.

Section 04 · Initialization

Initialization Matters — K-Means++

🌱

Seed Far, Not At Random

K-Means++ picks the first centroid at random, then chooses each next one with probability proportional to its squared distance from the closest existing centroid — so seeds spread across the blobs. It's the scikit-learn default (init='k-means++') because it converges faster and avoids the bad local optima that plain random starts fall into.

Section 05 · Choosing K

How Many Clusters? The Elbow Method

💪

The Bend Is The Sweet Spot

Plot WCSS against K. It always falls as K rises, but the drop is steep at first, then flattens. The elbow — where extra clusters stop buying much — is the natural choice. Pair it with the silhouette score and a sanity check against domain sense; if the elbow is unclear, silhouette often breaks the tie.

Section 05 · Quality

Silhouette — Are The Clusters Any Good?

Silhouette of a point

s = (b − a) / max(a, b)

a = mean distance to its own cluster; b = mean distance to the nearest other cluster.

The range

−1 ≤ s ≤ +1

≈ +1 well inside its cluster · ≈ 0 on a boundary · < 0 probably misassigned.

> 0.7Strong structure

0.5–0.7Reasonable

0.25–0.5Weak / overlapping

< 0.25No real clusters

📐

Elbow Finds K · Silhouette Judges It

Run K-Means for a range of K and pick the one with the highest average silhouette. Unlike the elbow — which can be ambiguous — silhouette gives a single number, and even lets you spot individual points that landed in the wrong cluster.

Section 06 · Preprocessing

Scaling Is Mandatory, Not Optional

⚠️

Distance Is Ruled By The Biggest-Scale Feature

K-Means assigns points by Euclidean distance. If income spans 0–100,000 and age spans 0–100, income utterly dominates the distance — age becomes invisible and clusters form on income alone. StandardScaler (zero mean, unit variance) puts every feature on equal footing before clustering.

📏 THE FIX

Always scale first — inside a Pipeline

Wrap StandardScaler and KMeans together so scaling is fit on training data only. Skipping this is the single most common K-Means mistake — clusters that look meaningless are almost always clusters formed on one runaway feature. If features are heavily skewed, consider a log transform before scaling.

Section 07 · Code

K-Means With scikit-learn

from sklearn.cluster import KMeans
from sklearn.preprocessing import StandardScaler
from sklearn.metrics import silhouette_score

X_scaled = StandardScaler().fit_transform(X)   # step 1 — always scale

km = KMeans(
    n_clusters=3,
    init='k-means++',   # smart seeding (default)
    n_init=10,           # 10 restarts, keep the best
    max_iter=300,
    random_state=42)      # reproducible
labels = km.fit_predict(X_scaled)

print(km.inertia_)                        # WCSS
print(silhouette_score(X_scaled, labels)) # cluster quality

🔁

Always Set n_init And random_state

n_init=10 runs the whole algorithm ten times from different seeds and keeps the lowest-WCSS result — cheap insurance against a bad start. random_state makes runs reproducible. For millions of rows, swap in MiniBatchKMeans for a big speed-up at a tiny accuracy cost.

Section 08 · Limitations

Where K-Means Breaks Down

🚫

Four Built-In Assumptions

K-Means assumes clusters are spherical, similar-sized, similar-density, and linearly separable — and needs K up front. Crescents, rings, elongated or unequal clusters break it. It's also sensitive to outliers, since a single far point can drag a centroid away.

Section 08 · Alternatives

When K-Means Isn't The Answer

Problem	Why K-Means Struggles	Use Instead
Non-spherical shapes	Assumes round clusters	DBSCAN · Spectral
Unknown K	Must pre-specify	DBSCAN · Hierarchical
Outliers / noise	Centroids get dragged	DBSCAN · K-Medoids
Overlapping / soft clusters	Forces hard assignment	Gaussian Mixture (GMM)
Varying density	Assumes equal spread	DBSCAN · HDBSCAN
Millions of rows	Full passes are slow	MiniBatchKMeans

🧭

Still The Right First Try

Despite these limits, K-Means is fast, scalable, and easy to interpret — start here on roughly-round, well-separated data, and switch to a specialized method only when the diagnostics (bad silhouette, crescents on a t-SNE plot) tell you to.

Section 09 · Variants

The K-Means Family

⚡

MiniBatch K-Means

Updates centroids on small random batches instead of the full set. Near-identical results, dramatically faster on huge data.

🛡️

K-Medoids

Uses actual data points as centres, not means — far more robust to outliers, and works with any distance metric.

🌫️

Gaussian Mixture

Soft, probabilistic clustering — each point gets a membership probability, and clusters can be elliptical, not just round.

🧬

Same Core Idea, Different Trade-offs

All three keep K-Means' assign-and-update spirit but relax one assumption: MiniBatch trades a hair of accuracy for speed, K-Medoids trades speed for outlier-robustness, and GMM trades simplicity for soft, elliptical clusters. Pick the relaxation your data demands.

Section 10 · Applications

Where K-Means Is Used Every Day

🛍️

Customer Segmentation

Group shoppers by spend and behaviour to target campaigns and pricing.

🖼️

Image Compression

Reduce an image to K representative colours — classic colour quantization.

📄

Document Grouping

Cluster articles or tickets by topic on top of TF-IDF or embeddings.

🧭

Feature Engineering

Turn cluster IDs (or distances to centroids) into features for a supervised model.

🗜️

Vector Quantization

Compress signals and embeddings by mapping vectors to their nearest centroid.

🚨

Anomaly Screening

Points far from every centroid make quick, cheap outlier candidates.

Section 11 · Golden Rules

Seven Rules For K-Means

🏅 K-Means, Distilled

1Always scale features first. StandardScaler in a Pipeline — the #1 K-Means mistake to avoid.

2Use init='k-means++' (the default) — smart seeding beats random every time.

3Set n_init=10+ so the best of several restarts wins, avoiding bad local optima.

4Choose K with elbow + silhouette, then sanity-check against domain knowledge.

5Profile clusters on original features. Numbers mean nothing until you describe each group.

6Switch algorithms when assumptions break — DBSCAN/GMM for odd shapes, MiniBatch for scale.

7Set random_state for reproducible clusters across runs.

Wrap-Up

You Now Own K-Means

assign→ nearest centroid

update→ cluster mean

WCSS↓Monotone descent

++Smart seeding

elbow+ silhouette

σ=1Scale first

🎯

The Through-Line

K-Means alternates two simple moves — assign points to the nearest centroid, then recentre — driving the within-cluster distance down until the groups lock in. Scale your features, seed with K-Means++, choose K with the elbow and silhouette, and know when its round-cluster assumption calls for a different tool.

📚

Where To Go Next

Cluster the Iris and Mall-Customers datasets, sweep K with elbow and silhouette, then compare DBSCAN and Gaussian Mixtures on the two-moons data to feel exactly where K-Means stops and they begin.

🎯 End of tutorial · Press ← to review, or click Restart