Skip to content
Tutorials Center
My learning

Topics

Lesson 28 of 39 ยท Clustering

Hierarchical Clustering

Learn agglomerative and divisive hierarchical clustering: distance matrices, single, complete, average and Ward linkage, dendrograms, cutting the tree, and BIRCH, CURE and Chameleon for large data.

Hierarchical clustering does not ask for k up front. It builds a whole hierarchy of clusters, from every record on its own up to one cluster holding everything, and you decide afterwards where to cut. The hierarchy is drawn as a tree called a dendrogram. This is useful when you want to see structure at several levels (species, genus, family) or when you do not know how many groups exist.

There are two directions:

  • Agglomerative (bottom-up): start with each record as its own cluster and repeatedly merge the two closest clusters. This is the common one (AGNES).
  • Divisive (top-down): start with one cluster and repeatedly split it (DIANA). It is rarer because the number of possible splits is huge.

Distance between clusters: linkage

Merging needs a distance between two clusters, not just two records. The rule is called the linkage:

Linkage Distance between clusters Behavior
Single Closest pair of records Finds elongated shapes; suffers "chaining" through noise
Complete Farthest pair of records Compact, similar-diameter clusters; sensitive to outliers
Average Mean of all pairwise distances A compromise (UPGMA)
Ward Merge that increases total within-cluster variance least Compact, balanced clusters; Euclidean only; often the best default
Centroid Distance between cluster means Can produce inversions in the tree

Agglomerative clustering step by step

Python Agglomerative clustering from scratch

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 merge order and the merge distances are exactly what a dendrogram draws: the height of each join is the distance at which the merge happened.

Using SciPy and cutting the tree

scipy.cluster.hierarchy.linkage returns the merge table, fcluster cuts the tree into flat clusters, and dendrogram (with no_plot=True) returns the leaf order without drawing.

Python linkage, cutting and leaf order

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 big jump in the last merge distances shows where natural clusters end: cutting where the gap between consecutive merge heights is largest is a common rule. The cophenetic correlation measures how faithfully the tree preserves the original pairwise distances (closer to 1 is better).

Compare linkage on awkward shapes

Python Linkage on two 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.

Single linkage follows the chain of nearby points around each moon; the other linkages cut the moons into compact halves.

Strengths and limits

  • No k needed in advance and the dendrogram is easy to interpret.
  • Works with any distance or similarity matrix.
  • Greedy and irreversible: once two clusters merge, they never separate, so an early mistake stays.
  • Cost: needs the distance matrix, about O(n^2) memory and O(n^2 log n) time or worse, so it does not scale to millions of records.

Hierarchical methods for large data

Several algorithms keep the hierarchical idea but scale better:

  • BIRCH scans the data once, building a compact CF-tree of cluster summaries (count, linear sum, squared sum). It clusters the summaries, so memory stays small. It prefers round clusters.
  • CURE represents each cluster by several well-scattered representative points shrunk toward the center, which finds non-spherical shapes and resists outliers.
  • Chameleon merges sub-clusters using dynamic modeling: it merges two clusters only if their interconnectivity and closeness are high relative to their internal values.
Python BIRCH on a larger set

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.

For the next family, which handles noise and arbitrary shapes directly, see density and grid clustering.

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 single-record clusters and repeatedly merges the closest pair.
  2. 2. Which linkage can create long chains of records through noise?

    Single linkage uses the closest pair, so a thin bridge of points can join two clusters.
  3. 3. What does the height of a join in a dendrogram show?

    Higher joins merge clusters that were farther apart.
  4. 4. What is a major limitation of hierarchical clustering?

    Greedy merges cannot be undone and the O(n^2) distance matrix limits dataset size, which BIRCH and CURE address.

Summary

  • Hierarchical clustering builds a tree of nested clusters; cut the dendrogram to get flat clusters.
  • Agglomerative merges bottom-up, divisive splits top-down.
  • Linkage (single, complete, average, Ward) defines cluster distance and the shape of results; Ward is a strong default.
  • BIRCH, CURE and Chameleon extend the idea to large data and complex shapes.

Next: Density-Based and Grid-Based Clustering