Module 4 — Partitionnement hiérarchique et dendrogrammes

Les k-moyennes imposaient de choisir $k$ avant de voir quoi que ce soit. Le partitionnement hiérarchique renverse l'ordre : il construit d'abord toute l'arborescence des regroupements possibles, et vous décidez ensuite où la couper. On voit la structure avant de trancher — un avantage considérable en exploration.

Le principe agglomératif : fusionner de proche en proche

L'approche dominante part du plus fin et remonte :

1. chaque observation constitue son propre groupe ;
2. on fusionne les deux groupes les plus proches ;
3. on répète jusqu'à n'avoir plus qu'un seul groupe contenant tout.

L'histoire complète de ces fusions — qui a rejoint qui, et à quelle distance — forme une arborescence : le dendrogramme. Rien n'est décidé pendant la construction ; toutes les granularités coexistent dans l'arbre.

Le critère de liaison : la décision qui change tout

« Les deux groupes les plus proches » suppose de définir la distance entre deux groupes, et non entre deux points. Ce choix, le critère de liaison, détermine la forme des groupes obtenus bien plus que le reste.

Critère	Distance entre groupes	Tendance
liaison simple	entre leurs deux points les plus proches	suit les formes allongées, mais provoque des enchaînements
liaison complète	entre leurs deux points les plus éloignés	groupes compacts, sensible aux aberrants
liaison moyenne	moyenne de toutes les paires	compromis équilibré
Ward	augmentation d'inertie induite par la fusion	groupes homogènes de taille comparable

Ward est le choix par défaut raisonnable : en minimisant l'augmentation d'inertie à chaque fusion, il poursuit le même objectif de compacité que les k-moyennes, avec des résultats souvent proches mais accompagnés de l'arborescence complète. La liaison simple est la plus atypique : capable de suivre des formes étirées, elle souffre de l'effet de chaînage, où deux groupes distincts se retrouvent reliés par un mince pont de points intermédiaires.

from scipy.cluster.hierarchy import linkage, dendrogram, fcluster

Z = linkage(X_s, method="ward")
dendrogram(Z, truncate_mode="lastp", p=30)   # arbre lisible sur gros volumes
groupes = fcluster(Z, t=4, criterion="maxclust")   # coupe en 4 groupes

Lire un dendrogramme et choisir la coupe

Sur le dendrogramme, chaque fusion est une barre horizontale dont la hauteur indique la distance à laquelle elle s'est produite. C'est là qu'est l'information : une fusion très haute signifie qu'on a réuni deux groupes qui étaient loin l'un de l'autre — donc, vraisemblablement, deux structures réellement distinctes.

D'où la règle de lecture : on coupe l'arbre juste sous un grand saut vertical. Les branches ainsi séparées correspondent à des groupes bien distincts, et le nombre de branches coupées donne $k$. Cette lecture visuelle est le pendant de la méthode du coude du module 3, avec un atout : on voit simultanément toutes les granularités possibles, et l'imbrication des groupes (segments et sous-segments) se lit directement.

Forces, coût, et complémentarité avec les k-moyennes

L'atout principal est donc l'exploration : pas de $k$ imposé, une visualisation riche, et la hiérarchie des sous-groupes en prime. S'y ajoute la souplesse : le hiérarchique accepte n'importe quelle matrice de distances, y compris non euclidienne — utile pour des données textuelles ou des séquences, là où les k-moyennes exigent une moyenne calculable.

Le prix à payer est le coût de calcul, quadratique en mémoire comme en temps : au-delà de quelques dizaines de milliers d'observations, la matrice de distances devient impraticable. Autre différence de fond : une fusion est définitive, jamais remise en question, là où les k-moyennes réaffectent les points à chaque itération.

Le duo qui fonctionne en pratique

Sur un gros jeu de données, la démarche efficace combine les deux : un partitionnement hiérarchique sur un échantillon de quelques milliers de points pour lire la structure et estimer $k$ dans le dendrogramme, puis des k-moyennes avec ce $k$ sur la totalité des données. On récupère la lisibilité de l'un et la capacité de traitement de l'autre.

En résumé

• L'approche agglomérative fusionne les groupes les plus proches de proche en proche et produit une arborescence complète : le dendrogramme.
• Le critère de liaison décide de la forme des groupes ; Ward est le défaut raisonnable, la liaison simple suit les formes allongées mais chaîne.
• On choisit $k$ en coupant sous un grand saut vertical du dendrogramme ; toutes les granularités et l'imbrication se lisent d'un coup d'œil.
• Excellent en exploration et compatible avec toute matrice de distances, mais coût quadratique et fusions irréversibles.

Module suivant : DBSCAN, qui abandonne la notion de centre pour détecter des groupes de forme quelconque et isoler le bruit.