Qu'est-ce que le voisin le plus proche K ? Un algorithme ML pour classer les données

Les algorithmes sont le moteur du monde de l'apprentissage automatique.

Ils sont souvent loués pour leurs capacités prédictives et considérés comme des travailleurs acharnés qui consomment d'énormes quantités de données pour produire des résultats instantanés.

Parmi eux, il y a un algorithme souvent qualifié de paresseux. Mais c'est assez performant quand il s'agit de classer les points de données. C'est ce qu'on appelle l'algorithme des k plus proches voisins et il est souvent cité comme l'un des plus importants.   apprentissage automatique   algorithmes.

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

L' algorithme des k plus proches voisins (KNN) est une méthode de classification des données permettant d'estimer la probabilité qu'un point de données devienne membre d'un groupe ou d'un autre en fonction du groupe auquel appartiennent les points de données les plus proches.

L'algorithme du k plus proche voisin est un type de   apprentissage automatique supervisé   algorithme utilisé pour résoudre les problèmes de classification et de régression. Cependant, il est principalement utilisé pour des problèmes de classification.

KNN est un apprentissage paresseux et un algorithme non paramétrique .

C'est ce qu'on appelle un algorithme d'apprentissage paresseux ou un apprenant paresseux, car il n'effectue aucune formation lorsque vous fournissez les données de formation. Au lieu de cela, il stocke simplement les données pendant le temps de formation et n'effectue aucun calcul. Il ne construit pas de modèle tant qu'une requête n'est pas effectuée sur l'ensemble de données. Cela rend KNN idéal pour   fouille de données.

Elle est considérée comme une méthode non paramétrique car elle ne fait aucune hypothèse sur la distribution des données sous-jacentes. En termes simples, KNN essaie de déterminer à quel groupe appartient un point de données en examinant les points de données qui l'entourent.

Considérez qu'il y a deux groupes, A et B.

Pour déterminer si un point de données appartient au groupe A ou au groupe B, l'algorithme examine les états des points de données à proximité. Si la majorité des points de données sont dans le groupe A, il est très probable que le point de données en question soit dans le groupe A et vice versa.

En bref, KNN consiste à classer un point de données en examinant le point de données annoté le plus proche, également appelé voisin le plus proche .

Ne confondez pas la classification K-NN avec le clustering K-means. KNN est un algorithme de classification supervisée qui classe les nouveaux points de données en fonction des points de données les plus proches. D'autre part, le clustering K-means est un   sans surveillance   algorithme de clustering qui regroupe les données en un nombre K de clusters.

Comment fonctionne KNN ?

Comme mentionné ci-dessus, l'algorithme KNN est principalement utilisé comme classificateur. Voyons comment fonctionne KNN pour classer les points de données d'entrée invisibles.

Contrairement à la classification utilisant des réseaux de neurones artificiels, la classification des k plus proches voisins est facile à comprendre et simple à mettre en œuvre. Il est idéal dans les situations où les points de données sont bien définis ou non linéaires.

Essentiellement, KNN exécute un mécanisme de vote pour déterminer la classe d'une observation invisible. Cela signifie que la classe avec le vote majoritaire deviendra la classe du point de données en question.

Si la valeur de K est égale à un, nous n'utiliserons que le voisin le plus proche pour déterminer la classe d'un point de données. Si la valeur de K est égale à dix, alors nous utiliserons les dix voisins les plus proches, et ainsi de suite.

Pour mettre cela en perspective, considérons un point de données non classé X. Il existe plusieurs points de données avec des catégories connues, A et B, dans un nuage de points.

Supposons que le point de données X soit placé près du groupe A.

Comme vous le savez, nous classons un point de données en regardant les points annotés les plus proches. Si la valeur de K est égale à un, nous n'utiliserons qu'un seul voisin le plus proche pour déterminer le groupe du point de données.

Dans ce cas, le point de données X appartient au groupe A car son voisin le plus proche est dans le même groupe. Si le groupe A a plus de dix points de données et que la valeur de K est égale à 10, alors le point de données X appartiendra toujours au groupe A car tous ses voisins les plus proches sont dans le même groupe.

