Tuto Python & Scikit-learn : KNN (k-nearest neighbors)
Table des matières
Introduction
L’apprentissage automatique, en anglais le machine learning, est une discipline de l’intelligence artificielle qui utilise les mathématiques, en particulier les statistiques, afin de permettre aux ordinateurs la possibilité de résoudre des tâches sans qu’elles soient explicitement programmées.
Il existe plusieurs types d’apprentissages : apprentissage supervisé, apprentissage non supervisé, apprentissage semi-supervisé, etc. Lors de ce tutoriel, nous allons nous focaliser sur une méthode d’apprentissage supervisé qui est les k plus proches voisins (en anglais k-nearest neighbors : K-NN ou KNN).
1. Définition
L’algorithme des k plus proches voisins est tout d’abord une méthode d’apprentissage supervisé. Qui est utilisé pour la classification, c’est-à-dire pour les données avec des étiquettes discrètes, ainsi que la régression, c’est-à-dire les données avec des étiquettes continues.
Afin de faire une prédiction, cet algorithme ne construit pas de modèle prédictif comme il est le cas pour les algorithmes de régression. Cependant, il n’y a pas de phases d’apprentissage puisqu’il classifie directement des points dont la classe est inconnue en fonction de leurs distances par rapport à des points appartenant à une classe connue auparavant. Cet algorithme est ainsi classé dans la catégorie de lazy learning.
L’algorithme KNN agit en deux étapes :
- 1ère étape : L’algorithme en premier lieu calcule la distance et stocke les k voisins plus proches pour chaque échantillon de l’ensemble d’apprentissages.
- 2ème étape : Ensuite pour un échantillon sans étiquette l’algorithme récupère les k voisins plus proches de celui-ci et prédit sa classe par vote.
Exemple :
Afin de simplifier comment fonctionne cet algorithme, prenons l’exemple suivant où on a deux classes : la classe étoile et la classe triangle. Et on souhaite déterminer la classe du cercle rouge.
Le K dans l’algorithme KNN fait référence au nombre des plus proches voisins dont nous souhaitons prendre des votes. Prenons alors comme exemple K = 3.
Alors on dessine un cercle dont le centre est le cercle rouge et qui contient trois voisins sur le plan.
Les trois plus proches voisins du cercle rouge sont deux étoiles et un triangle. Ceci dit, le cercle rouge appartient alors à la classe étoile puisqu’on a deux votes de la classe étoile et un seul vote de la classe triangle.
2. Prérequis
Afin d’appliquer l’algorithme KNN on suppose que l’ensemble de données (dataset) contient peu de bruit, qu’il est étiqueté et qu’il ne contient que les caractéristiques pertinentes.
L’utilisation de l’algorithme des k plus proches voisins sur de larges ensembles de données n’est pas recommandée, car il prendra beaucoup plus de temps.
3. Module Scikit-learn
La bibliothèque Scikit-learn de Python destinée à l’apprentissage automatique approvisionne le module sklearn.neighbors qui contient les méthodes d’apprentissage basées sur les voisins.
Comme spécifié précédemment, l’algorithme KNN est utilisé ainsi pour la classification plutôt que pour la régression. Ce que nous allons détailler dans ce qui suit.
3.1. KNN classifier
Afin de bien assimiler le fonctionnement de l’algorithme KNN nous allons aboutir à travers l’exploitation de l’exemple de dataset suivant concernant des fruits :
Le but est la prédiction de l’étiquette d’un fruit.
Tout d’abord nous allons importer les modules numpy, pandas et sklearn (que les éléments dont on a besoin), ensuite on charge le fichier Excel comprenant les données. Puis on affiche les cinq premiers enregistrements de l’ensemble des données à l’aide de la fonction head() afin d’avoir une idée sur la dataset.
- Code :
import numpy as np
import pandas as pd
from sklearn.model_selection import train_test_split
df = pd.read_excel('C:/Users/LENOVO/Desktop/coursGratuit/fruitDataset.xlsx')
df.head()
- Résultat de l’exécution :
On ci-après une correspondance entre la valeur de l’étiquette du fruit et son nom dans le but de faciliter l’interprétation des résultats.
- Code :
nom_fruit_cible = dict( zip (df.etiquette_fruit.unique(), df.nom_fruit.unique()))
print( nom_fruit_cible )_excel('C:/Users/LENOVO/Desktop/coursGratuit/fruitDataset.xlsx')
df.head()
- Résultat de l’exécution :
On définit ensuite deux variables x et y représentant respectivement les valeurs de caractéristiques et la valeur cible. Puis, on utilise la fonction train_test_split pour fractionner l’ensemble des données en données de train et de test qui sont par défaut à 75/25 %.
- Code :
x = df [['poids', 'largeur', 'hauteur']]
y = df['etiquette_fruit']
x_train, x_test, y_train, y_test = train_test_split(x, y, random_state=0)
- Résultat de l’exécution :
Maintenant que les données sont fractionnées en train-test, nous allons créer une instance de l’objet classifier, qui est dans ce cas un classificateur KNN (KNeighborsClassifier).
On définit par la suite le paramètre k qui est le nombre de voisins à une valeur égale à 3 et qui sera utilisé par le classificateur.
On entraine le classificateur à l’aide de la méthode fit() qu’on lui passe en paramètres x_train et y_train.
- Code :
from sklearn.neighbors import KNeighborsClassifier
#instanciation et définition du k
knn = KNeighborsClassifier(n_neighbors = 3)
#training
knn.fit(x_train,y_train)
- Résultat de l’exécution :
Pour le moment le classificateur KNN n’a pas utilisé aucune donnée de test, alors on va utiliser la méthode score() qui prend en paramètre ces valeurs de test précédemment défini et en calcule la précision de l’algorithme. Celle-ci est définie comme la fraction des éléments de l’ensemble de tests dont le véritable label a été correctement prédit.
- Code :
knn.score(x_test,y_test)
- Résultat de l’exécution :
Alors dans les deux applications suivantes on va entrer le poids, la largeur et la hauteur d’un fruit et on demande au classificateur de prédire le nom du fruit en utilisant la méthode de prédiction predict().
- Code :
prediction_fruit = knn.predict([[20,4.3,5.5]])
nom_fruit_cible[prediction_fruit[0]]
- Résultat de l’exécution :
- Code :
prediction_fruit = knn.predict([[180,8.0,6.8]])
target_fruits_name[prediction_fruit[0]]
- Résultat de l’exécution :
3.2. KNN regressor
Nous appliquerons cet algorithme sur la même dataset de fruit utilisé pour le KNN classifier.
Nous allons procéder comme précédemment en important les modules nécessaires, puis on charge la dataset en dataframe avec pandas. Ensuite, on crée les correspondances entre la valeur de l’étiquette d’un fruit et le nom de celui-ci. Après, nous définissons deux variables, l’une pour les valeurs de caractéristiques et l’autre pour la valeur cible. Pour ensuite fractionner l’ensemble des données en des données de train et de test.
- Code :
import numpy as np
import pandas as pd
from sklearn.model_selection import train_test_split
#charger dataframe
df = pd.read_excel('C:/Users/LENOVO/Desktop/coursGratuit/fruitDataset.xlsx')
df.head()
#mappint etiquette et nom
nom_fruit_cible = dict( zip (df.etiquette_fruit.unique(), df.nom_fruit.unique()))
print( nom_fruit_cible )
#valeurs des caractéristiques
x = df [['poids', 'largeur', 'hauteur']]
#valeur cible
y = df['etiquette_fruit']
#fractionner dataset (train-test)
x_train, x_test, y_train, y_test = train_test_split(x, y, random_state=0)
- Résultat de l’exécution :
Maintenant que les données sont fractionnées en train-test, nous allons créer une instance de l’objet regressor, qui est dans ce cas un classificateur KNN (KNeighborsRegressor).
On définit par la suite le paramètre k qui est le nombre de voisins à une valeur égale à 3 et qui sera utilisé par le classificateur.
On entraine le KNeighborsRegressor à l’aide de la méthode fit() qu’on lui passe en paramètres x_train et y_train.
- Code :
from sklearn.neighbors import KNeighborsRegressor
knnr = KNeighborsRegressor(n_neighbors = 3)
knnr.fit(x_train, y_train)
- Résultat de l’exécution :
Pour le moment le KNN régression n’a pas utilisé aucune donnée de test, alors on va faire appel la méthode score() qui prend en paramètre ces valeurs de test précédemment défini et en calcule la précision de l’algorithme. Qui est définie comme la fraction des éléments de l’ensemble de test dont le véritable label a été correctement prédit.
- Code :
knnr.score(x_test, y_test)
- Résultat de l’exécution :
Dans l’application suivante, on va entrer le poids, la largeur et la hauteur d’un fruit et on demande au regressor de prédire le nom du fruit en utilisant la méthode de prédiction predict().
- Code :
prediction_fruit = knnr.predict([[20,4.3,5.5]])
nom_fruit_cible[prediction_fruit[0]]
- Résultat de l’exécution :
4. Méthodes de calcul de la distance
Pour le KNN de classification ainsi que de régression, ils ont un paramètre appelé metric qui désigne la méthode de calcul de la distance et qui prend par défaut la valeur ‘minkowski’.
Le tableau suivant regroupe les différentes métriques possibles destinées aux espaces vectoriels à valeurs réelles :
MÉTRIQUE | ARGUMENT | DISTANCE |
euclidean | sqrt(sum((x - y)^2)) | |
manhattan | sum(|x - y|) | |
chebyshev | max(|x - y|) | |
minkowski | p | sum(|x - y|^p)^(1/p) |
wminkowski | p, w | sum(|w * (x - y)|^p)^(1/p) |
seuclidean | V | sqrt(sum((x - y)^2 / V)) |
mahalanobis | V | sqrt((x - y)' V^-1 (x - y)) |
5. Cas d’utilisation
L’algorithme KNN peut être utilisé pour les exemples de cas suivants :
- La prédiction des prix des actions.
- Les systèmes de recommandation.
- L’analyse du risque de crédit.
- Planification prévisionnelle des voyages.
6. Avantages et limites
6.1. Avantages
L’algorithme KNN est facile à comprendre et à interpréter. Il est utile pour les données non linéaires et est considéré comme un algorithme polyvalent puisqu’il est utile pour la classification et la régression.
6.2. Limites
Puisque le KNN ne nécessite pas un modèle pour faire une prévision, en revanche, il doit garder en mémoire toutes les observations afin de réaliser sa prévision. Alors pour les grandes tailles de jeu de données ceci entrainera un temps beaucoup plus large.
Ainsi, le choix de la métrique (méthode de calcul de la distance) et e nombre voisins K n’est pas quelque chose d’évidente. Il faut tester plusieurs combinaisons pour avoir un résultat satisfaisant.
7. Exercices
Exercice 1 :
Appliquez l’algorithme des k (k = 3) plus proches voisins (classifier) sur la dataset iris. Et calculez la précision de celui-ci.
Notez qu’on veut fractionner la dataset comme suivant : 80% pour les valeurs de training et 20% pour le test.
Exercice 2 :
Appliquez l’algorithme des k (k = 3) plus proches voisins (regressor) sur la dataset iris en utilisant la métrique « euclidean ». Et calculez la précision de celui-ci.
8. Correction
Exercice 1 :
Aperçu de la dataset :
- Code :
df = pd.read_csv('C:/Users/LENOVO/Desktop/coursGratuit/iris.csv')
df.head()
- Résultat de l’exécution :
Nous allons importer tout d’abord les modules nécessaires (pandas et KNeighborsClassifier), puis on charge la dataset en dataframe avec pandas. Ensuite, nous définissons deux variables, l’une pour les valeurs de caractéristiques (longueur et largeur) et l’autre pour la valeur cible (espèce de l’iris). Pour ensuite fractionner l’ensemble des données en des données de train et de test.
Puis nous allons créer une instance de l’objet classifier, qui est dans ce cas un classificateur KNN (KNeighborsClassifier).
On définit par la suite le paramètre k qui est le nombre de voisins à une valeur égale à 3 et qui sera utilisé par le classificateur.
On entraine le KNeighborsClassifier à l’aide de la méthode fit() qu’on lui passe en paramètres x_train et y_train.
Puis on va entrer la longueur et la largeur d’un iris et on demande au classifier de prédire son espèce (sachant la dataset contient trois types : 0 pour setosa, 1 pour versicolor et 2 pour virginica) en utilisant la méthode de prédiction predict().
Et on calcul finalement la précision à l’aide de la méthode score().
- Code :
import pandas as pd
from sklearn.neighbors import KNeighborsClassifier
#traitement du fichier csv
df = pd.read_csv('C:/Users/LENOVO/Desktop/coursGratuit/iris.csv')
a = df.loc[:,"petal_length"]
b = df.loc[:,"petal_width"]
x = list(zip(a, b))
y = df.loc[:,"species"]
#fractionner dataset (train-test)
x_train, x_test, y_train, y_test = train_test_split(x, y, test_size=0.20)
#instanciation et définition du k
knn = KNeighborsClassifier(n_neighbors = 3)
#training
knn.fit(x_train, y_train)
#Prédiction
longueur = 2.5
largeur = 0.75
prediction = knn.predict([[longueur, largeur]])
#calcule de précision
print(knn.score(x_test, y_test))
#affichage des résultats
resultat = "Résultat : "
if prediction[0] == 0:
resultat = resultat + "setosa"
if prediction[0] == 1:
resultat = resultat + "versicolor"
if prediction[0] == 2:
resultat = resultat + "virginica"
print(txt)
- Résultat de l’exécution :
Exercice 2 :
On reproduit les mêmes lignes code de l’exercice précédent, mais en faisant appel à KNeighborsRegressor eten spécifiant dans ces paramètres la métrique « euclidean ».
- Code :
import pandas as pd
from sklearn.neighbors import KNeighborsRegressor
#traitement du fichier csv
df = pd.read_csv('C:/Users/LENOVO/Desktop/coursGratuit/iris.csv')
df.head()
a = df.loc[:,"petal_length"]
b = df.loc[:,"petal_width"]
x = list(zip(a, b))
y = df.loc[:,"species"]
#fractionner dataset (train-test)
x_train, x_test, y_train, y_test = train_test_split(x, y, test_size=0.20)
#instanciation et définition du k
knnr = KNeighborsRegressor (n_neighbors = 3, metric = 'euclidean')
#training
knnr.fit(x_train, y_train)
#Prédiction
longueur = 2.5
largeur = 0.75
prediction = knnr.predict([[longueur, largeur]])
#calcule de précision
print(knnr.score(x_>Q, y_test))
#affichage des résultats
resultat = "Résultat : "
if prediction[0] == 0:
resultat = resultat + "setosa"
if prediction[0] == 1:
resultat = resultat + "versicolor"
if prediction[0] == 2:
resultat = resultat + "virginica"
print(txt)
- Résultat de l’exécution :
Conclusion
Lors de ce tutoriel, nous avons défini l’algorithme KNN, son principe et ses cas d’utilisation. Nous avons également vu réagir cet algorithme sur un ensemble de données pour les deux cas d’utilisation du KNN à savoir le cas de classification et de régression. Et finalement on a cité quelques avantages ainsi que limites pour cet algorithme.
Article publié le 09 Novembre 2020par Imane BENHMIDOU