Single, complete, and average linkage
Definition taught in Hierarchical clustering and kernel density estimation, part of Statistical learning
Single, complete, and average linkage
| Type | Definition |
| Taught in | Hierarchical clustering and kernel density estimation |
| Part | Statistical learning |
| Questions using it | 1 |
Single linkage, or nearest neighbour, takes the distance between the closest pair with one point in each cluster,
d_S(D_1,D_2)=\min\{d(x,y):x\in D_1,\, y\in D_2\}.
The clusters are close as soon as they touch.
Complete linkage, or furthest neighbour, takes the distance between the farthest pair,
d_C(D_1,D_2)=\max\{d(x,y):x\in D_1,\, y\in D_2\}.
A merge is cheap only when every cross pair is close.
Average linkage, in the group-average sense, takes the mean of all cross pairs,
d_A(D_1,D_2)=\frac{1}{|D_1|\,|D_2|}\sum_{x\in D_1}\sum_{y\in D_2}d(x,y),
where |\cdot| is the cardinality of the multiset. Clusters are allowed to be multisets so that duplicate points are legal.
Used in
- Taught in Hierarchical clustering and kernel density estimation, where the derivation and examples are.
- Questions that use it (1) — Linkage by hand (answer)
- All 6 questions on Hierarchical clustering and kernel density estimation
See also
Single linkage · -nearest neighbours · Complete linkage · Average linkage · Dendrogram · Kernel density estimator · Hierarchical clustering · Agglomerative and divisive clustering