Clustering Algorithms

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

Programming

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?

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

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.

Initial state: The clustering is A, B, C, D. Each point is its own cluster, as required at the beginning of linkage-based clustering.

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.

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.

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.

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.

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

Assuming the algorithm begins with one large cluster.
Linkage-based clustering begins with every data point in its own single-point cluster.
Fix: Write the initial state as one cluster per data point, then follow the successive merges.
Choosing a pair using only the original point list after a merge.
The next decision is based on the new collection of clusters, not only on the original individual points.
Fix: Replace the merged pair with the new cluster and reconsider the distances involving the updated collection.
Confusing a point-to-point distance with a cluster-to-cluster distance.
A point distance must be extended into a distance between clusters before whole clusters can be compared.
Fix: State the linkage rule explicitly. Under single linkage, use the minimum member-to-member distance.
Forgetting why the cluster count decreases.
Two clusters are replaced by one merged cluster.
Fix: Track the count before and after each round: one merge removes exactly one cluster from the collection.
Defining the distance rule but not the stopping rule.
A clear linkage-based algorithm needs both a way to measure cluster distance and a condition for stopping.
Fix: 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

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

Key Takeaways

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.