Hierarchical & DBSCAN Clustering

Plot the GPS coordinates of every reported burglary in a city over six months. The points are not scattered evenly. They form dense knots along certain streets, thin trails connecting them, and a scatter of isolated incidents in the suburbs. You want to find the hotspots.

Ask k-means for six clusters and it will give you six. But every point gets assigned to one, including the isolated suburban incidents that belong to nothing. The hotspots along a curved high street get chopped in half, because k-means draws straight boundaries between centres. And the number six was your guess — the data may contain eleven hotspots, or three.

The problem is that k-means answers a specific question: given that there are exactly k round groups covering all the data, where are they? Sometimes that is the right question. For hotspots it is the wrong one on all three counts — you do not know the number, the shapes are not round, and not every point belongs to a group.

Two families of algorithms drop different parts of those assumptions.

Hierarchical clustering: build the whole tree, decide later

Instead of committing to a number of clusters, build every possible number at once.

The bottom-up (agglomerative) version:

1. Start with every point as its own cluster. With 200 points you have 200 clusters.
2. Find the two closest clusters and merge them. Now 199.
3. Repeat until everything is in one cluster.

Record every merge and you get a dendrogram — a tree whose leaves are individual points and whose height at each junction is the distance at which those two groups joined.

distance   | 12|                    ┌──────────────┐   |                    │              │  8|              ┌─────┴───┐          │   |              │         │          │  4|          ┌───┴──┐   ┌──┴──┐    ┌──┴──┐   |          │      │   │     │    │     │  0|   ───────A──────B───C─────D────E─────F───                cut here (dist 6) -> 3 clusters: {A,B} {C,D} {E,F}                cut here (dist 10) -> 2 clusters: {A,B,C,D} {E,F}

The dendrogram contains every clustering from 1 to n. You choose $k$ afterwards by drawing a horizontal line and counting the vertical lines it crosses — which is a genuinely different workflow from k-means, where changing $k$ means refitting.

Linkage: distance between clusters, not points

Step 2 says "find the two closest clusters", which requires deciding what distance between two groups means. This choice changes the results more than anything else.

Suppose cluster P = {(0,0), (1,0)} and cluster Q = {(4,0), (9,0)}. The pairwise distances are 4, 9, 3, and 8.

Ward linkage is different in kind. Rather than measuring a distance, it asks: of all available merges, which one increases total within-cluster sum of squares the least? That is the same objective k-means minimises, approached from the bottom up, and it is why Ward tends to give compact, similar-sized clusters. It requires Euclidean distance; the others accept any metric.

The chaining problem

Single linkage merges on the closest pair, so a thin bridge of intermediate points can fuse two obviously separate groups. Two dense blobs 20 units apart, with a line of stragglers spaced 2 units apart running between them, will merge into one cluster — every merge along the chain is a small step, and the algorithm never notices it has walked across the gap.

This is sometimes exactly what you want, since it lets single linkage discover elongated shapes no other linkage finds. More often it is a failure mode, and it is the main reason Ward or average linkage are the safer defaults.

1import scipy.cluster.hierarchy as sch2from sklearn.preprocessing import StandardScaler3from sklearn.cluster import AgglomerativeClustering4import matplotlib.pyplot as plt56X_scaled = StandardScaler().fit_transform(X)78linkage = sch.linkage(X_scaled, method="ward")9sch.dendrogram(linkage, truncate_mode="lastp", p=30)   # last 30 merges only10plt.ylabel("merge distance")1112# then cut the tree13model = AgglomerativeClustering(n_clusters=4, linkage="ward")14labels = model.fit_predict(X_scaled)

truncate_mode="lastp" matters in practice. A dendrogram of 5,000 points is an unreadable black smear at the bottom; showing only the final merges gives you the part that carries the decision.

Reading the tree for k

Look for the longest vertical stretch that no horizontal line crosses. A long gap means those clusters stayed separate over a wide range of distances — they are robustly distinct. Cutting in the middle of that gap gives a stable clustering. If merge heights rise smoothly with no notable gap, the data has no strong hierarchy and any cut is arbitrary.

