Un vote sans majorité

Exercice · niveau 2 · informatique (MP2I/MPI), chapitre 26 — Apprentissage automatique

Énoncé

Quatre points sur une droite : $1$ et $2$ sont rouges, $3$ et $4$ sont bleus. On classe le point $x = 2, 6$ par les $k$ plus proches voisins, pour $k = 1, 2, 3, 4$ . Que rend l'algorithme dans chaque cas ?

Corrigé

Les distances sont $∣2, 6 - 3∣ = 0, 4$ , puis $0, 6$ (vers $2$ ), $1, 4$ (vers $4$ ) et $1, 6$ (vers $1$ ). L'ordre des voisins est donc $3, 2, 4, 1$ .

$k$	voisins retenus	vote
$1$	$3$	bleu
$2$	$3, 2$	$1$ bleu, $1$ rouge : égalité
$3$	$3, 2, 4$	$2$ bleus, $1$ rouge : bleu
$4$	$3, 2, 4, 1$	$2$ bleus, $2$ rouges : égalité

Ce que l'exercice met en scène : en deux classes, un $k$ pair peut produire une égalité, et l'algorithme du cours n'a alors rien à rendre. On prend donc $k$ impair. Avec $c$ classes, la même précaution ne suffit plus — il faut départager, et le procédé usuel est de reprendre l'étiquette du plus proche voisin, seul point qui ne peut pas être à égalité avec lui-même.

Deuxième enseignement, à l'autre bout : pour $k = n$ , les voisins sont tous les points, le vote ne dépend plus de $x$ , et l'algorithme rend toujours la classe majoritaire globale. Entre $k = 1$ qui recopie le bruit et $k = n$ qui répond une constante, il y a un choix à faire, et le cours le dit : on l'évalue.

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.