Machine Learning

Unsupervised Learning

Hierarchical Clustering & DBSCAN

Chapter 1 ended by identifying two real limitations: K-Means requires choosing K in advance, and assumes roughly spherical clusters. This chapter covers two alt

JrCodex·8 min read

Jr Codex ML Notes

Level: Intermediate–Advanced Prerequisites: Chapter 1: K-Means Clustering Time to complete: ~25 minutes

Table of Contents

  1. Fixing K-Means's Limitations
  2. Hierarchical Clustering — Building a Tree of Clusters
  3. Linkage Methods
  4. Reading a Dendrogram
  5. DBSCAN — Density-Based Clustering
  6. DBSCAN's Key Parameters
  7. DBSCAN Handles Noise Naturally
  8. Choosing Between K-Means, Hierarchical & DBSCAN
  9. Summary & Next Steps

1. Fixing K-Means's Limitations

Chapter 1 ended by identifying two real limitations: K-Means requires choosing K in advance, and assumes roughly spherical clusters. This chapter covers two alternatives, each fixing one of these limitations directly.

This Chapter's Two Algorithms
─────────────────────────────────────────
  Hierarchical Clustering:    doesn't require choosing K
                                 upfront — builds a FULL TREE
                                 of nested clusters, letting
                                 you choose K AFTERWARD

  DBSCAN:                        doesn't assume spherical
                                    clusters at all — finds
                                    clusters of ARBITRARY shape,
                                    based on DENSITY
─────────────────────────────────────────

2. Hierarchical Clustering — Building a Tree of Clusters

Agglomerative (bottom-up) hierarchical clustering starts with every point as its own cluster, then repeatedly merges the two closest clusters until only one remains.

The Algorithm
─────────────────────────────────────────
  1. Start: EVERY point is its OWN cluster (n clusters, for n points)
  2. Find the two CLOSEST clusters (Section 3 defines "closest")
  3. MERGE them into one cluster
  4. REPEAT step 2-3 until only ONE cluster remains
  5. The FULL SEQUENCE of merges forms a TREE (a "dendrogram")
─────────────────────────────────────────

from sklearn.cluster import AgglomerativeClustering
import numpy as np
 
X = np.array([
    [25, 1200], [22, 1350], [30, 1100],
    [52, 8500], [48, 7900], [55, 9200],
])
 
model = AgglomerativeClustering(n_clusters=2)
labels = model.fit_predict(X)
print(labels)

3. Linkage Methods

"Closest clusters" (Section 2, step 2) needs a precise definition when clusters contain more than one point — different linkage methods define this differently.

from sklearn.cluster import AgglomerativeClustering
 
model_single = AgglomerativeClustering(n_clusters=2, linkage="single")           # MINIMUM distance
model_complete = AgglomerativeClustering(n_clusters=2, linkage="complete")          # MAXIMUM distance
model_average = AgglomerativeClustering(n_clusters=2, linkage="average")               # AVERAGE distance
model_ward = AgglomerativeClustering(n_clusters=2, linkage="ward")                        # minimizes VARIANCE increase
Linkage Methods, Compared
─────────────────────────────────────────
  Single:    distance between the CLOSEST pair of points
               (one from each cluster) — can produce long,
               "chained" clusters

  Complete:     distance between the FARTHEST pair of points
                  — tends to produce more COMPACT, evenly-sized
                  clusters

  Average:         average distance across ALL pairs — a
                      balance between single and complete

  Ward:                merges clusters that result in the
                          SMALLEST increase in within-cluster
                          variance — similar in spirit to
                          Chapter 1's K-Means objective,
                          scikit-learn's default and often the
                          best general-purpose choice
─────────────────────────────────────────

4. Reading a Dendrogram

The full merge history (Section 2) is visualized as a dendrogram — a tree diagram directly showing how clusters combined at every step.

from scipy.cluster.hierarchy import dendrogram, linkage
import matplotlib.pyplot as plt
 
Z = linkage(X, method="ward")
 
dendrogram(Z)
plt.xlabel("Data points")
plt.ylabel("Distance at which clusters merged")
plt.title("Dendrogram")
Reading a Dendrogram
─────────────────────────────────────────
    Distance
       │        ┌───────────┐
       │        │           │
       │    ┌───┴───┐   ┌───┴───┐
       │    │       │   │       │
       │   [A]     [B] [C]     [D]

  HEIGHT of a merge = how DISSIMILAR the two merging clusters
  were. LOW merges = very similar clusters combining early;
  HIGH merges = quite different clusters, combined only at
  the very end.

  To choose K clusters: draw a HORIZONTAL line at some height,
  and count how many VERTICAL lines it crosses — that's your K.
─────────────────────────────────────────

This is the key advantage over Chapter 1's K-Means: the ENTIRE hierarchy is computed once, and K can be chosen afterward by picking where to "cut" the tree — you don't need to commit to K before seeing the results, and can explore multiple K values from a single computation.

5. DBSCAN — Density-Based Clustering

DBSCAN (Density-Based Spatial Clustering of Applications with Noise) defines clusters as dense regions of points, separated by sparser regions — fundamentally different from both prior algorithms' distance/variance-based approach.

from sklearn.cluster import DBSCAN
import numpy as np
 
# Revisiting Chapter 1's concentric rings — where K-Means FAILED
np.random.seed(0)
theta = np.linspace(0, 2*np.pi, 100)
inner_ring = np.column_stack([np.cos(theta), np.sin(theta)]) + np.random.normal(0, 0.1, (100, 2))
outer_ring = np.column_stack([3*np.cos(theta), 3*np.sin(theta)]) + np.random.normal(0, 0.1, (100, 2))
X_rings = np.vstack([inner_ring, outer_ring])
 
