Hierarchical Clustering & DBSCAN
K-Means requires you to choose in advance and assumes spherical clusters. Hierarchical clustering builds a tree of clusters without specifying . 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?
| Method | Definition | Pros/Cons |
|---|---|---|
| Single | Min distance between any two points | Handles elongated clusters; chain effect |
| Complete | Max distance between any two points | Compact clusters; sensitive to outliers |
| Average | Mean distance between all pairs | Balanced; most commonly used |
| Ward | Minimizes within-cluster variance | Produces equally-sized clusters |
For A(1,1), B(2,2), C(8,8), D(9,9), all three linkages produce the same clusters ( and ) but at different dendrogram heights: single at 8.49, average at 9.90, complete at 11.31. Key pairwise distances: (intra-cluster, first merges); then , , — single linkage uses the minimum (8.49), complete the maximum (11.31), average the mean (). 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:
Dendrogram
A tree diagram showing the merge history. Cut the dendrogram at a height to choose the number of clusters:
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
Dendrogram
Scatter
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.
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 ; border points lie within reach of a core point; everything else is noise (label ). For the formal point-type definitions, the complete 9-point worked example classifying every point at / min_samples=3, and the k-distance elbow method for parameter selection:
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.
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 -th nearest neighbor for each point (sorted). Look for the "elbow":
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
| Algorithm | K needed? | Cluster shape | Handles noise | Scaling |
|---|---|---|---|---|
| K-Means | Yes | Spherical | No | |
| Hierarchical | No (cut dendrogram) | Varies by linkage | No | |
| DBSCAN | No | Arbitrary | Yes | w/ index (low-dim); worst case |
DBSCAN struggles with varying density
DBSCAN uses a single 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
- Using K-Means on non-spherical data: If clusters are crescent-shaped or nested, use DBSCAN or hierarchical clustering.
- Not scaling features before clustering: DBSCAN and hierarchical clustering use distance metrics. Always standardize.
- 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
epsvia the k-distance elbow; it struggles with varying densities.
Related concepts
- K-Means Clustering: the centroid-based method these contrast with
- t-SNE & UMAP: visualizing the clusters you find