Intelligence Artificielle - Algorithme des K-moyennes

Classification par apprentissage non-supervisé

= "Clustering"

• Objectif : regrouper $n$ objets en $K$ classes (= $K$ clusters)

Exemple : $n=$ 10 objets de $\mathbb{R}^2$ à regrouper en $K = $ 3 classes

• distance = distance euclidienne

Algorithme des K-moyennes

en anglais K-means

• Idée : l'algorithme débute avec K clusters, qui évoluent jusqu'à convergence

NB : très différent de CAH

Algorithme des K-moyennes

Initialement, on choisit K centroïdes (Etape 0)

NB : chaque centroïde est un point pris au hasard parmi les objets à classer (ou non)

NB : chaque centroïde a vocation à représenter un cluster

On itère le procedé suivant, jusqu'à ce que les points ne changent plus de cluster :

• on rattache chaque objet au centroïde le plus proche, définissant ainsi K clusters (Etape 1)

• on recalcule le centroïde de chaque cluster comme le barycentre de l'ensemble ses points (Etape 2)

NB : chaque centroïde est un point pris au hasard parmi les objets à classer (ou non)

NB : (admis) le processus termine.

NB : le résultat n'est pas forcément "optimal"

Exemple

Ensemble d'objets de $\mathbb{R}^2$ à regrouper

• $K = 3$

• distance = distance euclidienne

Etape 0 : choix aléatoire des 3 centroïdes

Etape 1 : rattachement des points au centroïde le plus proche

Etape 2 : calcul des nouveaux centroïdes (barycentre)

Etape 1 : rattachement des points au centroïde le plus proche

Etape 2 : calcul des nouveaux centroïdes (barycentre)

Etape 1 : rattachement des points au centroïde le plus proche

Pas de changement : fin de l'algorithme

NB : avec un autre choix initial ?

Avec d'autres choix initiaux, ça ne se passe pas forcément aussi bien ...

On peut converger vers un minimum local (qui ne soit pas un minimum global)

Etape 0 : choix aléatoire des 3 centroïdes

Etape 1 : rattachement des points au centroïde le plus proche

Etape 2 : calcul des nouveaux centroïdes (barycentre)

Etape 1 : rattachement des points au centroïde le plus proche

Etape 2 : calcul des nouveaux centroïdes (barycentre)

Etape 1 : rattachement des points au centroïde le plus proche

Pas de changement : fin de l'algorithme

Problème de convergence vers un minimum local ?

En pratique, pour contourner le problème, on applique plusieurs fois l'algorithme, et on retient le "meilleur" résultat

Celui qui minimise la quantité : $\displaystyle\sum_{j=1}^K \sum_{x \in Cl_j} ||g_j-x|| $

• où $Cl_j$ est le cluster $j$ et $g_j$ son centroïde

NB : somme des distances entre les points et les centroïdes de leurs clusters de rattachement

Exercice : implémenter l'algorithme K-means

... rien de très compliqué, un peu fastidieux à implémenter ...

Exemple d'application

Pas beaucoup plus compliqué, pour une application plus concrète

Réduire le nombre de couleurs utilisées dans une image

par exemple pour compresser une image, ou à des fins artistiques

Transformer l'image suivante en image à 4 couleurs

Objets à regrouper ? K = ? Comment obtenir l'image finale ?

les objets sont les couleurs de chaque pixel de l'image (triplets RGB : valeurs dans $\lbrack| 0;255 |\rbrack^3$)

on regroupe ces triplets RGB en 4 classes

les 4 centroïdes finaux correspondent aux 4 couleurs de l'image finale

pour obtenir l'image finale, on remplace chaque pixel par la couleur du centroïde le plus proche

NB : inutile d'appliquer l'algorithme à tous les pixels de l'image. Le résultat reste satisfaisant en prenant un pixel sur 100

A implémenter en TP !