k plus proches voisins et matrice de confusion

Vue d'ensemble

Comment un ordinateur peut-il reconnaître un chiffre manuscrit, filtrer un courriel indésirable, ou dire si une tumeur est bénigne ou maligne ? Une des idées les plus simples et les plus efficaces tient en une phrase : « dis-moi qui sont tes voisins, je te dirai qui tu es ». C'est le principe des k plus proches voisins (k-NN, pour k-nearest neighbors). Dans ce chapitre, on part d'exemples déjà étiquetés, on mesure des distances, on vote, et on obtient un classifieur. Puis on apprend à mesurer sa qualité avec la matrice de confusion.

Au programme. On se place en apprentissage supervisé : on dispose d'un jeu de données où chaque exemple porte déjà son étiquette (sa classe), et on veut prédire la classe d'un nouvel exemple. On étudie l'algorithme des k plus proches voisins comme méthode de classification, la distance euclidienne comme mesure de proximité, le rôle du paramètre

k

, le coût d'une prédiction, et l'évaluation d'un classifieur binaire par la matrice de confusion et le taux de bonnes prédictions.

Prérequis

Représenter des données par des listes / tableaux (un point de dimension $p$ est une liste de $p$ nombres).
Trier une liste (par insertion ou sélection) — ici on trie des exemples par distance croissante.
Complexité temporelle : savoir compter les opérations d'une boucle et raisonner en $O (n)$ .
Bases de Python : boucles for, listes, fonctions, dictionnaires.

🎯 Accompagnement Majorant

Le déclic « apprentissage » en une séance. Beaucoup d'élèves confondent « entraînement » et « prédiction », ou récitent k-NN sans savoir tracer un vote. Nos mentors alumni X · Centrale · Mines te font coder et exécuter l'algorithme à la main, jusqu'au réflexe d'oral.

Trouver un mentor →

Jeu de données étiqueté et classification

En apprentissage supervisé, on part d'un ensemble d'exemples dont on connaît déjà la réponse. Chaque exemple est un couple : un point (le vecteur de ses caractéristiques, ou features) et une étiquette (sa classe). L'ensemble de ces exemples s'appelle le jeu d'entraînement.

Définition 1.1 — Classification supervisée

On dispose d'un jeu d'entraînement de $n$ exemples $((x^{(1)}, y^{(1)}), \dots, (x^{(n)}, y^{(n)}))$ , où chaque $x^{(i)} \in R^{p}$ est un point de dimension $p$ et chaque $y^{(i)}$ appartient à un ensemble fini de classes. Classer un nouveau point $x$ , c'est lui attribuer une classe $\overset{y}{^}$ à partir de ce jeu d'entraînement.

Quand l'ensemble des classes possibles a exactement deux éléments (par exemple malade / sain, spam / légitime), on parle de classification binaire. Voici un petit jeu de données à $p = 2$ caractéristiques (donc des points du plan), avec deux classes « rouge » et « bleu », qui servira de fil rouge :

# Chaque exemple = (point, classe). Ici point = (abscisse, ordonnee).
train = [
    ((1, 2), "rouge"),
    ((2, 4), "rouge"),
    ((5, 5), "bleu"),
    ((4, 3), "bleu"),
    ((0, 0), "rouge"),
]
x = (3, 3)   # nouveau point, de classe INCONNUE : c'est lui qu'on veut classer

🔍 Décryptage ligne par ligne

train = [ ... ]une liste de

n = 5

exemples. Chaque élément est un couple (point, classe) : Python autorise un tuple dont le premier membre est lui-même un tuple.

((1, 2), "rouge")l'exemple dont le point est

(1, 2)

et l'étiquette est la chaîne "rouge". Le point est un couple de nombres, la classe est connue.

x = (3, 3)le point à classer. On ne lui donne PAS d'étiquette : l'algorithme doit la deviner à partir de train.

📝 Vocabulaire. On dit qu'un modèle est « entraîné » sur train. Pour k-NN, l'entraînement est trivial : on se contente de mémoriser le jeu d'entraînement. Tout le travail a lieu au moment de la prédiction. C'est un exemple d'apprentissage dit « paresseux » (lazy).

Mesurer la proximité : la distance euclidienne

Pour dire quels exemples sont « proches » du point à classer, il faut une notion de distance. En dimension quelconque, la plus courante est la distance euclidienne, généralisation directe du théorème de Pythagore.

Définition 2.1 — Distance euclidienne

