Hierarchical Clustering
Linkage-based clustering repeatedly merges clusters, beginning with single-point clusters.
The First Round
Hierarchical clustering is a clustering approach built around repeated merging. It begins with every data point in its own single-point cluster. In each round, the algorithm looks at the existing clusters, identifies the closest pair according to a chosen cluster-distance rule, and merges that pair.
The Merge Cycle
- Start with every data point in its own single-point cluster.
- Use the selected cluster-distance method to compare the existing clusters.
- Identify the closest pair of clusters under that method.
- Merge the selected pair into one cluster.
- Repeat the comparison and merge process for the next round.
The important state change is the merge. Two existing clusters become one new cluster. Other clusters remain available for later comparisons, and the next round evaluates the updated collection of clusters rather than the original collection of individual points.
Why the Count Falls
Every merge replaces two clusters with one cluster. Therefore, the total number of clusters decreases after every merge. If a round begins with a collection of clusters, the merge removes two separate entries from that collection and puts back one combined entry. Continued merging can eventually produce one large cluster containing all domain points.
Counting Merges
Suppose a round starts with four clusters and the algorithm performs one merge.
Before the merge: There are four separate clusters.
During the merge: The algorithm selects two clusters and combines them.
After the merge: The selected pair is represented by one cluster, while the other two clusters remain separate.
The next round has three clusters. The count decreases because two clusters were replaced by one.
Three Linkage Rules
A linkage rule defines the distance between two clusters by examining distances between their members. Single, average, and max linkage use different summaries of those member-to-member distances. Because the summary can change, the same pair of clusters can receive different cluster distances under different linkage rules. That can cause different pairs to be chosen for the next merge.
| Linkage method | Cluster distance is based on |
|---|---|
| Single linkage | The minimum distance between a member of one cluster and a member of the other cluster |
| Average linkage | The average of the distances between members of the two clusters |
| Max linkage | The maximum distance between members of the two clusters |
A Linkage Comparison
One Pair of Clusters, Three Distances
Consider two hypothetical clusters. The distances between their members are 2, 5, and 9.
Single linkage: Single linkage uses the minimum member-to-member distance, so the cluster distance is 2.
Average linkage: Average linkage uses the average of the member-to-member distances, so the cluster distance is 16 divided by 3.
Max linkage: Max linkage uses the maximum member-to-member distance, so the cluster distance is 9.
The same two clusters have different distances under the three linkage rules: 2 for single linkage, 16 divided by 3 for average linkage, and 9 for max linkage.
This example shows why the linkage choice matters before the algorithm selects its next merge. The algorithm compares cluster distances, and the selected rule determines how those distances are summarized. A pair that looks close under one rule may not be the closest pair under another rule.
The Two Required Choices
A linkage-based clustering algorithm is defined by two choices. First, it needs a cluster-distance method, such as single, average, or max linkage, to determine how far apart two clusters are. Second, it needs a rule for when merging stops. The distance method controls which pair is considered closest at each round; the stopping rule controls how long the repeated merging process continues.
Common Reasoning Errors
Assuming the number of clusters stays constant
A merge replaces two clusters with one, so the cluster count decreases after every merge.
Fix:
Update the collection of clusters after each round: remove the selected pair and add their combined cluster.Treating single linkage as an average
Single linkage uses the minimum member-to-member distance.
Fix:
Match the summary to the method: minimum for single, average for average, and maximum for max linkage.Treating max linkage as the nearest connection
Max linkage uses the maximum distance between the clusters' elements.
Fix:
Look for the largest relevant member-to-member distance when computing max linkage.Specifying only a linkage method
A linkage-based clustering algorithm requires both a cluster-distance method and a stopping rule.
Fix:
State both choices before describing the algorithm.
Check Your Understanding
A linkage-based algorithm begins with six single-point clusters. It performs two merges. How many clusters exist after the second merge? Then state which linkage method uses the minimum member-to-member distance and name the second parameter required to define the algorithm.
Hints
- Each merge replaces two clusters with one, so account for one fewer cluster after each merge.
- Compare the words minimum, average, and maximum with the three linkage methods.
- The second parameter determines when the repeated merging process stops.
What do you think happens?
Two clusters have member-to-member distances of 3, 6, and 12. Which linkage method assigns the distance 3 to the pair?
Reveal answer
Answer: Single linkage
Single linkage defines the distance between two clusters using the minimum member-to-member distance.
Key Takeaways
- Hierarchical clustering begins with every data point in its own single-point cluster.
- Each round identifies the closest pair under a chosen cluster-distance rule and merges that pair.
- The number of clusters decreases after every merge because two clusters become one.
- Single, average, and max linkage use the minimum, average, and maximum member-to-member distances respectively.
- A complete linkage-based clustering definition requires both a cluster-distance method and a rule for when merging stops.
Key Takeaways
- The process starts with one cluster per data point and repeatedly merges clusters.
- Every merge reduces the cluster count by one and updates the state used in the next round.
- Single linkage uses the minimum, average linkage uses the average, and max linkage uses the maximum member-to-member distance.
- The two defining choices are the cluster-distance method and the stopping rule.