Skip to content
Retour aux résultats

Regroupement par K-moyennes

Introduite par
MacQueen, J. B.; Lloyd, S. P.
Année
1967 (formalized 1982)
Type
Partitional clustering
Famille
Machine learning

Ce texte est une traduction automatique et n’a pas encore été relu. Lire l’original en anglais

Taille de police

À quoi sert-elle ?

Le K-moyennes est un algorithme classique de regroupement non supervisé et partitionnel qui divise un ensemble de données en K groupes disjoints en attribuant itérativement chaque observation à son centroïde le plus proche et en mettant à jour les centroïdes comme la moyenne des points qui leur sont assignés.

C'est l'un des outils exploratoires les plus utilisés en apprentissage automatique et en analyse de données.

L’intuition derrière la méthode

Imaginez déposer K aimants sur une carte de points de données. Chaque point est attiré par son aimant le plus proche, puis chaque aimant se déplace vers le centre de gravité des points qu'il a attirés. Répétez ce cycle d'attraction et de déplacement jusqu'à ce que rien ne bouge : les aimants ont trouvé K groupements naturels. Le K-moyennes formalise exactement cette idée, en minimisant la distance totale au carré de chaque point à son centre de cluster, appelée somme des carrés intra-cluster (WCSS ou inertie).

Histoire

L'idée du K-moyennes a été introduite indépendamment par MacQueen en 1967, qui a inventé le terme, et formalisée comme un algorithme itératif efficace par Stuart Lloyd chez Bell Labs dans les années 1950 (publié en 1982). L'amélioration de l'initialisation k-means++ par Arthur et Vassilvitskii en 2007 a abordé le problème de la sensibilité aux minima locaux. Aujourd'hui, le K-moyennes reste une méthode fondamentale d'apprentissage non supervisé enseignée dans pratiquement tous les cursus de science des données.

Quand l’utiliser

Le K-moyennes convient au regroupement exploratoire de grands ensembles de données purement numériques lorsque vous avez besoin d'un partitionnement rapide et évolutif et que vous êtes à l'aise pour spécifier K à l'avance ou pour le rechercher avec la méthode du coude ou de la silhouette. Il fonctionne bien pour la segmentation client, la compression d'images, le regroupement de sujets de documents, et le pré-traitement avant l'apprentissage supervisé. Évitez-le lorsque les clusters sont non sphériques, de tailles ou de densités très variables, lorsque les caractéristiques sont catégorielles ou ordinales (utilisez k-modes ou k-prototypes à la place), lorsque le nombre de clusters est totalement inconnu et que des expériences avec K variable ne sont pas réalisables, ou lorsque les données contiennent de nombreux points aberrants (utilisez DBSCAN ou des variantes robustes à la place).

Limites et points d’attention

  • Nécessite que K soit spécifié à l'avance ; choisir un K incorrect produit des clusters dénués de sens.
  • Suppose des clusters sphériques de taille similaire ; les clusters allongés, irréguliers ou d'échelles différentes sont divisés ou fusionnés incorrectement.
  • Sensible aux points aberrants : un seul point extrême peut éloigner un centroïde du cœur du cluster.
  • Ne fonctionne qu'avec des caractéristiques numériques continues ; les données catégorielles nécessitent un algorithme différent (k-modes).
  • Converge vers un minimum local ; les résultats peuvent varier d'une exécution à l'autre avec différentes graines aléatoires, sauf si k-means++ ou plusieurs redémarrages sont utilisés.

Les conditions de la source ne remplacent ni une revue scientifique indépendante ni la validation par un moteur d’analyse.

Points forts

  • Rapide et évolutif : O(nKdi) par itération, pratique sur des millions d'observations avec un K et des dimensions modérés.
  • Simple à implémenter, largement disponible dans tous les principaux frameworks ML, et facile à expliquer à des publics non techniques.
  • Fonctionne bien sur des clusters larges, bien séparés, approximativement sphériques et de taille similaire.
  • L'initialisation k-means++ réduit considérablement la sensibilité aux conditions de départ par rapport à l'initialisation aléatoire.
  • Déterministe avec une graine aléatoire fixe, rendant les résultats reproductibles.

Applications

  • Segmentation client pour le marketing et la personnalisation basée sur des caractéristiques comportementales ou démographiques.
  • Compression d'images par quantification des couleurs des pixels vers K valeurs représentatives (quantification de couleurs).
  • Regroupement de documents et de textes comme étape dans les pipelines de modélisation de sujets après vectorisation.
  • Pré-traitement de détection d'anomalies : les points éloignés de tout centroïde sont des candidats aberrants.
  • Étape d'initialisation pour des algorithmes plus complexes tels que les modèles de mélange gaussien ou le regroupement hiérarchique.
  • Analyse d'expression génique pour regrouper des gènes ou des échantillons avec des profils d'expression similaires.

Comment ça marche

Comment ça marche

1

K centroïdes de cluster sont placés dans l'espace des caractéristiques, soit en sélectionnant aléatoirement K points de données (Forgy), soit par la stratégie plus intelligente k-means++ qui répartit les centroïdes initiaux pour réduire la probabilité de minima locaux médiocres. Le choix de l'initialisation est important : k-means++ conduit généralement à une convergence plus rapide et à de meilleures solutions finales.

2

Chaque observation est assignée au cluster dont le centroïde est le plus proche selon la distance euclidienne. Cette assignation stricte crée K partitions disjointes des données. Formellement, chaque point x_i est assigné au cluster c_i = argmin_k ||x_i - mu_k||^2.

Formule
c_i = \arg\min_k \|x_i - \mu_k\|^2
3

Chaque centroïde est recalculé comme la moyenne arithmétique de tous les points actuellement assignés à ce cluster : mu_k = (1/|C_k|) fois la somme de tous les x_i dans C_k. Cette étape garantit que le nouveau centroïde minimise la WCSS au sein de chaque cluster étant donné l'assignation actuelle.

Formule
\mu_k = \frac{1}{|C_k|} \sum_{x_i \in C_k} x_i
4

Les étapes d'assignation et de mise à jour alternent jusqu'à ce que les positions des centroïdes cessent de changer (ou changent de moins d'un seuil de tolérance) ou qu'un nombre maximum d'itérations soit atteint. L'algorithme est garanti de converger vers un minimum local de WCSS, mais pas nécessairement vers le minimum global.

5

La qualité de la solution est évaluée par la WCSS totale (inertie) J = somme sur les clusters de la somme sur les points assignés de ||x_i - mu_k||^2. Le choix de K est une préoccupation distincte abordée par la méthode du coude, les scores de silhouette, ou les statistiques d'écart, car l'algorithme lui-même nécessite que K soit spécifié à l'avance.

Formule
J = \sum_{k=1}^{K} \sum_{x_i \in C_k} \|x_i - \mu_k\|^2

Pièges courants

  • Oublier de standardiser les caractéristiques avant le regroupement — les variables sur de grandes échelles domineront les calculs de distance.
  • Sélectionner K en inspectant uniquement la WCSS intra-échantillon sans le graphique du coude ou la validation par silhouette, conduisant à un K trivialement petit ou grand.
  • Exécuter une seule initialisation et accepter le premier résultat sans plusieurs redémarrages pour se prémunir contre les minima locaux médiocres.
  • Inclure des variables catégorielles ou ordinales dans la matrice des caractéristiques sans encodage approprié ou sans passer à k-modes.
  • Traiter les étiquettes de cluster comme des identités de groupe significatives sans validation externe, surtout lorsque les clusters ne sont pas bien séparés.

Questions fréquentes

Comment choisir le bon nombre de clusters K ?

Exécutez le K-moyennes pour une gamme de valeurs de K, tracez la somme des carrés intra-cluster en fonction de K, et recherchez un 'coude' où le taux de diminution ralentit brusquement. Complétez cela avec des scores de silhouette, qui mesurent à quel point chaque point est similaire à son propre cluster par rapport aux clusters voisins ; une silhouette moyenne plus élevée indique des clusters mieux définis.

Pourquoi obtiens-je des résultats différents à chaque exécution ?

Le K-moyennes est sensible à l'initialisation et converge vers un minimum local plutôt que global de la WCSS. Utilisez l'initialisation k-means++ et définissez une graine aléatoire fixe pour la reproductibilité. Exécuter l'algorithme plusieurs fois avec différentes graines et conserver la solution avec l'inertie la plus faible est une bonne pratique.

Le K-moyennes fonctionne-t-il avec des données catégorielles ?

Non. Le K-moyennes repose sur la distance euclidienne et les moyennes de centroïdes, qui sont indéfinies pour les variables catégorielles. Pour des données purement catégorielles, utilisez k-modes ; pour des données mixtes numériques et catégorielles, utilisez k-prototypes.

Quand devrais-je préférer DBSCAN ou GMM au K-moyennes ?

Utilisez DBSCAN lorsque les clusters ont des formes irrégulières ou que vous avez besoin d'une détection automatique de points aberrants sans spécifier K. Utilisez les Modèles de Mélange Gaussien (GMM) lorsque vous souhaitez des assignations de cluster souples (probabilistes) ou des clusters de tailles et d'orientations différentes, au prix d'une complexité computationnelle plus élevée.

Dois-je mettre à l'échelle mes caractéristiques ?

Oui, presque toujours. Le K-moyennes utilise la distance euclidienne, donc les caractéristiques avec de grandes plages numériques domineront le regroupement. Appliquez une standardisation par score z ou une mise à l'échelle min-max avant d'ajuster le K-moyennes, à moins que toutes les caractéristiques ne soient déjà à la même échelle.

Méthodes associées

Sources

  1. Lloyd, S. P. (1982). Least squares quantization in PCM. IEEE Transactions on Information Theory, 28(2), 129–137.

    Ouvrir la référence DOI
    Copié.
  2. MacQueen, J. B. (1967). Some methods for classification and analysis of multivariate observations. Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability, 1, 281–297.

    Ouvrir la référence de la publication
    Copié.