Arbres de décision

Introduction

L'objectif de ce TP est de vous faire manipuler des arbres de décision. On utilisera pour cela la bibliothèque rpart de R. Celle-ci contient les fonctions permettant de construire et exploiter un arbre de décision ; l'algorithme utilisé ici est CART.

Avant cela, nous allons organiser notre compte pour s'y retrouver par la suite, quand on aura travailler sur plusieurs TP. Ce qui suit n'a de sens que s'il est effectué sur votre compte personnel (que vous conservez de séances en séances). Donc, si vous n'êtes pas sur votre compte personnel, passez directement à la suite ; vous ferez ce qui suit lorsque vous travaillerez sur votre compte personnel pour la première fois.

Comme d'habitude, vous commencez par ouvrir une fenêtre shell. Pour éviter de mélanger les commandes que vous tapez dans les différents TP, il est judicieux d'organiser votre travail en dossiers. Ainsi, vous pourriez créer un dossier intitulé « fouilleDeDonnées » en tapant la commande suivante :

mkdir fouilleDeDonnées

Vous vous positionnez dans ce dossier en tapant la commande :

cd fouilleDeDonnées

Là, vous pouvez créer un dossier intitulé « introductionR » et y placer vos fichiers .RData et .Rhistory.

  1. Créez ce dossier en prenant exemple sur ce que vous avez tapé ci-dessus ;
  2. Positionnez-vous dans ce dossier.

Vous allez copier vos fichiers .RData et .Rhistory dans ce dossier (on suppose pour cela que ces deux fichiers se trouvent sur votre compte). Tapez les deux commandes :

cp ../../.RData .
cp ../../.Rhistory .

La première commande copie le fichier dénommé .RData qui se trouve dans le dossier qui contient (..) le dossier qui contient (..) votre dossier courant.

Maintenant que vous avez mis de côté votre travail effectué lors du premier TP, vous pouvez vous positionner dans le dossier concernant le deuxième TP (qu'il faut d'abord créer). Pour cela, tapez la commande :

cd ..
mkdir arbreDeDécision
cd arbreDeDécision

