Skip to content
Tutorials Center
My learning

Topics

Lesson 63 of 111 ยท Unsupervised Learning

Hierarchical Clustering

Learn agglomerative clustering: how linkage types differ, how to read and cut a SciPy dendrogram, and how connectivity constraints change the result.

k-means makes you choose the number of clusters up front and gives you a single flat answer. Hierarchical clustering takes a different view: it builds a whole family of clusterings at once, from "every row is its own cluster" to "everything is one cluster", organized as a tree. You then decide where to cut the tree, after looking at it.

The most common version is agglomerative (bottom-up) clustering. This lesson explains the merge process, the linkage rules that define "distance between clusters", how to draw and cut a dendrogram with SciPy, and when connectivity constraints and hierarchical methods are the right choice.

Merging from the bottom up

Agglomerative clustering starts with n clusters of one point each. Then, repeatedly:

  1. Find the two closest clusters.
  2. Merge them into one.
  3. Record the distance at which the merge happened.

After n - 1 merges only one cluster is left. The record of merges is the tree. Cutting it at a chosen height gives a flat clustering with as many groups as the branches that cross that height.

The one missing piece is: how far apart are two clusters when each has many points? That is the job of the linkage.

Four common linkages

Single Closest pair of points.
Complete Farthest pair of points.
Average Mean of all pair distances.
Ward Merge that adds least variance.

Ward is the default and behaves most like k-means.

1 / 2

Linkage types

In scikit-learn, AgglomerativeClustering(linkage=...) accepts:

  • "ward" (default): merges the pair of clusters whose union increases the total within-cluster variance the least. It works only with Euclidean distance and tends to produce compact, similar-size clusters.
  • "complete": the distance between clusters is the largest distance between any two of their points. It avoids long chains and prefers compact groups.
  • "average": the average of all pairwise distances between the two clusters.
  • "single": the smallest distance between any two points. Clusters can grow into long chains, which is useful for elongated shapes and harmful when a few noisy points bridge two real groups.
Python Linkage on blobs and moons

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

On the blobs, ward, complete and average linkage all recover the three groups. On the moons, single linkage is the one that follows each crescent, because the crescents are connected chains of close neighbors. There is no universally best linkage; choose by the shape you expect, and check visually.

Dendrograms with SciPy

scikit-learn's estimator returns only labels. To see the whole tree, use scipy.cluster.hierarchy:

  • linkage(X, method="ward") returns the merge table: one row per merge with the two merged clusters, the distance, and the size of the new cluster.
  • dendrogram(Z) draws the tree. The height of each join is the merge distance.
  • fcluster(Z, t, criterion=...) cuts the tree and returns flat labels.

Long vertical lines in a dendrogram mean "these clusters were far apart when they merged". A good cut is often placed through the longest gap, where no merges happen over a wide range of heights.

Python Draw and cut a dendrogram

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The last merges have by far the largest distances: that is the tree telling you the data falls into three groups. fcluster labels start at 1, not 0. For big datasets, dendrograms with every leaf are unreadable; use truncate_mode="lastp", p=20 to show only the top merges.

linkage needs a matrix of pairwise distances. It computes them from X itself, so memory and time grow with the square of the number of rows. Hierarchical clustering is for thousands of rows, not millions.

Cutting the tree in scikit-learn

AgglomerativeClustering can cut for you in two ways: n_clusters=k or distance_threshold=t (with n_clusters=None). With a threshold the number of clusters is a result. The fitted attributes n_clusters_, labels_ and children_ describe it.

Python A distance threshold instead of k

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Raising the threshold merges more, so the cluster count falls. With ward linkage, thresholds are in units that depend on the data's scale and size, which is why people read them off a dendrogram instead of guessing.

Connectivity constraints

By default any two clusters can merge. A connectivity matrix restricts merges to neighbors: you pass a sparse graph (usually kneighbors_graph) and only clusters that are connected through the graph may merge. This has two effects: it often makes the algorithm faster, and it lets average (or complete) linkage follow curved shapes, because merges can only happen between neighboring clusters, so clusters grow along the data. In the experiment below the same linkage jumps from an ARI of about 0.24 to a perfect 1.00 just by adding the graph. Ward linkage on the same graph does not improve here, so try more than one linkage.

Python Connectivity lets average linkage follow curves

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

With the same linkage the result changes completely: the graph stops clusters from merging across the gap between the crescents. If the graph is not connected (some points have no path to others), scikit-learn warns and completes it, so choose n_neighbors large enough.

When to prefer hierarchical clustering

Choose it when:

  • you want to explore several levels of grouping and decide the cut after looking at the dendrogram;
  • the data has a natural hierarchy (species, products, organizations, documents);
  • the dataset is small or medium, so the quadratic cost is fine;
  • you want a deterministic result: unlike k-means it does not depend on random starts.

Avoid it for very large datasets, and remember that merges are greedy and final: once two clusters join, they never separate, so an early mistake stays. It also cannot assign new points to the fitted clusters (there is no predict); for that, train a classifier on the labels, or use an algorithm with a centroid model.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does agglomerative clustering do at each step?

    It starts with every point as its own cluster and merges the closest pair repeatedly until one cluster is left. The merge history forms the tree.
  2. 2. Which linkage can follow long, thin chains of points, and also be fooled by bridges of noise?

    Single linkage uses the closest pair of points between clusters, so clusters can stretch along chains. A few stray points between two groups can join them.
  3. 3. In a dendrogram, what does a very tall vertical line before a merge indicate?

    The height of a join is the merge distance. A big jump suggests the data naturally separates into the clusters just below that line.
  4. 4. Why can't you call predict on a fitted AgglomerativeClustering to label new points?

    The result is a merge tree over the training points. To label new data you can train a classifier on the cluster labels or choose a method with a predictive model.

Summary

  • Agglomerative clustering merges the two closest clusters repeatedly, producing a tree of every possible grouping.
  • The linkage defines cluster distance: ward (default, compact), complete, average, and single (chains).
  • SciPy's linkage, dendrogram and fcluster let you draw the tree and cut it by height or by number of clusters; scikit-learn's distance_threshold does the same.
  • A connectivity graph limits merges to neighbors, which speeds things up and lets average linkage follow curved shapes.
  • It suits small and medium data, hierarchical structure and deterministic results; merges are final and there is no predict.

Next: group by density and find noise with DBSCAN, HDBSCAN and Density Clustering.