K-moyennes

Le problème des k-moyennes (k-means en anglais) est un problème d'optimisation combinatoire permettant de formaliser le problème de partitionnement de données. Par extension, on parle d'algorithme des k-moyennes, ou de méthode des k-moyennes, pour désigner l'algorithme de Lloyd, qui est l'heuristique la plus classiquement utilisée pour ce problème. Étant donnés un ensemble de points et un entier k, le problème est de trouver une partition de ces points en k groupes minimisant la variance à l'intérieur de chaque groupe. Plus précisément, il s'agit de minimiser la somme des carrés des distances de chaque point à la moyenne des points de son groupe. 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. Il s'agit par ailleurs d'un cas particulier du problème de quantification en traitement du signal.