La première commande vous positionne dans le dossier qui contient le dossier courant (c'est le dossier dénommé fouilleDeDonnées) ; la deuxième crée un nouveau dossier intitulé arbreDeDécision ; la troisième vous y positionne.
Vous pouvez maintenant lancer R.

La prochaine fois que vous vous connecterez à votre compte, naturellement, les dossiers seront toujours là. Il nefaudra plus faire tout ce que l'on vient d'indiquer, mais simplement vous positionnez dans le dossier correspondant au TP sur les arbres de décision, en tapant les commandes :

cd fouilleDeDonnées
cd arbreDeDécision

Si vous vouliez retrouver vos commandes du TP d'introduction à R, il vous suffirez de vous positionnez dans le dossier correspondant à ce TP et d'y lancer R, soit :

cd ~/fouilleDeDonnées
cd introductionR

La construction d'un arbre de décision

Chargement de la bibliothèque rpart

Pour pouvoir construire des arbres de décision, nous allons utiliser la bibliothèque rpart de l'environnement R. Il faut tout d'abord la rendre accessible. Pour cela, on tape la la commande suivante :

library(rpart)

À chaque fois que vous lancez R et que vous voulez utiliser les fonctions qui vont être décrites ci-dessous, il faut taper cette commande.

Chargement du jeu de données

Nous allons tout d'abord découvrir cette bibliothèque sur l'exemple du jeu de tennis. Commençons par charger le jeu de données comme on l'a vu lors du premier TP :

> tennis <- read.table
  ("http://www.grappa.univ-lille3.fr/~ppreux/ensg/miashs/datasets/tennum.txt")

Placé dans un data frame, on peut maintenant visualiser ce jeu de données :

> tennis
         Ciel Température Humidité   Vent Jouer
1  Ensoleillé        27.5       85 Faible    Non
2  Ensoleillé        25.0       90   Fort    Non
3     Couvert        26.5       86 Faible    Oui
4       Pluie        20.0       96 Faible    Oui
5       Pluie        19.0       80 Faible    Oui
6       Pluie        17.5       70   Fort    Non
7     Couvert        17.0       65   Fort    Oui
8  Ensoleillé        21.0       95 Faible    Non
9  Ensoleillé        19.5       70 Faible    Oui
10      Pluie        22.5       80 Faible    Oui
11 Ensoleillé        22.5       70   Fort    Oui
12    Couvert        21.0       90   Fort    Oui
13    Couvert        25.5       75 Faible    Oui
14      Pluie        20.5       91   Fort    Non

Construction d'un arbre de décision

Les commandes suivantes permettent de construire l'arbre de décision.

Tout d'abord, on doit spécifier quelques paramètres qui précise comment l'arbre de décision doit être construit.

On tapera la commande suivante :

> ad.tennis.cnt <- rpart.control (minsplit = 1)

La variable ad.tennis.cnt stocke les paramètres de l'algorithme.
minsplit = 1 signifie que le nombre minimal d'exemples nécessaires à la création d'un nœud est 1. La valeur par défaut est 20. Comme le jeu de données contient moins de 20 exemples, utiliser la valeur par défaut ne produirait pas d'arbre du tout, juste une racine !

(Remarque en passant : le nom utilisé pour cette variable, ad.tennis.cnt suit la convention R : il indique qu'il s'agît d'un arbre de décision (préfixe ad), pour le jeu de tennis (tennis !) et qu'il s'agît des paramètres de contrôle (cnt) ; des points (.) séparent ces différentes informations. Tout cela est complétement libre ; on aurait pu l'appeler toto, R ne nous l'aurait pas interdit. Par contre, pour nous, humains, c'est autrement plus parlant ainsi que toto. Vous prendrez donc l'habitude de nommer les variables en suivant ce principe.)

On va construire l'arbre de décision en indiquant :

C'est ce que fait la commande suivante :

> ad.tennis <- rpart (Jouer ~ Ciel + Température + Humidité + Vent, tennis, control = ad.tennis.cnt)

Dans cette commande, la notation :

Jouer ~ Ciel + Température + Humidité + Vent

est courante en R, lorsqu'il s'agît de construire un modèle de prédiction (classification supervisée ou régression). Elle signifie : prédire l'attribut Jouer en fonction des attributs Ciel, Température, Humidité et Vent

Après avoir effectuer cette commande, la variable ad.tennis contient l'arbre de décision qui a été construit. Regardons à quoi il ressemble...

Visualisation de l'arbre de décision

Représentation textuelle

On peut alors afficher le résultat de la construction sous forme de texte :

> ad.tennis
n= 14 

node), split, n, loss, yval, (yprob)
      * denotes terminal node

 1) root 14 5 Oui (0.3571429 0.6428571)  
   2) Ciel=Ensoleillé,Pluie 10 5 Non (0.5000000 0.5000000)  
     4) Humidité>=82.5 5 1 Non (0.8000000 0.2000000)  
       8) Température>=20.25 4 0 Non (1.0000000 0.0000000) *
       9) Température< 20.25 1 0 Oui (0.0000000 1.0000000) *
     5) Humidité< 82.5 5 1 Oui (0.2000000 0.8000000)  
      10) Température< 18.25 1 0 Non (1.0000000 0.0000000) *
      11) Température>=18.25 4 0 Oui (0.0000000 1.0000000) *
   3) Ciel=Couvert 4 0 Oui (0.0000000 1.0000000) *

Prenez le temps d'essayer de comprendre ce qui est affiché.

Représentation graphique

On peut également obtenir une représentation graphique :

> plot (ad.tennis)
> text (ad.tennis)

