Les k-moyennes à la main — exercice corrigé d'informatique (tronc commun des prépas scientifiques) (chapitre 19)

Étape 1 (Affectation) :
Les points $(1, 1)$ et $(1, 2)$ sont plus proches de $c_{1}$ $⟹$ affectés au groupe $1$ .
Les points $(2, 1)$ (distance nulle), $(5, 4), (6, 4), (5, 5)$ sont plus proches de $c_{2}$ $⟹$ affectés au groupe $2$ .
Étape 1 (Recentrage) :
Nouveau centre $c_{1} = moyenne ((1, 1), (1, 2)) = (1, 1, 5)$ .
Nouveau centre $c_{2} = moyenne ((2, 1), (5, 4), (6, 4), (5, 5)) = (4, 5, 3, 5)$ .
Étape 2 (Affectation) :
Le point $(2, 1)$ est maintenant à distance au carré $1, 25$ de $c_{1}$ et $12, 5$ de $c_{2}$ $⟹$ il bascule dans le groupe $1$ .
Les points $(1, 1)$ et $(1, 2)$ restent dans le groupe $1$ .
Les points $(5, 4), (6, 4), (5, 5)$ restent dans le groupe $2$ .
Étape 2 (Recentrage) :
Nouveau centre $c_{1} = moyenne ((1, 1), (2, 1), (1, 2)) = (4/3, 4/3) \approx (1, 33, 1, 33)$ .
Nouveau centre $c_{2} = moyenne ((5, 4), (6, 4), (5, 5)) = (16/3, 13/3) \approx (5, 33, 4, 33)$ .
Étape 3 : L'affectation ne change plus. Les centres sont stables, l'algorithme a convergé. Analyse : Malgré une mauvaise initialisation (les deux centres de départ appartenaient au même groupe de points), l'effet d'attraction des points distants sur le centre $c_{2}$ lui a permis d'émigrer vers le second groupe, illustrant la robustesse naturelle de l'algorithme.

Les $k$ -moyennes à la main