K-Plus Proches Voisins

L’algorithme des k-plus proches voisins (KNN) est un algorithme d’apprentissage supervisé non paramétrique utilisé pour les tâches de classification et de régression en apprentissage automatique. Il est basé sur le concept de proximité, supposant que des points de données similaires sont situés près les uns des autres. KNN est un algorithme d’apprentissage paresseux, ce qui signifie qu’il ne nécessite pas de phase d’entraînement et effectue ses prédictions en stockant l’ensemble du jeu de données d’entraînement et en l’utilisant pour déterminer la classe ou la valeur des nouveaux points de données. L’algorithme prédit le résultat pour un point de test en identifiant les ‘k’ points de données d’entraînement les plus proches du point testé et en déduit la sortie en fonction de ces voisins. Cette méthode est très intuitive et imite les stratégies de perception humaine qui consistent à comparer de nouvelles données à des exemples connus.

Comment fonctionne le KNN

KNN fonctionne en identifiant les ‘k’ points de données les plus proches d’un point de requête donné et en utilisant ces voisins pour faire une prédiction.

• Pour les tâches de classification, l’algorithme assigne le point de requête à la classe la plus commune parmi ses ‘k’ plus proches voisins, ce qui correspond au vote majoritaire. Le vote majoritaire dans le KNN peut être compris comme un “vote de pluralité” lorsqu’il y a plusieurs classes, où le point de requête est attribué à la classe ayant le plus grand nombre de voisins, même si cela ne constitue pas une majorité absolue.
• Pour les tâches de régression, il prédit la valeur en faisant la moyenne des valeurs des ‘k’ plus proches voisins.

Les principes de proximité et de similarité, qui sont au cœur de la perception humaine, sont également centraux dans le fonctionnement du KNN, car les points de données proches dans l’espace des caractéristiques sont supposés plus similaires et donc susceptibles d’avoir des résultats similaires.

Mesures de distance

Pour déterminer les voisins les plus proches, KNN utilise diverses mesures de distance, essentielles pour ses performances :

• Distance Euclidienne : La distance à vol d’oiseau entre deux points dans un espace multidimensionnel, couramment utilisée pour les variables continues. C’est la mesure de distance la plus courante pour le KNN et elle est particulièrement utile lorsque les données sont denses et continues.
• Distance de Manhattan : Également appelée distance de taxi, elle calcule la distance en sommant les différences absolues entre les coordonnées de deux points. Elle est utile dans les scénarios de déplacement en grille où les mouvements sont contraints à des directions orthogonales.
• Distance de Minkowski : Une forme généralisée des distances euclidienne et Manhattan, paramétrée par ‘p’. Si p=1, cela devient la distance de Manhattan, et si p=2, cela devient la distance euclidienne. Cette mesure offre une flexibilité selon la valeur de ‘p’ choisie.
• Distance de Hamming : Utilisée pour les données catégorielles, elle compte le nombre de bits différents entre deux vecteurs binaires. Ceci est particulièrement utile dans les problèmes de classification binaire où les attributs ont des valeurs binaires.

Choisir la bonne valeur de ‘k’

Le paramètre ‘k’ dans KNN représente le nombre de voisins à considérer. Choisir la bonne valeur de ‘k’ est crucial :

• Un petit ‘k’ peut conduire à un surapprentissage, où le modèle est trop sensible au bruit dans les données d’entraînement, capturant des motifs artificiels qui ne se généralisent pas.
• Un grand ‘k’ peut entraîner un sous-apprentissage, où le modèle devient trop général et ignore des motifs importants, menant à une mauvaise performance prédictive.
• Typiquement, ‘k’ est choisi par validation croisée et doit être un nombre impair pour éviter les égalités dans les décisions de classification. Le choix de ‘k’ peut avoir un impact significatif sur la précision du modèle et est souvent déterminé empiriquement.

Avantages et inconvénients

Avantages

• Simple et intuitif : Facile à comprendre et à mettre en œuvre, ce qui en fait un bon choix pour les débutants. La simplicité du KNN réside dans son approche directe de comparaison des instances de test avec les exemples stockés.
• Pas de phase d’entraînement : KNN ne nécessite pas de phase d’entraînement explicite, puisqu’il fait des prédictions en utilisant le jeu de données stocké. Cela signifie que le modèle peut être mis à jour simplement en ajoutant de nouveaux points de données.
• Polyvalent : Peut être utilisé aussi bien pour la classification que pour la régression, et son application est large dans différents domaines. Il est également utile pour les problèmes de classification multi-étiquettes.

