Comprendre le KNN : l'algorithme des k plus proches voisins
Un tutoriel simple et complet pour comprendre le KNN, savoir comment il fonctionne, comment choisir k et comment l'implémenter en Python.
Comprendre le KNN
Introduction
Le KNN, pour k-nearest neighbors ou k plus proches voisins, est l'un des algorithmes les plus simples à comprendre en machine learning.
Son idée est très intuitive : pour prédire la classe d'un nouvel élément, on regarde les éléments les plus proches autour de lui, puis on laisse la majorité décider.
Cet algorithme est particulièrement utile pour apprendre les bases du machine learning, car il ne demande pas un modèle compliqué pour commencer.
Ce que vous allez apprendre
À la fin de ce tutoriel, vous saurez :
- comprendre le principe du KNN ;
- savoir quand utiliser cet algorithme ;
- comprendre ce qu'est la distance entre deux points ;
- choisir une valeur de
k; - écrire un KNN simple en Python ;
- distinguer classification et régression avec KNN ;
- éviter les erreurs les plus fréquentes.
1. Qu'est-ce que le KNN ?
Le KNN est un algorithme supervisé.
Cela veut dire qu'on dispose déjà d'exemples connus, avec leurs bonnes réponses.
Ensuite, quand on reçoit un nouvel exemple, on le compare aux exemples déjà connus pour deviner sa classe.
Exemple simple
Imaginons que vous voulez classer des fruits.
Vous avez déjà des exemples :
- des pommes ;
- des poires ;
- des bananes.
Si un nouveau fruit arrive, le KNN regarde les fruits les plus proches de lui selon certains critères :
- taille ;
- poids ;
- couleur ;
- texture.
Si les voisins les plus proches sont majoritairement des pommes, alors le nouvel objet sera classé comme une pomme.
2. L'idée intuitive
Le KNN repose sur une idée très humaine :
on compare un nouvel élément aux éléments déjà connus, puis on choisit la catégorie la plus représentée parmi ses voisins les plus proches.
C'est simple, facile à comprendre et très utile pour commencer à apprendre le machine learning.
3. Pourquoi on parle de "voisins" ?
En machine learning, les données peuvent être représentées sous forme de points.
Par exemple, chaque point peut avoir deux caractéristiques :
- le poids ;
- la taille.
Dans ce cas, chaque point devient un élément dans un espace à deux dimensions.
Le KNN cherche les points les plus proches du nouveau point à classer.
4. La distance entre deux points
Pour savoir quels sont les voisins les plus proches, il faut mesurer la distance.
La distance la plus connue est la distance euclidienne.
Distance euclidienne
Si on a deux points (x1, y1) et (x2, y2), la distance euclidienne se calcule ainsi :
racine((x2 - x1)^2 + (y2 - y1)^2)
En Python :
import math
def euclidean_distance(a, b):
return math.sqrt((a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2)
Pourquoi la distance est importante
Sans distance, on ne peut pas dire quels sont les voisins les plus proches.
Le KNN a donc besoin d'une mesure pour comparer les exemples entre eux.
5. Que signifie k ?
Le k représente le nombre de voisins qu'on prend en compte.
Exemple
Si k = 3, on regarde les 3 points les plus proches.
Si k = 5, on regarde les 5 points les plus proches.
Ensuite, on choisit la classe qui revient le plus souvent.
Petit conseil
- un
ktrop petit peut rendre l'algorithme sensible au bruit ; - un
ktrop grand peut diluer l'information locale.
Il faut donc trouver un équilibre.
6. Classification et régression
Le KNN peut servir à deux choses différentes.
KNN pour la classification
On prédit une catégorie.
Exemples :
- spam ou non spam ;
- chien ou chat ;
- malade ou sain.
KNN pour la régression
On prédit une valeur numérique.
Exemples :
- le prix d'une maison ;
- une note ;
- une estimation de température.
Dans ce tutoriel, nous allons surtout nous concentrer sur la classification, car c'est le cas le plus simple pour comprendre le principe.
7. Exemple de données
Imaginons un petit jeu de données :
training_data = [
((1, 1), "Rouge"),
((2, 1), "Rouge"),
((2, 2), "Rouge"),
((6, 5), "Bleu"),
((7, 5), "Bleu"),
((8, 6), "Bleu"),
]
Chaque point possède :
- des coordonnées ;
- une étiquette, ici
RougeouBleu.
Si on veut classer un nouveau point, on va comparer sa position aux points déjà connus.
8. Implémenter un KNN simple en Python
Voici une version complète et facile à lire.
import math
from collections import Counter
def euclidean_distance(a, b):
return math.sqrt((a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2)
def knn_classify(training_data, point, k=3):
distances = []
for features, label in training_data:
distance = euclidean_distance(features, point)
distances.append((distance, label))
distances.sort(key=lambda item: item[0])
nearest_neighbors = distances[:k]
labels = [label for _, label in nearest_neighbors]
most_common = Counter(labels).most_common(1)
return most_common[0][0]
Explication ligne par ligne
distances = []
On va stocker toutes les distances calculées.
for features, label in training_data
On parcourt chaque exemple connu.
distance = euclidean_distance(features, point)
On mesure à quel point l'exemple est proche du nouveau point.
distances.sort(key=lambda item: item[0])
On trie les distances du plus petit au plus grand.
nearest_neighbors = distances[:k]
On garde seulement les k plus proches.
Counter(labels).most_common(1)
On compte quelle classe apparaît le plus souvent.
9. Tester l'algorithme
training_data = [
((1, 1), "Rouge"),
((2, 1), "Rouge"),
((2, 2), "Rouge"),
((6, 5), "Bleu"),
((7, 5), "Bleu"),
((8, 6), "Bleu"),
]
print(knn_classify(training_data, (2, 1.5), k=3))
print(knn_classify(training_data, (7, 5.5), k=3))
Résultat attendu :
Rouge
Bleu
10. Pourquoi ce code est intéressant
Ce code n'est pas optimisé pour de très grandes bases de données, mais il est excellent pour comprendre la logique du KNN.
Il montre clairement :
- le calcul des distances ;
- le tri des voisins ;
- le vote majoritaire.
11. Les limites du KNN
Le KNN est simple, mais il a aussi des limites.
1. Il peut devenir lent
Pour chaque nouvelle prédiction, il doit comparer le point avec beaucoup d'exemples.
2. Il dépend des données
Si les données d'entraînement sont mal choisies ou bruitées, les prédictions seront moins bonnes.
3. Il dépend de l'échelle des variables
Si une variable varie entre 0 et 1 et qu'une autre varie entre 0 et 10 000, la plus grande peut dominer la distance.
C'est pour cela qu'on normalise souvent les données avant d'utiliser KNN.
12. La normalisation
La normalisation consiste à mettre les variables sur une échelle plus comparable.
Par exemple :
- poids ;
- taille ;
- âge.
Si l'une des variables a des valeurs très grandes, elle risque d'écraser les autres dans le calcul de distance.
En pratique, c'est une étape très importante.
13. Comment choisir k ?
Il n'existe pas une valeur magique.
On choisit souvent k en testant plusieurs valeurs et en observant les résultats.
Règles simples
k = 1est très sensible aux cas isolés ;- un petit
kcapture les détails locaux ; - un grand
klisse davantage les résultats.
En général, on cherche une valeur équilibrée qui fonctionne bien sur les données réelles.
14. Variante avec d'autres distances
La distance euclidienne n'est pas la seule possibilité.
On peut aussi utiliser :
- la distance de Manhattan ;
- la distance de Minkowski ;
- d'autres mesures selon le contexte.
Le choix dépend du type de données et du problème à résoudre.
15. Erreurs fréquentes
Oublier de normaliser les données
C'est une erreur très courante avec KNN.
Choisir un k trop petit
Le modèle devient trop sensible aux exceptions.
Choisir un k trop grand
Le modèle perd en précision locale.
Mélanger classification et régression
Le vote majoritaire sert à la classification. Pour la régression, on prend plutôt une moyenne des valeurs voisines.
16. KNN en résumé
Le KNN est un algorithme simple, intuitif et très pratique pour apprendre les bases du machine learning.
À retenir :
- on compare un nouvel élément à ses voisins ;
- on utilise une mesure de distance ;
- on choisit les
kplus proches ; - on prend la majorité pour classer ;
- il faut souvent normaliser les données.
Exercices
Exercice 1
Implémentez la fonction euclidean_distance.
Exercice 2
Ajoutez un troisième point à la base d'entraînement et testez une nouvelle prédiction.
Exercice 3
Modifiez le code pour afficher les voisins les plus proches avant de retourner la classe.
Exercice 4
Essayez avec k = 1, k = 3 et k = 5.
Corrigés
Correction exercice 1
def euclidean_distance(a, b):
return math.sqrt((a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2)
Correction exercice 4
print(knn_classify(training_data, (2, 1.5), k=1))
print(knn_classify(training_data, (2, 1.5), k=3))
print(knn_classify(training_data, (2, 1.5), k=5))
Prochaine étape
Une fois le KNN compris, vous pouvez explorer d'autres algorithmes de machine learning plus avancés, comme les arbres de décision ou la régression logistique.