Clustering Algorithms

Linkage-based clustering begins with every data point as its own cluster.

Programming

Interactive lab

Try it: Linkage-Based Clustering

How agglomerative clustering starts from singletons and repeatedly merges the two closest clusters under single (min), complete (max) or average linkage, building a dendrogram until a stopping rule (k clusters or distance threshold r) says stop.

How it works

Start with every point in its own cluster and compute the distance matrix.
Cluster distance: single = closest pair of members (minimum), complete = farthest pair (max linkage), average = mean over all pairs.
Find the closest pair of current clusters (ties go to the pair listed first) and merge them; the cluster count drops by one.
Update the new cluster's row of the distance matrix and record the merge height in the dendrogram.
Stop when k clusters remain, or when every between-cluster distance is larger than r.

Default run (12 steps): 8 points, each its own cluster. Single linkage; stop when 3 clusters remain. … Done: 3 clusters — {A,B,C} {D,E,F,G} {H}.

Simplified: Toy 2-D data (3–10 points) with Euclidean distance. Real hierarchical clustering uses many more points, other distances and faster data structures.

Educational simulation

Loading the simulation…

From Individual Points to Groups

Linkage-based clustering starts in a deliberately fragmented state: every data point is placed in its own single-point cluster. The algorithm then repeatedly joins clusters together. At each round, it looks for the closest pair of current clusters and merges that pair. The process therefore produces a sequence of clusterings that becomes less fragmented over time.

What does the initial clustering look like when every data point starts in its own cluster?

The Repeated Merge Cycle

Each round follows the same basic cycle. First, consider the current collection of clusters. Next, compare the distances between those clusters. Then identify the closest pair and merge it. After the merge, the collection of clusters has changed, so the next round must work with the new collection rather than only with the original individual points.

What happens to the clusters from the initial state through each successive merge round?

How does the algorithm compare distances between clusters and decide which pair to merge next?

Why does merging two clusters reduce the total number of clusters by one?

Single-Linkage Distance

A point-to-point distance is not automatically a distance between clusters. The algorithm must extend the point-level distance so that it can compare whole clusters. Single linkage makes this extension by using the minimum member-to-member distance between two clusters. In other words, inspect every point in one cluster against every point in the other cluster, and use the closest pair as the distance between the clusters.

How is the distance between two clusters determined from the closest pair of points they contain?

Key point

Single linkage does not summarize two clusters by an average member distance in the supplied definition. It uses the closest member-to-member connection between them.

A Complete Merge Trace

Consider four data points named A, B, C, and D. The following numerical distances are a generated teaching example. They are chosen to show why the algorithm must reconsider the cluster collection after every merge.

Pair	Distance
A and B	1
A and C	4
A and D	7
B and C	3
B and D	6
C and D	2

Generated point-to-point distances for the merge trace

Worked example

Four Points Under Single Linkage

Starting with A, B, C, and D as separate clusters, follow the closest-pair merge rule using the generated distances in the table.

1
Initial state
The clustering is A, B, C, D. Each point is its own cluster, as required at the beginning of linkage-based clustering.
2
Round 1
The smallest point-to-point distance is between A and B, with distance 1. Merge them to create cluster AB. The current clustering is AB, C, D.
3
Reconsider the new collection
The distance from AB to C is the smaller of the A-to-C and B-to-C distances, so it is 3. The distance from AB to D is the smaller of the A-to-D and B-to-D distances, so it is 6. The C-to-D distance is 2.
4
Round 2
Among the current clusters, C and D are closest, with distance 2. Merge them to create CD. The current clustering is AB, CD.
5
Round 3
For AB and CD, inspect all cross-cluster member pairs. The smallest of those distances is 3, from B to C. Single linkage therefore assigns distance 3 to the pair of clusters and merges them.

Result

The sequence is A, B, C, D; then AB, C, D; then AB, CD; and finally ABCD. Each round uses the clusters produced by the preceding round.

The important transition occurs after A and B merge. The algorithm does not continue comparing only A, B, C, and D as if nothing changed. It now compares AB, C, and D. That is why a cluster-distance definition is necessary: once a cluster contains multiple points, the algorithm needs a rule for comparing that cluster with another cluster.

Defining the Algorithm Completely

Two choices are needed to define a linkage-based clustering algorithm clearly. The first is how to measure the distance between two clusters. Single linkage is one choice: it uses the minimum distance between their members. The second is when the repeated merging should stop. Without both choices, the merging process is not fully specified: the distance rule determines which pair is closest, while the stopping rule determines how far the sequence continues.

What two choices must be specified to define the algorithm: how cluster distance is measured and when merging stops?

Common Reasoning Errors

Common mistake
Assuming the algorithm begins with one large cluster.
What it looks like
Treating A, B, C, and D as one group before any round occurs.
Why it fails
Linkage-based clustering begins with every data point in its own single-point cluster.
Do this instead
Write the initial state as one cluster per data point, then follow the successive merges.
Common mistake
Choosing a pair using only the original point list after a merge.
What it looks like
After A and B become AB, continuing to compare only A, B, C, and D without treating AB as a new cluster.
Why it fails
The next decision is based on the new collection of clusters, not only on the original individual points.
Do this instead
Replace the merged pair with the new cluster and reconsider the distances involving the updated collection.
Common mistake
Confusing a point-to-point distance with a cluster-to-cluster distance.
What it looks like
Trying to compare AB with CD without a rule for turning their member distances into one cluster distance.
Why it fails
A point distance must be extended into a distance between clusters before whole clusters can be compared.
Do this instead
State the linkage rule explicitly. Under single linkage, use the minimum member-to-member distance.
Common mistake
Forgetting why the cluster count decreases.
What it looks like
Expecting the number of clusters to stay the same after merging A and B.
Why it fails
Two clusters are replaced by one merged cluster.
Do this instead
Track the count before and after each round: one merge removes exactly one cluster from the collection.
Common mistake
Defining the distance rule but not the stopping rule.
What it looks like
Saying single linkage is being used but not stating when the repeated merging ends.
Why it fails
A clear linkage-based algorithm needs both a way to measure cluster distance and a condition for stopping.
Do this instead
Record both choices whenever you describe the algorithm.

Apply the Merge Logic

EASY

Suppose the current clusters are PQ, R, and S. The cluster distances are 5 between PQ and R, 2 between PQ and S, and 4 between R and S. Which pair merges next? After that merge, what must the algorithm reconsider before choosing the following pair?

Hints

Choose the pair with the smallest distance among the current clusters.
After merging, replace the selected pair with one new cluster.
The next decision must use the updated cluster collection and its cluster distances.

Your attempt (not saved)

The immediate merge is PQ with S because their distance is 2, the smallest current cluster distance. The new collection is PSQ and R. Before another merge is selected, the algorithm must reconsider the distance between those new clusters. If single linkage is used, that distance is determined by the closest member-to-member distance across the two clusters.

What to Remember

1
Linkage-based clustering begins with every data point in its own cluster.
2
Each round merges the closest pair of current clusters, so the cluster count decreases by one after each merge.
3
After a merge, the algorithm must reconsider the updated cluster collection.
4
Single linkage defines the distance between two clusters as the minimum member-to-member distance between them.
5
A complete description specifies both the cluster-distance rule and when merging stops.

At a glance

Linkage-based clustering starts with one cluster per data point.
The algorithm repeatedly merges the closest pair of current clusters.
Every merge replaces two clusters with one, reducing the total by one.
Single linkage uses the closest pair of members across two clusters to define their distance.
A clear algorithm description includes both the cluster-distance rule and the stopping condition.

More concepts starting with C