Qu'est-ce que l'algorithme des k plus proches voisins ?

Découvrez l'algorithme des k plus proches voisins, l'un des discriminants de classification et de régression les plus populaires et les plus simples utilisés aujourd'hui dans l'apprentissage automatique

Vue arrière du code d'écriture d'un développeur

Algorithme des k plus proches voisins

L'algorithme des k plus proches voisins, également connu sous le nom de KNN ou k-NN, est un discriminant d'apprentissage supervisé non paramétrique, qui utilise la proximité pour effectuer des classifications ou des prédictions sur le regroupement d'un point de données individuel. Bien qu'il puisse être utilisé pour des problèmes de régression ou de classification, il est généralement utilisé comme algorithme de classification, en partant de l'hypothèse que des points similaires peuvent être trouvés les uns à côté des autres.


Pour les problèmes de classification, un libellé de classe est affecté sur la base d'un vote à la majorité : le libellé de classe le plus fréquemment représenté autour d'un point de données donné est utilisé. Bien que cela soit techniquement considéré comme un « vote à la majorité », le terme « vote majoritaire » est plus couramment utilisé dans la littérature. La distinction entre ces terminologies est que le « vote à la majorité » nécessite techniquement une majorité supérieure à 50 %, ce qui fonctionne principalement lorsqu'il n'y a que deux catégories. Lorsque vous avez plusieurs classes, par ex. quatre catégories, vous n'avez pas nécessairement besoin de 50 % des voix pour tirer une conclusion sur une classe ; vous pouvez affecter un libellé de classe avec un vote supérieur à 25 %. L'Université du Wisconsin-Madison résume bien cela avec un exemple  ici (PDF, 1,2 Mo) (lien externe à ibm.com). 

Les problèmes de régression utilisent un concept similaire à celui des problèmes de classification, mais dans ce cas, la moyenne des k plus proches voisins est utilisée pour faire une prédiction sur une classification. La principale distinction ici est que la classification est utilisée pour les valeurs discrètes, tandis que la régression est utilisée pour les valeurs continues. Cependant, avant qu'une classification puisse être effectuée, la distance doit être définie. La distance euclidienne est la plus couramment utilisée, et nous l'aborderons plus en détail ci-dessous.
Il convient également de noter que l'algorithme KNN fait également partie d'une famille de modèles « d'apprentissage paresseux », ce qui signifie qu'il ne stocke qu'un jeu de données d'apprentissage au lieu d'effectuer une phase d'entraînement. Cela signifie également que tous les calculs ont lieu lorsqu'une classification ou une prédiction est effectuée. Puisqu'il s'appuie fortement sur la mémoire pour stocker toutes ses données d'entraînement, il est également appelé méthode d'apprentissage basée sur les instances ou basée sur la mémoire.
Evelyn Fix et Joseph Hodges sont à l'origine des idées initiales autour du modèle KNN dans cet  article de 1951 (PDF, 1,1 Mo) (lien externe à ibm.com) tandis que Thomas Cover a développé leur concept dans ses recherches (PDF, 1 Mo) (lien externe à ibm.com), « Classification des modèles de voisins les plus proches ». Bien qu'il ne soit plus aussi populaire qu'avant, il reste l'un des premiers algorithmes que l'on apprend en science des données en raison de sa simplicité et de sa précision. Cependant, à mesure qu'un jeu de données grandit, KNN devient de plus en plus inefficace, compromettant la performance globale du modèle. Il est couramment utilisé pour les systèmes de recommandation simples, la reconnaissance de modèle, la fouille de données, les prévisions des marchés financiers, la détection d'intrusion, etc. 


Calculer KNN : mesures de distance

Pour récapituler, l'objectif de l'algorithme des k plus proches voisins est d'identifier les voisins les plus proches d'un point de requête donné, afin que nous puissions attribuer un libellé de classe à ce point. Pour ce faire, KNN a quelques exigences :

Déterminez vos mesures de distance

Afin de déterminer quels points de données sont les plus proches d'un point de requête donné, il vous faudra calculer la distance entre le point de requête et les autres points de données. Ces mesures de distance aident à former des limites de décision, qui partitionnent les points de requête en différentes régions. Vous verrez généralement des limites de décision visualisées avec les diagrammes de Voronoi.

Bien que vous puissiez choisir parmi plusieurs mesures de distance, cet article ne couvrira que les suivantes :

