informatique (tronc commun des prépas scientifiques) · Chapitre 19 · Exercice de TD

Le minimum local, en laboratoire

Algorithmique de l'apprentissage : voisins et moyennes · niveau 2

É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é de la question 1

(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$ .

Question 2 : comment l'IA t'aide

(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.

Élève

Je sais calculer l'affectation des points aux deux centres. Mais comment démontrer que l'algorithme est bloqué, et pas seulement qu'il fait un mauvais premier pas qu'il corrigera ensuite ?

Une itération des $k$ -moyennes enchaîne deux étapes : affectation, puis recentrage. Que faut-il constater sur les centres à la fin d'une itération pour avoir la certitude que plus rien ne bougera ?

Élève

Si les centres recalculés sont exactement les anciens, l'affectation suivante sera identique, puis le recentrage aussi, et ainsi de suite indéfiniment.

C'est cela. Fais donc les deux étapes : à quel centre chaque point est-il affecté, en comparant par exemple les distances de $(0, 0)$ à $c_{1}$ et à $c_{2}$ , et quelles sont les moyennes des deux groupes obtenus ?

L'IA ne donne pas la réponse : elle pose la question qui fait avancer. À toi de continuer.

Continue cet exercice avec l'IA

Reprends la question 2 là où le dialogue s'arrête, puis la suite de l'exercice.

Continuer avec l'IA — gratuit, sans inscription

Gratuit, sans inscription. L'IA te guide pas à pas, sans te donner la réponse.

Le cours du chapitre · Tous les exercices du chapitre

Continuer avec l'IA, gratuit →