Clustering hiérarchique

Débutant 35 min 13 sections

Les points fusionnent deux à deux jusqu'au dernier ; la hauteur de coupe fixe le nombre de groupes.

Télécharger le CSV Télécharger le script Python

Objectifs d'apprentissage

Comprendre la différence entre approches agglomérative et divisive
Interpréter un dendrogramme
Choisir le nombre de clusters avec le dendrogramme
Implémenter le clustering hiérarchique avec scikit-learn

Prérequis

Module K-Means Clustering recommandé

Théorie

Qu'est-ce que le clustering hiérarchique?

Le clustering hiérarchique créé une hiérarchie de clusters, représentée par un arbre appelé dendrogramme.

Deux approches:

Agglomérative (bottom-up): Chaque point est un cluster, on fusionne iterativement
Divisive (top-down): Tous les points forment un cluster, on divise iterativement

L'approche agglomérative est la plus courante.

Algorithme agglomératif:

Chaque point = 1 cluster
Trouver les 2 clusters les plus proches
Les fusionner en 1 cluster
Répéter jusqu'à n'avoir qu'un seul cluster

Avantages:

Pas besoin de spécifier k à l'avance
Dendrogramme visualise la structure à tous les niveaux
Pas d'initialisation aléatoire (déterministe)

Inconvénients:

Complexité O(n^3) en mémoire et temps
Pas adapte aux très grands datasets (>10K points)
Une fusion ne peut pas être défaite

Théorie

Schéma: Construction du dendrogramme

Algorithme agglomératif étape par étape:

flowchart TD subgraph E1 ["Étape 1"] A1["A"] B1["B"] C1["C"] D1["D"] E1T["E"] end subgraph E2 ["Étape 2: Fusion A+B"] AB["A-B"] C2["C"] D2["D"] E2T["E"] end subgraph E3 ["Étape 3: Fusion D+E"] AB2["A-B"] C3["C"] DE["D-E"] end subgraph E4 ["Étape 4: Fusion AB+C"] ABC["A-B-C"] DE2["D-E"] end subgraph E5 ["Étape 5: Fusion finale"] ALL["A-B-C-D-E"] end E1 --> E2 --> E3 --> E4 --> E5 class ALL ml-node-accent

Le dendrogramme:

flowchart TD ROOT["Racine
(tous les points)"] L["Cluster Gauche"] R["Cluster Droit"] LL["A"] LR["B"] RL["C"] RR["D"] ROOT --> L ROOT --> R L --> LL L --> LR R --> RL R --> RR class ROOT ml-node-main

Couper le dendrogramme à une certaine hauteur donne un nombre spécifique de clusters.

Exemple concret avec code couleur - Fusion de clusters:

Clusters actuels:

$\textcolor{#3498db}{Cluster\ A}$: points {$\textcolor{#3498db}{P_1, P_2}$} avec centre $(\textcolor{#3498db}{1.0}, \textcolor{#3498db}{2.0})$
$\textcolor{#e67e22}{Cluster\ B}$: points {$\textcolor{#e67e22}{P_3}$} avec centre $(\textcolor{#e67e22}{1.5}, \textcolor{#e67e22}{2.5})$
$\textcolor{#9B7AC4}{Cluster\ C}$: points {$\textcolor{#9B7AC4}{P_4, P_5}$} avec centre $(\textcolor{#9B7AC4}{8.0}, \textcolor{#9B7AC4}{7.0})$

Étape 1 - Calculer les distances entre clusters (linkage: average):

$d(\textcolor{#3498db}{A}, \textcolor{#e67e22}{B}) = \sqrt{(\textcolor{#3498db}{1.0} - \textcolor{#e67e22}{1.5})^2 + (\textcolor{#3498db}{2.0} - \textcolor{#e67e22}{2.5})^2} = \textcolor{#27ae60}{\mathbf{0.71}}$

$d(\textcolor{#3498db}{A}, \textcolor{#9B7AC4}{C}) = \sqrt{(\textcolor{#3498db}{1.0} - \textcolor{#9B7AC4}{8.0})^2 + (\textcolor{#3498db}{2.0} - \textcolor{#9B7AC4}{7.0})^2} = \textcolor{#e74c3c}{\mathbf{8.60}}$

$d(\textcolor{#e67e22}{B}, \textcolor{#9B7AC4}{C}) = \sqrt{(\textcolor{#e67e22}{1.5} - \textcolor{#9B7AC4}{8.0})^2 + (\textcolor{#e67e22}{2.5} - \textcolor{#9B7AC4}{7.0})^2} = \textcolor{#e74c3c}{\mathbf{7.91}}$

Étape 2 - Fusionner les plus proches:

Distance minimale: $d(\textcolor{#3498db}{A}, \textcolor{#e67e22}{B}) = \textcolor{#27ae60}{0.71}$

Résultat: Fusionner $\textcolor{#3498db}{A}$ et $\textcolor{#e67e22}{B}$ → Nouveau $\textcolor{#27ae60}{\mathbf{Cluster\ AB}}$

Légende des couleurs:

$\textcolor{#3498db}{Bleu}$: Cluster A et ses coordonnées
$\textcolor{#e67e22}{Orange}$: Cluster B et ses coordonnées
$\textcolor{#9B7AC4}{Violet}$: Cluster C (éloigné)
$\textcolor{#27ae60}{Vert}$: Distance minimale / clusters fusionnes
$\textcolor{#e74c3c}{Rouge}$: Distances trop grandes

Avancé Exercice manuel: À vous de calculer!

Objectif: Construire un dendrogramme à la main (clustering hiérarchique agglomératif).

CONTEXTE

4 points en 1D : A=1, B=2, C=6, D=7

Méthode : Agglomérative (bottom-up) avec linkage single (distance min entre clusters)

PARTIE 1 : Matrice des distances initiale

1.1) Calculez la distance entre chaque paire de points 1.2) Quels sont les 2 points les plus proches ?

PARTIE 2 : Première fusion

2.1) Fusionnez les 2 points les plus proches en un cluster 2.2) Calculez les distances du nouveau cluster aux autres points

PARTIE 3 : Suite des fusions

3.1) Quelle est la prochaine fusion ? 3.2) Continuez jusqu'à n'avoir qu'un seul cluster 3.3) À quelle hauteur coupe-t-on pour avoir 2 clusters ?

Avancé Solution de l'exercice manuel

SOLUTION DÉTAILLÉE

PARTIE 1 : Matrice des distances initiale

1.1) Distances :

	A	B	C	D
A	0	1	5	6
B	1	0	4	5
C	5	4	0	1
D	6	5	1	0

1.2) Plus proches : $\textcolor{#3498db}{(A,B)}$ et $\textcolor{#e67e22}{(C,D)}$ avec distance = 1

PARTIE 2 : Première fusion

2.1) Fusion : {A,B} → hauteur = $\textcolor{#F7E64D}{1}$

2.2) Distances (single linkage = min) :

d({A,B}, C) = min(d(A,C), d(B,C)) = min(5,4) = 4
d({A,B}, D) = min(d(A,D), d(B,D)) = min(6,5) = 5

	{A,B}	C	D
{A,B}	0	4	5
C	4	0	1
D	5	1	0

PARTIE 3 : Suite des fusions

3.1) Prochaine fusion : {C,D} (distance = 1) → hauteur = $\textcolor{#F7E64D}{1}$

3.2) Distances :

	{A,B}	{C,D}
{A,B}	0	4
{C,D}	4	0

Fusion finale : {{A,B}, {C,D}} → hauteur = $\textcolor{#e74c3c}{4}$

Dendrogramme :

Hauteur
   4  ─────────┬─────────
               │
   1  ───┬───  │  ───┬───
         │     │     │
   0     A  B  │  C  D

3.3) Pour 2 clusters :

$\boxed{\text{Couper entre hauteur 1 et 4}}$

→ Clusters : {A,B} et {C,D}

Légende : $\textcolor{#3498db}{Bleu}$: cluster 1, $\textcolor{#e67e22}{Orange}$: cluster 2, $\textcolor{#F7E64D}{Jaune}$: fusions

Code

Explorer les données

Ctrl+Entrée

Cliquez sur "Exécuter" pour voir le résultat