Les k plus proches voisins à la main — exercice corrigé d'enseignement scientifique (terminale) (chapitre 11)

Les

k

plus proches voisins à la main

De la machine de Turing à l'intelligence artificielle · niveau 2

Énoncé

Six exemples sont donnés dans un plan, avec leur classe : $P_{1} (1; 1)$ classe A, $P_{2} (2; 1)$ classe A, $P_{3} (4; 4)$ classe B, $P_{4} (5; 4)$ classe B, $P_{5} (4; 1)$ classe B, $P_{6} (1; 4)$ classe A. On veut classer le point $Q (3; 2)$ . 1. Calculer les six distances. 2. Classer $Q$ pour $k = 1$ , $k = 3$ , $k = 5$ . 3. Que conclure ? 4. Que se passerait-il si l'on multipliait toutes les abscisses par $100$ ?

Corrigé

1. On utilise $d = (x_{Q} - x_{P})^{2} + (y_{Q} - y_{P})^{2}$ : $d (Q, P_{1}) = 4 + 1 \approx 2, 24 (A), d (Q, P_{2}) = 1 + 1 \approx 1, 41 (A),$ $d (Q, P_{3}) = 1 + 4 \approx 2, 24 (B), d (Q, P_{4}) = 4 + 4 \approx 2, 83 (B),$ $d (Q, P_{5}) = 1 + 1 \approx 1, 41 (B), d (Q, P_{6}) = 4 + 4 \approx 2, 83 (A) .$

2. $k = 1$ : deux points sont à égale distance minimale, $P_{2}$ (A) et $P_{5}$ (B) : il y a égalité, et l'algorithme doit prévoir une règle de départage. $k = 3$ : $P_{2}$ (A), $P_{5}$ (B) et l'un des deux points à $2, 24$ , $P_{1}$ (A) ou $P_{3}$ (B) — donc $2$ A/ $1$ B ou $1$ A/ $2$ B selon le départage. $k = 5$ : soit $3$ A/ $2$ B, soit $2$ A/ $3$ B. Aucune de ces réponses n'est déterminée.

3. Que $Q$ est situé exactement à la frontière entre les deux classes, et que l'algorithme n'a aucune réponse solide à donner. Un système bien conçu devrait signaler cette incertitude plutôt que de trancher : c'est précisément ce que la plupart des systèmes ne font pas.

4. Les distances horizontales seraient multipliées par $100$ et les distances verticales inchangées : l'abscisse écraserait complètement l'ordonnée, et le voisinage serait déterminé par la seule abscisse. C'est un piège classique : les $k$ plus proches voisins dépendent des unités choisies. On normalise donc toujours les variables avant d'appliquer la méthode. La leçon est générale : un prétraitement des données, invisible dans le résultat, peut changer complètement les conclusions.