Introduction

Construction d’un arbre binaire maximal

Élagage et arbre optimal

Apprentissage Machine / Statistique

Arbres binaires de décision

P HILIPPE B ESSE

INSA de Toulouse
Institut de Mathématiques

INSA de Toulouse - Apprentissage Machine Arbres binaires

 Introduction
Construction d’un arbre binaire maximal
Élagage et arbre optimal

Introduction
Classification and regression trees (CART)
Breiman et col. (1984)
X j explicatives quantitatives ou qualitatives
Y quantitative : regression tree
Y qualitative à m modalités {T` ; ` = 1 . . . , m} : classification
tree
Objectif : construction d’un arbre de décision binaire
simple à interpréter
Méthodes calculatoires : pas d’hypothèses mais des
données

INSA de Toulouse - Apprentissage Machine Arbres binaires

 Introduction
Construction d’un arbre binaire maximal
Élagage et arbre optimal

 
 
Revenu < 10000
@ Revenu > 10000
@
@
   
@
@
   
Sexe=H@ Sexe=FAge < 50
@ Age > 50
@ @
@@ 
@
@ 
Tj T` Tj  

Exemple fictif : arbre binaire de classification

INSA de Toulouse - Apprentissage Machine Arbres binaires

 Principe
Introduction
Critère de division
Construction d’un arbre binaire maximal
Règle d’arrêt et affectation
Élagage et arbre optimal
Critères d’homogénéité

Définitions
Déterminer une séquence itérative de nœuds
Racine : nœud initial ou ensemble de l’échantillon
Feuille : nœud terminal
Nœud : choix d’une variable et d’une division
sous-ensemble auquel est appliquée une dichotomie
Division : valeur seuil ou groupes des modalités

INSA de Toulouse - Apprentissage Machine Arbres binaires

 Principe
Introduction
Critère de division
Construction d’un arbre binaire maximal
Règle d’arrêt et affectation
Élagage et arbre optimal
Critères d’homogénéité

C1
C8 C9
X 1  d1 X 1 > d1

d2
C2 C3
C3
X 2  d2 X 2 > d2

C4
C4 C5
X2
X 1  d3 X 1 > d3

C8 C9 d3 d1
X1

Exemple fictif : pavage dyadique de l’espace

INSA de Toulouse - Apprentissage Machine Arbres binaires

 Principe
Introduction
Critère de division
Construction d’un arbre binaire maximal
Règle d’arrêt et affectation
Élagage et arbre optimal
Critères d’homogénéité

Règles
Choix nécessaires :
1 Critère de la “meilleure” division parmi celles admissibles
2 Règle de nœud terminal : feuille
3 Règle d’affectation à une classe T` ou une valeur de Y
Division admissible : descendants 6= ∅
X j réelle ou ordinale : (cj − 1) divisions possibles
Attention effets incontrôlables si c grand
X j nominale : 2(cj −1) − 1 divisions
Fonction d’hétérogénéité Dκ d’un nœud
1 Nulle : une seule modalité de Y ou Y constante
2 Maximale : modalités de Y équiréparties ou grande
variance

INSA de Toulouse - Apprentissage Machine Arbres binaires

 Principe
Introduction
Critère de division
Construction d’un arbre binaire maximal
Règle d’arrêt et affectation
Élagage et arbre optimal
Critères d’homogénéité

Division optimale
Notation
κ : numéro d’un nœud
κG et κD les nœuds fils
L’algorithme retient la division rendant minimales

DκG + DκD

Chaque étape κ de construction de l’arbre :

