Understanding Hierarchical Clustering
Hierarchical clustering represents observations as nested groups rather than producing only one partition. In agglomerative clustering, each observation begins as its own cluster. At each step, the algorithm merges the two eligible clusters with the smallest linkage value, updates the relevant comparisons, and repeats. A complete tree for n observations contains n − 1 merges. These decisions are greedy: once two groups merge, later steps cannot separate them, even if another arrangement would improve a global objective.
Two choices determine what “closest” means. A distance metric compares individual observations; Euclidean distance measures straight-line separation in feature space. A linkage rule compares clusters. Single linkage uses the smallest distance between their members, complete linkage uses the largest, and average linkage uses the mean of all cross-cluster pairwise distances. Single linkage can connect distant regions through chains of nearby observations. Complete linkage discourages such chains but can be sensitive to extreme observations. Average linkage offers a compromise, not a universally superior solution.
Ward linkage uses a different criterion: it chooses the merge with the smallest increase in total within-cluster squared deviation from cluster means. For clusters A and B, this increase is |A||B|/(|A|+|B|) times the squared Euclidean distance between their means. Cluster sizes therefore matter, not just centroid separation. Ward requires Euclidean geometry and tends to favor compact groups. Its reported merge heights should not be interpreted as ordinary distances between individual observations.
A dendrogram displays the merge tree: leaves represent observations, branches represent merges, and merge heights encode linkage values. Cutting below a merge keeps its child groups separate. Building the full hierarchy does not require choosing K, but returning a flat partition requires a cluster count or distance threshold. Equal merge heights can make some cluster counts unavailable through a horizontal threshold alone, although a count-based cut can select a merge stage.
The hierarchy describes similarity under your chosen representation, not verified classes or causal relationships. Scaling changes that representation. Dense pairwise approaches can require quadratic memory, so hierarchical clustering can become expensive as datasets grow. Connectivity constraints can restrict eligible merges, but also change the clustering problem.
Practical walkthrough
Start by defining what one row represents and which features should determine similarity. Exclude identifiers unless their numerical differences genuinely express similarity. Check missing values and consider whether extreme observations are measurement errors or meaningful cases. For multiple features with different units, consider standardization; otherwise, a large numerical scale may dominate Euclidean distance. Standardization is a modeling choice, not proof that every feature deserves equal influence.
For the example below, four observations have one numerical feature in a shared unit. No scaling or imputation is needed. This is a descriptive analysis of those four observations, not an evaluation of performance on unseen data. In a held-out evaluation workflow, split before learning preprocessing parameters: fit imputers and scalers on training data only, then reuse them unchanged. Keep held-out data out of decisions about linkage and thresholds.
Choose complete linkage so that every candidate merge is judged by its largest cross-cluster distance. Set n_clusters=None and distance_threshold=4.0. In scikit-learn, these settings request threshold-based clustering; compute_full_tree=True explicitly requests the complete hierarchy. compute_distances=True makes merge heights available for inspection without plotting.
Run the code in an environment with scikit-learn installed. Inspect children_ alongside distances_: original observations have indices 0 through 3, and each successive merge receives a new index. The code reconstructs memberships to make those indices readable.
Finally, inspect the resulting groups rather than relying on numeric label names. Compare nearby thresholds and alternative justified linkages. Large gaps between merge heights suggest candidate cuts, but do not establish a uniquely correct number of clusters.
Worked example
from sklearn.cluster import AgglomerativeClustering
X = [[0.0], [1.0], [5.0], [8.0]]
names = ['A', 'B', 'C', 'D']
model = AgglomerativeClustering(
n_clusters=None,
distance_threshold=4.0,
linkage='complete',
metric='euclidean',
compute_full_tree=True,
compute_distances=True,
).fit(X)
members = {i: [name] for i, name in enumerate(names)}
for step, (children, height) in enumerate(
zip(model.children_, model.distances_)
):
left, right = map(int, children)
merged = sorted(members[left] + members[right])
members[len(names) + step] = merged
print(f"merge {step + 1}: {','.join(merged)} at {height:.1f}")
groups = {}
for name, label in zip(names, model.labels_):
groups.setdefault(int(label), []).append(name)
print('cut at 4.0:', sorted(groups.values()))
Expected output
merge 1: A,B at 1.0
merge 2: C,D at 3.0
merge 3: A,B,C,D at 8.0
cut at 4.0: [['A', 'B'], ['C', 'D']]
A and B merge first because their distance is 1. Afterward, the complete-linkage distance from {A, B} to C is max(5, 4) = 5, while C and D are only 3 apart. Thus C and D merge next. The final cross-cluster distances are 5, 8, 4, and 7; their maximum is 8. A threshold of 4 retains the first two merges but excludes the final one, leaving two groups. Printing sorted memberships avoids depending on arbitrary numeric cluster labels. The final height measures complete-linkage separation; it is not a confidence score or evidence that two natural classes exist.
Common mistakes and how to avoid them
Treating “no K upfront” as “no decision needed.”
Choose a count or threshold when requesting a partition. For threshold-based AgglomerativeClustering, set n_clusters=None. Check merge heights and boundary behavior: merges at or above distance_threshold are excluded.
Combining Ward linkage with a non-Euclidean metric.
Use Euclidean distance for Ward. If another metric better represents similarity, choose a compatible linkage such as average or complete and explain why that combination fits the data.
Reading dendrogram leaf order as a numerical similarity scale.
Read shared ancestors and merge heights instead. Branches can rotate without changing memberships or heights, so neighboring leaf positions alone do not establish which observations are closest.
Expecting the fitted estimator to predict clusters for new rows.
AgglomerativeClustering has no standard predict method. Refitting can change existing groups. If deployment needs fixed assignments, define and validate a separate assignment rule or choose an estimator supporting prediction.
Review questions
Why can single and complete linkage produce different trees from identical distances?
They summarize cross-cluster distances differently: single takes the minimum, complete the maximum. After an initial merge, these summaries can rank candidate merges differently, changing subsequent branches.
What happens in the example if the threshold rises from 4 to 9?
The final merge at height 8 becomes included, producing one cluster. The hierarchy itself stays the same; only the rule used to extract a partition changes.
Why does a greedy merge matter?
A mistaken early merge cannot be undone within that tree. Later decisions must preserve it, so changing the cut cannot recover every possible partition of the observations.
Does an appealing dendrogram establish that the clusters are meaningful?
No. A tree is produced even without useful group structure. Examine feature choices, sensitivity to scaling and linkage, and stability under reasonable data perturbations before interpreting groups substantively.
