logo

Algorithme K-Nearest Neighbour (KNN) pour l’apprentissage automatique

  • K-Nearest Neighbour est l’un des algorithmes d’apprentissage automatique les plus simples basés sur la technique d’apprentissage supervisé.
  • L'algorithme K-NN suppose la similitude entre les nouveaux cas/données et les cas disponibles et place le nouveau cas dans la catégorie la plus similaire aux catégories disponibles.
  • L'algorithme K-NN stocke toutes les données disponibles et classe un nouveau point de données en fonction de la similarité. Cela signifie que lorsque de nouvelles données apparaissent, elles peuvent être facilement classées dans une catégorie de suite de puits en utilisant l'algorithme K-NN.
  • L'algorithme K-NN peut être utilisé pour la régression ainsi que pour la classification, mais il est principalement utilisé pour les problèmes de classification.
  • K-NN est un algorithme non paramétrique , ce qui signifie qu'il ne fait aucune hypothèse sur les données sous-jacentes.
  • On l'appelle aussi un algorithme d'apprenant paresseux car il n'apprend pas immédiatement de l'ensemble d'apprentissage, mais il stocke l'ensemble de données et au moment de la classification, il effectue une action sur l'ensemble de données.
  • L'algorithme KNN, lors de la phase de formation, stocke simplement l'ensemble de données et lorsqu'il obtient de nouvelles données, il classe ces données dans une catégorie très similaire aux nouvelles données.
  • Exemple:Supposons que nous ayons l’image d’une créature qui ressemble à un chat et à un chien, mais que nous voulions savoir s’il s’agit d’un chat ou d’un chien. Donc pour cette identification, on peut utiliser l’algorithme KNN, car il travaille sur une mesure de similarité. Notre modèle KNN trouvera les caractéristiques similaires du nouvel ensemble de données aux images de chats et de chiens et, sur la base des caractéristiques les plus similaires, il le placera dans la catégorie des chats ou des chiens.
Algorithme K-Nearest Neighbour (KNN) pour l’apprentissage automatique

Pourquoi avons-nous besoin d’un algorithme K-NN ?

Supposons qu'il existe deux catégories, c'est-à-dire la catégorie A et la catégorie B, et que nous ayons un nouveau point de données x1, donc ce point de données se situera dans laquelle de ces catégories. Pour résoudre ce type de problème, nous avons besoin d’un algorithme K-NN. Avec l'aide de K-NN, nous pouvons facilement identifier la catégorie ou la classe d'un ensemble de données particulier. Considérez le diagramme ci-dessous :

Algorithme K-Nearest Neighbour (KNN) pour l’apprentissage automatique

Comment fonctionne K-NN ?

Le fonctionnement de K-NN peut être expliqué sur la base de l'algorithme ci-dessous :

    Étape 1:Sélectionnez le nombre K des voisinsÉtape 2:Calculer la distance euclidienne de K nombre de voisins Étape 3:Prenez les K voisins les plus proches selon la distance euclidienne calculée.Étape 4:Parmi ces k voisins, comptez le nombre de points de données dans chaque catégorie.Étape 5 :Attribuez les nouveaux points de données à la catégorie pour laquelle le nombre de voisins est maximum.Étape 6 :Notre modèle est prêt.

Supposons que nous ayons un nouveau point de données et que nous devions le placer dans la catégorie requise. Considérez l'image ci-dessous :

Structure Java
Algorithme K-Nearest Neighbour (KNN) pour l’apprentissage automatique
  • Tout d’abord, nous choisirons le nombre de voisins, nous choisirons donc le k=5.
  • Ensuite, nous calculerons le Distance euclidienne entre les points de données. La distance euclidienne est la distance entre deux points, que nous avons déjà étudiée en géométrie. Il peut être calculé comme suit :
Algorithme K-Nearest Neighbour (KNN) pour l’apprentissage automatique
  • En calculant la distance euclidienne, nous avons obtenu les voisins les plus proches, soit trois voisins les plus proches dans la catégorie A et deux voisins les plus proches dans la catégorie B. Considérez l'image ci-dessous :
Algorithme K-Nearest Neighbour (KNN) pour l’apprentissage automatique
  • Comme nous pouvons le voir, les 3 voisins les plus proches appartiennent à la catégorie A, ce nouveau point de données doit donc appartenir à la catégorie A.

Comment sélectionner la valeur de K dans l'algorithme K-NN ?

Vous trouverez ci-dessous quelques points à retenir lors de la sélection de la valeur de K dans l'algorithme K-NN :

  • Il n'existe pas de moyen particulier de déterminer la meilleure valeur pour « K », nous devons donc essayer certaines valeurs pour en tirer le meilleur parti. La valeur la plus préférée pour K est 5.
  • Une valeur très faible pour K, telle que K=1 ou K=2, peut être bruyante et entraîner des effets de valeurs aberrantes dans le modèle.
  • Des valeurs élevées pour K sont bonnes, mais elles peuvent rencontrer quelques difficultés.

Avantages de l'algorithme KNN :

  • C’est simple à mettre en œuvre.
  • Il est robuste aux données d'entraînement bruyantes
  • Cela peut être plus efficace si les données d’entraînement sont volumineuses.

Inconvénients de l'algorithme KNN :

  • Il faut toujours déterminer la valeur de K, ce qui peut parfois être complexe.
  • Le coût de calcul est élevé en raison du calcul de la distance entre les points de données pour tous les échantillons d'apprentissage.

Implémentation Python de l'algorithme KNN

Pour effectuer l'implémentation Python de l'algorithme K-NN, nous utiliserons le même problème et le même ensemble de données que ceux que nous avons utilisés dans la régression logistique. Mais ici, nous allons améliorer les performances du modèle. Ci-dessous la description du problème :

Problème pour l'algorithme K-NN : Il existe un constructeur automobile qui a fabriqué une nouvelle voiture SUV. L'entreprise souhaite diffuser les annonces aux utilisateurs intéressés par l'achat de ce SUV. Donc, pour ce problème, nous disposons d'un ensemble de données qui contient les informations de plusieurs utilisateurs via le réseau social. L'ensemble de données contient beaucoup d'informations mais le Salaire estimé et Âge nous considérerons pour la variable indépendante et le Variable achetée est pour la variable dépendante. Ci-dessous l'ensemble de données :

Algorithme K-Nearest Neighbour (KNN) pour l’apprentissage automatique

