k plus proches voisins
k-nearest neighbors
(KNN)
K. Nassiri
k plus proches voisins (KNN) Apprentissage supervisé : Classification
L'algorithme des k plus proches voisins (KNN) est une technique simple et populaire en ML
Il est utilisé pour :
Classification : prédire une catégorie (ex : « ce fruit est une pomme ou une orange ? »)
Régression : prédire une valeur numérique (ex : « ce logement coûte 250 000 MAD »)
Principe général
L’algorithme consiste à :
o Identifier les K points de données les plus proches d’une nouvelle observation
o Utiliser ces voisins pour faire une prédiction
Prédiction en KNN
En classification :
o On choisit la classe majoritaire parmi les K voisins
En régression :
o On calcule la moyenne des valeurs des K voisins
k plus proches voisins (KNN) Apprentissage supervisé : Classification
Classifie les données en fonction de leur similarité avec les points de données voisins.
Utilise des mesures de distance comme la distance euclidienne pour trouver les
voisins les plus proches.
Comme KNN ne fait aucune hypothèse sur la distribution des données sous-jacentes,
il s'agit d'une méthode d'apprentissage non paramétrique et basée sur les instances.
Sa force :
KNN est un algorithme de type "lazy learner" qui n'apprend pas explicitement un
modèle
Il stocke simplement les données d'entraînement.
Pour faire une prédiction :
il cherche les K points les plus proches dans l'espace des données (les
voisins) et fait une prédiction en se basant sur ces voisins.
k plus proches voisins (KNN) Apprentissage supervisé : Classification
Exemple
Considérons deux caractéristiques, à savoir la catégorie A et la catégorie B :
Les étoiles représentent la catégorie A et les rectangles représentent la catégorie B.
La nouvelle donnée vérifie ses voisines Étant donné que la majorité de ses
les plus proches (calcul de la distance voisins les plus proches sont des
entre le nouveau point et les autres rectangles (catégorie B), KNN prédit que
points des deux classes. la nouvelle observation appartient à la
L'algorithme KNN attribue une catégorie en fonction de la majorité des catégorie B.
points voisins.
L'image illustre comment KNN prédit la catégorie d’une nouvelle donnée à
partir de ses voisines les plus proches.
L'algorithme KNN fonctionne en utilisant la proximité et le vote majoritaire pour effectuer des prédictions.
k plus proches voisins (KNN) Apprentissage supervisé : Classification
Rappel simple
Point dans un espace :
Un individu (ex : une maison) peut être représenté par des coordonnées (ex : nombre
de pièces, superficie). Chaque caractéristique est une dimension.
Distance :
La longueur du segment qui relie deux points. Plus elle est petite, plus les points sont
« proches ».
K:
C'est un nombre entier (1, 3, 5...). Il représente le nombre de voisins que l'on va
consulter..
Voisin :
Un point de donnée existant dans notre base d'entraînement qui est géométriquement
proche du nouveau point.
k plus proches voisins (KNN) Apprentissage supervisé : Classification
Choix de la Métrique de distance dans KNN
Rôle des métriques de distance
Dans l’algorithme KNN, les métriques de distance permettent de :
o Identifier les voisins les plus proches
o Mesurer la similarité entre les données
Ces distances sont essentielles pour :
o la classification
o la régression
k plus proches voisins (KNN) Apprentissage supervisé : Classification
Choix de la Métrique de distance dans KNN
Distance Euclidienne
La distance euclidienne correspond à la distance directe (ligne droite) entre deux
points dans un plan ou dans l’espace.
Pour deux points A = (x₁, y₁) et B = (x₂, y₂) en 2D :
En général, pour n dimensions (caractéristiques) :
Le carré garantit que la distance est toujours positive et donne plus de poids aux grands écarts. La racine
carrée ramène le résultat à l'unité de mesure d'origine.
k plus proches voisins (KNN) Apprentissage supervisé : Classification
Choix de la Métrique de distance dans KNN
Distance de Manhattan
La distance de Manhattan mesure la distance en suivant uniquement des axes
horizontaux et verticaux
Il s’agit la distance totale que vous parcourriez si vous ne pouviez vous
déplacer que le long de lignes horizontales et verticales, comme dans un plan
en damier ou les rues d'une ville.
On l'appelle aussi « distance de taxi », car un taxi ne peut circuler que sur les rues
quadrillées d'une ville.
k plus proches voisins (KNN) Apprentissage supervisé : Classification
Choix de la Métrique de distance dans KNN
Distance de Minkowski
La distance de Minkowski est une formule générale qui englobe plusieurs
distances (les distances euclidienne et de Manhattan comme cas particuliers)
o Lorsque p=2, elle se réduit à la formule de la distance euclidienne,
o lorsque p=1, elle se réduit à celle de la distance de Manhattan.
La distance de Minkowski est par essence une formule flexible qui peut représenter soit
la distance euclidienne, soit la distance de Manhattan, selon la valeur de p.
k plus proches voisins (KNN) Apprentissage supervisé : Classification
Choix de la Métrique de distance dans KNN
Distance de Hamming
Pour des données catégorielles, on utilise souvent la distance de Hamming (nombre
de caractéristiques différentes).
La distance de Hamming compte le nombre de positions (caractéristiques) pour
lesquelles deux exemples diffèrent.
Pour deux vecteurs de caractéristiques catégorielles A et B de longueur n :
Hamming
où vaut 1 si la condition est vraie, 0 sinon.
o En français : on compare case par case, on ajoute 1 à chaque fois que les valeurs
sont différentes.
k plus proches voisins (KNN) Apprentissage supervisé : Classification
Le principe général
KNN est un algorithme non paramétrique (il ne suppose pas une forme particulière pour les données)
et paresseux (pas de phase d’entraînement : il stocke simplement tous les exemples).
Fonctionnement en 3 étapes :
1. Sélection de la valeur optimale de K
K représente le nombre de voisins les plus proches pris en compte pour la prédiction.
2. Stockage :
On garde en mémoire tous les points d’entraînement avec leurs étiquettes (ou
valeurs).
3. Requête : Pour un nouveau point x_new dont on veut la prédiction :
Calculer la distance entre x_new et chaque point d’entraînement.
Sélectionner les K points les plus proches (plus petites distances).
4. Décision (Vote pour la classification ou calcul de la moyenne pour la régression) :
En classification : la classe majoritaire parmi les K voisins (vote majoritaire).
En régression : la moyenne (ou médiane) des valeurs des K voisins.
k plus proches voisins (KNN) Apprentissage supervisé : Classification
Classification
[Link] les distances : Pour un nouveau point, calculer la distance (exple. Euclidienne)
avec tous les points de l'ensemble d'entraînement.
[Link] K voisins : Sélectionner les K points avec les distances les plus petites.
[Link] majoritaire : Pour classer un point de données dans une catégorie comme
« spam » ou « non-spam », l'algorithme KNN examine les K points les plus proches dans
l'ensemble de données. Ces points les plus proches sont appelés voisins. L'algorithme
détermine ensuite à quelle catégorie appartiennent ces voisins et sélectionne celle qui
apparaît le plus souvent. C'est ce qu'on appelle le vote majoritaire.
Régression
[Link] les distances : Même étape que pour la classification.
[Link] K voisins : Même étape que pour la classification.
[Link] des valeurs : l'algorithme recherche toujours les K points les plus proches.
Mais au lieu de voter pour une classe en classification, il calcule la moyenne des valeurs
de ces K voisins. Cette moyenne constitue la valeur prédite pour le nouveau point.
k plus proches voisins (KNN) Apprentissage supervisé : Classification
Ce schéma illustre la classification d'un point de test en fonction de ses voisins les
plus proches. À mesure que le point de test se déplace, l'algorithme identifie les
« k » points de données les plus proches (7 dans ce cas) et lui attribue l'étiquette de
classe majoritaire, soit la classe 2.
k plus proches voisins (KNN) Apprentissage supervisé : Classification
Le paramètre K
K est le nombre de voisins à consulter.
K trop petit (ex : 1) : l’algorithme est très sensible au bruit (surapprentissage). Chaque
point aberrant influence la prédiction.
K trop grand (ex : 100) : l’algorithme devient plus lisse mais risque de sous-apprendre
(les frontières de décision sont trop floues).
Règle empirique :
K = racine carrée du nombre d’exemples, ou un nombre impair pour éviter les égalités
en classification binaire. Cela permet d'éviter les égalités lorsqu'il s'agit de déterminer
la classe la plus fréquente parmi les classes voisines.
k plus proches voisins (KNN) Apprentissage supervisé : Classification
Exemples Pratiques
Cas A : Classification (Prédire une catégorie)
Imaginez que nous classons des fruits selon leur Poids et leur Douceur.
o Point A (Pomme) : (150g, 7/10)
o Point B (Orange) : (170g, 3/10)
o Nouveau fruit X : (160g, 6/10)
Si K=1, l'algorithme calcule la distance entre X et A, puis X et B. Le voisin le plus
proche gagne. X sera classé comme "Pomme".
160 150 6/10 7/10
160 170 6/10 3/10
k plus proches voisins (KNN) Apprentissage supervisé : Classification
Exemples Pratiques
Cas B : Régression (Prédire une valeur numérique)
Imaginons que nous voulons prédire le prix d'un appartement basé sur sa surface.
o Appart 1 : 50m² -> 200 000MAD
o Appart 2 : 55m² -> 210 000MAD
o Cible : 52m²
Avec K=2, l'algorithme prend les deux plus proches (ici 50 et 55) et fait la moyenne de
leurs prix :
200 000 + 210000
Prix prédit = = 205000MAD
2
k plus proches voisins (KNN) Apprentissage supervisé : Classification
Erreurs fréquentes
1) Oublier de normaliser les données :
Si une variable est en kilomètres (1 à 10) et une autre en grammes (100 à
5000), la distance sera dominée par les grammes. Il faut ramener toutes les
valeurs entre 0 et 1.
2) Choisir un K pair en classification :
Si K=2, vous risquez une égalité (1 voix contre 1). Utilisez toujours un
nombre impair pour trancher.
k plus proches voisins (KNN) Apprentissage supervisé : Classification
Mise en œuvre pratique Classification
from [Link] import KNeighborsClassifier
# Créer le modèle KNN
knn = KNeighborsClassifier(n_neighbors=2)
[Link](X_train, y_train)
# Prédiction
y_pred = [Link](X_test)
k plus proches voisins (KNN) Apprentissage supervisé : Classification
Mise en œuvre pratique Régression
from [Link] import KNeighborsRegressor
# Créer le modèle KNN
knn = KNeighborsRegressor(n_neighbors=2)
[Link](X_train, y_train)
# Prédiction
y_pred = [Link](X_test)