Hierarchical and Density Clustering

In Lesson 3, k-means sorted Maria's coffee-shop regulars into three neat loyalty tiers. But it asked two things of her that will not always be fair. First, she had to tell it the number of groups up front (centers = 3). Second, it only ever draws round, blob-shaped groups, because it measures everything by distance to a centre.

Now Maria is scouting a second location, so she pulls a map of where her 88 regulars actually live: each customer is a dot, placed by how many kilometres east and north of downtown they are. Two problems break k-means here. Her neighbourhoods are not round (one runs in a long thin strip along Main Street), and a handful of customers live scattered far out in the countryside, belonging to no neighbourhood at all.

This lesson gives Maria two tools that fix exactly those two limits:

• Hierarchical clustering builds a whole tree of nested groups, so she can read every possible number of neighbourhoods at once and never has to guess a number.
• Density clustering (DBSCAN) finds groups by where the dots are crowded, so it traces a group of any shape and quietly sets the far-flung stragglers aside as noise.

By the end of this lesson you will be able to:

• Explain how a dendrogram is built by merging, and cut it into any number of clusters you want
• Run hclust and cutree in R, and pick a linkage rule
• Say why k-means fails on odd shapes and outliers, and use DBSCAN's core, border and noise points to cluster by density instead

Prerequisites: you can run R and read its output, and you have done Lesson 3 on k-means (what clustering is, Euclidean distance, and why you scale features before measuring distance). Every new symbol is defined as it appears.

A tree built by merging

Hierarchical clustering never asks you for a number of groups. Instead it builds a family tree of the data, from the bottom up, using one stubbornly simple rule:

1. Start with every customer in a group of their own: 88 dots, 88 tiny groups.
2. Find the two groups that are closest together and merge them into one.
3. Repeat, merging the next-closest pair, until every dot has joined a single group at the top.

The record of which groups merged, and at what distance, is drawn as a dendrogram, the interactive tree below. Read it from the bottom up. Each leaf is one customer. Every time two branches join, that is a merge, and the height of the join is how far apart those two groups were when they merged. Similar customers join low down; groups that are very different only join near the top.

Here is the payoff. Because the tree holds every merge, you get every possible clustering at once. A horizontal line sliding down through the tree turns each branch it crosses into one cluster. Cut high and you get a few big groups; cut low and you get many small ones. Drag the cut line in the dendrogram below and watch the number of clusters change: that single tree is really many clusterings stacked on top of each other, and you choose the one you want after seeing them all.