Méthode des k moyennes

Adrien Guille, Université Lyon 2

Partie théorique

Partie pratique

Formulation du modèle

Soit le jeu de données composé de individus, chacun décrit selon descripteurs, sous la forme d'un vecteur réel de taille :

Le but de la méthode des k-moyennes (Lloyd 1957, Forgy 1965) est de déterminer un partitionnement de ces individus en groupes homogènes, la valeur de étant choisie a priori :

Estimation des paramètres du modèle

Cette méthode repose sur l'intuition suivante : les observations appartenant à un groupe sont proches du centroïde correspondant. La proximité d'une observation par rapport à un centroïde est caractérisée par la distance euclidienne :

Formulation du problème

La méthode des k-moyennes vise à identifier un partitionnement des observations minimisant la fonction objectif ci-dessous :

Autrement dit, il s'agit de déterminer les centroïdes et les affectations minimisant la somme du carré des distances entre les individus dans et le centroïde de leur groupe d'appartenance.

Résolution du problème

Algorithme général

L'aglorithme classiquement utilisé pour résoudre ce problème d'optimisation est le suivant :

  1. Initialiser les centroïdes en choisissant aléatoirement ;

  2. Répéter les étapes suivantes, jusqu'à convergence, c'est-à-dire lorsque les affectations et les centroïdes sont stables :

    1. Trouver les affectations optimales (i.e. ), les centroïdes étant fixés (détails);
    2. Trouver les centroïdes optimaux (i.e. ) sachant les affectations (détails);
  3. Retourner les centroïdes et les affectations.

Étape 2.1 de l'algorithme

Les affectations optimales à l'étape 2.a) sont déterminée ainsi :

Étape 2.2 de l'algorithme

Afin d'identifier les centroïdes optimaux à l'étape 2.b), on calcule d'abord le gradient de la fonction objectif par rapport à un centroïde , que l'on note , puis on résout l'équation .

On doit donc déterminer le gradient de la fonction suivante, par rapport à un centroïde quelconque :

On élimine les éléments qui ne sont pas liés à , que l'on considère comme constants :

On développe le carré de la différence entre et :

Comme précédemment, on élimine de cette expression les éléments qui ne sont pas liés à :

Enfin, on obtient :

On détermine finalement les centroïdes optimaux en résolvant l'équation :

On constate que les centroïdes optimaux à l'étape 2.b) sont obtenus en mesurant la moyenne des observations pour chaque groupe, d'où le nom de la méthode !

Estimation des paramètres du modèle en pratique

Il convient de noter que la fonction objectif optimisée par la méthode des k-moyennes n'est pas convexe, ce qui signifie que l'algorithme converge en général vers un minimum local. Le minimum local vers lequel converge l'algorithme est lié à l'initialisation aléatoire des centroïdes (étape 1 de l'algorithme). C'est pourquoi, une pratique commune consiste à réaliser plusieurs partitionnements avec différentes initialisation et à conserver le meilleur, c'est-à-dire le partitionnement ayant la plus petite valeur pour . Les figures 1 et 2 montrent comment, sur un même jeu de données, l'algorithme du gradient converge vers le partitionnement optimal grâce à une initialisation favorable, ou au contraire, converge vers un partionnement sous-optimal avec une initialisation différente.

Figure 1 : Initialisation conduisant à un bon partitionnement.

Figure 2 : Initialisation conduisant à un partitionnement sous-optimal.

Méthode des k moyennes avec R

 

Illustration : compression d'image par réduction de la palette de couleurs

Une image non compressée est décrite comme une matrice de pixel, chaque pixel étant décrit par 3 entiers compris entre 0 et 255, décrivant respectivement l'intensité pour le rouge, le vert et le bleu (RVB). Si l'image comporte pixels, il faut donc bits pour stocker les descriptions de tous les pixels (il faut 8 bits pour encoder une valeur entre 0 et 255). La plupart des smartphones actuels prennent des photos dans des résolutions supérieures ou égales à 8 mégapixels, ce qui signifie qu'ils produisent des images comportant au moins 8 millions de pixels. Ainsi, la représentation non compressée d'une image d'une définition de 8 mégapixels nécessite 192 000 000 bits, soit 24 mo.

En limitant le nombre de couleurs d'une image à seulement couleurs, on peut remplacer la description d'un pixel en RVB par un index pointant vers la palette réduite à couleurs RVB. Par exemple, si on choisit , la représentation de l'image ne nécessite plus que bits. Dans le cas d'une image d'une définition de 8 mégapixels, cela représente 32 000 384 bits, soit 4 mo.

On peut déterminer une palette réduite à couleurs en appliquant la méthodes des k-moyennes au jeu de données qui décrit les couleurs des pixels qui compose une image.

La figure 3 ci-après montre comment la représentation d'une image (une photographie du quartier Saint-Georges à Lyon) évolue en fonction de la perte induite par la compression par réduction de la palette à seulement couleurs, pour allant de 2 à 128.

Figure 3 : image compressée par réduction de la palette pour k = 2, 4, 8, 16, 32, 64 et 128.