Hierarchical Clustering › Formula

Imagine you're organizing a library. You start with individual books scattered on tables, and your goal is to arrange them into meaningful groups, perhaps by genre, then by author, then by publication date. As you work, you notice that some books naturally belong together, while others form distinct groups. This intuitive process of building organization from the bottom up, creating nested categories that reflect natural relationships, is exactly what hierarchical clustering does with data.

The mathematical challenge is significant: given a collection of data points, how do we discover and represent their natural hierarchical relationships? Unlike methods that require us to specify the number of groups in advance, hierarchical clustering builds a complete tree of relationships, called a dendrogram, that reveals how data points connect at every possible level of granularity. This tree shows us which points belong together, how they relate, when they merge, and why certain groupings make sense.

To build this hierarchy, we need to solve three fundamental problems in sequence:

1. Measuring similarity between individual points: How do we quantify how similar or different any two data points are?
2. Measuring similarity between groups of points: Once we have clusters, how do we decide which clusters should merge next?
3. Building the hierarchy systematically: How do we combine these measurements into an algorithm that creates a meaningful tree structure?

Each problem builds naturally on the previous one, and together they form a complete mathematical framework for hierarchical clustering. Let's explore each piece, understanding what the formulas say, why they're necessary, and how they work together to solve the clustering problem.

Before we can group points into clusters, we need a fundamental tool: a way to measure how similar or different any two points are. This might seem straightforward, but the choice of measurement determines what clusters we discover. Think of it like choosing between measuring distance "as the crow flies" versus "along city streets." The same two locations can appear very different depending on your metric.

In data science, we work with points that have multiple features. A customer might be described by attributes such as age and purchase frequency. A gene might be characterized by expression levels across hundreds of conditions. A document might be represented by word frequencies across thousands of terms. To measure similarity, we need a way to combine differences across all these dimensions into a single number.

The Euclidean Distance: Our Intuitive Starting Point

The most natural approach is to measure the straight-line distance between points, just as we would measure the distance between two cities on a map. This is the Euclidean distance, and it captures our intuitive sense of "closeness" in multidimensional space.

For two data points $\mathbf{x}_i$ and $\mathbf{x}_j$ in a d-dimensional space, the Euclidean distance is:

$$d_{euclidean}(\mathbf{x}_i, \mathbf{x}_j) = \sqrt{\sum_{k=1}^{d} (x_{ik} - x_{jk})^2}$$

where:

• $\mathbf{x}_i$: the $i$-th data point (a vector with $d$ features)
• $\mathbf{x}_j$: the $j$-th data point (a vector with $d$ features)
• $d$: the number of features (dimensions) in the data space
• $x_{ik}$: the value of the $k$-th feature for the $i$-th data point
• $x_{jk}$: the value of the $k$-th feature for the $j$-th data point
• $k$: index over features, ranging from 1 to $d$

Let's understand what each part of this formula accomplishes:

• $(x_{ik} - x_{jk})$: For each feature $k$, we compute how different the two points are. This difference can be positive or negative, depending on which point has the larger value.
• $(x_{ik} - x_{jk})^2$: We square each difference for two reasons: it ensures all terms are positive (so differences in opposite directions don't cancel out), and it gives more weight to larger differences. A difference of 10 contributes 100 to the sum, while a difference of 1 contributes only 1.
• $\sum_{k=1}^{d}$: We sum these squared differences across all $d$ features, combining differences in age, income, purchase frequency, and every other dimension into a single measure.
• $\sqrt{\cdot}$: Finally, we take the square root to return to the original units of measurement. Without this, we'd be working with squared distances, which would be harder to interpret and wouldn't have the same units as our original features.

The square root is more than a mathematical convenience. It ensures that if point A is twice as far from point B as point C is from point D, our distance metric reflects this relationship proportionally.

The Scale Problem: Why Standardization Matters

However, there's an important problem that emerges in real-world data: features often have dramatically different scales. Consider clustering customers using age (ranging from 18 to 80 years) and annual income (ranging from $20,000 to $200,000). In the Euclidean distance calculation, a $10,000 difference in income contributes $(10,000)^2 = 100,000,000$ to the squared distance sum, while a 10-year difference in age contributes only $10^2 = 100$. Income largely dominates the distance calculation, making age largely irrelevant to the clustering.

Our clusters will be determined almost entirely by income, ignoring potentially important patterns related to age. We need a way to ensure that every feature contributes to the distance calculation, regardless of its original scale.

The Solution: Standardized Euclidean Distance

The solution is to normalize each feature by its variability before computing distances. This gives us the standardized Euclidean distance:

$$d_{standardized}(\mathbf{x}_i, \mathbf{x}_j) = \sqrt{\sum_{k=1}^{d} \frac{(x_{ik} - x_{jk})^2}{s_k^2}}$$

where:

• $\mathbf{x}_i$: the $i$-th data point (a vector with $d$ features)
• $\mathbf{x}_j$: the $j$-th data point (a vector with $d$ features)
• $d$: the number of features (dimensions) in the data space
• $x_{ik}$: the value of the $k$-th feature for the $i$-th data point
• $x_{jk}$: the value of the $k$-th feature for the $j$-th data point
• $s_k$: the standard deviation of the $k$-th feature across all data points
• $k$: index over features, ranging from 1 to $d$

By dividing each squared difference by $s_k^2$, we're essentially asking: "How many standard deviations apart are these two points on this feature?" This normalization ensures that:

• A one-standard-deviation difference in age contributes the same amount to the distance as a one-standard-deviation difference in income
• Features with larger scales don't dominate the calculation
• All features contribute to determining which points are similar

This is why standardization is typically an important preprocessing step before hierarchical clustering. Without it, we're not discovering the true structure of our data. We're just finding patterns in whichever feature happens to have the largest numbers.

Once we can measure distances between individual points, we face a new and more subtle challenge: how do we measure the distance between two clusters, each of which may contain multiple points? This question is fundamental because hierarchical clustering repeatedly merges clusters, and at each step, we need a rule to decide which clusters are most similar and should merge next.

The challenge is that a cluster isn't a single point. It's a collection of points that may be spread out in various ways. Two clusters might each contain 100 points arranged in different patterns: one might be a tight, compact sphere, while another might be an elongated ellipse. How do we capture the "distance" between such complex objects?

This is where linkage criteria come into play. A linkage criterion defines how we compute the distance between two clusters based on the distances between the individual points within them. The choice of linkage criterion is one of the most important decisions in hierarchical clustering because it fundamentally shapes what kinds of clusters we discover.

Different linkage criteria answer different questions about cluster similarity, and each leads to distinct clustering behaviors. Rather than memorizing formulas, focus on the question each criterion asks and the kind of answer it provides.

Single Linkage: The Optimistic Criterion

The simplest approach is to define the distance between two clusters as the distance between their two closest points. This is called single linkage (also known as minimum linkage):

$$d_{single}(A, B) = \min_{a \in A, b \in B} d(a, b)$$

where:

• $A$: the first cluster (a set of data points)
• $B$: the second cluster (a set of data points)
• $a$: a data point belonging to cluster $A$
• $b$: a data point belonging to cluster $B$
• $d(a, b)$: the distance between points $a$ and $b$ (using the chosen distance metric)
• $\min$: the minimum operator (finds the smallest value)

Think of this as asking: "What's the shortest bridge between these two clusters?" If even one point from cluster A is close to one point from cluster B, the clusters are considered similar and likely to merge.

This lenient criterion has important consequences:

• It creates elongated, chain-like clusters: Because only one pair of points needs to be close, clusters can connect through narrow "bridges" of points. This is called the "chaining effect." Imagine a chain where each link is close to the next, even though the endpoints are far apart.
• It's sensitive to outliers: A single outlier point can create a spurious connection between otherwise distant clusters, distorting the entire hierarchy.
• It captures non-spherical clusters: Unlike methods that assume clusters are round, single linkage can discover clusters of arbitrary shape, as long as they're connected by a path of nearby points.

Single linkage is like an optimistic friend who sees connections everywhere. It's great for finding complex, non-linear structures, but it can also create clusters that don't reflect meaningful groupings.

Complete Linkage: The Pessimistic Criterion

At the opposite extreme, complete linkage (also known as maximum linkage) defines the distance between two clusters as the distance between their two farthest points:

$$d_{complete}(A, B) = \max_{a \in A, b \in B} d(a, b)$$

where:

• $A$: the first cluster (a set of data points)
• $B$: the second cluster (a set of data points)
• $a$: a data point belonging to cluster $A$
• $b$: a data point belonging to cluster $B$
• $d(a, b)$: the distance between points $a$ and $b$ (using the chosen distance metric)
• $\max$: the maximum operator (finds the largest value)

This is like asking: "What's the longest gap we'd need to bridge to connect these clusters?" This strict criterion requires that all points in the resulting merged cluster be relatively close to each other.

Complete linkage has very different characteristics:

• It creates compact, spherical clusters: Because it considers the worst-case distance, complete linkage tends to produce tight, ball-shaped clusters where all points are close together.
• It's less sensitive to outliers: A single outlier won't dramatically affect the cluster distance, since we're looking at the maximum distance anyway.
• It may break up natural clusters: If a natural cluster isn't perfectly spherical, perhaps it's elongated or has a complex shape, complete linkage may split it into multiple smaller clusters.

Complete linkage is like a perfectionist who wants everything to be tightly organized. It creates clean, compact groups, but it might miss clusters that don't fit the "round" assumption.

Average Linkage: The Balanced Approach

Between these two extremes, average linkage provides a balanced approach by considering all pairwise distances between points in the two clusters:

$$d_{average}(A, B) = \frac{1}{|A| \cdot |B|} \sum_{a \in A} \sum_{b \in B} d(a, b)$$

where:

• $A$: the first cluster (a set of data points)
• $B$: the second cluster (a set of data points)
• $|A|$: the number of data points in cluster $A$ (cardinality of set $A$)
• $|B|$: the number of data points in cluster $B$ (cardinality of set $B$)
• $a$: a data point belonging to cluster $A$
• $b$: a data point belonging to cluster $B$
• $d(a, b)$: the distance between points $a$ and $b$ (using the chosen distance metric)
• $\sum$: the summation operator (sums over all pairs of points)

This formula computes the average of all possible distances between points in cluster A and points in cluster B. By considering every pair, average linkage measures cluster similarity in a way that:

• Balances compactness and flexibility: It's stricter than single linkage because it requires overall similarity rather than one close pair, and more flexible than complete linkage because it does not require the worst-case distance to be small.
• Reflects the overall relationship: Rather than focusing on the best or worst connection, it considers the typical relationship between clusters.
• Often matches real-world structure: In practice, average linkage tends to produce clusters that better reflect the natural structure of real-world data, making it a popular default choice.

Average linkage is like a thoughtful analyst who considers all the evidence. It provides a balanced view that often captures meaningful patterns without the extremes of optimism or perfectionism.

The choice of linkage criterion fundamentally shapes what clusters we discover. Single linkage finds chains and complex shapes but can create spurious connections. Complete linkage finds compact spheres but may miss natural elongated clusters. Average linkage provides a practical middle ground that often works well in practice. Understanding these trade-offs helps us choose the right criterion for our specific data and goals.

Now that we understand how to measure distances between points and between clusters, we can assemble these pieces into a complete algorithm. The word "agglomerative" means "to collect into a mass," which describes what this algorithm does: it starts with individual points and gradually collects them into larger and larger clusters, building a complete hierarchy in the process.

The algorithm's strategy is straightforward: begin with each data point as its own cluster, then repeatedly merge the two most similar clusters until everything belongs to one big cluster. This process creates a complete hierarchy of clusterings, from $n$ clusters (one per point) all the way down to 1 cluster (everything together). A key property of this approach is that we get a solution for every possible number of clusters in a single run. We can examine the data at any level of granularity we choose.

Let's walk through the algorithm step by step, understanding what each step does, why it's necessary, and how it builds toward the complete hierarchy.

Step 1: Initialize with Individual Points

We start with the simplest possible clustering: each data point is its own cluster. If we have $n$ data points, we have $n$ clusters:

$$C_1 = \{x_1\}, C_2 = \{x_2\}, \ldots, C_n = \{x_n\}$$

where:

• $n$: the total number of data points in the dataset
• $C_i$: the $i$-th cluster (initially containing only point $x_i$)
• $x_i$: the $i$-th data point (a vector with $d$ features)
• $\{x_i\}$: a set containing only the point $x_i$

At this stage, every cluster contains exactly one point, so there's no ambiguity about cluster membership. This initialization gives us a clean starting point where we know exactly what each cluster contains. From here, we'll build upward, merging clusters to create larger groups.

Step 2: Compute the Initial Distance Matrix

Next, we calculate the distance between every pair of clusters. Initially, since each cluster contains only one point, this is simply the distance between individual points using our chosen distance metric (Euclidean, standardized Euclidean, etc.):

$$D_{ij} = d(x_i, x_j) \quad \text{for all } i, j \in \{1, 2, \ldots, n\}$$

where:

• $D_{ij}$: the distance between clusters $C_i$ and $C_j$ (entry in row $i$, column $j$ of the distance matrix)
• $d(x_i, x_j)$: the distance between data points $x_i$ and $x_j$ (using the chosen distance metric)
• $x_i$: the $i$-th data point
• $x_j$: the $j$-th data point
• $i, j$: indices ranging from 1 to $n$
• $n$: the total number of data points

This creates an $n \times n$ distance matrix where entry $D_{ij}$ tells us how far apart clusters $C_i$ and $C_j$ are. The matrix has several important properties:

• Symmetry: $D_{ij} = D_{ji}$ (distance from $i$ to $j$ equals distance from $j$ to $i$)
• Zero diagonal: $D_{ii} = 0$ (each point is distance zero from itself)
• Triangle inequality: For most distance metrics, $D_{ik} \leq D_{ij} + D_{jk}$ (the direct distance is never longer than going through an intermediate point)

This distance matrix is our "map" of relationships between all points. It tells us, at a glance, which points are similar and which are different.

Step 3: Find the Closest Clusters

Now we search through our distance matrix to find the pair of clusters that are closest together:

$$(i^*, j^*) = \arg\min_{i,j} D_{ij}$$

where:

• $i^*$: the index of the first cluster in the closest pair
• $j^*$: the index of the second cluster in the closest pair
• $D_{ij}$: the distance between clusters $C_i$ and $C_j$
• $\arg\min$: the argument of the minimum operator (finds the indices that minimize the distance)
• $i, j$: indices ranging over all pairs of clusters

The notation $\arg\min$ means "find the arguments (indices) that minimize the distance." In other words, we're finding which two clusters have the smallest distance between them. These are the clusters we'll merge next.

This step embodies the core principle of hierarchical clustering: merge the most similar clusters first. This greedy approach, making the locally optimal choice at each step, is what makes the algorithm computationally tractable. While it doesn't guarantee a globally optimal clustering (which would be computationally intractable), it produces meaningful hierarchies that reflect the natural structure of the data.

Step 4: Merge the Closest Clusters

We combine the two closest clusters into a single new cluster:

$$C_{new} = C_{i^*} \cup C_{j^*}$$

where:

• $C_{new}$: the newly created cluster formed by merging $C_{i^*}$ and $C_{j^*}$
• $C_{i^*}$: the first cluster to be merged (the cluster at index $i^*$)
• $C_{j^*}$: the second cluster to be merged (the cluster at index $j^*$)
• $\cup$: the set union operator (combines all points from both clusters)

The union symbol ($\cup$) means we're taking all points from both clusters and putting them together. After this merge, we now have $n-1$ clusters instead of $n$. This reduction continues with each merge until we eventually have just one cluster containing all points.

Step 5: Update the Distance Matrix

This is where the algorithm gets particularly interesting. After merging two clusters, we need to update our distance matrix to reflect the new cluster structure. We remove the rows and columns corresponding to the two merged clusters and add a new row and column for the merged cluster.

The distance from the new cluster $C_{new}$ to any other cluster $C$ is calculated using our chosen linkage criterion:

$$d(C_{new}, C) = \text{linkage\_function}(C_{i^*}, C_{j^*}, C)$$

The exact formula depends on which linkage criterion we're using:

• Single linkage: $d(C_{new}, C) = \min(d(C_{i^*}, C), d(C_{j^*}, C))$
• Complete linkage: $d(C_{new}, C) = \max(d(C_{i^*}, C), d(C_{j^*}, C))$
• Average linkage: $d(C_{new}, C) = \frac{|C_{i^*}|}{|C_{new}|} \cdot d(C_{i^*}, C) + \frac{|C_{j^*}|}{|C_{new}|} \cdot d(C_{j^*}, C)$

where:

• $C_{new}$: the newly merged cluster ($C_{i^*} \cup C_{j^*}$)
• $C$: any other existing cluster
• $C_{i^*}$: the first cluster that was merged to form $C_{new}$
• $C_{j^*}$: the second cluster that was merged to form $C_{new}$
• $d(C_{i^*}, C)$: the distance from cluster $C_{i^*}$ to cluster $C$ (from the previous distance matrix)
• $d(C_{j^*}, C)$: the distance from cluster $C_{j^*}$ to cluster $C$ (from the previous distance matrix)
• $|C_{i^*}|$: the number of points in cluster $C_{i^*}$
• $|C_{j^*}|$: the number of points in cluster $C_{j^*}$
• $|C_{new}|$: the number of points in the merged cluster ($|C_{i^*}| + |C_{j^*}|$)

The key insight is that we can compute these distances efficiently using only the existing distances and cluster sizes, without recalculating all pairwise distances from scratch. This efficiency is important for which makes the algorithm practical on real datasets.

Step 6: Repeat Until Complete

We repeat steps 3-5, each time merging the two closest clusters, until only one cluster remains. This process creates a binary tree structure called a dendrogram, where:

• Each leaf node represents an individual data point
• Each internal node represents a merge operation
• The height of each node corresponds to the distance at which the clusters were merged

The dendrogram is more than just a visualization. It's a complete record of the clustering process. By "cutting" the dendrogram at different heights, we can extract different numbers of clusters, making it easy to explore the data at multiple levels of granularity. A large gap in the merging distances (a long horizontal line in the dendrogram) suggests a natural separation point where clusters are clearly distinct.

The hierarchical clustering algorithm has several important mathematical properties that shape both its behavior and its limitations. Understanding these properties helps us appreciate why the algorithm works well in some situations and struggles in others.

The Greedy Nature: Local Optimality

Hierarchical clustering is a greedy algorithm, meaning that at each step, it makes the locally optimal choice (merging the two closest clusters) without considering how this decision might affect future merges. Like a chess player who makes the best immediate move without thinking several moves ahead, the algorithm can sometimes make choices that lead to suboptimal overall clustering.

However, this greedy approach is what makes the algorithm computationally tractable. If we tried to find the globally optimal clustering by considering all possible merge sequences, the problem would become computationally intractable for even moderately sized datasets. The number of possible cluster hierarchies grows exponentially with the number of points, making exhaustive search impractical.

The greedy strategy works well in practice because natural clusters tend to be well-separated. If two points belong together, they'll be close at every level of the hierarchy. The algorithm's local decisions usually align with the global structure we want to discover.

The Dendrogram: A Complete Hierarchy

The algorithm produces a binary tree structure called a dendrogram, where each internal node represents a merge operation. The height of each node in the dendrogram corresponds to the distance at which the clusters were merged. This visualization is powerful because it shows the complete clustering hierarchy at a glance.

The dendrogram has several important properties:

• Completeness: It contains information about clustering at every possible number of clusters, from $n$ down to 1
• Monotonicity: The merge distances are non-decreasing as we move up the tree (clusters merge at increasing distances)
• Interpretability: Large gaps in merge distances indicate natural cluster boundaries

By examining the dendrogram, we can identify natural cut points. These are heights where clusters were merged at much larger distances than previous merges, suggesting that the clusters below this point are clearly distinct.

Efficient Distance Updates: The Lance-Williams Formula

The distance matrix update step maintains the algorithm's efficiency. After each merge, we could recalculate all distances from scratch by computing distances between all pairs of points in the new and existing clusters, but this would be computationally expensive.

Instead, we use update formulas that allow us to compute the distance from the newly merged cluster to any other cluster using only the existing distances and cluster sizes. For average linkage, this is the Lance-Williams formula:

$$d(C_{new}, C) = \frac{|C_{i^*}|}{|C_{i^*}| + |C_{j^*}|} \cdot d(C_{i^*}, C) + \frac{|C_{j^*}|}{|C_{i^*}| + |C_{j^*}|} \cdot d(C_{j^*}, C)$$

where:

• $C_{new}$: the newly merged cluster ($C_{i^*} \cup C_{j^*}$)
• $C$: any other existing cluster
• $C_{i^*}$: the first cluster that was merged to form $C_{new}$
• $C_{j^*}$: the second cluster that was merged to form $C_{new}$
• $d(C_{new}, C)$: the distance from the merged cluster $C_{new}$ to cluster $C$
• $d(C_{i^*}, C)$: the distance from cluster $C_{i^*}$ to cluster $C$ (from the previous distance matrix)
• $d(C_{j^*}, C)$: the distance from cluster $C_{j^*}$ to cluster $C$ (from the previous distance matrix)
• $|C_{i^*}|$: the number of points in cluster $C_{i^*}$
• $|C_{j^*}|$: the number of points in cluster $C_{j^*}$

This formula is a weighted average of the distances from the two original clusters to cluster $C$, where the weights are proportional to the sizes of the original clusters. The larger cluster gets more weight in the calculation, which makes intuitive sense: if cluster $A$ has 100 points and cluster $B$ has 10 points, the merged cluster's distance to $C$ should be closer to $A$'s distance than to $B$'s distance.

This efficient update mechanism is what makes hierarchical clustering practical for datasets with thousands of points, even though the overall complexity is still $O(n^3)$ for computing the initial distance matrix and $O(n^2)$ for the merging process. Without these update formulas, the algorithm would be prohibitively slow for even moderate-sized datasets.

Computational Complexity: The Trade-off

The algorithm's computational requirements are an important consideration:

• Time complexity: $O(n^3)$ for most implementations, due to the need to compute and update the distance matrix
• Space complexity: $O(n^2)$ for storing the distance matrix
• Practical limits: Typically used for datasets with fewer than several thousand points

This complexity is the price we pay for the algorithm's completeness, which is the ability to examine clustering at every possible level of granularity. For larger datasets, we often need to use sampling strategies, approximate methods, or alternative clustering algorithms that scale better.

Together, these mathematical properties (the greedy strategy, the complete dendrogram, and the efficient update mechanisms) define how hierarchical clustering works and when it's most appropriate to use. The algorithm's strength lies in providing a complete, interpretable hierarchy that reveals the natural structure of data at multiple scales, while its limitations come from computational requirements and sensitivity to certain data characteristics.