Distance euclidienne (p=2) :  il s'agit de la mesure de distance la plus couramment utilisée, et elle est limitée aux vecteurs à valeurs réelles. En utilisant la formule ci-dessous, elle mesure une ligne droite entre le point de requête et l'autre point mesuré.

Distance de Manhattan (p=1) : il s'agit également d'une autre mesure de distance populaire, qui mesure la valeur absolue entre deux points. Elle est également appelée taxi-distance, ou distance d'un pâté de maisons, car elle est généralement visualisée avec une grille, qui montre comment on peut naviguer d'une adresse à une autre via les rues de la ville.

Distance de Minkowski : cette mesure de distance est la forme généralisée de la mesure de distance euclidienne et de celle de Manhattan. Le paramètre, p, dans la formule ci-dessous, permet la création d'autres mesures de distance. La distance euclidienne est représentée par cette formule lorsque p est égal à deux, et la distance de Manhattan est notée avec p égal à un.

Distance de Hamming : cette technique est généralement utilisée avec des vecteurs booléens ou de chaîne, identifiant les points où les vecteurs ne correspondent pas. De fait, elle a également été appelée la mesure de chevauchement. Elle peut être représentée par la formule suivante :

Par exemple, si vous aviez les chaînes suivantes, la distance de Hamming serait de 2, car seules deux des valeurs diffèrent.


Calculer KNN : définir k

La valeur k dans l'algorithme k-NN définit le nombre de voisins qui seront vérifiés pour déterminer la classification d'un point de requête spécifique. Par exemple, si k=1, l'instance sera affectée à la même classe que son seul voisin le plus proche. Définir k peut être un acte d'équilibrage, car différentes valeurs peuvent conduire à un surajustement ou à un sous-ajustement. Des valeurs inférieures de k peuvent avoir un écart élevé, mais un biais faible, et des valeurs plus élevées de k peuvent entraîner un biais élevé et un écart inférieur. Le choix de k dépendra en grande partie des données d'entrée, car les données avec plus de valeurs aberrantes ou de bruit fonctionneront probablement mieux avec des valeurs de k plus élevées. Dans l'ensemble, il est recommandé d'avoir un nombre impair pour k afin d'éviter les liens de classification, et les tactiques de validation croisée peuvent vous aider à choisir le k optimal pour votre jeu de données.

Algorithme des k plus proches voisins et Python

Pour approfondir le sujet, vous pouvez en savoir plus sur l'algorithme k-NN en utilisant Python et scikit-learn (également connu sous le nom de sklearn). Notre tutoriel dans Watson Studio vous aide à apprendre la syntaxe de base de cette bibliothèque, qui contient également d'autres bibliothèques populaires, telles que NumPy, Pandas et Matplotlib. Le code suivant est un exemple de création et de prédiction avec un modèle KNN :

depuis sklearn.neighbors importer KNeighborsClassifier
model_name = 'Discriminant du k plus proche voisin'
knnClassifier = KNeighborsClassifier(n_neighbors = 5, unité de mesure = 'minkowski', p=2)
knn_model = Pipeline(steps=[('preprocessor', preprocessorForFeatures), ('classifier' , knnClassifier)])
knn_model.fit(X_train, y_train)
y_pred = knn_model.predict(X_test)


Applications de k-NN dans l'apprentissage automatique

L'algorithme k-NN a été utilisé dans une variété d'applications, principalement dans le cadre de la classification. Certains de ces cas d'utilisation incluent :

Pré-traitement des données : les jeux de données ont souvent des valeurs manquantes, mais l'algorithme KNN peut estimer ces valeurs dans un processus connu sous le nom d'imputation des données manquantes.

Moteurs de recommandation : en utilisant les données de parcours de navigation des sites Web, l'algorithme KNN a été utilisé pour fournir des recommandations automatiques aux utilisateurs sur du contenu supplémentaire. Cette recherche (lien externe à ibm.com) montre qu'un utilisateur est affecté à un groupe particulier et, en fonction du comportement de l'utilisateur de ce groupe, il reçoit une recommandation. Cependant, étant donné les problèmes de mise à l'échelle avec KNN, cette approche peut ne pas être optimale pour les jeux de données plus volumineux.

Finance : il a également été utilisé dans une variété de cas d'utilisation financière et économique. Par exemple, un article (PDF, 391 Ko)  (lien externe à ibm.com) montre comment l'utilisation de KNN sur les données de crédit peut aider les banques à évaluer le risque d'un prêt à une entreprise ou à un individu. Il est utilisé pour déterminer la solvabilité d'un demandeur de prêt. Un autre journal (PDF, 447 Ko) (lien externe à ibm.com) met en évidence son utilisation dans les prévisions boursières, le change de devises, les contrats à terme et les analyses de blanchiment d'argent.

