Hierarchical clustering is a family of methods for organizing objects into nested groups according to their similarities or dissimilarities. Rather than producing only one partition, it constructs a hierarchy in which small clusters belong to larger clusters. The result is commonly represented by a dendrogram, a branching diagram whose leaves are individual objects and whose internal nodes represent groups. In machine learning, hierarchical clustering is usually classified as unsupervised learning, because the grouping is inferred without requiring labeled examples.
Two principal approaches build the hierarchy in opposite directions. Agglomerative methods begin with separate objects and repeatedly merge clusters; divisive methods begin with a single cluster and repeatedly split it. Their outputs support analysis at several resolutions, from fine subdivisions to broad categories. Applications include grouping genes by expression patterns, organizing documents, comparing ecological communities, and exploring relationships among images or other high-dimensional observations.
A hierarchy is not uniquely determined by a dataset. Its form depends on how objects are represented, how dissimilarity is measured, which merging or splitting rule is used, and how the resulting tree is interpreted. These choices determine both the computational demands and the scientific meaning of the analysis.
Mathematical structure and tree representation
Let be a finite collection of objects. A hierarchical clustering can be described as a family of nonempty subsets of containing every singleton and the full set , with the property that any two members are either disjoint or nested. Formally, for ,
This condition distinguishes a hierarchy from a collection of overlapping clusters. An object may belong to several groups along its path toward the root, but it cannot simultaneously belong to two intersecting branches that are not nested.
The natural representation is a rooted tree. Leaves represent observations, the root represents the entire dataset, and internal nodes represent clusters. If every operation merges exactly two clusters, the result is a binary tree with leaves and internal nodes. A complete agglomerative procedure then passes through partitions with clusters. These partitions are constrained to be nested: once two observations have joined, no later operation separates them. Divisive hierarchies impose the corresponding restriction that separated branches never reunite.
A dendrogram commonly assigns each internal node a height , interpreted as the dissimilarity or objective increment at which its child clusters joined. When heights never decrease toward the root, a horizontal cut at height defines a partition. For example, suppose and merge at height 1, and merge at height 2, and the two pairs merge at height 5. A cut between 2 and 5 produces and . The horizontal positions of leaves are largely a display choice: rotating the children of a node changes the drawing without changing the clustering.
For a monotone dendrogram, define as the height of the lowest node containing both observations, and set . These cophenetic dissimilarities satisfy the strong triangle inequality
Such a distance is called an ultrametric, although distinct observations merged at zero height technically yield a pseudoultrametric. A monotone hierarchical clustering can therefore be viewed as an ultrametric representation of the original dissimilarities. This representation simplifies relationships rather than necessarily preserving them exactly. Some linkage rules produce nonmonotone heights, or inversions, for which this interpretation requires modification.
Object representation and dissimilarity
Most classical methods start from a symmetric dissimilarity matrix , with entries and . A dissimilarity need not satisfy every axiom of a metric space. For example, algorithms based on minimum, maximum, or average intercluster dissimilarities can operate on many matrices that violate the triangle inequality. Nevertheless, the meaning of the resulting clusters remains dependent on the meaning of the supplied values. An algorithm cannot determine whether a large value represents biological divergence, textual difference, measurement noise, or an arbitrary coding decision.
For numerical vectors, Euclidean distance is a common choice:
It is sensitive to the units and scales of variables. In a dataset containing annual income and age, unscaled income values may dominate the distance merely because their numerical range is larger. Feature scaling changes this geometry. Standardization divides centered values by a measure of spread; robust alternatives use quantities such as the median and interquartile range. These transformations are substantive choices, not neutral preliminaries: standardizing a noisy variable can give it influence comparable to that of a reliable one.
Different data types require different comparisons. Cosine similarity compares vector directions and is common for documents and learned representations. Correlation-based dissimilarities emphasize the shape of profiles rather than their absolute levels. Binary presence–absence data may be compared using Jaccard similarity, especially when shared absences are not informative. Hamming distance counts differing positions in equal-length sequences, whereas edit distance allows insertions and deletions. Gower dissimilarity combines variable-specific comparisons for mixed numerical and categorical data, subject to explicit weighting and missing-value conventions.
Similarity and distance are not interchangeable without specifying a transformation. For nonzero vectors normalized to unit length,
so cosine dissimilarity is proportional to squared Euclidean distance on the unit sphere. A similar relation connects correlation and Euclidean distance after suitable centering and normalization. However, a monotone transformation of dissimilarities does not preserve every hierarchy. Single and complete linkage preserve their merge ordering under strictly increasing transformations, apart from tie conventions, because minima and maxima preserve order. Average linkage need not, because averaging transformed values can change comparisons. Missing-data handling introduces further complications: distances computed from different subsets of variables may be difficult to compare, even when each individual calculation appears reasonable.
Agglomerative linkage criteria
An agglomerative method repeatedly selects two current clusters with the smallest intercluster dissimilarity. The rule defining that dissimilarity is the linkage criterion. For clusters and , single and complete linkage are
Single linkage can recover elongated or irregular groups connected by short steps, but it exhibits chaining: a sequence of intermediate observations can connect regions whose endpoints are far apart. Complete linkage resists such chains and favors groups with smaller maximum pairwise dissimilarity, but an extreme observation can strongly affect its decisions.
Average linkage uses the mean of all cross-cluster dissimilarities:
It is also called the unweighted pair-group method with arithmetic mean, or UPGMA. Here “unweighted” means that original observations contribute equally. By contrast, weighted pair-group averaging, or WPGMA, assigns equal weight to the two child clusters when updating distances, regardless of their sizes. Consequently, its effective weights on original observations depend on the merger history. The names can therefore be misleading unless the weighting convention is stated.
Ward’s method takes a different approach: it merges the pair causing the smallest increase in within-cluster sum of squares. For Euclidean vectors, let and be cluster means. The increase is
This criterion favors compact groups in a squared-Euclidean sense. Like k-means clustering, it concerns within-group dispersion, but it makes irreversible local merges rather than repeatedly reassigning observations. It does not generally produce the globally optimal partition for each number of clusters. Software packages may display Ward heights as , a scaled version of it, or its square root; input-distance and output-height conventions therefore matter.
Centroid linkage compares cluster means directly, while median linkage recursively averages child representatives with equal weights. Both can produce inversions, in which a later merge has a lower height than an earlier one. A newly formed centroid may lie closer to another cluster than either of its children did. By contrast, standard single, complete, average, and Ward procedures have monotone heights under their appropriate assumptions. No linkage criterion dominates independently of the application: single linkage encodes connectivity, complete linkage emphasizes worst-case separation, average linkage summarizes cross-group dissimilarity, and Ward’s method emphasizes increases in dispersion. These are different definitions of what constitutes a coherent group.
Algorithms, recurrences, and computational cost
The direct agglomerative algorithm initializes singleton clusters, finds the closest pair, merges it, updates relevant distances, and repeats. Scanning all current pairs at each of stages gives a straightforward implementation. Storing all original pairwise distances requires memory. A condensed matrix contains entries; for , double-precision storage alone is approximately 40 billion bytes, or 40 GB, before accounting for working arrays and program overhead. This quadratic storage burden is often the first practical obstacle.
Many linkages admit the Lance–Williams update, introduced in 1967. If and merge, their dissimilarity to another cluster is updated as
The coefficients specify the linkage. For single linkage, , , and , yielding the minimum. Complete linkage changes to , yielding the maximum. Average linkage uses , , and . Ward updates require the corresponding squared-distance or objective convention.
More efficient algorithms exploit structural properties rather than repeatedly scanning every pair. Single linkage has a close connection to a minimum spanning tree of the weighted graph on the observations. Removing edges above a threshold produces the same connected components as cutting the single-linkage hierarchy at that threshold. Robin Sibson’s SLINK algorithm, published in 1973, constructs single linkage in time with auxiliary storage when dissimilarities can be supplied as needed. Nearest-neighbor-chain algorithms achieve quadratic worst-case time for several standard linkages, including complete, average, weighted average, and Ward linkage under appropriate conventions. Centroid and median linkage do not inherit the same guarantees.
The relevant computational complexity depends on the input model. If a full arbitrary dissimilarity matrix is explicitly supplied, its size is already quadratic. If observations are vectors in a low-dimensional space, geometric methods may avoid evaluating every pair in favorable cases. A priority queue can accelerate candidate selection but requires careful management of obsolete entries. Approximate neighbor graphs, sampling, and preliminary compression can extend scalability, although they may change the hierarchy. Parallel computing accelerates distance calculations more readily than it removes dependencies between successive merges. Reported performance consequently needs to distinguish distance construction, clustering itself, storage, and dendrogram rendering.
Divisive methods and related hierarchical models
Divisive clustering starts with all observations in one group and recursively splits groups until a stopping condition is reached. A binary split need not be the reverse of any agglomerative merge: top-down and bottom-up procedures usually optimize different local decisions. An exhaustive search over all two-way partitions of a cluster containing objects considers distinct nonempty splits. Practical algorithms therefore use heuristics, geometric criteria, or restricted optimization problems. The main design questions are which current cluster to divide, how to divide it, and when to stop.
DIANA, associated with the work of Leonard Kaufman and Peter Rousseeuw, is a classical dissimilarity-based divisive method. In its usual form, it selects a cluster with a large diameter and initializes a “splinter group” using an observation with high average dissimilarity to the others. Additional observations move into that group when their average dissimilarity to the remaining group exceeds their average dissimilarity to the splinter group. The procedure then repeats on selected clusters. Unlike an exhaustive search, this is a structured heuristic; its output reflects the initial splinter choice and subsequent transfer rule.
Other divisive approaches apply a two-cluster method recursively. Bisecting k-means repeatedly divides a chosen cluster using k-means with , often testing several initializations and selecting a split by a dispersion criterion. Graph-based approaches can divide a similarity graph using cuts or spectral information. These methods accommodate different notions of separation, but their node heights do not automatically have the same meaning as agglomerative linkage distances. Moreover, recursive bisection can impose a two-way organization even where the data contain a more natural three-way or uneven subdivision.
Some methods produce hierarchies without fitting the classical pairwise-linkage framework. BIRCH, introduced in 1996, summarizes numerical observations in a clustering-feature tree before optional further clustering; its tree is primarily a compact data structure, not simply the result of exact linkage on every original pair. HDBSCAN constructs a hierarchy of density-based clusters and extracts groups according to their persistence, allowing observations to be treated as noise. Decision-tree learning also creates nested partitions, but supervised trees choose splits using target outcomes, while classical hierarchical clustering does not. Likewise, a hierarchical probabilistic model represents nested latent structure through a specified probability distribution, rather than merely recording a sequence of merges. The common tree form should not obscure these different objectives and interpretations.
Choosing a partition and assessing a hierarchy
A hierarchy separates the construction of nested groups from the choice of a final partition. A cut can specify a number of clusters , a dissimilarity threshold, or a more elaborate rule that treats branches differently. For a fully resolved binary agglomerative tree, stopping after merges yields exactly clusters. A horizontal threshold need not yield every possible , because multiple merges can share a height. Branch-specific procedures can retain fine subdivisions in one part of a tree and broad groups elsewhere, but they introduce additional assumptions and tuning choices.
Internal validation evaluates clusters using the data and dissimilarities themselves. The silhouette coefficient compares an observation’s average dissimilarity to its own cluster with its smallest average dissimilarity to another cluster:
Values near 1 indicate stronger separation under that dissimilarity, values near 0 indicate proximity to a boundary, and negative values suggest closer average association with another group. Singleton clusters require a convention, commonly a score of zero. Averaging silhouettes across observations permits comparison of candidate cuts, but it may favor compact, well-separated groups over elongated or connected structures that are meaningful under another clustering model.
A different assessment compares the original dissimilarities with cophenetic dissimilarities . Their correlation, called the cophenetic correlation coefficient, measures how well the tree preserves pairwise dissimilarity relationships in that sense. A high value indicates a faithful hierarchical representation, not proof that the dataset contains discrete natural categories. A hierarchy can represent a continuous gradient reasonably well, and a biologically meaningful partition need not maximize this coefficient. Visual separation in a dendrogram is also sensitive to axis scaling and plotting choices.
Stability analysis examines whether branches recur after perturbations such as resampling observations, resampling features, or adding measurement noise. Bootstrap resampling can quantify branch reproducibility, but the sampling unit and assumed sampling process determine what the result means. Resampling genes in a sample-clustering analysis answers a different question from resampling patients. If external labels exist, measures such as the adjusted Rand index compare a selected partition with those labels; they do not directly validate every level of the hierarchy. When clustering contributes to a later predictive study, preprocessing learned from evaluation observations can create data leakage. Stability, geometric separation, agreement with external labels, and predictive usefulness are distinct forms of evidence rather than interchangeable definitions of correctness.
Historical development
Hierarchical classification predates electronic computing. Taxonomic systems in biology organized organisms into nested categories long before numerical clustering algorithms were formalized. Such classifications drew on judgments about anatomical and other characteristics, rather than a universally specified distance matrix and update rule. The development of numerical taxonomy in the mid-twentieth century sought to make similarity assessment and grouping more explicit and reproducible. Computing made it practical to compare many characters simultaneously and to construct trees by a defined sequence of operations.
Robert Sokal and Charles Michener’s 1958 work on statistical relationships among bees is an important early reference for average-linkage numerical classification. Sokal and Peter Sneath’s Principles of Numerical Taxonomy, published in 1963, helped establish the broader program of numerical taxonomy. Peter Sneath’s 1957 work also contributed to the use of computational classification in microbiology. These developments promoted classifications based on many measured characteristics, while also raising lasting questions about character weighting, similarity coefficients, and the relationship between observed resemblance and evolutionary history.
Joe H. Ward Jr.’s 1963 paper presented a hierarchical grouping procedure based on an objective function and the loss of information associated with merging groups. Its widely used sum-of-squares formulation became a standard alternative to methods defined directly by pairwise minima, maxima, or averages. G. N. Lance and W. T. Williams introduced their general recurrence in 1967, bringing several agglomerative methods into a common computational framework. S. C. Johnson’s 1967 work on hierarchical clustering schemes clarified mathematical relationships between hierarchies and distance representations. These contributions helped establish the subject as more than a collection of unrelated classification recipes.
Algorithmic work subsequently concentrated on reducing computational cost and understanding which properties permit efficient construction. Sibson’s SLINK in 1973 was a major result for single linkage. Nearest-neighbor-chain methods and later implementation research made other standard linkages more practical for large datasets. Kaufman and Rousseeuw’s 1990 book Finding Groups in Data systematized several clustering methods, including divisive approaches, and emphasized graphical and quantitative interpretation. During the 1990s, large-scale database analysis encouraged compressed and approximate approaches such as BIRCH. Hierarchical clustering also became prominent in molecular biology as high-throughput measurements expanded. Its modern use spans classical statistical software, scientific computing libraries, and exploratory interfaces, with continued attention to scalability, reproducibility, and the interpretation of tree structure.
Applications across scientific and information domains
A prominent application is the analysis of gene expression. An expression matrix can have genes as rows and biological samples as columns. Clustering rows groups genes with similar profiles across samples, while clustering columns groups samples with similar expression patterns. Michael Eisen and colleagues’ 1998 work helped establish the combination of hierarchical clustering and colored matrix displays in genomic analysis. A heat map with dendrograms on both axes exposes blocks of coordinated expression. Correlation-based comparisons highlight similar response shapes, whereas Euclidean comparisons preserve differences in magnitude unless preprocessing removes them. Co-clustering of genes can suggest shared regulation or function, but does not itself establish a causal mechanism.
In ecology, hierarchical methods group sampling sites by species composition or group species by their patterns of occurrence. Presence–absence comparisons and abundance-based dissimilarities emphasize different ecological relationships. A site containing many species absent elsewhere can appear distinctive under one coefficient but less so under another that downweights abundant species. Spatial adjacency constraints may be imposed when the intended groups must form connected regions. Such constrained clustering solves a different problem from unrestricted similarity grouping: geographically adjacent sites may be merged despite stronger ecological resemblance to a distant site.
In text analysis and information retrieval, documents can be represented by TF–IDF vectors or learned embeddings. Hierarchical grouping supports browsing from broad subjects to narrower themes without requiring a single predetermined number of categories. A top-level group of scientific documents might divide into biology and physics, with further divisions within each branch. However, a document covering several subjects does not fit naturally into a strictly nested, nonoverlapping hierarchy. In computer vision, clustering image representations can support collection browsing, duplicate exploration, and examination of learned feature spaces. The resulting groups reflect the representation: an embedding may emphasize object identity, visual texture, or semantic association.
Business and industrial applications include grouping customers by observed behavior, examining product similarity, and exploring groups of operational measurements. Hierarchies can reveal subgroups that would be hidden by a single flat partition, while merge heights provide a way to examine how rapidly distinct groups combine. In biological classification, UPGMA can also construct a rooted tree from evolutionary distances, but interpreting that tree as a phylogeny requires assumptions beyond those needed for descriptive clustering, particularly approximately clocklike evolution when branch heights are interpreted as time. A dendrogram of similarities, an evolutionary tree, and an organizational taxonomy may look alike while making fundamentally different claims about what their branches represent.
Limitations, sensitivity, and reproducible reporting
A hierarchy is always available for a finite dataset, even when the observations arise from one continuous cloud without discrete groups. The existence of branches is therefore not evidence by itself for natural categories. Agglomerative methods also make irreversible decisions: an early merger caused by noise or an unsuitable dissimilarity cannot later be undone. Divisive methods have the corresponding problem that an early split constrains all subsequent subdivisions. These restrictions create interpretable nested structure, but they can prevent a hierarchy from matching the best independent partition at every resolution.
Outliers, uneven sampling density, and high dimensionality affect different methods in different ways. A sparse chain can join otherwise distinct groups under single linkage; an extreme observation can dominate complete-linkage distances; and Ward’s method can divide elongated groups in order to limit increases in squared dispersion. In high-dimensional spaces, some distributions exhibit concentration of pairwise distances, weakening the contrast between near and far observations. Feature selection and representation learning alter this geometry, but also introduce modeling decisions. A hierarchy constructed from learned embeddings describes relationships in that learned space, not an assumption-free organization of the original objects.
Ties are another source of nonuniqueness. If several cluster pairs have the same minimum dissimilarity, choosing one first can affect later merges, especially for linkage rules whose updates depend on the newly formed clusters. Input ordering, floating-point rounding, and implementation details can consequently change a binary dendrogram. For single linkage, the connected-component partition at a fixed threshold is invariant even when binary resolutions of tied mergers differ. A multifurcating representation can sometimes express simultaneous joins more faithfully than an arbitrarily resolved binary tree. Separately, leaf ordering should not be confused with membership: aesthetically different dendrograms may encode exactly the same nested groups.
Reproducible reporting identifies the observational units, feature definitions, preprocessing, missing-value treatment, dissimilarity measure, linkage or splitting rule, and partition-selection criterion. For Ward clustering, the distance-squaring and height conventions are especially important. Reports also distinguish exact clustering from graph-restricted, sampled, or compressed approximations, and state the software implementation and any stochastic initialization or tie-breaking policy. Validation is most informative when tied to a specific claim: reproducible branches, correspondence to external categories, faithful distance representation, or usefulness in a downstream task. A hierarchy can support one of these claims without supporting the others, and substantive interpretation depends on keeping those distinctions explicit.