Hierarchical clustering is a family of unsupervised machine learning algorithms used to group similar data points into clusters based on a distance or similarity measure. Unlike partition-based methods (e.g., k-means), hierarchical clustering builds a tree-like structure (dendrogram) that shows the nested relationships between clusters. The two main approaches are agglomerative (bottom-up, merging clusters) and divisive (top-down, splitting clusters). The choice of linkage criterion (e.g., single, complete, average, Ward) determines how distances between clusters are computed. Hierarchical clustering is widely applied in bioinformatics (gene expression analysis), document clustering, image segmentation, and social network analysis, among other fields.

1 Fundamentals

1.1 Definition and Intuition

Hierarchical clustering is a method of cluster analysis that seeks to build a hierarchy of clusters. The core intuition is that clusters are not flat but nested: larger clusters contain smaller, more similar subgroups. This is represented by a dendrogram, a binary tree whose leaves correspond to individual data points and whose internal nodes represent clusters formed at various levels of similarity.

1.2 Distance Measures

Distance or similarity measures quantify how close two data points are. The choice of measure strongly influences the resulting hierarchy.

1.2.1 Euclidean Distance

Euclidean distance is the ordinary straight‑line distance between two points in Euclidean space. For points \(p\) and \(q\) with coordinates \((p_1,\dots,p_n)\) and \((q_1,\dots,q_n)\), it is defined as \(\sqrt{\sum_{i=1}^n (p_i - q_i)^2}\). It is the most common metric in hierarchical clustering when features are continuous and of comparable scale.

1.2.2 Manhattan Distance

Manhattan distance (or L1 distance) sums the absolute differences of coordinates: \(\sum_{i=1}^n |p_i - q_i|\). It is less sensitive to outliers than Euclidean distance and is useful when features are measured on different scales or when the grid‑like movement is natural (e.g., in urban geometry).

1.2.3 Cosine Similarity

Cosine similarity measures the cosine of the angle between two vectors: \(\frac{p \cdot q}{\|p\| \|q\|}\). It ranges from −1 to 1 and is often used for text data (term‑frequency vectors) where magnitude is irrelevant. For hierarchical clustering it is typically converted to a distance (e.g., \(1 - \text{cosine similarity}\)).

1.2.4 Other Distance Metrics

Other common metrics include correlation‑based distances (e.g., Pearson correlation), Mahalanobis distance (accounts for feature correlations), and Hamming distance (for categorical binary data). The choice depends on the data type and the domain.

1.3 Dendrogram

1.3.1 Construction

A dendrogram is a tree diagram where each leaf represents a data point, and each internal node marks the merger (or split) of two clusters. The vertical axis (or horizontal, in some layouts) indicates the distance or dissimilarity at which clusters are joined. Leaves are arranged so that similar groups appear adjacent.

1.3.2 Interpretation

The dendrogram shows the entire clustering history. By “cutting” the tree at a chosen height, the user obtains a set of flat clusters. A higher cut produces fewer clusters; a lower cut yields more clusters. The order of leaves does not imply a one‑dimensional ordering but reflects the clustering structure.

2 Types of Hierarchical Clustering

2.1 Agglomerative Clustering

2.1.1 Algorithm Steps

1. Initially treat each data point as its own cluster. 2. Compute a proximity matrix of distances between all clusters. 3. Find the two closest clusters (according to the chosen linkage criterion) and merge them. 4. Update the proximity matrix to reflect distances between the new cluster and the remaining clusters. 5. Repeat steps 3–4 until only one cluster remains.

2.1.2 Complexity

The standard implementation has time complexity \(O(n^3)\) in the worst case, but with optimizations (e.g., using a priority queue) it can be reduced to \(O(n^2 \log n)\) or \(O(n^2)\) for certain linkages (e.g., single linkage). Memory complexity is \(O(n^2)\) due to the proximity matrix.

2.2 Divisive Clustering

2.2.1 Algorithm Steps

1. Start with all data points in one cluster. 2. Split the cluster into two sub‑clusters (using a flat clustering algorithm such as k‑means or a monothetic/polythetic method). 3. Recursively apply splitting to each sub‑cluster until each point forms its own cluster or a stopping criterion is met.

2.2.2 Complexity

Divisive clustering is computationally more expensive than agglomerative because it evaluates many possible splits at each step. The complexity is often \(O(2^n)\) in naïve implementations, though heuristic methods (e.g., bisecting k‑means) reduce it to roughly \(O(n \log n)\) per split.

