Single linkage
Topic of Hierarchical clustering and kernel density estimation, part of Statistical learning · Also in Hierarchical clustering and kernel density estimation
Single linkage
| Type | Topic |
| Taught in | Hierarchical clustering and kernel density estimation · Hierarchical clustering and kernel density estimation |
| Part | Statistical learning |
| Questions using it | 2 |
In hierarchical clustering, the dissimilarity between two clusters is the smallest dissimilarity between a member of one and a member of the other. It follows long, thin clusters and is prone to chaining, where a string of close points joins two distant groups.
In Hierarchical clustering and kernel density estimation
Read each linkage as a different question. Single linkage asks whether any cross-pair is close, so a chain of nearby points can connect distant ends. Complete linkage asks whether every cross-pair is close, discouraging large diameters. Average linkage asks about the typical cross-pair. These criteria suggest tendencies. Spherical clusters and equal cluster sizes are further claims.
The partition can change substantially when a new sample is drawn from the same distribution, or when n changes. Single linkage shows this as chaining. A gap that separates two groups at one sample size can contain points when n is larger, and the linkage then joins the groups at the height of the closest new pair across the gap. Complete linkage is sensitive to distant outliers: one far point raises the maximum pairwise distance and can block a merge of clusters that are otherwise close. Average linkage lies between those two behaviours. No linkage is the most stable under every contamination pattern and every cluster shape. Single and complete linkage need only the pairwise dissimilarities. A linkage that uses means also needs an average of points, which may not exist for the dissimilarities of the previous section.
Example 1 (Chaining on six points) Question. Cluster the one-dimensional points 0,1,2.1,3.3,4.6,6.9 by single and complete linkage.
Solution. The gaps between neighbours are 1, 1.1, 1.2, 1.3, 2.3.
Single linkage merges \{0\} with \{1\} at 1.0. It then merges \{0,1\} with \{2.1\} at 1.1, because the nearest points across those sets are 1 and 2.1. It merges the result with \{3.3\} at 1.2, with \{4.6\} at 1.3, and finally with \{6.9\} at 2.3. The tree is a chain: each point is attached to the growing cluster through its nearest neighbour, and the merge heights are exactly the neighbour gaps 1.0,1.1,1.2,1.3,2.3.
Complete linkage makes the first merge \{0,1\} at 1.0 again. The next smallest distance is 1.2, between 2.1 and 3.3, so \{2.1,3.3\} forms at 1.2. Then \{4.6,6.9\} forms at 2.3. The union \{0,1\}\cup\{2.1,3.3\} has maximum cross distance 3.3-0=3.3. The two halves then merge at 6.9-0=6.9. Complete linkage finds three pairs and then joins those pairs. Single linkage finds a chain, with a possible split of 6.9 from the rest.
Average linkage, included for the comparison, has merge heights 1.0, 1.2, 1.9, 2.83, 4.7. The first two are the same pairs as complete linkage: \{0,1\} at distance 1.0, and \{2.1,3.3\} at distance 1.2. The distance from \{2.1,3.3\} to \{4.6\} is the mean of 4.6-2.1=2.5 and 4.6-3.3=1.3, which is 1.9, and that is the third merge. The six cross distances from \{0,1\} to \{2.1,3.3,4.6\} are 2.1,3.3,4.6,1.1,2.3,3.6, with mean 17/6=2.833, recorded as 2.83. The last merge attaches 6.9. Its distances to the five points already joined are 6.9,5.9,4.8,3.6,2.3, with mean 23.5/5=4.7.
In Hierarchical clustering and kernel density estimation, continued
The original vectors are not required. Edit distance between words, or between languages, counts insertions, deletions, and substitutions. The same counting compares genetic sequences. People can be clustered from the strength of a relationship, and sites from an ecological similarity, with no coordinates in sight. Single linkage and complete linkage, defined below, use only those pairwise numbers.
Used in
See also
Hierarchical clustering · Complete linkage · Single, complete, and average linkage · Kernel density estimator · Agglomerative and divisive clustering · Properties of the linkages · Divisive clustering · Kernel density estimation