Supposons qu'un autre point de données non classé Y soit placé entre le groupe A et le groupe B. Si K est égal à 10, nous choisissons le groupe qui obtient le plus de votes, ce qui signifie que nous classons Y dans le groupe dans lequel il a le plus de voisins. Par exemple, si Y a sept voisins dans le groupe B et trois voisins dans le groupe A, il appartient au groupe B.

Le fait que le classificateur attribue la catégorie avec le plus grand nombre de votes est vrai quel que soit le nombre de catégories présentes.

Vous vous demandez peut-être comment la métrique de distance est calculée pour déterminer si un point de données est un voisin ou non.

Il existe quatre façons de calculer la distance entre le point de données et son voisin le plus proche : distance euclidienne , distance de Manhattan , distance de Hamming et distance de Minkowski . Sur les trois, la distance euclidienne est la fonction ou la métrique de distance la plus couramment utilisée.

Pour valider l'exactitude de la classification KNN, un   matrice de confusion   est utilisé. D'autres méthodes statistiques telles que le test du rapport de vraisemblance sont également utilisées pour la validation.

Dans le cas de la régression KNN, la majorité des étapes sont les mêmes. Au lieu d'attribuer la classe avec les votes les plus élevés, la moyenne des valeurs des voisins est calculée et attribuée au point de données inconnu.

Pourquoi utiliser l'algorithme KNN ?

La classification est un problème critique en science des données et en apprentissage automatique. Le KNN est l'un des algorithmes les plus anciens et les plus précis utilisés pour la classification des modèles et les modèles de régression.

Voici quelques-uns des domaines dans lesquels l'algorithme du k plus proche voisin peut être utilisé :

• Cote de crédit : l'algorithme KNN aide à déterminer la cote de crédit d'un individu en le comparant à ceux qui présentent des caractéristiques similaires.
• Approbation de prêt : Semblable à la cote de crédit, l'algorithme du k plus proche voisin est bénéfique pour identifier les personnes les plus susceptibles de ne pas rembourser leurs prêts en comparant leurs caractéristiques avec des personnes similaires.
• Prétraitement des données : les ensembles de données peuvent avoir de nombreuses valeurs manquantes. L'algorithme KNN est utilisé pour un processus appelé imputation des données manquantes qui estime les valeurs manquantes.
• Reconnaissance de formes : La capacité de l'algorithme KNN à identifier des formes crée un large éventail d'applications. Par exemple, il aide à détecter les modèles d'utilisation des cartes de crédit et à repérer les modèles inhabituels. La détection de modèles est également utile pour identifier des modèles dans le comportement d'achat des clients.
• Prévision du cours des actions : étant donné que l'algorithme KNN a le don de prédire les valeurs d'entités inconnues, il est utile pour prédire la valeur future des actions sur la base de données historiques.
• Systèmes de recommandation : Étant donné que KNN peut aider à trouver des utilisateurs de caractéristiques similaires, il peut être utilisé dans les systèmes de recommandation. Par exemple, il peut être utilisé dans une plateforme de streaming vidéo en ligne pour suggérer du contenu qu'un utilisateur est plus susceptible de regarder en analysant ce que des utilisateurs similaires regardent.
• Vision par ordinateur : L'algorithme KNN est utilisé pour la classification des images. Puisqu'il est capable de regrouper des points de données similaires, par exemple, de regrouper des chats et des chiens dans une classe différente, il est utile dans plusieurs   vision par ordinateur   applications.

Comment choisir la valeur optimale de K

Il n'y a pas de manière spécifique de déterminer la meilleure valeur K - en d'autres termes - le nombre de voisins dans KNN. Cela signifie que vous devrez peut-être expérimenter quelques valeurs avant de décider laquelle choisir.

Une façon de le faire est de considérer (ou de prétendre) qu'une partie des échantillons d'apprentissage est "inconnue". Ensuite, vous pouvez catégoriser les données inconnues dans l'ensemble de test à l'aide de l'algorithme des k plus proches voisins et analyser la qualité de la nouvelle catégorisation en la comparant aux informations que vous avez déjà dans les données d'apprentissage.

