Qu’est ce que l’algorithme KNN ?

L’algorithme des K plus proches voisins ou K-nearest neighbors (kNN) est un algorithme de Machine Learning qui appartient à la classe des algorithmes d’apprentissage supervisé simple et facile à mettre en œuvre qui peut être utilisé pour résoudre les problèmes de classification et de régression. Dans cet article, nous allons revenir sur la définition de cet algorithme, son fonctionnement ainsi qu’une application directe en programmation.

KNN : Définition

L’algorithme des K plus proches voisins ou K-nearest neighbors (KNN) est un algorithme de Machine Learning d’apprentissage supervisé, simple et facile à mettre en œuvre, utilisable pour des tâches de classification comme de régression. Il repose sur la similarité entre exemples : un nouveau point est prédit à partir des K observations les plus proches dans l’espace des caractéristiques.

En apprentissage supervisé, un algorithme reçoit un ensemble de données étiquetées avec des valeurs de sortie correspondantes. Il exploite ces exemples connus pour prédire la sortie de nouvelles observations. Avec KNN, l’idée directrice est : si deux points se ressemblent selon une mesure de distance, leurs sorties devraient être proches. Ces notions sont couramment abordées en formation Data Analyst.

• Étape 1 : choisir K, le nombre de voisins à considérer.
• Étape 2 : mesurer la distance entre l’observation à prédire et toutes les observations d’entraînement.
• Étape 3 : agréger les K voisins les plus proches pour produire la prédiction.

KNN en classification vs régression : quelle différence ?

Tâche	Sortie KNN	Idée d’agrégation
Classification	Une étiquette de classe	Vote majoritaire parmi les K voisins (éventuellement pondéré par la distance)
Régression	Une valeur numérique	Moyenne ou médiane des valeurs des K voisins (éventuellement pondérée par la distance)

En classification, KNN attribue la classe la plus fréquente dans le voisinage du point cible. En régression, il calcule une valeur continue, typiquement la moyenne des sorties des K voisins. Le choix de K influence le compromis biais-variance : un K trop faible rend le modèle sensible au bruit, un K trop élevé lisse excessivement les prédictions.

KNN est-il non paramétrique et “lazy” ?

Oui. KNN est non paramétrique : il ne suppose pas de forme prédéfinie pour la relation entre variables et ne construit pas de modèle explicite à estimer. C’est aussi une méthode à base d’instances dite “lazy learning” : pas d’entraînement coûteux, l’algorithme conserve les données d’apprentissage et effectue le calcul principal au moment de la prédiction en recherchant les voisins les plus proches.

Conséquences : KNN est facile à comprendre et flexible, mais il peut devenir lent et gourmand en mémoire lorsque le volume de données ou le nombre de variables augmente. Il est aussi sensible à l’échelle des caractéristiques, d’où l’intérêt de normaliser les données et de choisir une mesure de distance adaptée au problème.

Comment fonctionne KNN étape par étape ?

L’intuition derrière l’algorithme des K plus proches voisins est simple : pour prédire la classe ou la valeur d’un nouveau point, on mesure sa proximité avec les observations étiquetées, on sélectionne les K plus proches, puis on décide par vote (classification) ou agrégation (régression).

Quelles sont les étapes clés (distance, tri, vote/agrégation) ?

Pipeline minimal attendu, sans code :

1. Choisir K : sélectionnez le nombre K de voisins à considérer. Commencez souvent petit, puis ajustez-le par validation croisée.
2. Préparer et choisir la distance : normalisez les variables si elles n’ont pas la même échelle, puis fixez une métrique (euclidienne, Manhattan, Minkowski, Hamming pour des variables catégorielles).
3. Calculer les distances : du point non classifié aux autres points du jeu d’entraînement.
4. Sélectionner les voisins : triez les points par distance croissante ou conservez directement les K plus proches sans trier toute la liste.
5. Décider :
   - en classification, appliquez un vote majoritaire, ou à majorité relative lorsque plusieurs classes existent.
   - en régression, agrégerez par moyenne ou médiane des K valeurs.
   Optionnel : pondérez les contributions par la distance (les plus proches comptent davantage).
6. Renvoyer la prédiction : étiquette prédite et, si utile, un score de confiance simple (proportion de votes, distance moyenne des voisins). Notre modèle est prêt.

En résumé : Étape 1 Sélectionnez K, Étape 2 Calculez la distance, Étape 3 Prenez les K voisins les plus proches, Étape 4 Comptez les classes, Étape 5 Attribuez la classe majoritaire ou la valeur agrégée, Étape 6 Utilisez le modèle sur de nouvelles données.

Que se passe-t-il en cas d’égalité de vote ?

• Choisir un K impair en classification binaire pour limiter les ex æquo.
• Pondérer par la distance : attribuez à chaque voisin un poids décroissant avec la distance (par exemple 1/(d+ε) ou 1/d²). Les plus proches influencent davantage le résultat.
• Arbitrer par la proximité moyenne : entre classes à égalité, choisissez celle dont les K voisins retenus ont la plus petite distance moyenne au point à prédire.
• Ajuster K : testez K±1 et retenez la valeur validée qui réduit les égalités sans dégrader les performances.
• Règles additionnelles : imposer une classe prioritaire selon le contexte métier, ou recourir à un seuil minimal de majorité et renvoyer « indécis » si le seuil n’est pas atteint.

Quelles distances utiliser avec KNN ?

Dans KNN, la notion de « voisins » dépend entièrement de la métrique choisie. Elle influence quels points sont considérés comme proches, la pondération implicite des variables et la forme de la frontière de décision. Le choix de la distance doit donc refléter la nature des variables, leur échelle et la présence de bruit. En pratique, standardisez presque toujours les variables numériques continues avant d’utiliser des distances basées sur des normes Lp afin d’éviter qu’une caractéristique à grande échelle ne domine le calcul.

À hautes dimensions, les distances euclidiennes ont tendance à se « concentrer » et différencient moins bien les voisins. Dans ces cas, une distance angulaire comme le cosinus, ou une réduction de dimension, peut offrir de meilleures séparations. À l’inverse, sur des données tabulaires compactes et bien mises à l’échelle, les distances L1 ou L2 sont souvent efficaces.

Euclidienne, Manhattan, Minkowski, Cosinus : quand choisir laquelle ?

Distance	Idée clé	Données typiques	Frontière de décision	Conseils
Euclidienne (L2)	Plus court chemin « à vol d’oiseau »	Variables continues de même ordre de grandeur	Zones circulaires ou sphériques autour des points	Sensible aux écarts d’échelle et aux valeurs extrêmes, standardiser les variables
Manhattan (L1)	Somme des écarts absolus par axe	Données avec variations anisotropes ou bruit par dimension	Zones en losange alignées sur les axes	Souvent plus robuste que L2 aux outliers le long d’un axe, standardiser aussi
Minkowski (Lp)	Généralise L1 et L2 avec un paramètre p	Tabulaires où l’on ajuste p par validation	Intermédiaire entre losanges (p=1) et cercles (p=2)	Choisir p via validation croisée, garder la normalisation des variables
Cosinus	Mesure l’angle, ignore la norme	Textes vectorisés TF-IDF, données creuses ou embeddings normalisés	Plans angulaires, séparation par direction	Préférer une normalisation à norme unitaire, peu sensible aux échelles globales

Cas concrets. Sur IRIS ou des jeux continus bien calibrés, la distance euclidienne fonctionne très bien après standardisation. Si vos variables sont de nature différente et présentent des écarts par dimension, la Manhattan peut limiter l’impact d’une dimension bruyante. Pour des documents représentés en TF-IDF ou des vecteurs creux, la distance cosinus sépare mieux par direction que par amplitude. Lorsque vous hésitez entre L1 et L2, utilisez la Minkowski avec un p ajusté par validation croisée afin d’obtenir la meilleure frontière de décision pour votre jeu de données.

Quels pré-traitements sont nécessaires ?

kNN repose sur une mesure de distance entre observations. Des échelles de variables hétérogènes, des variables catégorielles mal encodées ou des valeurs manquantes faussent ces distances. L’objectif des pré-traitements est donc de rendre chaque caractéristique comparable, surtout dans des jeux de données mixtes, puis d’appliquer le modèle dans une pipeline Scikit-Learn pour éviter toute fuite de données.

• Séparer d’abord entraînement, validation et test, puis ajuster tous les pré-traitements uniquement sur l’entraînement avant de transformer validation et test.
• Mettre les variables numériques sur une échelle comparable via normalisation ou standardisation.
• Encoder les variables catégorielles en indicatrices (one-hot) afin que la distance reflète des différences réelles et non un ordre arbitraire.
• Imputer les valeurs manquantes avec une stratégie adaptée au type de variable pour préserver une distance pertinente.
• Composer les étapes par type de colonnes avec un ColumnTransformer et chaîner dans une Pipeline avec le classificateur kNN.