Pour deux points $p = (p_{1}, \dots, p_{d})$ et $q = (q_{1}, \dots, q_{d})$ de $R^{d}$ , la distance euclidienne est $dist (p, q) = i = 1 \sum d (p_{i} - q_{i})^{2} .$ En dimension 2 : $dist ((p_{1}, p_{2}), (q_{1}, q_{2})) = (p_{1} - q_{1})^{2} + (p_{2} - q_{2})^{2}$ .

import math

def distance(p, q):
    s = 0
    for i in range(len(p)):        # i parcourt chaque coordonnee
        s += (p[i] - q[i]) ** 2    # on cumule les carres des ecarts
    return math.sqrt(s)            # racine de la somme

🔍 Décryptage ligne par ligne

def distance(p, q):on définit une fonction qui prend deux points p et q (deux listes/tuples de même longueur

d

) et rend un nombre.

s = 0accumulateur : il contiendra la somme des carrés des écarts

\sum_{i} (p_{i} - q_{i})^{2}

. On l'initialise à 0 AVANT la boucle.

for i in range(len(p)):i prend les valeurs

0, 1, \dots, d - 1

: on traite chaque coordonnée. len(p) est la dimension

d

, ce qui rend la fonction valable en dimension quelconque.

s += (p[i] - q[i]) ** 2on ajoute à s le carré de l'écart sur la coordonnée

i

. **2 est l'élévation au carré, ce qui rend l'écart positif et pénalise davantage les grands écarts.

return math.sqrt(s)on renvoie la racine carrée de la somme : c'est bien

\sum_{i} (p_{i} - q_{i})^{2}

. Sans la racine, on aurait la distance « au carré ».

📝 Pour comparer des distances (savoir laquelle est la plus petite), la racine carrée est facultative : elle est croissante, donc elle ne change pas l'ordre. On peut travailler sur la distance au carré pour gagner du temps. Mais pour afficher une vraie distance, on la garde.

💡 Exemple.

dist ((3, 3), (4, 3)) = (3 - 4)^{2} + (3 - 3)^{2} = 1 + 0 = 1

. Et

dist ((3, 3), (2, 4)) = 1 + 1 = 2 \approx 1, 414

L'algorithme des k plus proches voisins

Définition 3.1 — k plus proches voisins (k-NN)

Pour classer un point $x$ avec un entier $k \geq 1$ fixé :

calculer la distance de $x$ à chacun des $n$ points d'entraînement ;
retenir les $k$ exemples les plus proches (les $k$ plus petites distances) ;
renvoyer la classe majoritaire parmi ces $k$ voisins.

La traduction en Python suit exactement ces trois étapes :

from collections import Counter

def knn(train, x, k):
    dists = []
    for point, classe in train:          # (1) distance a chaque exemple
        d = distance(x, point)
        dists.append((d, classe))
    dists.sort()                         # (2) tri par distance croissante
    voisins = dists[:k]                  #     on garde les k premiers
    classes = [c for (d, c) in voisins]  #     leurs etiquettes
    comptes = Counter(classes)           # (3) on compte chaque classe
    return comptes.most_common(1)[0][0]  #     la classe la plus frequente

🔍 Décryptage ligne par ligne

dists = []liste qui recevra un couple (distance, classe) par exemple d'entraînement.

for point, classe in train:on parcourt les exemples. Le dépaquetage point, classe sépare directement le point et son étiquette (car chaque élément est un couple).

d = distance(x, point)distance de

x

au point courant. C'est ici que se fait tout le calcul : une distance par exemple.

dists.append((d, classe))on stocke la distance avec la classe, pour ne pas perdre l'étiquette quand on triera.

dists.sort()trie la liste de couples. Python compare d'abord le premier membre (la distance) : on obtient les exemples du plus proche au plus lointain.

voisins = dists[:k]tranche des

k

premiers éléments : les

k

plus proches voisins.

classes = [c for (d, c) in voisins]on extrait uniquement les étiquettes des

k

voisins (on jette les distances).

