Hierarchical & Density-Based Clustering | ML-101

Beyond K-Means

K-Means is fast and intuitive, but it forces you to choose K before you start and assumes clusters are spherical and roughly equal in size. Real-world data rarely cooperates. Galaxies form filaments, customer behavior clusters in irregular shapes, and biological categories nest inside one another. Two families of algorithms address these gaps: hierarchical clustering, which builds a tree of nested groupings without committing to K, and density-based clustering, which finds clusters of arbitrary shape by following regions of high data density.

Hierarchical Clustering

Hierarchical clustering produces a nested sequence of partitions, from every point in its own cluster all the way to every point in one cluster. The result is a tree structure called a dendrogram that captures the full merge (or split) history. You can cut the dendrogram at any height to obtain any number of clusters — without re-running the algorithm.

There are two complementary strategies:

Agglomerative (bottom-up): Start with n singleton clusters. At each step, merge the two closest clusters. Repeat until one cluster remains. This is the standard approach — it scales to moderate dataset sizes and is straightforward to implement.

Divisive (top-down): Start with all points in one cluster. Recursively split the most “heterogeneous” cluster. This is computationally more expensive and rarely used in practice, but can be effective when the top-level structure matters most.

Linkage Methods

Agglomerative clustering needs a rule for measuring the distance between two clusters (not just two points). The choice of linkage criterion dramatically shapes the resulting tree:

Single linkage: Distance between clusters is the minimum distance between any two points, one from each cluster. This produces long, elongated (chaining) clusters and is sensitive to noise — a single bridge point can merge two distant groups prematurely.

Complete linkage: Distance is the maximum distance between any two points across the clusters. This produces compact, spherical clusters and is more robust to noise but can fragment large clusters.

Average linkage: Distance is the average pairwise distance between all pairs of points across the two clusters. A compromise between single and complete — moderately robust and widely used.

Ward’s method: Rather than measuring inter-cluster distance directly, Ward’s criterion merges the pair of clusters that minimizes the increase in total within-cluster variance. This produces compact, roughly equal-sized clusters and is the most popular choice for agglomerative clustering in practice.

Ward Merge Cost

\Delta(A,B) = \dfrac{n_A \, n_B}{n_A + n_B} \, d(\boldsymbol{\mu}_A,\, \boldsymbol{\mu}_B)^2

When merging clusters A and B into A∪B, Ward’s criterion adds the increase in total within-cluster sum of squares. n_A and n_B are cluster sizes; d(μ_A, μ_B) is the Euclidean distance between their centroids. Ward’s method minimizes this quantity at each merge step.

Reading Dendrograms

The height at which two clusters merge in the dendrogram reflects their dissimilarity at the time of merging. A large jump in height between two consecutive merges suggests a natural cut point — the number of clusters at that cut is a good candidate for K. This is the hierarchical equivalent of the elbow method.

DBSCAN: Density-Based Clustering

DBSCAN (Density-Based Spatial Clustering of Applications with Noise) takes a fundamentally different view: a cluster is a dense region of points separated from other dense regions by sparse space. Points in sparse regions are labeled as noise (outliers) and assigned to no cluster. DBSCAN requires no K and can discover clusters of arbitrary shape.

DBSCAN has two hyperparameters:

ε (epsilon): The neighborhood radius. Two points are “neighbors” if their distance is at most ε.

MinPts: The minimum number of points that must lie within a point’s ε-neighborhood for that point to be a core point.

The algorithm classifies each point as one of three types:

Core point: Has at least MinPts neighbors within radius ε. Core points are in the interior of a dense region.

Border point: Has fewer than MinPts neighbors but falls within ε of a core point. Border points are on the edge of a cluster.

Noise point: Not a core point and not within ε of any core point. Noise points belong to no cluster — they are outliers.

DBSCAN then connects core points that are within ε of each other (and their reachable border points) into clusters. The algorithm runs in O(n log n) with a spatial index (e.g., a k-d tree) and O(n²) naively.

DBSCAN Neighborhood

N_{\varepsilon}(p) = \{\, q \in X \mid d(p,q) \leq \varepsilon \,\}

The ε-neighborhood of point p is the set of all points within distance ε. Point p is a core point if |N_ε(p)| ≥ MinPts. DBSCAN builds clusters by merging core points whose neighborhoods overlap.

Choosing ε and MinPts

A useful heuristic: set MinPts = 2 × number of dimensions (minimum 4). Then plot the k-nearest-neighbor distance for each point (k = MinPts − 1), sorted in ascending order. Look for the “elbow” — the sharp bend in this curve is a good estimate for ε. Points above the elbow are noise; points below are in dense regions.

Advantages of DBSCAN

Arbitrary cluster shapes: DBSCAN follows the data density, not centroid distances. Two interleaved crescents, a ring inside a disc, or a spiral galaxy — shapes that completely foil K-Means — are trivially separated by DBSCAN if their densities differ from the background.

No K required: The number of clusters is determined by the data structure. You do not need to specify K in advance. This is especially valuable for exploratory analysis where you have no prior about the number of groups.

Outlier detection built-in: Noise points are explicitly identified as a byproduct of the algorithm. DBSCAN is therefore both a clustering algorithm and an outlier detector.

Deterministic: Unlike K-Means, DBSCAN is deterministic — the same input always produces the same output (border point assignment can vary, but core point membership and noise labels are fixed).

DBSCAN struggles when clusters have very different densities, because a single (ε, MinPts) pair cannot simultaneously capture a tight dense cluster and a sparse diffuse one. HDBSCAN (Hierarchical DBSCAN) addresses this by varying the density threshold and extracting a cluster hierarchy, at the cost of greater complexity.

Comparing the Three Approaches

K-Means is fastest and most scalable. It works well when clusters are approximately spherical, similarly sized, and the number of clusters is known. Mini-Batch K-Means handles millions of points. Weakness: cannot handle arbitrary shapes, sensitive to initialization and outliers.

Hierarchical clustering produces a full tree of groupings and requires no K upfront — you choose the cut after seeing the dendrogram. Ward’s linkage often gives the best results. Weakness: O(n² log n) complexity makes it impractical for large datasets (>10,000 points without approximations).

DBSCAN finds arbitrary-shaped clusters and identifies outliers automatically. No K required. Works well when cluster densities are roughly uniform. Weakness: poor performance when density varies significantly across clusters; requires careful tuning of ε and MinPts.

In the next lesson, we turn to dimensionality reduction — PCA, t-SNE, and UMAP — techniques that compress high-dimensional data into two or three dimensions while preserving as much structure as possible.

Key Takeaways

Hierarchical clustering builds a dendrogram of nested groupings; cut at any height to choose K after the fact.
Agglomerative (bottom-up) is standard; Ward’s linkage minimizes within-cluster variance and usually gives the best results.
Linkage choice matters: single linkage chains, complete linkage compacts, average linkage balances, Ward minimizes variance increase.
DBSCAN defines clusters as dense regions separated by sparse space; it requires no K and automatically labels outliers as noise.
DBSCAN classifies points as core (dense interior), border (edge of cluster), or noise (outlier).
DBSCAN handles arbitrary cluster shapes but struggles when cluster densities differ significantly.
Choose K-Means for speed, hierarchical for interpretable trees, DBSCAN for arbitrary shapes and outlier detection.