NSI Première à Montréal • Algorithmique

Fiche de révision : l'algorithme des k plus proches voisins (NSI Première)

Q: Comment fonctionne l'algorithme des k plus proches voisins ?

On dispose d'une table d'exemples dont on connaît la classe. Pour un nouvel élément, on calcule sa distance à chaque exemple, on range les exemples du plus proche au plus éloigné, on garde les k premiers, et l'on prédit la classe la plus représentée parmi eux. Il n'y a pas de phase d'apprentissage : la table entière sert de modèle, et chaque prédiction la parcourt de nouveau.

Q: Comment choisir la valeur de k ?

On la choisit en mesurant les erreurs sur des exemples test, dont on connaît la classe mais qui ne sont pas dans la table. Un k égal à un suit chaque individu atypique, un k égal à la taille de la table répond toujours la classe la plus nombreuse. Avec deux classes, on prend un nombre impair pour éviter les égalités, puis on garde la valeur qui réussit le mieux sur les tests.

Q: Faut-il utiliser la distance euclidienne ou la distance de Manhattan ?

Les deux sont acceptées, et l'énoncé précise en général laquelle utiliser. La distance euclidienne mesure à vol d'oiseau, celle de Manhattan additionne les écarts de chaque attribut, comme un trajet le long d'un quadrillage. Elles peuvent désigner des plus proches voisins différents : le choix de la distance fait partie de l'algorithme, au même titre que le choix de k.

Q: Pourquoi faut-il normaliser les données avant de calculer les distances ?

Parce qu'un attribut exprimé avec de grands nombres écrase les autres. Si un prix varie de plusieurs centaines de dollars et une autonomie de quelques heures, la distance ne regarde presque plus que le prix. En ramenant chaque attribut entre zéro et un, à l'aide du minimum et du maximum de la table, on donne à chacun le même poids dans le calcul.

Cette fiche de révision accompagne le chapitre des k plus proches voisins du programme de NSI de première : distance entre deux éléments, tri d'une table par distance, vote de la classe majoritaire, influence du choix de k, préparation des données.

Elle ne redit pas le cours. Elle dit ce qui coûte des points en évaluation, ce que le correcteur attend exactement, et les contrôles à faire avant de rendre la copie.

Marque ici la fiche comme lue ou mets-la en favori : un compte gratuit, sans mot de passe, retient tes fiches lues et tes favoris d'une visite à l'autre et te dit quel chapitre attaquer ensuite. Crée ton espace, un courriel suffit.

Le fil du chapitre

Le vote ne décide rien : c'est la distance qui choisit les votants. Une mauvaise distance, un attribut qui n'est pas normalisé, une chaîne prise pour un nombre ou un $k$ mal choisi font voter les mauvais voisins, et la prédiction change sans qu'aucune erreur ne s'affiche.

Ce chapitre fait partie de NSI en Première

Pour s'entraîner Les exercices corrigés de ce chapitre, 10 exercices

Avant ce chapitre

Cette fiche suppose ces notions acquises. Si une méthode ci-dessous reste opaque, c'est presque toujours l'une d'elles qui manque, pas la fiche.

Remonter plus loin : la chaîne complète (5 chapitres) ↓

Le chemin de remédiation, du plus ancien au plus proche. Un élève qui reprend ce chapitre de zéro le reprend dans cet ordre.

1Algorithmique et ScratchTroisième, Mathématiques
2Algorithmique et PythonSeconde, Mathématiques
3Python : types, contrôle, fonctions et tableaux
4Algorithmique : preuve, terminaison et coût
5Traitement de données en tables et types construits

Notions couvertes

Algorithme des k plus proches voisins
Apprentissage supervisé
Distance euclidienne
Distance de Manhattan
Vote majoritaire
Dictionnaire de compteurs
Choix du paramètre k
Sur-ajustement
Normalisation min-max
Fichier CSV
Tri avec une clé
Coût d'une prédiction

L'essentiel

L'algorithme en quatre gestes

• MESURER : calculer la distance de l'élément à classer à CHAQUE exemple de la table.
• CLASSER : trier les exemples par distance croissante, ou garder seulement les $k$ meilleurs pendant le parcours.
• RETENIR : les $k$ premiers sont les votants. On vérifie que le $k$ -ième et le $(k+1)$ -ième ne sont pas à égalité avec deux classes différentes.
• VOTER : compter les étiquettes des votants dans un dictionnaire, puis rendre l'étiquette de plus grand compteur. C'est une majorité RELATIVE : avec trois classes, $3$ voix sur $7$ peuvent gagner.

