Single Linkage Clustering
The supplied source pack does not define PCA or variance maximization.
A Boundary Between Topics
Single Linkage Clustering is a clustering method. Clustering is an unsupervised grouping task: it organizes observations according to choices about similarity and distance. The supplied material does not define PCA, variance maximization, principal components, or dimensionality reduction. Therefore, this lesson establishes what the material does support: how clustering groups observations and how Single Linkage compares clusters during that process.
Model Input and Output
A clustering model receives observations together with a basis for judging similarity or distance. The source material emphasizes that the original input supplies a distance between points. The model then produces a grouping of those observations. Because the similarity and distance choices influence the result, changing those choices can change the resulting clusters.
Suppose a dataset has several observations and a distance value for each relevant pair of observations. A clustering model uses those distances to decide which observations or existing groups are close enough to be merged according to its algorithm. The output is a set of clusters rather than a reduced-dimensional representation established by the supplied material.
The Two Linkage Decisions
Linkage-based clustering begins with distances between individual points, but later it must compare clusters containing multiple points. Two decisions specify the algorithm. First, it must define the distance between clusters. Second, it must specify when to stop merging. Different choices for either decision can lead to different clusterings.
Separating the Algorithm's Decisions
A linkage-based method has several current clusters. What must be decided before its behavior is fully specified?
Define cluster distance: The method needs a rule for turning the distances between individual points into a distance between two clusters.
Choose a stopping rule: The method needs a rule for deciding when the repeated merging process ends.
Recognize possible variation: Changing either decision can produce a different clustering.
A linkage-based algorithm is not fully described by the word clustering alone; its cluster-distance rule and stopping decision matter.
The Closest-Pair Rule
Single Linkage defines the distance between two clusters as the minimum distance between any two members of those clusters. In plain language, compare every relevant cross-cluster pair and use the distance of the closest pair as the cluster-to-cluster distance.
Finding One Single Linkage Distance
Cluster A contains points A1 and A2. Cluster B contains points B1 and B2. The cross-cluster distances are A1-B1: 8, A1-B2: 3, A2-B1: 6, and A2-B2: 5. What is the Single Linkage distance between the clusters?
List the cross-cluster distances: The relevant values are 8, 3, 6, and 5. They compare a member of Cluster A with a member of Cluster B.
Select the minimum: The smallest cross-cluster distance is 3, belonging to the pair A1 and B2.
Assign the cluster distance: Single Linkage uses that smallest pairwise distance as the distance between Cluster A and Cluster B.
The Single Linkage distance between Cluster A and Cluster B is 3.
Repeated Merging
Linkage-based clustering repeatedly merges the closest clusters. After one merge, the number of clusters is reduced. The algorithm then evaluates the current clusters again, using its linkage rule to determine which pair is closest for the next merge. This process continues until the chosen stopping condition is reached.
What do you think happens?
If the closest pair of current clusters is merged, what happens to the number of clusters before the next comparison?
Reveal answer
Answer: It decreases.
Linkage-based clustering merges two current clusters into one, reducing the number of clusters each round.
Tracing Three Merge Rounds
Consider four current clusters named A, B, C, and D. Assume the closest pair at the first round is A and B, and that after this merge the closest current pair is AB and C. Trace the process.
First round: The algorithm identifies A and B as the closest current clusters and merges them. The current set becomes AB, C, and D.
Second round: The algorithm compares the current clusters again. By assumption, AB and C are now the closest pair, so they merge into ABC.
Third round: The current set is ABC and D. The algorithm can compare these remaining clusters and apply its stopping decision.
The process is iterative: merge the closest current clusters, reduce the number of clusters, then evaluate the new current state.
Mistakes About Single Linkage
Treating Single Linkage as the distance between cluster centers or representatives.
Single Linkage uses the minimum distance between any two members of the two clusters.
Fix:
Inspect the cross-cluster point distances and select the smallest one.Assuming that clustering and PCA are interchangeable.
The supplied material establishes clustering as an unsupervised grouping task but does not define PCA or dimensionality reduction.
Fix:
Describe the clustering output as groups, and do not attribute unsupported PCA behavior to it.Describing only the first merge.
Linkage-based clustering repeatedly merges the closest current clusters, and the current set changes after every merge.
Fix:
After each merge, describe the new cluster set and the next comparison.Ignoring the stopping decision.
A linkage-based algorithm also needs a rule for when to stop merging.
Fix:
State both the cluster-distance rule and the stopping decision.
Apply the Rule
Cluster X contains X1 and X2. Cluster Y contains Y1 and Y2. Their cross-cluster distances are X1-Y1: 9, X1-Y2: 4, X2-Y1: 7, and X2-Y2: 6. Identify the Single Linkage distance between Cluster X and Cluster Y, name the point pair that determines it, and explain why the other three distances do not determine the cluster distance.
Hints
- List all four distances between a member of Cluster X and a member of Cluster Y.
- Single Linkage selects the minimum cross-cluster distance.
- The determining pair is the pair associated with that minimum.
A linkage-based process currently has clusters A, B, C, and D. It merges A and C because they are the closest current pair. Describe the next state and explain what the algorithm must do before choosing another merge.
Hints
- Replace A and C with one combined cluster.
- The number of current clusters decreases.
- The algorithm must compare the new current clusters using its linkage rule.
Key Takeaways
- Clustering is an unsupervised grouping task whose result depends on similarity and distance choices.
- A clustering model uses observations and point-distance information to produce groups.
- Linkage-based clustering repeatedly merges the closest current clusters, reducing the number of clusters after each merge.
- Single Linkage defines the distance between two clusters as the minimum distance between any two of their members.
- The supplied material does not define PCA, variance maximization, principal components, or dimensionality reduction.
Key Takeaways
- Single Linkage is a clustering method, not a definition of PCA or dimensionality reduction.
- Clustering uses similarity or distance choices to organize observations into groups.
- Linkage-based clustering repeatedly merges the closest current clusters.
- Single Linkage measures two clusters by the closest pair of members across them.
- A complete linkage-based algorithm also needs a stopping decision.