Inconvénients

• Intensif en calcul : Comme il nécessite de stocker et de comparer chaque nouveau point de données à l’ensemble du jeu de données, il peut être lent et gourmand en ressources, en particulier avec de grands ensembles de données. La complexité temporelle du KNN est O(n), où n est le nombre d’échantillons d’entraînement.
• Sensible aux valeurs aberrantes : La présence de valeurs aberrantes peut fortement impacter les prédictions, car ces points anormaux peuvent fausser les résultats, notamment lorsque ‘k’ est faible.
• Malédiction de la dimensionnalité : Dans les espaces de haute dimension, les performances de l’algorithme peuvent se dégrader car les distances entre les points deviennent moins significatives. À mesure que la dimension augmente, le volume de l’espace augmente, rendant les données plus clairsemées. Cette rareté complique la recherche de voisins proches par le KNN.

Cas d’utilisation

KNN est utilisé dans divers domaines grâce à sa simplicité et son efficacité :

• Systèmes de recommandation : Utilisé pour recommander des produits ou du contenu aux utilisateurs sur la base des préférences d’utilisateurs similaires. KNN peut aider à identifier des utilisateurs ou objets similaires en évaluant la similarité des caractéristiques.
• Reconnaissance de formes : Employé dans la reconnaissance d’écriture manuscrite et d’autres tâches de reconnaissance de formes, où il peut classer les images selon la similarité des valeurs de pixels.
• Imputation de données : Utile pour remplir les valeurs manquantes dans les ensembles de données en les estimant à partir de points similaires, ce qui permet de préserver l’intégrité des données.
• Finance et santé : Appliqué dans la prédiction des marchés boursiers, l’évaluation des risques et le diagnostic médical en analysant les similarités dans les données historiques. En santé, il peut prédire des diagnostics de patients en comparant les symptômes à des cas connus.

Implémentation en Python

KNN peut être implémenté à l’aide de bibliothèques comme scikit-learn en Python. Voici un exemple de base d’utilisation du KNN pour la classification :

from sklearn.neighbors import KNeighborsClassifier
from sklearn.model_selection import train_test_split
from sklearn.datasets import load_iris
from sklearn.metrics import accuracy_score

# Charger le jeu de données
iris = load_iris()
X, y = iris.data, iris.target

# Diviser les données en ensembles d’entraînement et de test
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)

# Initialiser le classificateur KNN avec k=3
knn = KNeighborsClassifier(n_neighbors=3)

# Ajuster le modèle
knn.fit(X_train, y_train)

# Faire des prédictions
y_pred = knn.predict(X_test)

# Évaluer la précision
accuracy = accuracy_score(y_test, y_pred)
print(f"Accuracy: {accuracy:.2f}")

K-Plus Proches Voisins (KNN) en recherche scientifique

K-Plus Proches Voisins (KNN) est un algorithme fondamental utilisé dans de nombreux domaines tels que la recherche d’information multimédia, l’exploration de données et l’apprentissage automatique, en particulier dans le contexte de grands ensembles de données.

Articles de recherche notables :

• « Approximate k-NN Graph Construction: a Generic Online Approach » par Wan-Lei Zhao et al. :
  Présente une méthode efficace pour la recherche de k-plus proches voisins approximatifs et la construction de graphes. L’article démontre une solution dynamique et réalisable pour gérer différentes échelles et dimensions de données, prenant en charge des mises à jour en ligne qui ne sont pas possibles dans de nombreuses méthodes existantes. En savoir plus.

• « Parallel Nearest Neighbors in Low Dimensions with Batch Updates » par Magdalen Dobson et Guy Blelloch :
  Introduit des algorithmes parallèles combinant kd-tree et l’ordre de Morton dans une structure de zad-tree, optimisée pour les données de basse dimension. Les auteurs démontrent que leur approche est plus rapide que les algorithmes existants, réalisant d’importants gains de performance grâce au traitement parallèle. Le zad-tree prend en charge de façon unique les mises à jour dynamiques en lots en parallèle, une première dans les structures de données k-plus proches voisins. En savoir plus.

• « Twin Neural Network Improved k-Nearest Neighbor Regression » par Sebastian J. Wetzel :
  Explore une nouvelle approche de la régression k-plus proches voisins en utilisant des réseaux neuronaux jumeaux. Cette méthode se concentre sur la prédiction des différences entre les cibles de régression, menant à de meilleures performances que les réseaux neuronaux traditionnels et les techniques classiques de régression k-plus proches voisins sur de petits à moyens ensembles de données. En savoir plus.