Il n'y a pas de phase d'apprentissage : la table ENTIÈRE est le modèle, et chaque prédiction la reparcourt.

Deux distances, deux réponses possibles

• EUCLIDIENNE : $d=\sqrt{(x-x')^{2}+(y-y')^{2}}$ , la distance à vol d'oiseau. Écarts $3$ et $4$ : $d=5$ .
• MANHATTAN : $d=|x-x'|+|y-y'|$ , le trajet le long d'un quadrillage. Écarts $3$ et $4$ : $d=7$ .
• Toujours $|a|+|b|\ge\sqrt{a^{2}+b^{2}}$ , avec égalité seulement si un écart est nul. Les deux distances peuvent donc désigner des plus proches voisins DIFFÉRENTS.
• Pour CLASSER, le carré de la distance euclidienne suffit : la racine est croissante et ne change aucun rang. On garde la racine dès qu'on compare la distance à un seuil.

Les points à distance

2

du centre forment un cercle pour la distance euclidienne et un losange pour celle de Manhattan : P est à

2

à vol d'oiseau mais à

2{,}8

en suivant le quadrillage.

Préparer les données avant de mesurer

• Un fichier CSV lu par csv.DictReader ne contient que des CHAÎNES : on convertit les colonnes numériques par float, une seule fois, au chargement.
• Des attributs d'unités ou d'étendues différentes se NORMALISENT : $x'=\dfrac{x-\min}{\max-\min}$ , avec le minimum et le maximum de la table, appliqués tels quels à l'élément à classer.
• Le choix de $k$ se fait sur des exemples TEST, hors de la table ; $k$ impair avec deux classes.

Les pièges qui coûtent des points

Les erreurs ci-dessous sont celles que je corrige le plus souvent en séance. Chacune coûte des points sur une copie, même quand le raisonnement est juste.

1. Oublier la valeur absolue dans la distance de Manhattan

toute la question, et des prédictions fausses sans aucune erreur

Ce qu'il ne faut pas écrire

« s = s + (p[i] - q[i]) »

Ce qu'il faut écrire

« s = s + abs(p[i] - q[i]) »

Pourquoi : Sans valeur absolue, les écarts se compensent : $(0\,;0)$ et $(5\,;-5)$ se retrouvent à distance $5-5=0$ , et une distance peut même être négative. Contrôle en une seconde : une distance est positive, et nulle seulement entre deux points identiques.

2. Récupérer le résultat de sort

1 à 2 points, et une erreur à la ligne suivante

Ce qu'il ne faut pas écrire

« voisins = table.sort(key=distance_a_x) »

Ce qu'il faut écrire

« voisins = sorted(table, key=distance_a_x) »

Pourquoi : La méthode sort trie la liste SUR PLACE et renvoie None : voisins vaut None, et voisins[0] lève une erreur. sorted, au contraire, renvoie une nouvelle liste triée et laisse la table intacte pour les prédictions suivantes.

3. Appeler la fonction de clé au lieu de la passer

1 point, le tri ne s'exécute pas

Ce qu'il ne faut pas écrire

« sorted(table, key=distance_a_x(e)) »

Ce qu'il faut écrire

« sorted(table, key=distance_a_x) », le nom seul, sans parenthèses

Pourquoi : Le paramètre key attend une FONCTION, que sorted appellera elle-même sur chaque élément. Écrire les parenthèses l'appelle une fois, trop tôt, sur un argument qui n'existe pas encore ou qui n'est pas le bon.

4. Dépouiller le vote avec max

toute la fonction de vote

Ce qu'il ne faut pas écrire

« return max(compteurs) »

Ce qu'il faut écrire

« on garde la clé e dont compteurs[e] est le plus grand »

Pourquoi : Parcourir un dictionnaire, c'est parcourir ses CLÉS : max(compteurs) renvoie l'étiquette la plus grande dans l'ordre alphabétique. Avec {'rouge': 4, 'bleu': 1}, c'est bien 'rouge', mais avec {'vert': 1, 'bleu': 4}, c'est 'vert', qui a une seule voix. La forme correcte est une boucle, ou max(compteurs, key=compteurs.get).

5. Additionner des grandeurs d'échelles différentes

