Complete linkage
Topic of Hierarchical clustering and kernel density estimation, part of Statistical learning
Complete linkage
| Type | Topic |
| Taught in | Hierarchical clustering and kernel density estimation |
| Part | Statistical learning |
| Questions using it | 2 |
In hierarchical clustering, the dissimilarity between two clusters is the largest dissimilarity between a member of one and a member of the other. It favours compact clusters of similar diameter and resists chaining.
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.
Used in
- Taught in Hierarchical clustering and kernel density estimation
- Questions that use it (2) — Linkage by hand (answer) · Clustering and smoothing choices
- All 6 questions on Hierarchical clustering and kernel density estimation
See also
Hierarchical clustering · Single linkage · Average linkage · Single, complete, and average linkage · Kernel density estimator · Agglomerative and divisive clustering · Properties of the linkages · Divisive clustering