Étiquette : Machine learning

Premiers pas avec l’apprentissage machine: classification par recherche des plus proches voisins

Cette démo reprend un exemple tiré du livre de Lantz (2013), Machine Learning with R.  On utilise un dataset sur des biopsies en vue de détecter des cancers du sein. Pour ce faire, on fait appel à la fonction knn dans le package class. Cette fonction implémente la méthode de recherche des plus proches voisins (nearest neighbor). Accessoirement, cette démo utilise aussi la fonction CrossTable dans le package gmodels afin de visualiser la classification et voir si nous avons produit des faux négatifs et faux positifs.

D’abord, un peu de préparation. Il faudra d’abord installer class et gmodels si vous ne les avez pas déjà. On peut les installer via l’environnement RStudio, ou bien en exécutant ce code:

install.packages(c("gmodels", "class"))

On roule ensuite ce code:

library(class)
library(gmodels)

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

wbcd <- read.csv("https://resources.oreilly.com/examples/9781784393908/raw/ac9fe41596dd42fc3877cfa8ed410dd346c43548/Machine%20Learning%20with%20R,%20Second%20Edition_Code/Chapter%2003/wisc_bc_data.csv")
rownames(wbcd) <- wbcd$id #on prend la colonne id comme noms de rangée
wbcd$id <- NULL #la colonne id peut être enlevée, elle ne servira plus
wbcd_n <- as.data.frame(lapply(wbcd[2:31], normalize))
wbcd_train <- wbcd_n[1:469, ] #données de training
wbcd_test <- wbcd_n[470:569, ] #données pour vérifier le modèle
wbcd_train_labels <- wbcd[1:469, 1] #diagnostics des données de training
wbcd_test_labels <- wbcd[470:569, 1] #diagnostics des données de test

Nous avons chargé les packages, puis créé une petite fonction pour normaliser les données (elle va servir plus tard). La fonction read.csv a ensuite permis de récupérer le jeu de données depuis le serveur de la maison d’édition OReilly. Après un peu de nettoyage, nous avons créé des sous-ensembles de données qui serviront à l’entrainement de l’algorithme knn et la validation. On remarque que le diagnostic n’a pas été donné à knn pour les données de test. C’est normal. Nous allons entrainer notre système de manière à ce qu’il tente de découvrir ces diagnostics par lui-même. Pour ce faire, knn utilise cette syntaxe: knn(train, test, cl, k)

Où:

  • train et la matrice utilisée pour entrainer le système (excluant le diagnostic),
  • test est la matrice de test (excluant aussi le diagnostic),
  • cl (pour class) est un vecteur indiquant le diagnostic (la « bonne réponse ») pour la matrice train
  • k est un entier donnant le nombre de « voisins » à considérer (nearest neighbourgs), ce qui correspond grosso-modo à la précision dans le découpage.

En gros, l’algorithme knn classifie les données de test  en se basant sur le diagnostic donné par ses « voisins » les plus proches (les points de données similaires dans train). Plus précisément:

  1. On crée un espace ayant un nombre de dimensions correspondant au nombre de variables dans train et test.
  2. On situe chaque ligne des matrice train et test dans cet espace (les coordonnées vont être les valeurs qu’on pris les variables pour cette ligne de la matrice).
  3. Pour chaque point de test, on prend ses voisins les plus proches.
  4. On regarde dans le vecteur cl quelles classifications sont proposées par les voisins sélectionnés.
  5. La classification du point est typiquement établie en fonction de la règle de majorité. Cependant, on peut modifier cet aspect, nous allons l’essayer plus loin.

Le code suivant va permettre de faire la classification avec knn, puis d’en visualiser les résultats avec CrossTable:

wbcd_test_pred <- knn(train = wbcd_train, test = wbcd_test, cl = wbcd_train_labels, k=12)
CrossTable(x = wbcd_test_labels, y = wbcd_test_pred, prop.chisq=FALSE)

Voici la sortie dans R, produite par la fonction CrossTable:

## 
##  
##    Cell Contents
## |-------------------------|
## |                       N |
## |           N / Row Total |
## |           N / Col Total |
## |         N / Table Total |
## |-------------------------|
## 
##  
## Total Observations in Table:  100 
## 
##  
##                  | wbcd_test_pred 
## wbcd_test_labels |         B |         M | Row Total | 
## -----------------|-----------|-----------|-----------|
##                B |        61 |         0 |        61 | 
##                  |     1.000 |     0.000 |     0.610 | 
##                  |     0.953 |     0.000 |           | 
##                  |     0.610 |     0.000 |           | 
## -----------------|-----------|-----------|-----------|
##                M |         3 |        36 |        39 | 
##                  |     0.077 |     0.923 |     0.390 | 
##                  |     0.047 |     1.000 |           | 
##                  |     0.030 |     0.360 |           | 
## -----------------|-----------|-----------|-----------|
##     Column Total |        64 |        36 |       100 | 
##                  |     0.640 |     0.360 |           | 
## -----------------|-----------|-----------|-----------|
## 
##

On retrouve une légende indiquant le contenu des cellules, puis un tableau qui croise les prédictions de la fonction knn avec les diagnostics réels. B étant pour bénin et M pour malin, on peut donc constater qu’on a 61 vrais négatifs (B,B), 0 faux positif (B,M), 3 faux négatifs (M,B) et 36 vrais positifs (M,M).

Amélioration de la classification

Dans un contexte biomédical, on peut sérieusement se demander si 3% de faux négatifs est acceptable – après tout ces personnes risquent de ne pas recevoir un traitement qui est requis. Essayons d’améliorer la classification. Pour ce faire, nous allons tester trois méthodes: d’abord normaliser les données et augmenter la valeur de k. Nous allons ensuite aller plus loin que l’exemple du livre de Lantz et manipuler le paramètre optionnel afin de changer le nombre de votes requis pour qu’un point de données soit classifié comme bénin ou malin.

Le code suivant va convertir toutes nos variables en leurs scores Z, puis produire une nouvelle classification:

wbcd_z <- as.data.frame(scale(wbcd[-1])) #conversion de tout en scores Z (sauf la col 1 qui est le diagnostic)
wbcd_train_z <- wbcd_z[1:469, ]
wbcd_test_z <- wbcd_z[470:569, ]

wbcd_test_pred <- knn(train = wbcd_train_z, test = wbcd_test_z, cl = wbcd_train_labels, k=12)
CrossTable(x = wbcd_test_labels, y = wbcd_test_pred, prop.chisq=FALSE)

Le résultat:

##                  | wbcd_test_pred 
## wbcd_test_labels |         B |         M | Row Total | 
## -----------------|-----------|-----------|-----------|
##                B |        60 |         1 |        61 | 
##                  |     0.984 |     0.016 |     0.610 | 
##                  |     0.952 |     0.027 |           | 
##                  |     0.600 |     0.010 |           | 
## -----------------|-----------|-----------|-----------|
##                M |         3 |        36 |        39 | 
##                  |     0.077 |     0.923 |     0.390 | 
##                  |     0.048 |     0.973 |           | 
##                  |     0.030 |     0.360 |           | 
## -----------------|-----------|-----------|-----------|
##     Column Total |        63 |        37 |       100 | 
##                  |     0.630 |     0.370 |           | 
## -----------------|-----------|-----------|-----------|
## 
## 

Vous aurez constaté que nous avons empiré la situation: nous avons encore 3 faux négatifs, mais aussi 1 faux positif. Cette solution n’a pas fonctionné pour cette exemple.

Essayons plutôt d’augmenter le nombre de voisins consultés en manipulant le paramètre k:

wbcd_test_pred <- knn(train = wbcd_train, test = wbcd_test, cl = wbcd_train_labels, k=20)
CrossTable(x = wbcd_test_labels, y = wbcd_test_pred, prop.chisq=FALSE)

La sortie de CrossTable m’indique que j’ai encore 3 faux négatifs. Et si vous vous amusez à augmenter encore k, par exemple à 30, j’obtiens 4 faux négatifs, ce qui n’améliore en rien la situation.

Combinons les deux stratégies en utilisant à la fois des données normalisée et une valeur supérieure de k:

wbcd_test_pred <- knn(train = wbcd_train_z, test = wbcd_test_z, cl = wbcd_train_labels, k=23)
CrossTable(x = wbcd_test_labels, y = wbcd_test_pred, prop.chisq=FALSE)

Si vous exécutez le code, vous constaterez que j’ai encore 3 faux négatifs. En somme, nous n’avons pas réussi à faire disparaitre ces faux négatifs en transformant les données, en manipulant k, ou en appliquant ces deux modifications deux à la fois.

Pour aller plus loin…

