Qu’est-ce que l’algorithme des K plus proches voisins (KNN) en apprentissage automatique ?
Dernière mise à jour : 1er mars 2025
À la fin de cet article, vous serez capable de :
Expliquer les principes fondamentaux de KNN et son fonctionnement
Sélectionner les métriques de distance appropriées pour différents types de données
Implémenter KNN pour les tâches de classification et de régression
Optimiser les modèles KNN en sélectionnant la valeur idéale de k
Comprendre les limites de KNN et quand utiliser des approches alternatives
Appliquer KNN à des problèmes réels avec Python
Introduction : la similarité dans la prise de décision quotidienne
Imaginez que vous essayez de décider quel restaurant visiter dans une nouvelle ville. Que faites-vous généralement ? Vous pourriez demander des recommandations à des amis ayant des goûts similaires aux vôtres, en partant du principe que si des personnes ayant des préférences similaires aux vôtres ont apprécié un restaurant, vous l’apprécierez probablement aussi.
Ce concept intuitif — selon lequel des éléments ou des entités similaires les uns aux autres partagent souvent des caractéristiques importantes — est précisément ce qui alimente l’algorithme K-Nearest Neighbors (KNN). KNN formalise cette intuition en une puissante technique d’apprentissage automatique qui trouve des applications dans de nombreux domaines, des systèmes de recommandation au diagnostic médical.
L’algorithme knn est un algorithme d’apprentissage automatique supervisé qui peut résoudre à la fois des problèmes de classification et de régression. Il estime la probabilité qu’un point de données appartienne à un groupe ou à un autre en fonction des points de données existants qui en sont les plus proches. Contrairement à de nombreux algorithmes de ml qui construisent des modèles complexes, l’élégance de KNN réside dans sa simplicité : l’algorithme stocke simplement les données d’entraînement et effectue des prédictions en trouvant les exemples les plus similaires.
Définition de KNN
L’algorithme des K plus proches voisins est un algorithme d’apprentissage automatique supervisé qui s’appuie sur la proximité pour effectuer des classifications ou des prédictions concernant le regroupement d’un point de données individuel. En tant qu’algorithme non paramétrique d’apprentissage paresseux, KNN stocke l’intégralité du jeu de données d’entraînement et n’effectue des calculs qu’au moment de la classification. Cela signifie qu’au lieu de construire un modèle pendant une phase d’entraînement, KNN effectue des prédictions en comparant directement les nouveaux points de données aux données d’entraînement stockées. L’algorithme est polyvalent, étant utilisé à la fois pour les tâches de classification et de régression, et ses performances sont influencées par le choix de K (le nombre de plus proches voisins pris en compte) et par la métrique de distance utilisée pour mesurer la similarité.
Importance de KNN en science des données
L’algorithme KNN occupe une place importante dans le domaine du ml et de la science des données en raison de sa simplicité, de sa facilité d’interprétation et de son coût de calcul relativement faible pour les jeux de données de petite à moyenne taille. Son approche directe en fait un excellent point de départ pour les débutants en science des données, tandis que son efficacité garantit qu’il reste un outil précieux pour les professionnels expérimentés. KNN est largement appliqué dans divers domaines, notamment la classification d’images, la classification de textes et les systèmes de recommandation. Par exemple, il peut prédire l’attrition des utilisateurs dans un service de streaming, aider au diagnostic médical et contribuer aux prévisions financières. Sa capacité à gérer les relations non linéaires et sa robustesse face aux valeurs aberrantes renforcent encore son attrait, ce qui en fait un choix populaire dans l’industrie.
Concepts fondamentaux
Apprentissage supervisé vs. non supervisé
KNN appartient à la famille des algorithmes d’apprentissage supervisé, ce qui signifie qu’il nécessite des données d’entraînement étiquetées pour effectuer des prédictions. Dans l’apprentissage supervisé, l’algorithme apprend à partir d’exemples où les bonnes réponses (étiquettes) sont fournies, contrairement à l’apprentissage non supervisé où l’algorithme doit trouver des motifs dans des données non étiquetées.
Apprentissage paresseux vs. apprentissage empressé
Ce qui rend KNN unique parmi de nombreux algorithmes de ml, c’est qu’il est considéré comme un « apprenant paresseux ». La plupart des algorithmes passent par une phase d’entraînement explicite pour construire un modèle avant d’effectuer des prédictions. KNN, cependant, n’a pas de phase d’entraînement distincte : il stocke simplement le jeu de données d’entraînement et retarde tous les calculs jusqu’au moment de la prédiction. C’est pourquoi KNN est également appelé :
Apprentissage fondé sur les instances
Apprentissage basé sur la mémoire
Apprentissage non paramétrique
Comme KNN ne fait pas d’hypothèses sur la distribution sous-jacente des données (non paramétrique) et ne résume pas les données d’entraînement dans un modèle compact, il peut capturer des frontières de décision complexes que les modèles paramétriques pourraient manquer.
Classification vs. Régression avec KNN
KNN peut être utilisé pour les tâches de classification comme de régression :
Classification KNN : Prédit l’étiquette de classe d’une nouvelle instance en trouvant la classe la plus courante parmi ses k plus proches voisins. La classification d’un nouveau point de données est basée sur la classe la plus courante parmi ses k plus proches voisins (KNN).
Régression KNN : Prédit la valeur numérique d’une nouvelle instance en faisant la moyenne des valeurs de ses k plus proches voisins.
Espace des caractéristiques et similarité
La pierre angulaire de KNN est le concept de similarité ou de distance dans l’espace des caractéristiques. Chaque point de données est représenté comme un vecteur dans un espace multidimensionnel, où chaque dimension correspond à une caractéristique. La similarité entre deux points de données est inversement liée à la distance qui les sépare dans cet espace des caractéristiques : plus deux points sont proches, plus ils sont considérés comme similaires.
Métriques de distance en détail
Le choix de la métrique de distance est crucial dans KNN, car il affecte directement les points considérés comme les plus "proches" les uns des autres. Différentes métriques de distance sont appropriées pour différents types de données et domaines de problèmes.
Distance euclidienne
La distance euclidienne est la véritable distance en ligne droite entre deux points dans l’espace euclidien. C’est la métrique de distance la plus couramment utilisée dans KNN.
Formule mathématique :
Où x et y sont deux points dans un espace à n dimensions.
Quand l’utiliser : La distance euclidienne fonctionne bien lorsque les données sont continues et présentent des relations significatives dans toutes les dimensions. Elle est particulièrement appropriée lorsque les caractéristiques sont mesurées sur des échelles similaires.
Distance de Manhattan
Également connue sous le nom de distance city block ou L1, la distance de Manhattan calcule la somme des différences absolues entre les coordonnées de deux points. Dans l’algorithme KNN, les distances de Manhattan sont utilisées pour mesurer la proximité des points de données dans des structures de type grille, ce qui la rend particulièrement adaptée à de tels environnements.
Formule mathématique :
Quand l’utiliser : La distance de Manhattan est utile lorsque les caractéristiques représentent des attributs discrets ou binaires, ou lorsque l’espace des caractéristiques ressemble à une grille. Elle peut être moins sensible aux valeurs aberrantes que la distance euclidienne.
Similarité cosinus
La similarité cosinus mesure le cosinus de l’angle entre deux vecteurs, en se concentrant sur l’orientation plutôt que sur la magnitude.
Formule mathématique :
Quand l’utiliser : La similarité cosinus est particulièrement utile pour l’analyse de texte et les données creuses de grande dimension, où la magnitude des vecteurs peut être moins importante que leur direction.
Distance de Hamming
La distance de Hamming compte le nombre de positions auxquelles les éléments correspondants diffèrent dans deux séquences de même longueur.
Formule mathématique : Pour deux chaînes de même longueur, la distance de Hamming est le nombre de positions auxquelles les symboles correspondants diffèrent.
Quand l’utiliser : La distance de Hamming est idéale pour les données catégorielles ou lorsqu’on travaille avec des caractéristiques binaires. Elle est couramment utilisée en théorie de l’information, en théorie du codage et pour comparer des chaînes ou des vecteurs de bits.
Directives pour le choix des métriques de distance
Distance euclidienne : Données continues avec des échelles similaires
Distance de Manhattan : Espaces de type grille, indépendance des caractéristiques
Similarité cosinus : Données textuelles, données creuses de grande dimension
Distance de Hamming : Données catégorielles, caractéristiques binaires
N’oubliez pas que, quelle que soit la métrique de distance que vous choisissez, la mise à l’échelle des caractéristiques est souvent nécessaire pour empêcher les caractéristiques ayant des échelles plus grandes de dominer les calculs de distance.
L’algorithme KNN : étape par étape
Maintenant que nous comprenons le concept de distance, parcourons l’algorithme KNN étape par étape.
Exigences de prétraitement des données
Avant d’appliquer KNN, plusieurs étapes de prétraitement sont essentielles :
Mise à l’échelle des caractéristiques : Étant donné que les calculs de distance sont directement affectés par l’échelle des caractéristiques, la normalisation ou la standardisation est cruciale. Généralement, les caractéristiques sont mises à l’échelle dans l’intervalle [0, 1] ou standardisées pour avoir une moyenne de 0 et un écart-type de 1.
Gestion des valeurs manquantes : KNN ne peut pas gérer directement les valeurs manquantes, des techniques d’imputation doivent donc être appliquées.
Réduction de la dimensionnalité : Les données de grande dimension peuvent souffrir de la « malédiction de la dimensionnalité », où les métriques de distance deviennent moins significatives. Des techniques comme PCA peuvent aider à réduire la dimensionnalité.
Sélection des paramètres
Le paramètre le plus critique dans KNN est k, le nombre de voisins à considérer. Le choix de k a un impact significatif sur les performances du modèle :
Petit k (par exemple, k=1 ou k=3) : Le modèle peut avoir une forte variance (surapprentissage), en étant sensible au bruit dans les données d’entraînement.
Grand k (par exemple, k=20) : Le modèle peut avoir un fort biais (sous-apprentissage), risquant de manquer des motifs importants dans les données.
La valeur optimale de k est généralement déterminée par validation croisée, souvent à l’aide de techniques comme la méthode du coude ou la recherche par grille, que nous aborderons plus en détail plus tard.
Phase d’entraînement (ou son absence)
Comme mentionné précédemment, KNN n’a pas de phase d’entraînement traditionnelle. Au lieu de cela, il stocke simplement l’ensemble complet des données d’entraînement en mémoire. Cette caractéristique rend KNN rapide à « entraîner », mais potentiellement lent lors de la prédiction, surtout avec de grands ensembles de données.
Processus de prédiction
Comment calculer l’algorithme des K plus proches voisins
Pour déterminer la classe d’un point de données non observé sur la base de l’observation, l’algorithme des K plus proches voisins utilise essentiellement un mécanisme de vote majoritaire. Le vote majoritaire est un processus fondamental dans KNN, où l’algorithme classe un point de données en déterminant la catégorie à laquelle appartiennent la plupart de ses voisins les plus proches. Il indique que la classe qui reçoit le plus de votes sera la classe du point de données concerné. L’algorithme KNN classe un point de données donné en fonction de la proximité de ses voisins les plus proches.
Si K est égal à 1, nous ne considérerons que le voisin le plus proche d’un point de données pour déterminer sa classe. Les 10 voisins les plus proches seront utilisés si K est égal à 10, et ainsi de suite. Le point de test est classé en fonction de la valeur de « k » et de la proximité avec les points de données d’entraînement.
Considérons deux classes : A et B. L’algorithme examine les états des points de données voisins pour déterminer si un point de données appartient à la classe A ou à la classe B. Si la plupart des points de données sont dans le groupe A, il est presque certain que le point de données en question appartient au groupe A.
Pour les tâches de classification, KNN effectue des prédictions en suivant ces étapes :
Calculer la distance entre la nouvelle instance et toutes les instances de l’ensemble de données d’entraînement.
Sélectionner les k instances de l’ensemble de données d’entraînement qui sont les plus proches de la nouvelle instance.
Pour la classification : Effectuer un vote majoritaire des knn afin de déterminer la classe de la nouvelle instance.
Pour la régression : Calculer la moyenne (ou la moyenne pondérée) des valeurs des k plus proches voisins.
Comment KNN fonctionne entre deux classes. Source : https://www.ibm.com/in-en/topics/knn
Exemple de KNN en action
Un exemple classique de KNN en action est un système de recommandation pour un service de streaming de films. Imaginez une plateforme qui utilise l’algorithme KNN pour suggérer des films aux utilisateurs en fonction de leur historique de visionnage et de leurs notes passés. L’algorithme identifie les K plus proches voisins d’un utilisateur donné, où les voisins sont d’autres utilisateurs ayant des habitudes de visionnage similaires. En analysant les préférences de ces voisins, le système peut recommander des films qu’ils ont très bien notés mais que l’utilisateur cible n’a pas encore regardés. Cette approche de recommandation personnalisée améliore non seulement l’expérience utilisateur, mais augmente également l’engagement et la satisfaction des utilisateurs, illustrant la puissance pratique de l’algorithme KNN.
Variantes pondérées de KNN
Le KNN standard traite tous les voisins de manière égale, mais cela peut ne pas être idéal, car les voisins plus proches devraient logiquement avoir plus d’influence sur les prédictions. Le KNN pondéré y remédie en attribuant des poids aux voisins en fonction de leur distance :
Le poids de chaque voisin est généralement l’inverse de sa distance par rapport au point de requête.
Pour la classification, un vote pondéré est effectué.
Pour la régression, une moyenne pondérée est calculée.
La formule d’une approche simple pondérée par la distance pourrait ressembler à ceci :
weighti=1d(x,xi)2\text{weight}_i = \frac{1}{d(x, x_i)^2}weighti=d(x,xi)21
Où d(x, xi) est la distance entre le point de requête x et le voisin xi.
Optimisation des performances de KNN
Stratégies de validation croisée pour trouver le k optimal
La validation croisée en K plis est couramment utilisée pour déterminer la valeur optimale de k. Le processus consiste à :
Diviser l’ensemble de données en k plis (à ne pas confondre avec le k dans KNN).
Pour chaque valeur de k dans KNN (par exemple, k=1 à k=20) :
Entraîner et évaluer le modèle k fois, en utilisant à chaque fois un pli différent comme ensemble de test.
Calculer la performance moyenne sur l’ensemble des k plis.
Sélectionner la valeur de k qui donne la meilleure performance moyenne.
Méthode du coude
La méthode du coude consiste à tracer les performances du modèle (par exemple, la précision ou le taux d’erreur) en fonction de différentes valeurs de k et à rechercher un « point de coude » où le taux d’amélioration diminue significativement. Ce point indique souvent un bon compromis entre biais et variance.
Mise en œuvre de la recherche par grille
La recherche par grille est une façon systématique d’essayer différentes combinaisons d’hyperparamètres (y compris k et éventuellement des métriques de similarité) et de sélectionner la combinaison qui donne les meilleures performances sur un ensemble de validation.
Gestion du déséquilibre des classes
KNN peut être sensible au déséquilibre des classes, lorsque certaines classes comportent beaucoup plus d’exemples que d’autres. Les stratégies pour y remédier incluent :
Rééchantillonnage : Suréchantillonnage des classes minoritaires ou sous-échantillonnage des classes majoritaires.
Métriques d’évaluation différentes : Utilisation de métriques comme le score F1 ou l’AUC au lieu de la précision.
Vote pondéré : Attribution de poids différents aux classes en fonction de leur fréquence.
Considérations sur la dimensionnalité et la malédiction de la dimensionnalité
À mesure que le nombre de dimensions (caractéristiques) augmente, le volume de l’espace augmente de manière exponentielle. Ce phénomène, connu sous le nom de « malédiction de la dimensionnalité », peut rendre les métriques de distance moins significatives et KNN moins efficace. Dans les espaces à haute dimension :
Les points de données ont tendance à être équidistants les uns des autres.
Le concept de « plus proche » devient moins clair.
Le modèle nécessite exponentiellement plus de données.
Pour lutter contre cela, envisagez :
La sélection de caractéristiques pour supprimer les caractéristiques non pertinentes
Des techniques de réduction de la dimensionnalité comme PCA
L’utilisation de structures de données spécialisées comme les KD-trees pour une recherche efficace des plus proches voisins
Mise en œuvre pratique
Implémentons KNN pour une tâche de classification à l’aide de Python et scikit-learn.
Importation des modules
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
from sklearn.datasets import make_blobs
from sklearn.neighbors import KNeighborsClassifier
from sklearn.model_selection import train_test_split
from sklearn.metrics import accuracy_score
Jeu de données
Scikit-learn peut être utilisé pour créer des jeux de données synthétiques à partir d’échantillons d’entraînement, ce qui est idéal à des fins de démonstration.
X, y = make_blobs(n_samples = 4000, n_features = 3, centers = 3 ,cluster_std = 2, random_state = 80)
X
array([[ 7.60190561, 4.86336321, 6.97616573],
[ 5.97809745, 7.69910922, 2.77419701],
[-4.36024844, -2.23247572, -5.29113293],
...,
[-8.22252297, -6.88609334, -6.52102135],
[-3.96254707, -5.27559922, -2.70880022],
[-4.25865881, -1.67791521, -3.70523373]])
y
array([1, 1, 2, ..., 2, 2, 2])
Graphique
plt.figure(figsize = (6,6))
plt.scatter(X[:,0], X[:,1], c=y, marker= '.', s=10, edgecolors='blue')
plt.show()
df = pd.DataFrame(X)
df.head()
plt.rcParams['figure.figsize']=(10,15)
df.plot(kind='hist', bins=100, subplots=True, layout=(5,2), sharex=False, sharey=False)
plt.show()
L’implémentation du classificateur des K plus proches voisins
La première étape consiste à déterminer la valeur optimale de k. Le calcul de la valeur de K varie considérablement selon la situation. La valeur par défaut de K lors de l’utilisation de la bibliothèque Scikit-Learn est 5 et la métrique de distance par défaut utilisée est euclidienne.
Réglage du modèle pour obtenir une grande précision des K plus proches voisins
from sklearn.model_selection import GridSearchCV
param_grid = {'n_neighbors':np.arange(1,4)}
knn = KNeighborsClassifier()
knn_cv= GridSearchCV(knn,param_grid,cv=5)
knn_cv.fit(X,y)
print(knn_cv.best_params_)
print(knn_cv.best_score_)
{'n_neighbors': 3}
0.9887499999999999
#train-test split
X_train, X_test, y_train, y_test = train_test_split(X, y, random_state = 80)
# instantiate the model
knn = KNeighborsClassifier(n_neighbors=3)
# fit the model to the training set
knn.fit(X_train, y_train)
y_pred = knn.predict(X_test)
print('Model accuracy score: {0:0.4f}'. format(accuracy_score(y_test, y_pred)))
Score de précision du modèle : 0.9890.
Nous avons obtenu un taux de précision de 98,90 %, ce qui est considéré comme très bon. Nous avons augmenté le nombre de voisins de 1 à 4, et le modèle a obtenu les meilleures performances avec k=3.
Le modèle des K plus proches voisins n’implique aucune période d’entraînement, puisque les données elles-mêmes constituent un modèle qui servira de référence pour la prédiction lors des futures phases d’entraînement. Par conséquent, il est efficace en termes de temps, permettant une improvisation rapide pour une modélisation aléatoire sur les données disponibles.
KNN ne nécessite que deux hyperparamètres, une valeur K et une métrique de distance, ce qui le rend plus simple à régler que d’autres algorithmes d’apprentissage automatique.
La plupart des algorithmes de classification sont faciles à implémenter pour les problèmes de classification binaire, mais nécessitent des efforts supplémentaires pour les problèmes multi-classes. En revanche, KNN s’adapte aux problèmes multi-classes sans aucun effort supplémentaire.
Mécanisme principal
Le mécanisme principal de l’algorithme KNN consiste à identifier les K plus proches voisins d’un point de données donné et à utiliser leurs étiquettes de classe pour effectuer une prédiction. Pour les tâches de classification, l’algorithme attribue la classe la plus courante parmi les K plus proches voisins. Pour les tâches de régression, il calcule la moyenne des valeurs des K plus proches voisins afin de prédire la valeur du nouveau point de données. Cette approche est largement utilisée dans divers domaines en raison de sa simplicité et de son efficacité, lui permettant de traiter facilement à la fois les problèmes de classification et de régression.
Évaluation des métriques de performance
Lors de l’évaluation des modèles KNN, tenez compte de plusieurs métriques au-delà de la simple précision :
Précision : La proportion de prédictions correctes.
Précision positive : La proportion d’identifications positives qui étaient effectivement correctes.
Rappel : La proportion de positifs réels qui ont été correctement identifiés.
Score F1 : La moyenne harmonique de la précision et du rappel.
Matrice de confusion : Un tableau montrant les classifications correctes et incorrectes pour chaque classe.
Courbe ROC et AUC : Pour la classification binaire, montrant le compromis entre le taux de vrais positifs et le taux de faux positifs.
Conseils pour passer à l’échelle avec des jeux de données plus volumineux
KNN peut devenir coûteux en calcul avec de grands jeux de données. Voici quelques stratégies pour améliorer l’efficacité :
Utiliser des algorithmes de voisins les plus proches approximatifs : Des algorithmes comme le hachage sensible à la localité (LSH) peuvent trouver des voisins les plus proches approximatifs beaucoup plus rapidement que les méthodes exactes.
Implémenter des variantes de KNN pour l’efficacité : Des structures de données comme les arbres KD et les ball trees organisent les données pour rendre la recherche de voisins les plus proches plus efficace :
Arbres KD : Partitionnent l’espace à l’aide d’hyperplans, permettant l’élimination rapide de grandes portions de l’espace de recherche.
Ball trees : Partitionnent l’espace à l’aide d’hypersphères, ce qui peut être plus efficace que les arbres KD dans les espaces de grande dimension.
Échantillonner les données d’entraînement : Pour de très grands jeux de données, l’utilisation d’un échantillon représentatif peut réduire considérablement le temps de calcul avec un impact minimal sur la précision.
Traitement parallèle : Utiliser des processeurs multicœurs ou le calcul distribué pour accélérer les calculs de distance.
Applications concrètes
KNN est largement utilisé dans divers domaines en raison de sa simplicité et de son efficacité :
Systèmes de recommandation
KNN est la base du filtrage collaboratif dans les systèmes de recommandation. En trouvant des utilisateurs ayant des préférences similaires (voisins les plus proches), le système peut recommander des éléments que ces utilisateurs similaires ont aimés mais que l’utilisateur cible n’a pas encore vus.
Étude de cas : Recommandation de films
Un service de streaming pourrait utiliser KNN pour recommander des films aux utilisateurs en fonction de leur historique de visionnage. L’algorithme trouverait des utilisateurs ayant des habitudes de visionnage similaires et recommanderait des films que ces utilisateurs similaires ont appréciés mais que l’utilisateur cible n’a pas encore regardés.
Diagnostic médical
KNN peut aider au diagnostic médical en trouvant des patients présentant des symptômes ou des résultats de tests similaires et en utilisant leurs diagnostics pour prédire le diagnostic d’un nouveau patient.
Étude de cas : Prédiction du diabète
À l’aide de caractéristiques comme le taux de glucose, l’IMC, l’âge et la pression artérielle, KNN peut classer si un patient est susceptible d’être diabétique en comparant ses mesures à celles de patients dont les diagnostics sont connus.
Reconnaissance d’images
En vision par ordinateur, KNN peut être utilisé pour la classification d’images en comparant des vecteurs de caractéristiques extraits des images.
Exemple de projet : Reconnaissance de chiffres manuscrits
À l’aide du jeu de données MNIST, nous pouvons implémenter KNN pour reconnaître des chiffres manuscrits. Chaque image est représentée comme un vecteur de valeurs de pixels, et l’algorithme classe les nouvelles images en fonction de leur similarité avec les images d’entraînement.
Détection d’anomalies
KNN peut identifier des anomalies ou des valeurs aberrantes en trouvant des points qui sont éloignés de leurs voisins les plus proches.
Exemple d’implémentation : Détection de fraude à la carte bancaire
En calculant la distance moyenne au knn pour chaque transaction, celles présentant des distances anormalement élevées peuvent être signalées comme des fraudes potentielles.
Recherche de similarité vectorielle
Dans les espaces vectoriels de grande dimension comme ceux utilisés en NLP et en vision par ordinateur, KNN peut trouver efficacement des éléments similaires. Cela est particulièrement précieux dans des applications telles que :
Recherche de similarité d’images
Regroupement de documents
Appariement d’entités
Pour ces applications, les bases de données vectorielles spécialisées peuvent améliorer considérablement les performances par rapport aux bases de données traditionnelles, en particulier lorsqu’il s’agit de données de grande dimension où le calcul de similarité est intensif en calcul.
Limites et alternatives
Quand KNN échoue
Malgré sa simplicité et son efficacité, KNN présente plusieurs limites :
Coûteux en calcul : Pour les grands jeux de données, calculer les distances entre toutes les paires de points peut être prohibitif.
La malédiction de la dimensionnalité : Dans les espaces à haute dimension, le concept de distance devient moins significatif, ce qui rend KNN moins efficace.
Données déséquilibrées : KNN peut être biaisé en faveur de la classe majoritaire dans les jeux de données déséquilibrés.
Sensible au bruit et aux caractéristiques non pertinentes : Comme KNN repose sur des calculs de distance, les caractéristiques bruitées ou non pertinentes peuvent avoir un impact significatif sur ses performances.
Gourmand en mémoire : KNN nécessite de stocker l’ensemble du jeu de données d’entraînement en mémoire.
Avantages de KNN
Malgré ces limites, KNN offre plusieurs avantages :
Aucune période d’entraînement : Le modèle KNN n’implique aucune période d’entraînement, puisque les données elles-mêmes constituent le modèle. Cela le rend efficace en temps, permettant une improvisation rapide pour une modélisation aléatoire sur les données disponibles.
Réglage simple des hyperparamètres : KNN ne nécessite que deux hyperparamètres principaux — une valeur k et une métrique de similarité — ce qui le rend plus simple à régler que de nombreux autres algorithmes d’apprentissage automatique.
Prise en charge naturelle du multi-classe : Contrairement à de nombreux algorithmes de classification qui nécessitent un effort supplémentaire pour être implémentés dans des problèmes multi-classes, KNN s’adapte aux problèmes multi-classes sans complexité additionnelle.
Nature non paramétrique : KNN ne fait aucune hypothèse sur la distribution sous-jacente des données, ce qui lui permet de capturer des motifs complexes que les modèles paramétriques pourraient manquer.
Considérations sur la complexité computationnelle
Complexité temporelle pour la prédiction : O(MN log(k)) pour chaque prédiction, où M est la dimension des données (nombre de caractéristiques) et N est la taille ou le nombre d’instances dans le jeu de données d’entraînement. Cela s’explique par :
Le calcul des distances entre le point de requête et tous les points d’entraînement : O(MN)
La recherche des knn (généralement à l’aide d’un tri partiel) : O(N log(k))
Complexité spatiale : O(MN) pour stocker le jeu de données d’entraînement.
Cette complexité computationnelle peut rendre KNN impraticable pour les grands jeux de données sans optimisation. Cependant, il existe des structures de données et des algorithmes spécialisés qui peuvent rendre KNN plus efficace même pour les grands jeux de données.
Algorithmes alternatifs
Lorsque KNN n’est pas adapté, envisagez ces alternatives :
Arbres de décision et Random Forests : Gèrent mieux les caractéristiques non pertinentes et peuvent fournir l’importance des caractéristiques.
Support Vector Machines (SVM) : Plus efficaces dans les espaces à haute dimension et avec des frontières de décision complexes.
Naive Bayes : Efficace en calcul et fonctionne bien avec les données à haute dimension.
Réseaux de neurones : Capables d’apprendre des motifs complexes, mais nécessitent davantage de données et de ressources de calcul.
Approches hybrides
Combiner KNN avec d’autres algorithmes peut surmonter certaines de ses limites :
KNN avec sélection/extraction de caractéristiques : Appliquez des techniques de sélection de caractéristiques avant d’utiliser KNN afin de réduire la dimensionnalité.
Méthodes d’ensemble : Combinez KNN avec d’autres algorithmes par vote ou stacking.
Régression pondérée locale : Utilisez KNN pour identifier des voisinages locaux, puis appliquez une régression au sein de chaque voisinage.
Conclusion et ressources supplémentaires
K-Nearest Neighbors est un algorithme puissant et intuitif qui exploite le concept simple selon lequel des instances similaires tendent à avoir des résultats similaires. Malgré sa simplicité, KNN peut être très efficace lorsqu’il est correctement implémenté, avec un prétraitement approprié, une sélection de paramètres adéquate et des techniques d’optimisation.
Points clés à retenir
KNN est un algorithme d’apprentissage non paramétrique, basé sur les instances, qui peut être utilisé à la fois pour des tâches de classification et de régression.
Le choix de la métrique de similarité et la valeur de k sont essentiels pour les performances de KNN.
La mise à l’échelle des caractéristiques est essentielle avant d’appliquer KNN afin de garantir que toutes les caractéristiques contribuent de manière égale aux calculs de distance.
KNN peut souffrir du fléau de la dimensionnalité et peut être coûteux en calcul pour de grands ensembles de données.
Des implémentations efficaces utilisant des arbres KD ou des arbres de boules peuvent améliorer considérablement les performances.
Orientations futures pour la recherche sur KNN
Malgré sa simplicité et son efficacité, l’algorithme KNN présente plusieurs limites, telles que la sensibilité au bruit et aux valeurs aberrantes, un coût de calcul élevé et le besoin d’une mémoire substantielle pour stocker les données d’entraînement. Les orientations futures de la recherche sur KNN comprennent le développement d’algorithmes plus efficaces pour gérer de grands ensembles de données, l’amélioration de la robustesse au bruit et aux valeurs aberrantes, ainsi que l’exploration de nouvelles métriques de similarité et de nouveaux schémas de pondération. De plus, les chercheurs étudient l’intégration de KNN avec des technologies émergentes comme l’apprentissage profond, le traitement du langage naturel et la vision par ordinateur. En relevant ces défis et en élargissant ses applications, le développement continu de l’algorithme KNN aura un impact significatif sur le domaine de la science des données, garantissant sa pertinence et son utilité dans la résolution de problèmes complexes.
Articles académiques et ressources
Pour ceux qui souhaitent approfondir KNN et ses variantes, consultez ces ressources :
Cover, T. M., & Hart, P. E. (1967). "Nearest neighbor pattern classification." IEEE Transactions on Information Theory, 13(1), 21-27.
Altman, N. S. (1992). "An introduction to kernel and nearest-neighbor nonparametric regression." The American Statistician, 46(3), 175-185.
Weinberger, K. Q., & Saul, L. K. (2009). "Distance metric learning for large margin nearest neighbor classification." Journal of Machine Learning Research, 10, 207-244.
Cours et tutoriels en ligne
Coursera : Machine Learning by Andrew Ng
Kaggle : Feature Engineering and KNN
Documentation scikit-learn : Nearest Neighbors
En comprenant en profondeur l’algorithme KNN, les détails de son implémentation et les techniques d’optimisation, vous ajouterez à votre boîte à outils d’apprentissage automatique un outil polyvalent et puissant pouvant être appliqué dans de nombreux domaines.
Continuer à lire
VDBBench Adds Cost-Aware Benchmarking for Vector Databases
Compare Zilliz Cloud, Pinecone, and turbopuffer with VDBBench cost-aware vector database benchmarks across latency, freshness, multitenancy, and cold starts.
Similarity Metrics for Vector Search
Exploring five similarity metrics for vector search: L2 or Euclidean distance, cosine distance, inner product, and hamming distance.
Introducing DeepSearcher: A Local Open Source Deep Research
In contrast to OpenAI’s Deep Research, this example ran locally, using only open-source models and tools like Milvus and LangChain.