Apprentissage supervisé

ARBRE DE DÉCISION
Présentation générale
■ L'arbre de décision est une technique d'apprentissage
supervisé actif.
■ Il fait partie des méthodes d'apprentissage automatique
supervisé qui visent à apprendre des relations entre un
ensemble de caractéristiques (variables indépendantes) et
une variable cible (variable dépendante) à partir de données
d'entraînement.
■ L'arbre de décision est principalement utilisé pour deux types
de tâches la classification et la régression
Arbre de décision

3
Arbre de décision
◼ Exemple : Type de maladie en fonction des symptômes

Classifier l’instance suivante ?

5
<douleur = gorge, Fièvre = non>
Arbre de décision

◼ Un arbre de décision est représenté par une

séquence de conditions.

◼ Rhume = (Douleur = gorge et Fièvre = oui

ou
(Douleur = aucune et
toux = oui et fièvre = oui)

5
Arbre de décision: Apprentissage

◼ Première possibilité: produire un chemin pour

chaque donnée d’entraînement

A1
A1 A2 A3 Sortie
+ + + 1
+ + - 0 A2
+ - - 0

A3 A3

1
0 0

6
Arbre de décision: Apprentissage
❑ Etape1: Sélection de l’attribut de division
▪ Trouver l’attribut qui est le meilleur
discriminant sur l’ensemble d’entraînement

❑ Etape2 : Division des données

▪ Un nœud enfant est créé pour chacune des
valeurs possibles de l’attribut
▪ Les exemples d’entraînement sont ensuite
assignés à leurs nœuds correspondants

❑ Etape 3: Récursivité
• Les étapes 1 et 2 sont répétées pour chaque sous-
ensemble créé à partir de la division précédente.

L'algorithme continue à diviser les données jusqu'à ce

7
qu'un critère d'arrêt soit satifsfait
Comment choisir le
meilleur discriminant?

[39+, 31-‐-] [39+, 31-‐-]

Attr 1 Attr2

[20+, 15-‐-] [19+, 16-‐-] [39+, 0-‐-] [0+, 31-‐-]

Lequel des deux attributs choisir?

8
Élagage

◼ Contrôler la complexité du nombre des branches et des

feuilles pour réaliser un arbre de décision.

◼ Minimiser la taille de l’arbre.

◼ Trouver le nombre optimale de nœuds.
◼ Deux techniques d’élagage
 Pré-élagage.
 Post-élagage

9
Pré-élagage

◼ Arrêter quand il y a une classe majoritaire dans le nœud.

◼ Utiliser un seuil pour détecter une classe dominante.

◼ Inconvénients:
 Arrêter la construction de l’arbre peut donner un arbre sous optimal.

10
Post-élagage

◼ Finir la construction de l’arbre.

◼ Simplifier l’arbre en remontant des feuilles vers la
racine pour trouver ou élaguer.

◼ Utiliser des critères de qualité qui mesure un

compromis l’erreur obtenue et la complexité de
l’arbre.

◼ Utiliser un ensemble de validation pour mesurer

l’erreur à chaque nnœud.

11
L’algorithme CART

• Algorithme de classifcation utilisé à la fois pour la

classification et la régression

• Le principe général est de construire un arbre de décision

binaire en divisant récursivement les données en sous
ensembles de plus en plus petits de manière à minimiser
l’impureté des noeuds
L’algorithme CART – Critère de séparation
Utilise le Critère de séparation : Indice de Gini

Avec n : nombre de classes à prédire

pi : proportion de la classe dans le noeud

Plus l’indice de Gini est bas, plus le noeud est pure 𝒏

𝑰𝑮 = 𝟏 − ෍ 𝒑𝒊𝟐
Exemple : Arbre CART 𝒊=𝟏
- p1 = 1 et p2 = 0 IG = 0 >>> pure
- p1 = 0,5 et p2 = 0,5 IG = 0,5 >>> impureté maximale
- P1 =0,7 et p2 =0,3 IG = 0,42 >>> impureté moyenne

En séparant un noeud en 2 noeuds fils on cherche à minimiser l’impureté

et donc à maximiser la réduction de l’impureté

La variable la plus discriminante doit maximiser la formule du gain:

IG(avant séparation)-[pg*IG(filsg) +pd IG(filsd)]

Les "Pondérations" pg et pd sont les proportions des données qui se

trouvent dans chaque sous-ensemble g et d après la division
L’algorithme CART - Etapes
1- Sélectionner la valeur de division e/ou le seuil qui maximise la réduction
d’impureté

2- Création des noeuds filsg et filsd en fonction de la valeur de division et du

seuil

3- Répétition de manière récursive sur chaque nœud fils jusqu’à critère

d’arrêt

4- Eventuel « élagage de l’arbre »

➢ Critères d’arrêt:

▪ Profondeur maximale de l’arbre

▪ Nombre minimal d’exemples par feuille
▪ Impureté minimale
▪ …
L’algorithme CART- Exemple

Une banque dispose des informations

suivantes sur un ensemble de clients:

M : moyenne des montants sur le

compte client.
A : tranche d'âge du client.
E : valeur oui si le client a un niveau
d'études supérieures.

I : classe oui correspond à un client qui

effectue une consultation de ses
comptes bancaires en utilisant Internet

La racine peut être : M, A, E ????

 L’algorithme CART
- Exemple

Indice de Gini avant séparation au NIVEAU DE LA RACINE :

8 clients
I=oui : 3 clients
I=non : 5 clients

IG(avant séparation) = 1 – ( (3/8)² + (5/8)² ) = 0.46875

Proportion des I = oui
Proportion des I = non

Il faut étudier le Gain pour chaque attribut (M, A et E)et choisir celui
qui maximise la réduction de l’impureté
 L’algorithme CART

Gain de la variable M (Moyenne des montants sur le compte client ):

3 modalités de M (faible, moyen, elevé):

Il faut chercher le split à faire:

1ère possiblité de division: (non élevé, elevé)

2ème possibilté de division:(non moyen, moyen)
3ème possibilté de division: (non faible, faible)

Remarque:
Non élevé = moyen ou faible
Non moyen = faible ou élevé
Non faible = moyen ou élevé
L’algorithme CART

Gain de la variable
M (Moyenne des montants sur le compte client ):
3 modalités de M ( faible, moyen, elevé):

1ère possiblité de division: (non élevé , élevé)

M= Non elevé (Moyen+faible) : 6 clients →(I=oui : 3 clients, I=non : 3 client )

IG_fg =1 – ( (3/6)² + (3/6)² )=0,5

M= Elevé: 2 clients →(I=oui : 0 clients I=non : 2 clients)

IG_fd =1– ( (0/2)² + (2/2)² )=0

Gain= 0.46875 - ((6/8)* IG_fg + (2/8)* IG_fd)=0,09

L’algorithme CART

Gain de la variable M (Moyenne des montants sur le compte client ):

3 modalités de M ( faible, moyen, elevé):

2ème possibilté de division:

(non moyen, moyen)

M= non moyen : 5 clients →(I=oui : 1 clients, I=non : 4 client )

IG_fg =1 – ( (1/5)² + (4/5)² )=0,32

M= moyen: 3 clients →(I=oui : 2 clients I=non : 1 clients)

IG_fd=1– ( (2/3)² + (1/3)² )=0,444

Gain= 0.46875 - ((5/8)* IG_fg + (3/8)* IG_fd)=0,10

L’algorithme CART
Gain de la variable M (Moyenne des montants sur le compte client ):
3 modalités de M ( faible, moyen, elevé):

3ème possibilté de division:

(non faible , faible)

M= non faible: 5 clients →(I=oui : 2 clients, I=non : 3 clients )

IG_fg =1 – ( (2/5)² + (3/5)² )=0,48

M= faible: 3 clients →(I=oui : 1 clients I=non : 2 clients)

IG_fd=1– ( (1/3)² + (2/3)² )=0.444

Gain= 0.46875 - ((5/8)* IG_fg + (2/8)* IG_fd)=0,00225

L’algorithme CART
La variable A (tranche d’âge):
3 modalités de A : (jeune, moyen, agé):

• 1ère possibilité (non âgé, âgé)

A= non âgé: 5 client (I=oui : 3 client , I=non : 2 clients)

IG_fg=1– ( (3/5)² + (2/5)² )=0,48

A= âgé: 3 clients (I=oui : 0 clients , I=non : 3 clients )

IG_fd =1 – ( (0/3)² + (3/3)² )=0

Gain= 0.46875 - ((5/8)* IG_fg + (3/8)* IG_fd )=0,16875

L’algorithme CART
La variable A (tranche d’âge):
3 modalités de A : (jeune, moyen, âgé):

• 2ème possibilité
(non moyen, moyen)

A= non moyen : 4 clients (I=oui : 1 client , I=non : 3 clients)

IG_fg=1– ( (1/4)² + (3/4)² )=0.375

A= Moyen: 4 clients (I=oui : 2 clients , I=non : 2 clients )

IG_fd =1 – ( (2/4)² + (2/4)² )=0,5

Gain= 0.46875 - ((4/8)* IG_fg + (4/8)* IG_fd )=0,03

L’algorithme CART

La variable A (tranche d’âge):

3 modalités de A : (jeune, moyen, agé):

• 3ème possibilité(non jeune, jeune)

A= non jeune: 7 clients (I=oui : 2 client , I=non : 5 clients)

IG_fg=1– ( (2/5)² + (7/5)² )=0.375

A= jeune: 1 clients (I=oui : 1 clients , I=non : 0clients )

IG_fd =0

Gain= 0.46875 - ((7/8)* IG_fg + (1/8)* IG_fd )=0,11175

L’algorithme CART

La variable E :
2 modalités : binaire:

E= Oui : 5 clients (I=oui : 3 clients, I=non : 2 clients )

IG_fg= 1– ( (3/5)² + (2/5)² ) =0,48

E= Non: 3 clients (I=oui : 0 clients, I=non : 3 clients )

IG_fd=1– ( (0/3)² + (3/3)² )=0

Gain= 0.46875 - ((5/8)* IG_f1 + (3/8)* IG_f2 =0,14375

 L’algorithme CART

Synthèse pour le choix de la racine:

• E→ binaire→0,14
• M → (non élevé , élevé) → 0,09
• M → (non moyen , moyen) → 0,10
• M → (non faible , faible) → 0,00225
• A→(non âgé, âgé)→ 0,16875
• A→(non moyen, moyen)→ 0,03
• A→(non faible, faible)→ 0,11175

On choisit alors A (non agé, agé)

L’algorithme CART
La variable A étant notre racine:

A
Non âgé âgé

non
????

M ou E
??

Et nous continuons le travail sur

cette nouvelle portion de data
L’algorithme CART
La variable continue au niveau des features:
L’algorithme CART
La variable continue au niveau des features:

Pour le er cas 167,5

L’algorithme CART
La variable continue au niveau des features:

En cherchant l’indice
de Gini pour chaque
valeur de division,
selon les moyennes
pondérées:
Cas de la régression
Exemple Arbre de régression

moyenne

𝑦=140
ത

𝑦=120
ത 𝑦=190
ത

𝑦=110
ത 𝑦=145
ത 𝑦=180
ത 𝑦=220
ത
Critère de séparation
On considère le coût de chaque nœud après division:

Côut(nœud) = pg* MSE(filsg) +pd MSE (filsd)

pg et pd sont les proportions des données qui se trouvent

dans chaque sous-ensemble g et d après la division

σ𝒏
𝒊=𝟏(𝒚𝒊−𝒚)
𝟐
MSE =
𝒏

Mean Square Error (Erreur quadratique moyenne)

On choisit le nœud qui a un moindre coût et donc qui

minimise l’erreur de prédiction
Exemple Surface
𝑦=160
ത
Surface
72
Prix
180
<= 65 > 65 58 140
𝑦=140
ത 𝑦=170
ത
76 160

Pour le Seuil = 65

Avant division : 𝑦=
ത (180+140+160)/3 = 160
Après division :

<= 65 : 1 exemple et 𝑦ത = 140 (filsg)

> 65 : 2 exemples et 𝑦ത = 170 (filsd)

1 2
Côut (Nœud) = MSE(filsg) + MSE(filsd)
3 3

Gauche: MSE(filsg) = (140 − 140)2 = 0

Gauche: MSE(filsd) = ( (180 − 170)2 + (160 − 170)2 )/2=100

𝟏 𝟐
Côut (Nœud) = 0+ 100= 66,66
L’algorithme CART

Avantages
• Il s'agit d'un algorithme simple et intuitif, facile à
comprendre et à interpréter.

• Il peut traiter des données numériques et catégorielles.

• Il peut traiter les problèmes de classification multi-classes

en utilisant une extension appelée multi-classCART

• Sensible aux données d’apprentissage

Inconvénients
• Il a tendance à surapprendre les données, en particulier si
l'arbre est trop profond.

• Il s'agit d'un algorithme gourmand en mémoire qui peut ne

pas trouver l'arbre optimal.