How does hierarchical clustering work, and how do you decide the number of clusters from a dendrogram?

How to think about it

The crisp answer

Agglomerative hierarchical clustering starts with every data point as its own cluster, repeatedly merges the two closest clusters according to a chosen linkage rule, and records those merges in a dendrogram. You choose the number of clusters by drawing a horizontal cut through the dendrogram, usually just before a large jump in merge height, then checking whether the resulting groups are stable and useful.

Why the algorithm produces a tree

Hierarchical clustering is a family of clustering methods. The two broad styles are agglomerative, which builds one large cluster from many small ones, and divisive, which starts with one cluster and repeatedly splits it. In most interviews, “hierarchical clustering” means the agglomerative version unless someone says otherwise.

The algorithm needs three important choices:

• A distance metric, which defines how unlike two observations are. Euclidean distance is common for numeric features. Manhattan distance adds coordinate differences, while cosine distance compares the direction of vectors and is often useful for text embeddings.
• A linkage rule, which defines the distance between two clusters rather than two individual points.
• A stopping height, or equivalently a final number of clusters.

The agglomerative process is simple:

1. Start with n singleton clusters, meaning n clusters containing one point each.
2. Calculate the distance between every pair of clusters.
3. Merge the pair with the smallest linkage distance.
4. Record that distance as the merge height.
5. Repeat until all points belong to one cluster.

There are n - 1 merges, so the final result contains a complete history rather than just one answer. If you cut that history at different heights, you get different numbers of clusters.

A dendrogram is the visual form of that history. Its leaves are the original observations. Its branches show which observations joined together. The vertical axis shows the height at which a merge happened: higher usually means the algorithm had to join more dissimilar groups.

The horizontal position of a leaf is not a distance scale. Branches can often be flipped around internal nodes without changing the clustering. Two leaves next to each other in the drawing are not necessarily closer than two leaves far apart on the page.

The process is greedy. Once two clusters merge, that decision is not undone later. That is the source of both the method’s speed and one of its main weaknesses.

A concrete example

Suppose five customer accounts are represented by two already-scaled features: product usage and support intensity.

Account	Coordinates
A	(1, 1)
B	(1, 2)
C	(2, 2.5)
D	(8, 8)
E	(9, 8)

Use Euclidean distance and complete linkage. Euclidean distance is the straight-line distance between points. For A and B:

d(A, B) = sqrt((1 - 1)^2 + (1 - 2)^2) = 1

The first shortest pairs are A and B, and D and E. Their merge heights are both 1.00. Complete linkage then compares a cluster with another cluster by looking at the farthest cross-cluster pair.

The next merge is the cluster containing A and B with C. The distances from C to A and B are approximately 1.80 and 1.12, so complete linkage uses the larger value: approximately 1.80.

The final merge joins A, B, and C with D and E. The farthest cross-cluster pair is A and E, whose distance is approximately 10.63.

The important merge heights are therefore:

Merge	Height
A with B	1.00
D with E	1.00
AB with C	1.80
ABC with DE	10.63

There is a large empty interval between heights 1.80 and 10.63. Draw a horizontal line at height 5, and the tree has two branches:

• ABC
• DE

That gives two clusters.

Draw the line at height 1.5, and the tree has three branches:

• AB
• C
• DE

That gives three clusters. The algorithm did not need to be told k = 2 or k = 3 before fitting. Both answers are available from the same tree.

The height is not a probability, confidence score, or percentage of similarity. It is a dissimilarity value under the selected metric and linkage rule. A height of 10.63 means something different under Euclidean complete linkage than under cosine average linkage.

Linkage is not a footnote

“Closest clusters” is incomplete unless the linkage rule is specified. The rule can change the tree, the apparent gaps, and the final business interpretation.

Linkage	Cluster distance	Typical result
Single	Smallest distance between any cross-cluster pair	Can form long chains
Complete	Largest distance between any cross-cluster pair	Favors compact groups
Average	Mean of all cross-cluster pair distances	A middle ground
Ward	Increase in within-cluster squared error after merging	Compact, roughly round groups

Single linkage asks whether any two points are close. This makes it good at following elongated shapes, but it can create a chain: one sequence of bridge points connects groups that look separate to a human.

Complete linkage asks whether even the farthest points remain reasonably close. It usually produces tighter clusters, but a single outlier can make a proposed merge look very expensive.

Average linkage uses all cross-cluster distances. It is often a reasonable general-purpose choice when neither chaining nor extreme compactness is wanted.

Ward linkage chooses the merge that produces the smallest increase in within-cluster sum of squares, meaning the total squared distance of points from their cluster centroids. It often works well for numeric features with Euclidean geometry. It is not a universal option for arbitrary distance matrices, and it tends to prefer compact groups.

So linkage is a modeling decision, not a cosmetic setting. If the application cares about compact customer segments, Ward or complete linkage may make sense. If it cares about connected geographic regions, single linkage may be more appropriate, provided chaining is acceptable.

