Hierarchical clustering builds a full tree of merges, letting you pick the number of clusters after the fact and inspect structure at every scale. This page covers agglomerative clustering, linkage choices, scaling limits and practical code.
Hierarchical clustering produces a nested tree of clusters instead of a single flat partition. The common agglomerative (bottom-up) form starts with every point as its own cluster and repeatedly merges the two closest clusters until one remains. The merge history is drawn as a dendrogram: the height of each join is the distance at which the merge happened. Cutting the tree at a height (or asking for n clusters) yields a flat clustering, and you can choose the cut after seeing the structure — no need to fix k in advance as with K-Means.
Divisive (top-down) clustering splits recursively instead; bisecting K-Means is a practical version. Agglomerative is far more common.
The distance between two clusters is defined by the linkage:
min d(a, b). Follows elongated shapes but suffers chaining — a thin bridge of points merges two real clusters.max d(a, b). Produces compact, similar-diameter clusters; sensitive to outliers.The naive algorithm needs the full n × n distance matrix: O(n2) memory and O(n2) to O(n3) time depending on linkage and implementation (SciPy uses efficient O(n2) algorithms for the standard linkages). In practice that limits plain agglomerative clustering to tens of thousands of points. Options for larger data: provide a sparse connectivity graph (k-nearest-neighbors) so only local merges are considered, cluster a sample or K-Means micro-clusters first, or use BIRCH or HDBSCAN.
import numpy as np
from scipy.cluster.hierarchy import linkage, fcluster, dendrogram
from sklearn.cluster import AgglomerativeClustering
from sklearn.datasets import make_blobs
from sklearn.preprocessing import StandardScaler
from sklearn.metrics import silhouette_score
X, _ = make_blobs(n_samples=500, centers=4, random_state=1)
X = StandardScaler().fit_transform(X)
# SciPy: full merge tree, choose the cut afterwards
Z = linkage(X, method="ward") # (n-1) x 4 merge table
labels = fcluster(Z, t=4, criterion="maxclust")
# or cut by height: fcluster(Z, t=5.0, criterion="distance")
# dendrogram(Z, truncate_mode="lastp", p=20) # plot with matplotlib
# scikit-learn equivalent, with an optional connectivity constraint
from sklearn.neighbors import kneighbors_graph
conn = kneighbors_graph(X, n_neighbors=10, include_self=False)
agg = AgglomerativeClustering(n_clusters=4, linkage="ward", connectivity=conn).fit(X)
print(silhouette_score(X, agg.labels_).round(3))
# Average linkage with cosine distance, e.g. for embeddings
agg_cos = AgglomerativeClustering(n_clusters=None, distance_threshold=0.4,
metric="cosine", linkage="average").fit(X)
print("clusters found:", agg_cos.n_clusters_)k visually by the largest vertical gap in the dendrogram.distance_threshold groups near-duplicate records or embeddings without fixing a count.Pitfalls: merges are greedy and never undone, so an early bad merge propagates; results depend heavily on linkage and scaling; and dendrograms on more than a few hundred leaves need truncation to be readable.
Take five one-dimensional points: A=1, B=2, C=4, D=9, E=10. Ward's merge cost for clusters P and Q is the increase in total within-cluster sum of squares, Δ = (|P||Q| / (|P|+|Q|)) · (meanP − meanQ)2.
The shape is what matters: two cheap merges, one moderate merge, and one very expensive merge. The huge jump before the last merge says the data has two well-separated groups, and cutting anywhere in that gap returns {1, 2, 4} and {9, 10}. With single linkage the same data merges in the same order here, but on elongated or noisy data the orders diverge, which is why linkage choice matters.
scikit-learn and SciPy offer two ways to get a flat clustering: ask for n_clusters, or set a distance_threshold (SciPy: fcluster(Z, t, criterion="distance")). Thresholds are more interpretable when the distance has meaning, such as a cosine distance of 0.15 for near-duplicate text. Useful checks:
| Agglomerative (Ward) | K-Means | HDBSCAN | |
|---|---|---|---|
| Output | Full tree; flat cut on demand | One flat partition | Cluster tree condensed to flat clusters + noise |
| Deterministic | Yes (ties aside) | Depends on initialization | Yes |
| Metrics | Ward needs Euclidean; others any | Euclidean | Any metric |
| Memory | O(n2) | O(nk) | Roughly O(n) with spatial indexes in low dimensions |
| Outliers | Forced into clusters (single linkage isolates them late) | Pull centroids | Labeled as noise |
Typical real-world uses follow from the tree output: building product or document taxonomies that people browse level by level, ordering rows and columns of gene-expression or correlation heatmaps (the clustered heatmap), grouping near-duplicate records for entity resolution with a distance threshold, and phylogenetics, where average linkage (UPGMA) has a long history. In each case the value is the nested structure, not just one flat partition.
A common hybrid for large data: run MiniBatchKMeans with a few hundred to a few thousand centers, then cluster the centers hierarchically. You keep the interpretable tree while the expensive step runs on micro-clusters.
truncate_mode="lastp" to show only the top merges.Further reading: Ward, J. (1963), "Hierarchical grouping to optimize an objective function"; Müllner, D. (2011), "Modern hierarchical, agglomerative clustering algorithms" (arXiv:1109.2378); Murtagh & Contreras (2012), "Algorithms for hierarchical clustering: an overview". Related: Clustering overview, DBSCAN.