Arbre de décision et forêts aléatoires
Julien JACQUES
26/09/2018
Arbre de décision et forêts aléatoires
Arbre binaire de classification
Principe :
I on veut construire des sous-groupes d’individus les plus
homogènes possibles
I en définissant des endroits de coupures sur les variables
explicatives
plot(iris[,c(1,3)],col=iris[,5])
abline(h=2.5,col=4)
7
6
5
[Link]
4
3
2
1
4.5 5.0 5.5 6.0 6.5 7.0 7.5 8.0
Arbre binaire de classification
Les enjeux :
I trouver les variables et les endroits de coupure permettant de
découper en groupes les plus homogènes possibles (critère de
qualité ?)
I savoir jusqu’à quelle profondeur aller dans l’arbre (pour éviter
le sur-apprentissage)
Principe
I arbre binaire de classification : succession de noeuds
I noeud : défini par le choix d’une variable et d’une division ⇒
partition en 2 classes
I division : choix d’un seuil (variable explicative quanti.) ou d’un
groupe de modalités (variable explicative quali.)
I racine (noeud initial) : ensemble de l’échantillon ; la procédure
est itérée pour chacun des 2 fils du noeud init. Et ainsi de suite.
Arbre binaire de classification
Critère de division
I D : critère d’hétérogénéité d’un noeud
I critère d’entropie
0.7
0.6
K
0.5
X nk nk
entropie
0.4
D = −2n log
0.3
n n
0.2
k=1
0.1
0.0
0.0 0.2 0.4 0.6 0.8 1.0
p
où n est le nombre d’éléments du noeud, nk celui de la classe k,
et avec la convention 0 log 0 = 0
I indice de Gini
0.5
0.4
K
nk nk
indice de Gini
X
0.3
D=− 1−
0.2
n n
k=1
0.1
0.0
0.0 0.2 0.4 0.6 0.8 1.0
p
I on retient la division qui maximise
Dnoeud − (Dfils gauche + Dfils droit )
Arbre binaire de classification
Règle définissant un noeud terminal
I si un des noeuds fils est vide
I si le nombre d’observation est inférieur à un seuil (entre 1 et 5)
Règle d’affectation d’un noeud à une classe
I la classe majoritaire
I la classe a posteriori la plus probable (si des probabilités a priori
sont connues)
I la classe la moins coûteuse (si des coûts de mauvais
classements sont connus)
Arbre binaire de classification
Construction d’un arbre optimal
I les arbres ainsi créés sont souvent très raffinés et donc instable
(sur-ajustement)
I on va recherche des arbres plus parcimonieux :
Méthode CART {(Breinman et al. 1984)}
1. construction de l’arbre maximal
2. construction d’une séquence d’arbre emboités
I on compare tous les arbres obtenus en supprimant une des
dernières divisions (et donc une feuille) suivant un critère
d’erreur de classement, et on retient le meilleur
I ainsi de suite en remontant jusqu’à la racine
3. comparer les arbres obtenus via un taux de mauvais classement
estimé sur échantillon test ou par validation croisée
Arbre binaire de classification
Avantages
I règle d’affectation lisible
I aucune hypothèse paramétrique
I robuste vis-à-vis des données atypiques
I traitement indifférencié des variables continues et catégorielles
Inconvenients
I demande des tailles d’échantillons grandes
I coûteux en temps de calcul
I parfois instable
Packages R
library('rpart')
library('[Link]')
Arbre classification sous R
arbre=rpart(Species~.,data=iris)
[Link](arbre)
setosa setosa
.33 .33 .33 versicolor
100% virginica
yes [Link] < 2.5 no
versicolor
.00 .50 .50
67%
[Link] < 1.8
setosa versicolor virginica
1.00 .00 .00 .00 .91 .09 .00 .02 .98
33% 36% 31%
Arbre classification sous R
Avec découpage apprentissage / test et prédiction
indiceApp=sample(1:150,100)
dfApp=iris[indiceApp,]
dfTest=iris[-indiceApp,]
arbre=rpart(Species~.,data=dfApp)
res=predict(arbre,newdata=dfTest,type='class')
table(res,dfTest$Species)
##
## res setosa versicolor virginica
## setosa 22 0 0
## versicolor 0 12 0
## virginica 0 2 14
Random Forest
Compromis biais variance
I un modèle trop simple risque d’être trop biaisé, trop loin du
vrai modèle
I un modèle trop complexe risque d’avoir une grande variance,
c’est-à-dire d’être trop sensible aux fluctuations
d’échantillonnage (sur-apprentissage)
Le meilleur modèle sera celui qui réalisera le meilleur
compromis entre biais et variance.
Bagging
L’idée du bagging (Boostrap Aggregating) est de faire coopérer
plusieurs arbres de classification construits sur des échantillons
bootstrap (tirage avec remise) :
I on tire B échantillons de taille n avec remise
I pour chaque échantillon on estime un arbre de classification
I pour un nouvel individu à classer, on le classe avec chaque
arbre construit, et on retient la classe majoritaire
Bagging
Avantage :
I le bagging permet de réduire la variance par rapport à un
unique arbre de classification
I même si le bagging peut être utiliser pour tous types de
modèle, il est particulièrment adapté pour les arbres de
classification non élagués :
I les arbres non élagués auront des biais faibles
I l’aggrégation de ces arbres permet de réduire la variance
Bagging sous R
Exemple d’utilisation du bagging avec les arbres de décisions sur les
données iris
library(adabag)
sub=sample(1:nrow(iris),2*nrow(iris)/3)
model <- bagging(Species~.,data=iris[sub,],mfinal=10)
pred <- [Link](model,newdata=iris[-sub, ])
pred$confusion
## Observed Class
## Predicted Class setosa versicolor virginica
## setosa 13 0 0
## versicolor 0 22 4
## virginica 0 1 10
Bagging sous R
Même exercice mais en créant des arbres individuels plus profonds
model2 <- bagging(Species~., data=iris[sub,],mfinal=10,
control=list(cp=0,minsplit=2,minbucket=1))
pred <- [Link](model2,newdata=iris[-sub,])
pred$confusion
## Observed Class
## Predicted Class setosa versicolor virginica
## setosa 13 0 0
## versicolor 0 23 3
## virginica 0 0 11
Bagging sous R
L’importance relative des variables peut être obtenue par :
model2$importance
## [Link] [Link] [Link] [Link]
## 71.497831 26.566594 1.935574 0.000000
Cet indicateur prendre en compte le gain d’index de Gini obtenu par
une variable dans chaque arbre.
Random Forest
Pour que le bagging soit efficace, il faut que :
I les arbres soient profonds (taille minimal des feuilles = 1)
I les arbres soient différents les uns des autres
Les forêts aléatoires considérent des arbres profonds et introduit
une perturbation dans le choix des variables à chaque
segmentation de noeud : plutôt que de tester toutes les p variables,
on en teste que m choisies aléatoirement parmi p.
Random Forest sous R
On peut utiliser le package randomForest :
library(randomForest)
model=randomForest(Species~.,data=iris[sub,],ntree=200,mtry=3)
On peut afficher la matrice de confusion sur l’échantillon Out-Of-Bag
(calculées sur données non choisies dans chaque échantillon bootstrap) :
model$confusion
## setosa versicolor virginica [Link]
## setosa 37 0 0 0.00000000
## versicolor 0 25 2 0.07407407
## virginica 0 1 35 0.02777778
Random Forest sous R
L’importance des variables est donnée par :
varImpPlot(model)
model
[Link]
[Link]
[Link]
[Link]
0 5 10 15 20 25 30
MeanDecreaseGini
Random Forest sous R
On peut calculer l’erreur sur un échantillon test, même si c’est
inutile car on a l’erreur OOB intégrée :
model=randomForest(Species~.,data=iris[sub,])
pred<-predict(model,newdata=iris[-sub,],type="class")
table(pred,iris[-sub,5])
##
## pred setosa versicolor virginica
## setosa 13 0 0
## versicolor 0 23 3
## virginica 0 0 11
Bilan sur Random Forest
Avantages :
I bonnes performances en prédiction
I pas de problème d’overfitting (on peut augmenter B)
I mesure de l’importance des variables
I évaluation de l’erreur intégrée (OOB)
Inconvénient :
I problème si le nombre de variables pertinentes est faible