comptes = Counter(classes)Counter construit un dictionnaire {classe : nombre d'occurrences} : c'est le décompte des votes.

comptes.most_common(1)[0][0]most_common(1) rend la liste [(classe_gagnante, votes)] ; [0][0] en extrait la classe majoritaire, qu'on renvoie.

Déroulé pas à pas sur l'exemple

On classe $x = (3, 3)$ avec $k = 3$ . On calcule d'abord les $n = 5$ distances, puis on trie, puis on vote sur les 3 premiers.

Étape 1-2 : distances de $x = (3, 3)$ à chaque exemple, puis tri croissant
Rang après tri	Point	Classe	Distance à $x$	Dans les $k = 3$ ?
1	(4, 3)	bleu	$1 = 1, 000$	✓ voisin
2	(2, 4)	rouge	$2 \approx 1, 414$	✓ voisin
3	(1, 2)	rouge	$5 \approx 2, 236$	✓ voisin
4	(5, 5)	bleu	$8 \approx 2, 828$	—
5	(0, 0)	rouge	$18 \approx 4, 243$	—

Étape 3 : vote majoritaire parmi les $k = 3$ voisins
Classe	Votes parmi les 3 voisins	Résultat
rouge	2 (points (2,4) et (1,2))	majorité ✓ → prédiction : rouge
bleu	1 (point (4,3))	—

Bilan : le voisin le plus proche est bleu, mais les deux suivants sont rouges. Avec $k = 3$ , la majorité l'emporte : $\overset{y}{^} =$ rouge. On note au passage que $k = 1$ aurait donné bleu (le seul voisin retenu) : le choix de $k$ change la réponse.

⚠ Piège. Le vote porte sur la classe des voisins, jamais sur leur distance. On ne fait PAS la moyenne des distances : on compte combien de voisins portent chaque étiquette. Confondre les deux est l'erreur classique.

📐 Méthode d'oral. Pour dérouler k-NN à la main : (1) dresse le tableau des

n

distances ; (2) trie mentalement en repérant les

k

plus petites (inutile de tout trier, un tri partiel suffit) ; (3) fais un bâton par classe sur ces

k

voisins ; (4) annonce la classe qui a le plus de bâtons.

Le rôle du paramètre k

Le nombre $k$ de voisins consultés est un hyperparamètre : on le fixe avant de prédire, il n'est pas « appris ». Son réglage change complètement le comportement du classifieur.

$k$ petit (ex. $k = 1$ ) : la prédiction ne dépend que du voisin le plus proche. Le modèle colle aux données, mais devient sensible au bruit : un seul exemple mal étiqueté ou aberrant à côté de $x$ fait basculer la réponse.
$k$ grand : on moyenne sur beaucoup de voisins, la frontière entre classes devient lisse et robuste au bruit. Mais si $k$ est trop grand, on consulte des points lointains, peu pertinents, et à l'extrême ( $k = n$ ) on renvoie toujours la classe majoritaire globale, quel que soit $x$ .
Parité de $k$ : en classification binaire, on choisit $k$ impair pour éviter les égalités de votes (par ex. 2 contre 2 avec $k = 4$ ), qui rendraient la classe majoritaire ambiguë.

⚠ Piège. « Plus

k

est grand, mieux c'est » est FAUX. Il existe un

k

intermédiaire optimal : trop petit on sur-réagit au bruit, trop grand on efface les détails utiles de la frontière. On règle

k

en testant plusieurs valeurs et en gardant celle qui donne les meilleures prédictions sur des données de test.

💡 Exemple. Sur notre jeu,

x = (3, 3)

est prédit bleu avec

k = 1

mais rouge avec

k = 3

. Le voisin bleu le plus proche est isolé ; en élargissant à 3 voisins, l'environnement majoritairement rouge reprend le dessus.

Coût d'une prédiction

Combien coûte une prédiction ? Pour classer un seul point $x$ sur un jeu de $n$ exemples :

on calcule $n$ distances, chacune en $O (p)$ opérations (une soustraction, un carré, une addition par coordonnée) : coût $O (n p)$ ;
on cherche les $k$ plus petites : un tri complet coûte $O (n lo g n)$ , mais un simple parcours suffit à extraire les $k$ plus proches ;
le vote sur $k$ voisins coûte $O (k)$ , négligeable devant le reste.

À dimension $p$ fixée, le coût dominant est le calcul des $n$ distances : chaque prédiction est en $O (n)$ . C'est le point faible de k-NN : il n'y a pas de phase d'entraînement coûteuse, mais chaque prédiction relit tout le jeu d'entraînement. Sur un très grand jeu, prédire devient lent.

📝 À comparer avec des modèles qui, eux, passent du temps à s'entraîner une fois, puis prédisent très vite. k-NN fait l'inverse : entraînement gratuit, prédiction coûteuse.

Évaluer un classifieur : la matrice de confusion

Une fois un classifieur construit, il faut mesurer sa qualité. On le teste sur des exemples dont on connaît la vraie classe (le jeu de test), et on compare la classe prédite à la classe réelle. Pour un classifieur binaire, on choisit une classe « positive » (par ex. malade) et une classe « négative » (sain), et on range chaque exemple de test dans l'une de quatre cases.

Définition 4.1 — Matrice de confusion (binaire)

C'est un tableau $2 \times 2$ qui croise la classe réelle et la classe prédite :

VP (vrais positifs) : réellement positifs, prédits positifs ;
FN (faux négatifs) : réellement positifs, prédits négatifs (on les a « ratés ») ;
FP (faux positifs) : réellement négatifs, prédits positifs (fausse alerte) ;
VN (vrais négatifs) : réellement négatifs, prédits négatifs.

Les prédictions correctes sont sur la diagonale (VP et VN) ; les erreurs sont hors diagonale (FP et FN).

Exemple : dépistage sur 100 patients (positif = malade)
	Prédit positif	Prédit négatif	Total réel
Réel positif (malade)	VP = 40	FN = 10	50
Réel négatif (sain)	FP = 5	VN = 45	50
Total prédit	45	55	100

Définition 4.2 — Taux de bonnes prédictions et taux d'erreur

Le taux de bonnes prédictions (ou exactitude, accuracy) est la proportion d'exemples correctement classés : $taux de bonnes pr \overset{e}{ˊ} dictions = \frac{V P + V N}{V P + V N + F P + F N} .$ Le taux d'erreur est son complément : $\frac{F P + F N}{total} = 1 - taux de bonnes pr \overset{e}{ˊ} dictions$ .

Sur l'exemple : $V P + V N = 40 + 45 = 85$ bonnes prédictions sur $100$ , donc

$taux de bonnes pr \overset{e}{ˊ} dictions = \frac{40 + 45}{100} = \frac{85}{100} = 0, 85 = 85%, taux d’erreur = \frac{5 + 10}{100} = 0, 15 = 15%.$

def taux_bonnes_predictions(VP, FP, VN, FN):
    total = VP + FP + VN + FN     # nombre total d'exemples testes
    return (VP + VN) / total      # proportion sur la diagonale

print(taux_bonnes_predictions(40, 5, 45, 10))   # -> 0.85

🔍 Décryptage ligne par ligne

def taux_bonnes_predictions(VP, FP, VN, FN):on passe les quatre cases de la matrice de confusion. L'ordre des arguments est une convention à fixer une fois pour toutes.

total = VP + FP + VN + FNsomme des quatre cases = nombre total d'exemples de test. C'est le dénominateur.

return (VP + VN) / totalnumérateur = les deux cases correctes (diagonale). La division donne une proportion entre 0 et 1. Le / est la division flottante en Python 3.

print( ... ) # -> 0.85vérification : avec (VP,FP,VN,FN)=(40,5,45,10), on obtient bien

85/100 = 0, 85

⚠ Piège. Le taux de bonnes prédictions seul peut tromper si les classes sont déséquilibrées. Si 99 % des exemples sont négatifs, un classifieur qui répond « négatif » tout le temps atteint 99 % d'exactitude tout en ne détectant AUCUN positif (FN énorme). La matrice de confusion, elle, révèle immédiatement ce défaut : la ligne des positifs est presque vide de VP.

🎯 Accompagnement Majorant

VP, FP, VN, FN sans jamais se tromper. L'inversion faux positif / faux négatif coûte des points chaque année. Nos mentors alumni X · Centrale · Mines te donnent la grille mentale « vrai/faux = correct ou non, positif/négatif = ce qu'on a prédit » et te font enchaîner les matrices en autonomie.

Trouver un mentor →

Exercices corrigés

Exo 1Distance et voisin le plus procheFacile

On considère les points $A = (1, 1)$ , $B = (4, 5)$ et le point à classer $x = (1, 4)$ . Calcule $dist (x, A)$ et $dist (x, B)$ , puis dis lequel de $A$ ou $B$ est le plus proche de $x$ .

Voir la correction détaillée

dist (x, A) = (1 - 1)^{2} + (4 - 1)^{2} = 0 + 9 = 9 = 3

dist (x, B) = (1 - 4)^{2} + (4 - 5)^{2} = 9 + 1 = 10 \approx 3, 162

Comme

3 < 10

, le point le plus proche de

x

est

A

. Avec

k = 1

x

recevrait donc la classe de

A

Exo 2Dérouler k-NN à la mainIntermédiaire

Jeu d'entraînement : $(0, 0) \to$ A, $(1, 0) \to$ A, $(0, 1) \to$ B, $(3, 3) \to$ B, $(4, 4) \to$ B. On classe $y = (1, 1)$ . Donne la prédiction pour $k = 1$ , puis pour $k = 3$ . Le résultat change-t-il ?

Voir la correction détaillée

Distances de

y = (1, 1)

: à

(0, 0)

2 \approx 1, 414

(A) ; à

(1, 0)

0 + 1 = 1

(A) ; à

(0, 1)

1 + 0 = 1

(B) ; à

(3, 3)

4 + 4 = 8 \approx 2, 828

(B) ; à

(4, 4)

9 + 9 = 18 \approx 4, 243

(B).

Tri croissant :

(1, 0) 1, 00 A

;

(0, 1) 1, 00 B

;

(0, 0) 1, 41 A

;

(3, 3) 2, 83 B

;

(4, 4) 4, 24 B

. (En cas d'égalité de distance, le tri de Python conserve les deux ; ici (1,0) et (0,1) sont à égalité, l'ordre exact entre eux n'affecte pas le vote sur

k = 3

k = 1

: le plus proche est

(1, 0)

, classe A.

k = 3

: les 3 plus proches sont

(1, 0) A

(0, 1) B

(0, 0) A

→ votes : A = 2, B = 1 → majorité A.

Ici la prédiction reste A dans les deux cas : elle ne change pas.

Exo 3Lire une matrice de confusionDifficile

Un classifieur de courriels (positif = « spam ») est testé sur 200 messages. Il donne : $V P = 60$ , $F N = 15$ , $F P = 25$ , $V N = 100$ . (a) Vérifie que le total est cohérent. (b) Calcule le taux de bonnes prédictions et le taux d'erreur. (c) Un courriel légitime classé « spam » est-il un FP ou un FN ? Pourquoi est-ce le plus gênant ici ?

Voir la correction détaillée

(a) Total

= V P + F N + F P + V N = 60 + 15 + 25 + 100 = 200

. Cohérent avec les 200 messages testés.

(b) Bonnes prédictions

= V P + V N = 60 + 100 = 160

. Taux

= \frac{160}{200} = 0, 80 = 80%

. Taux d'erreur

= \frac{F P + F N}{200} = \frac{25 + 15}{200} = \frac{40}{200} = 0, 20 = 20%

(c) Un courriel légitime (réel négatif) prédit « spam » (prédit positif) est un faux positif (FP). C'est le plus gênant : on met à la corbeille un vrai message, l'utilisateur peut manquer un courriel important — alors qu'un FN (spam laissé passer) n'est qu'une gêne mineure.

Récap final — Ce qu'il faut absolument retenir

k-NN classe un point par vote de ses voisins ; la matrice de confusion mesure la qualité du classifieur. Voici les réflexes à avoir avant l'oral.

Sais-tu expliquer ce qu'est un jeu d'entraînement étiqueté et la différence entre entraînement et prédiction en apprentissage supervisé ?
Sais-tu écrire et décrypter la fonction de distance euclidienne en dimension quelconque $\sum_{i} (p_{i} - q_{i})^{2}$ ?
Sais-tu énoncer les 3 étapes de k-NN (distances à tous les points, garder les $k$ plus proches, classe majoritaire) ?
Sais-tu dérouler k-NN à la main sur un petit exemple 2D (tableau des distances, tri, vote) ?
Sais-tu expliquer l'effet de $k$ (petit = sensible au bruit, grand = lisse), et pourquoi on prend $k$ impair en binaire ?
Sais-tu justifier que chaque prédiction coûte $O (n)$ et que l'entraînement de k-NN est quasi gratuit ?
Sais-tu définir VP, FP, VN, FN sans les confondre, et placer une prédiction dans la bonne case ?
Sais-tu calculer le taux de bonnes prédictions $(V P + V N) / total$ et le taux d'erreur ?
Sais-tu expliquer pourquoi l'exactitude seule trompe sur des classes déséquilibrées ?

Vue d'ensemble

Prérequis

Jeu de données étiqueté et classification

Mesurer la proximité : la distance euclidienne

L'algorithme des k plus proches voisins

Déroulé pas à pas sur l'exemple

Le rôle du paramètre k

Coût d'une prédiction

Évaluer un classifieur : la matrice de confusion

Exercices corrigés

Récap final — Ce qu'il faut absolument retenir

Débloque la fiche complète

Quiz — k plus proches voisins

Fiches associées

Recherche par dichotomie

Variables, types et affectations

Conditions et booléens

Boucles for et while

Fonctions : paramètres et valeurs de retour

Listes et chaînes de caractères

Tu veux aller plus loin sur ce chapitre ?