Classification Supervisée.
Algorithme CART et forêts aléatoires.
1 Arbres de décisions
Un arbre de décision est un classifieur t : X → Y qui s’exprime sous la forme d’une
succession de questions/réponses posées sur les données.
Exemple : On suppose que les variables observées sont X = (T, P, F ), où :
— T : variable quantitative, taille de l’individu en m
— P : variable quantitative, poids de l’individu en kg
— F : variable qualitative, 1 si l’individu est fumeur, 0 s’il ne l’est pas,
et que la variable Y à prédire vaut 1 si l’individu présente un risque de développer une certaine
pathologie, 0 si l’individu n’a pas de risque. On peut par exemple définir un classifieur t ainsi :
La première "question" posée Q1 est : le rapport P/T 2 (indice de masse corporelle) est-il
inférieur à 25, compris entre 25 et 30, ou supérieur à 30 ?
— s’il est inférieur à 25, on estime qu’il n’y a pas de risque (on pose donc Ŷ = t(X) = 0)
— s’il est compris entre 25 et 30, on pose une deuxième question Q2 : l’individu est-il fumeur
ou pas (F = 1 ou F = 0) ?
— s’il est fumeur on estime qu’il y a un risque : Ŷ = t(X) = 1,
— sinon on pose Ŷ = t(X) = 0
— s’il est supérieur à 30, on estime qu’il y a un risque : Ŷ = t(X) = 1
On peut visualiser cette règle sous la forme d’un arbre :
Un peu de terminologie à connaître : cet arbre contient 5 branches, et 6 noeuds. Parmi ces
noeuds, on distingue le noeud racine en haut, et 4 noeuds terminaux, appelés aussi feuilles.
Lorsque tous les noeuds non terminaux n’ont que deux branches (autrement dit lorsque
chaque question posée n’a que deux réponses possibles), on dit que l’arbre est binaire. Ici ce
n’est pas le cas, puisque le noeud racine a trois branches. Remarquons cependant qu’on peut
toujours définir un arbre binaire équivalent à n’importe quel arbre, en ajoutant des noeuds. Voici
par exemple l’arbre binaire équivalent à l’arbre précédent :
1
2 La méthode CART
Comment construire un arbre de classification performant à partir de données d’apprentissage
(Xi , Yi ) 1 ≤ i ≤ n ? La méthode CART (Classification And Regression Trees) a été introduite
par Breiman, Friedman, Olshen et Stone en 1984 ; elle est sans doute la plus connue. Comme
son nom l’indique, il s’agit d’une méthode permettant de construire des arbres pour faire de la
classification (i.e. l’ensemble Y est fini) aussi bien que pour de la régression (Y = R). Dans le
cadre de ce cours nous ne parlons que de classification.
La construction de l’arbre par la méthode CART se fait progressivement. On se place d’abord
au noeud racine et on considère un ensemble de questions possibles à poser. Pour chacune de ces
questions on calcule les réponses à cette question pour tous les individus de la base, ce qui sépare
la population en plusieurs sous-populations. On évalue alors les proportions de Y = 0 et Y = 1
parmi ces sous-populations, ce qui permet de choisir la meilleure question (cf plus bas). Puis
on recommence le procédé dans chaque sous-branche ainsi crée, avec la sous-population corres-
pondante. On s’arrête lorsque la sous population ne contient plus qu’une seule classe Y = 0 ou
Y = 1 (à moins qu’on décide de s’arrêter avant suivant un autre critère). Un noeud ne contenant
ainsi qu’une seule classe est appelé noeud pur.
Voici les principes permettant de définir la méthode CART :
— chaque question posée ne concerne qu’une seule variable,
— chaque question posée doit être la plus discriminante possible, c’est-à-dire qu’elle doit
permettre de séparer au mieux les deux classes parmi les données d’apprentissage.
Quelques remarques sur ces principes : le premier principe est restrictif : ainsi dans l’exemple
précédent, la première question porte sur les deux variables P et T , et donc cette question ne
pourrait pas être considérée avec la méthode CART. Ensuite le deuxième principe nécessite pour
être appliqué d’avoir une mesure de l’homogénéité des classes dans une population. Ceci se fait
à l’aide de l’indice de Gini :
Définition 2.1. Soit h un noeud, on appelle indice de Gini de h la quantité
I(h) = 1 − P1 (h)2 − P0 (h)2
2
où P0 (h) (respectivement P1 (h)) est la proportion de la classe 0 (resp. 1) parmi la sous-population
associée au nœud h.
Plus l’indice de Gini est petit, meilleur est le nœud : l’une des deux classes prédomine.
Remarque 2.1. Dans le cas binaire on a P1 (h) = 1 − P0 (h), de sorte que I(h) = 2P0 (h)(1 −
P0 (h)) = 2P1 (h)(1 − P1 (h)). Voici ci-dessous le tracé de la valeur de I(h) en fonction de P0 (h).
On voit bien que plus les deux classes sont hétérogènes dans le noeud (P0 (h) grand par rapport à
P1 (h) ou l’inverse), plus l’indice de Gini est petit.
Lorsqu’on considère une question possible à poser, on crée deux noeuds dans l’arbre cor-
respondant aux deux réponses possibles. On voudrait que chacun de ces noeuds ait un indice
de Gini le plus petit possible. De plus il est logique d’accorder plus d’importance à un noeud
contenant beaucoup d’individus. Par conséquent on va chercher à minimiser la somme des indices
de Gini de chaque noeud, pondérée par la taille de la population. On arrive donc à la règle de
segmentation suivante :
Règle de segmentation : On découpe le nœud h selon la variable X p , p ∈ {1, . . . , P }
telle que
p1 I(X p = 1) + p0 I(X p = 0)
où p1 (resp. p0 ) est la proportion d’individus du nœud h ayant la modalité X p = 1 (resp.
X p = 0), p0 = 1 − p1 soit minimal.
Exemple : On va étudier la construction de l’arbre à partir d’un exemple. On dispose des
données suivantes concernant des matchs d’une équipe de football :
3
observation match (X 1 ) balance (X 2 ) mauvaise condition (X 3 ) match précédent (X 4 ) match (Y )
à domicile positive climatique gagné gagné
e1 Vrai Vrai Faux Faux Vrai
e2 Faux Faux Vrai Vrai Vrai
e3 Vrai Vrai Vrai Faux Vrai
e4 Vrai Vrai Faux Vrai Vrai
e5 Faux Vrai Vrai Vrai Faux
e6 Faux Faux Vrai Faux Faux
e7 Vrai Faux Faux Vrai Faux
e8 Vrai Faux Vrai Faux Faux
On prend la convention X p = 1 si X p =Vrai, et X p = 0 si X p =Faux, et Y = 1 si Y =Gagné
et Y = 0 si Y =Perdu. On dispose de 8 individus, les 8 équipes dont 4 ont le label ’Gagné’ et 4
le label ’Perdu’.
— On commence par la racine de l’arbre, contenant tous les individus. On a 4 question
possibles à poser : ”X 1 = 1?”, ”X 2 = 1?”, ”X 3 = 1?”, ”X 4 = 1?”.
— Si on veut découper la racine de l’arbre selon la variable X 1 (question ”X 1 = 1?”), on
crée deux nouveaux noeuds :
— Dans le noeud X 1 = 1, on aura les observations e1 , e3 , e4 , e7 , e8 (donc 5 obser-
vations). Parmi elles, trois ont la modalité Y = 1 (e1 , e3 et e4 ), et deux ont la
modalité Y = 0 (e7 et e8 ). Par conséquent,
3 2 2 2
I(X 1 = 1) = 1 − − = 0.48.
5 5
— Dans le noeud X 1 = 0, on aura les observations e2 , e5 , e6 (donc 3 observations).
Parmi elles, une a la modalité Y = 1 (e2 ), et deux ont la modalité Y = 0 (e5 et
e6 ). Par conséquent,
1 2 2 2
I(X 1 = 0) = 1 − − = 0.44.
3 3
A final la somme pondérée pour ce choix de question vaut :
5 3
I(X 1 = 1) + I(X 1 = 0) = 0.465.
8 8
— On recommence les calculs en envisageant cette fois la question ”X 2 = 1?”). On aura
alors 3 2 1 2
I(X 2 = 1) = 1 − − = 0.375,
4 4
1 2 3 2
I(X 2 = 0) = 1 − − = 0.375,
4 4
et donc la somme pondérée pour ce choix vaut 0.375.
— On procède de même avec la question ”X 3 = 1?”. On aura alors
2 2 3 2
I(X 3 = 1) = 1 − − = 0.48,
5 5
2 2 1 2
I(X 3 = 0) = 1 − − = 0.44,
3 3
et donc la somme pondérée pour ce choix vaut
5 3
I(X 3 = 1) + I(X 3 = 0) = 0.465.
8 8
4
— Enfin pour la question ”X 4 = 1?” :
2 2 2 2
I(X 4 = 1) = 1 − − = 0.5,
4 4
2 2 2 2
I(X 4 = 0) = 1 − − = 0.5,
4 4
et donc la somme pondérée pour ce choix vaut 0.5.
Conclusion : le choix de question donnant la plus petite valeur du critère est la question
portant sur X 2 (valeur 0.375). On a ainsi commencé à construire notre arbre ainsi :
On doit ensuite continuer le découpage dans chaque noeud créé. Notons que la question
portant sur X 2 ayant déjà été posée, il est inutile de la considérer à nouveau (N.B. ce
serait différent si la variable n’était pas binaire, voir plus bas).
— Pour le noeud X 2 = 1, contenant les observations e1 , e3 , e4 , e5 , on envisage les 3 questions
possibles :
— Si on découpe ce noeud suivant la valeur de X 1 , alors :
— dans la branche X 1 = 1 on aura e1 , e3 , e4 (3 individus). Tous sont de type Y = 1.
Donc,
3 2 0 2
I(X 1 = 1) = 1 − − = 0.
3 3
— dans la branche X 1 = 0 on aura e5 , qui est de type Y = 0. Donc,
0 2 1 2
I(X 1 = 0) = 1 − − = 0.
1 1
La somme pondérée pour ce choix vaut donc 0. Comme il s’agit de la valeur minimale,
il est en fait inutile de considérer les deux autres questions. On est certain d’être
optimal en choisissant cette question.
Ainsi notre arbre devient à présent :
Notons que les deux nouveaux noeuds ainsi créés sont purs : il n’y aura plus besoin de les
découper à nouveau.
— Pour le noeud X 2 = 0, contenant les observations e2 , e6 , e7 , e8 , on envisage les 3 questions
possibles :
5
— Si on découpe ce noeud suivant la valeur de X 1 , alors :
— dans la branche X 1 = 1 on aura e7 et e8 (2 individus). Tous sont de type Y = 0.
Donc,
0 2 2 2
I(X 1 = 1) = 1 − − = 0.
2 2
— dans la branche X 1 = 0 on aura e2 (de type Y = 1) et e6 (de type Y = 0). Donc,
1 2 1 2
I(X 1 = 0) = 1 − − = 0.5.
2 2
La somme pondérée pour ce choix vaut donc
2 2
I(X 1 = 1) + I(X 1 = 0) = 0.25.
4 4
— Si on découpe suivant X 3 , alors :
1 2 2 2
I(X 3 = 1) = 1 − − = 0.44,
3 3
0 2 1 2
I(X 3 = 0) = 1 − − = 0.
1 1
La somme pondérée pour ce choix vaut donc
3 1
I(X 1 = 1) + I(X 1 = 0) = 0.33.
4 4
— Enfin si on découpe suivant X 4 , alors :
1 2 1 2
I(X 4 = 1) = 1 − − = 0.5,
2 2
0 2 2 2
I(X 4 = 0) = 1 − − = 0.
2 2
La somme pondérée pour ce choix vaut donc
2 2
I(X 1 = 1) + I(X 1 = 0) = 0.25.
4 4
Finalement ici on a deux possibilités : découper suivant X 1 ou suivant X 4 . Choisissons
X 1 de façon arbitraire. Notre arbre devient à présent :
6
— Il ne reste plus qu’à découper une dernière fois le noeud contenant e2 et e6 . Il suffit pour
cela de sélectionner une variable discriminante pour ces deux individus ; on aura forcément
alors une valeur 0 pour le critère. C’est le cas en fait pour la variable X 4 uniquement et
pas pour X 3 , donc on choisit de découper suivant X 4 .
Au final l’arbre complet obtenu par la méthode CART sur cet exemple est le suivant :
2.1 Cas de variables non binaires
L’exemple qui vient d’être détaillé ne comportait que des variables binaires. Si une variable
X p n’est pas binaire, on distingue deux cas :
— X p est catégorielle et prend pour modalités {1, . . . , q}, q > 2. Dans ce cas le nœud
correspondant à la segmentation selon la variable X p engendre q nouveaux nœuds (l’arbre
n’est plus binaire). On minimise cette fois la quantité
p1 I(X p = 1) + . . . + pq I(X p = q),
où chaque pk , 1 ≤ k ≤ q correspond à la proportion d’individus ayant la modalité X p = k.
— X p est quantitative : on considère alors des questions du type ”X p ≥ s?”, où s est un
seuil donné. Il y aurait donc a priori une infinité de questions possibles suivant les valeurs
de s. Cependant, on peut voir facilement qu’il n’y a que n − 1 seuils à considérer au plus,
où n est la taille de la sous-population contenue dans le noeud. Voici un autre exemple
pour comprendre ce point : on reprend en fait l’exemple initial du chapitre et on suppose
que l’on dispose des données d’entraînement suivantes :
individu taille (T ) poids (P ) fumeur (F ) risque (Y )
e1 1.60 55 Non Non
e2 1.65 85 Non Oui
e3 1.85 100 Oui Oui
e4 1.70 55 Oui Non
e5 1.75 75 Non Non
Ici les deux premières variables sont quantitatives. Pour déterminer les seuils possibles pour
la variable T , classons les individus par valeurs croissantes de T :
individu e1 e2 e4 e5 e3
taille 1.60 1.65 1.70 1.75 1.85
7
Il n’y alors que 4 questions différentes à considérer pour T . En effet,
— pour une valeur du seuil inférieure à 1.60, ou supérieure à 1.85, la question posée ne sépare
pas la population ; elle est donc inutile.
— pour toutes les valeurs du seuil comprises entre 1.60 et 1.65, les noeuds créés contiendront
d’un côté e1 et de l’autre e2 , . . . , e5 . Toutes ces valeurs de seuil sont donc équivalentes vis-
à-vis des données d’entraînement et correspondent donc à une seule question à considérer.
— de même pour toutes les valeurs du seuil entre 1.65 et 1.70, entre 1.70 et 1.75, entre 1.75
et 1.80, ou entre 1.80 et 1.85. On obtient ainsi 3 seuils discriminants supplémentaires.
Pour la variable P , on peut raisonner de même : dans ce cas il n’y aura en fait que 3 questions
possibles, car deux individus ont un poids égal à 55, ce qui les rend indistinguables vis-à-vis de
cette variable. Enfin pour la variable F , il n’y a qu’une seule question puisque cette variable est
binaire. Au final on a donc 8 questions au total à envisager dans cet exemple.
Notons que dans ce cas l’arbre induit par la méthode CART est très simple : en effet on peut
remarquer que la variable P est totalement discriminante, avec un seuil égal à 80 (ou toute autre
valeur entre 75 et 85), et donc on obtient l’arbre de décision suivant :
Cet arbre a peu de chances d’être performant ; le problème ici est simplement qu’il y a trop
peu de données.
2.2 Critères d’arrêt et élagage de l’arbre
La méthode décrite dans la partie précédente aboutit à des arbres complètement développés,
c’est-à-dire qu’à la fin l’arbre ne contient que des noeuds terminaux purs. En pratique pour des
données réelles avec une grande quantité d’observations, les arbres ainsi créés sont très complexes
et donc peuvent être longs à obtenir et à utiliser par la suite. Mais surtout il y a un fort risque
de sur-apprentissage avec de tels arbres : l’erreur d’apprentissage (ou erreur apparente) est égale
à zéro, mais l’erreur de généralisation sera probablement élevé. Pour éviter ceci, on construit en
pratique des arbres simplifiés, ce qui se fait de deux manières :
— lors de la construction de l’arbre, on fixe des critères d’arrêt afin de ne pas développer
l’arbre jusqu’au bout,
— de plus, une fois la construction de l’arbre terminée, on procède à une étape d’élagage
en supprimant progressivement des branches afin de déterminer un sous-arbre optimal.
Lorsque, l’arbre n’est pas développé jusqu’au bout, la classe associée aux noeuds comprenant
plusieurs observations correspond à la classe majoritaire parmi ces observations. S’il y a égalité,
la classe est choisie de manière arbitraire.
2.2.1 Conditions d’arrêt :
Voici les critères d’arrêt du développement de l’arbre de décision les plus couramment em-
ployés :
— Le nombre de feuilles à atteint le maximum fixé (≤ n).
8
— La profondeur de l’arbre à atteint le maximum fixé (≤ P dans le cas de variables expli-
catives binaires).
— L’effectif (taille de la sous-population) de chaque nœud terminal est inférieur à un seuil
fixé.
2.2.2 Élagage de l’arbre
La solution adoptée par l’algorithme CART pour limiter le sur-apprentissage est l’élagage
de l’arbre : on supprime les feuilles "trop précises" (qui ont un faible nombre d’individus,...)
pour obtenir un sous arbre offrant un classifieur qui soit meilleur en prévision. Les étapes de
l’algorithme sont alors les suivantes :
Étape 1 : Création de l’arbre complet T (en prenant en compte éventuellement des critères
d’arrêt).
Étape 2 : Élagages successifs de l’arbre T : construction d’une suite d’arbres emboîtés Tm =
T . . . T0 .
Étape 3 : Choix de l’arbre élagué T ∗ parmi (T0 , . . . , Tm ) par validation croisée.
On ne détaillera pas ici la méthode utilisée pour l’étape 2.
2.3 Avantages et inconvénients de CART
2.3.1 Avantages
— Sélection automatique des variables discriminantes (les autres n’interviennent pas dans la
construction de l’arbre).
— Accepte tous type de variables.
— Peu sensible aux individus extrêmes.
2.3.2 Inconvénients
— Effet papillon : Si on modifie une seule variable l’arbre peut être modifié complètement
si cette variable est choisie parmi les premières étapes.
— CART est un algorithme glouton (greedy algorithm) : A chaque étape, le choix
d’une variable de segmentation conditionne tout le sous-arbre correspondant. Or le choix
de cette variable se fait sur un critère qui se place à l’étape courante sans prendre en
compte tous les sous-arbres possibles, c’est-à-dire toutes les questions qu’on posera en-
suite. Autrement dit, en cherchant à chaque étape à poser la meilleure question, on élimine
des stratégies possibles qui consisteraient à choisir d’abord des variables moins discrimi-
nantes, puis par la suite des variables très discriminantes, pour au final avoir un arbre très
performant. Ceci amène à utiliser des méta-algorithmes tels que le Bagging ou le Boosting
pour améliorer les performances de CART. La méthode des forêts aléatoires décrite à la
section suivante en est un exemple.
— Temps de calculs importants.
3 Forêts aléatoires
La méthode des forêts aléatoires (Random Forests) est relativement récente (L. Breiman,
2001) et très performante. L’idée consiste à générer un grand nombre d’arbres de décision diffé-
rents en faisant varier de façon aléatoire les données d’entrée. Les règles de décision associées à
9
chaque arbre sont ensuite moyennées pour obtenir le classifieur final. Ceci vise à corriger un des
inconvénients principaux de la méthode CART (effet papillon).
A chaque construction d’un arbre, on fait varier à la fois les variables et les observations,
comme expliqué dans les deux sections suivantes :
3.1 Variation aléatoires des observations : Bagging
A chaque construction d’un arbre, les observations d’entrée sont tirées au sort selon la mé-
thode du bootstrap : on effectue un tirage avec remise de taille n à partir des n observations.
Le tirage avec remise a pour effet de répéter certaines observations, ce qui leur confère plus de
poids, et à l’inverse d’en supprimer certaines autres, tout ceci de façon aléatoire.
Si elle est utilisée seule, cette technique de bootstrap pour les arbres décisionnels est déjà
une méthode efficace, dénommée bagging (pour bootstrap aggregating) : on crée un grand
nombre d’arbres différents par bootstrap sur les observations, puis le classifieur est obtenu par
vote à la majorité (cf plus bas)
3.2 Variation des variables d’entrée
En plus du bagging, l’algorithme des forêts aléatoires ajoute une deuxième source d’aléa en
sous-échantillonant de façon aléatoire les variables candidates lors du développement de l’arbre.
Plus précisément, à chaque étape de l’algorithme CART lors du choix de la question à poser, seul
un sous-ensemble des variables est considéré. Ce sous-ensemble est choisi aléatoirement par tirage
au sort parmi les P variables disponibles, (ce tirage au sort étant re-effectué pour chaque noeud).
Le nombre de variables √ tirées à chaque fois est un paramètre de l’algorithme. Il est souvent fixé
à une valeur proche de P (par exemple sa partie entière).
3.3 Critère d’arrêt des arbres
Dans la méthode des forêts aléatoires, on peut définir un critère d’arrêt de développement
en fixant un seuil sur le nombre d’individus contenus dans un noeud (en dessous du seuil on ne
développe plus). Cependant ceci sert essentiellement à accélérer l’algorithme et non à améliorer les
performances de classification. En effet il y a beaucoup moins de risque de sur-apprentissage avec
les forêts aléatoires, même en développant jusqu’au bout les arbres, car les réponses individuelles
des arbres sont aggrégés dans la réponse finale. Dans l’algorithme implémenté en R ce critère
d’arrêt est d’ailleurs fixé par défaut à 1, autrement dit il est désactivé.
3.4 Vote à la majorité
Ceci est l’étape finale de la méthode des forêts aléatoires : une fois tous les arbres construits,
on définit le classifieur final par vote à la majorité : une observation est classée en l’évaluant sur
tous les arbres et en attribuant la classe majoritaire parmi toutes les réponses.
3.5 Exemple
Voici un exemple complet de classification avec la méthode des forêts aléatoires. On reprend
les données "football" précédentes et on va construire trois arbres aléatoires.
N.B. Cet exemple est fait dans un but purement pédagogique : en pratique cette méthode a
un intérêt pour des données de grande taille et le nombre d’arbres créés doit être grand (500 par
défaut dans l’algorithme R).
10
— Premier arbre : On effectue d’abord le bootstrap : tirage au sort de n observations
parmi n avec remise. On obtient les observations suivantes : e3 , e03 , e6 , e1 , e5 , e01 , e001 , e2 , où
les e0i et e00i désignent des copies des observations ei .
Le tableau de données tab avec lequel on travaille pour ce premier arbre est donc le
suivant :
X1 X2 X3 X4 Y
e3 Vrai Vrai Vrai Faux Vrai
e03 Vrai Vrai Vrai Faux Vrai
e6 Faux Faux Vrai Faux Faux
e1 Vrai Vrai Faux Faux Vrai
e5 Faux Vrai Vrai Vrai Faux
e01 Vrai Vrai Faux Faux Vrai
e001 Vrai Vrai Faux Faux Vrai
e2 Faux Faux Vrai Vrai Vrai
√
— On commence par la racine. On tire au sort 2 variables (car 4 = 2) parmi les 4
variables X 1 , . . . , X 4 .
Les variables sélectionnées sont X 3 et X 1 ; le tableau restreint à ces variables est donc :
X3 X1 Y
e3 Vrai Vrai Vrai
e03 Vrai Vrai Vrai
e6 Vrai Faux Faux
e1 Faux Vrai Vrai
e5 Vrai Faux Faux
e01 Faux Vrai Vrai
e001 Faux Vrai Vrai
e2 Vrai Faux Vrai
On a donc deux choix à étudier :
— découpage suivant X 3 : la branche X 3 = 1 contient e3 , e03 , e6 , e5 , e2 , parmi lesquels
3 sont de type Y = 1 et 2 de type Y = 0. L’indice de Gini vaut donc 1 − (2/5)2 −
(3/5)2 = 0.48. La branche X 3 = 0 contient e1 , e01 , e001 , toutes de type Y = 1, donc
l’indice de Gini vaut 0. Le critère pour ce choix vaut donc (5/8)×0.48+(3/8)×0 =
0.3.
— découpage suivant X 1 : la branche X 1 = 1 contient e3 , e03 , e1 , e01 , e001 , toutes de type
Y = 1, donc l’indice de Gini vaut 0. La branche X 3 = 0 contient e6 , e5 , e2 , parmi
lesquels 1 est de type Y = 1 et 2 de type Y = 0. L’indice de Gini vaut donc
1 − (2/3)2 − (1/3)2 = 0.44. Le critère pour ce choix vaut donc (5/8) × 0 + (3/8) ×
0.44 = 0.17.
Au final le choix qui minimise le critère est le découpage suivant X 1 .
— On passe ensuite aux découpages suivants. Pour la branche X 1 = 1, il n’y a plus rien
à faire car toutes les observations sont de type Y = 1. Donc le découpage s’arrête
là. Il reste à découper la branche X 1 = 0, contenant e6 , e5 , e2 . On tire au sort deux
variables parmi X 2 , X 3 , X 4 (car le découpage suivant X 1 a déjà été utilisé). On obtient
par exemple X 2 et X 4 . Le nouveau sous-tableau de données est donc
X2 X4 Y
e6 Faux Faux Faux
e5 Vrai Vrai Faux
e2 Faux Vrai Vrai
11
On peut voir facilement ici sans faire de calculs que le deux découpages suivant X 2
ou X 4 seront équivalents, car ils donneront une branche contenant une observation de
type Y = 0 et une branche contenant deux observations, une de chaque type. Donc
on peut choisir arbitrairement de découper suivant X 2 par exemple, ce qui donne la
branche X 2 = 1 contenant e5 et la branche X 2 = 0 contenant e6 et e2 .
— Il ne reste enfin qu’à découper la branche X 2 = 0, contenant e6 et e2 . Comme il ne
reste que les deux variables X 3 et X 4 , le tirage au sort des variables est inutile. Le
sous-tableau de données est à présent
X3 X4 Y
e6 Vrai Faux Faux
e2 Vrai Vrai Vrai
La seule variable qui sépare les données est alors X 4 , et c’est donc la seule possible
pour le découpage.
On a donc achevé la construction du premier arbre aléatoire. Voici sa représentation, où
l’on a noté dans chaque noeud les observations restantes et les deux variables tirées au
sort pour le prochain découpage :
— On reprend le même principe pour construire deux autres arbres aléatoires. Voici les arbres
obtenus :
Deuxième arbre : cet arbre ne contient que deux branches ; en effet le tirage au sort
initial des observations et des variables fait qu’il est possible de séparer parfaitement les
deux classes Y = 1 et Y = 0 en découpant avec la variable X 2 :
12
Troisième arbre : cet arbre est au contraire plus complexe que le premier :
— Au final la forêt aléatoire est construite. On peut maintenant utiliser le classifieur ainsi :
supposons qu’on cherche à classer une nouvelle observation e9 , de variables X = (0, 0, 0, 1).
Alors en suivant les trois arbres on a :
— e9 est classé en Y = 1 suivant le premier arbre,
— e9 est classé en Y = 0 suivant le deuxième arbre,
— e9 est classé en Y = 1 suivant le troisième arbre,
et par conséquent l’estimation obtenue par vote à la majorité sera Ŷ = 1.
13
