L'algorithme des $k$ plus proches voisins ($k$-nearest neighbors, ou KNN) est un algorithme de classification : étant donné un nouvel élément, il prédit sa catégorie en regardant les catégories des $k$ éléments les plus proches dans un jeu de données existant.
Étapes :
Pour mesurer la proximité entre deux points, on utilise la distance euclidienne.
En dimension 2, entre les points $A(x_1 ~; y_1)$ et $B(x_2 ~; y_2)$ : $$ d(A,\; B) = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2} $$
En dimension $n$, entre les points $(a_1,\; a_2,\; …,\; a_n)$ et $(b_1,\; b_2,\; …,\; b_n)$ : $$ d = \sqrt{\sum_{i=1}^{n} (b_i - a_i)^2} $$
Si les caractéristiques n'ont pas la même échelle (par exemple une taille en mètres et un poids en kilogrammes), la caractéristique avec les plus grandes valeurs domine le calcul de distance.
Solution : normaliser chaque caractéristique pour que ses valeurs soient comprises entre 0 et 1 : $$ x_{\text{norm}} = \frac{x - x_{\min}}{x_{\max} - x_{\min}} $$
Cas particulier : si tous les échantillons ont la même valeur pour une caractéristique ($x_{\max} = x_{\min}$), la formule donne une division par zéro. Cette caractéristique n'apporte aucune information pour distinguer les points : le plus propre est de la retirer du jeu de données. Si on la garde, on lui assigne une valeur neutre comme $0{,}5$ (milieu de l'intervalle) plutôt que $0$, qui biaiserait artificiellement vers la borne basse.
| Erreur | Correction | Explication |
|---|---|---|
| Prédire avec $k = 1$ | Utiliser $k \geqslant 3$ (impair) | Avec $k = 1$, une seule donnée aberrante suffit à fausser la prédiction. |
| Ne pas normaliser (taille en cm, poids en kg) | Normaliser entre 0 et 1 | La taille (150-190) dominerait le poids (50-100) dans le calcul de distance. |
| Trier par distance décroissante | Trier par distance croissante | On veut les voisins les plus proches, donc les distances les plus petites. |
| Compter les votes sans gérer l'égalité | Choisir $k$ impair ou ajouter une règle de départage | $k$ impair évite l'égalité uniquement quand il n'y a que deux catégories. Avec trois catégories ou plus, un partage $1{-}1{-}1$ reste possible avec $k = 3$. |
import math
def distance(a, b):
"""Distance euclidienne entre deux points (listes de coordonnées)."""
return math.sqrt(sum((ai - bi) ** 2 for ai, bi in zip(a, b)))
# En 2D
print(distance([1, 2], [4, 6])) # 5.0
# En 3D
print(distance([0, 0, 0], [1, 1, 1])) # 1.732...def knn(donnees, nouveau, k):
"""Prédit la catégorie du point 'nouveau'.
donnees : liste de tuples (coordonnees, categorie)
nouveau : liste de coordonnées
k : nombre de voisins."""
# Étape 1 : calculer les distances
distances = []
for coords, cat in donnees:
d = distance(coords, nouveau)
distances.append((d, cat))
# Étape 2 : trier par distance croissante
distances.sort()
# Étape 3 : sélectionner les k plus proches
voisins = distances[:k]
# Étape 4 : vote majoritaire
decompte = {}
for d, cat in voisins:
decompte[cat] = decompte.get(cat, 0) + 1
# Renvoyer la catégorie la plus fréquente.
# En cas d'égalité, max() renvoie la première clé rencontrée dans le
# dictionnaire, donc le résultat dépend de l'ordre des voisins. Pour
# un code robuste, il faudrait détecter l'égalité et appliquer une
# règle de départage (par exemple, la catégorie du voisin le plus proche).
return max(decompte, key=decompte.get)# Données : (longueur pétale, largeur pétale) -> espèce
fleurs = [
([1.4, 0.2], "setosa"),
([1.3, 0.3], "setosa"),
([4.5, 1.5], "versicolor"),
([4.7, 1.4], "versicolor"),
([5.1, 1.8], "virginica"),
([5.9, 2.1], "virginica"),
]
# Prédire l'espèce d'une nouvelle fleur
nouvelle = [4.6, 1.4]
print(knn(fleurs, nouvelle, k=3)) # "versicolor"def normaliser(donnees):
"""Normalise chaque caractéristique entre 0 et 1."""
n = len(donnees[0][0]) # nombre de caractéristiques
mins = [min(d[0][i] for d in donnees) for i in range(n)]
maxs = [max(d[0][i] for d in donnees) for i in range(n)]
resultat = []
for coords, cat in donnees:
# Si maxs[i] == mins[i], la caractéristique est constante et
# n'apporte aucune info. On assigne 0.5 (valeur neutre) plutôt
# que de diviser par zéro. Mieux : retirer cette caractéristique.
norm = [(coords[i] - mins[i]) / (maxs[i] - mins[i])
if maxs[i] != mins[i] else 0.5
for i in range(n)]
resultat.append((norm, cat))
return resultat, mins, maxsSoit les points $A(1 ~; 3)$, $B(4 ~; 7)$, $C(2 ~; 1)$ et $D(5 ~; 4)$.
Calculs :
Vérification :
import math
A, B, C, D = [1,3], [4,7], [2,1], [5,4]
print(distance(A, B)) # 5.0
print(distance(A, C)) # 2.236...
print(distance(A, D)) # 4.123...On dispose du jeu de données suivant (taille en cm, poids en kg, catégorie) :
| Taille (cm) | Poids (kg) | Catégorie |
|---|---|---|
| 160 | 55 | A |
| 165 | 60 | A |
| 170 | 70 | B |
| 175 | 75 | B |
| 180 | 80 | B |
| 155 | 50 | A |
Distances au point $(168 ~; 65)$ :
distance(a, b) qui calcule la distance euclidienne entre deux points (représentés comme des listes de coordonnées).knn(donnees, nouveau, k) qui prédit la catégorie d'un nouveau point.import math
def distance(a, b):
return math.sqrt(sum((ai - bi) ** 2 for ai, bi in zip(a, b)))
def knn(donnees, nouveau, k):
distances = []
for coords, cat in donnees:
d = distance(coords, nouveau)
distances.append((d, cat))
distances.sort()
voisins = distances[:k]
decompte = {}
for d, cat in voisins:
decompte[cat] = decompte.get(cat, 0) + 1
return max(decompte, key=decompte.get)
# Jeu de données
donnees = [
([160, 55], "A"), ([165, 60], "A"),
([170, 70], "B"), ([175, 75], "B"),
([180, 80], "B"), ([155, 50], "A"),
]
nouveau = [168, 65]
print(knn(donnees, nouveau, k=3)) # "A"
print(knn(donnees, nouveau, k=1)) # "B" (seul voisin : (170,70))
print(knn(donnees, nouveau, k=5)) # "B" (3 B, 2 A)Analyse : avec $k = 1$, le plus proche voisin est $(170, 70)$ de catégorie B. Avec $k = 5$, on inclut trois points B et deux points A, donc la prédiction bascule en B. Le choix de $k$ influence directement le résultat : c'est un hyperparamètre qu'il faut ajuster.
On dispose des données suivantes (revenu en euros, âge en années, catégorie) :
| Revenu | Âge | Catégorie |
|---|---|---|
| 25000 | 30 | X |
| 30000 | 25 | X |
| 80000 | 45 | Y |
| 75000 | 50 | Y |
Sans normalisation, distances au point $(35000, 40)$ :
Les trois plus proches : $(30000, 25)$, $(25000, 30)$, $(75000, 50)$ $\to$ 2 X, 1 Y $\to$ prédiction X.
Normalisation : revenu varie de 25 000 à 80 000 (amplitude 55 000), âge varie de 25 à 50 (amplitude 25).
Distances normalisées :
Les trois plus proches : X (0,44), X (0,61), Y (0,83) $\to$ prédiction X. Même résultat ici, mais les distances sont bien plus équilibrées.