Chapitre 11 — Clustering hiérarchique

🎯 Objectifs d'apprentissage

Distinguer clustering agglomératif et divisif.
Définir les quatre fonctions de lien : simple, complet, moyen, centroïdal.
Construire et lire un dendrogramme.
Calculer les distances de linkage sur un petit exemple.
Connaître les avantages et limites du clustering hiérarchique.

11.1 — Le problème à résoudre

Le clustering hiérarchique forme des clusters séparés par récurrence. Il s'agit de partitionner les données pour toutes les échelles possibles de taille de partition, dans une hiérarchie à plusieurs niveaux. main_5.pdf, p. 14

💡 Intuition

Au départ, chaque personne est son propre groupe. Les deux personnes les plus proches se donnent la main. Puis les groupes proches se fusionnent progressivement jusqu'à former un grand groupe unique. L'historique des fusions forme un arbre généalogique appelé dendrogramme.

11.2 — Agglomératif vs divisif

Type	Principe
*Agglomératif (ascendant, bottom-up)*	Chaque observation forme un cluster de taille 1. À chaque itération, on fusionne les deux clusters les plus proches. Arrêt quand il ne reste qu'un seul cluster.
*Divisif (descendant, top-down)*	On part d'un seul cluster contenant toutes les observations. À chaque itération, on sépare un cluster en deux. Arrêt quand chaque cluster ne contient plus qu'une seule observation.

main_5.pdf, p. 17

11.3 — Le dendrogramme

📘 Définition à connaître

Un dendrogramme est un arbre dont les $n$ feuilles correspondent chacune à une observation. Chaque nœud de l'arbre correspond à un cluster :

La racine est un cluster contenant toutes les observations.
Chaque feuille est un cluster contenant une observation.
Les clusters ayant le même parent sont agglomérés en un seul cluster au niveau au-dessus.
Un cluster est subdivisé en ses enfants au niveau au-dessous.

La longueur d'une branche de l'arbre est proportionnelle à la distance entre les deux clusters qu'elle connecte. C'est ce qui permet de lire visuellement le résultat.

main_5.pdf, p. 15

Pour obtenir une partition à $K$ clusters, on coupe le dendrogramme horizontalement à la hauteur souhaitée. Les branches coupées forment les clusters.

11.4 — Algorithme agglomératif

📘 Algorithme

Initialisation :

Chaque observation est placée dans son propre cluster.
Calcul d'une matrice $M$ de similarité entre clusters.

Répéter :

Sélectionner dans $M$ les deux clusters les plus semblables $C i$ et $C j$ .
Fusionner pour former un cluster $C k$ .
Mettre à jour $M$ pour calculer la similarité entre $C k$ et les autres clusters.

Arrêt : un seul cluster.

main_5.pdf, p. 18

11.5 — Les fonctions de lien (linkage)

Déterminer les deux clusters les plus proches nécessite de définir une distance entre clusters. C'est ce qu'on appelle une fonction de lien (linkage).

Fonction de lien	Formule	Intuition
Lien simple (single)	$d simple (C k, C l) = min d(u, v)$	Distance minimale entre un élément de $C k$ et un élément de $C l$
Lien complet (complete)	$d complet (C k, C l) = max d(u, v)$	Distance maximale entre un élément de $C k$ et un élément de $C l$
Lien moyen (average, UPGMA)	$d moyen (C k, C l) = (1 / \|C k \|\|C l \|) \sum \sum d(u, v)$	Distance moyenne entre tous les couples
Lien centroïdal (centroid, UPGMC)	$d centroïdal (C k, C l) = d(μ k, μ l)$	Distance entre les centroïdes des clusters

main_5.pdf, p. 19–21

⚠️ Attention — piège classique

Ne confondez pas lien moyen et lien centroïdal :

Lien moyen : moyenne de toutes les distances par paires.
Lien centroïdal : une seule distance, calculée entre les deux centroïdes.

11.6 — Exemple guidé — Linkage

✏️ Exemple guidé

Soient $C 1 = {p 1 = (0, 0) T, p 2 = (1, 0) T}$ et $C 2 = {p 3 = (0, 3) T}$ .

Distances individuelles :

