Single Linkage
Linkage-based clustering builds its result progressively.
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…
Grouping Without Labels
Clustering organizes data points into groups without being given correct group labels in advance. That makes it different from a labeled prediction problem: there is no provided answer set whose prediction accuracy can automatically decide whether one grouping is correct. Instead, the result depends on what similarity means and what structural goal the method emphasizes.
Clustering Inputs and Outputs
A clustering task starts with a collection of elements, written as X, and information about how those elements relate to one another. That relationship information may be a distance function or a similarity function. Some clustering methods also receive a requested number of clusters, k. The algorithm uses these inputs to produce an organization of X into groups.
| Possible output | What it represents |
|---|---|
| Hard clustering | Each element is assigned to a separate group. |
| Soft clustering | Each element receives a vector of probabilities describing possible membership in the groups. |
| Dendrogram | A hierarchy whose leaves are single-element sets and whose root contains the full domain. |
Clustering can return different forms of organization.
Why Groupings Can Differ
A dataset does not always contain one uniquely correct grouping. Similarity is not necessarily transitive: object A may resemble object B, and object B may resemble object C, while A and C are still quite different. Cluster membership is transitive, however. If A and B share a cluster and B and C share that same cluster, A and C also share it. A clustering method must therefore resolve a conflict that the data itself may leave ambiguous.
| Emphasis | Possible consequence |
|---|---|
| Keeping close points together | Points connected by local similarity may be grouped. |
| Preventing far-apart points from sharing a cluster | A method may resist grouping points that are globally far apart. |
Different structural goals can make multiple clusterings meaningful.
The Repeated Merge Process
Linkage-based clustering builds its result progressively. It begins with every data point in its own one-point cluster. In each round, it identifies the closest pair of current clusters and merges them. Since two groups become one, the number of clusters decreases after every merge. If the procedure continues without stopping, all points eventually belong to one cluster.
Tracing Three Merge Rounds
Suppose a linkage-based method starts with six one-point clusters: A, B, C, D, E, and F.
- 1Start
The current state contains six clusters, each holding one point.
- 2Round 1
The method identifies the closest pair of current clusters and merges that pair. The state now contains five clusters.
- 3Round 2
The method measures the current cluster relationships again, identifies the closest current pair, and merges them. The state now contains four clusters.
- 4Later rounds
The same find-and-merge cycle continues. A stopping rule determines whether the process ends with several groups or continues until one group contains all points.
The important state change is not merely that points are grouped; after every merge, the next distance comparison is made between the new current clusters.
Closest-Pair Distance
Single linkage defines the distance between two clusters by finding the closest pair of members, with one member taken from each cluster. The smallest point-to-point distance becomes the distance between the two clusters.
Comparing Two Candidate Cluster Pairs
Assume Cluster A and Cluster B contain several points, as do Cluster C and Cluster D. The closest cross-cluster pair for A and B is very close, while every cross-cluster pair for C and D is farther apart.
- 1Inspect A and B
Look at every pair formed by one point from A and one point from B. Single linkage keeps the closest of those pairs as the distance between A and B.
- 2Inspect C and D
Repeat the same process for C and D. Their cluster distance is determined by their own closest cross-cluster pair.
- 3Compare cluster distances
The pair of clusters with the smaller closest-pair distance is treated as the closer pair for the next merge.
Single linkage does not require every point in one cluster to be close to every point in the other cluster. One close cross-cluster connection is enough to make the cluster pair appear close under this rule.
The Chaining Effect
The closest-pair rule creates a chaining effect. Imagine a sequence in which each point is close to the next point, but the points at the two ends are far apart. Once one end of the sequence joins a growing cluster, the next nearby point can connect to it. Repeated local connections can eventually join the entire sequence, even when its distant ends do not resemble one another.
The unintuitive part is that single linkage evaluates the closest available connection between clusters, not the overall separation of their most distant members. A chain can therefore connect globally dissimilar regions through a series of locally close links. This behavior is not a separate accident added to the method; it follows directly from choosing the minimum cross-cluster distance.
Common Interpretation Mistakes
Common mistake Assuming every dataset has one objectively correct clustering.
What it looks likeTreating the first grouping produced by a method as the only meaningful organization.
Why it failsDifferent notions of similarity and different structural goals can make multiple clusterings meaningful for the same data.
Do this insteadAsk what similarity means in the task and what behavior the chosen method emphasizes.
Common mistake Confusing point-to-point distance with cluster-to-cluster distance.
What it looks likeAssuming two clusters must be compared using every point equally or using a representative point.
Why it failsSingle linkage defines cluster distance using the closest pair with one member from each cluster.
Do this insteadSearch for the smallest cross-cluster point distance.
Common mistake Expecting a single-linkage cluster to be compact everywhere.
What it looks likeRejecting a result because its points are connected by a long sequence rather than packed into one tight region.
Why it failsA chain of local similarities can connect distant ends.
Do this insteadCheck whether a sequence of close links explains the merge.
Common mistake Forgetting that cluster distances change after a merge.
What it looks likeContinuing to use the distances from the initial one-point clusters after two clusters have been combined.
Why it failsLinkage-based clustering repeatedly compares the current clusters, whose membership changes after every merge.
Do this insteadReconsider the current cluster relationships at each round.
Common mistake Ignoring the stopping rule.
What it looks likeDescribing the final result without stating when the merging process ended.
Why it failsThe stopping rule determines whether merging ends with several groups or continues until all points belong to one cluster.
Do this insteadInclude the stopping condition when explaining a linkage-based result.
Check Your Understanding
Two current clusters each contain many points. Exactly one point in the first cluster is very close to exactly one point in the second cluster, while most other cross-cluster pairs are far apart. Under single linkage, how does this close pair affect the distance between the clusters, and what possible chaining behavior should you watch for?
Hints
- Single linkage searches for the closest pair with one member from each cluster.
- The smallest cross-cluster distance determines the cluster distance.
- Consider what could happen if another cluster has one point close to the growing combined cluster.
What do you think happens?
A linkage-based process currently has four clusters. It merges the closest pair and does not stop. How many clusters remain immediately after that merge?
Reveal answer
Three
A merge replaces two current clusters with one, so the total number decreases by one.
Key Takeaways
- 1Clustering organizes unlabeled elements, so the data does not always determine one uniquely correct grouping.
- 2A clustering task uses elements and relationship information such as distances or similarities; it can produce hard groups, soft memberships, or a dendrogram.
- 3Linkage-based clustering begins with one-point clusters and repeatedly merges the closest current pair until a stopping rule ends the process.
- 4Single linkage measures two clusters by their closest cross-cluster pair.
- 5Because one close connection is sufficient, a long chain of nearby points can join groups whose distant ends are globally dissimilar.
At a glance
- Clustering is an unsupervised organization problem rather than labeled prediction.
- Multiple clusterings can be meaningful because similarity and structural goals can be interpreted in different ways.
- Linkage-based clustering repeatedly merges the closest current clusters, reducing the cluster count after each merge.
- Single linkage uses the closest pair of points across two clusters.
- The resulting chaining effect can connect distant regions through a sequence of local similarities.