\( \newcommand{\vect}[1]{\boldsymbol{\mathbf{#1}}} \newcommand{\mat}[1]{\boldsymbol{\mathbf{#1}}} \newcommand{\R}{\mathbb{R}} \newcommand{\E}{\mathbb{E}} \newcommand{\Prob}{\mathbb{P}} \newcommand{\T}{^{\top}} \newcommand{\norm}[1]{\lVert #1 \rVert} \newcommand{\abs}[1]{\lvert #1 \rvert} \newcommand{\ihat}{\mkern1mu\hat{\boldsymbol{\imath}}\mkern2mu} \newcommand{\jhat}{\mkern1mu\hat{\boldsymbol{\jmath}}\mkern2mu} \newcommand{\pd}[2]{\frac{\partial #1}{\partial #2}} \newcommand{\argmax}{\operatorname*{arg\,max}} \newcommand{\argmin}{\operatorname*{arg\,min}} \newcommand{\cdata}[1]{\class{c-data}{#1}} \newcommand{\cmodel}[1]{\class{c-model}{#1}} \newcommand{\ctruth}[1]{\class{c-truth}{#1}} \newcommand{\cgrad}[1]{\class{c-grad}{#1}} \newcommand{\closs}[1]{\class{c-loss}{#1}} \newcommand{\cparam}[1]{\class{c-param}{#1}} \newcommand{\csecond}[1]{\class{c-second}{#1}} \renewcommand{\,}{\mkern3mu} \)

ML03.2 · Hierarchical clustering

A free, illustrated module of 4 lessons and one interactive in ML03 Unsupervised Learning: Merging from the bottom up; Linkage: what closest means; Cutting the dendrogram; Single linkage, spanning trees and large data.

ML03.2 L2 · Intermediate 4 lessons · about 115 min Live · in review

Part of ML03 Unsupervised Learning in the Machine Learning track.

Hierarchical clustering builds every clustering at once. Start with each point alone, keep merging the two closest clusters, and record the merges as a dendrogram. These four lessons run the merging by hand and from scratch, compare what single, complete, average and Ward linkage mean by closest, cut the tree into clusters and measure its faithfulness with the cophenetic correlation, and show that single linkage is a minimum spanning tree, fast but fragile, before turning to methods for larger data.

What you need first. Distances between points (ML01.3) and the k-means objective with its running example of nine points (ML03.1). Means and sums of squares; a first look at Pearson correlation helps in the third lesson. NumPy and SciPy for the code.

Lessons

1. Merging from the bottom up ML03.2.1 25 min

   Agglomerative clustering starts with every point alone and keeps merging the two closest clusters. Run it by hand on six values, read the dendrogram that records every merge, and build it from scratch with a distance matrix.

2. Linkage: what closest means ML03.2.2 30 min

   Single, complete and average linkage measure the gap between two clusters by their closest, farthest or average pair, and Ward’s linkage by the rise in squared error. Derive Ward’s formula and the Lance-Williams update, and see the four trees of the six values.

3. Cutting the dendrogram ML03.2.3 30 min

   A horizontal cut turns a dendrogram into clusters. Cut by height or by number of clusters, measure how faithfully the tree keeps the distances with the cophenetic correlation, and match SciPy’s fcluster and cophenet and scikit-learn’s AgglomerativeClustering.

4. Single linkage, spanning trees and large data ML03.2.4 30 min

   Single linkage is a minimum spanning tree in disguise. Prove that Kruskal’s algorithm adds edges in the order single linkage merges, see why that makes single linkage fast and fragile, and meet bisecting k-means and connectivity constraints for larger data.

The interactive

ML03.2-X1 · Dendrogram cutter. Up to twelve draggable points in the plane with their dendrogram beside them. Choose single, complete, average or Ward linkage, step through the merges one at a time, and drag the cut line (or use its slider) to colour the clusters it makes, with the merge heights and the cophenetic correlation in the read-out. It lives in Cutting the dendrogram.