How to choose the number of clusters

Start with the dendrogram. Look for a height interval containing no merges. A horizontal cut through that interval separates branches that have already formed from branches that would only appear after joining substantially more dissimilar groups.

In the example, the interval from 1.80 to 10.63 is strong evidence for two clusters. It is not mathematical proof that two is the true answer. Unsupervised data does not come with a hidden label saying “there are exactly two groups.”

Next, compare plausible cuts with an internal metric. The silhouette score compares how close each point is to its own cluster with how close it is to the nearest competing cluster. Higher values are generally better, but the score favors particular geometries and should not overrule the purpose of the analysis.

Check stability as well. Rerun the clustering after resampling rows, slightly perturbing feature values, or changing a reasonable preprocessing choice. If the same groups keep appearing, confidence increases. If customers move between clusters whenever five rows are removed, the apparent segmentation is fragile.

Finally, ask whether the cut is useful. A marketing team may need three segments it can name and target. A fraud system may prefer one small high-risk group and a broad normal group. A cluster containing two percent of the data may be valuable, or it may be too small to act on. The best cut depends on the decision the clusters support.

Common trap: the tallest gap is a candidate, not an automatic answer. A single extreme outlier can create a dramatic final jump, and cutting there may produce “one normal cluster plus one weird point” rather than a useful segmentation.

The preprocessing and scale trap

Distance-based clustering is only as sensible as the coordinate system behind it. Suppose revenue ranges from 0 to 100,000, while support tickets range from 0 to 20. With raw Euclidean distance, revenue dominates because a difference of 10,000 contributes 100,000,000 to the squared distance, while a one-ticket difference contributes only 1.

Standardization, such as converting each feature to a z-score, can put the features on comparable scales. Robust scaling can be preferable when extreme values are common. But do not standardize blindly. If revenue is intentionally meant to count much more than tickets, encode that business weighting deliberately instead of letting raw units make the decision by accident.

Categorical variables, missing values, and text embeddings also need appropriate representations and metrics. One-hot encoding a high-cardinality category and feeding it into Euclidean clustering can create a very different geometry from what the business intended.

When hierarchical clustering is the wrong tool

The full hierarchy is useful, but it is expensive. A complete pairwise distance structure needs n(n - 1) / 2 unique distances. With n = 100,000, that is 4,999,950,000 distances. At eight bytes per distance, the unique values alone occupy about 40 GB; a full square matrix is about 80 GB, before metadata and working memory.

Actual runtime depends on the implementation, linkage, and whether candidate merges are restricted to nearby points. Straightforward implementations can approach cubic time, while optimized implementations can do better. Either way, hierarchical clustering is usually a poor choice for millions of observations or for a model that must update every few seconds.

Use it when the dataset is small or medium-sized, the hierarchy itself is informative, and exploratory analysis matters. Consider k-means or a scalable variant when the data is large and compact centroid-based groups are acceptable. Consider a density-based method when arbitrary shapes and noise are central to the problem. None of these methods removes the need to define what “similar” means.

A failure mode you can recognise

The classic symptom of single-linkage failure is a dendrogram that looks like a thin comb. Many points join one after another at modest heights, and the two groups that looked obvious in a scatter plot become one long connected chain.

In the customer example, imagine adding several accounts between C and D. Single linkage may connect ABC to DE through one close bridge pair, because it needs only one short cross-cluster distance. Complete linkage would care about the farthest pair and resist that merge much longer.

The fix is not automatically “choose a different number of clusters.” First inspect the metric, scaling, linkage, and possible bridge points. Compare a few defensible choices and validate the resulting memberships.

What they’ll ask next

How is hierarchical clustering different from k-means?

Hierarchical clustering builds a reusable merge tree and does not require k in advance, but it is more expensive and its early merges are irreversible. K-means requires k before fitting, repeatedly reassigns points to centroids, and is usually much faster at scale. Its objective naturally favors compact, centroid-shaped groups, while hierarchical clustering can reveal structure at several resolutions.

How do you choose the linkage rule?

Choose it from the geometry and the failure you can tolerate. Ward is a strong choice for scaled numeric data and compact Euclidean groups. Average linkage is a reasonable compromise. Complete linkage favors tight clusters but can react strongly to outliers. Single linkage can recover elongated connected structure but is vulnerable to chaining. I would compare the result with a domain-relevant validation check rather than choose from habit.

Does the dendrogram tell you the exact number of clusters?

No. It shows the merge history. A large height gap suggests a cut, but the final choice also depends on stability, cluster quality, outliers, and what the clusters will be used for. If there is no clear gap, I would report sensitivity across several cuts instead of pretending the data contains a precise natural k.

Say this in the interview

“Hierarchical clustering greedily builds a dendrogram by merging clusters under a chosen distance and linkage rule; I select the number of clusters by cutting across a meaningful height gap, then validate that cut against stability, geometry, and the business decision.”