K-Means pas à pas

Comment fonctionne K-Means

K-Means partage $n$ points en $k$ groupes en cherchant $k$ centres qui minimisent l'inertie, la somme des carrés des distances de chaque point à son centre :

L'algorithme de Lloyd alterne deux étapes, chacune ne pouvant que faire baisser $J$ :

1. Affectation — chaque point rejoint le centre le plus proche : $c(i) = \arg\min_j \lVert x_i - \mu_j \rVert^2$ ;
2. Mise à jour — chaque centre se place au barycentre de ses points : $\mu_j = \frac{1}{\lvert C_j \rvert} \sum_{i \in C_j} x_i$.

Il s'arrête quand l'affectation ne change plus. La convergence est garantie, mais vers un minimum local : le résultat dépend des centres de départ.

Ce que la démonstration montre

• Trois groupes : le cas favorable. Relancez plusieurs fois avec des centres « au hasard » : il arrive que deux centres se partagent un groupe et qu'un troisième en couvre deux. k-means++ écarte les centres au départ et évite presque toujours ce piège.
• Groupes étirés : K-Means mesure des distances euclidiennes et suppose des groupes ronds de même taille ; des groupes allongés sont découpés en travers.
• Sans structure : l'algorithme rend toujours $k$ groupes, même quand il n'y en a pas. C'est à vous de vérifier qu'ils ont un sens.
• Deux anneaux : aucune frontière droite ne sépare un anneau de l'autre ; K-Means échoue par construction. Une méthode à densité (DBSCAN) ou spectrale est adaptée.

Choisir k

L'inertie diminue toujours quand $k$ augmente (elle vaut zéro pour $k = n$) : elle ne suffit pas à choisir $k$. On cherche le « coude » de la courbe inertie-$k$, ou on utilise le score de silhouette.