The cost

Agglomerative clustering computes and maintains distances between all pairs: $O(n^2)$ memory and typically $O(n^2 \log n)$ time. At 10,000 points the distance matrix holds 50 million entries — workable. At 100,000 points it is 5 billion, roughly 40 GB, and the approach is simply unavailable. Hierarchical clustering is for datasets up to a few tens of thousands of rows.

Hierarchical clustering does not ask you for k. It asks you for a notion of distance between groups, and then shows you every possible k so that you can choose with the structure in front of you.

DBSCAN: clusters are dense regions, everything else is noise

DBSCAN drops a different assumption. It does not partition the data at all. Some points belong to clusters; some are labelled noise and belong to nothing.

Two parameters:

• eps ($\varepsilon$) — the radius defining "nearby".
• min_samples — how many points must be within that radius for a region to count as dense.

Every point is then one of three kinds:

The algorithm picks an unvisited core point, claims everything within eps, then repeats from each newly claimed core point, spreading outward until the density runs out. Then it starts a new cluster elsewhere.

Because clusters grow by spreading through dense regions rather than radiating from a centre, they can be any shape at all — crescents, rings, long winding streets. The burglary hotspot along a curved high street is exactly what DBSCAN is good at.

A concrete count

With eps=1.5 and min_samples=4, take a point that has 6 neighbours within 1.5 units: it is a core point. A point on the edge with 2 neighbours, one of which is that core point: it is a border point, joins the cluster, but the search stops there. A point with 0 neighbours within 1.5 units: noise.

Change min_samples to 8 and the first point (6 neighbours) is no longer core. If nothing else nearby qualifies either, an entire cluster of 30 points becomes noise. DBSCAN is sensitive to these parameters in a way that is not gradual — small changes can restructure the result completely.

Choosing eps without guessing

There is a standard method. For every point, compute the distance to its $k$-th nearest neighbour (with $k$ = min_samples), sort those distances, and plot them. Points inside clusters have small $k$-th-neighbour distances; noise points have large ones. The plot therefore stays flat and then bends sharply upward, and the distance at the bend is a good eps.

1import numpy as np2from sklearn.neighbors import NearestNeighbors3import matplotlib.pyplot as plt45min_samples = 86nn = NearestNeighbors(n_neighbors=min_samples).fit(X_scaled)7distances, _ = nn.kneighbors(X_scaled)8kth = np.sort(distances[:, -1])910plt.plot(kth)11plt.ylabel(f"distance to {min_samples}th nearest neighbour")12plt.xlabel("points, sorted")13# eps = the y-value at the knee

For min_samples, a common starting rule is twice the number of dimensions, raised if the data is noisy. Higher values produce fewer, denser clusters and more noise.

1from sklearn.cluster import DBSCAN23db = DBSCAN(eps=0.6, min_samples=8).fit(X_scaled)4labels = db.labels_56n_clusters = len(set(labels)) - (1 if -1 in labels else 0)7n_noise = (labels == -1).sum()8print(f"{n_clusters} clusters, {n_noise} noise points "9      f"({n_noise / len(labels):.1%})")

Always print the noise fraction. If 70% of your data is noise, eps is too small. If 0% is, it is probably too large and DBSCAN has degenerated into "one big cluster".

Where DBSCAN breaks

Varying density. This is the fundamental limitation. A single eps defines a single density threshold for the whole dataset. If your data has one tight cluster and one diffuse one, no single value works: an eps small enough to separate the tight cluster from its neighbours will shatter the diffuse cluster into noise, and one large enough to hold the diffuse cluster together will merge the tight ones.

HDBSCAN is the standard answer — it runs DBSCAN across all density thresholds and extracts the clusters that persist longest, which removes eps from your responsibilities entirely and handles mixed densities well. It is available as sklearn.cluster.HDBSCAN in recent versions.

