Hierarchical clustering and DBSCAN

The big idea

k-means asks you for k up front and assumes round clusters. Two other families drop those demands.

Hierarchical clusteringClustering that builds a nested hierarchy of clusters, usually bottom-up by repeatedly merging the two closest clusters, displayed as a dendrogram. works like a family tree in reverse. Start with every point as its own family, then repeatedly marry the two closest families until everyone is one clan. The record of all the marriages is a tree, and you choose the number of clusters afterwards by deciding how far back in history to look.

DBSCANDensity-Based Spatial Clustering of Applications with Noise: groups points that have many neighbours within a radius eps, and labels isolated points as noise. works like spotting crowds from a helicopter. Wherever people stand densely packed, that is a crowd, whatever its shape. Lone walkers between crowds belong to none of them: they are noise. You never say how many crowds to find.

How it works

Step 1: Agglomerative clustering merges the closest pair

Agglomerative clusteringBottom-up hierarchical clustering: every point starts as its own cluster and the two closest clusters are merged at each step. starts with n clusters of one point. At each step it merges the two closest clusters, until one remains. On six points on a line at 0, 1, 1.5, 5, 6 and 9, using the shortest distance between clusters, the merges happen at heights 0.5 (1 and 1.5), 1.0 (0 joins them), 1.0 (5 and 6), 3.0 (9 joins 5 and 6) and 3.5 (everything).

Step 2: Read the dendrogram and cut it

A dendrogramA tree diagram of hierarchical clustering. Leaves are data points; the height of each join is the distance at which two clusters were merged. shows each merge as a join at the height where it happened. Long vertical lines mean a cluster stayed separate for a long distance: a natural group. Cutting the tree at a height gives clusters; cutting where the vertical lines are longest gives the most natural split. One fit gives you every possible number of clusters.

Step 3: Choose a linkage

"Distance between two clusters" has several definitions, called linkageThe rule for measuring distance between clusters in hierarchical clustering: single (closest pair), complete (farthest pair), average (mean pairwise) or Ward (increase in within-cluster variance).:

• Single: distance between the closest pair of points. Follows chains and odd shapes, but one bridge of points can merge two groups (chaining).
• Complete: distance between the farthest pair. Compact clusters, sensitive to outliers.
• Average: mean distance over all pairs. A compromise.
• Ward: merge the pair that increases total within-cluster variance least. Similar to k-means in spirit; a good default for round clusters.

In the code, Ward scores 0.869 on three blobs but 0.241 on two moons; single linkage scores 1.000 on the moons and only 0.560 on the blobs. The right linkage depends on the shapes you expect.

Hierarchical clustering needs all pairwise distances, which costs order n^2 memory and at least n^2 time, so it suits thousands of points, not millions.

Step 4: DBSCAN grows clusters from dense points

DBSCAN has two parameters: a radius epsIn DBSCAN, the radius of the neighbourhood around each point. and a count minPts. It labels every point as one of three kinds:

• A core pointIn DBSCAN, a point with at least minPts points (itself included) within distance eps. has at least minPts points within distance eps.
• A border point is within eps of a core point but is not core itself.
• A noise point is neither. It gets no cluster (label -1 in scikit-learn).

Clusters grow by linking core points that are within eps of each other, like a chain of people within arm's reach, and then adding their border points. The shape can be anything, the number of clusters comes out of the data, and outliers are flagged instead of forced into a cluster.

Step 5: Choose eps and minPts

minPts is often set to about twice the number of features, or at least 4 or 5. For eps, plot each point's distance to its k-th nearest neighbour (k = minPts), sorted: the "knee" where distances shoot up separates dense points from sparse ones. In the code, on two moons with 20 noise points, eps = 0.05 shatters the data into 13 clusters with 243 noise points, eps = 0.15 finds exactly 2 clusters and 16 noise points (perfect agreement on the moons), and eps = 0.3 merges everything into one cluster.

Try it

Try this:

1. Start at eps 0.45, minPts 5. Lower eps step by step. When do the moons start breaking into fragments, and when do most points become noise?
2. Raise eps until the two moons merge into one cluster. Which points bridge them?
3. At eps 0.45, raise minPts to 12. Which points turn from core to border or noise first?

Going deeper

Code: merges, linkages and DBSCAN settings

