A dendrogram is a tree-shaped diagram that represents a hierarchy of nested groups. It is most commonly used in cluster analysis to show how observations are progressively combined into larger clusters or divided into smaller ones. Leaves usually represent individual observations, while internal nodes represent groups containing all the leaves below them. In many statistical dendrograms, the height of each internal node records the dissimilarity or clustering criterion at which its groups merge. The branching structure describes membership; the height scale, when present, adds quantitative information.
Structure and interpretation
A dendrogram is a rooted tree in the terminology of graph theory. Its principal elements are:
- Leaves: the objects being classified, such as samples, species, documents, or variables.
- Internal nodes: clusters formed from smaller clusters.
- Root: the cluster containing every object represented in the diagram.
- Branches: connections expressing the nesting of clusters.
- Node heights: numerical levels assigned to merges or splits, when the hierarchy has a quantitative scale.
The diagram may be drawn vertically, horizontally, or radially. Orientation does not change the hierarchy.
In a conventional vertical dendrogram, leaves appear along the bottom and merge heights increase upward. Two observations that first share a cluster at a low height are closely associated under the chosen clustering procedure. A merger at a high level indicates that the procedure kept the corresponding groups separate until a larger dissimilarity or clustering cost was reached.
The left-to-right order of leaves is generally not unique. Swapping the two children of an internal node preserves both cluster membership and merge height. Consequently, nearby labels are not necessarily similar, and the horizontal distance between leaves ordinarily has no quantitative meaning. Interpretation depends on the branches connecting the leaves and the height of their first shared node.
A dendrogram is therefore not a conventional plot of points in a coordinate system: most of its geometry is a layout choice rather than a direct representation of measured distance.
Construction by hierarchical clustering
The main statistical source of dendrograms is hierarchical clustering, which produces nested groups rather than only a single partition.
Agglomerative methods
Agglomerative clustering begins with each of observations in its own cluster. At each step, it combines a pair of clusters selected by a rule for measuring between-cluster dissimilarity. This continues until all observations belong to one cluster.
With pairwise merges, the resulting dendrogram has leaves and internal nodes. Ties may be resolved by an implementation-dependent rule or represented as a merger with more than two children.
The input is often a dissimilarity matrix , where measures how different observations and are. Dissimilarities may come from Euclidean distance, a transformation of correlation, or a measure designed for categorical, sequence, or other structured data. They need not satisfy all the requirements of a distance in a metric space.
Divisive methods
Divisive clustering starts with all observations in one group and repeatedly splits groups into smaller ones. It also produces a nested hierarchy that can be displayed as a dendrogram. The splitting criterion need not correspond to any agglomerative linkage rule.
The essential property is nesting: once a group has been divided, later groups lie entirely within one of its descendants. A hierarchy does not allow groups to overlap arbitrarily.
Linkage rules and their effects
In agglomerative clustering, a linkage rule defines the dissimilarity between clusters. Different rules can produce substantially different dendrograms from the same observations.
Let and be clusters, and let denote the dissimilarity between observations.
Single linkage
Single linkage uses the smallest cross-cluster dissimilarity:
It can identify elongated or irregularly shaped groups, but it is susceptible to chaining: a sequence of nearby observations can connect groups whose endpoints are far apart.
Complete linkage
Complete linkage uses the largest cross-cluster dissimilarity:
It tends to favor groups with small diameters, but a single distant observation can strongly affect when a cluster merges.
Average linkage
A common average-linkage rule averages all cross-cluster dissimilarities:
Here, and are the numbers of observations in the clusters. This rule differs from weighted-average linkage, which gives equal weight to the two previously formed clusters during updates, regardless of their sizes.
Ward’s method
Ward’s method selects the merger producing the smallest increase in within-cluster sum of squared deviations. For observations in Euclidean space, this increase is
where and are cluster centroids.
Ward’s method has a least-squares interpretation and tends to favor compact groups. Its standard interpretation relies on squared Euclidean geometry. Software conventions differ in whether displayed heights represent this increase directly or a related transformation, so height scales from different implementations are not automatically interchangeable.
Cutting a dendrogram into clusters
A dendrogram represents many possible clusterings at once. A horizontal cut through a conventional, nondecreasing-height dendrogram selects the groups that remain separate at the chosen level.
Each cut produces a partition of the observations: every observation belongs to exactly one selected cluster. Lower cuts generally yield more clusters; higher cuts yield fewer.
A clustering may be selected by:
- specifying a dissimilarity threshold;
- requesting a particular number of clusters;
- examining large gaps between successive merge heights;
- applying an external criterion for cluster quality or stability.
A large vertical gap can suggest a useful separation, but it does not establish a uniquely correct cluster count. Tied merge heights can also cause a threshold cut to jump directly between cluster counts. Obtaining an intermediate count may then require an additional tie-breaking convention.
Some linkage methods, notably centroid and median linkage, can produce inversions, in which a later merge has a lower height than an earlier merge. Such dendrograms still encode nested membership, but ordinary horizontal-cut interpretations require care.
Mathematical interpretation
A finite hierarchy on a set can be described as a family of nonempty subsets containing and all singleton subsets, with the property that any satisfy
This nesting condition distinguishes hierarchical groups from arbitrary overlapping collections.
Suppose the hierarchy has nonnegative heights that do not decrease from a node toward the root. For distinct observations and , define the cophenetic dissimilarity as the height of the smallest cluster containing both. Set . Then
This is the strong triangle inequality, characteristic of an ultrametric space. If distinct observations can merge at height zero, the construction gives a pseudoultrametric rather than a strictly separating ultrametric.
Thus, a nondecreasing-height dendrogram represents an ultrametric description of the data, even when the original dissimilarities are not ultrametric. The cophenetic values generally differ from the original pairwise dissimilarities: the hierarchy summarizes them rather than preserving them exactly.
One diagnostic compares the original dissimilarities with cophenetic dissimilarities using a correlation coefficient. Strong agreement indicates that the tree preserves aspects of the pairwise structure, but does not by itself validate a particular cluster count or substantive interpretation.
Applications and related diagrams
Dendrograms are widely used in exploratory statistics and machine learning. Applications include grouping documents, comparing ecological communities, organizing chemical compounds, and examining relationships among variables.
In gene expression analysis, dendrograms are often placed beside a heat map. One hierarchy may organize samples, while another organizes genes or other measured features. The resulting row and column arrangements can make patterns visible, although the displayed blocks depend on preprocessing and clustering choices.
Dendrograms also resemble phylogenetic trees, which represent hypotheses about evolutionary relationships. The terms are not fully interchangeable. A statistical clustering dendrogram does not automatically demonstrate common ancestry, and its merge heights need not represent evolutionary time or accumulated evolutionary change. Likewise, organizational charts and other branching diagrams may show a hierarchy without encoding numerical dissimilarity.
Limitations and interpretation
A dendrogram reflects analytical choices as well as data structure.
Preprocessing matters. With Euclidean distance, a variable measured on a much larger numerical scale can dominate the result unless scaling is addressed. Transformations, feature selection, and missing-data imputation can also change the hierarchy.
Linkage imposes a grouping criterion. Single linkage emphasizes connectivity, complete linkage emphasizes diameter, and Ward’s method emphasizes within-group squared dispersion. Their dendrograms answer different operational questions.
A hierarchy always exists even when distinct groups do not. A clustering algorithm can organize observations drawn from a continuous distribution into a tree. The presence of branches is not evidence that the underlying population contains discrete categories.
Branches do not express uncertainty automatically. Merge height is not a p-value, confidence level, or probability that a cluster is real. Procedures based on bootstrap sampling or other perturbations can assess aspects of stability, but their results depend on the resampling scheme and assumptions.
Early decisions may be irreversible. Standard agglomerative methods do not reconsider an earlier merger. Small changes in observations or tied distances can therefore alter later parts of the tree.
Large diagrams can be difficult to read. Truncation and branch collapsing improve readability but conceal detail. Leaf ordering can aid comparison without changing the hierarchy, yet visually prominent patterns may partly reflect that ordering.
Computational costs can be substantial. Storing all pairwise dissimilarities requires quadratic space in the number of observations. Runtime depends on the linkage rule and implementation; algorithms that avoid a full stored distance matrix are available for some settings.