K-moyennes

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 groupes, 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. Un algorithme classique de k-means est le même que l'algorithme de quantification de Lloyd-Max. Étant donné un ensemble de points (x1, x2, ..., xn), on cherche à partitionner les n points en k ensembles S = {S1, S2, ..., Sk} (k ≤ n) en minimisant la distance entre les points à l'intérieur de chaque partition : où μi est le barycentre des points dans Si. Le terme « k-means » a été utilisé pour la première fois par James MacQueen en 1967, bien que l'idée originale ait été proposée par Hugo Steinhaus en 1957. L'algorithme classique a été proposé par Stuart Lloyd en 1957 à des fins de modulation par impulsions et codage, mais il n'a pas été publié en dehors des Laboratoires Bell avant 1982. En 1965, E. W. Forgy publia une méthode essentiellement similaire, raison pour laquelle elle est parfois appelée « méthode de Lloyd-Forgy ». Une version plus efficace, codée en Fortran, a été publiée par Hartigan et Wong en 1975/1979. 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.