Faut-il normaliser ou standardiser les variables ?

Oui, car kNN calcule des distances (euclidienne par défaut). Sans mise à l’échelle, une variable mesurée en grandes unités domine le calcul et écrase les autres. Deux pratiques courantes sont recommandées avec Scikit-Learn.

• StandardScaler (standardisation): centre-réduit chaque variable numérique (moyenne 0, écart-type 1). Bon choix par défaut, notamment quand les distributions sont proches d’une loi normale.
• MinMaxScaler (normalisation): projette chaque variable dans l’intervalle [0, 1]. Utile si vous souhaitez préserver des bornes naturelles ou comparer des variables déjà limitées.
• Bonnes pratiques: ajuster le scaler sur l’ensemble d’entraînement uniquement (fit/fit_transform), puis appliquer transform sur validation et test, idéalement au sein d’une Pipeline. En présence de fortes valeurs extrêmes, un RobustScaler peut être envisagé.

Comment traiter variables catégorielles et valeurs manquantes ?

• Variables catégorielles
  • Encoder en one-hot avec OneHotEncoder pour éviter d’introduire un ordre artificiel. Paramétrer handle_unknown="ignore" pour gérer des catégories nouvelles au test.
  • Limiter l’inflation dimensionnelle en regroupant les modalités très rares dans une catégorie “autre” si besoin.
  • Conserver la mise à l’échelle pour les seules variables numériques. Les colonnes one-hot n’ont généralement pas besoin d’être rescalées.

• Numériques: imputer par la moyenne ou la médiane avec SimpleImputer selon la robustesse souhaitée.
• Catégorielles: imputer par la modalité la plus fréquente ou une valeur constante explicite (par exemple “inconnu”).
• Option avancée: KNNImputer peut mieux respecter la structure locale des données, au prix d’un coût de calcul plus élevé. Comme pour tout pré-traitement, ajuster l’imputeur uniquement sur l’entraînement.

• Définir deux listes de colonnes: numériques et catégorielles.
• Bâtir un ColumnTransformer qui applique SimpleImputer + scaler sur les numériques, et SimpleImputer + OneHotEncoder sur les catégorielles.
• Chaîner ce transformeur avec KNeighborsClassifier ou KNeighborsRegressor dans une Pipeline, puis valider par cross-validation.

Ces étapes assurent que les distances utilisées par kNN traduisent des proximités réelles entre observations, même lorsque les données combinent des variables numériques et catégorielles, et qu’elles contiennent des valeurs manquantes.

Comment choisir la bonne valeur de k ?

Le choix de k conditionne directement les performances d’un modèle kNN, en classification comme en régression. Trop petit, k rend le modèle très sensible au bruit local. Trop grand, il lisse à l’excès la frontière de décision et perd de l’information. L’objectif est donc d’identifier un k qui généralise bien sur des données nouvelles, pas seulement sur l’échantillon d’entraînement.

En pratique, on sélectionne k par validation croisée et en examinant la courbe d’erreur en fonction de k. Cette approche, simple et robuste, complète utilement l’intuition issue d’un tracé « erreur vs k » déjà évoqué plus haut et permet d’éviter les conclusions hâtives propres à un seul découpage apprentissage/test.

Validation croisée et courbe d’erreur vs k : comment procéder ?

1. Préparer les données: séparer un jeu de test final (hold-out) pour l’évaluation ultime, puis travailler sur le jeu d’entraînement.
2. Standardiser les variables: comme kNN repose sur des distances, appliquez une normalisation (par exemple StandardScaler) à l’intérieur d’un pipeline avec KNeighborsClassifier pour éviter toute fuite de données. Voir aussi notre page dédiée à Scikit-Learn.
3. Définir une grille de k: par exemple k ∈ {1, 3, 5, …, 31}. Adaptez la plage à la taille et à la structure de vos données.
4. Lancer une validation croisée: utilisez une CV stratifiée (classification) avec 5 à 10 folds pour estimer, pour chaque k, une métrique pertinente (exactitude, F1, RMSE en régression, etc.).
5. Tracer la courbe: k en abscisse, erreur moyenne de CV (ou 1 − score) en ordonnée. Recherchez le minimum et la stabilité du score.
6. Sélectionner k: privilégiez le plus petit k parmi ceux qui atteignent le meilleur score moyen ou un score quasi équivalent, afin de limiter la complexité et la sensibilité au bruit.
7. Réentraîner et tester: réentraînez le pipeline complet avec ce k sur tout le jeu d’entraînement, puis évaluez une seule fois sur le jeu de test mis de côté au début.