max Dκ − (D(κG + DκD )

{Divisions de X j ;j=1,p}

INSA de Toulouse - Apprentissage Machine Arbres binaires

 Principe
Introduction
Critère de division
Construction d’un arbre binaire maximal
Règle d’arrêt et affectation
Élagage et arbre optimal
Critères d’homogénéité

Feuille et affectation
Un Nœud est terminal ou feuille, si :
Homogène
Plus de partition admissible
Nombre d’observations inférieur à un seuil
Affectation
Y quantitative, la valeur est la moyenne des observations
Y qualitative, chaque feuille est affectée à une classe T` de
Y en considérant le mode conditionnel :
la classe la mieux représentée dans le nœud
la classe a posteriori la plus probable si des a priori sont
connus
la classe la moins coûteuse si des coûts de mauvais
classement sont donnés

INSA de Toulouse - Apprentissage Machine Arbres binaires

 Principe
Introduction
Critère de division
Construction d’un arbre binaire maximal
Règle d’arrêt et affectation
Élagage et arbre optimal
Critères d’homogénéité

Y quantitative : hétérogénéité en régression

Hétérogénéité du nœud κ :

1 X
Dκ = (yi − yκ )2
|κ|
i∈κ

où |κ| est l’effectif du nœud κ

Minimiser la variance intra-classe

Les nœud fils κG et κD minimisent :

|κG | X |κD | X
(yi − yκG )2 + (yi − yκD )2 .
n n
i∈κG i∈κD

Hétérogénéité et déviance dans le cas gaussien

(Breiman et al. 1984)
INSA de Toulouse - Apprentissage Machine Arbres binaires
 Principe
Introduction
Critère de division
Construction d’un arbre binaire maximal
Règle d’arrêt et affectation
Élagage et arbre optimal
Critères d’homogénéité

Y qualitative : hétérogénéité en discrimination

Hétérogénéité du nœud κ :
Entropie avec la notation 0 log(0) = 0
m
X
Dκ = −2 |κ|p`κ log(p`κ )
`=1

p`κ : proportion de la classe T` de Y dans κ.

Concentration de Gini : Dκ = m ` `
P
`=1 pκ (1 − pκ )
Statistique du test du χ2 (CHAID)
Entropie et déviance d’un modèle multinomial (Breiman et al.
1984)

INSA de Toulouse - Apprentissage Machine Arbres binaires

 Principe
Introduction
Critère de division
Construction d’un arbre binaire maximal
Règle d’arrêt et affectation
Élagage et arbre optimal
Critères d’homogénéité

Discrimination : extensions
Les probabilités conditionnelles sont définies par la règle
de Bayes lorsque les probabilités a priori π` sont connues
Sinon, les probabilités de chaque classe sont estimées sur
l’échantillon et donc les probabilités conditionnelles
s’estiment par des rapports d’effectifs :

p`k est estimée par n`k /n+k

Des coûts de mauvais classement connus conduisent à la

minimisation d’un risque bayésien

INSA de Toulouse - Apprentissage Machine Arbres binaires

 Introduction Construction de la séquence d’arbres
Construction d’un arbre binaire maximal Recherche de l’arbre optimal
Élagage et arbre optimal Exemples

Élagage : notations
Recherche d’un modèle parcimonieux
Complexité d’un arbre : KA = nombre de feuilles de A
Qualité d(ajustement de A :
KA
X
D(A) = Dκ
κ=1

Dκ : hétérogénéité feuille κ

INSA de Toulouse - Apprentissage Machine Arbres binaires

 Introduction Construction de la séquence d’arbres
Construction d’un arbre binaire maximal Recherche de l’arbre optimal
Élagage et arbre optimal Exemples

Séquence d’arbres emboı̂tés

Critère de qualité pénalisé par la complexité :

C(A) = D(A) + γ × KA

Pour γ = 0 : Amax = AKA minimise C(A)

Lorsque γ croı̂t, la division de AH , dont l’amélioration de D
est inférieure à γ, est annulée ; ainsi
deux feuilles sont regroupées (élaguées)
le nœud père devient terminal
AKA devient AKA −1
Après itération du procédé :

Amax = AKA ⊃ AKA −1 ⊃ · · · A1

INSA de Toulouse - Apprentissage Machine Arbres binaires

 Introduction Construction de la séquence d’arbres
Construction d’un arbre binaire maximal Recherche de l’arbre optimal
Élagage et arbre optimal Exemples

Algorithme de sélection de l’arbre optimal

Arbre maximal Amax
Séquence AK . . . A1 emboı̂tée associée à
Séquence des valeurs γκ
for dov = 1, . . . , V
Estimation de la séquence d’arbres associée à γκ
Estimation de l’erreur
end for
Séquence des moyennes de ces erreurs
γOpt optimal
Arbre associé à γOpt dans AK . . . A1
Attention : Séquences d’arbres différentes, même séquence γκ

INSA de Toulouse - Apprentissage Machine Arbres binaires

 Introduction Construction de la séquence d’arbres
Construction d’un arbre binaire maximal Recherche de l’arbre optimal
Élagage et arbre optimal Exemples

Remarques pratiques
Sélection de variables et interactions
Invariance par transformation monotone
Hiérarchie et instabilité
Découpes compétitives, surrogate et données manquantes
Variantes : ternaire, linéaire...
Approximation étagée de la régression : algorithme MARS

INSA de Toulouse - Apprentissage Machine Arbres binaires

 Introduction Construction de la séquence d’arbres
Construction d’un arbre binaire maximal Recherche de l’arbre optimal
Élagage et arbre optimal Exemples

Ozone : arbre de discrimination élagué par validation croisée

INSA de Toulouse - Apprentissage Machine Arbres binaires
 Introduction Construction de la séquence d’arbres
Construction d’un arbre binaire maximal Recherche de l’arbre optimal
Élagage et arbre optimal Exemples

100
250
Valeurs observees

50
Résidus
150

0
−100 −50
50
0

0 50 100 200 300 0 50 100 200 300

Valeurs predites Valeurs predites

Ozone : observations et résidus en fonction des prévisions

INSA de Toulouse - Apprentissage Machine Arbres binaires

 Introduction Construction de la séquence d’arbres
Construction d’un arbre binaire maximal Recherche de l’arbre optimal
Élagage et arbre optimal Exemples

Banque : élagage par échantillon de validation

INSA de Toulouse - Apprentissage Machine Arbres binaires

 Introduction Construction de la séquence d’arbres
Construction d’un arbre binaire maximal Recherche de l’arbre optimal
Élagage et arbre optimal Exemples
Endpoint = CARVP

Cnon
569/294
|

MOYRVL< 3.02
MOYRVL>=3.02
Cnon Coui
475/90 94/204

RELAT>=5.5 DMVTPL>=2.602
RELAT< 5.5 DMVTPL< 2.602
Cnon Coui Coui Coui
462/61 13/29 93/121 1/83

FACANL< 11.44 AGER< 26DMVTPL< 2.674

FACANL>=11.44 AGER>=26 DMVTPL>=2.674
Cnon Coui Cnon CnonCoui Coui
457/51 5/10 8/0 70/17
5/29 23/104

DMVTPL>=2.602 FACANL< 11.32

DMVTPL< 2.602 FACANL>=11.32
Cnon Cnon Cnon Coui
381/28 76/23 67/10 3/7

DMVTPL< 1.199
DMVTPL>=1.199
Cnon Coui
76/3 0/20

Banque : Elagage par validation croisée

INSA de Toulouse - Apprentissage Machine Arbres binaires