Hierarchical clustering

Also known as: agglomerative clustering

On this page 8

Hierarchical clustering is an unsupervised learning method that organizes observations into a nested hierarchy of clusters, usually drawn as a tree diagram called a dendrogram. In machine learning and the wider field of artificial intelligence, it is one of the classic ways to discover structure in unlabeled data without fixing the number of groups in advance.

The most common form, agglomerative clustering, starts with every point as its own cluster and repeatedly merges the two closest clusters until one cluster remains. The analyst then cuts the tree at a chosen height or cluster count, which makes the method attractive for exploratory analysis, taxonomy building and any task where groups exist at several scales.

How agglomerative and divisive clustering build the tree

Hierarchical clustering builds its tree either bottom-up or top-down. The bottom-up variant, agglomerative clustering, computes a pairwise distance matrix, merges the closest pair, updates the distances between the new cluster and all others, and repeats for n – 1 merge steps. The top-down variant, divisive clustering, starts with one cluster containing all points and recursively splits it.

Each merge is recorded with the distance at which it occurred. That merge height becomes the vertical axis of the dendrogram, so tall vertical links indicate well-separated groups and short links indicate points that were already close. The full record of merges is the linkage matrix, which most libraries return as an array of n – 1 rows.

The table below contrasts the two directions of tree construction.

ApproachStarting pointTypical costPractical note
AgglomerativeOne cluster per pointO(n²) memory, O(n²) to O(n³) timeDefault in almost all libraries
DivisiveOne cluster with all pointsExponential if exact, so heuristics are usedBetter at finding large top-level splits
Bisecting k-meansOne cluster split by k-meansClose to linear per splitPractical divisive approximation
Agglomerative and divisive approaches compared

Linkage criteria and distance metrics

The linkage criterion defines how the distance between two clusters is computed from the distances between their members, and it is the most consequential choice in hierarchical clustering. Different linkages applied to the same data can produce very different trees, so the choice must match the expected shape of the groups.

The following table summarizes the standard linkage criteria and their typical behavior.

LinkageCluster distance defined asTypical cluster shapeMain weakness
Single linkageMinimum distance between membersElongated, chain-likeChaining effect through noise points
Complete linkageMaximum distance between membersCompact, similar diameterSensitive to outliers
Average linkageMean of all pairwise distancesModerately compactCompromise with no strong guarantee
Ward linkageIncrease in within-cluster varianceSpherical, similar sizeRequires Euclidean distance
Centroid linkageDistance between cluster meansSphericalCan produce non-monotonic merges
Common linkage criteria and their effects

The distance metric is a separate decision. Euclidean distance suits continuous, scaled features; Manhattan distance is more robust to single large deviations; cosine distance fits text embeddings and other high-dimensional vectors where direction matters more than magnitude. Ward linkage is defined only for squared Euclidean geometry, so pairing it with cosine or correlation distance produces results that are hard to interpret.

Reading and cutting a dendrogram

A dendrogram is read from the leaves upward, and a horizontal cut across it produces a flat clustering. Cutting at a fixed distance threshold yields every cluster that formed below that height, while cutting at a fixed number of clusters k finds the height that leaves exactly k branches. One tree therefore supports many partitions without refitting.

Analysts often look for the largest vertical gap between successive merges, which plays a role similar to the elbow method used with k-means clustering. Quantitative aids include the cophenetic correlation coefficient, which measures how faithfully the tree preserves the original pairwise distances, and the silhouette score computed for several cut levels. A cophenetic correlation above about 0.75 is usually read as a reasonable fit, although no universal threshold exists.

Hierarchical clustering compared with other clustering methods

Hierarchical clustering differs from neighboring methods mainly in that it does not require k in advance and returns a full multiscale structure rather than a single partition. The trade-off is computational: the quadratic memory requirement limits exact implementations to roughly tens of thousands of points on ordinary hardware.

MethodNeeds number of clustersScales to large dataCluster shapes found
Hierarchical clusteringNo, chosen at the cutLimited, quadratic memoryDepends on linkage
k-means clusteringYesYes, near linearConvex, similar size
DBSCANNo, uses density parametersYes with spatial indexingArbitrary shapes, marks noise
Gaussian mixture modelYesModerateElliptical, soft assignments
Spectral clusteringYesLimited by eigendecompositionNon-convex, graph-based
Hierarchical clustering and related methods

A common hybrid workflow runs k-means first to create a few hundred micro-clusters and then applies hierarchical clustering to their centroids. This keeps the interpretable tree while reducing the memory cost by orders of magnitude, an idea also used in the BIRCH algorithm.

Practical setup and configuration choices

Good results depend more on preprocessing and linkage choice than on the clustering routine itself. Because the method works directly on distances, feature scaling is mandatory when features use different units, and high-dimensional data often benefits from principal component analysis before clustering to reduce noise in the distance matrix.

SituationRecommended choiceReason
Numeric features, compact groups expectedWard linkage, EuclideanMinimizes within-cluster variance
Text or embedding vectorsAverage linkage, cosineDirection-based similarity, no Ward constraint
Elongated or connected structuresSingle linkageFollows chains of nearby points
Data with outliersAverage linkage after outlier removalLimits distortion of merge heights
More than about 50,000 pointsMicro-clusters first, then hierarchyAvoids quadratic memory
Configuration decisions by situation

Mixed categorical and numeric data can be handled with Gower distance, which combines per-feature dissimilarities on a common scale. Libraries such as SciPy and scikit-learn also allow connectivity constraints, which only permit merges between neighbors in a graph and are useful for image segmentation and geographic regions.

Limitations and common mistakes

The defining limitation of agglomerative clustering is that merges are greedy and irreversible. A merge made early on the basis of local distances can never be undone, so an error at the bottom of the tree propagates to every higher level. This also makes the result sensitive to ties and small perturbations in the data.

  • Skipping feature scaling, which lets a single large-range feature dominate every distance.
  • Using Ward linkage with non-Euclidean distances, which breaks its variance interpretation.
  • Treating the dendrogram as proof that clusters exist; the method always produces a tree, even for uniform random data.
  • Choosing the cut level only by visual impression instead of checking stability across resamples.
  • Ignoring the quadratic memory cost until a large job fails on the full distance matrix.

Explained without jargon

Hierarchical clustering sorts things into groups inside groups, much like a family tree. It begins by pairing the two most similar items, then pairs the next most similar items or small groups, and keeps going until everything sits in one big group.

The result is a tree picture that shows which items belong together and how strongly. The useful part is that nobody has to decide the number of groups at the start. A person can look at the tree and choose the level of detail afterward, for example three broad families or twelve narrow ones.

A typical use case

A retail analytics team wants to understand the purchasing patterns of about 8,000 store locations. Each store is described by 40 standardized features, such as share of sales by category, average basket size and weekend traffic. The team applies agglomerative clustering with Ward linkage on the scaled features after reducing them to 12 principal components.

The dendrogram shows a large gap that separates three broad store families: urban convenience, suburban family and rural destination stores. Cutting lower reveals eleven subgroups, including a distinct cluster of tourist locations with strong seasonal peaks. The cophenetic correlation is 0.81, and the subgroups remain stable when the team reruns the analysis on random 80 percent samples.

The outcome is a two-level store taxonomy used for assortment planning: category managers plan at the family level, while regional managers fine-tune stock using the eleven subgroups.