Hierarchical Clustering & DBSCANOpen in Colab
ML project loop
Data·Hypothesis space·Objective·Optimization·Evaluation·Deployment feedback

Hierarchical Clustering & DBSCAN

K-Means requires you to choose KK in advance and assumes spherical clusters. Hierarchical clustering builds a tree of clusters without specifying KK. DBSCAN finds arbitrarily shaped clusters based on density.

Agglomerative hierarchical clustering

Bottom-up approach: start with each point as its own cluster, then repeatedly merge the two closest clusters.

Linkage methods

How do we measure distance between clusters?

MethodDefinitionPros/Cons
SingleMin distance between any two pointsHandles elongated clusters; chain effect
CompleteMax distance between any two pointsCompact clusters; sensitive to outliers
AverageMean distance between all pairsBalanced; most commonly used
WardMinimizes within-cluster varianceProduces equally-sized clusters

For A(1,1), B(2,2), C(8,8), D(9,9), all three linkages produce the same clusters ({A,B}\{A,B\} and {C,D}\{C,D\}) but at different dendrogram heights: single at 8.49, average at 9.90, complete at 11.31. Key pairwise distances: d(A,B)=d(C,D)=2≈1.41d(A,B)=d(C,D)=\sqrt{2}\approx1.41 (intra-cluster, first merges); then d(B,C)≈8.49d(B,C)\approx8.49, d(A,C)=d(B,D)≈9.90d(A,C)=d(B,D)\approx9.90, d(A,D)≈11.31d(A,D)\approx11.31 — single linkage uses the minimum (8.49), complete the maximum (11.31), average the mean (≈9.90\approx9.90). The structure matches because the blobs are well-separated — linkages disagree on cluster assignments only when clusters are elongated, of unequal size, or connected by bridge points. For the full pairwise distance matrix, step-by-step merge trace, Ward linkage derivation, and a comparison on crescents:

Deep dive
Hierarchical Clustering Linkage Methods
Includes runnable notebook

Dendrogram

A tree diagram showing the merge history. Cut the dendrogram at a height to choose the number of clusters:

Python
import numpy as np
from scipy.cluster.hierarchy import dendrogram, linkage
import matplotlib.pyplot as plt

X = np.array([[1,1], [2,2], [8,8], [9,9], [5,5]])

Z = linkage(X, method='ward')
plt.figure(figsize=(10, 5))
dendrogram(Z, labels=['A','B','C','D','E'])
plt.title('Dendrogram (Ward linkage)')
plt.xlabel('Points')
plt.ylabel('Distance')
plt.show()

Choosing the number of clusters

Look for the longest vertical line in the dendrogram that doesn't cross any horizontal merge line. Cut there. This gives the natural number of clusters.

Hierarchical Clustering — Dendrogram

Linkage:

Dendrogram

024477195distance57826413

Scatter

12345678
linkagesingle
cut height0.0
clusters8

Left: dendrogram tree — horizontal lines are merge events, height = distance. Drag the cut-height slider to slice the tree and reveal clusters. Right: scatter plot colored by resulting cluster assignment.

Python
from sklearn.cluster import AgglomerativeClustering

# Cut at 2 clusters
agg = AgglomerativeClustering(n_clusters=2, linkage='ward')
labels = agg.fit_predict(X)
print(f"Labels: {labels}")  # [0, 0, 1, 1, 0]

DBSCAN (Density-Based Spatial Clustering)

DBSCAN finds clusters of arbitrary shape based on density — regions where points are closely packed. A core point has at least min_samples neighbors within radius ε\varepsilon; border points lie within reach of a core point; everything else is noise (label −1-1). For the formal point-type definitions, the complete 9-point worked example classifying every point at ε=2\varepsilon=2 / min_samples=3, and the k-distance elbow method for parameter selection:

Deep dive
DBSCAN: Core, Border, Noise Classification
Includes runnable notebook

Why DBSCAN is powerful

Unlike K-Means, DBSCAN can find clusters of any shape (crescents, rings, blobs). It automatically detects outliers as noise points and doesn't require specifying the number of clusters.

Python
from sklearn.cluster import DBSCAN

X = np.array([[1,1], [1,2], [2,1], [2,2], [8,8], [8,9], [9,8], [9,9], [5,5]])

db = DBSCAN(eps=2, min_samples=3)
labels = db.fit_predict(X)
print(f"Labels: {labels}")  # [0, 0, 0, 0, 1, 1, 1, 1, -1]
# -1 = noise point

Choosing DBSCAN parameters

eps estimation

Use the k-distance graph: plot the distance to the kk-th nearest neighbor for each point (sorted). Look for the "elbow":

Python
from sklearn.neighbors import NearestNeighbors

nn = NearestNeighbors(n_neighbors=3)
nn.fit(X)
distances, _ = nn.kneighbors(X)
k_distances = np.sort(distances[:, -1])

plt.figure(figsize=(8, 5))
plt.plot(k_distances)
plt.xlabel('Points (sorted)')
plt.ylabel('3rd nearest neighbor distance')
plt.title('k-Distance Graph — choose eps at the elbow')
plt.grid(True, alpha=0.3)
plt.show()

min_samples rule of thumb

  • min_samples ≥ dimension + 1 (at least 3 for 2D data)
  • min_samples ≥ 2 × dimension for larger datasets
  • Larger values → more conservative clustering, fewer noise points

Comparison

AlgorithmK needed?Cluster shapeHandles noiseScaling
K-MeansYesSphericalNoO(nKd)O(nKd)
HierarchicalNo (cut dendrogram)Varies by linkageNoO(n2d)O(n^2 d)
DBSCANNoArbitraryYesO(nlog⁡n)O(n \log n) w/ index (low-dim); O(n2)O(n^2) worst case

DBSCAN struggles with varying density

DBSCAN uses a single ε\varepsilon for all clusters. If clusters have very different densities, DBSCAN will either merge dense clusters or fragment sparse ones. Consider HDBSCAN for varying densities.

Exercise

What does the 'eps' parameter in DBSCAN control?

Need a hint?

It defines a neighborhood around each point.

Exercise

In hierarchical clustering, which linkage method is most sensitive to outliers?

Need a hint?

Think about which method uses the maximum distance.

Exercise

How do you choose the eps parameter for DBSCAN?

Need a hint?

Use a k-distance graph.

Common mistakes

  1. Using K-Means on non-spherical data: If clusters are crescent-shaped or nested, use DBSCAN or hierarchical clustering.
  2. Not scaling features before clustering: DBSCAN and hierarchical clustering use distance metrics. Always standardize.
  3. Setting eps too small/large: Too small → everything is noise. Too large → everything merges into one cluster. Use the k-distance graph.

Key takeaways

  • Hierarchical clustering builds a dendrogram; cut it for any K — no K upfront.
  • Linkage (single/complete/average/ward) changes cluster shape.
  • DBSCAN finds arbitrary shapes by density and labels sparse points as noise.
  • Tune DBSCAN's eps via the k-distance elbow; it struggles with varying densities.

Related concepts

Concept neighbourhood

How this concept connects — click any node to jump there, or explore the whole concept map.

Builds onRelatedGo deeper
Hierarchical Clustering & DBSCANLinear & Logistic Regress…K-Means Clusteringt-SNE & UMAPEvaluating Clusters & Cho…Anomaly & Outlier Detecti…Hierarchical Clustering L…DBSCAN: Core, Border, Noi…K-Means: Full Algorithm