---
source: 'https://howaiworks.ai/glossary/clustering'
section: glossary
title: Clustering
description: >-
  Grouping unlabeled data into clusters: which algorithm to pick, why each one
  imposes a shape, how to choose k, and how to tell if the clusters are real.
tags:
  - unsupervised learning
  - Machine Learning
  - pattern discovery
  - dimensionality reduction
category: Machine Learning
datePublished: '2025-07-16'
lastUpdated: '2026-07-21'
---

# Clustering

> Grouping unlabeled data into clusters: which algorithm to pick, why each one imposes a shape, how to choose k, and how to tell if the clusters are real.

## Definition

Clustering divides unlabeled data into groups whose members resemble each other more than they
resemble anything outside the group, and the practical question — *which algorithm* — has a short
answer. Reach for **k-means** when you expect a handful of compact, roughly equal-sized blobs and
can name how many; **DBSCAN or HDBSCAN** when the groups may be irregularly shaped, unknown in
number, or surrounded by junk you want excluded rather than assigned; **hierarchical clustering**
when you would rather see the whole merge order than commit to one cut; **Gaussian mixtures** when
groups overlap and you want a probability of membership instead of a hard label.

That list is short because the real difficulty is elsewhere. No algorithm finds *the* groups in your
data; each finds the best groups **of the shape it was built to look for**, and it will return them
whether or not such groups exist. On two concentric rings, k-means scores an adjusted Rand index of
−0.001 against the true grouping — indistinguishable from random — while DBSCAN scores 1.000. Neither
algorithm malfunctioned. They were asked different questions, and each answered its own correctly.
Everything else on this page follows from that.

## How It Works

Every clustering method is built from three separable choices: a **distance** that says what
"similar" means, an **objective or rule** that says what a good grouping is, and a **search** that
tries to find one. Most disappointing results trace to the first two, which people rarely think of
as choices at all.

### Distance is a modelling decision, usually made by accident

Take two people described by height in metres and weight in kilograms: (1.60 m, 80 kg) and
(1.80 m, 60 kg). Their squared Euclidean distance is 0.20² + 20² = 0.04 + 400 = 400.04. Height
contributes **0.01%** of the distance and weight contributes the rest, so any algorithm using this
metric is clustering on weight and quietly ignoring height. Now record height in centimetres instead
of metres. The same two people, the same information, but the distance becomes 20² + 20² = 800, and
height and weight now carry exactly half each. The clusters change because a unit changed.

