Les k-means pas à pas
deux gaussiennes sur une droite, deux centres, et le paysage du critère vu du dessus
1 · CRITÈRE
$$W(c_1,c_2)=\frac{1}{n}\sum_{k=1}^{2}\sum_{i\in C_k}\left(x_i-c_k\right)^2,
\qquad x_i\sim\tfrac12\,\mathcal{N}\!\left(-\tfrac{\delta}{2},\sigma^2\right)+\tfrac12\,\mathcal{N}\!\left(\tfrac{\delta}{2},\sigma^2\right)$$
inertie intraclasse : la carte montre \(W\) pour chaque couple de centres \((c_1,c_2)\), chaque point étant affecté au centre le plus proche
2 · L'ALGORITHME ET SON CHEMIN SUR LE CRITÈRE
les données sur la droite, colorées par classe
carte de \(W(c_1,c_2)\) vue du dessus · un clic = centres initiaux
\(W\) au fil des demi-étapes
Espace ou → : étape suivante. Une étape = affectation puis mise à jour des centres. Changer \(\delta\) ou \(\sigma\) garde l'initialisation et relance l'algorithme.
3 · RAPPELS SUR LES K-MEANS
- Algorithme de Lloyd : on minimise \(W\) alternativement en la partition (chaque point va au centre le plus proche) puis en les centres (\(c_k\) = barycentre de \(C_k\)). \(W\) ne peut que décroître : convergence en un nombre fini d'étapes.
- Sur la carte, chaque mise à jour fait descendre le point \((c_1,c_2)\) ; l'affectation ne le déplace pas mais change la « nappe » quadratique sur laquelle il descend.
- Huygens : \(T = W + B\), inertie totale = intraclasse + interclasse. Minimiser \(W\) revient à maximiser \(B\).
- La carte est symétrique par rapport à la diagonale \(c_1=c_2\) (échange des étiquettes) : deux minima globaux jumeaux. L'algorithme peut s'arrêter sur un minimum local : d'où plusieurs initialisations, ou k-means++.
- Si \(\delta\) est petit devant \(\sigma\), les k-means coupent quand même en deux : pour une seule gaussienne, les centres optimaux sont \(\pm\sigma\sqrt{2/\pi}\approx\pm0{,}80\,\sigma\).
- En dimension 1, l'optimum exact s'obtient en triant les points et en testant les \(n-1\) coupures : ici \(W^\star\) = .