🎯 What You'll Learn
- Build a dendrogram with agglomerative clustering and understand how to read it to choose the number of clusters
- Understand the four linkage criteria (single, complete, average, Ward) and when each is appropriate
- Implement hierarchical clustering with both scikit-learn and SciPy
- Master DBSCAN's core/border/noise point model and the two parameters
epsandmin_samples - Compare K-Means, hierarchical clustering, and DBSCAN on non-convex datasets to choose the right algorithm for each problem
1 Hierarchical Clustering: The Idea
K-Means partitions data into exactly K flat clusters. Hierarchical clustering builds a tree of clusters — called a dendrogram — that captures the nested structure of data at multiple scales. This is powerful: you don't commit to a specific K upfront. Instead, you build the full tree and cut it at the level that makes sense for your problem.
There are two philosophies:
- Agglomerative (bottom-up): Start with every single data point as its own cluster (n clusters). At each step, merge the two closest clusters. Repeat until everything is one big cluster. This is by far the most common approach.
- Divisive (top-down): Start with all points in one cluster and recursively split it. Computationally expensive and rarely used in practice.
The agglomerative approach runs in O(n² log n) time — much slower than K-Means O(nKt) for large datasets. But for small-to-medium datasets (n < 10,000), it provides rich information about cluster structure that K-Means cannot.
import numpy as np
from sklearn.datasets import make_blobs
# Dataset for illustration
X, _ = make_blobs(n_samples=15, centers=3, cluster_std=0.5, random_state=42)
print(f"Dataset: {X.shape[0]} points in 2D")
# Agglomerative clustering with sklearn — directly gives labels
from sklearn.cluster import AgglomerativeClustering
agg = AgglomerativeClustering(n_clusters=3, linkage='ward')
labels = agg.fit_predict(X)
print(f"Cluster labels: {labels}")
print(f"Cluster sizes: {np.bincount(labels)}")
# Unlike K-Means, there is no .predict() method — agglomerative
# clustering must be refit to include new pointsIn biology, species form families → orders → classes → phyla. In retail, products cluster into SKUs → categories → departments. In text analysis, words cluster into topics → themes → domains. K-Means flattens this hierarchy into a single level. Agglomerative clustering captures the full multilevel structure and lets you decide at which level to "cut."
2 Linkage Criteria: How to Measure Distance Between Clusters
At each step of agglomerative clustering, we need to merge the "closest" pair of clusters. But how do you define the distance between two groups of points? The choice of linkage criterion dramatically affects the resulting dendrogram.
| Linkage | Distance definition | Tends to produce | Use when |
|---|---|---|---|
| Single | Min distance between any two points (one from each cluster) | Long chain-like clusters; susceptible to "chaining" | Non-ellipsoidal, connected clusters |
| Complete | Max distance between any two points (furthest pair) | Compact, roughly equal-sized clusters | When cluster diameter should be minimized |
| Average | Mean of all pairwise distances between clusters | Compromise between single and complete | General purpose, moderate noise tolerance |
| Ward ⭐ | Increase in total within-cluster variance after merge | Compact, well-separated, similar-sized clusters | Default choice — best overall performance |
import numpy as np
from sklearn.cluster import AgglomerativeClustering
from sklearn.datasets import make_blobs
from sklearn.metrics import silhouette_score
X, y_true = make_blobs(n_samples=300, centers=4, cluster_std=0.9, random_state=42)
print(f"{'Linkage':>10} {'Silhouette':>12} {'Description':>30}")
print("-" * 60)
for linkage in ['ward', 'average', 'complete', 'single']:
agg = AgglomerativeClustering(n_clusters=4, linkage=linkage)
labels = agg.fit_predict(X)
sil = silhouette_score(X, labels)
desc = {
'ward': 'Minimises within-cluster variance',
'average': 'Average pairwise distances',
'complete': 'Maximises inter-cluster diameter',
'single': 'Minimum distance (chaining risk)',
}
print(f"{linkage:>10} {sil:>12.4f} {desc[linkage]:>30}")
# Ward typically achieves the best silhouette on well-structured data3 Reading the Dendrogram
The dendrogram is a binary tree diagram that shows the full merge history. Each leaf is a data point (or small cluster). Moving up the tree, leaves merge into clusters. The height of a merge represents the distance (or variance increase, for Ward) at which the two sub-clusters were joined — higher merges mean less similar clusters being combined.
To decide on K clusters from the dendrogram: draw a horizontal line across it. The number of vertical lines the horizontal cut crosses equals the number of clusters. A natural choice is to cut where the vertical "gaps" (distances between merge heights) are largest — long vertical lines before the cut indicate that you're merging quite dissimilar clusters, suggesting the data has a natural break there.
Drag the slider below to slide the "cut line" up and down a dendrogram built from 7 sample points. Watch the cluster count update live — this is exactly the visual process described above, just made interactive:
Cut height = 0.00 — every point is its own cluster (7 clusters).
import numpy as np
import matplotlib.pyplot as plt
from scipy.cluster.hierarchy import dendrogram, linkage, fcluster
from sklearn.datasets import make_blobs
from sklearn.preprocessing import StandardScaler
# Generate data with 4 natural clusters
X, y_true = make_blobs(n_samples=80, centers=4, cluster_std=0.7, random_state=42)
X_scaled = StandardScaler().fit_transform(X)
# ── Build the linkage matrix (SciPy format) ──
# linkage() returns an (n-1) x 4 matrix:
# [cluster_a, cluster_b, distance, n_merged_points]
Z = linkage(X_scaled, method='ward')
print(f"Linkage matrix shape: {Z.shape}") # (79, 4) for 80 points
print(f"First few merges (closest pairs):")
for i in range(5):
print(f" Merge {i+1}: clusters {int(Z[i,0])} + {int(Z[i,1])} "
f"at distance {Z[i,2]:.4f} → {int(Z[i,3])} points")
# ── Plot the dendrogram ──
plt.figure(figsize=(14, 6))
dendrogram(
Z,
leaf_rotation=90,
leaf_font_size=8,
color_threshold=Z[-4, 2], # color groups at 4-cluster level
above_threshold_color='gray'
)
plt.axhline(y=Z[-4, 2] * 1.01, color='red', linestyle='--',
alpha=0.7, label='Cut for K=4')
plt.xlabel('Sample Index')
plt.ylabel('Ward Distance (variance increase)')
plt.title('Dendrogram — Agglomerative Clustering (Ward Linkage)')
plt.legend()
plt.tight_layout()
plt.savefig('dendrogram.png', dpi=150)
# ── Extract cluster labels at a specific cut ──
# Option 1: specify number of clusters directly
labels_k4 = fcluster(Z, t=4, criterion='maxclust') # K=4
# Option 2: cut at a distance threshold
labels_dist = fcluster(Z, t=Z[-4, 2] * 1.01, criterion='distance')
print(f"\nK=4 labels (fcluster): {np.bincount(labels_k4 - 1)}") # fcluster is 1-indexed
print(f"Same via distance cut: {np.bincount(labels_dist - 1)}")
# ── Finding the largest "gap" (elbow in dendrogram heights) ──
merge_distances = Z[:, 2]
gaps = np.diff(merge_distances)
# The largest gap suggests where to cut
cut_idx = np.argmax(gaps[-10:]) # look at last 10 merges (top of tree)
print(f"\nLargest gap in top-10 merges suggests K = {10 - cut_idx}")Use SciPy (linkage + dendrogram) when you want to visualize the dendrogram and interactively explore cut heights. Use scikit-learn (AgglomerativeClustering) when you want cluster labels to plug into a Pipeline or combine with other sklearn tools. They use the same underlying algorithms and produce identical cluster assignments for the same parameters.
4 Full Hierarchical Clustering Implementation
import numpy as np
import matplotlib.pyplot as plt
from sklearn.cluster import AgglomerativeClustering
from sklearn.preprocessing import StandardScaler
from sklearn.metrics import silhouette_score
from scipy.cluster.hierarchy import dendrogram, linkage
from sklearn.datasets import load_iris
# Use Iris dataset — known to have 3 species (natural clusters)
iris_data = __import__('sklearn.datasets', fromlist=['load_iris']).load_iris()
X_iris = iris_data.data
y_iris = iris_data.target
feature_names = iris_data.feature_names
# Scale
scaler = StandardScaler()
X_iris_sc = scaler.fit_transform(X_iris)
# ── 1. Plot the dendrogram to choose K ──
Z_iris = linkage(X_iris_sc, method='ward')
plt.figure(figsize=(16, 6))
dendrogram(Z_iris, leaf_rotation=90, leaf_font_size=6,
color_threshold=Z_iris[-3, 2])
plt.axhline(y=Z_iris[-3, 2] * 1.01, color='red', linestyle='--', label='K=3 cut')
plt.title('Iris Dendrogram (Ward Linkage) — Cut Suggests K=3')
plt.ylabel('Ward Distance')
plt.legend()
plt.tight_layout()
plt.savefig('iris_dendrogram.png', dpi=150)
# ── 2. Fit with sklearn for labels + evaluation ──
agg_iris = AgglomerativeClustering(n_clusters=3, linkage='ward')
labels_iris = agg_iris.fit_predict(X_iris_sc)
print("=== Hierarchical Clustering on Iris ===")
print(f"Cluster sizes: {np.bincount(labels_iris)}")
print(f"Silhouette score: {silhouette_score(X_iris_sc, labels_iris):.4f}")
# Compare to true labels (note: cluster numbers may not match species numbers)
from sklearn.metrics import adjusted_rand_score, normalized_mutual_info_score
print(f"Adjusted Rand Index: {adjusted_rand_score(y_iris, labels_iris):.4f}")
print(f"NMI: {normalized_mutual_info_score(y_iris, labels_iris):.4f}")
# ── 3. Try different n_clusters ──
print("\nSilhouette score by K:")
for k in range(2, 8):
agg_k = AgglomerativeClustering(n_clusters=k, linkage='ward')
lbl = agg_k.fit_predict(X_iris_sc)
print(f" K={k}: {silhouette_score(X_iris_sc, lbl):.4f}")
# ── 4. Connectivity constraints (optional) ──
# You can add a connectivity matrix to enforce that only
# spatially adjacent points merge — useful for image segmentation
from sklearn.neighbors import kneighbors_graph
connectivity = kneighbors_graph(X_iris_sc, n_neighbors=10, include_self=False)
agg_conn = AgglomerativeClustering(n_clusters=3, linkage='ward', connectivity=connectivity)
labels_conn = agg_conn.fit_predict(X_iris_sc)
print(f"\nWith connectivity constraint: Silhouette = {silhouette_score(X_iris_sc, labels_conn):.4f}")5 DBSCAN: Density-Based Clustering
DBSCAN (Density-Based Spatial Clustering of Applications with Noise) takes a completely different approach to clustering. Instead of minimizing distances to centroids or building merge trees, DBSCAN defines clusters as dense regions of points separated by sparse regions.
DBSCAN classifies every point into one of three types:
- Core point: A point that has at least
min_samplespoints (including itself) within radiuseps. Core points are the "dense" backbone of a cluster. - Border point: A point that is within
epsof a core point but does not itself have enough neighbors to be a core point. Border points belong to a cluster but cannot extend it. - Noise point (outlier): A point that is not within
epsof any core point. These receive the special label -1 — they belong to no cluster.
A cluster is defined as the set of all points reachable from a core point through other core points. Two core points are in the same cluster if you can "hop" between them through a chain of core points that are within eps of each other.
Use the slider to change eps (with min_samples fixed at 4) on a fixed set of 2D points, and watch each point's role flip live between core (● green), border (amber), and noise (red) — the shaded circle around each core point shows its eps-neighborhood:
eps = 0.60, min_samples = 4 — counting core / border / noise points.
import numpy as np
from sklearn.cluster import DBSCAN
from sklearn.datasets import make_moons
from sklearn.preprocessing import StandardScaler
# K-Means fails on crescent shapes — DBSCAN handles them naturally
X_moons, y_true = make_moons(n_samples=300, noise=0.05, random_state=42)
X_moons_sc = StandardScaler().fit_transform(X_moons)
# Fit DBSCAN
db = DBSCAN(eps=0.3, min_samples=5)
db_labels = db.fit_predict(X_moons_sc)
# Analyze results
n_clusters = len(set(db_labels)) - (1 if -1 in db_labels else 0)
n_noise = (db_labels == -1).sum()
n_core = len(db.core_sample_indices_)
print(f"Number of clusters found: {n_clusters}")
print(f"Number of noise points: {n_noise}")
print(f"Number of core points: {n_core}")
print(f"Cluster sizes: {[(db_labels == k).sum() for k in range(n_clusters)]}")
# Core, border, and noise point identification
core_mask = np.zeros(len(X_moons_sc), dtype=bool)
core_mask[db.core_sample_indices_] = True
border_mask = (~core_mask) & (db_labels != -1)
noise_mask = db_labels == -1
print(f"\nCore points: {core_mask.sum()}")
print(f"Border points: {border_mask.sum()}")
print(f"Noise points: {noise_mask.sum()}")Unlike K-Means or hierarchical clustering, DBSCAN does not require you to specify the number of clusters. The number of clusters emerges naturally from the density structure of the data and the chosen eps/min_samples parameters. This is a significant practical advantage when the true K is unknown — which is almost always.
6 DBSCAN Parameters: eps and min_samples
DBSCAN has exactly two parameters, and both critically affect results:
eps (epsilon): The radius of the neighborhood around each point. Too small → almost everything is noise. Too large → all points merge into one cluster. A practical method: compute the k-nearest-neighbor distance for each point (k = min_samples - 1), sort and plot these distances, and look for an "elbow" — that elbow value is a good candidate for eps.
min_samples: The minimum number of points required in an eps-neighborhood for a point to be a core point. Larger values → fewer, more robust clusters with stricter density requirements; smaller values → more clusters, more sensitive to local density variations. Rule of thumb: min_samples ≥ 2 × n_features.
import numpy as np
import matplotlib.pyplot as plt
from sklearn.cluster import DBSCAN
from sklearn.neighbors import NearestNeighbors
from sklearn.preprocessing import StandardScaler
from sklearn.datasets import make_blobs
X, _ = make_blobs(n_samples=300, centers=4, cluster_std=0.8, random_state=42)
X_sc = StandardScaler().fit_transform(X)
# ── k-NN distance plot to choose eps ──
# Using k = min_samples - 1 = 4 (for min_samples=5)
k = 4
nbrs = NearestNeighbors(n_neighbors=k).fit(X_sc)
distances, _ = nbrs.kneighbors(X_sc)
kth_distances = np.sort(distances[:, -1]) # distance to k-th nearest neighbor
plt.figure(figsize=(8, 5))
plt.plot(kth_distances, linewidth=2)
plt.xlabel('Points (sorted by k-NN distance)')
plt.ylabel(f'{k}-NN Distance')
plt.title('k-NN Distance Plot — Choose eps at the Elbow')
plt.grid(alpha=0.3)
plt.tight_layout()
plt.savefig('knn_distance_plot.png', dpi=150)
# The "elbow" in this plot ≈ 0.5 suggests eps=0.5
# ── Grid search over eps and min_samples ──
from sklearn.metrics import silhouette_score
print(f"{'eps':>6} {'min_samples':>12} {'K':>5} {'Noise':>6} {'Silhouette':>12}")
print("-" * 50)
for eps in [0.3, 0.5, 0.7, 1.0]:
for min_samp in [3, 5, 10]:
db = DBSCAN(eps=eps, min_samples=min_samp)
labels = db.fit_predict(X_sc)
n_clusters = len(set(labels)) - (1 if -1 in labels else 0)
n_noise = (labels == -1).sum()
if n_clusters > 1:
sil = silhouette_score(X_sc, labels)
else:
sil = float('nan')
print(f"{eps:>6.1f} {min_samp:>12} {n_clusters:>5} {n_noise:>6} {sil:>12.4f}")
# ── Best configuration ──
db_best = DBSCAN(eps=0.5, min_samples=5)
labels_best = db_best.fit_predict(X_sc)
n_clusters_best = len(set(labels_best)) - (1 if -1 in labels_best else 0)
print(f"\nBest config (eps=0.5, min_samples=5): {n_clusters_best} clusters, "
f"{(labels_best==-1).sum()} noise points")A single eps cannot simultaneously handle a dense cluster (where you need small eps to separate points within the cluster from noise) and a sparse cluster (where you need large eps to connect distant cluster members). For datasets with clusters of very different densities, use HDBSCAN (Hierarchical DBSCAN), available in hdbscan library or sklearn.cluster.HDBSCAN (sklearn ≥ 1.3). HDBSCAN automatically adapts eps to local density.
7 DBSCAN Advantages and When to Use It
DBSCAN has several unique strengths that make it irreplaceable in certain scenarios:
- Arbitrary cluster shapes: Discovers crescents, rings, spirals, filaments — any shape defined by density, not geometry.
- Automatic outlier detection: Noise points (label = -1) are not forced into any cluster. This is simultaneously anomaly detection.
- No K required: The number of clusters is determined by the data's density structure, not a user parameter.
- Robust to noise: Noise points don't affect cluster formation — they're explicitly labeled out.
import numpy as np
import matplotlib.pyplot as plt
from sklearn.cluster import DBSCAN
from sklearn.datasets import make_moons, make_circles
from sklearn.preprocessing import StandardScaler
fig, axes = plt.subplots(2, 3, figsize=(15, 9))
datasets = [
('Moons', make_moons(n_samples=300, noise=0.06, random_state=42)[0], (0.25, 5)),
('Circles', make_circles(n_samples=300, noise=0.05, factor=0.5, random_state=42)[0], (0.25, 5)),
('Blobs with noise',
np.vstack([
np.random.default_rng(42).normal([0, 0], 0.5, (100, 2)),
np.random.default_rng(43).normal([4, 0], 0.5, (100, 2)),
np.random.default_rng(44).normal([2, 4], 0.5, (100, 2)),
np.random.default_rng(45).uniform(-3, 7, (20, 2)), # noise
]),
(0.5, 5)
),
]
cluster_colors = ['#e41a1c', '#377eb8', '#4daf4a', '#984ea3', '#ff7f00']
for col, (name, X_raw, (eps, minsamp)) in enumerate(datasets):
X_sc = StandardScaler().fit_transform(X_raw)
db = DBSCAN(eps=eps, min_samples=minsamp)
labels = db.fit_predict(X_sc)
n_clusters = len(set(labels)) - (1 if -1 in labels else 0)
noise_mask = labels == -1
for k in range(n_clusters):
mask = labels == k
axes[0, col].scatter(X_sc[mask, 0], X_sc[mask, 1],
c=cluster_colors[k % len(cluster_colors)],
alpha=0.7, s=20, label=f'Cluster {k}')
if noise_mask.any():
axes[0, col].scatter(X_sc[noise_mask, 0], X_sc[noise_mask, 1],
c='black', alpha=0.4, s=15, marker='x', label='Noise')
axes[0, col].set_title(f'DBSCAN on {name}\n({n_clusters} clusters, {noise_mask.sum()} noise)')
axes[0, col].legend(fontsize=7)
# Mark core vs border points
core_mask = np.zeros(len(X_sc), dtype=bool)
core_mask[db.core_sample_indices_] = True
border_mask = (~core_mask) & (labels != -1)
colors_type = np.where(core_mask, 'steelblue', np.where(border_mask, 'orange', 'red'))
axes[1, col].scatter(X_sc[:, 0], X_sc[:, 1], c=colors_type, alpha=0.6, s=15)
axes[1, col].set_title(f'Point Types\nBlue=Core, Orange=Border, Red=Noise')
plt.suptitle("DBSCAN: Arbitrary Shapes, Automatic Outlier Detection", fontsize=13)
plt.tight_layout()
plt.savefig('dbscan_results.png', dpi=150)8 Comparing All Three Algorithms
Now that you know all three major clustering algorithms, here is a comprehensive comparison to guide your algorithm selection:
| Property | K-Means | Hierarchical (Ward) | DBSCAN |
|---|---|---|---|
| Requires K? | ✅ Yes | ⚠️ After dendrogram | ❌ No |
| Cluster shape | Spherical/convex only | Convex (Ward) or arbitrary (single) | Arbitrary shape |
| Handles outliers? | ❌ Absorbed into clusters | ❌ Absorbed | ✅ Labeled as noise (-1) |
| Scalability | ✅ O(nKt) — very fast | ❌ O(n² log n) — slow | ⚠️ O(n log n) with index |
| Predict new points? | ✅ Yes (.predict) | ❌ Must refit | ⚠️ Approximate only |
| Hierarchical structure | ❌ No | ✅ Full dendrogram | ❌ No |
| Sensitive to scale? | ✅ Yes — must scale | ✅ Yes — must scale | ✅ Yes — must scale |
import numpy as np
import matplotlib.pyplot as plt
from sklearn.cluster import KMeans, AgglomerativeClustering, DBSCAN
from sklearn.datasets import make_moons
from sklearn.preprocessing import StandardScaler
from sklearn.metrics import adjusted_rand_score
# Non-convex dataset where K-Means fails
X_m, y_m = make_moons(n_samples=300, noise=0.05, random_state=42)
X_m_sc = StandardScaler().fit_transform(X_m)
algorithms = [
('K-Means (K=2)', KMeans(n_clusters=2, n_init=10, random_state=42)),
('Hierarchical (K=2)', AgglomerativeClustering(n_clusters=2, linkage='ward')),
('DBSCAN', DBSCAN(eps=0.25, min_samples=5)),
]
fig, axes = plt.subplots(1, 3, figsize=(15, 4))
colors = ['#e41a1c', '#377eb8', '#999999']
for ax, (name, algo) in zip(axes, algorithms):
labels = algo.fit_predict(X_m_sc)
ari = adjusted_rand_score(y_m, np.where(labels == -1, 2, labels))
unique = sorted(set(labels))
for k in unique:
mask = labels == k
col = colors[min(k, 2)] if k >= 0 else '#999999'
label_str = f'Cluster {k}' if k >= 0 else 'Noise'
ax.scatter(X_m_sc[mask, 0], X_m_sc[mask, 1], c=col, alpha=0.7, s=15, label=label_str)
ax.set_title(f'{name}\nARI = {ari:.3f}')
ax.legend(fontsize=8)
plt.suptitle('Comparing Clustering Algorithms on Crescent Data', fontsize=12)
plt.tight_layout()
plt.savefig('algorithm_comparison.png', dpi=150)
# ARI: K-Means ≈ 0.49 (poor), Hierarchical ≈ 0.49 (poor), DBSCAN ≈ 1.0 (perfect)Real-World Spotlight: Geospatial Crime Hotspot Analysis with DBSCAN
Urban planners and law enforcement agencies use DBSCAN on GPS coordinates of reported crimes to identify crime hotspots — dense spatial clusters — while distinguishing them from isolated incidents (noise). Standard K-Means would force every incident into a cluster; DBSCAN correctly identifies isolated events as noise.
import numpy as np
import matplotlib.pyplot as plt
from sklearn.cluster import DBSCAN
from sklearn.preprocessing import StandardScaler
np.random.seed(42)
# Simulate crime incidents across a city (lat/lon coordinates)
# Three genuine hotspots + scattered noise
hotspot_1 = np.random.normal([40.712, -74.006], [0.008, 0.012], (150, 2)) # Manhattan
hotspot_2 = np.random.normal([40.678, -73.944], [0.006, 0.008], (120, 2)) # Brooklyn
hotspot_3 = np.random.normal([40.730, -73.990], [0.005, 0.007], (80, 2)) # Village
isolated = np.random.uniform([40.65, -74.05], [40.77, -73.92], (50, 2)) # scattered
crimes = np.vstack([hotspot_1, hotspot_2, hotspot_3, isolated])
print(f"Total crime incidents: {len(crimes)}")
# DBSCAN with geographic parameters
# eps ≈ 0.01 degrees ≈ ~1 km; min_samples=10 (need dense area to be a hotspot)
db = DBSCAN(eps=0.015, min_samples=10)
labels = db.fit_predict(crimes)
n_hotspots = len(set(labels)) - (1 if -1 in labels else 0)
n_noise = (labels == -1).sum()
print(f"\nCrime hotspots found: {n_hotspots}")
print(f"Isolated incidents: {n_noise} ({n_noise/len(crimes):.1%} of total)")
for h in range(n_hotspots):
mask = labels == h
lat_c = crimes[mask, 0].mean()
lon_c = crimes[mask, 1].mean()
print(f"\nHotspot {h+1}: {mask.sum()} incidents, "
f"center ({lat_c:.4f}N, {lon_c:.4f}W)")
# Visualize
fig, ax = plt.subplots(figsize=(10, 8))
cluster_colors = ['#e41a1c', '#377eb8', '#4daf4a', '#984ea3']
for h in range(n_hotspots):
mask = labels == h
ax.scatter(crimes[mask, 1], crimes[mask, 0],
c=cluster_colors[h % len(cluster_colors)],
s=30, alpha=0.7, label=f'Hotspot {h+1} (n={mask.sum()})')
noise_mask = labels == -1
ax.scatter(crimes[noise_mask, 1], crimes[noise_mask, 0],
c='gray', s=15, alpha=0.4, marker='x', label=f'Isolated ({n_noise})')
ax.set_xlabel('Longitude')
ax.set_ylabel('Latitude')
ax.set_title('Crime Hotspot Analysis — DBSCAN on GPS Coordinates')
ax.legend()
plt.tight_layout()
plt.savefig('crime_hotspots.png', dpi=150)
# Hierarchical clustering on customer purchase sequences
print("\n--- Bonus: Hierarchical Clustering on Customer Purchase Patterns ---")
from sklearn.cluster import AgglomerativeClustering
from sklearn.metrics import silhouette_score
np.random.seed(0)
# 200 customers × 10 product categories (purchase frequency)
n_customers, n_categories = 200, 10
customer_purchases = np.abs(np.random.randn(n_customers, n_categories))
# Three archetypes: essentials buyers, electronics buyers, fashion buyers
customer_purchases[:70, :3] *= 4 # essentials (categories 0-2)
customer_purchases[70:140, 3:7] *= 4 # electronics (categories 3-6)
customer_purchases[140:, 7:] *= 4 # fashion (categories 7-9)
scaler = StandardScaler()
X_cust = scaler.fit_transform(customer_purchases)
agg = AgglomerativeClustering(n_clusters=3, linkage='ward')
cust_labels = agg.fit_predict(X_cust)
print(f"Customer segments found: {np.bincount(cust_labels)}")
print(f"Silhouette score: {silhouette_score(X_cust, cust_labels):.4f}")The DBSCAN approach found three genuine hotspots and correctly identified isolated incidents as noise — something K-Means cannot do without manual post-processing. Law enforcement can prioritize patrols around the hotspot centers while treating isolated incidents as one-off occurrences rather than evidence of an emerging cluster. The hierarchical clustering bonus shows how dendrogram-based analysis naturally reveals three distinct customer purchase archetypes without requiring prior knowledge of K.
✍️ Practice Exercises
- Load the Wine dataset (
from sklearn.datasets import load_wine). Run agglomerative clustering with all four linkage methods. Plot the Ward dendrogram and choose K by visual inspection. Compare ARI scores across linkage methods. - Apply DBSCAN to the
make_circlesdataset. Use the k-NN distance plot to choose an appropriateeps. How does DBSCAN compare to K-Means on this dataset? - Implement a parameter search for DBSCAN: vary
epsfrom 0.1 to 2.0 andmin_samplesfrom 2 to 15. For each pair that produces at least 2 clusters, record the silhouette score. Plot a heatmap of silhouette scores. - Generate a dataset with three clusters of very different densities (use
make_blobswith differentcluster_stdvalues per center). Show that DBSCAN struggles. Then research HDBSCAN in sklearn (≥1.3) and compare.
📚 Primary Source for This Lesson
scikit-learn: Clustering Overview — covers agglomerative clustering, DBSCAN, and all other sklearn clustering algorithms with visual comparisons.
Original DBSCAN paper: Ester et al. (1996) "A density-based algorithm for discovering clusters in large spatial databases with noise" (KDD-96). For hierarchical clustering theory, see Hastie, Tibshirani & Friedman, Chapter 14.3.