This is the most common practical error in applied clustering, and the fix is boring: standardise
every feature to zero mean and unit variance first. The subtler consequence is that standardising
then gives every feature equal weight, which is also an assumption — one that ten redundant columns
about price exploit by outvoting the single column about behaviour. What goes into the feature
vector is part of the clustering; see [feature selection](https://howaiworks.ai/glossary/feature-selection) and
[dimensionality reduction](https://howaiworks.ai/glossary/dimensionality-reduction).

### The objective cannot choose k, and here is the arithmetic

k-means minimises the within-cluster sum of squared distances to the cluster centroids, called
*inertia*. Run it on the same 1,000-point dataset at increasing k and inertia falls monotonically:
584.82 at k=1, then 384.05, 246.56, 184.03, 153.05 — and 0.00 at k=1,000, where every point is its
own centroid and its distance to itself is zero. The objective is minimised, perfectly, by the
answer that groups nothing. **"Pick the k that minimises the objective" is therefore not a
criterion**, and no amount of data will supply one.

The **elbow heuristic** is what people use instead: plot inertia against k and look for the bend
where extra clusters stop buying much. It is a heuristic because it asks you to see a corner on a
smooth curve. On that ring data, the successive drops are 201, 137, 63 and 31 — the sharpest bend
sits between k=3 and k=4, while the true number of groups is 2. The elbow points at the wrong answer
on a dataset where the right one is known.

**Silhouette score** is the more informative tool. For each point it compares *a*, the mean distance
to the other members of its own cluster, with *b*, the mean distance to the members of the nearest
other cluster, giving s = (b − a) / max(a, b). A point sitting at a = 0.8 inside a cluster whose
nearest rival is b = 2.4 away scores (2.4 − 0.8) / 2.4 = **0.67**; a point that is closer to the
neighbouring cluster than to its own, a = 2.4 against b = 0.8, scores **−0.67**. Averaged over the
dataset, silhouette measures separation relative to compactness — which is a real property, but as
the Challenges section shows, not the same property as "these clusters exist".

### The search is approximate, and that is not a bug you can fix

Finding the partition that truly minimises inertia is NP-hard, and the search space is why: the
number of ways to split just 25 points into 5 non-empty groups is 2,436,684,974,110,751 — over
2.4 × 10¹⁵. Lloyd's algorithm, the thing everyone calls "k-means", sidesteps this by alternating two
cheap steps — assign each point to its nearest centroid, move each centroid to the mean of its
points — until nothing moves. It converges quickly, at cost roughly O(n × k × d × i) for n points,
d dimensions and i iterations, and it converges to a **local** optimum that depends on where the
centroids started. That is why libraries run it several times from different seeds (scikit-learn's
`n_init`) and keep the best, and why k-means++ initialisation, which spreads the initial centroids
apart with probability proportional to squared distance, is the default.

## Types

The field's standard taxonomy sorts algorithms by what they assume a cluster *is*. Read it as four
different definitions of the word, not four tools of equal generality.

**Centroid-based** methods define a cluster as the set of points nearest to a representative point.
k-means is the archetype: minimising squared distance to a centroid means the boundary between any
two clusters is a straight line equidistant from both, so the regions are convex and the clusters
come out roughly spherical and similarly sized. Hand it two concentric rings and it slices them like
a pie, because a pie slice genuinely is the lowest-inertia answer available. k-medoids and k-medians
swap the objective for something more robust to outliers but keep the same geometry.

**Density-based** methods define a cluster as a connected region where points are packed more tightly
than the surroundings. DBSCAN needs two parameters — a radius `eps` and a minimum neighbour count
`min_samples` — and grows clusters by linking points that have enough neighbours within `eps`,
leaving everything else labelled as noise. This buys three things k-means cannot offer: arbitrary
shapes, a cluster count discovered rather than declared, and explicit outliers. It pays for them
with a single global density threshold, so a dataset containing one dense group and one diffuse
group cannot be handled at any `eps`. HDBSCAN removes that limitation by building the clustering
across all density thresholds at once and extracting the most persistent groups.

**Hierarchical** methods refuse to pick one grouping and produce the whole nested family instead,
usually agglomerative: start with every point as its own cluster and repeatedly merge the closest
pair, recording the merge order as a dendrogram you can cut at any height. The *linkage* rule is the
assumption in disguise. Single linkage measures cluster distance by the closest pair and so happily
traces long chains and irregular shapes; complete linkage uses the farthest pair and produces compact
balls; Ward's method merges the pair that increases total within-cluster variance least, which is the
k-means objective in hierarchical clothing — and inherits the same bias toward spheres. The cost is
scale: n points have n(n−1)/2 pairwise distances, so 100,000 points imply about 5 billion pairs and
roughly 20 GB just to hold them at 4 bytes each.

**Distribution-based** methods assume the data was generated by a mixture of probability
distributions and try to recover their parameters. A Gaussian mixture model fitted by
expectation-maximisation gives each point a *probability* of belonging to each component rather than
a hard assignment, and because each component has its own covariance matrix it can represent
elongated and tilted ellipses that k-means cannot. Constrain every covariance to be spherical and
equal and the algorithm degenerates into k-means, which is the cleanest statement of what k-means
was assuming all along.

## Real-World Applications

Customer segmentation is the textbook example and is covered under
[unsupervised learning](https://howaiworks.ai/glossary/unsupervised-learning); the deployments below are the ones where
clustering is load-bearing infrastructure rather than an analysis step.

**Searching a billion vectors without comparing to a billion vectors.** Approximate nearest-neighbour
indexes such as FAISS's IVF build their speed on k-means. The index clusters the corpus once into
`nlist` cells, stores each vector under its nearest centroid, and at query time compares the query
only against the `nprobe` nearest centroids' contents. With 4,096 cells and `nprobe` set to 16, a
search touches 16/4096 — one 256th — of the database, and the recall you lose is the recall of
answers that happened to fall in an unvisited cell. Every [vector search](https://howaiworks.ai/glossary/vector-search)
and [semantic search](https://howaiworks.ai/glossary/semantic-search) system at scale contains a clustering step of this
kind, and the knob trading latency against recall is a clustering parameter.

**Colour quantisation.** Reducing a 24-bit image, which can address 2²⁴ = 16,777,216 distinct
colours, to a 256-entry palette for GIF or PNG-8 is k-means in three-dimensional RGB space with
k=256. Storage drops from 3 bytes per pixel to 1 byte plus a fixed 768-byte palette, a threefold
reduction, and the visible quality of the result is exactly the quality of the clustering.

**Codebooks inside neural audio codecs.** Vector-quantised models — VQ-VAE, and the residual
vector quantisation used by SoundStream and EnCodec in [audio processing](https://howaiworks.ai/glossary/audio-processing)
— represent a continuous [embedding](https://howaiworks.ai/glossary/embedding) by the index of the nearest entry in a
learned codebook. Those codebooks are initialised and maintained by k-means over the encoder's own
activations, which is what turns a continuous signal into the discrete tokens a language model can
consume.

**Deduplicating training corpora.** Web-scale text collections are full of near-duplicates, and
removing them measurably improves the models trained on them. The standard pipeline hashes each
document with MinHash, buckets the hashes with locality-sensitive hashing, and clusters the
collisions into groups of near-identical documents, keeping one survivor per group — the only
affordable way to ask which of a billion documents are the same document.

## Key Concepts

- **Adjusted Rand index needs labels you usually do not have**: it compares a clustering against a
  known truth, corrected so that random agreement scores 0. Useful for benchmarking algorithms on
  data where the answer is known, useless on the data you actually care about.
- **`eps` is a distance, so it is scale-dependent too**: DBSCAN's radius has units. Rescale the
  features and every previously tuned `eps` is wrong.
- **Soft assignment carries information hard assignment destroys**: a point at 51%/49% between two
  Gaussian components and a point at 99%/1% get the same label from k-means and different, more
  honest, answers from a mixture model.

## Challenges

**There is no held-out test set.** Every other part of supervised
[machine learning](https://howaiworks.ai/glossary/machine-learning) rests on comparing predictions against withheld
answers, and clustering has no answers to withhold. This makes internal indices — silhouette,
Calinski-Harabasz, Davies-Bouldin — dangerously reassuring, because they measure whether the
partition is geometrically tidy, not whether the partition corresponds to anything. Run k-means on
1,000 points drawn uniformly at random from a square and the silhouette peaks at about **0.41** at
k=4: a number routinely reported as evidence of well-separated structure, produced by data
containing none at all. The algorithm did what it was asked. It divided a square into four boxes.

**Stability is the right check, and it is necessary rather than sufficient.** The honest question is
whether the same structure reappears when the data or the seed changes: refit on bootstrap
resamples, on reshuffled input order, and from different random initialisations, then measure the
agreement between the resulting partitions. A grouping that dissolves under resampling was a
property of your sample, not your population. But the uniform-noise example fails this test too —
across 30 bootstrap resamples it reproduces its own four boxes at a mean adjusted Rand index of
**0.94**, because slicing a square into quadrants is an extremely stable thing to do. Stability
detects clusterings that are accidental; it cannot certify that clusters exist.

What remains is the external check, and it is not a metric: does the clustering change a decision?
A segmentation that produces a different email, a different intervention or a different research
priority has been validated by the only evidence available. A clustering nobody acts on has not been
validated by anything, whatever its silhouette says.

**Distances stop discriminating as dimensions grow.** In high-dimensional space the distances
between all pairs of points converge, so "nearest" loses its meaning — and every method on this page
is built on "nearest". Take 1,000 points drawn uniformly at random and measure the ratio of the
largest pairwise distance to the smallest: in 2 dimensions it is about 1,942, in 10 dimensions 9.9,
in 100 dimensions 1.69, and in 1,000 dimensions **1.19**. By then the farthest point is barely 19%
farther away than the closest one, and a clustering built on that gap is building on nothing. This
is why practitioners run PCA or UMAP before clustering, and why clustering
[embeddings](https://howaiworks.ai/glossary/embedding) — where a trained encoder has already arranged the space so that
distance means something — works better than clustering raw high-dimensional features.

**Naming a cluster is not the same as validating it.** A human reads the centroid, decides the group
means "price-sensitive weekend shoppers", and acts on that — an interpretation laid on top of an
arithmetic partition, and the step where confidence most exceeds evidence.

## Future Trends

The durable shift is that clustering has moved off raw features and onto learned representations.
Clustering documents by TF-IDF meant hand-designing what similarity meant; clustering their
[embeddings](https://howaiworks.ai/glossary/embedding) means the similarity was learned from data, so the metric problem
moved into the encoder rather than disappearing. Deep clustering pushes this further by training the
representation and the clustering jointly, shaping the space to be clusterable. The second movement
is toward fewer knobs — HDBSCAN over DBSCAN, because a global `eps` was always the wrong thing to
ask a user for — and toward constrained clustering, where a handful of must-link and cannot-link
pairs from a domain expert steer an otherwise unsupervised search. That last one is an admission
worth making explicit: a few labels resolve ambiguity that no amount of unlabeled data can.

## Code Example

The failure that matters, in nine lines. `make_circles` generates two concentric rings, so the true
answer is known; adjusted Rand index scores each algorithm against it, where 0 is chance and 1 is
perfect.

```python
from sklearn.cluster import KMeans, DBSCAN
from sklearn.datasets import make_circles
from sklearn.metrics import adjusted_rand_score

X, y = make_circles(n_samples=1000, factor=0.4, noise=0.05, random_state=0)

km = KMeans(n_clusters=2, n_init=10, random_state=0).fit(X)
db = DBSCAN(eps=0.2, min_samples=5).fit(X)

print("k-means agreement with the true rings:", round(adjusted_rand_score(y, km.labels_), 3))
print("DBSCAN  agreement with the true rings:", round(adjusted_rand_score(y, db.labels_), 3))
print("k-means within-cluster sum of squares:", round(km.inertia_, 1))
```

Output:

```
k-means agreement with the true rings: -0.001
DBSCAN  agreement with the true rings: 1.0
k-means within-cluster sum of squares: 383.9
```

k-means was given the correct k and still scored at chance, and the last line is the point: 383.9 is
the lowest within-cluster sum of squares available for k=2 on this data. k-means solved its problem
optimally. Its problem was the wrong one.

## Frequently Asked Questions

### What is the difference between clustering and classification?

Clustering is unsupervised learning that groups data without predefined labels, while classification is supervised learning that assigns data to known categories.

### How do I choose the right number of clusters?

Nothing in the data chooses it for you: k-means inertia falls all the way to zero at k = n, so minimising the objective is not a criterion. The elbow heuristic and silhouette score narrow the range, and a downstream decision — how many segments a team can actually act on — usually settles it.

### When should I use K-means vs DBSCAN?

Use K-means for spherical clusters with similar sizes, and DBSCAN for irregularly shaped clusters or when you don't know the number of clusters.

### Why did k-means split my clusters in the wrong place?

Almost always because of the distance metric, not the algorithm. Euclidean distance on unscaled features lets whichever column has the largest numeric range dominate the result, so standardise features first — and if the true groups are elongated, nested or ring-shaped, k-means cannot represent them at any k.

### How do I know the clusters are real and not an artefact?

You cannot know from an internal score alone: k-means on 1,000 points drawn uniformly at random reaches a silhouette of about 0.41 at k=4, a value often read as solid structure. Check stability under resampling and reseeding, then check whether the clusters change a decision someone makes.

### Can clustering handle categorical data?

Yes, but you need to encode categorical variables or use algorithms specifically designed for mixed data types.

### How do I evaluate clustering results?

Use metrics like silhouette score, Calinski-Harabasz index, or Davies-Bouldin index, along with domain knowledge and visualization.

## Related

### Related terms

- [Unsupervised Learning](https://howaiworks.ai/glossary/unsupervised-learning)
- [Dimensionality Reduction (DR)](https://howaiworks.ai/glossary/dimensionality-reduction)
- [Pattern Recognition (PR)](https://howaiworks.ai/glossary/pattern-recognition)
- [Anomaly Detection (AD)](https://howaiworks.ai/glossary/anomaly-detection)
- [Embedding](https://howaiworks.ai/glossary/embedding)
- [Data Analysis](https://howaiworks.ai/glossary/data-analysis)

---

Source: https://howaiworks.ai/glossary/clustering — HowAIWorks.ai