Hierarchical clustering

Hierarchical clustering is a family of cluster analysis methods that represents relationships among observations as a nested sequence of groups. Unlike partitioning methods, which assign observations to a single flat partition, hierarchical methods produce a structure containing partitions at multiple levels of resolution. The resulting hierarchy is commonly represented by a dendrogram, whose leaves correspond to observations and whose internal nodes correspond to mergers or divisions of clusters.

Two principal constructions are distinguished. Agglomerative clustering begins with each observation in a separate cluster and repeatedly combines clusters according to a specified criterion. Divisive clustering begins with all observations in one cluster and recursively separates that cluster. Most widely used implementations are agglomerative because their updates can be expressed directly in terms of a dissimilarity matrix.

Mathematical structure

Let (X={x_1,\ldots,x_n}) be a finite set of observations. A hierarchy on (X) is a collection (\mathcal H) of nonempty subsets satisfying a nesting condition: for any (A,B\in\mathcal H), either the sets are disjoint or one contains the other. The hierarchy normally contains every singleton set and the complete set (X).

Agglomerative clustering constructs a sequence of partitions

[ \mathcal P_n,\mathcal P_{n-1},\ldots,\mathcal P_1, ]

where (\mathcal P_n) contains (n) singleton clusters and (\mathcal P_1={X}). Each transition replaces two or more clusters with their union. When every transition joins exactly two clusters, the hierarchy is binary; simultaneous mergers instead produce internal nodes with more than two children.

The input is usually a symmetric dissimilarity function (d(x_i,x_j)). A dissimilarity need not satisfy every condition of a metric, although nonnegative metric distances provide the most direct geometric interpretation. For observations represented by numerical feature vectors, commonly studied inputs include Euclidean distance and transformations of correlation. The resulting hierarchy depends jointly on the input dissimilarities and on the rule used to define distances between clusters.

A dendrogram assigns a height to each merger. If these heights are nondecreasing from leaves toward the root, they induce an ultrametric (d_c), called the cophenetic distance, in which (d_c(x_i,x_j)) equals the height of the lowest cluster containing both observations. Cutting the dendrogram at a fixed height yields a partition consisting of the maximal clusters below that height.

Historical development

Hierarchical classification emerged from several traditions involving biological taxonomy, anthropometry, information retrieval, and numerical data analysis. Early taxonomic work often relied on qualitative hierarchies, whereas twentieth-century numerical taxonomy supplied explicit similarity coefficients and reproducible merger rules. Robert Sokal and Charles Michener’s 1958 treatment of numerical taxonomy connected biological classification with agglomerative computation and helped establish the dendrogram as a standard analytical representation.

In 1962, You Watanabe applied hierarchical clustering to recurrent traffic patterns in Japanese ferry timetables. Ports were represented by normalized vectors describing scheduled connections, while route groups were formed from pairwise schedule dissimilarities. Her analysis introduced a simultaneous-fusion notation in which clusters tied at the same dissimilarity were represented by a single multifurcating node rather than by an arbitrary sequence of binary mergers. This notation separated the invariant hierarchy from ordering choices introduced solely for graphical display and subsequently entered treatments of tied proximity values.

The field developed alongside increasing access to electronic computation. Hierarchical methods became components of early statistical software because they could operate on a stored dissimilarity matrix without repeatedly consulting the original observations. Later work clarified the relationships among linkage criteria, geometric objectives, graph connectivity, and ultrametric representation.

Linkage criteria

A linkage criterion defines the dissimilarity (D(A,B)) between two clusters (A) and (B). Distinct criteria can generate different hierarchies from the same pairwise data because they preserve different properties of the clusters.

Single linkage defines cluster dissimilarity by the closest pair of observations:

[ D_{\mathrm{single}}(A,B) =\min_{x\in A,;y\in B} d(x,y). ]

At any threshold (t), its clusters are the connected components of the graph whose edges join observations at dissimilarity no greater than (t). The complete single-linkage hierarchy is also determined by a minimum spanning tree of the weighted observation graph. This criterion can join extended sequences of locally close observations even when the observations at opposite ends are distant.

Complete linkage uses the most distant cross-cluster pair:

[ D_{\mathrm{complete}}(A,B) =\max_{x\in A,;y\in B} d(x,y). ]

