Le clustering par k-moyennes est une méthode de quantification vectorielle, issue à l'origine du traitement du signal, qui partitionne n observations en k clusters, où chaque observation appartient au cluster dont la moyenne (le centre ou centroïde du cluster) est la plus proche. Cela aboutit à un partitionnement de l'espace des données en cellules de Voronoï. L'algorithme est largement utilisé en apprentissage automatique pour l'analyse de données non supervisée, comme la segmentation de clientèle, la compression d'images et la reconnaissance de formes.
Les k-moyennes minimisent les variances intra-cluster, mesurées par les distances euclidiennes au carré, mais pas les distances euclidiennes classiques, ce qui correspondrait au problème de Weber, plus difficile. La moyenne optimise les erreurs au carré, alors que seule la médiane géométrique minimise les distances euclidiennes. Par exemple, de meilleures solutions euclidiennes peuvent être trouvées en utilisant les k-médianes et les k-médoïdes.
Le problème est difficile sur le plan computationnel (NP-difficile) ; cependant, des algorithmes heuristiques efficaces convergent rapidement vers un optimum local. Ceux-ci sont généralement similaires à l'algorithme d'espérance-maximisation pour les mélanges de distributions gaussiennes, via une approche de raffinement itératif employée à la fois par les k-moyennes et la modélisation par mélange gaussien. Les deux utilisent des centres de clusters pour modéliser les données ; toutefois, le clustering par k-moyennes tend à trouver des clusters d'étendue spatiale comparable, tandis que le modèle de mélange gaussien permet aux clusters d'avoir des formes différentes.
L'algorithme non supervisé des k-moyennes a une relation lâche avec le classifieur des k-plus proches voisins, une technique d'apprentissage automatique supervisée populaire pour la classification, souvent confondue avec les k-moyennes en raison du nom. Appliquer le classifieur du 1-plus proche voisin aux centres de clusters obtenus par les k-moyennes classe de nouvelles données dans les clusters existants, ce que l'on appelle le classifieur du centroïde le plus proche ou l'algorithme de Rocchio.
Définition formelle
Étant donné un ensemble d'observations (x1, x2, ..., xn), où chaque observation est un vecteur réel à d dimensions, le clustering par k-moyennes vise à partitionner les n observations en k (≤ n) ensembles S = {S1, S2, ..., Sk} afin de minimiser la somme des carrés intra-cluster (WCSS), c'est-à-dire la variance. Formellement, l'objectif est de trouver :
argmin sur S de la somme de i=1 à k de la somme de x dans Si de ||x - μi||^2,
où μi est la moyenne (également appelée centroïde) des points dans Si, et ||·|| est la norme L2 usuelle. Cela équivaut à minimiser les écarts quadratiques par paires des points dans le même cluster, comme le montre l'identité selon laquelle la somme des distances au carré à la moyenne est égale à la distance quadratique moyenne par paire.
Algorithme
L'algorithme le plus courant, souvent appelé algorithme de Lloyd, utilise une approche de raffinement itératif. Il commence avec un ensemble initial de k centroïdes, puis alterne entre deux étapes : l'affectation et la mise à jour. Dans l'étape d'affectation, chaque observation est assignée au cluster dont le centroïde est le plus proche, généralement en utilisant la distance euclidienne. Dans l'étape de mise à jour, le centroïde de chaque cluster est recalculé comme la moyenne des points assignés. Ces étapes se répètent jusqu'à ce que les affectations ne changent plus, indiquant une convergence vers un optimum local.
L'initialisation est cruciale ; la méthode k-moyennes++, qui répartit les centroïdes initiaux, est une heuristique populaire pour améliorer la qualité du clustering final. L'algorithme est sensible au choix de k, et des méthodes comme la méthode du coude ou l'analyse de silhouette sont utilisées pour estimer un nombre approprié de clusters.
Propriétés et limites
Les k-moyennes supposent que les clusters sont sphériques et de taille similaire, ce qui limite leur applicabilité aux données avec des formes de clusters complexes. L'algorithme est également sensible aux valeurs aberrantes, car la moyenne est influencée par les valeurs extrêmes. Il converge vers un optimum local, pas nécessairement global, et différentes initialisations peuvent donner des résultats différents. Malgré ces limites, sa simplicité et son évolutivité en font un choix populaire pour les grands ensembles de données, en particulier dans les pipelines de augmentation de données et de prétraitement.
Applications
Les k-moyennes sont utilisées dans divers domaines. En intelligence artificielle, elles servent de référence pour les tâches de clustering. En vision par ordinateur, elles sont utilisées pour la segmentation d'images et la quantification des couleurs. En marketing, elles aident à segmenter les clients en fonction de leur comportement d'achat. En traitement du langage naturel, elles peuvent regrouper des documents ou des plongements de mots. L'algorithme est également un élément constitutif de techniques plus avancées, telles que l'apprentissage de caractéristiques en apprentissage profond et les modèles d'IA générative.
Relation avec d'autres méthodes
Les k-moyennes sont liées aux modèles de mélange gaussien (GMM), car les deux utilisent un raffinement itératif et des centres de clusters. Cependant, les GMM permettent aux clusters d'avoir des formes et des covariances différentes, tandis que les k-moyennes supposent des clusters isotropes. Le classifieur du centroïde le plus proche, dérivé des k-moyennes, est une méthode de classification supervisée simple. Les k-moyennes sont souvent confondues avec les k-plus proches voisins (k-NN), mais elles sont distinctes : les k-moyennes sont non supervisées, tandis que les k-NN sont supervisés.
Histoire et développement
Le concept des k-moyennes a été proposé pour la première fois par Hugo Steinhaus en 1956, et le terme « k-moyennes » a été inventé par James MacQueen en 1967. L'algorithme de Lloyd, publié en 1957 mais peu connu jusqu'en 1982, est l'implémentation standard. Au fil des ans, de nombreuses variantes ont été développées, comme les k-moyennes par mini-lots pour les données à grande échelle et les c-moyennes floues pour le clustering doux.