Astuce pratique: en cas d’égalité de performances entre plusieurs valeurs, choisir la plus petite aide souvent à conserver une frontière suffisamment flexible sans devenir trop instable. Si vos classes sont déséquilibrées, complétez l’exactitude par des métriques comme F1 pondéré ou l’balanced accuracy.

k impair, sensibilité au bruit et pondération par distance ?

Quelques règles simples aident à poser un bon premier choix, tout en gardant en tête le compromis biais, variance: petit k, variance élevée et risque de surapprentissage; grand k, biais élevé et risque de sous-apprentissage.

• Commencez avec un k impair en classification binaire, cela réduit les égalités lors du vote. Ajustez ensuite par validation croisée.
• Point de départ utile: k proche de √N (N = nombre d’observations d’entraînement), puis affinez avec la grille et la CV.
• Évitez k = 1 en production: très sensible aux valeurs aberrantes et au bruit local. Essayez au moins k = 3 ou 5.
• Activez la pondération par distance (weights="distance") quand les densités locales diffèrent ou en présence d’outliers: les voisins plus proches pèsent davantage, ce qui diminue l’impact des points éloignés.
• Choisissez une métrique de distance adaptée: Euclidienne par défaut, Manhattan si vos variables suivent des distributions avec valeurs absolues plus pertinentes, toujours après standardisation.
• Sur données déséquilibrées, complétez la sélection de k avec des métriques robustes aux déséquilibres et, si besoin, échantillonnez ou pondérez les classes.

En synthèse: définissez une grille raisonnable, évaluez-la proprement par validation croisée dans un pipeline avec mise à l’échelle, inspectez la courbe d’erreur en fonction de k et retenez la valeur offrant le meilleur compromis généralisation/simplicité.

Comment évaluer un modèle KNN ?

Un KNN se juge sur des données tenues à l’écart de l’entraînement, idéalement via une validation croisée. Normalisez toujours les variables d’entrée après la séparation train/test pour éviter les fuites, puis choisissez K en observant l’erreur selon K ou par recherche croisée. Dans notre exemple IRIS, nous obtenions un excellent taux de bonne classification, mais seule une évaluation rigoureuse permet de confirmer la performance et de comprendre les erreurs.

En pratique, on combine plusieurs métriques selon l’objectif (classification ou régression) et le contexte métier. Les fonctions de Scikit-Learn facilitent le calcul des rapports et courbes utiles.

Classification : accuracy, F1, précision/rappel, matrice de confusion, ROC/PR

• Accuracy (exactitude) : part de prédictions correctes. À privilégier quand les classes sont équilibrées et que toutes les erreurs ont le même coût.
• Précision : parmi les positifs prédits, quelle part est correcte. À privilégier quand les faux positifs sont coûteux (par exemple alerter à tort un utilisateur).
• Rappel : parmi les positifs réels, quelle part est retrouvée. À privilégier quand les faux négatifs sont critiques (fraude rare, détection d’incident, santé).
• F1-score : moyenne harmonique précision et rappel. Bon compromis en cas de déséquilibre de classes ou quand précision et rappel importent autant. Pensez aux moyennes macro (toutes classes pondérées de façon égale), weighted (pondérées par le support) et micro (globales).
• Matrice de confusion : vue détaillée des vrais/faux positifs et négatifs par classe. Utile pour diagnostiquer les types d’erreurs et ajuster le seuil de décision ou le voting du KNN (poids par distance).
• Courbe ROC et AUC-ROC : capacité de classement global, moins sensible au choix de seuil. Pratique quand le déséquilibre est modéré et que l’on compare plusieurs modèles.
• Courbe PR et AUC-PR : plus informative en cas de classes très déséquilibrées. À privilégier quand la classe positive est rare.

Conseils rapides : en présence de fort déséquilibre, ne vous fiez pas à l’accuracy, inspectez la matrice de confusion et optimisez F1 ou AUC-PR. Avec des classes équilibrées, accuracy et AUC-ROC donnent une bonne première vue. Ajustez K et le weights du KNN (uniforme ou distance) en validant sur la métrique métier prioritaire.