2.3 Comparison Between Agglomerative and Divisive

Agglomerative clustering builds the hierarchy from the bottom up and is more common in practice due to its simpler implementation and lower complexity. Divisive clustering is less used but can be advantageous when a global top‑down perspective is needed, or when the number of clusters is very small. Both approaches produce the same tree for some linkage criteria if the algorithm is deterministic and the distance matrix is ultrametric, but generally they yield different hierarchies.

3 Linkage Criteria

3.1 Single Linkage (Minimum)

Distance between two clusters is defined as the minimum distance between any point in the first cluster and any point in the second. It tends to produce long, chain‑like clusters and is sensitive to noise.

3.2 Complete Linkage (Maximum)

Distance between clusters is the maximum distance between any point in one cluster and any point in the other. It produces compact, spherical clusters but is sensitive to outliers.

3.3 Average Linkage

3.3.1 Unweighted Pair Group Method with Arithmetic Mean (UPGMA)

The distance between two clusters is the arithmetic mean of all pairwise distances between points in the two clusters. It assumes equal weights for all points and is widely used in bioinformatics.

3.3.2 Weighted Pair Group Method with Arithmetic Mean (WPGMA)

Similar to UPGMA but treats clusters as equal regardless of size, assigning equal weight to each cluster when computing the average. It is less common.

3.4 Centroid Linkage

Distance between clusters is the distance between their centroids (mean vectors). The resulting hierarchy can be non‑monotonic (i.e., reversals in the dendrogram) and is sensitive to cluster size differences.

3.5 Ward’s Method (Minimum Variance)

Ward’s method merges the two clusters that minimize the increase in total within‑cluster variance after the merge. It tends to produce compact, equally sized clusters and is computationally efficient using Lance‑Williams updates.

3.6 Comparison of Linkage Criteria

  • Single linkage: chaining effect, useful for elongated shapes.
  • Complete linkage: compact clusters, outlier‑sensitive.
  • Average linkage: compromise, often robust.
  • Centroid linkage: may produce inversions.
  • Ward’s method: variance‑based, assumes spherical clusters.

Empirical performance depends on data distribution and application domain.

4 Algorithm Details

4.1 Agglomerative Hierarchical Clustering

4.1.1 Proximity Matrix

The algorithm begins by computing an \(n \times n\) distance matrix (or similarity matrix) of all pairwise distances between data points. This matrix is updated after each merge.

4.1.2 Merging Process

At each iteration, the two clusters with the smallest distance according to the chosen linkage are merged. The merged cluster’s distances to others are recalculated using the Lance‑Williams recurrence formula, which generalizes all common linkage criteria.

4.1.3 Computational Complexity

The naïve implementation has \(O(n^3)\) time. Priority‑queue‑based implementations (e.g., nearest‑neighbor chain algorithm for single/complete linkage) achieve \(O(n^2)\). For average linkage and Ward’s method, \(O(n^2)\) is typical. Memory is dominated by the \(O(n^2)\) proximity matrix.

4.2 Divisive Hierarchical Clustering

4.2.1 Monothetic vs. Polythetic

  • Monothetic division: splits are based on a single attribute (one variable). Simple but may not capture multivariate structure.
  • Polythetic division: uses all attributes (e.g., k‑means, principal component analysis). More common and flexible.

4.2.2 Bisecting k‑means

A fast divisive approach: at each step, the largest (or most heterogeneous) cluster is split into two using k‑means with \(k=2\). The recursion continues until a desired number of clusters or until each cluster is a leaf. Complexity is roughly \(O(n \log k)\).

5 Choosing the Number of Clusters

5.1 Dendrogram Cutting

The simplest method: cut the dendrogram at a chosen height or distance threshold. The number of clusters is then the number of branches that cross the cut line. The cut height can be selected by visual inspection or by domain knowledge.

5.2 Inconsistent Coefficient

This coefficient evaluates the depth of each merge relative to surrounding merges. A merge with a large inconsistent value suggests a natural cluster boundary. The coefficient is computed as the ratio of the merge distance to the average distance of merges at the same level.

5.3 Silhouette Index

For a given number of clusters \(k\), the silhouette coefficient measures how similar a point is to its own cluster compared to other clusters. The optimal \(k\) maximizes the average silhouette width over all points.

5.4 Gap Statistic

The gap statistic compares the total within‑cluster dispersion (e.g., sum of squared distances) for the observed data with that expected under a null reference distribution. The number of clusters is chosen where the gap is largest (or where the gap stops increasing significantly).

6 Applications

6.1 Bioinformatics

6.1.1 Gene Expression Analysis

Hierarchical clustering is used to group genes with similar expression profiles across conditions. The resulting dendrograms help identify co‑expressed gene modules and regulatory pathways. Heatmaps often pair a dendrogram with a color‑coded matrix.

6.1.2 Phylogenetic Trees

In evolutionary biology, hierarchical clustering (especially UPGMA and neighbor‑joining) constructs phylogenetic trees that depict evolutionary relationships among species or sequences based on genetic distances.

6.2 Document and Text Clustering

Documents (e.g., news articles, research papers) are represented as term‑frequency vectors. Hierarchical clustering groups similar texts, enabling topic discovery, document organization, and information retrieval.

6.3 Image Segmentation

Image pixels or superpixels are clustered based on features such as color, texture, or spatial coordinates. Hierarchical methods produce multiscale segmentations that can be examined at different levels of detail.

6.4 Social Network Analysis

Users or nodes in a social network are clustered based on connectivity or attribute similarity. Hierarchical clustering reveals community structure at multiple scales, from small cliques to large‑scale groups.

6.5 Other Domains

  • Marketing: customer segmentation based on purchase patterns.
  • Climate science: grouping weather stations or climate zones.
  • Neuroscience: clustering brain regions based on functional connectivity.
  • Astronomy: grouping stars or galaxies by spectral features.

7 Advantages and Limitations

7.1 Advantages

7.1.1 No Pre‑specified Number of Clusters

Hierarchical clustering does not require the user to specify the number of clusters beforehand. The dendrogram allows exploration of clusterings at any granularity.

7.1.2 Hierarchical Interpretation

The dendrogram provides a visual and interpretable representation of data structure, including nested relationships that flat clustering cannot show.

7.1.3 Works with Non‑Globular Shapes

With single linkage, hierarchical clustering can capture irregular, elongated, or chain‑like cluster shapes, unlike k‑means which assumes convex clusters.

7.2 Limitations

7.2.1 High Computational Cost

The need to compute and store an \(n \times n\) distance matrix makes hierarchical clustering impractical for very large datasets (e.g., millions of points).

7.2.2 Sensitivity to Noise and Outliers

Outliers can create spurious clusters or cause early merges that distort the hierarchy, especially with single or centroid linkage.

7.2.3 Difficulty with Large Datasets

Both memory (\(O(n^2)\)) and time (\(O(n^3)\) or \(O(n^2)\)) scale poorly. Even with optimizations, datasets exceeding tens of thousands of points become challenging.

8 Variants and Extensions

8.1 Constrained Hierarchical Clustering

Spatial or relational constraints (e.g., contiguity in a map) are enforced so that only clusters that are adjacent in a defined graph can be merged. This is used in geographic or image segmentation.

8.2 Hierarchical Clustering with Categorical Data

Standard distance measures (e.g., Euclidean) do not apply directly. Variants use matching coefficients (e.g., Jaccard, Hamming) or binary encoding. Linkage criteria remain the same.

8.3 Approximate Hierarchical Clustering (e.g., BIRCH)

BIRCH (Balanced Iterative Reducing and Clustering using Hierarchies) pre‑clusters the data into a tree (CF‑tree) and then applies hierarchical clustering on the compressed representation. It handles large datasets by reducing the effective \(n\). Other approximations include using k‑d trees or nearest‑neighbor graphs.

9.1 Partitional Clustering (k‑means, DBSCAN)

Partitional methods produce a flat partition of the data, often requiring a pre‑specified number of clusters. k‑means assumes spherical clusters; DBSCAN handles arbitrary shapes but does not produce a hierarchy. Hierarchical clustering offers more structure but at higher cost.

9.2 Ensemble Clustering

Multiple clustering solutions (from different algorithms or random initializations) are combined to produce a robust result. Hierarchical clustering can serve as a base learner or as a way to generate a consensus dendrogram.

9.3 Evaluation of Clustering Results

Internal indices (e.g., silhouette, Dunn index) assess compactness and separation without ground truth. External indices (e.g., adjusted Rand index, normalized mutual information) compare a clustering to a predefined reference. Dendrogram‑specific evaluations include the cophenetic correlation coefficient, which measures how faithfully the dendrogram preserves pairwise distances.