Merge the two closest clusters, repeat, and keep the whole tree. Choose how many clusters you want afterwards.
Overview
The algorithm
Agglomerative clustering is almost trivially simple:
each point starts as its own cluster.
Find the two closest clusters and merge them.
Repeat until one cluster remains.
Recording the distance at each merge gives a dendrogram — the chart above plots just that: merge number against the distance at which it happened.
Hierarchical Clustering and Dendrograms
This module needs JavaScript: the
numbers are computed in the page rather than recorded.
Worth knowing
Start with every point as its own cluster. Repeatedly merge the two closest, until one remains.
The result is a tree. Cutting it at a height gives a clustering — and every height gives a different k.
Linkage defines the distance between two clusters, and changes the answer more than any other choice.
Single linkage chains through bridges; complete linkage insists on tight clusters; average sits between them.
Hierarchical Clustering and Dendrograms
Building the whole tree once. Choosing how many clusters you want after seeing it.
The point: k comes last
K-means and DBSCAN both need a choice before they run — how many clusters, or how dense. Hierarchical clustering needs neither. It builds one tree, and a flat cut through it makes a clustering.
Drag the cut height and watch the count change. A cut low down leaves many small clusters, a cut high up leaves few, and the tree itself never changed. That is truly handy when you don't know what structure to expect, because you can look at the merge distances before committing.
Large jumps in the curve are helpful: a merge that costs much more than the one before it joined two things that weren't really close. Cutting just below a big jump is the dendrogram equal of the elbow.
Linkage changes everything
The method needs a distance between two *clusters*, not two points, and there is no single right answer. Switch the control and the shape of the curve changes a lot.
Single linkage — distance between the nearest pair. Merges cheaply when any two members are close. So It can follow elongated shapes. Its failure mode is chaining: two well-separated blobs joined by a thin bridge of points merge into one, because the bridge gives a short hop at each step.
Complete linkage — distance between the furthest pair. A merge is only cheap if *each* member of one cluster is close to each member of the other, so clusters come out compact and roughly equal in diameter. It breaks up elongated structures that truly belong together, and is sensitive to outliers, since one distant member sets the whole distance.
Mean linkage — the mean over all cross-pairs. Between the two, and the usual default.
Ward linkage, not offered here, merges the pair that grows within-cluster variance least. It behaves much like k-means and is the most common choice for roughly spherical clusters.
Linkage
Produces
Fails at
Single
elongated, chain-following
bridges between clusters
Complete
compact, similar sized
genuinely elongated clusters
Average
a compromise
nothing dramatic
Ward
spherical, balanced
non-convex shapes
Reading a real dendrogram
A conventional dendrogram draws each merge as a bracket at its height, with the leaves at the bottom. Two things are worth knowing about reading one.
Height is real. Flat spot isn't. The left-to-right order is chosen to keep the drawing untangled and carries no info. Two adjacent leaves aren't always similar.
The tree is greedy and permanent. Once two clusters merge they never separate, so an early mistake. Two points joined because of noise — passes all the way up. Hierarchical clustering doesn't revisit choices.
Cost
The naive method is O(n³), and careful setups reach O(n² log n) with O(n²) memory for the distance mat. That memory is often the binding constraint: 100,000 points is a mat of ten billion distances.
This is why hierarchical clustering is a small-to-medium-data method. Above a few tens of thousands of points, k-means or a sampled variant is the hands-on choice.
Linkage, on two little clusters
"There's no single right answer" for the distance between two clusters is easiest to see on numbers. Cluster A = {0, 1}, cluster B = {5, 9}. The four cross-pair distances are 5, 9, 4, 8, and each linkage reads a different one:
linkage
cluster distance
from
single (nearest pair)
4
1 to 5
complete (furthest pair)
9
0 to 9
average (mean of all four)
6.5
(5+9+4+8)/4
Single linkage merges as soon as *any* two members are close. This Lets it follow an elongated shape but also lets a thin bridge of points chain two separate blobs into one. Complete linkage merges only when *each* member is close, giving compact clusters but breaking truly stretched ones and taking its distance from a single furthest outlier. Mean sits between them and is the usual default. The same three points would cut the tree at three different heights. This Is why the dendrogram's shape — and any k read off it — changes fully with the linkage rule, before the data has changed at all. And the whole thing carries an O(n²) distance mat: 100,000 points is ten billion distances, which is the memory wall that keeps this a small-to-medium-data method.
Two more properties are worth carrying. The tree is *greedy and permanent*: once two clusters merge they never separate. So A mistake made early — two points joined because of noise — rides all the way up the dendrogram, because the method never revisits a choice. And the left-to-right order of the leaves carries no info. It's chosen only to keep the drawing untangled, so two adjacent leaves aren't always similar. Height in the diagram is real — it's the distance at which a merge happened, and a large vertical jump means two things that weren't really close were forced together — but flat spot is decoration.
Ward linkage, not among the three above, merges the pair that grows within-cluster variance least. It behaves much like k-means and is the usual choice for roughly spherical clusters. This Rounds out the rule of thumb — single for elongated shapes, complete for compact ones, mean as a safe middle, Ward when the clusters are blobs.
Where it goes wrong with Hierarchical Clustering and Dendrograms
Not scaling the features. As with each distance-based method.
Using single linkage on data with any bridge between clusters. Chaining will merge them.
Reading meaning into leaf order. It's a drawing rule.
Trying it on a large dataset. The distance mat won't fit.
Questions people ask about Hierarchical Clustering and Dendrograms
What is a dendrogram? A tree showing the order in which clusters merge and the distance at each merge. Cut it at a height to get a flat set of clusters.
Which linkage should I use? Ward is a good default for compact, similar-sized clusters. Single linkage finds chains but is sensitive to noise, and average and complete sit in between.
How do I choose where to cut the dendrogram? Look for a long vertical gap with no merges, and cut within it. That gap shows the clusters are well separated at that level.
Does hierarchical clustering scale to large datasets? Poorly. It needs the pairwise distance matrix, so memory grows with the square of the number of points. Beyond tens of thousands of rows, use k-means or a sampled subset.
Do I need to scale features? Yes, because distances drive every merge. A large-scale feature will dominate otherwise.
Can I undo a merge? No. Agglomerative merges are final, so an early bad merge stays in the tree.
Cluster without choosing k first
Agglomerative clustering merges the two closest groups over and over. You get each k at once. The linkage rule decides what "closest" means. It changes the answer fully.
example_01.pyscikit-learn
import numpy as np
from sklearn.datasets import make_blobs
from sklearn.metrics import adjusted_rand_score, silhouette_score
from scipy.cluster.hierarchy import linkage, fcluster
X, y = make_blobs(n_samples=300, centers=4, cluster_std=1.0, random_state=0)
Z = linkage(X, method="ward")
print("the merge log -- 299 merges, each joining two groups into one.")
print("%8s %8s %8s %12s %10s" % ("step", "group A", "group B", "distance", "size"))
for i in list(range(3)) + list(range(len(Z) - 5, len(Z))):
a, b, d, n = Z[i]
print("%8d %8d %8d %12.4f %10d" % (i, a, b, d, n))
print(" first merges: single points at almost no distance.")
print(" last merges: whole clusters across large gaps.")
print()
print("the last few merge distances, and the jump before each:")
for i in range(len(Z) - 6, len(Z) - 1):
print(" cut here -> %d clusters next merge costs %8.3f (%.2fx the last)"
% (len(X) - i - 1, Z[i, 2], Z[i, 2] / Z[i - 1, 2]))
print(" cut here -> 1 cluster the root, %8.3f" % Z[-1, 2])
print()
print(" 'find the biggest jump' always answers 2. the useful reading is")
print(" where the RATIO stops being dramatic -- a judgement call,")
print(" which is why the silhouette column below is worth having.")
print()
print("one tree, every k, no refitting:")
print("%6s %14s %14s" % ("k", "agreement", "silhouette"))
for k in (2, 3, 4, 5, 6):
labels = fcluster(Z, k, criterion="maxclust")
print("%6d %14.4f %14.4f"
% (k, adjusted_rand_score(y, labels), silhouette_score(X, labels)))
print(" k-means has to be rerun from scratch for each k. this is one fit.")
Output
The next block compares the four linkage methods and shows where single linkage wins.
example_02.pyscikit-learn
import numpy as np
from sklearn.cluster import AgglomerativeClustering
from sklearn.datasets import make_blobs, make_moons
from sklearn.metrics import adjusted_rand_score
X, y = make_blobs(n_samples=300, centers=4, cluster_std=1.0, random_state=0)
print("linkage is the whole personality of the algorithm:")
for method in ("ward", "complete", "average", "single"):
m = AgglomerativeClustering(n_clusters=4, linkage=method).fit(X)
print(" %-10s agreement %.4f, cluster sizes %s"
% (method, adjusted_rand_score(y, m.labels_),
sorted(np.bincount(m.labels_), reverse=True)))
print()
print(" ward -- minimise total variance. compact, even sizes.")
print(" complete -- furthest members. compact, sensitive to outliers.")
print(" average -- mean pairwise distance. a middle ground.")
print(" single -- closest members. chains through thin bridges.")
print()
Xm, ym = make_moons(n_samples=300, noise=0.06, random_state=0)
print("that chaining is a weakness and a feature. on two crescents:")
for method in ("ward", "single"):
m = AgglomerativeClustering(n_clusters=2, linkage=method).fit(Xm)
print(" %-10s agreement %.4f" % (method, adjusted_rand_score(ym, m.labels_)))
print(" single linkage follows the shape. ward cuts straight across it.")
print()
print("the cost is O(n^2) in memory -- a full distance matrix. at")
print("100,000 rows that is 40GB, which is why k-means still exists.")
Output
Check yourself
0 of 3
Answer without scrolling back up.
What is the advantage of building the whole tree?
One tree, and a horizontal cut at any height gives a clustering. Cutting just below a large jump in merge distance is the dendrogram's version of the elbow.
What is chaining, and which linkage causes it?
Single linkage uses the nearest pair, so a bridge provides a cheap merge at every step. Complete linkage has the opposite failure: it breaks up genuinely elongated clusters.
Why is hierarchical clustering impractical for large datasets?
100,000 points is ten billion distances. Time is O(n^2 log n) at best, but memory is usually what stops you first.
Cheat sheet
Hierarchical Clustering and Dendrograms
Build a clustering tree from pairwise distances and read a dendrogram to choose the number of clusters after the algorithm finishes.
Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.