Hierarchical Clustering
Hierarchical clustering builds a multi-level hierarchy of clusters rather than a single flat partition, producing a tree structure called a dendrogram that shows how points and clusters merge together at increasing levels of dissimilarity. Unlike k-means, it does not require the number of clusters to be chosen upfront — instead, you build the full hierarchy once and then decide afterward, by cutting the dendrogram at a chosen height, how many clusters to extract. This makes it especially useful for exploratory analysis where the natural number of groups isn't known in advance, such as in gene expression analysis or organizational taxonomy discovery.
Cricket analogy: Instead of deciding upfront how many 'types' of batsmen exist, an analyst builds a full tree merging similar players step by step — Kohli with Root, then that pair with Williamson — and only decides how many groups to name after seeing the whole tree.
Agglomerative vs. Divisive
There are two directions to build the hierarchy. Agglomerative (bottom-up) clustering, by far the more common approach, starts with every point as its own cluster and repeatedly merges the two closest clusters until only one remains. Divisive (top-down) clustering starts with all points in a single cluster and recursively splits it into smaller clusters. Divisive approaches are computationally far more expensive because evaluating every possible split at each step is combinatorially large, which is why nearly all practical hierarchical clustering implementations, including scikit-learn's AgglomerativeClustering, use the bottom-up approach.
Cricket analogy: Building a team hierarchy by starting with each of the eleven players separate and merging the two most similar into a partnership, repeating until one group remains, is the common bottom-up approach; starting with the whole squad and splitting it apart is rarer since evaluating every possible split is exhausting.
Linkage Criteria
Agglomerative clustering needs a rule for measuring distance between clusters (not just between individual points), called the linkage criterion. Single linkage uses the minimum distance between any pair of points across two clusters, which can produce elongated, chain-like clusters. Complete linkage uses the maximum pairwise distance, favoring compact, evenly-sized clusters. Average linkage uses the mean pairwise distance, balancing the two. Ward's method, one of the most commonly used defaults, merges the pair of clusters that results in the smallest increase in total within-cluster variance — it tends to produce clusters of comparable size and is often the best default for roughly spherical data.
Cricket analogy: Grouping bowlers by the closest single pair of deliveries (single linkage) can chain together very different bowlers through one shared outlier ball; grouping by the worst-matched pair (complete linkage) forces tighter, more even groups, while Ward's method, minimizing variance, tends to give the most balanced groupings for typical squads.
import numpy as np
from scipy.cluster.hierarchy import dendrogram, linkage, fcluster
from sklearn.cluster import AgglomerativeClustering
from sklearn.datasets import make_blobs
from sklearn.preprocessing import StandardScaler
X, _ = make_blobs(n_samples=150, centers=3, cluster_std=1.0, random_state=10)
X_scaled = StandardScaler().fit_transform(X)
# Build the linkage matrix for dendrogram visualization
Z = linkage(X_scaled, method='ward')
# Cut the dendrogram to extract a specific number of flat clusters
labels = fcluster(Z, t=3, criterion='maxclust')
print('Cluster sizes:', np.bincount(labels))
# Equivalent scikit-learn API for direct model fitting
model = AgglomerativeClustering(n_clusters=3, linkage='ward')
sk_labels = model.fit_predict(X_scaled)
print('Agreement with scipy labels (up to relabeling):', len(set(zip(labels, sk_labels))))A dendrogram's vertical axis (merge height) directly encodes dissimilarity: the higher up the tree two clusters merge, the more dissimilar they were. This means you can visually estimate a good number of clusters by looking for the tallest vertical gap the cut line can pass through without crossing a horizontal merge line — a technique conceptually similar to the elbow method in k-means.
Hierarchical clustering has O(n^2) to O(n^3) time and memory complexity depending on implementation, since it must track pairwise distances between all points or clusters. This makes it impractical for very large datasets (tens of thousands of points or more) without approximations, unlike k-means which scales roughly linearly.
- Hierarchical clustering builds a dendrogram showing nested merges of clusters, without requiring k to be fixed in advance.
- Agglomerative (bottom-up) clustering is far more common than divisive (top-down) clustering.
- Linkage criteria (single, complete, average, Ward) define how distance between clusters is measured and shape the resulting cluster geometry.
- Ward's method minimizes the increase in within-cluster variance at each merge and tends to produce balanced, compact clusters.
- Cutting the dendrogram at a chosen height extracts a flat set of clusters after the fact.
- Hierarchical clustering's quadratic-or-worse complexity makes it impractical for very large datasets.
Practice what you learned
1. What is a dendrogram?
2. Which approach is used by nearly all practical hierarchical clustering implementations?
3. What does Ward's linkage method optimize for at each merge step?
4. How do you obtain a specific number of flat clusters from a dendrogram?
5. Why is hierarchical clustering typically impractical for very large datasets?
Was this page helpful?
You May Also Like
k-Means Clustering
An unsupervised algorithm that partitions data into k groups by iteratively assigning points to the nearest centroid and recomputing centroids until convergence.
DBSCAN and Density-Based Clustering
Learn how DBSCAN groups points by local density rather than distance to a centroid, letting it discover arbitrarily shaped clusters and flag outliers automatically.
Dimensionality Reduction and PCA
See how Principal Component Analysis compresses many correlated features into fewer uncorrelated components while preserving most of the variance in data.
Feature Scaling and Normalization
Learn why rescaling numeric features onto comparable ranges matters, and how standardization, min-max scaling, and robust scaling each affect model behavior.