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.

Historique[modifier | modifier le code]

Le terme « k-means » a été utilisé pour la première fois par James MacQueen en 1967[1], bien que l'idée originale ait été proposée par Hugo Steinhaus en 1957[2]. L'Algorithme classique a été proposé par Stuart Lloyd en 1957 à des fins de modulation d'impulsion codée, mais il n'a pas été publié en dehors des Bell Labs avant 1982[3]. En 1965, E.W.Forgy publia une méthode essentiellement similaire, raison pour laquelle elle est parfois appelée « méthode de Lloyd-Forgy » [4]. Une version plus efficace, codée en Fortran, a été publiée par Hartigan et Wong en 1975/1979[5],[6].

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

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'à ce qu'il y ait 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

Analyse[modifier | modifier le code]

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

À k fixé, la complexité lisse est polynomiale pour certaines configurations, dont des points dans un espace euclidien[7] et le cas de la divergence de Kullback-Leibler[10]. Si k fait partie de l'entrée, la complexité lisse est encore polynomiale pour le cas euclidien[11]. 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[12]. Dans le cas euclidien, il existe un algorithme d'approximation polynomial, de ratio 9, par recherche locale[13].

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. MacQueen, J. B. (1967). « Some Methods for classification and Analysis of Multivariate Observations » in Proceedings of 5th Berkeley Symposium on Mathematical Statistics and Probability. 1: 281–297. Consulté le 2009-04-07. 
  2. H. Steinhaus, « Sur la division des corps matériels en parties », Bull. Acad. Polon. Sci., vol. 4, no 12,‎ , p. 801–804 (zbMATH 0079.16403)
  3. S. P. Lloyd, « Least square quantization in PCM », Bell Telephone Laboratories Paper,‎ Published in journal much later: S. P. Lloyd., « Least squares quantization in PCM », IEEE Transactions on Information Theory, vol. 28, no 2,‎ , p. 129–137 (DOI 10.1109/TIT.1982.1056489, lire en ligne)
  4. E.W. Forgy, « Cluster analysis of multivariate data: efficiency versus interpretability of classifications », Biometrics, vol. 21,‎ , p. 768–769 (JSTOR 2528559)
  5. J.A. Hartigan, Clustering algorithms, John Wiley & Sons, Inc.,‎
  6. J. A. Hartigan et M. A. Wong, « Algorithm AS 136: A K-Means Clustering Algorithm », Journal of the Royal Statistical Society, Series C, vol. 28, no 1,‎ , p. 100–108 (JSTOR 2346830)
  7. a et b David Arthur et Sergei Vassilvitskii, « Worst-Case and Smoothed Analysis of the ICP Algorithm, with an Application to the k-Means Method », SIAM J. Comput., vol. 39, no 2,‎ , p. 766-782.
  8. voir Nombre de Stirling pour plus de détails
  9. Andrea Vattani, « k-means Requires Exponentially Many Iterations Even in the Plane », Discrete & Computational Geometry, vol. 45, no 4,‎ , p. 596-616
  10. Bodo Manthey et Heiko Röglin, « Worst-Case and Smoothed Analysis of k-Means Clustering with Bregman Divergences », JoCG, vol. 4, no 1,‎ , p. 94-132.
  11. David Arthur, Bodo Manthey et Heiko Röglin, « Smoothed Analysis of the k-Means Method », Journal of the ACM, vol. 58, no 5,‎ , p. 19 (lire en ligne)
  12. The Hardness of Kmeans Clustering Sanjoy Dasgupta, Technical Report CS2008-06, Department of Computer Science and Engineering, University of California, San Diego
  13. 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,‎ , p. 89-112 (lire en ligne)

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]