Lien simple, lien complet : deux dendrogrammes

Lien simple. $\{c,d\}$ à la hauteur $1$ ; $\{a,b\}$ à $2$ ; puis $\{a,b\}$ et $\{c,d\}$ fusionnent à $3$ (car $|5-2|=3$) ; enfin $e$ rejoint le tout à $3,5$ (car $|9,5-6|=3,5$).

Lien complet. $\{c,d\}$ à $1$ ; $\{a,b\}$ à $2$ ; puis $\{c,d\}$ et $e$ fusionnent à $4,5$ (car $\max (|9,5-5|,|9,5-6|)=4,5$, à comparer à $\max (|5-0|,\dots )=6$ entre $\{a,b\}$ et $\{c,d\}$) ; enfin tout se réunit à $9,5$.

Les deux arbres ne sont pas les mêmes : le lien simple groupe $\{a,b,c,d\}$ puis $e$ ; le lien complet groupe $\{c,d,e\}$ puis $\{a,b\}$.

Ce que la comparaison enseigne. Le lien n'est pas un détail de mise en œuvre : c'est un choix de modélisation, et il change le résultat. Le lien simple ne demande qu'un point proche pour fusionner : il suit les chaînes de points et produit des paquets allongés — c'est l'effet de chaînage, visible ici puisqu'il relie $a$ à $d$ par la seule chaîne $abcd$ alors que $|a-d|=6$. Le lien complet exige que tous les points soient proches : il produit des paquets compacts, et il isole $\{a,b\}$ jusqu'au bout.

Ce qui, en revanche, ne change pas : les deux méthodes sont déterministes. Relancées cent fois sur ces cinq points, elles rendent cent fois le même arbre — c'est la ligne du tableau du cours qui les sépare des $k$-moyennes.