Algorithme des k-moyennes

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

L'algorithme des k-moyennes (ou K-means en anglais) est un algorithme de partitionnement de données relevant des statistiques et de l'apprentissage automatique (plus précisément de l'apprentissage non supervisé). C'est une méthode dont le but est de diviser des observations en K partitions (clusters) dans lesquelles chaque observation appartient à la partition avec la moyenne la plus proche. Les nuées dynamiques sont une généralisation de ce principe, pour laquelle chaque partition est représentée par un noyau pouvant être plus complexe qu'une moyenne. L'algorithme classique de K-means est le même que l'algorithme de quantification de Lloyd-Max.

Description[modifier | modifier le code]

Étant donné un ensemble d'observations (x1, x2, …, xn), où chaque observation est un vecteur de dimension d, l'algorithme k-means de regroupement vise à partitionner les n observations dans k ensembles S = {S1, S2, …, Sk} (kn) afin de minimiser la distance entre les points à l'intérieur de chaque partition :

\underset{\mathbf{S}}{\operatorname{arg\,min}} \sum_{i=1}^{k} \sum_{\mathbf x_j \in S_i} \left\| \mathbf x_j - \boldsymbol\mu_i \right\|^2

μi est la moyenne des points dans Si.

Algorithme[modifier | modifier le code]

Algorithme standard[modifier | modifier le code]

  • Choisir k points qui représentent la position moyenne des partitions m1(1),…,mk(1) initiales (au hasard par exemple)
  • Répéter jusqu'à convergence :
- assigner chaque observation à la partition la plus proche (i.e effectuer une partition de Voronoï selon les moyennes).
S_i^{(t)} = \left\{ \mathbf x_j : \big\| \mathbf x_j - \mathbf m^{(t)}_i \big\| \leq \big\| \mathbf x_j - \mathbf m^{(t)}_{i^*} \big\|\ \forall\ i^*=1,\ldots,k \right\}
- mettre à jour la moyenne de chaque cluster
\mathbf m^{(t+1)}_i = \frac{1}{|S^{(t)}_i|} \sum_{\mathbf x_j \in S^{(t)}_i} \mathbf x_j

La convergence est atteinte quand il n'y a plus de changement.

Convergence[modifier | modifier le code]

Il y a un nombre fini de partitions possibles à k classes (voir Nombre de Stirling pour plus de détails). De plus, chaque étape de l'algorithme fait strictement diminuer la fonction de coût, positive, et fait découvrir une meilleure partition.

Cela permet d'affirmer que l'algorithme converge toujours en temps fini, vers un minimum local.

On peut aussi exhiber un contre-exemple montrant que la partition finale n'est pas toujours optimale.


Malgré ça, l'algorithme peut être lent à converger, et on conseille donc de rajouter deux critères d'arrêt lors de son implémentation :

  • nombre d'étapes limité (souvent faible, de l'ordre de 10 pour 2 ou 3 classes sur des ensembles de point 1x2 de taille 200),
  • taux de décroissance du coût limité : on s'arrête dès que la différence entre le coût après et avant l'étape est assez faible.

Complexité algorithmique[modifier | modifier le code]

Le problème du clustering par les K-means est NP-difficile dans le cas général[1]. En pratique, il est donc fréquemment fait usage d'heuristiques[réf. nécessaire].

Avantages et inconvénients[modifier | modifier le code]

Un inconvénient[réf. nécessaire] de cet algorithme est que les clusters dépendent de l'initialisation et de la distance choisie.

Le fait de devoir choisir a priori le paramètre K peut être perçu comme un inconvénient ou un avantage. Dans le cas du calcul des sac de mots par exemple, cela permet de fixer exactement la taille du dictionnaire désiré. Au contraire, dans certains partitionnements de données on préférera s'affranchir d'une telle contrainte.

Implémentations[modifier | modifier le code]

Cette section ne cite pas suffisamment ses sources. Pour l'améliorer, ajouter en note des références vérifiables ou les modèles {{Référence nécessaire}} ou {{Référence souhaitée}} sur les passages nécessitant une source.

Libres[modifier | modifier le code]

Commerciales[modifier | modifier le code]

Références[modifier | modifier le code]

  1. The Hardness of Kmeans Clustering Sanjoy Dasgupta, Technical Report CS2008-06, Department of Computer Science and Engineering, University of California, San Diego

Voir aussi[modifier | modifier le code]

Bibliographie[modifier | modifier le code]

Articles connexes[modifier | modifier le code]

Liens externes[modifier | modifier le code]