Cours Machine

Learning: Arbres
de d´ecision
pr´esent´ee par :

E Q UI P E MACHINE LEARNING

Unit´e p´edagogique: G´enie Logiciel et

Math´ematiques

Equipe Machine 1 Novembre 1/

Plan

1 Introductio
n
2 D´efinition et
exemple
3

Algorithme
4 Construction d’arbre de d´
ecision
5

Conclusion

Equipe Machine 2 Novembre 2/

Introductio
n

Equipe Machine 3 Novembre 3/

Introduction

Objectif
Il s’agit de pr´edire le comportement de sportifs (jouer : variable `a pr´edire) en
fonction de donn´ees m´et´eo (variables pr´edictives):
Outlook.
Temperatur
e. Humidity.
Wind

Equipe Machine 3 Novembre 3/

Introductio
n
Segmentez les donn´ees en fonction des feautures pour pr´edire le
r´esultat.

Equipe Machine 4 Novembre 4/

Introductio
n
Segmentez les donn´ees en fonction des feautures pour pr´edire le
r´esultat.

Equipe Machine 4 Novembre 4/

Introductio
n
Segmentez les donn´ees en fonction des feautures pour pr´edire le
r´esultat.

Equipe Machine 4 Novembre 4/

Introduction

Segmentez les donn´ees en fonction des feautures pour pr´edire le

r´esultat.

Les figures qui nous premet de pr´edire jouer ou non sont des arbres de
d´ecision.
Equipe Machine 4 Novembre 4/
Plan

1 Introductio
n
2 D´efinition et
exemple
3

Algorithme
4 Construction d’arbre de d´
ecision
5

Conclusion

Equipe Machine 5 Novembre 5/

Arbres de D
´ecision
Motivatio
nroduire des classifications compr´ehensibles par l’utilisateur (versus les autres
P
m´ethodes)

Equipe Machine 6 Novembre 6/

Arbres de D
´ecision
Motivatio
nroduire des classifications compr´ehensibles par l’utilisateur (versus les autres
P
m´ethodes)

D
´efinitio
Ensemble de r`egles de classification basant leur d´ecision sur des tests associ´es
aux attributs, organis´es de mani`ere arborescente.
n

Equipe Machine 6 Novembre 6/

Arbres de D
´ecision
Motivatio
nroduire des classifications compr´ehensibles par l’utilisateur (versus les autres
P
m´ethodes)

D
´efinitio
Ensemble de r`egles de classification basant leur d´ecision sur des tests associ´es
aux attributs, organis´es de mani`ere arborescente.
n
Object
if
L’objectif est de cr´eer un mod`ele qui pr´edit les valeurs de la variable cible, en se
basant sur un ensemble de s´equences de r`egles de d´ecision d´eduites `a partir des
donn´ees d’apprentissage.

Equipe Machine 6 Novembre 6/

Arbres de D
´ecision
Motivatio
nroduire des classifications compr´ehensibles par l’utilisateur (versus les autres
P
m´ethodes)

D
´efinitio
Ensemble de r`egles de classification basant leur d´ecision sur des tests associ´es
aux attributs, organis´es de mani`ere arborescente.
n
Object
if
L’objectif est de cr´eer un mod`ele qui pr´edit les valeurs de la variable cible, en se
basant sur un ensemble de s´equences de r`egles de d´ecision d´eduites `a partir des
donn´ees d’apprentissage.

Remarqu
e
Un arbre de d´ecision (decision tree) est une structure tr`es utilis´ee en Machine
learning. Son fonctionnement repose sur des heuristiques construites selon des
techniques d’apprentissage supervis´ees.

Equipe Machine 6 Novembre 6/

Arbre de D
´ecision
Les arbres de d´ecision ont une structure hi´erarchique.
Les arbres de d´ecision sont compos´es de noeuds et de feuilles reli´es par
des branches. Dans leur repr´esentation graphique, la racine est plac´ee en
haut et les feuilles en bas. Les noeuds internes sont appel´es des noeuds de
d´ecision.
Les noeuds internes peuvent contenir une ou plusieurs r`egles (aussi appel
´ees tests ou
conditions).

Equipe Machine 7 Novembre 7/

G´en´eralit´es sur les arbres
de d´ecision

Les valeurs que peut prendre une variable dans un arbre

de d´ecision sont appel´ees instances ou attributs.
Les noeuds terminaux contiennent la classe aussi appel
´ee classe `a pr´edire ou variable cible.
Apr`es sa construction, un arbre de d´ecision peut ˆetre
traduit sous la forme d’un ensemble de r`egles de d
´ecision.
Lorsque la classe `a pr´edire est une variable qualitative,
nous avons un arbre de classification.
Si la classe `a pr´edire est une variable quantitative,
nous avons un arbre de r´egression.

Equipe Machine 8 Novembre 8/

Exemple
Arbre de d´ecision
D´ecider si une institution bancaire peut accorder ou non un prˆet `a un
demandeur de prˆet.

Equipe Machine 9 Novembre 9/

Exemple
Arbre de d´ecision
D´ecider si une institution bancaire peut accorder ou non un prˆet `a un demandeur de
prˆet.

La d´ecision de la variable cible Prˆet se base sur les variables moyenne du

salaire (MoySal), ˆage (ˆage) et possession d’autres comptes (Autres
comptes).
Les attributs des feuilles de l’arbre: Prˆet, sont des valeurs bool´eennes qui
correspondent `a
une classification dans l’ensemble {Oui, Non}.

Equipe Machine 9 Novembre 9/

Exemple
Arbre de d´ecision
D´ecider si une institution bancaire peut accorder ou non un prˆet `a un demandeur de
prˆet.

La d´ecision de la variable cible Prˆet se base sur les variables moyenne du

salaire (MoySal), ˆage (ˆage) et possession d’autres comptes (Autres
comptes).
Les attributs des feuilles de l’arbre: Prˆet, sont des valeurs bool´eennes qui
correspondent `a
une classification dans l’ensemble {Oui, Non}.

Equipe Machine 9 Novembre 9/

Exemple

Cet arbre de d´ecision engendre les r`egles de d

´ecisions suivantes: Si MoySal > 50000$ alors
Prˆet = Oui.

Si MoySal < 50000$ et Aˆ ge < 25 alors Prˆet =

Non.

Si MoySal < 50000$ et Aˆ ge > 25 et AutresComptes

= Oui alors
Prˆet = Oui.
Si MoySal < 50000$ et Aˆ ge > 25 et AutresComptes
= Non alors
Prˆet = Non.

Equipe Machine 10 Novembre 10 /

Exemple

Cet arbre de d´ecision engendre les r`egles de d

´ecisions suivantes: Si MoySal > 50000$ alors
Prˆet = Oui.

Si MoySal < 50000$ et Aˆ ge < 25 alors Prˆet =

Non.

Si MoySal < 50000$ et Aˆ ge > 25 et AutresComptes

= Oui alors
Prˆet = Oui.
Si MoySal < 50000$ et Aˆ ge > 25 et AutresComptes
= Non alors
Prˆet = Non.

L’institution
Equipe Machine est en mesure de d´ecider
10 facilement si elle
Novembre 10 /
Plan

1 Introductio
n
2 D´efinition et
exemple
3

Algorithme
4 Construction d’arbre de d´
ecision
5

Conclusion

Equipe Machine 11 Novembre 11 /

Algorithmes de construction d’arbres de d
´ecision.
D´ebut
Algorithme
Input :
E : ensemble
d’´echantillons L :
ensemble d’attributs.
Output:
un arbre de d
1 Si tous les exemples sont de la mˆeme classe
´ecision Faire :
Alors cr´eer et retourner une feuille ´etiquet´ee par cette
2 classe.
Sinon
1 R´ep´eter
1 Trouver le meilleur attribut dans l’ensemble L : A
2 R´epartir les exemples de E en n sous-ensembles, selon la
valeur de cet attribut.
3 Allouer un noeud ´etiquet´e par A
4 Refaire le mˆeme processus pour toutes les valeurs de A et
faire de ces noeuds
2 les fils du
5Jusqu’`a noeud ´etiquet´e par A
indice
d’arrˆet.
Fin Algorithme
Equipe Machine 12 Novembre 12 /
Algorithme pour construire les arbres de
d´ecision

Il existe plusieurs algorithmes automatiques pour construire

les arbres de d´ecision:
ID3 (Iterative Dichotomiser 3): d´evelop´e en
1986 par Ross Quinlan.
Il peut ˆetre appliqu´e seulement sur les caract
´eristiques nominales. Il est utilis´e pour le classement.
C4.5: une extension de ID3 par Ross Quinlan.
Il peut ˆetre appliqu´e sur tous les types de
caract´eristiques. Il est utilis´e pour le
classement.
C5.0: une extension commerciale de C4.5,
toujours par Ross Quinlan.
CART (Classification and Regression Trees)

Equipe Machine 13 Novembre 13 /

Algorithme
CART
Parmi les plus performants et plus r´epandus
(Scikit-learn) Accepte tout type de variables
Utilise le Crit`ere de s´eparation : Indice de Gini
L’algorithme r´ecursif CART (Classification And Regression
Trees) permet la construction d’un arbre de d´ecision par
la maximisation de l’indice de Gini.
Cet algorithme g´en`ere des arbres de d´ecision binaires.

Equipe Machine 14 Novembre 14 /

Indice de
Gini
L’indice de Gini a ´et´e introduit par Breiman en 2001.
Cet indice mesure l’impuret´e, qui est un concept tr`es
utile dans la construction des arbres de d´ecision.
La qualit´e d’un noeud et son pouvoir discriminant
peuvent ˆetre
´evalu´es par son impuret´e.
L’indice Gini est donn´e par la relation
Σ |Tj | suivante:
GINI(T ) = 1 − m ( )2
|T
j=1
|
avec T ensemble de donn´ee, m nombre de classes et |Tj |
d´esigne le cardinal de la classe j.
Si l’ensemble de donn´ees T est partitionn´e en deux
partitions
(T1, T2), alors le gain de gini|Test:
1| |T2
Gain de Gini(X, T ) = GINI(T1 ) + GINI(T2 )
||T |T
Equipe Machine
| 15 | Novembre 15 /
Plan

1 Introductio
n
2 D´efinition et
exemple
3

Algorithme
4 Construction d’arbre de d´
ecision
5

Conclusion

Equipe Machine 16 Novembre 16 /

Construction d’arbre de d´ecision:
Exemple banque

Equipe Machine 17 Novembre 17 /

Construction d’arbre de d´ecision:
Exemple banque

M: moyenne des montants sur le compte client.

A: tranche d’ age du client.
R: localité du résidence du client.
E: valeur oui si le client a un niveau d’ études
supérieures.
I: classe oui corrspond à un client qui
effectue une consultation de ses comptes
Equipe Machine 17 Novembre 17 /
Construction d’arbre de d´ecision:
Exemple banque
Indice de Gini
avant s´eparation
(IG(as)): 8 clients:
I = oui: 3
client.
I = non: 5
I G ( a sclient.
) = 1 − ( (83 )2 + ( 5 ) 2 )
IG(as)=0.468 8
78 3
: Fr´equence
8
Ide
= oui
5
8 Fr´equence
Ide=
non

M: moyenne des montants sur le compte client.

A: tranche d’ˆage du client.
R: localit´e du r´esidence du client.
E: valeur oui si le client a un niveau d’´etudes sup
´erieures.
I: classe oui corrspond à un client qui
effectue une consultation de ses comptes
Equipe Machine 17 Novembre 17 /
Indice de
GINI
L’indice de GINI de la variable M: moyenne des montants sur le
compte client.

Equipe Machine 18 Novembre 18 /

Indice de
GINI
L’indice de GINI de la variable A: tranche d’ˆage du
client.

Equipe Machine 19 Novembre 19 /

Indice de
GINI
L’indice de GINI de la variable R: localit´e du r´esidence
du client.

Equipe Machine 20 Novembre 20 /

Indice de
GINI
L’indice de GINI de la variable E: valeur oui si le client a un niveau d’´etudes
sup´erieures.

Equipe Machine 21 Novembre 21 /

Indice de
GINI
Indice de GINI de
M I G ( a s ) − (IG(M=facile) + IG(M=Moyene) + IG(M=Elev
´e))
= 0.46875 − (0.44444 + 0.44444 + 0)
I G ( M ) = −0.4201388

Equipe Machine 22 Novembre 22 /

Indice de
GINI
Indice de GINI de
M I G ( a s ) − (IG(M=facile) + IG(M=Moyene) + IG(M=Elev
´e))
= 0.46875 − (0.44444 + 0.44444 + 0)
I G ( M ) = −0.4201388

Indice de GINI de
R IG(as) − (IG(R=Village) + IG(R=Bourg ) +
IG(R=Ville))
= 0.46875 − (0.44444 + 0.5 + 0.4444444)
I G ( R ) = −0.9201388

Equipe Machine 22 Novembre 22 /

Indice de
GINI
Indice de GINI de
M I G ( a s ) − (IG(M=facile) + IG(M=Moyene) + IG(M=Elev
´e))
= 0.46875 − (0.44444 + 0.44444 + 0)
I G ( M ) = −0.4201388

Indice de GINI de
R IG(as) − (IG(R=Village) + IG(R=Bourg ) +
IG(R=Ville))
= 0.46875 − (0.44444 + 0.5 + 0.4444444)
I G ( R ) = −0.9201388

Indice de GINI de
A IG(as) − (IG(A=jeune) + IG(A=Moyen) + IG(A=Ag
´e))
= 0.46875 − (0 + 0.5 + 0)
I G ( A ) = −0.03125

Equipe Machine 22 Novembre 22 /

Indice de
GINI
Indice de GINI de
M I G ( a s ) − (IG(M=facile) + IG(M=Moyene) + IG(M=Elev
´e))
= 0.46875 − (0.44444 + 0.44444 + 0)
I G ( M ) = −0.4201388

Indice de GINI de
R IG(as) − (IG(R=Village) + IG(R=Bourg ) +
IG(R=Ville))
= 0.46875 − (0.44444 + 0.5 + 0.4444444)
I G ( R ) = −0.9201388

Indice de GINI de
A IG(as) − (IG(A=jeune) + IG(A=Moyen) + IG(A=Ag
´e))
= 0.46875 − (0 + 0.5 + 0)
I G ( A ) = −0.03125

Indice de GINI de
E I G ( a s ) − (I G (E= O ui ) +
IG(E=Non))
= 0.46875 − (0.48 + 0)
Equipe Machine
I G ( E ) = −0.01125388
22 Novembre 22 /
PREMIER RESULTAT DE L’INDICE DE
GINI
La variable la plus s´eparatrice est celle qui
maximise:

IG(as) − (IG(fils1) + IG(fils2) + ...... + IG(filsn))

⇓
E

Equipe Machine 23 Novembre 23 /

PREMIER RESULTAT DE L’INDICE DE
GINI
La variable la plus s´eparatrice est celle qui
maximise:

IG(as) − (IG(fils1) + IG(fils2) + ...... + IG(filsn))

⇓
E

Equipe Machine 23 Novembre 23 /

Construction d’arbre de d´ecision:
Exemple banque

M: moyenne des montants sur le compte client.

A: tranche d’ age du client.
R: localité du résidence du client.
E: valeur oui si le client a un niveau d’ études
supérieures.
I: classe oui corrspond à un client qui
effectue une consultation de ses comptes
Equipe Machine 17 Novembre 17 /
CALCUL DE L’INDICE DE GINI :
E=OUI

Indice de Gini avant s´eparation avec E

= Oui :
Indice de Gini avant s´eparation
(IG(as 1 )): 5 clients:
I = oui: 3 client.
I = non: 2 client.
I G ( a s 1 ) = 1 − ( (53 )2 + ( 2 ) 2 ) = 0.48
5

3
5: Fr´equence de I = oui lorsque E =
oui
2
5 Fr´equence de I = non lorsque E =
oui

Equipe Machine 24 Novembre 24 /

Indice de
GINI
Indice de Gini de la variable M (Moyenne des montants sur
le compte client ) avec E=Oui :

Equipe Machine 25 Novembre 25 /

Indice de
GINI
Indice de GINI de fils M = faible & E = oui: 1
client.
I = oui: 1 client.
I = non: 0 client.
I G ( M = faible&E = oui) = 1 − (1( 1 )2 + ( 0 ) 2 ) =
0 1

Equipe Machine 26 Novembre 26 /

Indice de
GINI
Indice de GINI de fils M = faible & E = oui: 1
client.
I = oui: 1 client.
I = non: 0 client.
I G ( M = faible&E = oui) = 1 − (1( 1 )2 + ( 0 ) 2 ) =
0 1

Indice de GINI de fils M = Moyen & E = oui: 3

client.
I = oui: 2 clients.
I = non: 1 client.
I G ( M = Moyen&E = oui) = 1 − (3( 2 )2 + ( 1 ) 2 ) =
0.4444444 3

Equipe Machine 26 Novembre 26 /

Indice de
GINI
Indice de GINI de fils M = faible & E = oui: 1
client.
I = oui: 1 client.
I = non: 0 client.
I G ( M = faible&E = oui) = 1 − (1( 1 )2 + ( 0 ) 2 ) =
0 1

Indice de GINI de fils M = Moyen & E = oui: 3

client.
I = oui: 2 clients.
I = non: 1 client.
I G ( M = Moyen&E = oui) = 1 − (3( 2 )2 + ( 1 ) 2 ) =
0.4444444 3

Indice de GINI de fils M = Elev´e & E = oui: 1

client.
I = oui: 0 client.
I = non: 1 client.
I G ( M = Elev´e&E = oui) = 1 − (1( 0 )2 + ( 1 ) 2 ) =
0 Equipe Machine 1
26 Novembre 26 /
Indice de GINI de M avec E =
oui

Indice de GINI de M avec E = oui

IG(as1) − (IG(M=facile) + IG(M=Moyene) + I G(M=Elev
´e))
= 0.48 − (0 + 0.44444 + 0)
IG(M &E = oui) = 0.0355556

Equipe Machine 27 Novembre 27 /

Indice de
GINI
Indice de Gini de la variable A (Tranche d’ˆage du client) avec
E = Oui :

Equipe Machine 28 Novembre 28 /

Indice de
GINI
Indice de GINI de fils A = jeune & E = oui: 1
client.
I = oui: 1 client.
I = non: 0 client.
I G ( A = Jeune&E = oui) = 1 − ( (1 1 )2 + ( 0 ) 2 ) =
0 1

Equipe Machine 29 Novembre 29 /

Indice de
GINI
Indice de GINI de fils A = jeune & E = oui: 1
client.
I = oui: 1 client.
I = non: 0 client.
I G ( A = Jeune&E = oui) = 1 − ( (1 1 )2 + ( 0 ) 2 ) =
0 1

Indice de GINI de fils A = jeune & E = oui: 2

client.
I = oui: 2 clients.
I = non: 0 client.
I G ( A = jeune&E = oui) = 1 − ( 2( 2 )2 + ( 0 ) 2 ) =
0 2

Equipe Machine 29 Novembre 29 /

Indice de
GINI
Indice de GINI de fils A = jeune & E = oui: 1
client.
I = oui: 1 client.
I = non: 0 client.
I G ( A = Jeune&E = oui) = 1 − ( (1 1 )2 + ( 0 ) 2 ) =
0 1

Indice de GINI de fils A = jeune & E = oui: 2

client.
I = oui: 2 clients.
I = non: 0 client.
I G ( A = jeune&E = oui) = 1 − ( 2( 2 )2 + ( 0 ) 2 ) =
0 2

Indice de GINI de fils M = Ag´e & E = oui: 2

client.
I = oui: 0 client.
I = non: 2 clients.
I G ( M = Ag´e&E = oui) = 1 − (2( 0 )2 + ( 2 ) 2 ) =
0 Equipe Machine 2
29 Novembre 29 /
Indice de GINI de A avec E =
oui

Indice de GINI de A avec E = oui

IG(as1) − (IG(A=jeune) + IG(A=Moyen) + I G(A=Ag
´e))
= 0.48 − (0 + 0 + 0)
IG(A&E = oui) = 0.48

Equipe Machine 30 Novembre 30 /

Indice de
GINI
Indice de Gini de la variable R (Localit´e de r´esidence du
client) avec
E = Oui :

Equipe Machine 31 Novembre 31 /

Indice de
GINI
Indice de GINI de fils R = Village & E = oui: 1
client.
I = oui: 1 client.
I = non: 0 client.
I G ( R = Village&E = oui) = 1 − (1( 1 )2 + ( 0 ) 2 ) =
0 1

Equipe Machine 32 Novembre 32 /

Indice de
GINI
Indice de GINI de fils R = Village & E = oui: 1
client.
I = oui: 1 client.
I = non: 0 client.
I G ( R = Village&E = oui) = 1 − (1( 1 )2 + ( 0 ) 2 ) =
0 1

Indice de GINI de fils R = Bourg & E = oui: 1

client.
I = oui: 1 client.
I = non: 0 client.
I G ( A R B o u r g & E = oui) = 1 − (1( 1 )2 + ( 0 ) 2 ) =
0 2

Equipe Machine 32 Novembre 32 /

Indice de
GINI
Indice de GINI de fils R = Village & E = oui: 1
client.
I = oui: 1 client.
I = non: 0 client.
I G ( R = Village&E = oui) = 1 − (1( 1 )2 + ( 0 ) 2 ) =
0 1

Indice de GINI de fils R = Bourg & E = oui: 1

client.
I = oui: 1 client.
I = non: 0 client.
I G ( A R B o u r g & E = oui) = 1 − (1( 1 )2 + ( 0 ) 2 ) =
0 2

Indice de GINI de fils R = Ville & E = oui: 3

client.
I = oui: 1 client.
I = non: 2 clients.
I G ( M = Ag´e&E = oui) = 1 − (3( 1 )2 + ( 2 ) 2 ) = 0.4444444
3
Equipe Machine 32 Novembre 32 /
Indice de GINI de R avec E =
oui

Indice de GINI de R avec E = oui

IG(as1) − (IG(R=Village) + IG(R=Bourg) + IG(R=Ville))
= 0.48 − (0 + 0 + 0.444444)
IG(R&E = oui) = 0.0355556

Equipe Machine 33 Novembre 33 /

Construction d’arbre de d´ecision:
Exemple banque

M: moyenne des montants sur le compte client.

A: tranche d’ age du client.
R: localité du résidence du client.
E: valeur oui si le client a un niveau d’ études
supérieures.
I: classe oui corrspond à un client qui
effectue une consultation de ses comptes
Equipe Machine 17 Novembre 17 /
Arbre de d
´ecision

Equipe Machine 34 Novembre 34 /

Plan

1 Introductio
n
2 D´efinition et
exemple
3

Algorithme
4 Construction d’arbre de d´
ecision
5

Conclusion

Equipe Machine 35 Novembre 35 /

Avantages et Inconv
´enients
Avantages
Simples `a comprendre et `a interpr´eter.
Ils peuvent travailler sur des donn´ees avec peu de
pr´eparation. Ils acceptent les donn´ees num
´eriques et nominales.
Ils donnent de bonne performance mˆeme si leurs
hypoth`eses sont un peu viol´ees par le mod`ele r´eel `a
partir duquel les donn´ees ont ´et´e g´en´er´ees.

Equipe Machine 36 Novembre 36 /

Avantages et Inconv
´enients
Avantages
Simples `a comprendre et `a interpr´eter.
Ils peuvent travailler sur des donn´ees avec peu de
pr´eparation. Ils acceptent les donn´ees num
´eriques et nominales.
Ils donnent de bonne performance mˆeme si leurs
hypoth`eses sont un peu viol´ees par le mod`ele r´eel `a
partir duquel les donn´ees ont ´et´e g´en´er´ees.

Inconv´enients
Ils peuvent ˆetre aussi complexes, ils ne g´en
´eralisent pas bien (overfitting: surapprentissage).
Ils peuvent ˆetre instable `a cause des variations
des donn´ees. Ils peuvent ˆetre biais´es `a la
classe dominante.
Equipe Machine 36 Novembre 36 /
 MERCI POUR VOTRE
ATTENTION

Equipe Machine 37 Novembre 37 /