Le $k$ -NN à la main

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

Énoncé

Soit le jeu d'entraînement à deux classes : classe A : $(1, 1), (1, 2), (2, 1), (2, 2)$ ; classe B : $(5, 5), (5, 6), (6, 5), (6, 6)$ . Classer les points $x_{1} = (3, 3)$ et $x_{2} = (4, 5)$ pour $k = 1$ puis $k = 3$ en détaillant les calculs de distances au carré, de voisinage et de vote.

Corrigé

Pour $x_{1} = (3, 3)$ :
Distances au carré vers la classe A : $d^{2} (x_{1}, (1, 1)) = 8$ , $d^{2} (x_{1}, (1, 2)) = 5$ , $d^{2} (x_{1}, (2, 1)) = 5$ , $d^{2} (x_{1}, (2, 2)) = 2$ .
Distances au carré vers la classe B : $d^{2} (x_{1}, (5, 5)) = 8$ , $d^{2} (x_{1}, (5, 6)) = 13$ , $d^{2} (x_{1}, (6, 5)) = 13$ , $d^{2} (x_{1}, (6, 6)) = 18$ .
Voisins les plus proches par ordre croissant : $(2, 2)$ [ $d^{2} = 2$ , classe A], puis $(1, 2)$ [ $d^{2} = 5$ , classe A] et $(2, 1)$ [ $d^{2} = 5$ , classe A].
Pour $k = 1$ : le plus proche est de classe A.
Pour $k = 3$ : les trois plus proches sont de classe A. Vote majoritaire : A (3 voix contre 0).
Pour $x_{2} = (4, 5)$ :
Distances au carré vers la classe A : $d^{2} (x_{2}, (1, 1)) = 25$ , $d^{2} (x_{2}, (1, 2)) = 18$ , $d^{2} (x_{2}, (2, 1)) = 20$ , $d^{2} (x_{2}, (2, 2)) = 13$ .
Distances au carré vers la classe B : $d^{2} (x_{2}, (5, 5)) = 1$ , $d^{2} (x_{2}, (5, 6)) = 2$ , $d^{2} (x_{2}, (6, 5)) = 4$ , $d^{2} (x_{2}, (6, 6)) = 5$ .
Voisins par ordre croissant : $(5, 5)$ [ $d^{2} = 1$ , classe B], $(5, 6)$ [ $d^{2} = 2$ , classe B], puis $(6, 5)$ [ $d^{2} = 4$ , classe B].
Pour $k = 1$ : classe B.
Pour $k = 3$ : vote majoritaire B (3 voix contre 0). Note : Les deux nuages A et B étant très espacés, le choix du paramètre $k$ ne modifie pas la décision pour ces points. Le choix de $k$ devient critique uniquement pour des points situés à proximité immédiate de la frontière de séparation des classes (ex: $(3.5, 3.5)$ ).

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.

Le k-NN à la main

Énoncé

Corrigé

Le $k$ -NN à la main