Single Linkage
Clustering is an unsupervised organization problem rather than a labeled prediction problem.
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. |
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.
Start: The current state contains six clusters, each holding one point.
Round 1: The method identifies the closest pair of current clusters and merges that pair. The state now contains five clusters.
Round 2: The method measures the current cluster relationships again, identifies the closest current pair, and merges them. The state now contains four clusters.
Later 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.
Inspect 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.
Inspect C and D: Repeat the same process for C and D. Their cluster distance is determined by their own closest cross-cluster pair.
Compare 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
Assuming every dataset has one objectively correct clustering.
Different notions of similarity and different structural goals can make multiple clusterings meaningful for the same data.
Fix:
Ask what similarity means in the task and what behavior the chosen method emphasizes.Confusing point-to-point distance with cluster-to-cluster distance.
Single linkage defines cluster distance using the closest pair with one member from each cluster.
Fix:
Search for the smallest cross-cluster point distance.Expecting a single-linkage cluster to be compact everywhere.
A chain of local similarities can connect distant ends.
Fix:
Check whether a sequence of close links explains the merge.Forgetting that cluster distances change after a merge.
Linkage-based clustering repeatedly compares the current clusters, whose membership changes after every merge.
Fix:
Reconsider the current cluster relationships at each round.Ignoring the stopping rule.
The stopping rule determines whether merging ends with several groups or continues until all points belong to one cluster.
Fix:
Include 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
Answer: Three
A merge replaces two current clusters with one, so the total number decreases by one.
Key Takeaways
- Clustering organizes unlabeled elements, so the data does not always determine one uniquely correct grouping.
- A clustering task uses elements and relationship information such as distances or similarities; it can produce hard groups, soft memberships, or a dendrogram.
- Linkage-based clustering begins with one-point clusters and repeatedly merges the closest current pair until a stopping rule ends the process.
- Single linkage measures two clusters by their closest cross-cluster pair.
- Because one close connection is sufficient, a long chain of nearby points can join groups whose distant ends are globally dissimilar.
Key Takeaways
- 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.