Numérique et sciences informatiques (NSI) · Première

Fiche de révision : l’algorithme des k plus proches voisins

L’essentiel à connaître, sur une seule page. Imprime-la ou enregistre-la en PDF.

ULUMINE · Numérique et sciences informatiques (NSI) · Première

L’algorithme des k plus proches voisins

Pour classer une cible, kNN cherche ses k plus proches voisins parmi des exemples étiquetés et retient la classe majoritaire.

Algorithme

  • 1. Distance de la cible à chaque donnée : √((xA − xB)² + (yA − yB)²).
  • 2. Trier par distance croissante ; 3. garder les k premiers ; 4. vote majoritaire.
  • Python : sorted(donnees, key=dist)[:k] puis comptage dans un dictionnaire.

Choix de k

  • Le résultat peut changer avec k.
  • k impair pour deux classes ; k = 1 sensible au bruit ; k trop grand → classe majoritaire globale.
  • Choisir k en testant sur des données de classe connue.

Limites

  • Toutes les distances recalculées à chaque prédiction.
  • Caractéristiques à mettre à des échelles comparables.
  • Données biaisées → prédictions biaisées.

Pièges à éviter

  • Oublier le carré ou la racine dans la distance.
  • Prendre les k plus éloignés (tri dans le mauvais sens).
  • Croire que la prédiction ne dépend pas de k.
  • Mélanger des caractéristiques d’échelles très différentes.

À découvrir aussi

Première · Numérique et sciences informatiques (NSI)

Représenter les entiers : binaire, hexadécimal, complément à deux

Écrire un entier en base 2 et en base 16, passer d’une base à l’autre, coder les entiers relatifs en complément à deux : cours et exercices de NSI en Première.