(La commande plot dessine l'arbre alors que la commande text affiche le texte dans les nœuds et sur les branches.)

Voyez si ce que vous voyez graphiquement est compatible avec ce que vous aviez compris dans la représentation textuelle. Si nécessaire, reprenez le temps de comprendre la représentation textuelle.

L'aspect graphique de l'arbre peut être paramétré. Essayez (interprétez chaque commande et toutes les valeurs affichées) :

La prédiction de la classe d'une donnée par un arbre de décision

La fonction predict() utilise un arbre de décision pour prédire la classe de nouvelles données. Elle prend en paramètres l'arbre et un data frame qui contient les données dont il faut prédire la classe. Pour prédire la classe des données du jeu d'exemples (avec lesquels on a construit l'arbre de décision), on tapera la commande :

> predict(ad.tennis, tennis)
   Non Oui
1    1   0
2    1   0
3    0   1
4    0   1
5    0   1
6    1   0
7    0   1
8    1   0
9    0   1
10   0   1
11   0   1
12   0   1
13   0   1
14   1   0

Exercice : utilisez l'arbre pour donner une prédiction dans les situations suivantes :

        Ciel Température Humidité   Vent
1 Ensoleillé          30       90 Faible
2    Couvert          25       70   Fort
3      Pluie          15       86   Fort

Indication : vous avez deux possibilités :

  1. mettre ces données dans un fichier dont le format est similaire à tennum.txt, puis le chargez dans un data frame et faire la prédiction ;
  2. créer directement un data frame.

Il FAUT que vous sachiez faire les deux. Donc, faites-le.

Voitures : un exemple un peu plus réaliste

On va utiliser ici le jeu de données car.test.frame. Affichez son contenu. Vous obtiendrez plus de renseignements sur ce jeu de données avec la commande ?car.test.frame.

Exercice : construisez un arbre de décision (appelez-le ad.car) à partir de ce jeu de données pour prédire la variable Type à partir des autres variables (Price, Country, ...). Vous utiliserez les mêmes paramètres que pour le tennis (minsplit=1). Que pensez-vous de l'arbre obtenu ? Comment pourrait-on l'améliorer ?

Validation croisée, élagage et estimation des erreurs apparente et réelle

Élagage

Il est possible d'élaguer automatiquement un arbre de décision avec la fonction prune() (qui veut dire élaguer, en anglais) (ça veut dire prune aussi, d'ailleurs). Essayez par exemple, sur l'arbre des voitures prune(arbre, 0.02). La valeur passée en paramètre (0.02) s'appelle le « complexity parameter ». Sa définition exacte se trouve dans le document pdf mis en référence. Essayez plusieurs valeurs de ce paramètre et observez son effet sur l'arbre élagué.

Détermination de l'abre optimal

La question se pose maintenant de déterminer quel est l'arbre optimal (celui qui risque le moins de faire des erreurs de prédiction). Par défaut, rpart() effectue un élagage de l'arbre et une validation croisée à 10 plis sur chaque arbre élagué. Les mesures effectuées au long de cette procédure sont stockées dans une table dénommée la cptable.

Supposons que l'arbre de décision construit avec le jeu de données sur les voitures soit placé dans ad.car. La commande ad.car$cptable affiche cette table qui va nous permettre de répondre à la question précédente (quel est l'arbre optimal) :

> ad.car$cptable
          CP nsplit  rel error    xerror       xstd
1 0.28888889      0 1.00000000 1.1333333 0.06146363
2 0.20000000      1 0.71111111 0.8444444 0.08294973
3 0.13333333      2 0.51111111 0.7111111 0.08587483
4 0.04444444      3 0.37777778 0.5333333 0.08432740
5 0.03333333      5 0.28888889 0.6222222 0.08587483
6 0.02222222      9 0.15555556 0.5555556 0.08486251
7 0.01111111     14 0.04444444 0.5111111 0.08369059
8 0.01000000     18 0.00000000 0.5111111 0.08369059

Il est possible que vous n'obteniez pas les mêmes résultats car le choix des exemples dans la validation croisée est aléatoire. rel error mesure l'erreur apparente (erreur d'entraînement). xerror mesure le taux d'erreur dans la validation croisée à 10 plis que l'on considère comme un estimateur correct de l'erreur réelle. xstd est l'écart-type de l'erreur de validation croisée. L'arbre qui nous intéresse est celui qui minimise xerror + xstd (l'erreur moyenne estimée + 1 écart-type). Si plusieurs arbres minimise cette valeur, on prend toujours le plus petit (à performances équivalentes, on choisit le plus petit modèle).

Les autres arbres

L'arbre que vous obtenez par la commande rpart() correspond à la dernière ligne de la cptable : c'est le plus grand. Les lignes précédentes correspondent aux différents élagages de cet arbre qui produisent des arbres de plus en plus petits, jusqu'à obtenir une racine-feuille.

Vous pouvez obtenir tous les autres arbres aussi (les 7 autres, ici). Pour cela, il faut indiquer le cp dans la fonction prune(). Il faut bien comprendre comment se lit cette table et la relation entre valeur de cp et l'arbre élagué correspondant :

Notez bien que la borne inférieure de l'intervalle est exclus : la valeur de cp = 0,2 correspond à l'arbre 3, pas au 2.

Détermination de la probabilité d'erreur de prédiction d'un arbre de décision

Vous avez obtenu cet arbre dont nous n'indiquons que le début ci-dessous :

> ad.car
n= 60

node), split, n, loss, yval, (yprob)
      * denotes terminal node

  1) root 60 45 Compact (0.25 0.05 0.22 0.22 0.15 0.12)
    2) Weight>=2567.5 45 30 Compact (0.33 0.067 0.29 0 0.16 0.16)
      4) Weight< 3127.5 24  9 Compact (0.62 0 0.17 0 0.21 0)
...

Les nombres 60 et 45 indiquent respectivement le nombre d'exemples avec lesquels l'arbre est construit (60) et le nombre d'exemples mal classés par la racine-feuille (45). Réduit à une simple racine, l'arbre fait donc une erreur de 45/60.

Dans la cptable, les valeurs d'erreur sont normalisées pour en simplifier l'interprétation. Cette normalisation consiste à faire en sorte que l'erreur apparente de la racine-feuille soit égale à 1. Clairement, pour cela, R a divisé cette valeur (ainsi que toutes les valeurs des colonnes rel error, xerror et xstd) par l'erreur de la racine-feuille que l'on a calculé juste au-dessus (45/60).

Maintenant, on peut calculer l'erreur apparente de chacun des arbres construits par rpart pour les différentes valeurs de cp : il suffit de multiplier sa rel error par l'erreur de la racine-feuille. L'erreur apparente telle qu'on l'a définie en cours est l'erreur de l'arbre non élagué (le plus grand, c'est-à-dire celui qui correspond à la dernière ligne de la cptable).

Références

Annexes

La fonction plot()

On indique uniquement les bases de la fonction plot(). Elle permet de faire des graphes de courbes. Supposons que vous tapiez :

x <- c (1, 3, 2, -5)
y <- c (0.1, 0.2, 0.9, -0.05)
plot (x, y)

vous obtenez un graphique avec 4 points dont les abscisses sont dans le vecteur x, les ordonnées dans le vecteur y. Plutôt que des vecteurs, ce peut être aussi des colonnes (attributs) d'un data frame.

Vous pouvez spécifier des légendes et une couleur (verte) pour les points :

plot (x, y, main = "graphique de base", xlab = "légende des x", ylab = "légende des y", col = "green")

La fonction lines()

lines() permet d'ajouter une ligne brisée sur un graphique déjà commencé avec plot(). Supposons que l'on veuille ajouter une ligne bleue qui va du point (-2, 0.2) au point (0, 0.1), de là au point (-4, 0.6) et de là, au point (1, 0.5). Je tape les commandes suivantes : (en supposant que vous avez tapé au préalable les commandes ci-dessus concernant la fonction plot())

x.zigzag <- c (-2, 0, -4, 1)
y.zigzag <- c (0.2, 0.1, 0.6, 0.5)
lines (x.zigzag, y.zigzag, col = "blue")

Le paramètre lty permet de représenter les segments en pointillés, ... Par exemple :

lines (c(-1,1,-3), c (0.1, -0.1, 0.5), col = "green", lty=2)

La valeur de lty est un entier compris entre 1 (lignes pleines = par défaut) et 6. Faites des essais.

La fonction points()

points() permet d'ajouter des points sur un graphique déjà commencé avec plot(). Supposons que l'on veuille ajouter des points rouges en (0, 0), (1, 1) et (-2, 0.5). Je tape les commandes suivantes : (en supposant que vous avez tapé au préalable les commandes ci-dessus concernant la fonction plot())

x.points <- c (0, 1, -2)
y.points <- c (0, 1, 0.5)
points (x.points, y.points, col = "red")

Le paramètre pch permet de représenter les points de différentes manières (disque plein, carré, triangle, ...). Par exemple :

points (c (0.45, 0.45), c(0.55, 0.65), col = "dark blue", pch = 19)

affiche les points sous forme de disques (pch = 19) bleus foncés (col = "drak blue"). La valeur de pch est un entier compris entre 1 (par défaut : un cercle) et 25. Faites des essais.