Soins de santé : KNN a également eu des applications dans l'industrie des soins de santé, en faisant des prédictions sur le risque de crises cardiaques et de cancer de la prostate. L'algorithme fonctionne en calculant les expressions géniques les plus probables.

Reconnaissance de modèle : KNN a également aidé à identifier des modèles, tels que la classification de texte et de caractères (lien externe à ibm.com). Cela a été particulièrement utile pour identifier les numéros manuscrits que vous pourriez trouver sur des formulaires ou des enveloppes postales. 


Avantages et inconvénients de l'algorithme KNN

Comme tout algorithme d'apprentissage automatique, k-NN a ses forces et ses faiblesses. Selon le projet et l'application, il peut s'avérer être le bon choix ou le mauvais.

Avantages

Facile à implémenter : compte tenu de la simplicité et de la précision de l'algorithme, c'est l'un des premiers discriminants qu'un nouveau spécialiste des données apprendra.

Il s'adapte facilement : à mesure que de nouveaux échantillons d'apprentissage sont ajoutés, l'algorithme s'ajuste pour tenir compte de toute nouvelle donnée, toutes les données d'apprentissage étant stockées en mémoire.

Peu d'hyperparamètres : KNN ne nécessite qu'une valeur k et une mesure de distance, ce qui est peu par rapport aux autres algorithmes d'apprentissage automatique.

Inconvénients

Mise à l'échelle difficile : puisque KNN est un algorithme paresseux, il utilise plus de mémoire et de stockage de données par rapport aux autres discriminants. Cela peut être coûteux en termes de temps et d'argent. Davantage de mémoire et de stockage augmenteront les dépenses de l'entreprise et plus de données peuvent prendre plus de temps à calculer. Alors que différentes structures de données, telles que Ball-Tree, ont été créées pour remédier aux inefficacités de calcul, un discriminant différent peut s'avérer idéal en fonction de la problématique métier.

Malédiction de la dimensionnalité : l'algorithme KNN a tendance à être victime de la malédiction de la dimensionnalité, ce qui signifie qu'il fonctionne mal avec des entrées de données de grande dimension. Cette dernière est aussi parfois appelée le phénomène de peaking (PDF, 340 Mo) (lien externe à ibm.com), où une fois que l'algorithme a atteint le nombre optimal de fonctions, des fonctionnalités supplémentaires augmentent le nombre d'erreurs de classification, en particulier lorsque la taille d'échantillon est plus petite.

Enclin au surajustement : en raison de la « malédiction de la dimensionnalité », KNN est également plus enclin au surajustement. Bien que les techniques de sélection des fonctions et de réduction de la dimensionnalité soient utilisées pour éviter que cela ne se produise, la valeur de k peut également avoir un impact sur le comportement du modèle. Des valeurs inférieures de k peuvent surajuster les données, tandis que des valeurs plus élevées de k ont tendance à « lisser » les valeurs de prédiction, car il calcule la moyenne des valeurs sur une plus grande zone ou sur le voisinage. Cependant, si la valeur de k est trop élevée, il peut sous-ajuster les données. 


Solutions connexes

IBM Cloud Pak for Data

IBM Cloud Pak for Data est une plateforme de données ouverte et extensible qui fournit un data fabric pour rendre toutes les données disponibles pour l'IA et l'analytique, sur n'importe quel cloud.


IBM Watson Studio

Créez, exécutez et gérez des modèles d'IA. Préparez les données et construisez des modèles dans n'importe quel cloud à l'aide d'un code source ouvert ou de la modélisation visuelle. Prévoyez et optimisez vos résultats.


IBM Db2 on Cloud

Découvrez Db2 on Cloud, une base de données cloud SQL entièrement gérée, configurée et optimisée pour des performances robustes.



Étapes suivantes

Nœud k-NN et IBM Cloud Pak for Data

Cloud Pak for Data est un ensemble d'outils qui aide à préparer les données pour la mise en œuvre de l'IA. k-NN noeud est une méthode de modélisation disponible dans IBM Cloud Pak for Data, ce qui rend le développement de modèles prédictifs très simple. Le module d'extension se déploie sur n'importe quel cloud et s'intègre de manière transparente dans votre infrastructure de cloud existante.