2 Les modèles classifiers

Les modèles classifiers sont utilisés en machine learning lorsque la variable réponse $Y$ est qualitative. Il en existe plusieurs, les arbres de décision, les forêts aléatoires, les naïve bayes les réseaux de neuronnes artificiels.

2.1 Arbres de décision

2.1.1 Présentation

Cet outil d’aide à la décision ou d’exploration de données permet de représenter un ensemble de choix sous la forme graphique d’un arbre. C’est une des méthodes d’apprentissage supervisé les plus populaires pour les problèmes de classification de données.

Concrètement, un arbre de décision modélise une hiérarchie de tests pour prédire un résultat. Il existe deux principaux types d’arbre de décision :

Les arbres de régression (Regression Tree) permettent de prédire une quantité réelle, une valeur numérique (par exemple, le prix d’une maison ou la durée de séjour d’un patient dans un hôpital) ;
Les arbres de classification (Classification Tree) permettent de prédire à quelle classe la variable de sortie appartient (cela permet par exemple de répartir une population d’individus, comme des clients d’une entreprise en différents types de profils).

Les décisions possibles sont situées aux extrémités des branches (les « feuilles » de l’arbre) et sont atteintes en fonction de décisions prises à chaque étape. Un arbre de décision fonctionne en appliquant de manière itérative des règles logiques très simples (typiquement des séparations de données par « hyperplan », généralisation d’un plan à plus de 2 dimensions), chaque règle étant choisie en fonction du résultat de la règle précédente. Les arbres de décision ont pour avantage d’être simple à interpréter, très rapide à entrainer, d’être non paramétrique, et de nécessiter très peu de prétraitement des données. Ils peuvent être calculés automatiquement par des algorithmes d’apprentissage supervisé capables de sélectionner automatiquement les variables discriminantes au sein de données non-structurées et potentiellement volumineuses. Ces algorithmes permettent aussi d’extraire des règles logiques qui n’apparaissaient pas dans les données brutes. Un autre usage en machine learning consiste à construire non pas un arbre mais une forêt d’arbres de décision. Une décision est alors prise en faisant « voter » l’ensemble des arbres et en choisissant la réponse majoritaire (pour un choix discret) ou la moyenne des réponses (pour une variable continue). Les résultats ainsi obtenus sont remarquables notamment lorsque les arbres de décision sont utilisés en forêts aléatoires (Random Forest*).

Le package R rpart propose une implémentation des méthodes de construction d’arbres de décision inspirées de l’approche CART décrite dans l’ouvrage éponyme de Breiman, Friedman, Olshen et Stone en 1983.

Il existe des tutos : https://apiacoa.org/blog/2014/02/initiation-a-rpart.fr.html

2.1.2 Exemple

Les données sont accessibles dans le package rpart.plot et décrivent 1046 passagers selon 6 variables :

pclass donne la classe tarifaire sur le bateau ;
survided indique si le passager a survécu ;
sex donne le genre du passager ;
age donne l’âge du passager exprimé en années ;
sibsp donne le nombre de frères, sœurs, mari ou épouse à bord ;
parch donne le nombre d’enfants ou de parents à bord.

library(rpart)
library(rpart.plot)
data(ptitanic)

2.1.2.1 Construction de l’arbre

Attention, il arrive sur des données de petite taille que les paramètres par défaut de rpart soient trop conservateurs. Par exemple, rpart ne découpe pas une feuille contenant 20 observations. De même rpart demande une amélioration relative d’au moins 1 % de la qualité d’une partition pour effectuer un découpage. Pour changer ces valeurs, il suffit d’utiliser la commande rpart.control en précisant les éléments à modifier. On divise le jeu de données en test et train pour pouvoir ensuite attester de la justesse de notre modèle.

train <- ptitanic %>% sample_frac(0.8)
test <- anti_join(ptitanic, train)

ptitanicTree <- rpart(survived~.,data=train,control=rpart.control(minsplit=5,cp=0))

construit un arbre en continuant les découpages dans les feuilles qui contiennent au moins 5 observations (paramètre minsplit) et sans contrainte sur la qualité du découpage (paramètre cp mis à 0). L’arbre construit de cette façon est assez volumineux et contient 65 feuilles.

rpart.plot(ptitanicTree, main = "Arbre de décision")

2.1.2.2 Simplification de l’arbre

Pour choisir le bon niveau de simplification, ou encore le bon nombre de feuilles, on procède par validation croisée. La fonction rpart réalise par défaut une estimation des performances de l’arbre par validation croisée à 10 blocs pour chaque niveau de simplification pertinent. Le nombre de blocs se règle au moment de la construction de l’arbre grâce au paramètre xval de rpart.control.