$d(p 1, p 3) = \sqrt((0-0)² + (0-3)²) = \sqrt9 = 3,000$
$d(p 2, p 3) = \sqrt((1-0)² + (0-3)²) = \sqrt(1 + 9) = \sqrt10 \approx 3,162$

1. Lien simple : $min(3,000 ; 3,162) = 3,000$

2. Lien complet : $max(3,000 ; 3,162) = 3,162$

3. Lien moyen : $(3,000 + 3,162) / 2 = 3,081$

Interprétation : le choix de la fonction de lien modifie la géométrie des regroupements. Le lien simple favorise les chaînages (clusters allongés), le lien complet favorise les groupes sphériques compacts.

11.7 — Application : single linkage pas à pas

Extrait de l'exemple du cours (main_5.pdf, p. 22–27) avec 6 points dans le plan :

Point	x	y
p₁	0,40	0,53
p₂	0,22	0,38
p₃	0,35	0,32
p₄	0,26	0,19
p₅	0,08	0,41
p₆	0,45	0,30

Étapes successives (single linkage) :

Distance minimale globale : $d(p 3, p 6) = 0,10$ → Cluster ${p 3, p 6}$ .
Distance minimale mise à jour : $0,14$ → Cluster ${p 2, p 5}$ .
Distance minimale : $0,14$ → Cluster ${p 2, p 5, p 3, p 6}$ .
Distance minimale : $0,16$ → ajout de $p 4$ .
Distance minimale : $0,22$ → ajout de $p 1$ . Arrêt.

En coupant le dendrogramme à hauteur 0,15, on obtient 3 clusters : ${p 3, p 6}$ , ${p 2, p 5}$ , ${p 1}$ et ${p 4}$ — soit selon la coupe, 2 à 4 clusters.

11.8 — Algorithme divisif et MST

📘 Algorithme divisif (descendant)

Initialisation : placer toutes les observations dans un seul cluster (la racine).

Répéter :

Sélectionner dans le cluster $C k$ les deux sous-clusters les plus éloignés.
Diviser $C k$ en deux clusters $C i$ et $C j$ .

Méthode de partitionnement : on peut utiliser K-Means, ou l'Arbre Couvrant Minimum (Minimal Spanning Tree, MST).

Avec MST : on coupe progressivement l'arête de longueur maximale dans l'arbre couvrant minimum.

main_5.pdf, p. 29–31

11.9 — Avantages et limites

Avantages	Inconvénients
Facile à implémenter Fournit une structure (préférable pour une analyse détaillée qu'une méthode de partitionnement) Flexibilité : nombre de clusters non fixé à l'avance, choisi après le dendrogramme Permet d'évaluer plusieurs possibilités en utilisant des mesures d'homogénéité et de séparation	Passage à l'échelle difficile : complexité en $θ(n²)$ Plus adapté aux jeux de données contenant peu d'échantillons Sensible aux anomalies (outliers) Pas de remise en cause des classes fusionnées

main_5.pdf, p. 32

11.10 — Évaluation d'un clustering

En l'absence d'étiquettes, la qualité d'un clustering est difficile à évaluer : les « bons clusters » ne sont pas connus. Les critères d'évaluation incluent :

Des indices reposant sur des rapports de distances intra / extra clusters : séparabilité et homogénéité.
Le jugement d'un expert ou l'évaluation par un utilisateur.
L'utilisation de données étiquetées si elles existent.
La comparaison avec une segmentation de référence.

main_5.pdf, p. 33

📌 À retenir

Deux familles : agglomératif (bottom-up) et divisif (top-down).
Dendrogramme : arbre généalogique des fusions ; on coupe pour obtenir $K$ clusters.
Quatre fonctions de lien : simple (min), complet (max), moyen (moyenne), centroïdal (centres).
Complexité en $θ(n²)$ → peu adapté aux gros volumes.
Contrairement à K-Means, $K$ n'est pas fixé à l'avance.

🎯 À l'examen

Définissez mathématiquement le lien simple et le lien complet.
Comment obtient-on une partition à $K$ clusters à partir d'un dendrogramme ?
Pourquoi le clustering hiérarchique est-il difficilement applicable aux très grands jeux de données ?
Quelle est la différence entre lien moyen et lien centroïdal ?