Lorsqu'il s'agit d'un problème à deux classes, il est préférable de choisir une valeur impaire pour K. Sinon, un scénario peut survenir où le nombre de voisins dans chaque classe est le même. De plus, la valeur de K ne doit pas être un multiple du nombre de classes présentes.

Une autre façon de choisir la valeur optimale de K consiste à calculer le sqrt(N), où N désigne le nombre d'échantillons dans l'ensemble de données d'apprentissage.

Cependant, K avec des valeurs inférieures, telles que K = 1 ou K = 2, peut être bruité et soumis aux effets des valeurs aberrantes. Le risque de surajustement est également élevé dans de tels cas.

D'un autre côté, K avec des valeurs plus grandes, dans la plupart des cas, donnera lieu à des frontières de décision plus lisses, mais elles ne devraient pas être trop grandes. Sinon, les groupes avec un nombre inférieur de points de données seront toujours mis en minorité par les autres groupes. De plus, un K plus grand sera coûteux en calcul.

Avantages et inconvénients de KNN

L'un des avantages les plus importants de l'utilisation de l'algorithme KNN est qu'il n'est pas nécessaire de créer un modèle ou d'ajuster plusieurs paramètres. Puisqu'il s'agit d'un algorithme d'apprentissage paresseux et non d'un apprenant avide, il n'est pas nécessaire de former le modèle ; à la place, tous les points de données sont utilisés au moment de la prédiction.

Bien sûr, c'est coûteux en temps de calcul et en temps. Mais si vous disposez des ressources de calcul nécessaires, vous pouvez utiliser KNN pour résoudre les problèmes de régression et de classification. Cependant, il existe plusieurs algorithmes plus rapides qui peuvent produire des prédictions précises.

Bien sûr, KNN n'est pas un algorithme d'apprentissage automatique parfait. Étant donné que le prédicteur KNN calcule tout à partir de zéro, il n'est peut-être pas idéal pour les grands ensembles de données.

KNN et la malédiction de la dimensionnalité

Lorsque vous avez d'énormes quantités de données à portée de main, il peut être assez difficile d'en extraire des informations rapides et simples. Pour cela, nous pouvons utiliser des algorithmes de réduction de dimensionnalité qui, essentiellement, font en sorte que les données "aillent directement au point".

Le terme "malédiction de la dimensionnalité" pourrait donner l'impression qu'il sort tout droit d'un film de science-fiction. Mais cela signifie que les données ont trop de fonctionnalités.

Si les données comportent trop de fonctionnalités, il existe un risque élevé de sur-ajustement du modèle, conduisant à des modèles inexacts. Trop de dimensions compliquent également le regroupement des données, car chaque échantillon de données de l'ensemble de données apparaîtra à égale distance les uns des autres.

L'algorithme des k plus proches voisins est très sensible au surajustement en raison de la malédiction de la dimensionnalité. Cependant, ce problème peut être résolu avec le   implémentation de la force brute   de l'algorithme KNN. Mais ce n'est pas pratique pour les grands ensembles de données.

KNN ne fonctionne pas bien s'il y a trop de fonctionnalités. Par conséquent, des techniques de réduction de la dimensionnalité telles que l'analyse en composantes principales (ACP) et la sélection des caractéristiques doivent être effectuées pendant la phase de préparation des données.

KNN : l'algorithme paresseux qui a conquis les cœurs

Bien qu'il soit le plus paresseux parmi les algorithmes, KNN s'est bâti une réputation impressionnante et est un algorithme incontournable pour plusieurs problèmes de classification et de régression. Bien sûr, en raison de sa paresse, ce n'est peut-être pas le meilleur choix pour les cas impliquant de grands ensembles de données. Mais c'est l'un des algorithmes les plus anciens, les plus simples et les plus précis.

La formation et la validation d'un algorithme avec une quantité limitée de données peuvent être une tâche herculéenne. Mais il existe un moyen de le faire efficacement. C'est ce qu'on appelle la validation croisée et implique de réserver une partie des données d'apprentissage en tant qu'ensemble de données de test.