Machine Learning – KNN


KNN – Le concept

Littéralement K nearest neighbors, ce qui peut se traduire en Français les K(un nombre) plus proches voisins.

Il s’agit d’un algorithme simple mais très efficace pour classifier des données labellisées.

 

Afin de comprendre le concept, le plus simple est d’imaginer de sélectionner un ensemble de critères pour classifier des objets dans deux ou plusieurs catégories.

Par exemple classer des aliments dans une catégorie (fruit, légume, céréale  etc…) en appliquant une note à des critères comme la sucrosité, la salinité, le degré de croquant etc..

 

On peut alors introduire un nouvel élément et tenter de le classer en fonction de sa proximité avec les éléments existant du tableau.

 

 

KNN calcule la distance Euclidienne entre chaque critère du raisin et leur homologue pour chaque observation dans le tableau.

La distance Euclidienne est égale à la racine carrée de la somme des carrés des distances.

Quelle est la distance Rasin-Pomme ?

La même opération est réalisée pour chaque enregistrement de la table.

 

Il est alors possible d’identifier quels sont les aliments les plus proches du raisin.

 

Si on affecte 1 au paramètre K, le raisin sera classifié en fonction du type de son plus proche voisin.

Si on affecte 5, le raisin sera alors classifié en fonction du type le plus fréquent parmi les 5 plus proches voisins.

 

En pratique, on utilise généralement la racine carrée du nombre d’observations du dataset comme paramètre de départ pour K.

 

Standardisation des valeurs

 

En pratique certains critères auront des valeurs maximales et minimales nettement supérieures à celles d’autres critères.

Il est alors nécessaire de d’ajuster (normaliser) les valeurs afin d’éviter que certains critères n’aient un poids trop important.

 

Pour standardiser nous pouvons utiliser la distance Min-Max (position d’une valeur entre 0 et 1)  0——x————-1

 

Nouvelle valeur du critère = (Valeur – Valeur Min du critère)/(Valeur Max du critère-Valeur Min du critère)

Ou

Z-Score (nombre d’écarts types d’une valeur)

Nouvelle valeur du critère = (Valeur – Moyenne du critère)/Ecart Type du critère)

 

Cette dernière standardisation permet de tenir compte du poids de certaines valeurs extrêmes.

 

Lorsque les valeurs ne sont pas numériques, il est alors nécessaires de les transformer en leur attribuant une valeur numérique adaptée.

 

Application dans R

 

Tout d’abord charger le dataset iris.

data(iris)

dataset <- iris

 

La fonction str(dataset) permet d’observer la structure du dataset :

Nous pouvons ensuite voir que le critère Species est celui qui contient nos ‘labels’ c’est-à-dire la classification que nous souhaitons déterminer pour les futures observations.

Il est important que ce critère se présente sous la forme d’un facteur, lorsque ce n’est pas le cas, il convient de transformer le type de données

 

dataset$Species<- factor(dataset$Species, levels = c(« Setosa », « Versicolor »…..),labels = c(« Set », « Mal »…))

 

Les observations étant classées, il convient de les mélanger en prélevant un échantillon de la taille totale du dataset.

 

dataset=dataset[sample(150),]

 

 

Nous devons ensuite standardiser nos valeurs numériques en créant une fonction spécialisée que nous nommerons Standard():

 

Standard<- function(x){return ((x-min(x))/(max(x)-min(x)))}

 

 

Nous devons appliquer cette fonction à chaque critère numérique , ce qui serait fastidieux manuellement, nous pouvons nous faciliter la tâche en utilisant la fonction lapply() qui applique une fonction à chaque élément d’une liste(chaque critère ici).

 

dataset_std <- as.data.frame(lapply(dataset[1:4], Standard))

 

 

Les valeurs sont bien standardisées  (comprises entre 0 et 1)

 

Création d’un Dataset d’entrainement et d’un Dataset de test

 

Les observations étant plus classées il n’y a pas besoin de générer des échantillons aléatoires, une simple sélection par ligne suffira :

train <- dataset_std[1:130, ]

test <- dataset_std[131:150, ]

 

Pour rappel ces deux dataset ne contiennent pas les labels (la catégorie d’iris), nous devons donc les stocker à part dans deux différents vecteurs à partir de la 5ème colonne du dataset.

 

train_labels <- dataset[1:130, 5]

test_labels <- dataset[131:150, 5]

Utiliser l’algorithme KNN

 

L’un des packages utilisant KNN est le package class

 

install.packages(« class »)

library(class)

 

Nous pouvons maintenant utiliser la fonction knn() pour classifier les observations de notre dataset de test :

 

Resultat <- knn(train=train,test=test,cl=train_labels,k=11)

 

Pour mémoire nous avons choisi K comme étant la racine carrée du nombre total d’observation sqrt(130).

 

Le vecteur résultat stocke les valeurs prédites.

 

Evaluation

 

Tout d’abord charger le module gmodels

Install.packages(« gmodels »)

library(gmodels)

 

Puis générer une table croisée entre les valeurs prévues et les valeurs réelles.

 

CrossTable(x = test_labels, y = Resultat,prop.chisq=FALSE)

L’addition des valeurs donne un résultat de 100 % : toutes les valeurs prédites correspondent aux valeurs réelles.

 

Dans PowerBI

 

Créer une requête vide

 

let

Source = R.Execute(« 

data(iris);

dataset <- iris;

dataset=dataset[sample(150),];

Standard<- function(x){return ((x-min(x))/(max(x)-min(x)))};

dataset_std <- as.data.frame(lapply(dataset[1:4], Standard));

train <- dataset_std[1:130, ];

test <- dataset_std[131:150, ];

train_labels <- dataset[1:130, 5];

test_labels <- dataset[131:150, 5];

library(class);

Resultat<- data.frame(knn(train=train,test=test,cl=train_labels,k=11))

« )

in

Source

 

Nous pouvons alors exploiter chacune des tables créées par R

 

Supposons maintenant que nous souhaitions que notre algorithme soit appliqué à des valeurs externes (par exemple stockées dans un fichier csv).

Il n’est pas actuellement possible de faire directement référence à une autre requête PowerQuery par exemple à cette Table importée :

 

Mais il est possible de faire référence à la même source de données dans la requête R, en modifiant la source du vecteur test  dans la requête script R (Algorithme) :

test <- read.csv(‘d:/Nouvelles fleurs.csv’,sep=’;’);

 

Ainsi, la requête PowerQuery ‘Classique’ et la requête R utilisent les mêmes données.

 

Les applications sont nombreuses : la table externe peut être localisée dans le cloud et alimentée en continu par plusieurs sources, les résultats de la classification visualisés dans PowerBI.

 

 

Laissez un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *