Regroupement par K-moyennes

Le regroupement par K-moyennes partitionne les observations en un nombre fixe de grappes en minimisant la somme totale des carrés des distances intra-grappes par rapport aux centroïdes des grappes.

Definition

Le regroupement par K-moyennes est une méthode de partitionnement qui établit un nombre prescrit de centres de grappes et attribue chaque observation à son centre le plus proche afin de minimiser la somme totale des carrés des distances euclidiennes entre les observations et leurs centres attribués.

Scope

Ce sujet aborde l'objectif de la somme des carrés intra-grappes, l'algorithme itératif d'affectation et de mise à jour qui alterne entre l'affectation des points au centroïde le plus proche et le recalcul des centroïdes, la dépendance à l'initialisation et les optima locaux qui en résultent, le choix du nombre de grappes, ainsi que les hypothèses et les limites de la méthode.

Core questions

• Comment les observations peuvent-elles être partitionnées pour minimiser la dispersion intra-grappe ?
• Pourquoi l'algorithme ne converge-t-il que vers un optimum local et comment cela est-il atténué ?
• Comment le nombre de grappes est-il choisi ?
• Quelles formes et échelles de grappes la méthode suppose-t-elle implicitement ?

Key theories

Minimisation de la somme des carrés intra-grappes

Le K-moyennes recherche la partition et l'ensemble de centroïdes minimisant la somme totale des carrés des distances entre les points et les centres de leurs grappes, un objectif pour lequel l'itération alternée d'affectation et de mise à jour diminue de manière monotone le critère.

Sensibilité à l'optimum local

Étant donné que l'objectif est non convexe, l'algorithme converge vers un minimum local qui dépend des centres initiaux, ce qui motive des redémarrages multiples et un amorçage (seeding) soigneux.

Clinical relevance

Le K-moyennes est une méthode rapide et évolutive par défaut pour le partitionnement de grands ensembles de données. Il est utilisé dans la quantification vectorielle, la réduction de couleur d'image, la segmentation de clientèle et comme initialisation pour des modèles plus complexes.

History

L'idée de partitionnement basée sur les centroïdes a été formalisée par MacQueen, qui a nommé le k-moyennes en 1967, s'appuyant sur l'algorithme de quantification antérieur de Lloyd. Il est devenu l'une des méthodes de regroupement les plus largement utilisées en raison de sa simplicité et de sa rapidité.

Debates

Hypothèses implicites du K-moyennes

La minimisation de la distance euclidienne au carré favorise les grappes approximativement sphériques et de tailles égales. Par conséquent, le K-moyennes peut induire en erreur lorsque les grappes sont allongées, de tailles inégales ou non convexes, ce qui motive le recours à des alternatives basées sur des modèles ou sur la densité.

Key figures

• James MacQueen
• Stuart Lloyd

Seminal works

• hastie2009
• everitt2011
• macqueen1967

Frequently asked questions

Pourquoi le K-moyennes donne-t-il des résultats différents lors de différentes exécutions ?

Son objectif est non convexe, de sorte que l'algorithme converge vers un optimum local qui dépend des centres initiaux aléatoires ; l'exécuter plusieurs fois et conserver le meilleur résultat est une pratique courante.

Comment choisir le nombre de grappes k ?

Les heuristiques courantes incluent la méthode du coude (elbow method) pour la somme des carrés intra-grappes, la statistique du gap et la largeur moyenne de silhouette, bien qu'aucune ne soit définitive et que la connaissance du domaine guide souvent le choix.