La dernière stratégie consiste à ajuster l’algorithme de manière à ce que la décision de classification ne se fasse plus à la majorité (50% + 1) mais demande un consensus plus fort entre les voisins. Le code suivant va consulter 20 voisins, mais requiert qu’au moins 17 d’entre eux soient d’accord, plutôt que 11 en temps normal. Le paramètre optionnel l  nous permet d’indiquer à knn quel seuil de décision utiliser.

wbcd_test_pred <- knn(train = wbcd_train, test = wbcd_test, cl = wbcd_train_labels, k=20, l=17)
CrossTable(x = wbcd_test_labels, y = wbcd_test_pred, prop.chisq=FALSE)

Roulement de tambour et…

##                  | wbcd_test_pred 
## wbcd_test_labels |         B |         M | Row Total | 
## -----------------|-----------|-----------|-----------|
##                B |        55 |         0 |        55 | 
##                  |     1.000 |     0.000 |     0.655 | 
##                  |     1.000 |     0.000 |           | 
##                  |     0.655 |     0.000 |           | 
## -----------------|-----------|-----------|-----------|
##                M |         0 |        29 |        29 | 
##                  |     0.000 |     1.000 |     0.345 | 
##                  |     0.000 |     1.000 |           | 
##                  |     0.000 |     0.345 |           | 
## -----------------|-----------|-----------|-----------|
##     Column Total |        55 |        29 |        84 | 
##                  |     0.655 |     0.345 |           | 
## -----------------|-----------|-----------|-----------|
## 
## 

En modifiant ainsi le seuil décisionnel, nous avons réussi à faire une classification parfaite pour les 100 cas de la matrice de test. Pas mal!

Le code complet

Note: je n’inclus pas l’installation des packages class et gmodels (voir en haut de ce billet de blog) car je préfère vous laisser gérer cette installation selon vos préférences.

library(class)
library(gmodels)
normalize <- function(x) {
 return ((x - min(x)) / (max(x) - min(x)))
}
wbcd <- read.csv("https://resources.oreilly.com/examples/9781784393908/raw/ac9fe41596dd42fc3877cfa8ed410dd346c43548/Machine%20Learning%20with%20R,%20Second%20Edition_Code/Chapter%2003/wisc_bc_data.csv")
rownames(wbcd) <- wbcd$id #on prend la colonne id comme noms de rangée
wbcd$id <- NULL #la colonne id peut être enlevée, elle ne servira plus
wbcd_n <- as.data.frame(lapply(wbcd[2:31], normalize))
wbcd_train <- wbcd_n[1:469, ] #données de training
wbcd_test <- wbcd_n[470:569, ] #données pour vérifier le modèle
wbcd_train_labels <- wbcd[1:469, 1] #diagnostics des données de training
wbcd_test_labels <- wbcd[470:569, 1] #diagnostics des données de test
wbcd_test_pred <- knn(train = wbcd_train, test = wbcd_test, cl = wbcd_train_labels, k=12)
CrossTable(x = wbcd_test_labels, y = wbcd_test_pred, prop.chisq=FALSE)
wbcd_z <- as.data.frame(scale(wbcd[-1])) #conversion de tout en scores Z (sauf la col 1 qui est le diagnostic)
wbcd_train_z <- wbcd_z[1:469, ]
wbcd_test_z <- wbcd_z[470:569, ]
wbcd_test_pred <- knn(train = wbcd_train_z, test = wbcd_test_z, cl = wbcd_train_labels, k=12) #1er essai de classification
CrossTable(x = wbcd_test_labels, y = wbcd_test_pred, prop.chisq=FALSE)
wbcd_test_pred <- knn(train = wbcd_train, test = wbcd_test, cl = wbcd_train_labels, k=20) #2e essai avec k=20
CrossTable(x = wbcd_test_labels, y = wbcd_test_pred, prop.chisq=FALSE)
wbcd_test_pred <- knn(train = wbcd_train_z, test = wbcd_test_z, cl = wbcd_train_labels, k=23) #3e essai avec Z
CrossTable(x = wbcd_test_labels, y = wbcd_test_pred, prop.chisq=FALSE)
wbcd_test_pred <- knn(train = wbcd_train, test = wbcd_test, cl = wbcd_train_labels, k=20, l=17) #4e essai avec l=17
CrossTable(x = wbcd_test_labels, y = wbcd_test_pred, prop.chisq=FALSE)