Régression : MAE, RMSE, R²

• MAE (mean absolute error) : erreur moyenne absolue, exprimée dans l’unité de la cible. Facile à interpréter et robuste aux valeurs extrêmes. Repère utile : comparer le MAE à la tolérance métier, à l’écart type de la cible ou à l’amplitude typique des valeurs.
• RMSE (root mean squared error) : pénalise davantage les grosses erreurs. À privilégier si les écarts importants sont particulièrement coûteux. Repères : un RMSE nettement supérieur au MAE signale des outliers ou des erreurs concentrées sur certains cas.
• R² : proportion de variance expliquée. 1 signifie parfait, 0 équivaut à prédire la moyenne, négatif indique pire que la moyenne. Repères indicatifs à adapter au domaine : proche de 0.3 faible, 0.3, 0.6 moyen, au-delà de 0.6 bon, sous réserve de la difficulté du problème et du bruit de mesure.

Synthèse : choisissez la métrique alignée sur le risque métier. Optimisez K par validation croisée en minimisant MAE ou RMSE selon votre priorité, puis contrôlez R² pour vérifier la part de variance capturée. Comparez toujours vos scores à une base simple (moyenne ou médiane) pour valider l’apport réel du KNN.

Quelles variantes de KNN existent ?

KNN se décline en plusieurs variantes utiles selon la règle de vote, la définition du voisinage, la métrique de distance et l’algorithme de recherche. Dans scikit-learn, ces réglages sont exposés dans les classes KNeighborsClassifier et KNeighborsRegressor, ainsi que leurs équivalents fondés sur un rayon pour s’adapter aux variations locales de densité.

• Vote uniforme ou pondéré par la distance : soit chaque voisin compte pareil, soit l’on pondère son influence par 1/distance. Réglage pratique dans scikit-learn via weights= »uniform » ou weights= »distance ». Effet attendu : une pondération par distance lisse souvent la frontière de décision et réduit l’influence des voisins lointains.
• Voisinage à k fixe ou par rayon : au lieu d’un nombre k constant, on peut considérer tous les voisins dans un rayon donné r. Utile lorsque la densité varie selon les zones. En classification, RadiusNeighborsClassifier permet de fixer radius et de gérer les points sans voisin via outlier_label. En régression, RadiusNeighborsRegressor applique la même logique. Effet attendu : adaptativité aux zones denses ou clairsemées, mais sensibilité au choix de r.
• Métriques de distance : euclidienne, Manhattan, Minkowski (paramètre p), Hamming pour variables binaires, cosine pour vecteurs directionnels. Le choix de la métrique modifie la géométrie du voisinage et donc la frontière de décision. Réglages fréquents : metric= »minkowski », p=1 (Manhattan) ou p=2 (Euclidienne), metric= »hamming », metric= »cosine ».
• Algorithme de recherche : « auto », « kd_tree », « ball_tree » ou « brute ». Le choix affecte surtout la vitesse selon la dimension et la structure des données, pas la prédiction elle-même. En dimension élevée, le calcul « brute » peut devenir compétitif, alors qu’en dimension modérée les arbres accélèrent les requêtes.

Pondération par distance, voisins par rayon (RadiusNeighbors), métriques personnalisées ?

• Pondération par distance (weights= »distance ») : renforce l’influence des voisins les plus proches, utile si les classes se chevauchent. Effets attendus : frontières plus lisses, moins d’impact des points isolés lointains. Bon réflexe : normaliser les variables avant apprentissage pour éviter qu’une échelle domine le calcul des distances.
• Voisins par rayon (radius=r) : pratique si la densité n’est pas uniforme. Avec RadiusNeighborsClassifier, un point sans voisin dans le rayon peut recevoir un label d’exception via outlier_label. Effets attendus : zone de décision qui s’ajuste localement, au prix d’un r à valider par recherche d’hyperparamètres. Variante régression disponible avec RadiusNeighborsRegressor.
• Métriques personnalisées (metric, p, metric_params) : ajustez la notion de proximité à la nature des variables. Exemples rapides : Hamming sur variables binaires, cosine pour des vecteurs orientés, Minkowski avec p=1 ou p=2 pour privilégier respectivement Manhattan ou Euclidienne. Conséquence : la forme des voisinages change, ce qui peut améliorer la séparation entre classes ou la stabilité des prédictions.
• Accélération de la recherche (algorithm, leaf_size) : « kd_tree » ou « ball_tree » pour des données de dimension modérée, « brute » souvent plus simple en très haute dimension. Mesurez le temps d’inférence, pas seulement la métrique d’exactitude.