2 points, et une prédiction dictée par un seul attribut

Ce qu'il ne faut pas écrire

« distance = écart d'autonomie en heures + écart de prix en dollars »

Ce qu'il faut écrire

« on normalise chaque attribut par $x'=\dfrac{x-\min}{\max-\min}$ avant de mesurer »

Pourquoi : Si le prix s'étend sur $800$ dollars et l'autonomie sur $20$ heures, un écart de $20$ dollars pèse autant que toute l'étendue d'autonomie : la distance ne regarde plus que le prix. Changer d'unité changerait les voisins, ce qui est absurde. Après normalisation, chaque attribut va de $0$ à $1$ .

6. Calculer avec les valeurs d'un CSV sans les convertir

toute la question, et un tri faux sans message

Ce qu'il ne faut pas écrire

« min([f['longueur'] for f in feuilles]) donne la plus petite longueur »

Ce qu'il faut écrire

« on applique float à chaque colonne numérique juste après le chargement »

Pourquoi : csv.DictReader lit du TEXTE. Les chaînes se comparent caractère par caractère : '10.5' est plus « petite » que '8.5' parce que '1' précède '8'. La soustraction, elle, lève une TypeError, ce qui est l'erreur heureuse ; la comparaison n'en lève aucune.

7. Juger k = 1 sur les exemples de la table

1 à 2 points sur la question d'interprétation

Ce qu'il ne faut pas écrire

« k = 1 réussit 100 % des exemples de la table, c'est le meilleur choix »

Ce qu'il faut écrire

« on mesure le taux de réussite sur des exemples TEST, absents de la table »

Avec

k=1

, le point atypique de la classe B décide seul ; avec

k=3

, les deux points de la classe A qui l'entourent l'emportent.

Pourquoi : Chaque exemple de la table est son propre plus proche voisin, à distance $0$ : le $100\ \%$ est garanti et ne prouve rien. Sur des exemples nouveaux, $k=1$ suit les individus atypiques de la table : c'est le sur-ajustement.

8. Choisir un k pair avec deux classes

1 point, et un programme qui ne sait pas conclure

Ce qu'il ne faut pas écrire

« Avec $k=4$ , il y a toujours une classe majoritaire »

Ce qu'il faut écrire

« Avec deux classes, on prend $k$ impair : $3$ , $5$ , $7$ »

Pourquoi : Quatre voix peuvent se partager $2$ contre $2$ . Un nombre impair de voix ne se coupe jamais en deux moitiés égales. Avec trois classes, même un $k$ impair ne suffit plus : $5$ voix donnent $2$ , $2$ , $1$ , et il faut une règle de départage écrite.

Quelle méthode choisir

Quelle précaution avant de lancer l'algorithme, selon les données

Une table d'exemples étiquetés et un élément à classer

Si Les valeurs viennent d'un fichier CSV → Convertir par float les colonnes numériques, une fois, au chargement

Exemple : '10.5' < '8.5' est vrai pour des chaînes, faux pour des nombres
Si Les attributs ont des unités ou des étendues différentes → Normaliser chaque attribut : $x'=\dfrac{x-\min}{\max-\min}$

Exemple : Étendues $20$ h et $800$ dollars : rapport $40$ , le prix décide seul sans normalisation
Si Il y a deux classes → Prendre $k$ impair, et le choisir sur des exemples test

Exemple : $k=3$ : un score de $2$ contre $1$ au pire, jamais d'égalité
Si Il y a trois classes ou plus → Écrire une règle de départage, par exemple la classe du plus proche voisin

Exemple : $k=5$ : $2$ , $2$ et $1$ voix, aucun $k$ n'évite ce cas
Si On ne compare que des rangs de distance → Le carré de la distance euclidienne suffit, sans racine

Exemple : Carrés $25$ , $36$ , $49$ : même ordre que $5$ , $6$ , $7$

Aucune de ces branches ne lève d'erreur quand on l'oublie : le programme tourne et prédit. C'est pour cela qu'elles se vérifient AVANT, et non en attendant un message.

La rédaction attendue

Le correcteur coche des étapes. Les voici dans l'ordre, avec la phrase de conclusion qu'il attend mot pour mot.

Écrire la fonction de prédiction

Quand l'utiliser : Quand un énoncé demande d'écrire ou de compléter l'algorithme des k plus proches voisins