Étapes pour implémenter l'algorithme K-NN :

  • Étape de prétraitement des données
  • Ajustement de l'algorithme K-NN à l'ensemble d'entraînement
  • Prédire le résultat du test
  • Test de précision du résultat (Création d'une matrice de confusion)
  • Visualisation du résultat de l'ensemble de test.

Étape de prétraitement des données :

L'étape de prétraitement des données restera exactement la même que celle de la régression logistique. Ci-dessous le code correspondant :

 # importing libraries import numpy as nm import matplotlib.pyplot as mtp import pandas as pd #importing datasets data_set= pd.read_csv('user_data.csv') #Extracting Independent and dependent Variable x= data_set.iloc[:, [2,3]].values y= data_set.iloc[:, 4].values # Splitting the dataset into training and test set. from sklearn.model_selection import train_test_split x_train, x_test, y_train, y_test= train_test_split(x, y, test_size= 0.25, random_state=0) #feature Scaling from sklearn.preprocessing import StandardScaler st_x= StandardScaler() x_train= st_x.fit_transform(x_train) x_test= st_x.transform(x_test) 

En exécutant le code ci-dessus, notre ensemble de données est importé dans notre programme et bien prétraité. Après la mise à l'échelle des fonctionnalités, notre ensemble de données de test ressemblera à :

Algorithme K-Nearest Neighbour (KNN) pour l’apprentissage automatique

À partir de l'image de sortie ci-dessus, nous pouvons voir que nos données sont mises à l'échelle avec succès.

    Ajustement du classificateur K-NN aux données d'entraînement :
    Nous allons maintenant adapter le classificateur K-NN aux données d'entraînement. Pour ce faire, nous importerons le KNeighboursClassifier une sorte de Voisins Sklearn bibliothèque. Après avoir importé la classe, nous créerons le Classificateur objet de la classe. Le paramètre de cette classe sera
      n_voisins :Définir les voisins requis de l’algorithme. Habituellement, il en faut 5.métrique='minkowski' :C'est le paramètre par défaut et il décide de la distance entre les points.p=2 :C’est l’équivalent de la métrique euclidienne standard.
    Et puis nous adapterons le classificateur aux données de formation. Ci-dessous le code correspondant :
 #Fitting K-NN classifier to the training set from sklearn.neighbors import KNeighborsClassifier classifier= KNeighborsClassifier(n_neighbors=5, metric='minkowski', p=2 ) classifier.fit(x_train, y_train) 

Sortie : En exécutant le code ci-dessus, nous obtiendrons le résultat suivant :

 Out[10]: KNeighborsClassifier(algorithm='auto', leaf_size=30, metric='minkowski', metric_params=None, n_jobs=None, n_neighbors=5, p=2, weights='uniform') 
    Prédire le résultat du test :Pour prédire le résultat de l'ensemble de test, nous allons créer un y_pred vecteur comme nous l’avons fait dans la régression logistique. Ci-dessous le code correspondant :
 #Predicting the test set result y_pred= classifier.predict(x_test) 

Sortir:

Le résultat du code ci-dessus sera :

Algorithme K-Nearest Neighbour (KNN) pour l’apprentissage automatique
    Création de la matrice de confusion :
    Nous allons maintenant créer la matrice de confusion pour notre modèle K-NN afin de voir la précision du classificateur. Ci-dessous le code correspondant :
 #Creating the Confusion matrix from sklearn.metrics import confusion_matrix cm= confusion_matrix(y_test, y_pred) 

Dans le code ci-dessus, nous avons importé la fonction confusion_matrix et l'avons appelée en utilisant la variable cm.

Sortir: En exécutant le code ci-dessus, nous obtiendrons la matrice ci-dessous :

Algorithme K-Nearest Neighbour (KNN) pour l’apprentissage automatique

Dans l'image ci-dessus, nous pouvons voir qu'il y a 64+29= 93 prédictions correctes et 3+4= 7 prédictions incorrectes, alors que dans la régression logistique, il y avait 11 prédictions incorrectes. On peut donc dire que les performances du modèle sont améliorées grâce à l'utilisation de l'algorithme K-NN.

    Visualisation du résultat de l'ensemble d'entraînement :
    Nous allons maintenant visualiser le résultat de l'ensemble d'entraînement pour le modèle K-NN. Le code restera le même que celui de Logistic Regression, à l'exception du nom du graphique. Ci-dessous le code correspondant :
 #Visulaizing the trianing set result from matplotlib.colors import ListedColormap x_set, y_set = x_train, y_train x1, x2 = nm.meshgrid(nm.arange(start = x_set[:, 0].min() - 1, stop = x_set[:, 0].max() + 1, step =0.01), nm.arange(start = x_set[:, 1].min() - 1, stop = x_set[:, 1].max() + 1, step = 0.01)) mtp.contourf(x1, x2, classifier.predict(nm.array([x1.ravel(), x2.ravel()]).T).reshape(x1.shape), alpha = 0.75, cmap = ListedColormap(('red','green' ))) mtp.xlim(x1.min(), x1.max()) mtp.ylim(x2.min(), x2.max()) for i, j in enumerate(nm.unique(y_set)): mtp.scatter(x_set[y_set == j, 0], x_set[y_set == j, 1], c = ListedColormap(('red', 'green'))(i), label = j) mtp.title('K-NN Algorithm (Training set)') mtp.xlabel('Age') mtp.ylabel('Estimated Salary') mtp.legend() mtp.show() 

Sortir:

comment lire le fichier csv en java

En exécutant le code ci-dessus, nous obtiendrons le graphique ci-dessous :

Algorithme K-Nearest Neighbour (KNN) pour l’apprentissage automatique

Le graphique de sortie est différent du graphique que nous avons obtenu dans la régression logistique. Cela peut être compris dans les points ci-dessous :

    • Comme nous pouvons le voir, le graphique montre le point rouge et les points verts. Les points verts correspondent à la variable Acheté (1) et les points rouges à la variable non achetée (0).
    • Le graphique montre une limite irrégulière au lieu de montrer une ligne droite ou une courbe car il s'agit d'un algorithme K-NN, c'est-à-dire trouver le voisin le plus proche.
    • Le graphique a classé les utilisateurs dans les catégories appropriées, car la plupart des utilisateurs qui n'ont pas acheté le SUV se trouvent dans la région rouge et les utilisateurs qui ont acheté le SUV sont dans la région verte.
    • Le graphique montre un bon résultat mais il y a quand même des points verts dans la région rouge et des points rouges dans la région verte. Mais ce n'est pas un gros problème, car ce modèle évite les problèmes de surajustement.
    • Notre modèle est donc bien formé.
    Visualisation du résultat de l'ensemble de tests :
    Après l'entraînement du modèle, nous allons maintenant tester le résultat en mettant un nouvel ensemble de données, c'est-à-dire Test dataset. Le code reste le même à l'exception de quelques modifications mineures : comme x_train et y_train sera remplacé par x_test et y_test .
    Ci-dessous le code correspondant :
 #Visualizing the test set result from matplotlib.colors import ListedColormap x_set, y_set = x_test, y_test x1, x2 = nm.meshgrid(nm.arange(start = x_set[:, 0].min() - 1, stop = x_set[:, 0].max() + 1, step =0.01), nm.arange(start = x_set[:, 1].min() - 1, stop = x_set[:, 1].max() + 1, step = 0.01)) mtp.contourf(x1, x2, classifier.predict(nm.array([x1.ravel(), x2.ravel()]).T).reshape(x1.shape), alpha = 0.75, cmap = ListedColormap(('red','green' ))) mtp.xlim(x1.min(), x1.max()) mtp.ylim(x2.min(), x2.max()) for i, j in enumerate(nm.unique(y_set)): mtp.scatter(x_set[y_set == j, 0], x_set[y_set == j, 1], c = ListedColormap(('red', 'green'))(i), label = j) mtp.title('K-NN algorithm(Test set)') mtp.xlabel('Age') mtp.ylabel('Estimated Salary') mtp.legend() mtp.show() 

Sortir:

Algorithme K-Nearest Neighbour (KNN) pour l’apprentissage automatique

Le graphique ci-dessus montre la sortie de l'ensemble de données de test. Comme nous pouvons le voir sur le graphique, le résultat prévu est bon car la plupart des points rouges sont dans la région rouge et la plupart des points verts sont dans la région verte.

Cependant, il y a peu de points verts dans la région rouge et quelques points rouges dans la région verte. Ce sont donc les observations incorrectes que nous avons observées dans la matrice de confusion (7 Sortie incorrecte).