Distance Functions
The same two clusters can receive different distances under single, average, and max linkage.
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.
Loading the simulation…
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.
- 1Starting state
The clusters are A, B, C, and D, so there are four clusters.
- 2First merge
A and B become AB. The clusters are now AB, C, and D, so there are three clusters.
- 3Second merge
C and D become CD. The clusters are now AB and CD, so there are two clusters.
- 4Third 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 |
The linkage method determines how the member-to-member distances are summarized into one distance between clusters.
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.
- 1Single linkage
Single linkage selects the minimum of the member-to-member distances, so the cluster distance is 2.
- 2Average linkage
Average linkage uses all four distances and takes their average: (2 + 4 + 7 + 9) divided by 4 equals 5.5.
- 3Max 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
Common mistake Treating single linkage as the distance between the cluster centers or an overall average.
What it looks likeTwo clusters have member-to-member distances 2, 4, 7, and 9, but the cluster distance is reported as 5.5 for single linkage.
Why it failsSingle linkage uses the minimum member-to-member distance, not the average.
Do this insteadChoose the smallest relevant member-to-member distance for single linkage.
Common mistake Assuming average linkage uses only one representative pair of points.
What it looks likeUsing only the nearest pair to describe the distance between two clusters under average linkage.
Why it failsAverage linkage uses all of the relevant member-to-member distances through their average.
Do this insteadInclude the relevant member-to-member distances before taking their average.
Common mistake Assuming max linkage is the same as single linkage.
What it looks likeSelecting the distance 2 from the set 2, 4, 7, and 9 for both methods.
Why it failsMax linkage uses the maximum distance, while single linkage uses the minimum.
Do this insteadUse the largest member-to-member distance for max linkage.
Common mistake Thinking a merge removes data points.
What it looks likeAfter A and B become AB, counting only AB and forgetting that A and B are still members of the new cluster.
Why it failsA merge changes the grouping of points; it replaces two clusters with one.
Do this insteadTrack the new combined cluster and retain its members.
Common mistake Defining the algorithm with a linkage method but no stopping rule.
What it looks likeChoosing average linkage without stating when repeated merging ends.
Why it failsThe algorithm requires both a cluster-distance method and a rule for when merging stops.
Do this insteadState 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
- 1Linkage-based clustering begins with every data point in its own single-point cluster.
- 2Each round identifies the closest pair of clusters according to a chosen cluster-distance rule and merges them.
- 3Every merge replaces two clusters with one, so the cluster count decreases by one and can eventually reach one large cluster.
- 4Single linkage uses the minimum member-to-member distance, average linkage uses the average, and max linkage uses the maximum.
- 5A complete linkage-based clustering algorithm requires both a cluster-distance method and a stopping rule.
At a glance
- 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.