Comprendre Partitionnement en k moyennes
Le k-moyennes cherche une partition des données en k groupes minimisant la distance quadratique totale de chaque point au centre de son groupe. Explorer toutes les partitions possibles est irréalisable, l’algorithme emploie donc un raffinement itératif simple et rapide.
Deux étapes alternent. Étant donné les centroïdes courants, affecter chaque point au plus proche. Étant donné ces affectations, recalculer chaque centroïde comme la moyenne de ses membres. Chaque étape ne peut que diminuer, ou laisser inchangée, la distance quadratique intra-groupe totale, et comme les affectations possibles sont en nombre fini, la procédure doit se terminer.
La convergence se fait toutefois vers un optimum local. Une mauvaise initialisation peut produire une partition véritablement médiocre, les implémentations exécutent donc l’algorithme plusieurs fois depuis des points de départ différents et conservent le meilleur résultat. Le schéma d’initialisation k-means++ améliore les choses en écartant les centroïdes initiaux les uns des autres plutôt qu’en les tirant uniformément au hasard.
L’objectif encode des hypothèses fortes qu’il est facile de négliger. Minimiser la distance euclidienne quadratique à un centre favorise des groupes ronds, de tailles semblables et de densités semblables. Les groupes allongés, imbriqués ou très inégaux sont systématiquement mal partitionnés, et comme l’algorithme renvoie toujours exactement k groupes, il scindera volontiers un groupe authentique unique, ou en fusionnera deux, si k est mal choisi.
Comment calculer
minimize Σₖ Σ_{i ∈ Cₖ} ‖xᵢ − μₖ‖²
où
- Cₖ
- l’ensemble des observations affectées au groupe k
- μₖ
- le centroïde du groupe k, la moyenne de ses membres
- ‖xᵢ − μₖ‖²
- la distance euclidienne quadratique d’un point à son centroïde
Exemple : Partitionnement en k moyennes
Pour une segmentation de clientèle sur la dépense et la fréquence de visite avec k = 3, l’algorithme part de trois centres arbitraires, affecte chaque client au plus proche, puis déplace chaque centre vers la moyenne des clients qui lui sont affectés, et répète jusqu’à ce que les affectations cessent de changer.
Choisir k est le problème le plus difficile. La méthode du coude trace la variance intra-groupe totale en fonction de k : elle décroît toujours quand k augmente, mais le rythme d’amélioration chute typiquement d’un coup à un certain point, et ce coude suggère une valeur raisonnable. James et ses coauteurs recourent exactement à ce genre de critère visuel du coude pour décider combien de composantes retenir en analyse en composantes principales.
Le critère est une heuristique, non un test. Sur des données sans véritable structure de groupes, l’algorithme renvoie tout de même k groupes d’apparence soignée, et le coude peut être ambigu ou absent. Toute structure de groupes doit être confrontée à la connaissance du domaine plutôt qu’acceptée parce que l’algorithme l’a produite.
Questions fréquentes
Comment choisir k ?
Il n’existe pas de réponse purement statistique. La méthode du coude et le score de silhouette sont les heuristiques usuelles, mais le choix doit normalement être éclairé par l’usage que l’on fera des groupes. Différentes valeurs de k peuvent chacune se défendre selon les objectifs.
Pourquoi des exécutions différentes donnent-elles des résultats différents ?
L’algorithme converge vers un optimum local déterminé par ses centroïdes initiaux. Des départs aléatoires différents aboutissent à des optima différents, ce qui explique pourquoi les implémentations relancent plusieurs fois par défaut et pourquoi l’initialisation k-means++ est généralement préférée.
L’échelle des variables importe-t-elle ?
Énormément. L’objectif est une distance euclidienne : une variable mesurée en grandes unités domine le calcul de distance et détermine de fait le partitionnement. Les variables doivent être standardisées, sauf si leurs échelles relatives sont délibérément significatives.
En résumé
Le k-moyennes est rapide, simple et à convergence garantie, mais vers un optimum local seulement, et il impose des groupes sphériques de tailles semblables que les données en aient ou non. Standardisez les variables, relancez plusieurs fois, et traitez les groupes obtenus comme une hypothèse plutôt qu’un résultat.