Linkage-Based Clustering Algorithms
Clustering is an unsupervised grouping task.
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…
A Boundary Before the Algorithm
The supplied material supports a clear account of clustering and linkage-based algorithms, but it does not define PCA, variance maximization, principal components, or dimensionality reduction. That boundary matters: clustering and PCA should not be treated as two names for the same task. This article therefore focuses on the supported topic: grouping data points according to similarity and distance, then repeatedly merging groups according to a chosen linkage rule.
From Data Points to Groups
Clustering is an unsupervised grouping task. A clustering model receives data points together with a way to judge distance between points. Its output is a grouping of those points into clusters. Because the result depends on similarity and distance choices, changing those choices can produce different clusterings.
| Task | What the supplied material establishes |
|---|---|
| Clustering | Groups data points using similarity and distance choices. |
| PCA and dimensionality reduction | Not defined by the supplied material. |
This comparison marks the evidence boundary rather than defining PCA.
The Starting State
Linkage-based clustering begins in a maximally fragmented state: every data point is its own single-point cluster. The algorithm does not begin with several large groups. Instead, it constructs larger clusters by repeatedly selecting two existing clusters and merging them.
A Generated Starting State
Begin linkage-based clustering with four data points named A, B, C, and D.
- 1Create one cluster per point
The initial cluster collection is {A}, {B}, {C}, and {D}. Each point is separate.
- 2Prepare for a merge
The algorithm compares the distances between the current clusters and identifies the closest pair according to its linkage rule.
The process starts with four clusters, not one and not an already chosen grouping.
The Repeated Merge Cycle
Each round follows the same basic cycle. First, inspect the current collection of clusters. Next, determine the distance between candidate clusters. Then select the closest pair and merge it. Finally, replace the two old clusters with the new combined cluster before beginning the next round. The next decision must use this updated collection, because a merge changes which clusters are available for comparison.
Why the Count Drops
Suppose a round begins with two distinct clusters, X and Y. A merge removes X and Y from the current collection and inserts one combined cluster. Therefore, that round replaces two cluster entries with one, so the number of clusters decreases by one. This is why repeated merging produces progressively less fragmented clusterings.
Counting the Rounds
A generated process starts with four clusters and performs one merge.
- 1Before the merge
There are four current clusters.
- 2Perform the merge
Two clusters are replaced by one combined cluster.
- 3Count afterward
The other two clusters remain, and the merged pair contributes one cluster, giving three clusters.
One merge changes the count from four clusters to three clusters.
Single Linkage Distance
Single Linkage defines the distance between two clusters as the minimum distance between any member of the first cluster and any member of the second cluster.
This definition extends a point-to-point distance into a cluster-to-cluster distance. To compare cluster A with cluster B, consider all distances from members of A to members of B. Single Linkage keeps the smallest one. The pair of points producing that smallest distance is enough to determine the distance between the two clusters.
Finding a Single Linkage Distance
Generated example: Cluster A contains A1 and A2. Cluster B contains B1 and B2. The four cross-cluster distances are 7, 4, 6, and 9.
- 1List cross-cluster distances
Compare every member of Cluster A with every member of Cluster B.
- 2Find the minimum
Among 7, 4, 6, and 9, the smallest distance is 4.
- 3Apply the linkage rule
Single Linkage uses that smallest member-to-member distance as the distance between the two clusters.
The Single Linkage distance between Cluster A and Cluster B is 4 in this generated example.
The Two Defining Decisions
A linkage-based clustering algorithm is not fully specified by saying only that it merges clusters. Two decisions are required. First, define how to turn point-to-point distances into a distance between clusters. Single Linkage makes this the minimum member-to-member distance. Second, define when the repeated merging should stop. Different choices for either decision can lead to different clusterings.
| Decision | Question it answers | Single Linkage process |
|---|---|---|
| Cluster-distance rule | How far apart are two current clusters? | Use the minimum distance between any member of one cluster and any member of the other. |
| Stopping rule | When should repeated merging stop? | The supplied material requires a stopping choice but does not specify one particular stopping rule. |
These two decisions specify the linkage-based algorithm clearly.
Mistakes in Tracing the Process
Common mistake Treating clustering and PCA as the same task.
What it looks likeSaying that the source defines PCA as a clustering method.
Why it failsThe supplied material defines clustering but does not define PCA, variance maximization, principal components, or dimensionality reduction.
Do this insteadKeep the topics separate and use this material to explain clustering only.
Common mistake Starting with preselected large clusters.
What it looks likeBeginning a linkage-based trace with two groups when every point should initially stand alone.
Why it failsLinkage-based clustering begins with every data point as its own cluster.
Do this insteadWrite the initial state as one single-point cluster for each data point.
Common mistake Keeping the old cluster list after a merge.
What it looks likeMerging X and Y but continuing to compare X and Y as separate current clusters in the next round.
Why it failsThe next decision is based on the new cluster collection.
Do this insteadRemove the two merged clusters and insert their combined cluster before continuing.
Common mistake Using just one arbitrarily chosen pair of members for Single Linkage.
What it looks likeMeasuring two clusters using the distance between their first listed points.
Why it failsSingle Linkage uses the minimum distance across all member-to-member comparisons between the two clusters.
Do this insteadConsider all cross-cluster member distances and select the smallest.
Common mistake Forgetting the stopping decision.
What it looks likeDefining how cluster distances are computed but never stating when merging ends.
Why it failsThe supplied material identifies both the cluster-distance rule and the stopping choice as necessary decisions.
Do this insteadState both decisions when specifying the algorithm.
Practice the State Changes
A linkage-based process currently contains the clusters {A}, {B}, {C}, and {D}. The algorithm selects {B} and {D} as the closest pair and merges them. Describe the new cluster collection, explain how the cluster count changes, and state what must happen before the next merge is selected.
Hints
- Replace the two selected clusters with one combined cluster.
- Count the entries before and after the replacement.
- The next decision must use the updated cluster collection.
Generated Single Linkage exercise: Cluster P contains P1 and P2. Cluster Q contains Q1 and Q2. Their cross-cluster distances are 8, 3, 5, and 6. Which value represents the Single Linkage distance between P and Q, and why?
Hints
- List all distances between a member of P and a member of Q.
- Single Linkage selects the minimum member-to-member distance.
The Algorithm in One Pass
- 1Clustering is an unsupervised task that groups data points using similarity and distance choices.
- 2The supplied material does not define PCA or dimensionality reduction, so those ideas should not be merged with the clustering account presented here.
- 3Linkage-based clustering starts with every data point in its own cluster.
- 4Each round selects the closest pair of current clusters, merges them, and updates the cluster collection.
- 5A merge replaces two clusters with one, so the cluster count decreases by one.
- 6Single Linkage defines cluster distance as the minimum distance between any member of one cluster and any member of the other.
- 7A complete algorithm specification needs both a cluster-distance rule and a stopping rule.
Key Takeaways
- Linkage-based clustering builds groups by repeatedly merging current clusters.
- It begins with one single-point cluster per data point and decreases the cluster count by one after each merge.
- Single Linkage measures two clusters by their closest pair of members.
- The next merge must be chosen from the updated cluster collection.
- A linkage-based algorithm requires a cluster-distance rule and a stopping rule.