High dimensions. DBSCAN depends on distance, and in high dimensions distances between all pairs of points converge towards each other. Beyond roughly 10–15 features, "within eps" stops distinguishing anything useful and DBSCAN either finds one cluster or all noise. Reduce dimensionality first.

Border-point ambiguity. A border point reachable from two clusters is assigned to whichever was processed first, so results can differ slightly with row order. Minor, but worth knowing if you need exact reproducibility.

Choosing between the three

The "assigns new points" row has real operational consequences. K-means produces centroids, so classifying tomorrow's customer is a distance calculation. Hierarchical clustering and DBSCAN produce no such artefact — a new point requires rerunning the whole algorithm, or training a separate classifier on the cluster labels to serve as a predictor.

A practical decision path

1. Do you need to assign new points cheaply, forever? K-means, or fit a classifier on top of whatever labels you produce.
2. Are there outliers that genuinely belong to nothing? DBSCAN or HDBSCAN. Forcing anomalies into clusters distorts every cluster they land in.
3. Are the shapes non-convex — curves, rings, streets? DBSCAN.
4. Do you want to see structure at multiple levels of granularity? Hierarchical. Retail category trees and taxonomies are natural fits.
5. Millions of rows? MiniBatchKMeans; the others will not finish.
6. No idea? Run all three, compare silhouette scores, and — more importantly — look at the cluster profiles and see which set a domain expert recognises.

All three on the same data

1import pandas as pd2import numpy as np3from sklearn.preprocessing import StandardScaler4from sklearn.cluster import KMeans, AgglomerativeClustering, DBSCAN5from sklearn.metrics import silhouette_score67X_scaled = StandardScaler().fit_transform(df[features])89runs = {10    "kmeans-4": KMeans(n_clusters=4, n_init=10, random_state=42),11    "ward-4":   AgglomerativeClustering(n_clusters=4, linkage="ward"),12    "dbscan":   DBSCAN(eps=0.6, min_samples=8),13}1415for name, algo in runs.items():16    labels = algo.fit_predict(X_scaled)17    mask = labels != -1                     # exclude noise from the score18    n_clusters = len(set(labels[mask]))19    if n_clusters > 1:20        sil = silhouette_score(X_scaled[mask], labels[mask])21    else:22        sil = float("nan")23    print(f"{name:10s} clusters={n_clusters}  "24          f"noise={(~mask).sum():5d}  silhouette={sil:.3f}")

The mask line is not optional. Passing DBSCAN's −1 labels straight into silhouette_score treats "noise" as a cluster, which it is not — noise points are scattered everywhere, so their internal cohesion is terrible and the score is dragged down for a reason that has nothing to do with cluster quality.

A representative result on customer data with a few genuine outliers:

DBSCAN's higher silhouette here is partly earned and partly definitional — removing 412 awkward points from the evaluation makes the rest look tidier. The honest question is whether those 412 are noise you should exclude or a genuine fourth segment you have just deleted. Look at them before deciding: if they share a coherent profile, they are a small cluster DBSCAN's density threshold missed, not noise.

What this means when you build something

Pick the algorithm by the shape of your question rather than by which one is fashionable.

If you need a fixed number of groups you will act on repeatedly, and new customers must be assignable tomorrow without retraining, k-means is the operationally correct choice even when another method scores better, because centroids are a deployable artefact and a dendrogram is not.

If your data contains points that genuinely belong to nothing — fraud, sensor faults, one-off events — use DBSCAN or HDBSCAN, and treat the noise label as a result rather than a failure. Being told "these 412 rows do not fit any pattern" is often more valuable than being told which arbitrary group they were forced into.

And whatever you run, look at the noise fraction, the cluster sizes, and the silhouette before you look at the cluster profiles. A method that returns one cluster containing 97% of the data and six containing four points each has not found structure; it has found a parameter setting. Adjusting that setting before you start writing up the segments will save you from a very confident presentation of nothing.