On peut afficher les résultats de cette opération grâce à la fonction printcp, comme ci-dessous. La courbe indique le taux de mauvaises classifications relativement au score d’origine (dans un arbre réduit à une seule feuille dans laquelle la décision correspond à la classe majoritaire), estimé par la validation croisée. Les barres d’erreur autour de chaque estimation sont aussi obtenues par validation croisée. Ici, comme on a 809 morts et 500 survivants, l’erreur de référence est d’environ 38,2 %. L’axe des abscisses indique la complexité de l’arbre par l’intermédiaire du nombre de feuilles.

plotcp(ptitanicTree)

Si le jeu de données est trop grand, on a un risque de sur-appprentissage. Dans ce cas là, les performances s’améliorent dans un premier temps quand on augmente le nombre de feuilles puis se dégradent en raison du sur-apprentissage. On choisit en général la complexité qui minimise l’erreur estimée. L’axe en haut représente le nombre de feuilles, et celui du bas le “cp” a entrer dans la commande suivante. On choisi de garder 7 feuilles avec un cp de 0.0088 (parce que 2 feuilles c’est pas un arbre).

Pour obtenir l’arbre simplifié, on utilise la fonction prune, comme dans le code suivant :

ptitanicSimple <- prune(ptitanicTree,cp=0.0088)
ptitanicSimple

## n= 1047 
## 
## node), split, n, loss, yval, (yprob)
##       * denotes terminal node
## 
##  1) root 1047 390 died (0.62750716 0.37249284)  
##    2) sex=male 688 131 died (0.80959302 0.19040698)  
##      4) age>=9.5 648 107 died (0.83487654 0.16512346) *
##      5) age< 9.5 40  16 survived (0.40000000 0.60000000)  
##       10) sibsp>=2.5 14   1 died (0.92857143 0.07142857) *
##       11) sibsp< 2.5 26   3 survived (0.11538462 0.88461538) *
##    3) sex=female 359 100 survived (0.27855153 0.72144847)  
##      6) pclass=3rd 168  79 died (0.52976190 0.47023810)  
##       12) sibsp>=2.5 17   2 died (0.88235294 0.11764706) *
##       13) sibsp< 2.5 151  74 survived (0.49006623 0.50993377)  
##         26) age>=18.25 111  51 died (0.54054054 0.45945946) *
##         27) age< 18.25 40  14 survived (0.35000000 0.65000000) *
##      7) pclass=1st,2nd 191  11 survived (0.05759162 0.94240838) *

rpart.plot(ptitanicSimple, main = "Arbre de décision simplifié")

2.1.2.3 Vérification de la justesse de l’arbre

Un outil important pour pouvoir vérifier de la justesse de l’arbre créé est la matrice de confusion. La diagonale représente le nombre de “bien classés” pour toutes les modalités.

library(dplyr)
library(knitr)
test_tree <- test %>%
  mutate(survived_dtree = predict(ptitanicSimple, type = "class", test))
confusion <- table(test_tree$survived_dtree,test_tree$survived)
kable(confusion)

	died	survived
died	52	22
survived	7	43

sum(diag(confusion)) / nrow(test)

## [1] 0.766129

Dans ce cas là, la justesse de l’arbre de décision est de 0.84%

2.2 Forêts aléatoires

2.2.1 Présentation

L’algorithme des « forêts aléatoires » (ou Random Forest parfois aussi traduit par forêt d’arbres décisionnels) est un algorithme de classification qui réduit la variance des prévisions d’un arbre de décision seul, améliorant ainsi leurs performances. Pour cela, il combine de nombreux arbres de décisions dans une approche de type bagging.

L’algorithme des « forêts aléatoires » a été proposé par Leo Breiman et Adèle Cutler en 2001. Dans sa formule la plus classique, il effectue un apprentissage en parallèle sur de multiples arbres de décision construits aléatoirement et entraînés sur des sous-ensembles de données différents. Le nombre idéal d’arbres, qui peut aller jusqu’à plusieurs centaines voire plus, est un paramètre important : il est très variable et dépend du problème. Concrètement, chaque arbre de la forêt aléatoire est entrainé sur un sous ensemble aléatoire de données selon le principe du bagging, avec un sous ensemble aléatoire de features (caractéristiques variables des données) selon le principe des « projections aléatoires ». Les prédictions sont ensuite moyennées lorsque les données sont quantitatives ou utilisés pour un vote pour des données qualitatives, dans le cas des arbres de classification. L’algorithme des forêts aléatoires est connu pour être un des classifieurs les plus efficaces « out-of-the-box » (c’est-à-dire nécessitant peu de prétraitement des données).

qu’est-ce qui est aléatoire dans un arbre aléatoire ? Cette méthode de machine learning compte deux grands pans d’aléatoire : (1) dans le sampling sur lesquels sont construits les arbres (2) dans la sélection des variables sur lesquelles sont effectuées la segmentation.