1 Écrire la spécification : ce que la fonction reçoit, ce qu'elle renvoie, et la précondition sur k.
2 Construire la liste des couples (distance, étiquette), un par exemple de la table.
3 Trier cette liste par distance croissante, avec sort sur la liste de travail ou sorted.
4 Garder les k premiers couples par une tranche et en extraire les étiquettes.
5 Compter les étiquettes dans un dictionnaire et renvoyer celle du plus grand compteur, avec la règle de départage écrite en commentaire.
6 Tester sur un petit exemple fait à la main, dont on connaît les voisins.

Phrase de conclusion

« predire(table, cible, k) calcule la distance de cible à chaque exemple de table, range les exemples par distance croissante, garde les k premiers et renvoie l'étiquette la plus fréquente parmi eux ; en cas d'égalité, celle du plus proche. Précondition : 0 < k <= len(table). »

Le piège : Oublier la précondition sur k : avec k plus grand que la table, la tranche ne lève pas d'erreur et vote avec toute la table, alors qu'un accès par indice en lèverait une.

Barème : 1 point pour les distances, 1 point pour le tri correctement écrit, 1 point pour la sélection des k premiers, 2 points pour le vote par dictionnaire, 1 point pour la précondition et la règle de départage.

Vérifier avant de rendre

Cinq minutes de vérification récupèrent plus de points qu'un exercice de plus commencé à la hâte.

Une distance est-elle positive, et nulle entre deux points identiques ?

On appelle la fonction de distance sur un point et lui-même, puis sur deux points dont les écarts se compensent. Tout résultat négatif ou nul à tort condamne la fonction.

Entre $(0\,;0)$ et $(5\,;-5)$ , une version sans valeur absolue renvoie $0$ : elle est fausse.
La somme des compteurs vaut-elle k ?

Après le comptage, on additionne les valeurs du dictionnaire. Tout autre total signale une tranche mal écrite ou un vote sur la mauvaise liste.

Pour $k=7$ : $3+2+2=7$ . Un total de $12$ dit qu'on a fait voter toute la table.
Le k-ième et le (k+1)-ième voisins sont-ils à égalité ?

On lit les distances autour de la frontière. Deux distances égales portant deux classes différentes rendent le choix des votants arbitraire.

Rangs $3$ et $4$ à $1{,}5$ , l'un fitis, l'autre véloce : $k=3$ est ambigu, on le signale.
Les colonnes numériques sont-elles des nombres ?

Juste après le chargement, on affiche le type d'une valeur de chaque colonne. Un str dans une colonne de mesures annonce des tris faux.

type(table[0]['longueur']) doit afficher float, pas str.

L'exercice type décortiqué

Une prédiction complète, à la main

On classe des citrons en verts ou jaunes d'après leur largeur et leur hauteur, en centimètres. Table : V1 $(3\,;4)$ vert, V2 $(1\,;5)$ vert, J1 $(6\,;7)$ jaune, J2 $(5\,;7)$ jaune, J3 $(6\,;5)$ jaune. Prédisez la couleur du citron C $(4\,;5)$ pour $k=3$ , avec la distance euclidienne.

Le citron C est plus près d'un citron vert, V1, que de tout autre, mais les deux suivants, J3 et J2, sont jaunes.

Étape 1

Les deux attributs sont en centimètres, d'étendues $5$ et $3$ : pas de normalisation nécessaire.

Pourquoi

On regarde les échelles AVANT de mesurer. Si l'un des attributs était en grammes, il faudrait normaliser, sinon il déciderait seul du vote.

Étape 2

Carrés des distances à C : V1 $1+1=2$ ; V2 $9+0=9$ ; J1 $4+4=8$ ; J2 $1+4=5$ ; J3 $4+0=4$ .

Pourquoi

On compare des carrés : la racine est croissante et ne change aucun rang, et le calcul reste exact, sans calculatrice.

Étape 3

Rangement : V1 $2$ , J3 $4$ , J2 $5$ , J1 $8$ , V2 $9$ .

Pourquoi

On vérifie la frontière : le troisième est à $5$ , le quatrième à $8$ , aucune égalité. Les trois votants sont donc bien définis.

Étape 4

Votants pour $k=3$ : V1 vert, J3 jaune, J2 jaune. Compteurs : jaune $2$ , vert $1$ .

Pourquoi

La somme des compteurs vaut $3$ , soit $k$ : le vote porte sur la bonne liste.

