Skip to content

Learn / Unsupervised

Clustering

Grouping points that belong together, without labels. Centroids, densities, mixtures and hierarchies.

Jump to the playground

On this page
  1. Intuition
  2. What the data looks like
  3. How the data is prepared
  4. Algorithms
  5. The maths
  6. Real-world examples
  7. Playground
  8. In Python
  9. Pitfalls

Intuition

Clustering sorts points into groups so that members of a group are more alike than members of different groups. The algorithms differ in what “a group” means: a blob around a centre (k-means), a dense region (DBSCAN), a bell-shaped cloud (Gaussian mixture), or a branch of a tree (agglomerative).

What the data looks like

Each row is one thing you want to group. There is no answer column; the algorithm adds one.

ATM grouping: one row per ATM One row = one ATM over the last quarter. Answer: none in the data; the model adds a cluster number.
rowatminputwithdrawals_dayinputpeak_hourinputweekend_shareinputcash_outs_monthoutputcluster
ATM-17310180.224A
ATM-2395120.480B
ATM-31288170.253A
ATM-40120130.511B

The cluster column is not in the data you start with. The algorithm writes it, and you name the groups afterwards ("busy evening ATMs", "quiet weekend ATMs").

Example rows are invented for illustration.

How the data is prepared

  • Standardise every feature; otherwise the one measured in the largest units decides the clusters.
  • Choose the distance: Euclidean for numeric features, cosine for embeddings.
  • Handle outliers: k-means will happily spend a centroid on three extreme customers.
  • Reduce dimensions first when there are many correlated features; distances lose meaning in high dimensions.

Algorithms

k-means

Alternate between assigning points to the nearest centroid and moving centroids to the mean.

Cost
O(iters·n·k)
Strength
Fast, simple, scales well.
Weakness
You must pick k; assumes round, equal-sized clusters.
Used for
customer segmentation, ATM grouping
Open in the playground

E-means

Start with too many centroids and let evolution merge, delete and nudge them until the description length stops improving.

Cost
O(gens·n·k)
Strength
Finds the number of clusters on its own.
Weakness
Still assumes round clusters; slower than k-means.
Used for
segments when k is unknown, ATM grouping
Open in the playground

Mini-batch k-means

k-means on small random batches.

Cost
O(iters·batch·k)
Strength
Handles very large or streaming data.
Weakness
Slightly worse clusters than full k-means.
Used for
segmenting millions of customers
Open in the playground

DBSCAN

Grow clusters from dense regions; sparse points are noise.

Cost
O(n log n) with an index
Strength
Finds arbitrary shapes and outliers; no k.
Weakness
Struggles when densities differ; ε is sensitive.
Used for
anomaly pockets, geo clustering
Open in the playground

Gaussian mixture (EM)

Model the data as a blend of Gaussians and fit them with expectation-maximisation.

Cost
O(iters·n·k)
Strength
Soft assignments; elliptical clusters.
Weakness
Can converge to poor local optima.
Used for
overlapping segments, density estimation
Open in the playground

Agglomerative

Start with every point alone and repeatedly merge the two closest clusters.

Cost
O(n²) memory
Strength
Gives a full hierarchy (dendrogram); no k up front.
Weakness
Does not scale to large n.
Used for
document topics, taxonomy building
Open in the playground

The maths

k-means minimises the within-cluster sum of squares (inertia):

J=∑j=1k∑xi∈Cj∥xi−μj∥2J = \sum_{j=1}^{k} \sum_{x_i \in C_j} \lVert x_i - \mu_j \rVert^2

by alternating two steps that can only lower JJ: assign each point to its nearest centroid, then move each centroid to the mean of its points. The result depends on where the centroids start, which is why k-means++ spreads the initial centroids out.

E-means removes the need to choose kk. It treats the set of centroids as an organism that evolves: each generation tries merging the closest pair, deleting the smallest cluster and nudging a centroid, and keeps whichever change lowers a description-length fitness,

fitness=−2log⁡L+plog⁡n\text{fitness} = -2\log L + p\log n

where LL is the likelihood of the data under one spherical Gaussian per cluster and pp the number of parameters. More clusters always fit better, but each one costs log⁡n\log n per parameter, so the search settles where an extra cluster stops paying for itself.

A Gaussian mixture softens this. Each point gets a responsibility rijr_{ij} for every component (E-step), and each component’s mean and covariance are re-estimated from the points weighted by rijr_{ij} (M-step).

The silhouette of a point compares its mean distance to its own cluster, aa, with the mean distance to the nearest other cluster, bb:

s=b−amax⁡(a,b)∈[−1,1]s = \frac{b - a}{\max(a, b)} \in [-1, 1]

Real-world examples

  • Customer segmentation: groups by product usage and transaction behaviour, for targeted offers.
  • ATM grouping: clustering machines by usage pattern to plan cash loading and maintenance.
  • Anomaly pockets: DBSCAN’s “noise” points are candidates for review.
  • Document topics: clustering embeddings of support tickets.

Playground

Three models on the same blobs. k-means is told k = 3. E-means starts with ten centroids and has to discover the number of clusters itself: watch the loss chart step down each time it merges two clusters or deletes one. DBSCAN needs no k either but counts dense regions. Raise the blob count to six, or switch the data to moons, and press Train again. Use Add model for a fourth.

Data
More data options
Model A
Model B
Model C

Uses at most 3000 training points.

A · k-means

Click the plot to add a point.

B · E-means

Press Train to compare.

C · DBSCAN

Press Train to compare.

inertia per step (axis fitted to the range)

Train a model to see its loss curve.

Step -train ━test ┅

colour = cluster · ✕ = noise · ● train ○ test

Press Train. The verdict appears here.

In Python

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

Xs = StandardScaler().fit_transform(X)

for k in range(2, 9):  # there is no "right" k: look at the curve, then at the segments themselves
    km = KMeans(n_clusters=k, n_init=10, random_state=42).fit(Xs)
    print(k, round(km.inertia_), round(silhouette_score(Xs, km.labels_), 3))

Pitfalls

  • k-means on non-round clusters. It cuts moons and rings in half, as the playground shows.
  • Trusting one run. Different seeds can give different clusters; check stability.
  • Picking k from a metric alone. The elbow is a hint; the test is whether the business can use the segments.
  • DBSCAN with varying density. One ε cannot fit both a tight and a loose cluster.