Module 2 — k-moyennes : principe, initialisation et limites

Les k-moyennes sont au partitionnement ce que la régression linéaire est au supervisé : le point de départ obligé, simple, rapide, et instructif jusque dans ses défauts. Les comprendre vraiment — y compris ce qu'elles ne savent pas faire — prépare tous les algorithmes qui suivent.

L'algorithme : deux étapes qui alternent

On fixe d'avance le nombre de groupes $k$. L'algorithme place alors $k$ centroïdes (les centres des groupes) et répète deux étapes jusqu'à stabilisation :

1. Affectation : chaque point rejoint le centroïde le plus proche ;
2. Mise à jour : chaque centroïde se replace à la moyenne des points qui lui ont été affectés.

Et ainsi de suite. Comme les centroïdes bougent, les affectations changent ; comme les affectations changent, les centroïdes bougent. Le processus converge toujours, et généralement en quelques dizaines d'itérations.

from sklearn.cluster import KMeans
from sklearn.preprocessing import StandardScaler

X_s = StandardScaler().fit_transform(X)     # imperatif : voir module 1
km = KMeans(n_clusters=4, n_init=10, random_state=42).fit(X_s)
km.labels_            # le groupe attribue a chaque point
km.cluster_centers_   # les k centroides, lisibles comme des profils types

Un mot sur cluster_centers_ : chaque centroïde est un vecteur de moyennes, donc un profil type du groupe. C'est le principal outil d'interprétation — « le groupe 2, ce sont les clients à panier élevé et faible fréquence ». Sans cette lecture, un partitionnement reste une colonne de numéros sans signification.

Ce que l'algorithme minimise : l'inertie

Les k-moyennes ne tâtonnent pas au hasard : elles minimisent l'inertie intra-classe, la somme des carrés des distances de chaque point à son centroïde.

$$\text{inertie} = \sum_{j=1}^{k} \sum_{x \in C_j} \lVert x - \mu_j \rVert^2$$

Autrement dit : des groupes aussi compacts que possible. Cette quantité, exposée par km.inertia_, ne cesse de décroître quand $k$ augmente — jusqu'à valoir zéro quand chaque point est son propre groupe. Elle ne peut donc pas, seule, servir à choisir $k$ ; c'est tout l'objet du module 3.

L'initialisation : pourquoi k-means++ compte

Les deux étapes convergent vers un minimum local, qui dépend de la position initiale des centroïdes. Un mauvais tirage de départ produit un partitionnement médiocre — deux centroïdes coincés dans le même nuage, un groupe évident coupé en deux.

Deux garde-fous, actifs par défaut dans scikit-learn et à ne jamais désactiver sans raison :

• k-means++ place les centroïdes initiaux loin les uns des autres, ce qui écarte d'emblée les configurations absurdes ;
• n_init relance l'algorithme plusieurs fois avec des tirages différents et conserve la solution de plus faible inertie.

Les limites structurelles : ce que k-moyennes ne voit pas

Ces limites ne sont pas des bogues mais des conséquences directes de la définition. Les connaître évite d'accuser les données.

Limite	Origine	Conséquence
$k$ à fixer d'avance	l'algorithme ne le déduit pas	il faut un critère externe (module 3)
groupes sphériques de taille comparable	minimisation d'une distance au centre	échoue sur les formes allongées ou incurvées
tout point est affecté	pas de notion de bruit	les valeurs aberrantes tirent les centroïdes
sensible à l'échelle	distance euclidienne	standardisation obligatoire

La deuxième ligne est la plus lourde de conséquences. Deux croissants imbriqués, structure évidente à l'œil, sont massacrés par les k-moyennes : minimiser la distance à un centre revient à découper l'espace en cellules convexes, et aucun découpage de ce type ne suit une courbe. C'est précisément le vide que DBSCAN comblera au module 5.

Variantes utiles à connaître

MiniBatchKMeans traite les très gros volumes en travaillant sur des échantillons successifs, pour une qualité à peine dégradée. k-médoïdes remplace la moyenne par un point réel du jeu de données, ce qui résiste mieux aux valeurs aberrantes et permet des distances non euclidiennes. Et pour des variables catégorielles, la moyenne n'a plus de sens : on passe à k-modes, ou l'on change de représentation.

En résumé

• Les k-moyennes alternent affectation au centroïde le plus proche et mise à jour des centroïdes à la moyenne, jusqu'à convergence.
• Elles minimisent l'inertie intra-classe (groupes compacts) ; cette inertie décroît toujours avec $k$ et ne suffit donc pas à le choisir.
• La convergence est locale : k-means++ et n_init protègent des mauvaises initialisations.
• Elles supposent des groupes sphériques de taille comparable, affectent tout point y compris les aberrants, et exigent une standardisation préalable.

Module suivant : choisir le nombre de groupes avec la méthode du coude et le score de silhouette.