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 une heuristique classique pour ce problème, souvent appelée méthodes des k-moyennes, utilisée pour 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]

Il existe un algorithme classique pour le problème, parfois appelé méthode des k-moyennes, très utilisé en pratique et considéré comme efficace bien que ne garantissant ni l'optimalité, ni un temps de calcul polynomial[1].

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[2]. 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, c'est-à-dire termine.

La solution finale n'est pas toujours optimale. De plus le temps de calcul peut-être exponentiel en le nombre de points, même pour dans le plan[3]. Dans la pratique, il est possible d'imposer une limite sur le nombre d’itération ou un critère sur l'amélioration entre itération.

A k fixé, la complexité lisse est polynomiale pour certaines configurations, dont des points dans un espace euclidien[1] et le cas de la divergence de Kullback-Leibler[4]. Si k fait partie de l'entrée, la complexité lisse est encore polynomiale pour le cas euclidien[5]. Ces résultats expliquent en partie l'efficacité de l'algorithme en pratique.

Autre aspects algorithmiques[modifier | modifier le code]

Le problème des k-moyenne est NP-difficile dans le cas général[6]. Dans le cas euclidien, il existe un algorithme d'approximation polynomial, de ratio 9, par recherche locale[7].

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. a et b David Arthur, « Worst-Case and Smoothed Analysis of the ICP Algorithm, with an Application to the k-Means Method », SIAM J. Comput., vol. 39, no 2,‎ 2009, p. 766-782.
  2. voir Nombre de Stirling pour plus de détails
  3. Andrea Vattani, « k-means Requires Exponentially Many Iterations Even in the Plane », Discrete & Computational Geometry, vol. 45, no 4,‎ 2011, p. 596-616
  4. « Worst-Case and Smoothed Analysis of k-Means Clustering with Bregman Divergences », JoCG, vol. 4, no 1,‎ 2013, p. 94-132.
  5. David Arthur, Bodo Manthey et Heiko Röglin, « Smoothed Analysis of the k-Means Method », Journal of the ACM, vol. 58, no 5,‎ 2011, p. 19 (lire en ligne)
  6. The Hardness of Kmeans Clustering Sanjoy Dasgupta, Technical Report CS2008-06, Department of Computer Science and Engineering, University of California, San Diego
  7. Tapas Kanungo, David M. Mount, Nathan S. Netanyahu, Christine D. Piatko, Ruth Silverman et Angela Y. Wu, « A local search approximation algorithm for k-means clustering », Comput. Geom., vol. 28, no 2-3,‎ 2004, p. 89-112

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]