K-moyennes

Un article de Wikipédia, l'encyclopédie libre.
(Redirigé depuis Algorithme des k-moyennes)
Aller à : navigation, rechercher

Le partitionnement en k-moyennes (ou K-means en anglais) est une méthode de partitionnement de données et un problème d'optimisation combinatoire. Étant donnés des points et un entier k, le problème est de diviser les points en k partitions, souvent appelés clusters, de façon à minimiser une certaine fonction. On considère la distance d'un point à la moyenne des points de son cluster ; la fonction à minimiser est la somme des carrés de ces distances.

Il existe un algorithme classique pour ce problèmes, souvent appelé algorithme des k-moyennes, utilisé dans la plupart des applications. Le problème est aussi étudié comme un problème d'optimisation classique, avec par exemple des algorithmes d'approximation.

Les k-moyennes sont notamment utilisées en apprentissage non supervisé où l'on divise des observations en k partitions. 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.

Définition[modifier | modifier le code]

Étant donné un ensemble de points (x1, x2, …, xn), on cherche à partitionner les n points en k ensembles S = {S1, S2, …, Sk} (kn) en minimisant 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 classique[modifier | modifier le code]

Description[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.

Analyse[modifier | modifier le code]

Il y a un nombre fini de partitions possibles à k classes[1]. 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.

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.

Autre aspects algorithmiques[modifier | modifier le code]

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

Applications[modifier | modifier le code]

Avantages et inconvénients pour l'apprentissage[modifier | modifier le code]

Un inconvénient possible des k-moyennes pour le partitionnement est que les clusters dépendent de l'initialisation et de la distance choisie[réf. souhaitée].

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.

Quantification vectorielle[modifier | modifier le code]

Article détaillé : Quantification vectorielle.

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

  1. voir Nombre de Stirling pour plus de détails
  2. 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]

Implémentations libres[modifier | modifier le code]

Implémentations commerciales[modifier | modifier le code]