Linkage

Linkage is the method for calculating inter-cluster distance.

Linkage types

The "closeness" of two clusters can be defined in different ways:

single: the distance between the two closest members; forms long chains.
complete: between the two farthest members; tight clusters of similar diameter.
average: the mean over all member pairs; in between.
ward: the merge that increases within-cluster variance least; round clusters similar to KMeans (default).

The chaining effect

The strength of single linkage is also its weakness: even a single chain of noise points linking two clusters merges them. Ward is more robust to noise but can't split curved shapes:

for l in ["single", "complete", "average", "ward"]:
    e = AgglomerativeClustering(n_clusters=2, linkage=l).fit_predict(Xm)
    print(l, adjusted_rand_score(ym, e))

The right linkage is chosen according to the expected shape of the clusters in the data.

Exercise Compare linkages

Run AgglomerativeClustering(n_clusters=2, linkage=l) on the moon data with the four linkage types. On each line print the linkage name and the ARI with round(..., 3).

Show example solution

from sklearn.datasets import make_moons
from sklearn.cluster import AgglomerativeClustering
from sklearn.metrics import adjusted_rand_score

X, y = make_moons(n_samples=200, noise=0.05, random_state=0)

for l in ["single", "complete", "average", "ward"]:
    e = AgglomerativeClustering(n_clusters=2, linkage=l).fit_predict(X)
    print(l, round(adjusted_rand_score(y, e), 3))

Test yourself

Which linkage gives the best result for two moon-shaped clusters?
- All the same
- single
- ward
- complete
Show answer

single — single merges along a chain of neighbouring points and follows the curved shape.

Merge by the farthest members.

ag = AgglomerativeClustering(n_clusters=3, linkage=____)

Show answer

ag = AgglomerativeClustering(n_clusters=3, linkage="complete")

Match the linkages.

single

Closest members, chains
complete

Farthest members
average

Mean over all pairs
ward

Least variance increase

Next lesson: Advantages

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies