Distance Functions
Linkage-based clustering repeatedly merges clusters, beginning with single-point clusters.
From Points to Clusters
Linkage-based clustering starts with the finest possible grouping: every data point is placed in its own single-point cluster. The algorithm then repeatedly looks for the closest pair of clusters according to a chosen cluster-distance rule and merges that pair. The important idea is that the algorithm does not create all clusters at once. It builds larger clusters round by round.
A Merge Changes the State
Suppose an iteration begins with four clusters: A, B, C, and D. If A and B are identified as the closest pair, they become one cluster, AB. The next round therefore begins with AB, C, and D. The original points have not disappeared; only their grouping has changed.
Every merge replaces two clusters with one cluster. That is why the cluster count decreases by exactly one after each merge.
Counting Clusters Through Three Rounds
Four single-point clusters begin a linkage-based clustering process. Three merges occur.
Starting state: The clusters are A, B, C, and D, so there are four clusters.
First merge: A and B become AB. The clusters are now AB, C, and D, so there are three clusters.
Second merge: C and D become CD. The clusters are now AB and CD, so there are two clusters.
Third merge: AB and CD become ABCD. Only one cluster remains.
The count changes from four to three to two to one because every merge removes one separate cluster.
Choosing a Cluster Distance
Once clusters contain more than one point, the algorithm needs a way to describe the distance between two whole clusters. A cluster contains multiple members, so there can be several member-to-member distances between the clusters. Linkage is the rule that reduces those member-to-member distances to one cluster distance.
| Linkage method | Member-to-member distances used | Cluster distance |
|---|---|---|
| Single linkage | All relevant member-to-member distances | The minimum distance |
| Average linkage | All relevant member-to-member distances | The average distance |
| Max linkage | All relevant member-to-member distances | The maximum distance |
Three Linkage Rules
Single linkage uses the closest member-to-member connection between two clusters: their cluster distance is the minimum member-to-member distance. Average linkage uses all relevant member-to-member distances and takes their average. Max linkage uses the opposite extreme from single linkage: their cluster distance is the maximum member-to-member distance.
One Pair of Clusters, Three Distances
Two clusters have four relevant member-to-member distances: 2, 4, 7, and 9. Compare the cluster distance under single, average, and max linkage.
Single linkage: Single linkage selects the minimum of the member-to-member distances, so the cluster distance is 2.
Average linkage: Average linkage uses all four distances and takes their average: (2 + 4 + 7 + 9) divided by 4 equals 5.5.
Max linkage: Max linkage selects the maximum of the member-to-member distances, so the cluster distance is 9.
The same two clusters have a distance of 2 under single linkage, 5.5 under average linkage, and 9 under max linkage.
Defining the Algorithm
A linkage-based clustering algorithm is not fully defined by saying only that it repeatedly merges clusters. Two choices are required. First, specify the cluster-distance method, such as single, average, or max linkage. Second, specify the rule for when merging stops. Together, these choices determine how cluster distances are evaluated and when the repeated process ends.
- Cluster-distance method: how the distance between two clusters is calculated.
- Stopping rule: when the repeated merging process ends.
Mistakes in Reading Linkage
Treating single linkage as the distance between the cluster centers or an overall average.
Single linkage uses the minimum member-to-member distance, not the average.
Fix:
Choose the smallest relevant member-to-member distance for single linkage.Assuming average linkage uses only one representative pair of points.
Average linkage uses all of the relevant member-to-member distances through their average.
Fix:
Include the relevant member-to-member distances before taking their average.Assuming max linkage is the same as single linkage.
Max linkage uses the maximum distance, while single linkage uses the minimum.
Fix:
Use the largest member-to-member distance for max linkage.Thinking a merge removes data points.
A merge changes the grouping of points; it replaces two clusters with one.
Fix:
Track the new combined cluster and retain its members.Defining the algorithm with a linkage method but no stopping rule.
The algorithm requires both a cluster-distance method and a rule for when merging stops.
Fix:
State both parameters explicitly.
Apply the Mechanism
A clustering round contains the clusters P, Q, and R. The algorithm merges P and Q. Describe the cluster set in the next round, state how the number of clusters changed, and explain what additional choice is needed to calculate distances involving the new cluster PQ.
Hints
- Replace P and Q with one combined cluster.
- Count the clusters before and after the merge.
- The additional choice is the linkage rule used to summarize member-to-member distances.
Two clusters have relevant member-to-member distances 3, 5, 8, and 10. Identify the cluster distance under single, average, and max linkage. Then explain why selecting a linkage method is necessary before deciding which pair of clusters is closest.
Hints
- Single linkage selects the minimum.
- Average linkage uses all four distances and takes their average.
- Max linkage selects the maximum.
Key Takeaways
- Linkage-based clustering begins with every data point in its own single-point cluster.
- Each round identifies the closest pair of clusters according to a chosen cluster-distance rule and merges them.
- Every merge replaces two clusters with one, so the cluster count decreases by one and can eventually reach one large cluster.
- Single linkage uses the minimum member-to-member distance, average linkage uses the average, and max linkage uses the maximum.
- A complete linkage-based clustering algorithm requires both a cluster-distance method and a stopping rule.
Key Takeaways
- Linkage-based clustering builds groups through repeated merging, beginning with single-point clusters.
- The cluster count drops by one after every merge because two clusters become one.
- Single, average, and max linkage summarize member-to-member distances using the minimum, average, and maximum respectively.
- The two defining parameters are the cluster-distance method and the rule for when merging stops.