Linkage-Based Clustering
Clustering is an unsupervised organization problem rather than a labeled prediction problem.
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…
Why One Grouping May Not Be Enough
Suppose you are given a collection of unlabeled data points and asked to organize them into groups. There may not be one objectively correct answer waiting to be discovered. Clustering is an unsupervised organization problem, so there are no supplied labels whose prediction accuracy can provide a single clear measure of success.
The result depends on what similarity means and on which structural goal the method emphasizes. One approach may emphasize keeping close points together, while another may emphasize preventing far-apart points from sharing a cluster. Both concerns can lead to meaningful but different groupings.
Clustering Inputs and Outputs
A clustering task starts with a collection of elements, written as X, together with information about how those elements relate to one another. That information may be a distance function or a similarity function. Some clustering methods also receive a requested number of clusters, k.
The output is an organization of X into groups. A hard clustering assigns each element to a separate group. A soft clustering assigns each element a vector of probabilities describing possible membership in the groups. A dendrogram is another possible output: it represents a hierarchy whose leaves are single-element sets and whose root contains the full domain.
The First Clustering Round
Linkage-based clustering builds its result progressively. At the beginning, every data point is placed in its own one-point cluster. The algorithm then examines the current collection of clusters, identifies the closest pair, and merges that pair.
A Generated First Round
Consider four generated data points named A, B, C, and D. Assume the closest pair of current clusters is the pair containing A and B.
- 1Start
The current clusters are {A}, {B}, {C}, and {D}. Every point begins alone.
- 2Compare
The algorithm compares the current clusters using its chosen distance-between-clusters rule.
- 3Merge
Because {A} and {B} are the closest current clusters in this generated situation, they become {A, B}.
- 4Update
The next round uses {A, B}, {C}, and {D} as the current cluster collection. It does not use only the original one-point clusters.
After this merge, the number of clusters has decreased from four to three.
How Cluster Distance Controls a Merge
A point-to-point distance is not enough for this procedure because the algorithm compares clusters, not just individual points. The point-to-point notion must be extended into a distance between clusters. In each round, the pair with the smallest current cluster distance is selected for merging.
Single linkage defines the distance between two clusters by finding the closest pair of members, with one member taken from each cluster. That smallest cross-cluster point-to-point distance becomes the distance between the clusters.
Finding a Single-Linkage Distance
Let cluster P contain points p1 and p2, and cluster Q contain points q1 and q2. Suppose the four cross-cluster distances are: p1 to q1 is 8, p1 to q2 is 5, p2 to q1 is 3, and p2 to q2 is 7.
- 1List cross-cluster pairs
Consider only pairs with one point from P and one point from Q.
- 2Find the closest pair
The smallest listed cross-cluster distance is 3, between p2 and q1.
- 3Assign the cluster distance
Under single linkage, the distance between P and Q is therefore controlled by the p2-to-q1 pair.
The single-linkage distance between P and Q is the closest cross-cluster distance: the distance between p2 and q1, which is 3 in this generated example.
The Chaining Effect
Single linkage can produce an unintuitive result because one close connection is enough to make two clusters appear close. After a merge, a point in the growing cluster may be close to a point in another cluster, even if many other points across the two clusters are far apart.
Repeated local connections can therefore join a long sequence of points. The points at the two distant ends of the sequence may not resemble one another directly, yet single linkage can connect them through intermediate points. This is called the chain effect in the supplied material.
Defining the Algorithm Clearly
A description such as “repeatedly merge close clusters” is incomplete. Two design choices determine the behavior of a linkage-based clustering algorithm: how distance between clusters is measured, and when the merging process stops.
| Choice | Question it answers | Single-linkage lesson |
|---|---|---|
| Cluster distance rule | How close are two current clusters? | Use the closest member-to-member pair |
| Stopping rule | When should merging end? | Specify the point at which the progressive process stops |
Both choices are needed for a clear description of the algorithm.
Common mistake Assuming that clustering must discover one uniquely correct grouping.
What it looks likeTreating the output as correct only when it matches a single expected partition.
Why it failsClustering is unsupervised, and different notions of similarity or structural goals can support different meaningful groupings.
Do this insteadState what similarity means and what structural goal the method is emphasizing.
Common mistake Comparing only the original individual points after the first merge.
What it looks likeAfter merging two points, continuing to select the next pair from the original one-point list.
Why it failsThe next decision must use the new collection of current clusters.
Do this insteadReconsider the cluster collection after every merge.
Common mistake Assuming single linkage requires every cross-cluster pair to be close.
What it looks likeRejecting a merge because most pairs across two clusters are far apart.
Why it failsSingle linkage uses the closest cross-cluster pair; one close connection can control the cluster distance.
Do this insteadSearch for the minimum member-to-member distance between the two clusters.
Common mistake Describing the method without a stopping rule.
What it looks likeSaying only that the algorithm repeatedly merges the closest clusters.
Why it failsThe distance rule and the point at which merging stops both determine the defined procedure.
Do this insteadSpecify both the cluster-distance rule and the stopping rule.
Practice the Merge Process
Imagine that the current clusters are {A}, {B}, and {C}. Under single linkage, the closest cross-cluster pair between {A} and {B} is closer than the closest cross-cluster pair between either of those clusters and {C}. What happens next, and how many clusters remain?
Hints
- The algorithm selects the closest pair of current clusters.
- A merge replaces two clusters with one cluster.
Practice Result
Starting with {A}, {B}, and {C}, suppose {A} and {B} have the smallest single-linkage distance.
- 1Select
Choose {A} and {B}, because their current cluster distance is the smallest.
- 2Merge
Replace the two selected clusters with {A, B}.
- 3Count
The current collection is now {A, B} and {C}, so there are two clusters.
The next state contains two clusters: {A, B} and {C}.
What to Remember
- 1Clustering is an unsupervised organization problem, so the same data can support multiple meaningful groupings.
- 2A clustering task takes elements and relationship information such as distances or similarities, and it produces groups, probabilities, or a hierarchy.
- 3Linkage-based clustering starts with every point in its own cluster and repeatedly merges the closest current clusters.
- 4Every merge replaces two clusters with one, so the number of clusters decreases after each round.
- 5Single linkage uses the closest pair of members across two clusters, which can create a chain connecting globally dissimilar ends.
- 6A complete algorithm description must specify both how cluster distance is measured and when merging stops.
At a glance
- Clustering does not always have one uniquely correct answer because similarity and structural goals can be defined in different ways.
- Linkage-based clustering begins with one cluster per point and builds larger clusters through successive merges.
- The closest pair of current clusters determines each merge, so the algorithm must reconsider the cluster collection after every round.
- Single linkage defines cluster distance using the closest cross-cluster pair, making it vulnerable to chaining effects.
- The two essential design choices are the cluster-distance rule and the stopping rule.