KNN passe-t-il à l’échelle ?

kNN est un apprentissage par instance : il ne construit pas de modèle, il mémorise l’ensemble d’entraînement puis compare chaque nouvelle observation à toutes les observations existantes. Conséquence directe, le calcul et la mémoire augmentent avec le nombre d’exemples et la dimension. Comme rappelé plus haut, l’algorithme devient beaucoup plus lent à mesure que le nombre d’observation et de variables indépendantes augmente.

En pratique, kNN s’industrialise bien lorsque les volumes et la dimension restent modérés, ou si l’on recourt à des structures d’index adaptées, à de l’approximation contrôlée et à une réduction de dimension. Le bon compromis dépend de la latence visée, du rappel acceptable et des ressources mémoire disponibles.

Quelle complexité en temps et mémoire à l’inférence ?

Ordres de grandeur avec une recherche linéaire sur n points en dimension d :

Étape	Temps par requête	Mémoire	Impacts pratiques
Calcul des distances vers n points (dimension d)	O(n × d)	,	Latence qui croît linéairement avec le volume et la dimension.
Sélection des k plus proches	O(n log k) avec tas, souvent proche de O(n) car k est petit	O(k)	Coût marginal si k est faible.
Total inférence brute	O(n × d)	O(n × d) pour stocker les vecteurs (+ étiquettes)	Le stockage domine vite : par exemple, en float32, la mémoire suit 4 octets × n × d.

Remarques : vectoriser des requêtes en lot peut accélérer le calcul par produits matriciels, mais ne change pas l’ordre de grandeur. Sur de très grands volumes, l’I/O mémoire devient souvent le goulot d’étranglement autant que le CPU.

Quelles accélérations (KD-tree, Ball-tree, ANN/LSH) et quand les utiliser ?

• Index exacts
  KD-tree : partitions par axes, très efficace en faible dimension (typiquement jusqu’à quelques dizaines de variables numériques). Construction souvent O(n log n), requêtes sous-linéaires en moyenne lorsque d est faible. À privilégier pour des jeux compacts et métriques euclidiennes.
  Ball-tree : partitions en hypersphères, mieux adapté que KD-tree lorsque les frontières ne sont pas alignées sur les axes ou pour des métriques générales. Bénéfice qui décroît quand la dimension augmente.
• Approximate Nearest Neighbors (ANN)
  LSH : hachage sensible à la similarité, adapté aux très hautes dimensions, aux vecteurs creux, aux métriques comme cosinus ou Jaccard. Temps de requête sous-linéaire en échange d’un rappel imparfait.
  Graphes de proximité (ex. HNSW) et partitions quantifiées : navigation sur graphe ou index inversés avec quantification pour réduire la mémoire. Excellent compromis précision/latence sur des millions de vecteurs.
• Accélération matérielle
  Brute force GPU : extrêmement compétitif jusqu’à des dizaines de millions de comparaisons par requête grâce aux produits matriciels, utile quand on exige l’exactitude tout en gardant une latence faible.

Repères d’usage : préférez KD-tree/Ball-tree quand la dimension est faible et l’exactitude stricte est requise. Au-delà, ou dès que les volumes deviennent massifs ou les contraintes de latence serrées, orientez-vous vers l’ANN, en ajustant le rappel visé. Pour des scorings en lot hors ligne, le calcul exhaustif multi-threadé ou GPU reste simple et fiable.

Malédiction de la dimensionnalité : que faire ?

Quand la dimension augmente, les distances se concentrent, les index se dégradent et kNN perd en pouvoir discriminant. Avant d’optimiser l’index, améliorez l’espace des caractéristiques.

• Sélection de variables : filtrage par information mutuelle, F-test/ANOVA, importance de modèles arbres, élimination récursive des attributs. Supprimer le bruit aide autant la précision que la latence.
• Réduction de dimension : PCA pour des embeddings denses et stables, LDA si les classes sont connues, UMAP pour préserver les voisinages locaux (souvent avec un léger coût d’approximation). Revalider k et la métrique après projection.
• Normalisation et métrique : standardiser ou mettre à l’échelle les variables, envisager des pondérations par caractéristique ou une distance de type Mahalanobis quand pertinent.
• Représentations dédiées : utiliser des embeddings plus compacts issus du domaine (texte, image, séries temporelles) afin de réduire naturellement la dimension utile.

Quels sont les avantages et limites de KNN ?

KNN repose sur une idée simple : prédire en s’appuyant sur les observations les plus proches. Cette simplicité en fait un bon choix de départ, mais son efficacité dépend fortement des données et de la mise en œuvre. Voici une synthèse utile pour décider quand l’utiliser et comment l’optimiser.

En bref : KNN est simple, interprétable localement et polyvalent (classification, régression, recherche de similarité). Ses limites principales concernent la sensibilité à l’échelle des variables et au bruit, le coût de prédiction et la dimensionnalité. Les bonnes pratiques de préparation des données et d’indexation permettent de lever la plupart de ces freins.

Quels sont ses points forts ?

• Simplicité et mise en œuvre rapide : pas de modèle paramétrique à entraîner, peu d’hyperparamètres à régler (k, métrique de distance). L’algorithme est simple et facile à mettre en œuvre, comme rappelé plus haut dans l’article.
• Interprétabilité locale : chaque prédiction s’explique par les voisins retenus et leurs distances. Il est facile de montrer « qui a influencé la décision », un atout pour l’explicabilité.
• Polyvalence : utilisable pour la classification et la régression, adapté aux frontières de décision irrégulières, compatible avec plusieurs distances (euclidienne, Manhattan, etc.) et utile pour la recherche de similarité ou l’imputation de valeurs manquantes.
• Mise à jour sans réentraînement : l’ajout de nouvelles observations améliore immédiatement la base de référence, pratique lorsque les données évoluent fréquemment.

Cas concret : sur des jeux structurés comme IRIS, KNN atteint rapidement de bonnes performances avec un choix de k raisonnable, et la décision reste facile à justifier en affichant les voisins les plus proches. Avec Scikit-Learn, on l’intègre en quelques lignes dans un pipeline.

Quelles limites et comment les atténuer ?

• Sensibilité aux échelles : une variable à grande amplitude domine la distance.
  Parades : standardiser ou normaliser les caractéristiques (StandardScaler, MinMaxScaler), choisir une métrique adaptée, éventuellement pondérer ou sélectionner les variables.
• Sensibilité au bruit et aux valeurs aberrantes : avec k trop petit, quelques points bruyants peuvent inverser le vote.
  Parades : utiliser k > 1, tester la pondération par la distance (les voisins proches comptent plus), nettoyer les outliers et privilégier des métriques robustes si besoin.
• Coût de prédiction et mémoire : la prédiction nécessite de comparer à de nombreuses observations, ce qui devient lent et gourmand en mémoire sur de gros volumes.
  Parades : utiliser des index d’espace de recherche (k-d tree, ball tree), des méthodes de voisins approximatifs pour accélérer, réduire le jeu d’entraînement par prototypage/échantillonnage, vectoriser les calculs et prévoir des prédictions par lot.
• Dimensionnalité élevée : la distance perd en pouvoir discriminant quand le nombre de variables augmente.
  Parades : sélection de caractéristiques, réduction de dimension (PCA), ingénierie de variables ou metric learning pour rapprocher les points pertinents.
• Choix de k et de la métrique : k trop petit, variance élevée ; k trop grand, biais élevé.
  Parades : rechercher k et la métrique par validation croisée, démarrer avec une valeur de k modérée et impaire en classification binaire, considérer la pondération par distance.
• Déséquilibre de classes : les classes majoritaires dominent le voisinage.
  Parades : stratifier les découpages, équilibrer l’entraînement (rééchantillonnage), utiliser la pondération par distance ou des poids d’échantillons.
• Variables catégorielles : encodage et distance inadaptés peuvent fausser la proximité.
  Parades : encodage approprié (one-hot) et, si pertinent, distances dédiées aux variables non numériques.

En pratique : créez un pipeline Scikit-Learn StandardScaler + KNeighborsClassifier/KNeighborsRegressor, recherchez automatiquement k, la métrique et la pondération avec la validation croisée, mesurez plusieurs scores (précision, F1, RMSE selon la tâche) et vérifiez la latence de prédiction. Cette démarche garantit un KNN robuste et exploitable en production.

KNN : Exemple d’utilisation

