Les $k$ -moyennes à la main

Exercice · informatique (tronc commun des prépas scientifiques), chapitre 19 — Algorithmique de l'apprentissage : voisins et moyennes

Énoncé

Soient les points $1 D$ suivants : $(1, 1), (2, 1), (1, 2), (5, 4), (6, 4), (5, 5)$ . On initialise deux centres de groupes à $c_{1} = (1, 1)$ et $c_{2} = (2, 1)$ . Dérouler les étapes de l'algorithme des $k$ -moyennes jusqu'à sa convergence et analyser si la mauvaise initialisation des centres compromet la qualité du partitionnement.

Corrigé

É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 $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 autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.

Les k-moyennes à la main

Énoncé

Corrigé

Les $k$ -moyennes à la main