model = DBSCAN(eps=0.5, min_samples=5)
labels = model.fit_predict(X_rings)
print(np.unique(labels))      # correctly identifies the TWO rings as separate clusters!
Why DBSCAN Succeeds Where K-Means Failed
─────────────────────────────────────────
  DBSCAN doesn't assume any particular SHAPE — it just looks
  for regions where points are DENSELY packed together,
  separated by sparser "empty" regions.

  The inner ring and outer ring are each internally DENSE, and
  clearly SEPARATED from each other by an empty gap — exactly
  what DBSCAN is built to detect, regardless of the actual
  GEOMETRIC shape involved.
─────────────────────────────────────────

6. DBSCAN's Key Parameters

Two Parameters Define "Density"
─────────────────────────────────────────
  eps (epsilon):       the MAXIMUM distance between two points
                          for them to be considered "neighbors"

  min_samples:            the MINIMUM number of neighbors
                              (within eps) a point needs to be
                              considered a "CORE point" (part of
                              a dense region)
─────────────────────────────────────────

from sklearn.cluster import DBSCAN
 
# Smaller eps = STRICTER density requirement — more, smaller clusters
model_strict = DBSCAN(eps=0.3, min_samples=5)
 
# Larger eps = LOOSER density requirement — fewer, larger clusters
model_loose = DBSCAN(eps=1.0, min_samples=5)
Choosing eps — the K-Distance Plot
─────────────────────────────────────────
  A common practical technique: for each point, compute the
  distance to its k-th nearest neighbor (k = min_samples),
  sort these distances, and plot them — look for an "elbow"
  (directly echoing Chapter 1's elbow method concept) where
  distances start increasing sharply — that point suggests a
  reasonable eps value.
─────────────────────────────────────────

7. DBSCAN Handles Noise Naturally

A genuinely distinctive DBSCAN feature: points that don't belong to any dense region are explicitly labeled as noise (-1), rather than being forced into the nearest cluster regardless of fit.

from sklearn.cluster import DBSCAN
import numpy as np
 
X_with_outliers = np.array([
    [1, 1], [1.1, 1.1], [0.9, 0.9],      # a dense cluster
    [5, 5], [5.1, 5.1], [4.9, 4.9],      # another dense cluster
    [20, 20],                               # a clear OUTLIER, far from everything
])
 
model = DBSCAN(eps=1.0, min_samples=2)
labels = model.fit_predict(X_with_outliers)
print(labels)      # e.g. [0, 0, 0, 1, 1, 1, -1] — -1 marks the outlier as NOISE
K-Means vs DBSCAN on Outliers
─────────────────────────────────────────
  K-Means (Ch.1):     FORCES every point into one of K clusters,
                         even a clear outlier — potentially
                         distorting that cluster's centroid

  DBSCAN (this chapter): explicitly labels genuine outliers as
                            NOISE, never forcing them into an
                            ill-fitting cluster — directly
                            connects to the Data Science Notes'
                            outlier detection chapter's concern
                            with contaminating an analysis
─────────────────────────────────────────

8. Choosing Between K-Means, Hierarchical & DBSCAN

Decision Guide
─────────────────────────────────────────
  Know roughly HOW MANY clusters you expect, clusters are
  reasonably SPHERICAL/similar-sized, want SPEED on large data
      → K-Means (Chapter 1)

  Want to EXPLORE different numbers of clusters without
  recomputing, want to SEE the full nested structure, dataset
  is SMALL to MEDIUM (hierarchical clustering doesn't scale as
  well to very large datasets)
      → Hierarchical Clustering (this chapter)

  Clusters have IRREGULAR shapes, dataset likely contains
  genuine OUTLIERS/noise, don't know or want to specify K in
  advance
      → DBSCAN (this chapter)
─────────────────────────────────────────
K-MeansHierarchicalDBSCAN
Requires K upfront?YesNo (choose after)No (density-based)
Handles irregular shapes?NoSomewhatYes
Handles outliers/noise?No (forces assignment)NoYes (explicit noise label)
Scales to large data?WellPoorlyReasonably

9. Summary & Next Steps

Key Takeaways

  • Hierarchical clustering builds a complete tree of nested clusters via repeated merging, letting you choose K after the fact by "cutting" the dendrogram at a chosen height, rather than committing upfront.
  • Linkage methods (single, complete, average, ward) define what "closest clusters" means differently, with ward's variance-minimizing approach as the common default.
  • DBSCAN defines clusters as dense regions separated by sparser areas, requiring no assumption about cluster shape — it correctly handles the concentric-ring case where K-Means fails.
  • DBSCAN naturally identifies noise/outlier points rather than forcing every point into a cluster, a genuine advantage for messy real-world data.

Module 6 Complete (Clustering) — Next: Dimensionality Reduction

You now have three distinct clustering algorithms, each suited to different data shapes and requirements. Chapters 3-4 cover unsupervised learning's other major task — reducing the number of features while preserving the data's essential structure.

Concept Check

  1. Why does hierarchical clustering not require choosing K before running the algorithm, unlike K-Means?
  2. Why does DBSCAN succeed at separating concentric rings where K-Means fails?
  3. What does DBSCAN do with a genuine outlier that K-Means cannot?

Next Chapter

→ Chapter 3: Principal Component Analysis (PCA)

Jr Codex — 1-on-1 Personalized Coaching | Back to Module Index