Le minimum local, en laboratoire

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

Énoncé

Soient quatre points situés aux coins d'un rectangle allongé : $(0, 0), (0, 1), (10, 0), (10, 1)$ . On applique le $k$ -moyennes pour $k = 2$ . (a) Calculer l'inertie du partitionnement gauche/droite et celle du partitionnement bas/haut. (b) Démontrer que l'initialisation des centres à $c_{1} = (5, 0)$ et $c_{2} = (5, 1)$ conduit à un blocage immédiat de l'algorithme sur le mauvais partitionnement. (c) Proposer une solution algorithmique pour éviter ce problème.

Corrigé

(a)

Partitionnement optimal (gauche/droite) : Les centres sont $(0, 0.5)$ et $(10, 0.5)$ . La distance de chaque point à son centre est de $d^{2} = 0.25$ . L'inertie totale est de $4 \times 0.25 = 1$ .
Partitionnement sous-optimal (bas/haut) : Les centres sont $(5, 0)$ et $(5, 1)$ . Chaque point est situé à une distance de $5^{2} = 25$ de son centre. L'inertie totale est de $4 \times 25 = 100$ . (b) Avec les centres initiaux $c_{1} = (5, 0)$ et $c_{2} = (5, 1)$ :
Les points $(0, 0)$ et $(10, 0)$ sont plus proches de $c_{1}$ $⟹$ affectés au groupe 1.
Les points $(0, 1)$ et $(10, 1)$ sont plus proches de $c_{2}$ $⟹$ affectés au groupe 2. Lors de l'étape de recentrage, les nouveaux centres sont calculés comme les moyennes des groupes, redonnant précisément $c_{1} = (5, 0)$ et $c_{2} = (5, 1)$ . L'algorithme a convergé et s'arrête sur une inertie de 100, soit 100 fois supérieure à l'optimum global. (c) L'algorithme s'est figé dans un minimum local. Pour y remédier, on utilise la stratégie multi-départs : on lance l'algorithme $p$ fois (ex: $p = 10$ ) à partir de centres initiaux choisis aléatoirement, et on conserve la partition qui produit l'inertie minimale globale.

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.