Hierarchical Linkage & Density-Based DBSCAN | AI & Machine Learning Engineering

Centroid-based algorithms like k-Means assume that clusters are convex, isotropic, and spherical. When data features elongated filaments, concentric rings, or substantial background noise, k-Means shatters natural groupings.

To model arbitrary topological manifolds, unsupervised learning relies on Hierarchical Clustering and Density-Based Spatial Clustering of Applications with Noise (DBSCAN).

Manifold DiscoveryTopology

Arbitrary Topology

DBSCAN identifies clusters of arbitrary non-convex shapes and isolates anomalous noise without pre-specifying K.

1. Hierarchical Linkage: Deriving Ward's Minimum Variance#

Agglomerative hierarchical clustering begins with $N$ individual singleton clusters and iteratively merges the closest pair of clusters until a single root remains.

Architecture Diagram

Rendering diagram...

Derivation of Ward's Distance Formula#

Ward's Linkage minimizes the total within-cluster variance increase resulting from merging two clusters $A$ and $B$ .

Let cluster $A$ have $n_A$ points with mean vector $\mu_A$ , and cluster $B$ have $n_B$ points with mean vector $\mu_B$ . The Error Sum of Squares (ESS) of cluster $A$ is:

\text{ESS}_A = \sum_{x \in A} \|x - \mu_A\|_2^2

The combined cluster $A \cup B$ has size $n_A + n_B$ and mean centroid:

\mu_{A \cup B} = \frac{n_A \mu_A + n_B \mu_B}{n_A + n_B}

Step 1: Formulate the Variance Increase

The increase in variance $\Delta \text{ESS}_{A,B}$ caused by merging $A$ and $B$ is:

\Delta \text{ESS}_{A,B} = \text{ESS}_{A \cup B} - (\text{ESS}_A + \text{ESS}_B)

Step 2: Expand $\text{ESS}_{A \cup B}$ Around Individual Means

For any point $x \in A$ :

\|x - \mu_{A \cup B}\|_2^2 = \|(x - \mu_A) + (\mu_A - \mu_{A \cup B})\|_2^2 = \|x - \mu_A\|_2^2 + \|\mu_A - \mu_{A \cup B}\|_2^2 + 2(x - \mu_A)^T(\mu_A - \mu_{A \cup B})

Summing over all $x \in A$ , the cross-term vanishes because $\sum_{x \in A} (x - \mu_A) = 0$ :

\sum_{x \in A} \|x - \mu_{A \cup B}\|_2^2 = \text{ESS}_A + n_A \|\mu_A - \mu_{A \cup B}\|_2^2

Similarly for cluster $B$ :

\sum_{y \in B} \|y - \mu_{A \cup B}\|_2^2 = \text{ESS}_B + n_B \|\mu_B - \mu_{A \cup B}\|_2^2

Step 3: Compute the Net Shift Difference

Subtracting $\text{ESS}_A + \text{ESS}_B$ :

\Delta \text{ESS}_{A,B} = n_A \|\mu_A - \mu_{A \cup B}\|_2^2 + n_B \|\mu_B - \mu_{A \cup B}\|_2^2

Evaluate the centroid difference:

\mu_A - \mu_{A \cup B} = \mu_A - \frac{n_A \mu_A + n_B \mu_B}{n_A + n_B} = \frac{n_B(\mu_A - \mu_B)}{n_A + n_B}

\mu_B - \mu_{A \cup B} = \mu_B - \frac{n_A \mu_A + n_B \mu_B}{n_A + n_B} = \frac{-n_A(\mu_A - \mu_B)}{n_A + n_B}

Step 4: Substitute and Factor

Substitute these differences back into the expression:

\Delta \text{ESS}_{A,B} = n_A \left( \frac{n_B}{n_A + n_B} \right)^{\!2} \|\mu_A - \mu_B\|_2^2 + n_B \left( \frac{n_A}{n_A + n_B} \right)^{\!2} \|\mu_A - \mu_B\|_2^2

= \frac{n_A n_B^2 + n_B n_A^2}{(n_A + n_B)^2} \|\mu_A - \mu_B\|_2^2 = \frac{n_A n_B (n_A + n_B)}{(n_A + n_B)^2} \|\mu_A - \mu_B\|_2^2

Canceling $(n_A + n_B)$ yields Ward's classic metric:

\Delta \text{ESS}_{A,B} = \frac{n_A n_B}{n_A + n_B} \|\mu_A - \mu_B\|_2^2

