ML7.3 · LESSON 3 OF 6

Hierarchical clustering

Perform a clustering update and explain dimensionality reduction, mixtures and anomaly detection.

THE IDEA

Building a tree of groups, bottom up

k-means makes you choose k first and gives one flat split. Agglomerative hierarchical clustering starts the other way round: every point is its own cluster, and at each step it merges the two closest clusters. After n − 1 merges everything is one cluster. The record of merges, drawn as a tree with the merge distance as height, is a dendrogram. Cutting the tree with a horizontal line gives a flat clustering at any k you like, so you need not decide k in advance.

One question is still open: how far apart are two clusters, when each holds several points? That rule is the linkage.

Single: the smallest distance between a point in one and a point in the other (closest pair).
Complete: the largest such distance (farthest pair).
Average: the mean of all cross-pair distances.

For points 0 and 1 against the point 5: single gives 4, complete gives 5, average gives 4.5. Same data, three different answers to "how far apart?"

Step through the merges

Data:Linkage:

Every point is its own cluster. Press Merge to join the two closest clusters under single linkage.

merge heights so far: none

Press Merge. The dashed black line joins the pair that defines the last merge. The red dashed line on the tree is the cut that leaves the clusters coloured on the left. Start with the snake and blob data and single linkage, then switch the linkage without changing the data.

Merge heights only go up, because a merged cluster is never closer to anything than the pair that formed it was (for these three linkages). That is why the tree has no crossing lines. On the snake-and-blob data the last merge under single linkage happens at height 3.83, under complete linkage at 7.

Same data, different trees

Single linkage chains. A long thin cluster is a chain of points each close to the next, so single linkage happily joins it end to end. Its weakness: one stray point, or a few points forming a bridge, can link two groups or become a cluster of its own. On the data with a stray point the last two single-linkage merges are at 2.65 and 3.1: the stray point is the very last thing to join, so a 2-cluster cut gives you the stray point alone and everything else.

Complete linkage wants compact, round clusters. It measures the farthest pair, so it dislikes long clusters: on the snake-and-blob data the 2-cluster cut slices the snake in half and glues one half to the blob, because the farthest-pair distance from end to end of the snake (7) is bigger than the farthest-pair distance from half a snake to the blob. On the stray-point data complete linkage joins the stray point to the blob next to it (merge height 5.25) and the final cut matches the two real blobs. Average linkage sits between the two and works on both of these datasets, but that is a property of this data, not a promise.

Predict first. Changing the linkage but keeping the same data, the dendrogram...

Cost

n points -> n - 1 merges. A straightforward version recomputes
cluster-to-cluster distances each step; it is fine for hundreds of points
but slow for millions, which is why k-means is the usual choice for huge data.

Chapter context

Unsupervised methods expose structure according to their objectives and assumptions. They do not discover a single objectively correct organization of a dataset; changing distance, dimension or density assumptions can change the result.

TRY IT YOURSELF

Part 1. Do it on the plot

The "two clusters" tasks need you to stop exactly when two clusters remain: the colours show the cut.

Data:Linkage:

Every point is its own cluster. Press Merge to join the two closest clusters under single linkage.

merge heights so far: none

To do: Press Merge until a single cluster is left (the dendrogram reaches the top)
To do: Snake and blob data: with single linkage, stop at two clusters and see it recover the snake and the blob
To do: Same data, complete linkage, two clusters: see it cut the snake in half instead
To do: Switch to the data with a stray point: find a linkage whose two-cluster cut recovers the two blobs (with the stray point on the left)

Part 2. Do it in code

link_dist(X, A, B, method) takes two lists of row indices A and B and returns the linkage distance between those groups of points (Euclidean): 'single' is the smallest pairwise distance, 'complete' the largest, 'average' the mean over all pairs. Raise ValueError for any other method.
merge_heights(X, method) runs agglomerative clustering from one cluster per point and returns the list of n - 1 distances at which successive merges happen (always merging the closest pair of clusters). One point gives an empty list.

import numpy as np

def link_dist(X, A, B, method):
    # single = min, complete = max, average = mean of pairwise distances
    pass

def merge_heights(X, method):
    # distances of the n - 1 merges, in order
    pass

X = np.array([[0.0], [1.0], [5.0]])
print(link_dist(X, [0, 1], [2], "single"))

Ctrl/⌘ + Enter runs it

Stuck, or something not working? You can come back to it any time.

CHECK YOUR UNDERSTANDING

Can changing linkage change the dendrogram?

AYesBNo

Chapter reference: math, worked example & code

This section belongs to the whole chapter, so it is the same on every lesson in it and may cover a different lesson's topic. The code for the experiment you just ran is inside the experiment itself.

Math and notation

J=\sum_i\|x_i-\mu_{c_i}\|^2,\quad \mu_k=\frac1{|C_k|}\sum_{i\in C_k}x_i.

For centered data X, PCA uses leading eigenvectors of $X^TX/(n-1)$ , or an equivalent SVD. Centering and feature scaling are separate choices.

For a Gaussian mixture, EM responsibilities are

r_{ik}=\frac{\pi_k\mathcal N(x_i\mid\mu_k,\Sigma_k)}{\sum_j\pi_j\mathcal N(x_i\mid\mu_j,\Sigma_j)}.

Mixing weights pi are nonnegative and sum to one; each row of responsibilities also sums to one. Weighted sufficient-statistic updates differ from hard k-means assignments.

Worked example

With points [0,2,8,10] and starting centers [0,10], assignments are [0,2] and [8,10]. Updated means are 1 and 9. Squared errors are 1,1,1,1, totaling 4. This example gives one iteration; it does not prove that every initialization finds the best partition.

Reference code

The following example uses the Python standard library and does not call a remote service.

points, centers = [0,2,8,10], [0,10]
groups = [[x for x in points if min(range(2), key=lambda j: (x-centers[j])**2) == i] for i in range(2)]
updated = [sum(group)/len(group) for group in groups]
assert updated == [1,9]
assert sum((x-c)**2 for group,c in zip(groups,updated) for x in group) == 4

Python examples are provided for study and local execution; this page does not execute Python.

Common mistakes

Clusters are objective-dependent. PCA maximizes variance, which may not correspond to useful semantic structure. Anomaly detection is not the same as identifying known fraud classes.