Comment un programme peut-il deviner l’espèce d’une fleur, ou décider si un message est indésirable ? Une idée simple consiste à regarder les exemples déjà connus qui lui ressemblent le plus. C’est le principe de l’algorithme des k plus proches voisins (kNN, pour k nearest neighbors), un premier pas vers l’apprentissage automatique.
Une question sur ce cours ?
ULU, le tuteur d’ULUMINE, t’aide à partir de ce cours.
Objectifs
- Comprendre le principe d’une classification à partir de données étiquetées
- Calculer une distance entre deux éléments décrits par des nombres
- Dérouler l’algorithme des k plus proches voisins et son vote majoritaire
- Mesurer l’influence de k et connaître les limites de la méthode
1. Le problème de classification
On dispose d’un jeu de données d’apprentissage : des éléments décrits par des caractéristiques numériques (taille, poids, mesures…) et dont la classe (l’étiquette) est connue. On veut prédire la classe d’un nouvel élément, la cible, à partir de ses seules caractéristiques.
Algorithme des k plus proches voisins : Pour classer la cible : on calcule sa distance à chaque élément connu, on garde les k plus proches, et on lui attribue la classe majoritaire parmi ces k voisins.
2. Distance et algorithme
d(A, B) = √((xA − xB)² + (yA − yB)²)
| Point | Coordonnées | Classe | Distance à P |
|---|---|---|---|
| A | (1, 1) | rouge | √2 ≈ 1,41 |
| B | (2, 1) | rouge | 1 |
| F | (1, 3) | rouge | √2 ≈ 1,41 |
| C | (4, 3) | bleu | √5 ≈ 2,24 |
| D | (5, 4) | bleu | √13 ≈ 3,61 |
| E | (3, 4) | bleu | √5 ≈ 2,24 |
Classer P (2, 2)
- Ordre des distances : B (1), puis A et F (√2), puis C et E (√5), puis D.
- k = 1 : le plus proche voisin est B, rouge → P est classé rouge.
- k = 3 : B, A, F sont tous rouges → rouge.
- k = 5 : B, A, F, C, E → 3 rouges contre 2 bleus → rouge.
from math import sqrt
def distance(p, q):
return sqrt((p[0] - q[0]) ** 2 + (p[1] - q[1]) ** 2)
def knn(donnees, cible, k):
"""donnees : liste de tuples (x, y, classe). Renvoie la classe prédite."""
def dist(d):
return distance((d[0], d[1]), cible)
voisins = sorted(donnees, key=dist)[:k]
votes = {}
for x, y, classe in voisins:
votes[classe] = votes.get(classe, 0) + 1
meilleure = None
for c in votes:
if meilleure is None or votes[c] > votes[meilleure]:
meilleure = c
return meilleure3. Le choix de k
Classer Q (3, 2) avec les mêmes données
- Distances : B et C : √2 ; E : 2 ; A et F : √5 ; D : √8.
- k = 3 : B (rouge), C (bleu), E (bleu) → bleu.
- k = 5 : on ajoute A et F (rouges) → 3 rouges contre 2 bleus → rouge.
La prédiction dépend de k !
- k trop petit (k = 1) : la prédiction est sensible à un exemple isolé ou mal étiqueté.
- k trop grand : on consulte des exemples éloignés ; avec k égal au nombre de données, on prédit toujours la classe la plus fréquente.
- Avec deux classes, un k impair évite les égalités de votes.
- En pratique, on choisit k en testant l’algorithme sur des données dont on connaît déjà la classe et en mesurant le taux de bonnes réponses.
À retenir
- kNN classe une cible à partir d’exemples étiquetés : distance, k plus proches, vote majoritaire.
- Distance euclidienne : √((xA − xB)² + (yA − yB)²).
- Le résultat peut changer avec k ; k impair évite les égalités pour deux classes.
- On choisit k en testant sur des données de classe connue.
- Limites : coût (toutes les distances), échelles des caractéristiques, qualité et biais des données.
Et maintenant, à toi !
Vérifie que tu as compris avec les exercices, puis révise avec la fiche.