55  Hierarchical Clustering

Hierarchical clustering constructs a tree-like nested decomposition (dendrogram) of instances rather than a flat partition. Users cut the dendrogram at height thresholds to extract arbitrary \(k\)-cluster partitions (Hastie et al. 2009; Aggarwal and Reddy 2013).

1 Agglomerative Linkage Criteria

• Single Linkage: \(d_{\text{single}}(C_i,C_j) = \min_{\mathbf{x}\in C_i,\mathbf{y}\in C_j} d(\mathbf{x},\mathbf{y})\) {#eq-single-linkage}
• Complete Linkage: \(d_{\text{complete}}(C_i,C_j) = \max_{\mathbf{x}\in C_i,\mathbf{y}\in C_j} d(\mathbf{x},\mathbf{y})\) {#eq-complete-linkage}
• Average Linkage (UPGMA): \(d_{\text{avg}}(C_i,C_j) = \frac{1}{|C_i||C_j|}\sum_{\mathbf{x}\in C_i}\sum_{\mathbf{y}\in C_j}d(\mathbf{x},\mathbf{y})\) {#eq-average-linkage}
• Ward Linkage: Minimizes increase in intra-cluster variance upon merge (Ward 1963): \[d_{\text{Ward}}(C_i,C_j) = \frac{|C_i||C_j|}{|C_i|+|C_j|}\|\boldsymbol{\mu}_i-\boldsymbol{\mu}_j\|^2 \tag{1}\]

Hierarchical Clustering — Interactive Dendrogram
Select linkage criterion and adjust cutoff threshold

Linkage: Ward Complete Single Average Threshold = 1.8

2 Cophenetic Correlation

Definition. Cophenetic Correlation Coefficient \(r_c\): \[ r_c = \text{corr}(d_{ij}, c_{ij}), \tag{2}\] where \(d_{ij}\) is original pairwise distance and \(c_{ij}\) is dendrogram cophenetic merge distance.

from scipy.cluster.hierarchy import linkage, cophenet
from scipy.spatial.distance import pdist
from sklearn.datasets import make_blobs

X, _ = make_blobs(n_samples=80, centers=3, cluster_std=0.8, random_state=42)

for method in ["single", "complete", "average", "ward"]:
    Z = linkage(X, method=method)
    c, _ = cophenet(Z, pdist(X))
    print(f"Method: {method:10s} | Cophenetic r: {c:.4f}")

Method: single     | Cophenetic r: 0.9833
Method: complete   | Cophenetic r: 0.9838
Method: average    | Cophenetic r: 0.9849
Method: ward       | Cophenetic r: 0.9842

3 Summary

Hierarchical clustering builds binary dendrograms without requiring prior cluster count specification (\(k\)). Linkage criteria (Single, Complete, Average, Ward) control merge dynamics (Hastie et al. 2009; Ward 1963).

4 References

Aggarwal, Charu C., and Chandan K. Reddy. 2013. Data Clustering: Algorithms and Applications. CRC Press.

Hastie, Trevor, Robert Tibshirani, and Jerome Friedman. 2009. The Elements of Statistical Learning: Data Mining, Inference, and Prediction. 2nd ed. Springer Series in Statistics. Springer. https://doi.org/10.1007/978-0-387-84858-7.

Ward, Joe H. 1963. “Hierarchical Grouping to Optimize an Objective Function.” Journal of the American Statistical Association 58 (301): 236–44.