2. DBSCAN: Density Foundations#

DBSCAN (Density-Based Spatial Clustering of Applications with Noise) views clusters as contiguous dense regions bounded by regions of low point density.

Architecture Diagram

Rendering diagram...

Definitions & Topological Concepts#

Let $D \subset \mathbb{R}^d$ be a dataset. Given radius parameter $\epsilon > 0$ and density threshold $\text{MinPts} \in \mathbb{N}$ :

$\epsilon$ -Neighborhood:

N_\epsilon(p) = \{q \in D : \text{dist}(p, q) \le \epsilon\}

Core Point: A point $p$ is a core point if $|N_\epsilon(p)| \ge \text{MinPts}$ .
Directly Density-Reachable: A point $p$ is directly density-reachable from point $q$ if $p \in N_\epsilon(q)$ and $q$ is a core point.
Density-Reachable: A point $p$ is density-reachable from point $q$ if there exists a sequence of core points $p_1, p_2, \dots, p_n$ such that $p_1 = q$ , $p_n = p$ , and $p_{i+1}$ is directly density-reachable from $p_i$ .
Density-Connected: Two points $p$ and $q$ are density-connected if there exists an intermediate point $o \in D$ such that both $p$ and $q$ are density-reachable from $o$ .

A DBSCAN Cluster is formally defined as a maximal set of density-connected points. Any sample not belonging to any cluster is designated as anomalous Noise (assigned label $-1$ ).

3. From-Scratch Implementation: Zero Dependencies#

The following implementations construct the complete DBSCAN algorithm from scratch in Python and Rust using only built-in collections and standard math.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
import math
from typing import List, Set

class DBSCANFromScratch:
    def __init__(self, eps: float = 1.5, min_pts: int = 3):
        self.eps = eps
        self.min_pts = min_pts
        self.labels: List[int] = []

    @staticmethod
    def _euclidean_dist(a: List[float], b: List[float]) -> float:
        return math.sqrt(sum((x_i - y_i) ** 2 for x_i, y_i in zip(a, b)))

    def _region_query(self, X: List[List[float]], point_idx: int) -> List[int]:
        neighbors = []
        for i, sample in enumerate(X):
            if self._euclidean_dist(X[point_idx], sample) <= self.eps:
                neighbors.append(i)
        return neighbors

    def fit(self, X: List[List[float]]) -> List[int]:
        num_samples = len(X)
        # -1 represents Noise, 0 represents Unvisited
        self.labels = [0] * num_samples
        cluster_id = 0

        for i in range(num_samples):
            if self.labels[i] != 0:
                continue

            neighbors = self._region_query(X, i)
            if len(neighbors) < self.min_pts:
                self.labels[i] = -1  # Mark as Noise
            else:
                cluster_id += 1
                self._expand_cluster(X, i, neighbors, cluster_id)

        return self.labels

    def _expand_cluster(self, X: List[List[float]], core_idx: int, neighbors: List[int], cluster_id: int):
        self.labels[core_idx] = cluster_id
        # Use a queue for breadth-first density traversal
        queue = list(neighbors)

        while queue:
            current_idx = queue.pop(0)

            # If formerly labeled noise, it is a border point; reassign to cluster
            if self.labels[current_idx] == -1:
                self.labels[current_idx] = cluster_id

            if self.labels[current_idx] == 0:
                self.labels[current_idx] = cluster_id
                sub_neighbors = self._region_query(X, current_idx)
                if len(sub_neighbors) >= self.min_pts:
                    queue.extend(sub_neighbors)

if __name__ == "__main__":
    # Concentric clusters with an outlier
    X = [
        [1.0, 1.2], [1.1, 1.0], [0.9, 1.1], [1.0, 0.9], # Dense Cluster 1
        [6.0, 6.2], [6.1, 6.0], [5.9, 6.1], [6.0, 5.9], # Dense Cluster 2
        [15.0, 15.0]                                     # Outlier Noise
    ]

    dbscan = DBSCANFromScratch(eps=1.5, min_pts=3)
    labels = dbscan.fit(X)
    print("DBSCAN Cluster Labels (-1 is Noise):", labels)

4. Active Knowledge Checks#

Concept check

In Ward's hierarchical linkage criterion, why does the merge distance Delta ESS equal (n_A * n_B / (n_A + n_B)) * ||mu_A - mu_B||^2?

Concept check

What occurs when a data point p in DBSCAN has fewer than MinPts neighbors within epsilon, but is within the epsilon-neighborhood of an existing Core Point?