Première · Numérique et sciences informatiques

Algorithme des k plus proches voisins

Comprendre le principe de l'algorithme des k plus proches voisins et savoir l'appliquer pas à pas pour attribuer une classe à un nouvel élément.

Aperçu gratuit
Illustration de la fiche « Algorithme des k plus proches voisins »

Les points essentiels

  • L'algorithme des k plus proches voisins classe un nouvel élément à partir des éléments déjà étiquetés les plus proches de lui.
  • Chaque élément est décrit par des attributs numériques : ce sont ses coordonnées dans l'espace des données.

Les mots à connaître

Élément étiqueté
Élément d'un jeu de données dont la classe est déjà connue.
Attribut
Grandeur numérique qui décrit un élément et sert à calculer les distances.

Un exemple pour comprendre

Un jeu de données contient quatre points étiquetés : A(1 ; 1) et B(2 ; 2) de classe rouge, C(6 ; 6) et D(7 ; 6) de classe bleue. On veut classer le point P(3 ; 3) avec k = 3. Quelle classe obtient P ?

Étape 1 — Calculer les distances euclidiennes au point P. d(P, A) = √((3 − 1)² + (3 − 1)²) = √8 ≈ 2,83 d(P, B) = √((3 − 2)² + (3 − 2)²) = √2 ≈ 1,41 d(P, C) = √((3 − 6)² + (3 − 6)²) = √18 ≈ 4,24 d(P, D) = √((3 − 7)² + (3 − 6)²) = √25 = 5 Étape 2 — Ranger les distances par ordre croissant : B (1,41), A (2,83), C (4,24), D (5). Étape 3 — Garder les k = 3 plus proches : B, A et C. Étape 4 — Compter les classes : rouge (B, A), bleue (C). La classe rouge est majoritaire avec 2 voisins sur 3. Conclusion : le point P est classé dans la classe rouge.

Première page de l’Essentiel : Algorithme des k plus proches voisins
Ketty