Un algorithme itératif d'apprentissage non supervisé qui partitionne n points de données en k grappes en alternant l'affectation de chaque point au centroïde de grappe le plus proche et le recalcul des centroïdes comme la moyenne des points affectés jusqu'à stabilisation des affectations ou atteinte d'un critère d'arrêt.

Principe

Optimiser un objectif non convexe (somme des distances au carré aux centres de clusters) par mises à jour coordonnées : étape d'affectation (étiquetage par centroïde le plus proche) et étape de mise à jour (recalcul des centroïdes), qui diminue monotoniquement l'objectif mais peut converger vers des minima locaux dépendant de l'initialisation.

Démonstration

Pour un jeu de points 2D et k=3, initialiser trois centroïdes (aléatoirement ou via k‑means++), affecter chaque point au centroïde le plus proche, recalculer chaque centroïde comme la moyenne de ses points, et itérer ; des grappes se forment autour de régions denses mais peuvent se scinder ou se coller selon la forme et k.

Mauvaise application

Appliquer k‑means à des données non euclidiennes, attributs catégoriels sans encodage, grappes de tailles très différentes ou de formes non convexes, ou choisir un k inadapté (trop grand/petit) conduit à des grappes trompeuses et à l'effondrement ou au vidage de centroïdes.

Conséquence

Donne un partitionnement simple, évolutif et interprétable via les centroïdes ; toutefois les résultats sont sensibles à k et à l'initialisation, supposent des grappes sphériques euclidiennes et ne capturent pas des structures arbitraires ou hiérarchiques sans adaptations.

Inversion

Traiter chaque point comme sa propre grappe (k=n) ou regrouper tous les points en une seule grappe (k=1) sont des renversements triviaux : ils minimisent certains termes de l'objectif mais suppriment l'information de regroupement significative.

Limite

Conçu pour des espaces numériques euclidiens avec un k pré-spécifié ; exclut l'application directe à des données purement catégorielles sans transformation, des métriques non euclidiennes (sauf adaptation), et les modèles de mélange probabilistes où la structure de variance importe (préférer GMM).

Tension sémantique

Souvent confondu avec des méthodes basées sur centroïdes ou des modèles de mélange gaussien ; k‑means est basé sur centroïdes avec affectations dures minimisant la distance euclidienne au carré, tandis que les GMM attribuent des probabilités molles et modélisent la covariance, offrant des compromis différents.

Synthèse

Le k‑moyennes alterne affectation au centroïde le plus proche et recomputation des centroïdes pour diminuer la variance intra‑grappe : une méthode de partitionnement rapide et centrée sur le centroïde adaptée aux grappes euclidiennes approximativement sphériques mais fragile face à l'initialisation, au choix de k et aux formes non convexes.