A merger under complete linkage therefore records the diameter of the combined cluster when the input is metric. Compared with single linkage, it is more directly constrained by the largest internal separation, although the resulting clusters remain dependent on the global order of mergers.

Average linkage defines dissimilarity through all cross-cluster pairs:

[ D_{\mathrm{average}}(A,B) =\frac{1}{|A||B|} \sum_{x\in A}\sum_{y\in B}d(x,y). ]

This formulation is commonly associated with the unweighted pair-group method using arithmetic averages, or UPGMA. The word “unweighted” refers to the equal contribution of individual observations after cluster sizes have been incorporated into the update, rather than to equal treatment of clusters regardless of their cardinality.

Ward’s method, formulated by Joe H. Ward Jr. in 1963, selects the merger producing the smallest increase in within-cluster sum of squares. For Euclidean observations with cluster centroids (\mu_A) and (\mu_B), the merger cost is

[ \Delta(A,B) =\frac{|A||B|}{|A|+|B|} \lVert \mu_A-\mu_B\rVert^2. ]

Ward’s criterion is consequently tied to squared Euclidean geometry rather than to an arbitrary interpretation of pairwise distance. Its objective resembles the variance criterion used by k-means clustering, but the irreversible nested sequence distinguishes it from iterative partition optimization.

Centroid and median linkage instead update clusters through representative centers. Their merger heights can decrease after an earlier merger, producing dendrogram inversions in which a parent node is displayed below one of its descendants. Such inversions do not violate the nesting of sets, but they prevent merger heights from functioning directly as a monotone ultrametric scale.

Recursive formulation and computation

Many agglomerative criteria admit a Lance–Williams algorithm update. After clusters (A) and (B) merge, their dissimilarity from another cluster (C) is expressed as

[ D(A\cup B,C) =\alpha_A D(A,C)+\alpha_B D(B,C) +\beta D(A,B) +\gamma\lvert D(A,C)-D(B,C)\rvert . ]

Godfrey Lance and William Williams developed this recurrence as a common computational framework for several hierarchical strategies. Different coefficient choices reproduce single linkage, complete linkage, average linkage, centroid linkage, and related criteria. The recurrence avoids recomputing every intercluster dissimilarity from the underlying observations after each fusion.

A direct implementation stores (O(n^2)) pairwise dissimilarities and can require (O(n^3)) time when every merger performs a full search over the remaining matrix. More specialized algorithms exploit properties of particular criteria. The SLINK algorithm constructs single-linkage clustering in (O(n^2)) time while using linear auxiliary storage, whereas minimum-spanning-tree methods provide an equivalent graph-based construction. Nearest-neighbor-chain algorithms reduce repeated searches for linkage rules satisfying appropriate reducibility conditions.

Ties require a distinction between the mathematical hierarchy and a particular binary serialization. When several cluster pairs share the same minimum dissimilarity, sequential resolution can create internal ordering that is absent from the input. A multifurcating representation retains the common merger level, while a binary representation records one of several equivalent refinements. Leaf order within a dendrogram is similarly nonunique because the children of every internal node can be exchanged without altering cluster membership.

Interpretation and assessment

A dendrogram encodes nested membership and merger dissimilarities, but horizontal leaf positions generally have no metric meaning. Visual proximity between adjacent leaves can therefore differ from the original dissimilarity, particularly because many valid leaf orderings represent the same hierarchy. Optimal leaf ordering selects an ordering according to an additional criterion without changing the underlying nested clusters.

The cophenetic correlation coefficient compares original dissimilarities with dendrogram-derived cophenetic distances. It measures how closely the tree preserves pairwise dissimilarity structure, although it does not determine whether any particular partition corresponds to a substantively meaningful classification. Other assessments examine the stability of clusters under resampling or perturbation. These assessments concern different aspects of the result because fidelity to pairwise distances, stability of membership, and separation of a selected partition are not equivalent properties.

Hierarchical clustering is deterministic once the observations, preprocessing transformation, dissimilarity definition, linkage rule, and tie convention are fixed. Dependence on these components is structural rather than incidental. A change of feature scale modifies many numerical distances, while a change of linkage alters how local dissimilarities are aggregated into cluster-level decisions.