Intelligence Artificielle - CAH

Classification par apprentissage non-supervisé

= "Clustering"

Exemple : regrouper ces 7 points en 3 clusters

Classification par apprentissage non-supervisé

• Les objets sont représéntés par $d$ caractéristiques

• On dispose d'une fonction de distance entre objets $dist$

• On dispose de $n$ objets que l'on souhaite regrouper en $K$ classes (= $K$ clusters)

Algorithme CAH

Classification Ascendante Hiérarchique

• initialement, 1 objet = 1 cluster

• on fusionne les clusters les plus proches jusqu'à ce qu'il n'y ait plus que $K$ clusters

NB : il faut donc définir une distance entre clusters (= distance interclusters)

NB CAH : il y a 2 distances : la distance inter-objets ET la distance interclusters

Distance entre clusters : plusieurs possibilités

Distance entre clusters : plusieurs possibilités

le "lien minimum" : distance des points les plus proches

$dist(Cl_1, Cl_2) = min_{x\in Cl_1, y \in Cl_2}(dist(x,y))$

Distance entre clusters : plusieurs possibilités

le "lien maximum" : distance des points les plus lointains

$dist(Cl_1, Cl_2) =max_{x\in Cl_1, y \in Cl_2}(dist(x,y))$

Distance entre clusters : plusieurs possibilités

le "lien moyen" : moyenne des distances

$dist(Cl_1, Cl_2) = \dfrac{1}{n_1\times n_2}\displaystyle\sum_{x\in Cl_1, y \in Cl_2}(dist(x,y))$

Distance entre clusters : plusieurs possibilités

distance entre les isobarycentres

$dist(Cl_1, Cl_2) = dist(g_1, g_2)$

où $g_i = \displaystyle \dfrac{1}{n_i}\sum_{x\in Cl_i}x$

Distance entre clusters : plusieurs possibilités

(HP) distance de Ward (pondération $\times$ distance entre les isobarycentres)

$dist(Cl_1, Cl_2) =\dfrac{n_1\times n_2}{n_1 + n_2}dist(g_1, g_2)$

(HP) distance de Ward : effet du facteur $\dfrac{n_1\times n_2}{n_1 + n_2}$

facteur multiplicatif de la distance entre les barycentres

• si $n_1 = n_2$ : $\dfrac{n_1\times n_2}{n_1 + n_2} = n_1 / 2$ : deux clusters de même taille sont d'autant plus proches qu'ils sont petits

• si $n_1 >> n_2$ : $\dfrac{n_1\times n_2}{n_1 + n_2} \simeq n_2$ : plus un cluster est petit, plus il se fait facilement absorber par un gros cluster

Exemple : regrouper en 3 clusters

Avec la distance inter-clusters du lien minimum $dist(Cl_1, Cl_2) = min_{x\in Cl_1, y \in Cl_2}(dist(x,y))$

Les points blancs représentent des classes différentes

quels sont les deux clusters les plus proches ?

Avec la distance inter-clusters : $dist(Cl_1, Cl_2) = min_{x\in Cl_1, y \in Cl_2}(dist(x,y))$

NB : il n'y a qu'un point par cluster : $dist(\{x\},\{y\}) = dist(x,y)$

quels sont les deux clusters les plus proches ?

quels sont les deux clusters les plus proches ?

quels sont les deux clusters les plus proches ?

Il ne reste que 3 clusters : fin de l'algorithme CAH

Effet du choix de la distance inter-cluster

Selon la distance choisie, on ne fusionne pas forcément les mêmes clusters !

Quels sont les clusters à fusionner ?

avec $dist(Cl_1, Cl_2) = min_{x\in Cl_1, y \in Cl_2}(dist(x,y))$

avec $dist(Cl_1, Cl_2) = min_{x\in Cl_1, y \in Cl_2}(dist(x,y))$

on fusionne Vert et Jaune

Quels sont les clusters à fusionner ?

avec $dist(Cl_1, Cl_2) = max_{x\in Cl_1, y \in Cl_2}(dist(x,y))$

avec $dist(Cl_1, Cl_2) = max_{x\in Cl_1, y \in Cl_2}(dist(x,y))$

on fusionne Vert et Orange

"Dendrogramme"

Lorsqu'on regroupe les objets jusqu'à ce qu'il n'y ait plus qu'une classe, on peut gardrer la trace des relations hiérarchiques : on obtient en dendrogramme

On a commencé par fusionner B et E, puis {B,E} avec C ...

NB : un dendrogramme est un arbre binaire.

• ses feuilles sont les objets à classer

• ses noeuds internes représentent les fusions de clusters

Dendrogramme $\rightarrow$ clusters

A partir du dendrogramme, on peut retrouver les clusters obtenus pour les différentes valeurs de $K$

2 clusters : {A,F} et {B,C,D,E}

4 clusters : {A}, {F}, {D} et {B,C,E}

Exercice : arbre phylogénétique