Étape 5

Prédiction : jaune. Pour comparaison, $k=1$ aurait prédit vert, le plus proche étant V1.

Pourquoi

Comparer deux valeurs de k montre que la réponse dépend du nombre de votants : c'est l'influence de k que le programme demande de savoir décrire.

Conclusion rédigée

Avec $k=3$ et la distance euclidienne, le citron C est prédit jaune, par $2$ voix contre $1$ .

L'erreur classique sur cet exercice : Prendre le plus proche voisin pour la réponse : V1 est le plus proche, mais il est mis en minorité par les deux suivants dès que trois voisins votent.

À savoir par cœur

• Mesurer, classer, retenir k votants, voter.
• Euclidienne : $\sqrt{(x-x')^{2}+(y-y')^{2}}$ ; Manhattan : $|x-x'|+|y-y'|$ .
• Pour classer, le carré de la distance suffit.
• sorted renvoie une nouvelle liste, sort renvoie None.
• key=f, sans parenthèses.
• max(compteurs) compare les CLÉS, pas les compteurs.
• Deux classes : $k$ impair. Trois classes : une règle de départage.
• $k=1$ sur-ajuste ; $k=n$ répond toujours la classe la plus nombreuse.
• Normalisation : $x'=\dfrac{x-\min}{\max-\min}$ , min et max de la table.
• CSV : que des chaînes, float au chargement.
• Choisir k sur des exemples test, jamais sur la table.
• Pas d'apprentissage : chaque prédiction reparcourt toute la table.

Questions fréquentes

Comment fonctionne l'algorithme des k plus proches voisins ?

On dispose d'une table d'exemples dont on connaît la classe. Pour un nouvel élément, on calcule sa distance à chaque exemple, on range les exemples du plus proche au plus éloigné, on garde les k premiers, et l'on prédit la classe la plus représentée parmi eux. Il n'y a pas de phase d'apprentissage : la table entière sert de modèle, et chaque prédiction la parcourt de nouveau.

Comment choisir la valeur de k ?

On la choisit en mesurant les erreurs sur des exemples test, dont on connaît la classe mais qui ne sont pas dans la table. Un k égal à un suit chaque individu atypique, un k égal à la taille de la table répond toujours la classe la plus nombreuse. Avec deux classes, on prend un nombre impair pour éviter les égalités, puis on garde la valeur qui réussit le mieux sur les tests.

Faut-il utiliser la distance euclidienne ou la distance de Manhattan ?

Les deux sont acceptées, et l'énoncé précise en général laquelle utiliser. La distance euclidienne mesure à vol d'oiseau, celle de Manhattan additionne les écarts de chaque attribut, comme un trajet le long d'un quadrillage. Elles peuvent désigner des plus proches voisins différents : le choix de la distance fait partie de l'algorithme, au même titre que le choix de k.

Pourquoi faut-il normaliser les données avant de calculer les distances ?

Parce qu'un attribut exprimé avec de grands nombres écrase les autres. Si un prix varie de plusieurs centaines de dollars et une autonomie de quelques heures, la distance ne regarde presque plus que le prix. En ramenant chaque attribut entre zéro et un, à l'aide du minimum et du maximum de la table, on donne à chacun le même poids dans le calcul.

Passer à la pratique

Exercices corrigés : Les k plus proches voisins

Une méthode se prouve sur une copie, pas sur une fiche. La série du même chapitre reprend chacun de ces pièges dans un exercice, avec le corrigé rédigé étape par étape.

10 exercices corrigés
100 points
180 minutes

Faire les exercices

Fiche précédente Traitement de données en tables et types construits Fiche suivante Interactions homme-machine sur le Web

© Ahmed Squalli Houssaini. Fiche publiée sur www.letuteurscientifique.ca/fiches/nsi-k-plus-proches-voisins. Libre pour l'usage personnel et en classe ; sa republication ailleurs demande une autorisation écrite (mentions légales).

Voir aussi

Toutes les fiches Tous les exercices Tuteur NSI

Vous cherchez un tuteur en NSI à Montréal ?

Contactez-moi pour une première séance. Bachelier en informatique de McGill et maîtrise en informatique appliquée de Concordia, je travaille l'algorithmique sur des données réelles, jusqu'aux pièges qui ne lèvent aucune erreur.

Me contacter WhatsApp

Site par Studio Squalli