Nous pouvons à présent passer de l’intuition à la pratique avec un exemple simple, puis un mini-workflow reproductible. Grâce à la librairie Scikit-Learn, nous pouvons utiliser le classificateur KNeighborsClassifier sur un jeu de données comme IRIS, visualiser l’effet du paramètre k et choisir une configuration performante de manière rigoureuse.

Objectif concret : obtenir une frontière de décision compréhensible en 2D, mettre en place un pipeline d’entraînement et d’évaluation en quelques étapes, puis relier KNN à des cas d’usage réels.

À quoi ressemble la frontière de décision en 2D (exemple jouet) ?

Sur un jeu 2D jouet avec deux classes, la frontière de décision KNN dépend fortement de k et de la métrique. Un k petit produit une frontière très découpée, sensible au bruit local, avec un risque de surapprentissage. Un k plus grand lisse la frontière, réduit la variance et augmente le biais, ce qui peut manquer de détails locaux. Côté distance, l’Euclidienne crée des régions plutôt circulaires, la Manhattan des régions en losange, et le vote pondéré par la distance donne plus d’influence aux voisins les plus proches.

Exemple jouet à reproduire : placez deux nuages de points séparés. Testez la prédiction d’un nouveau point avec k = 1, 5, puis 15. Observez la classe prédite et la zone de décision autour de ce point. Répétez avec distance Euclidienne puis Manhattan, et comparez la forme des régions de décision. Astuce pratique : privilégier un k impair pour limiter les ex æquo en classification binaire.

Comment l’implémenter rapidement avec scikit-learn ?

1. Préparer les données : séparer les variables explicatives X et la cible y, gérer les valeurs manquantes et les éventuels déséquilibres de classes.
2. Créer la séparation apprentissage/test : utiliser un train/test split stratifié pour préserver la distribution des classes sur l’ensemble de test.
3. Mettre à l’échelle dans un pipeline : standardiser les variables numériques avec StandardScaler puis enchaîner KNeighborsClassifier dans un même pipeline. Toujours ajuster le scaler uniquement sur l’entraînement pour éviter toute fuite d’information.
4. Choisir k et la distance par validation croisée : faire varier k, la métrique (euclidienne, manhattan) et le vote (uniforme ou pondéré par la distance) via cross-val ou une recherche d’hyperparamètres. Retenir la configuration offrant le meilleur score moyen et une variance satisfaisante.
5. Évaluer sur le test : rapporter l’accuracy, la matrice de confusion, la précision et le rappel. Vérifier les erreurs typiques et la robustesse du modèle.
6. Industrialiser : conserver le pipeline entraîné, documenter les hyperparamètres retenus et la procédure de mise à l’échelle, puis surveiller les performances dans le temps.

Sur IRIS, KNN peut atteindre un excellent taux de bonne classification lorsque les variables sont standardisées et que k est choisi par validation croisée. La courbe d’erreur en fonction de k présente souvent un plateau optimal, ce qui évite de surajuster à un k trop petit et de trop lisser à un k trop grand.

Lecture de la courbe : un sweet spot apparaît souvent autour d’un intervalle de k où l’erreur est minimale et stable. En-dessous, la variance est élevée et le modèle surapprend. Au-delà, la frontière devient trop lisse et l’on observe de l’sous-apprentissage. Retenez la plus petite valeur de k dans la zone optimale pour garder une bonne réactivité locale.

Où KNN est-il utilisé en pratique ?

• Recherche de similarité : retrouver des images, documents ou clients proches d’un élément requête dans un espace vectoriel.
• Recommandation : proposer des produits ou contenus de profils voisins, sur la base de comportements ou d’attributs partagés.
• Imputation de valeurs manquantes : estimer une valeur manquante par la moyenne ou la médiane des voisins les plus proches.
• Détection d’anomalies : repérer des points isolés, éloignés de leurs plus proches voisins, indicateurs potentiels d’outliers ou de fraude.

Cas concret : chez un e-commerçant, on peut décrire chaque transaction par la distance au domicile et par un ratio prix-d’achat courant versus médian du client. Après mise à l’échelle, KNN classe une nouvelle transaction comme suspecte si ses plus proches voisines appartiennent majoritairement à la classe « fraude ». Ce raisonnement par proximité se transpose facilement à la détection d’abus d’abonnement, au repérage de contenus hors-profil ou à l’identification de clients similaires pour l’upsell.

Autres exemples déjà rencontrés : OCR pour la reconnaissance d’écriture, notations de crédit et octroi de prêts en comparant un individu à des profils proches.