Le clustering K-Means est une méthode de quantification vectorielle, issue à l'origine du traitement du signal, qui partitionne un ensemble d'observations en k clusters, où chaque observation appartient au cluster dont la moyenne est la plus proche, appelée centroïde du cluster. Cela aboutit à un partitionnement de l'espace des données en cellules de Voronoï. L'algorithme est largement utilisé en apprentissage automatique pour des tâches telles que la segmentation client, la compression d'images et la reconnaissance de formes, et il constitue une technique fondamentale en intelligence artificielle et en analyse de données.
L'objectif du k-means est de minimiser la somme des carrés intra-cluster (WCSS), qui est la somme des distances euclidiennes au carré entre chaque point et son centroïde de cluster. Cela équivaut à minimiser les écarts quadratiques par paires des points au sein du même cluster. Cependant, le k-means minimise les distances euclidiennes au carré, et non les distances euclidiennes régulières ; ces dernières nécessiteraient de résoudre le problème de Weber, plus difficile. Pour la minimisation de la distance euclidienne, des alternatives comme les k-médianes ou les k-médoïdes sont plus appropriées.
Le problème de trouver le clustering k-means optimal est difficile sur le plan computationnel (NP-difficile), mais des algorithmes heuristiques efficaces convergent rapidement vers un optimum local. L'approche la plus courante est l'algorithme de Lloyd, qui assigne itérativement les points au centroïde le plus proche, puis met à jour les centroïdes en calculant la moyenne des points assignés. Ce raffinement itératif est similaire à l'algorithme d'espérance-maximisation utilisé pour les modèles de mélanges gaussiens, mais le k-means tend à trouver des clusters d'étendue spatiale comparable, tandis que les mélanges gaussiens permettent des formes différentes.
Algorithme et implémentation
L'algorithme k-means standard commence par un ensemble initial de k centroïdes, qui peuvent être choisis aléatoirement ou à l'aide de méthodes comme k-means++ pour améliorer la convergence. L'algorithme répète deux étapes jusqu'à convergence : l'assignation, où chaque observation est assignée au cluster dont le centroïde est le plus proche, et la mise à jour, où chaque centroïde est recalculé comme la moyenne de tous les points de son cluster. La convergence est généralement détectée lorsque les assignations ne changent plus ou lorsque l'amélioration du WCSS tombe sous un seuil.
Plusieurs variantes existent, notamment le k-means par mini-lots pour les grands ensembles de données et le k-means sphérique pour les données textuelles. Le choix de k est souvent déterminé à l'aide de la méthode du coude, de l'analyse de silhouette ou de la statistique de gap. La complexité temporelle de l'algorithme est approximativement O(nkd*i), où n est le nombre d'observations, d est la dimensionnalité et i est le nombre d'itérations.
Relation avec d'autres méthodes
Le k-means est un algorithme non supervisé, ce qui signifie qu'il ne nécessite pas de données étiquetées. Il a une relation lâche avec le classifieur des k plus proches voisins (k-NN), une technique supervisée. Appliquer le classifieur du plus proche voisin (1-NN) aux centres de clusters obtenus par k-means classe les nouvelles données dans les clusters existants ; cela est connu sous le nom de classifieur du centroïde le plus proche ou algorithme de Rocchio. Cette connexion met en évidence comment le clustering non supervisé peut soutenir des tâches supervisées.
Le k-means est également lié aux modèles de mélanges gaussiens (GMM). Les deux utilisent des centres de clusters pour modéliser les données, mais les GMM permettent aux clusters d'avoir des formes et des tailles différentes, tandis que le k-means suppose des clusters sphériques de variance similaire. Par conséquent, le k-means est plus simple et plus rapide, mais moins flexible.
Applications et limites
Le k-means est utilisé dans de nombreux domaines. Dans Amazon Web Services et Google Cloud, c'est un outil courant pour analyser le comportement des utilisateurs et optimiser l'allocation des ressources. En vision par ordinateur, il est utilisé pour la segmentation d'images et la quantification des couleurs. En marketing, il segmente les clients en fonction de leurs habitudes d'achat. L'algorithme est également un élément de base pour des méthodes plus complexes, telles que l'extraction de caractéristiques en apprentissage profond et le prétraitement des données en IA générative.
Cependant, le k-means a des limites. Il nécessite que le nombre de clusters k soit spécifié à l'avance, ce qui n'est pas toujours connu. Il est sensible à la sélection initiale des centroïdes, bien que k-means++ atténue ce problème. Il suppose que les clusters sont convexes et isotropes, ce qui peut ne pas être vrai pour des données réelles. Les valeurs aberrantes peuvent fausser les centroïdes, et l'algorithme peut converger vers des optima locaux. Malgré ces problèmes, sa simplicité et son efficacité en font un choix populaire.
Contexte historique et développement
L'algorithme k-means a été proposé pour la première fois par Hugo Steinhaus en 1956, puis affiné par Stuart Lloyd en 1957 aux Bell Labs (bien que non publié avant 1982). Le nom « k-means » a été inventé par James MacQueen en 1967. Depuis lors, de nombreuses améliorations ont été développées, notamment k-means++ pour une meilleure initialisation et la variante par mini-lots pour l'évolutivité. L'algorithme reste un pilier des programmes d'études en apprentissage automatique et est implémenté dans des bibliothèques majeures telles que scikit-learn et TensorFlow.