Clustering Hierarchique

Debutant 35 min 13 sections

Decouvrez le clustering hierarchique et les dendrogrammes pour comprendre la structure de vos donnees a differents niveaux.

Telecharger CSV Telecharger Script Python

Objectifs d'apprentissage

Comprendre la difference entre approches agglomerative et divisive
Interpreter un dendrogramme
Choisir le nombre de clusters avec le dendrogramme
Implementer le clustering hierarchique avec scikit-learn

Prerequis

Module K-Means Clustering recommande

Theorie

Qu'est-ce que le clustering hierarchique?

Le clustering hierarchique cree une hierarchie de clusters, representee par un arbre appele dendrogramme.

Deux approches:

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

L'approche agglomerative est la plus courante.

Algorithme agglomeratif:

Chaque point = 1 cluster
Trouver les 2 clusters les plus proches
Les fusionner en 1 cluster
Repeter jusqu'a n'avoir qu'un seul cluster

Avantages:

Pas besoin de specifier k a l'avance
Dendrogramme visualise la structure a tous les niveaux
Pas d'initialisation aleatoire (deterministe)

Inconvenients:

Complexite O(n^3) en memoire et temps
Pas adapte aux tres grands datasets (>10K points)
Une fusion ne peut pas etre defaite

Theorie

Schema: Construction du dendrogramme

Algorithme agglomeratif etape par etape:

flowchart TD subgraph E1 ["Etape 1"] A1["A"] B1["B"] C1["C"] D1["D"] E1T["E"] end subgraph E2 ["Etape 2: Fusion A+B"] AB["A-B"] C2["C"] D2["D"] E2T["E"] end subgraph E3 ["Etape 3: Fusion D+E"] AB2["A-B"] C3["C"] DE["D-E"] end subgraph E4 ["Etape 4: Fusion AB+C"] ABC["A-B-C"] DE2["D-E"] end subgraph E5 ["Etape 5: Fusion finale"] ALL["A-B-C-D-E"] end E1 --> E2 --> E3 --> E4 --> E5 style ALL fill:#F7E64D,color:#1A1A1A

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 style ROOT fill:#9B7AC4,color:#FFFFFF

Couper le dendrogramme a une certaine hauteur donne un nombre specifique 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})$

Etape 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}}$

Etape 2 - Fusionner les plus proches:

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

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

Legende des couleurs:

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

Avance Exercice manuel: A vous de calculer!

Objectif: Construire un dendrogramme a la main (clustering hierarchique agglomeratif).

CONTEXTE

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

Methode : Agglomerative (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 : Premiere 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'a n'avoir qu'un seul cluster

3.3) A quelle hauteur coupe-t-on pour avoir 2 clusters ?

Avance Solution de l'exercice manuel

SOLUTION DETAILLEE

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 : Premiere 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}

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

Code

Explorer les donnees

Cliquez sur "Executer" pour voir le resultat