import numpy as np
from scipy.cluster.hierarchy import fcluster, linkage
from sklearn.cluster import DBSCAN, AgglomerativeClustering
from sklearn.datasets import make_blobs, make_moons
from sklearn.metrics import adjusted_rand_score

# A tiny example: 6 points on a line, merged bottom-up
pts = np.array([[0.0], [1.0], [1.5], [5.0], [6.0], [9.0]])
Z = linkage(pts, method="single")
print("merge  clusters joined  height")
for i, (a, b, h, size) in enumerate(Z, 1):
    print(f"{i:>5}  {int(a):>3} + {int(b):<3}      {h:.1f}   (new cluster {5 + i}, size {int(size)})")
print("cut at height 2.0 ->", fcluster(Z, t=2.0, criterion="distance"))

# Linkage choice matters: blobs vs moons
datasets = {"3 blobs": make_blobs(300, centers=3, cluster_std=1.0, random_state=2),
            "2 moons": make_moons(300, noise=0.05, random_state=0)}
print("\nlinkage    3 blobs ARI   2 moons ARI")
for link in ["single", "complete", "average", "ward"]:
    s = [adjusted_rand_score(y, AgglomerativeClustering(len(set(y)), linkage=link).fit_predict(X))
         for X, y in datasets.values()]
    print(f"{link:<9}   {s[0]:.3f}         {s[1]:.3f}")

# DBSCAN: moons plus 20 scattered noise points
X, y = make_moons(300, noise=0.05, random_state=0)
rng = np.random.default_rng(0)
X = np.vstack([X, rng.uniform([-1.5, -1], [2.5, 1.5], (20, 2))])
print("\neps    minPts  clusters  noise points")
for eps, mp in [(0.05, 5), (0.15, 5), (0.3, 5), (0.6, 5), (0.15, 15)]:
    lab = DBSCAN(eps=eps, min_samples=mp).fit_predict(X)
    print(f"{eps:<5}  {mp:>6}  {len(set(lab) - {-1}):>8}  {np.sum(lab == -1):>12}")
lab = DBSCAN(eps=0.15, min_samples=5).fit_predict(X)
print(f"eps 0.15: ARI on the 300 moon points {adjusted_rand_score(y, lab[:300]):.3f}")

merge  clusters joined  height
    1    1 + 2        0.5   (new cluster 6, size 2)
    2    0 + 6        1.0   (new cluster 7, size 3)
    3    3 + 4        1.0   (new cluster 8, size 2)
    4    5 + 8        3.0   (new cluster 9, size 3)
    5    7 + 9        3.5   (new cluster 10, size 6)
cut at height 2.0 -> [1 1 1 2 2 3]

linkage    3 blobs ARI   2 moons ARI
single      0.560         1.000
complete    0.844         0.297
average     0.560         0.425
ward        0.869         0.241

eps    minPts  clusters  noise points
0.05        5        13           243
0.15        5         2            16
0.3         5         1             9
0.6         5         1             5
0.15       15        11           104
eps 0.15: ARI on the 300 moon points 1.000

Where DBSCAN struggles

A single eps assumes all clusters have similar density. A dense cluster next to a sparse one forces a choice: an eps small enough to separate the dense cluster turns the sparse one into noise. HDBSCANHierarchical DBSCAN: runs DBSCAN over all eps values and keeps the most stable clusters, handling clusters of different densities. fixes this by effectively trying every eps and keeping the clusters that persist longest; it is available in scikit-learn and is often the better default. DBSCAN also suffers in high dimensions, where distances concentrate and "dense" loses meaning; reduce dimensions first ( Principal Component Analysis ).

Trade-offs

Common mistakes

• Running hierarchical clustering on hundreds of thousands of points and running out of memory.
• Using the default Ward linkage on data with chained or crescent-shaped clusters.
• Picking eps by trial and error on a plot without checking the k-distance curve.
• Forgetting to scale features; DBSCAN's eps is a distance in the raw units.
• Treating DBSCAN's noise points as errors to discard without looking at them; they are often the interesting cases.

In the wild

Hierarchical clustering is standard in biology, where dendrograms of gene expression or species similarity are read directly, and in organizing documents or products into nested categories. DBSCAN and HDBSCAN are popular for geographic data (finding hotspots of GPS pings or incidents of any shape), for grouping embeddings in topic discovery, and for spotting outliers in sensor data, because they do not require k and they set noise aside.

Check yourself

Recap