Les forêts aléatoires marchent sur la méthode du Bagging. La méthode du Bagging a été introduite par Breiman (1996). Le mot Bagging est la contraction des mots Bootstrap et Aggregating. Étant donné un échantillon d’apprentissage $L_n$ et une méthode de prédiction (appelée règle de base), qui construit sur $L_n$ un prédicteur $\hat{h}(.,L_n)$. Le principe du Bagging est de tirer indépendamment plusieurs échantillons bootstrap , d’appliquer la règle de base sur chacun d’eux pour obtenir une collection de prédicteurs, et enfin d’agréger ces prédicteurs de base. L’idée du Bagging, et qu’en appliquant la règle de base sur différents échantillons bootstrap, on en modifie les prédictions, et donc on construit ainsi une collection variée de pré- dicteurs. L’étape d’agrégation permet alors d’obtenir un prédicteur performant (plus d’infos ici).

Comment ca marche?

La forêt aléatoire reste une boîte noire dans de nombreux cas : et pour cause, si vous construisez une forêt de 500, 1000, voire 10.000 (soyons fous) unités, vous ne pourrez pas avoir un regard sur le mécanisme de chaque arbre. Mais, voici globalement comment cela se passe, si nous voulons 500 arbres :

500 subsets de nos données sont pris aléatoirement, avec remplacement. En général, ces samples font chacune 2/3 de l’ensemble.
Pour chaque sous-groupe, un arbre de décision est créé.
Des variables de segmentation sont choisies aléatoirement, et l’arbre est splité en suivant la meilleure segmentation.
Chaque arbre est poussé à son maximum, sans « pruning ».
Nous voici avec 500 modèles différents, avec des calculs de précisions sur le 20% de données non utilisés.
Lorsque des données nouvelles sont présentées au modèle, elles seront évaluées par tous les arbres.

2.2.2 Exemple

2.2.2.1 Construction de la forêt aléatoire

Il est important de mettre une graine avec set.seed pour pouvoir reproduire les résultats

library(randomForest)
set.seed(12345)


random_forest <- randomForest(survived~.,data=train, na.action = na.omit, ntree = 1000, mtry = 3)
print(random_forest)

## 
## Call:
##  randomForest(formula = survived ~ ., data = train, ntree = 1000,      mtry = 3, na.action = na.omit) 
##                Type of random forest: classification
##                      Number of trees: 1000
## No. of variables tried at each split: 3
## 
##         OOB estimate of  error rate: 19.18%
## Confusion matrix:
##          died survived class.error
## died      452       45  0.09054326
## survived  114      218  0.34337349

2.2.2.2 Out Of Bag estimate of error rate

Chaque arbre est entraîné sur une fraction des data, qui est considérée comme « in-bag ». Ce qui permet à chaque arbre, une fois construit, d’estimer son taux d’erreur sur les données qu’il a laissé « out-of-bag » : plus ce taux est faible, plus le modèle est juste. Ce chiffre à lui seul pourrait servir d’indicateur de performance du modèle.

On peut accéder au nombre de fois qu’un individu a été laissé « out of bag » en avec model$oob.times.

plot(seq(from = 1, to = 1000),random_forest$err.rate[,1] , type = "l", xlab="Nombre d'arbres", ylab = "OOB")

2.2.2.3 Matrice de confusion

En colonne, la prédiction de l’algo, et en ligne la modalité réelle. La diagonale représente le nombre de bien classés pour toutes les modalités. Juste à côté, le class.error indique la proportion de mauvais résultats.

kable(random_forest$confusion)

	died	survived	class.error
died	465	32	0.0643863
survived	117	215	0.3524096

2.2.2.4 Justesse

c’est la somme de la diagonale de la matrice de confusion (ce qui a été bien classé) sur le nombre de colonne du jeu de données d’entrainement. On peut extraire la justesse du modèle sur les OOB (cross validation faite dans l’algorithme)

sum(diag(random_forest$confusion)) / nrow(train)

## [1] 0.6494747

On peut aussi claculer la justesse de la forêt aléatoire sur le “test set”. Cela permet de comparer les résultats de la forêt à ceux de l’arbre de décision.

test_forest <- test %>%
  mutate(survived_forest = predict(random_forest, newdata = test))
confusion <- table(test_forest$survived_forest,test_forest$survived)
kable(confusion)

	died	survived
died	45	23
survived	12	41

sum(diag(confusion)) / nrow(test)

## [1] 0.6935484

2.2.2.5 Importance des variables

Le modèle de Random Forest renvoie également un objet importance : il s’agit là de la diminution moyenne de l’impureté apportée par chaque variable. Elle est calculée par l’index de Gini : la diminution pour chaque noeud est cumulée, puis une moyenne sur l’ensemble des arbres est effectuée.

importance(random_forest)

##        MeanDecreaseGini
## pclass         48.02025
## sex           107.23037
## age            93.34747
## sibsp          23.48819
## parch          17.58632

randomForest::varImpPlot(random_forest)

Tuto - Machine Learning Supervisé

1 Machine learning ou apprentissage profond