Machine Learning

Chapitre 7: Arbres de Décision

(Decision Tree)

Ouissem Ben Fredj

[email protected]
Introduction
 Algorithmes de classification
1. Introduit au début des années 60 par Morgan & Sonquist
2. Les DT peuvent être utilisés à la fois pour la
classification et la régression
3. Facile à comprendre et à interpréter

Algorithmes typiques :
• Arbres de décision
• Induction basée sur des règles
• Les réseaux de neurones
• K-Voisin le plus proche
• Forêts aléatoires
• Réseaux bayésiens
• SVM
3
 Classification
 Ensemble de données : (a) Ensemble d'apprentissage , (b)
Ensemble de validation , (c) Ensemble de test
 Étant donné l’ensemble d’entrainement
o Utiliser l'ensemble d'entraînement pour créer le modèle
• Trouver un modèle pour le label en fonction des valeurs des
attributs
 Utilisez l'ensemble de validation pour :
o Ajuster (optimiser) les paramètres du modèle
o Évaluer la qualité des prédictions du modèle
 Utiliser un ensemble de Test pour estimer l’exactitude du
modèle
o Objectifs :
• Les enregistrements non vues doivent se voir attribuer une classe
aussi précisément que possible
• Le modèle doit pouvoir généraliser
• Déployer le modèle

4
Terminologie
 Arbres de décision
• Un arbre de décision est une structure arborescente de type
organigramme où un nœud interne représente une attribut, la
branche représente une règle de décision et chaque nœud feuille
représente le résultat.
• Cette structure de type organigramme vous aide dans la prise de
décision.
• C'est une visualisation comme un organigramme qui imite
facilement la pensée au niveau humain .
• C'est pourquoi les arbres de décision sont faciles à comprendre et
à interpréter .

6
 nœud racine
• Le nœud le plus élevé d'un arbre de décision est appelé
nœud racine .
• Il apprend à partitionner sur la base de la valeur de
l'attribut.
• Différentes structures arborescentes seront formées si
différentes "fonctions" sont utilisées pour diviser
l'arborescence à la racine.

7
 Nœuds internes et feuilles
Ceux-ci sont appelés nœuds internes ou nœuds de décision

Ceux-ci sont appelés nœuds feuilles ou nœuds terminaux

8
Day
Exemple de DT
Outlook Temperature Humidity Wind Play Tennis
1 Sunny Hot High Weak No
2 Sunny Hot High Strong No
3 Overcast Hot High Weak Yes
4 Rain Mild High Weak Yes
5 Rain Cool Normal Weak Yes
6 Rain Cool Normal Strong No
7 Overcast Cool Normal Strong Yes
8 Sunny Mild High Weak No
9 Sunny Cool Normal Weak Yes
10 Rain Mild Normal Weak Yes
11 Sunny Mild Normal Strong Yes
12 Overcast Mild High Strong Yes
13 Overcast Hot Normal Weak Yes
14 Rain Mild High Strong No

Outlook
Label
Sunny Overcast Rain

Humidity Yes Wind

High Normal Strong Weak

No Yes No Yes

9
Construire des arbres
 Données météo : jouer ou non?
Label
4 attributs
ID code Outlook Temperature Humidity Windy Play
a Sunny Hot High False No
b Sunny Hot High True No
14 enregsitrements  Training Data

c Overcast Hot High False Yes

d Rainy Mild High False Yes
e Rainy Cool Normal False Yes
f Rainy Cool Normal True No
g Overcast Cool Normal True Yes Arbre de
Decision
h Sunny Mild High False No ?
i Sunny Cool Normal False Yes
Attribut
j Rainy Mild Normal False Yes
à la
k Sunny Mild Normal True Yes racine?
l Overcast Mild High True Yes
m Overcast Hot Normal False Yes
n Rainy Mild High True No 11
Nœuds internes et nœuds feuilles

Outlook

Sunny Overcast Rain

Humidity Chaque nœud interne teste un attribut

High Normal Chaque branche correspond à un

nœud de valeur d'attribut
No Yes nœud feuille: une classification

12
 Construire l'arbre
L'idée de tout algorithme d'arbre de décision est la suivante:
1. Divisez les données en enregistrements d’entrainement et de test.
2. Démarrer la construction de l'arborescence (sélectionner un attribut au niveau
d'un nœud racine et d'un nœud de décision)
3. Évaluer l'arbre en utilisant les mesures de performance (ASM: Attribute Selection
Measure)
4. Choisissez le meilleur arbre qui résout le problème.
Construire l'arbre : apprendre

13
Un arbre à partir de données
ID code Outlook Temperature Humidity Windy Play
a Sunny Hot High False No
b Sunny Hot High True No
c Overcast Hot High False Yes
d Rainy Mild High False Yes
e Rainy Cool Normal False Yes
f Rainy Cool Normal True No
g Overcast Cool Normal True Yes
h Sunny Mild High False No
i Sunny Cool Normal False Yes
j Rainy Mild Normal False Yes
k Sunny Mild Normal True Yes
l Overcast Mild High True Yes
m Overcast Hot Normal False Yes
n Rainy Mild High True No

14
 DT : Algorithme
1. Commencez avec un ensemble de données d'entraînement appellé S. Il doit avoir
des attributs et un label.
2. Déterminer le meilleur attribut dans l'ensemble de données.
3. Divisez S en sous-ensemble qui contient les valeurs possibles pour le meilleur
attribut.
4. Créer un nœud d'arbre de décision contenant le meilleur attribut.
5. Générez de manière récursive de nouveaux arbres de décision en utilisant le
sous-ensemble de données créé à partir de l'étape 3 jusqu'à ce qu'une étape soit
atteinte où vous ne pouvez plus classer les données. Représentez la classe en
tant que nœud feuille.
ID code Outlook Temperature Humidity Windy Play
a Sunny Hot High False No
b Sunny Hot High True No
c Overcast Hot High False Yes
d Rainy Mild High False Yes
e Rainy Cool Normal False Yes
f Rainy Cool Normal True No
g Overcast Cool Normal True Yes
h Sunny Mild High False No
i Sunny Cool Normal False Yes
j Rainy Mild Normal False Yes
k Sunny Mild Normal True Yes
l Overcast Mild High True Yes
m Overcast Hot Normal False Yes
n Rainy Mild High True No

16
Limites de decision
Exemple : données (demande de prêt)
Approuver :
Oui/Non

20
 Demande de prêt : la tâche
d'apprentissage
 Apprendre un modèle de classification à partir des
données
 Utiliser le modèle pour classer les futures demandes
de prêt en
o Oui (approuvé) et
o Non (non approuvé)
 Quelle est la classe pour le cas/instance suivant ?

21
Un arbre de décision : exemple de
données sur les prêts
 décision et nœuds feuilles (classes)

22
Un arbre de décision : exemple de
données sur les prêts

Non

23
Est-ce le seul arbre que nous pouvons créer ?
 L'arbre de décision est-il unique ?

 Non . Voici un arbre plus simple.

 Nous voulons des arbres plus petits et
précis.
o Facile à comprendre et plus efficace

 Trouver le meilleur
arbre est NP-difficile.
 Tous les algorithmes de
construction d'arbres
actuels sont des
algorithmes
heuristiques 24
Mesure de sélection d'attribut -
Attribute Selection Measure
(ASM)
Construire l'arbre (ASM)
 L’ASM est une heuristique permettant de sélectionner le critère
de division qui partitionne les données de la meilleure manière.
 L' idée de base derrière tout algorithme d'arbre de décision
est la suivante :
1. Sélectionnez le meilleur attribut à l'aide des mesures de
sélection d'attributs (ASM) pour diviser les enregistrements.
2. Répéter récursivement le processus pour chaque enfant

26
Exemple: Sélection d’attributs
• Supposons que votre objectif
soit de prédire si un utilisateur Label 5 attributs
inconnu appréciera un cours
inconnu.
• À droite se trouve un dataset
d'évaluation de cours.

aimer
• 20 exemples: des évaluations
de cours et des réponses aux
questions que vous pourriez
poser.

Quelle est l'utilité de chaque attribut dans la

construction d’un arbre qui peut nous aider à Détester
deviner si un étudiant appréciera
ce cours ou le détester?
Comment construire l'Arbre ?
Quel attribut devrions-nous considérer en premier
pour diviser l'arbre ? 27
 Exemple: Sélection d’attributs
• Construire un histogramme de
labels pour :
o L'ensemble des données
o L’attribut Easy
o L’attribut IA
o L’attribut System
o L’attribut theory
o L’attribut Morning
 L'ensemble des données :
 Nombre total d'enregistrements = 20
o Enregistrements "J'aime" = 12/20
o enregistrements "Je deteste"= 8/20
o % "J'aime"  60%
o % "Je deteste"  40 %

28
Exemple: Sélection d’attributs

12 j'aime
Utile

8 je deteste

Vous voulez trouver un attribut qui est la plus utile

pour vous aider à deviner si cet étudiant appréciera
ce cours
29
 Mesure de sélection d'attribut
 L’ASM (attribute selection measure) fournit un classement à
chaque attribut
 Le score du meilleur attribut sera sélectionné comme attribut
de fractionnement (Source).
 Dans le cas d'un attribut à valeur continue, des points de
partage pour les branches doivent également être définis.
 mesures de sélection les plus populaires sont
1. Entropy
2. Information Gain,
3. Gain Ratio,
4. Reduction de Variance
5. Chi-Square
6. Gini Index,

30
 ASM "Entropy"
• L'entropie est une mesure du caractère aléatoire dans les
informations traitées.
• Plus l'entropie est élevée , plus il est difficile de tirer des
conclusions à partir de cette information.
• Lancer une pièce est un exemple d'action qui fournit des
informations aléatoires.

• D'après le graphique, il est tout à fait

évident que l' entropie H(X) est nulle
lorsque la probabilité est de 0 ou de 1.
• L'entropie est maximale lorsque la
probabilité est de 0,5 car elle projette un
caractère aléatoire parfait dans les
données et il n'y a aucune chance si le
résultat est parfaitement déterminé.
Plus la valeur est basse, mieux c'est !!
31
 "Entropy": un attribut
• L'entropie aide à trouver la pureté d'un attribut. Souvent considérée
comme une mesure de "désordre"
• Meilleure distinction des classes (plus de oui ou non dans une
branche)
• plus l'entropie est élevée, plus le désordre est élevé
• Mathématiquement, l'entropie pour un seul attribut est représentée
𝑐
par :
𝐸𝑛𝑡𝑟𝑜𝑝𝑦: 𝐸 𝑇 = ෍ −𝑃𝑖 𝑙𝑜𝑔2 (𝑃𝑖 )
• T: État actuel 𝑖=1

• C: Nombre de classes
• pi: Probabilité de sélectionner au hasard un
exemple dans la classe i
Exemple: Supposons un ensemble R = { a,a,a,b,b,b,b,b }
Entropie = -[ (3/8) Log 2 (3/8) + (5/8)Log 2 (5/8) ]
32
 "Entropy": un attribut
14 enregistrements
au total

P(PlayGolf=Yes) = 9/14 = 0,64

P(PlayGolf=No) = 5/14 = 0,36
E(playGolf)=E(5,9)=-(5/14)*log(5/14)-(9/14)*log(9/14) = 0.94
• L'entropie la plus élevée est lorsque Classe + et Classe - sont égaux
• En statistique, l' entropie est une mesure du nombre de façons dont un système
peut être arrangé
33
 "Entropie": attributs multiple
• Mathématiquement, l'entropie pour plusieurs attributs est
calculée par :
T: État actuel
𝐸 𝑇, 𝑋 = ෍ 𝑃 𝑐 𝐸(𝑐) X: Attribut sélectionné
𝑐∈𝑋
classes
Si l'entropie calculée
Outlook yes no total
est 0 .. Alors nous
sunny 2 3 5
pouvons arrêter de overcast 4 0 4
diviser et nous avons rainy 3 2 5
atteint une FEUILLE TOTAL 9 5 14

E(playGolf,Outlook) = P(sunny)*E(sunny)+P(overcast)*E(overcasty)+ P(rainy)*E(rainy)

= (5/14)*E(2,3)+(4/14)*E(4,0)+(5/14)*E(3,2)
= (5/14)*(-2/5*log(2/5)-3/5*log(3/5))
+(4/14)*(-4/4*log(4/4)-0/4*log(0/4))
+(5/14)*(-3/5*log(3/5)-2/5*log(2/5)) = 0.346+0+0.346=0.693
 Information Gain
• "Information gain" ou IG est une propriété statistique qui
mesure à quel point un attribut donné sépare les exemples
d'apprentissage en fonction de leur classification cible.
• Construire un arbre de décision consiste à trouver un attribut
qui renvoie le gain d'information le plus élevé et la plus petite
entropie.

nous avons besoin

de plus
d'informations ici
pour prendre une
décision

Pos = 5/10 Nég = 5/10 Pos = 8/10 Nég = 8/10

35
 Information Gain
• "Information gain" est une diminution de l'entropie. Il calcule
la différence entre l'entropie avant division et l'entropie
moyenne après division de l'ensemble de données en
fonction de valeurs d'attribut donné.
• L' algorithme d'arbre de décision ID3 utilise le gain
d'informations.

𝐼𝑛𝑓𝑜𝑟𝑚𝑎𝑡𝑖𝑜𝑛 𝐺𝑎𝑖𝑛: 𝐼𝐺 𝑇, 𝑋 = 𝐸 𝑇 − 𝐸(𝑇, 𝑋)

Entropie(T) Entropie(T,X)

36

IG(playGolf, Outlook) = E(playGolf) - E(playGolf, Outlook)

= 0.940 - 0.693 = 0.247
 Algorithme ID3
ID3 (Exemples, Target_Attribute, Attributs)
1. Créer un nœud racine pour l'arborescence
2. Si tous les exemples sont positifs
Renvoyez la racine de l'arbre à nœud unique, avec le label = +
3. Si tous les exemples sont négatifs
Renvoyez la racine de l'arbre à nœud unique, avec le label = -
4. Si le nombre d'attributs prédictifs est vide,
Renvoyez la racine de l'arbre à nœud unique, avec label =
valeur la plus courante de l'attribut cible dans les exemples
5. Sinon
…….. Diapositive suivant……….
Fin Si
Renvoyez (nœud racine)
5.1 A ← L'attribut qui classe le mieux les exemples (l’attribut avec le
IG maximal)
5.2 Attribut Arbre de décision pour Racine = A.
5.3 Pour chaque valeur possible, vi, de A,
5.3.1 Ajoutez une nouvelle branche d'arbre sous Racine,
correspondant au test A = vi
5.3.2 Soit Exemples(vi) le sous-ensemble d'exemples qui ont
la valeur vi pour A
5.3.3 Si Exemples(vi) est vide
sous cette nouvelle branche, ajoutez un nœud feuille
avec label = valeur cible la plus courante dans les
exemples
5.3.4 Sinon
sous cette nouvelle branche, ajoutez le sous-arbre
ID3 (Exemples (vi), Target_Attribute, Attributes - {A})
Fin SI
Fin Pour
 Outlook

sunny rainy
overcast
Humidity yes wind

high normal false true

No Yes
Yes No
 ID3: avantages et inconvénients
• Avantages
• Règles de prédiction compréhensibles.
• Temps relativement court pour construire l'arbre.
• L'arbre peut être réduit si toutes les données pointent vers
une seule classe.
• Ne nécessite pas tous les attributs dans certains cas
• Inconvénients
• Provoque un overfitting (variance élevée)
• Utilise un algorithme gourmand, il se peut donc qu'il ne
produise pas toujours un arbre optimal.
 Gain Ratio
• Information Gain (IG) (gain d'information ) préfère l'attribut avec
un grand nombre de valeurs distinctes.
• C4.5 , une amélioration de ID3, utilise le Gain Ratio qui est une
modification du Information Gain qui réduit son biais et est
généralement la meilleure option.
• Gain Ratio surmonte le problème de gain d'information en
prenant en compte le nombre de branches qui en résulterait avant
de faire la division.
• Il corrige Information Gain en prenant en compte l'information
intrinsèque d'un découpage.
• Gain Ratio ajoutera une pénalité à IG

𝐼𝐺(𝑇, 𝑋)
𝐺𝑎𝑖𝑛 𝑅𝑎𝑡𝑖𝑜: 𝐺𝑅 𝑇, 𝑋 =
𝑆𝑝𝑙𝑖𝑡𝐼𝑛𝑓𝑜(𝑋)
𝑆𝑝𝑙𝑖𝑡𝐼𝑛𝑓𝑜 𝑋 = − ෍ 𝑃 𝑐 𝑙𝑜𝑔2 (𝑃(𝑐))
𝑐∈𝑋 41
Gain Ratio : exemple
Outlook Temp Humidity Wind Play
sunny hot high FALSE NO
sunny hot high TRUE NO
overcast hot high FALSE YES
rainy mild high FALSE YES
rainy cool normal FALSE YES
rainy cool normal TRUE NO
overcast cool normal TRUE YES
sunny mild high FALSE NO
sunny cool normal FALSE YES
rainy mild normal FALSE YES
sunny mild normal TRUE YES
overcast mild high TRUE YES
overcast hot normal FALSE YES
rainy mild high TRUE NO

𝐼𝐺(𝑇, 𝑋)
𝐺𝑎𝑖𝑛 𝑅𝑎𝑡𝑖𝑜: 𝐺𝑅 𝑇, 𝑋 =
𝑆𝑝𝑙𝑖𝑡𝐼𝑛𝑓𝑜(𝑋) 42
 Gain Ratio : exemple
3 3 2 2

Play: classes
OUTLOOK yes no total P(c) Pi(yes) Pi(no) E(c)
sunny 2 3 5 0.357143 0.4 0.6 0.970951
overcast 4 0 4 0.285714 1 0 0
rainy 3 2 5 0.357143 0.6 0.4 0.970951
TOTAL 9 5 14
p(yes) p(no) E(T) E(T,X) IG splitInfo GR
0.642857 0.357143 0.940286 0.693536 0.24675 1.577406 0.156428

0.247
𝐺𝑎𝑖𝑛𝑅𝑎𝑡𝑖𝑜 𝑆, 𝑂𝑢𝑡𝑙𝑜𝑜𝑘 = = 0.1566
1.577 43
 Gain Ratio : exemple
classes
Temperature yes no total P(c) Pi(yes) Pi(no) E(c)
En utilisant les tableaux
hot
mild
2
4
2
2
4
6
0.285714 0.5 0.5 1
0.428571 0.666667 0.333333 0.918296
en face, on peut en
cool
TOTAL
3
9
1
5
4
14
0.285714 0.75 0.25 0.811278 déduire qu'Outlook a le
p(yes) p(no) E(T)
0.642857 0.357143 0.940286
E(T,X) IG splitInfo GR
0.911063 0.029223 1.556657 0.018773
Gain Ratio le plus élevé.
Donc le nœud racine
classes sera Outlook.
Wind yes no total Pc Pi(yes) Pi(no) E(c)
FALSE 6 2 8 0.571429 0.75 0.25 0.811278
TRUE 3 3 6 0.428571 0.5 0.5 1
TOTAL 9 5 14
p(yes) p(no) E(T) E(T,X) IG splitInfo GR Outlook
0.642857 0.357143 0.940286 0.892159 0.048127 0.985228 0.048849
sunny rainy
overcast
classes
Humidity yes no total Pc Pi(yes) Pi(no) E(c)
high 3 4 7 0.5 0.428571 0.571429 0.985228
normal 6 1 7 0.5 0.857143 0.142857 0.591673
TOTAL 9 5 14
p(yes) p(no) E(T) E(T,X) IG splitInfo GR
0.642857 0.357143 0.940286 0.78845 0.151836 1 0.151836
 Gain Ratio : exemple

Outlook-sunny Table
Outlook Temperature Humidity Wind Play
sunny hot high FALSE NO
sunny hot high TRUE NO
sunny mild high FALSE NO
sunny cool normal FALSE YES
sunny mild normal TRUE YES

classes
Temperature yes no total P(c) Pi(yes) Pi(no) E(c)
hot 0 2 2 0.4 0 1 0
mild 1 1 2 0.4 0.5 0.5 1
cool 1 0 1 0.2 1 0 0
TOTAL 2 3 5
p(yes) p(no) E(T) E(T,X) IG splitInfo GR
0.4 0.6 0.970951 0.4 0.570951 1.521928 0.37515
 Gain Ratio : exemple Humidity s'est avérée avoir le
GR la plus élevée. Donc le
classes
nœud de décision de la branche
Wind yes no total Pc Pi(yes) Pi(no) E(c)
FALSE 1 2 3 0.6 0.333333 0.666667 0.918296 Outlook-sunny sera Humidity.
TRUE 1 1 2 0.4 0.5 0.5 1
TOTAL 2 3 5
p(yes) p(no) E(T) E(T,X) IG splitInfo GR Créons les tableaux humidity-
0.4 0.6 0.970951 0.950978 0.019973 0.970951 0.020571 high et Humidity-normal
classes
Humidity-normal Table
Humidity yes no total Pc Pi(yes) Pi(no) E(c)
high 0 3 3 0.6 0 1 0 Humidity Wind Play
normal 2 0 2 0.4 1 0 0
TOTAL 2 3 5 normal FALSE YES
p(yes) p(no) E(T) E(T,X) IG splitInfo GR
0.4 0.6 0.970951 0 0.970951 0.970951 1 normal TRUE YES

Outlook
Humidity-high Table
Humidity Wind Play sunny rainy
overcast
high FALSE NO
Humidity ? ?
high TRUE NO
high normal
high FALSE NO
No Yes
Gain Ratio: exemple

Outlook-overcast

Outlook Temp Humidit Wind Play

overcast hot high FALSE YES
overcast cool normal TRUE YES
overcast mild high TRUE YES
overcast hot normal FALSE YES
Outlook

sunny rainy
overcast
Humidity yes ?

high normal
No Yes
 Outlook Temp Humidity Wind Play

Gain Ratio: exemple rainy

rainy
mild
cool
high
normal
FALSE YES
FALSE YES
rainy cool normal TRUE NO
rainy mild normal FALSE YES
Outlook-rainy rainy mild high TRUE NO
Humidity yes no total Pc Pi(yes) Pi(no) E(c)
high 1 1 2 0.4 0.5 0.5 1
normal 2 1 3 0.6 0.667 0.333 0.918 Wind s'est avérée avoir le
TOTAL 3 2 5
p(yes) p(no) E(T) E(T,X) IG splitInfo GR
GR la plus élevée. Donc le
0.6 0.4 0.971 0.951 0.02 0.971 0.021 nœud de décision de la
branche Outlook-rainy sera
Wind yes no total Pc Pi(yes) Pi(no) E(c) Wind.
FALSE 3 0 3 0.6 1 0 0
TRUE 0 2 2 0.4 0 1 0
TOTAL 3 2 5
p(yes) p(no) E(T) E(T,X) IG splitInfo GR
0.6 0.4 0.971 0 0.971 0.971 1

Temperature yes no total P(c) Pi(yes) Pi(no) E(c)

hot 0 0 0 0 0 0 0
cool 4 0 4 0.444 1 0 0
mild 3 2 5 0.556 0.6 0.4 0.971
TOTAL 7 2 9
p(yes) p(no) E(T) E(T,X) IG splitInfo GR
0.778 0.222 0.764 0.539 0.225 0.991 0.227
 Gain Ratio : exemple
Outlook-rainy

Outlook Temp Humidity Wind Play

rainy mild high FALSE YES
rainy cool normal FALSE YES
rainy mild normal FALSE YES Outlook-rainy-Wind-true
Outlook-rainy-Wind-false
Outlook Temp Humidity Wind Play
rainy cool normal TRUE NO
rainy mild high TRUE NO

Outlook

sunny rainy
overcast
Humidity yes wind

high normal false true

No Yes
Yes No
 Indice de Gini
• L' indice de Gini est une fonction de coût qui est également
utilisée pour évaluer les divisions dans l'ensemble de données.
• Il est calculé en soustrayant la somme des probabilités au carré de
chaque classe de un.
• Il privilégie les partitions plus grandes et faciles à mettre en œuvre
alors que le gain d'informations favorise les partitions plus petites
avec des valeurs distinctes.

L’𝑖𝑛𝑑𝑖𝑐𝑒 𝑑𝑒 𝐺𝑖𝑛𝑖 𝑝𝑜𝑢𝑟 une classe c d’un attribut 𝑋:

𝑐

𝐺𝑖𝑛𝑖𝑋𝑐 = 1 − ෍ 𝑝𝑖2
𝑖=1

𝐿𝑎 𝑠𝑜𝑚𝑚𝑒 𝑝𝑜𝑛𝑑é𝑟é𝑒 𝑑𝑒 𝑙′𝑖𝑛𝑑𝑖𝑐𝑒 𝑑𝑒 𝐺𝑖𝑛𝑖 𝑝𝑜𝑢𝑟 un attribut 𝑋:

𝑊𝑒𝑖𝑔ℎ𝑡𝑒𝑑 𝐺𝑖𝑛𝑖(X) = ෍ 𝑃𝑐 ∗ 𝐺𝑖𝑛𝑖𝑋𝑐
𝑐∈𝑋 50
 Indice de Gini
• L'indice de Gini fonctionne avec le label catégoriel "Succès" ou
"Échec". Il n'effectue que des divisions binaires.
o Une valeur plus élevée de l'indice de Gini implique une plus
grande inégalité , une plus grande hétérogénéité. L’attribut
avec Indice de Gini le plus bas sera selectioné.
• Étapes pour calculer l'indice de Gini pour une division

1. Calculez Gini pour les sous-nœuds, en utilisant la

formule ci-dessous pour le succès(p) et l'échec(q)
(p²+q²).
2. Calculez l'indice de Gini pour la division en utilisant le
score de Gini pondéré de chaque nœud de cette
division.
CART (Classification and Regression
Tree) utilise la méthode de l'indice de Gini 𝑊𝐺𝑖𝑛𝑖(X) = ෍ 𝑃𝑐 ∗ 𝐺𝑖𝑛𝑖𝑋𝑐
pour créer des points de partage. 𝑐∈𝑋 51
DT: Algorithmes

• L'algorithme d'arbre de décision ID3 utilise le

gain d'informations (IG)

• C4.5 , une amélioration de ID3, utilise le Gain

Ratio

• CART (Classification and Regression Tree)

utilise la méthode de l'indice de Gini

• Sklearn supporte l’Entropy et Gini

Formules 𝑐

𝐸𝑛𝑡𝑟𝑜𝑝𝑦: 𝐸 𝑇 = ෍ −𝑃𝑖 𝑙𝑜𝑔2 (𝑃𝑖 ) ↓

𝑖=1
𝐸 𝑇, 𝑋 = ෍ 𝑃 𝑐 𝐸(𝑐)
𝑐∈𝑋
ID3  𝐼𝑛𝑓𝑜𝑟𝑚𝑎𝑡𝑖𝑜𝑛 𝐺𝑎𝑖𝑛: 𝐼𝐺 𝑇, 𝑋 = 𝐸 𝑇 − 𝐸(𝑇, 𝑋) ↑

𝑆𝑝𝑙𝑖𝑡𝐼𝑛𝑓𝑜 𝑋 = − ෍ 𝑃 𝑐 𝑙𝑜𝑔2 (𝑃(𝑐))

𝑐∈𝑋
𝐼𝐺(𝑇, 𝑋)
C4.5  𝐺𝑎𝑖𝑛 𝑅𝑎𝑡𝑖𝑜: 𝐺𝑅 𝑇, 𝑋 =
𝑆𝑝𝑙𝑖𝑡𝐼𝑛𝑓𝑜(𝑋)
↑
𝑐

𝐺𝑖𝑛𝑖𝑋𝑐 = 1 − ෍ 𝑝𝑖2
𝑖=1

CART  𝐺𝑖𝑛𝑖(X) = ෍ 𝑃𝑐 ∗ 𝐺𝑖𝑛𝑖𝑋𝑐 ↓

𝑐∈𝑋
Construire des arbres : indice de
Gini
 Gini: exemple, Dataset
Weather Data
Outlook Temperature Humidity Wind Play
sunny hot high FALSE NO
sunny hot high TRUE NO
overcast hot high FALSE YES
rainy mild high FALSE YES
rainy cool normal FALSE YES
rainy cool normal TRUE NO
overcast cool normal TRUE YES
sunny mild high FALSE NO
sunny cool normal FALSE YES
rainy mild normal FALSE YES
sunny mild normal TRUE YES
overcast mild high TRUE YES
overcast hot normal FALSE YES
rainy mild high TRUE NO
 classes
Outlook yes no total P(c) Pi(yes) Pi(no) GINIi
sunny 2 3 5 0.357 0.4 0.6 0.48
overcast 4 0 4 0.286 1 0 0
rainy 3 2 5 0.357 0.6 0.4 0.48
W
TOTAL 9 5 14 GINI 0.343

Gini(Outlook=Sunny) = 1 – (2/5)2 – (3/5)2 = 1 – 0.16 – 0.36 = 0.48

Gini(Outlook=Overcast) = 1 – (4/4)2 – (0/4)2 = 0
Gini(Outlook=Rain) = 1 – (3/5)2 – (2/5)2 = 1 – 0.36 – 0.16 = 0.48

WGini(Outlook) = (5/14) x 0.48 + (4/14) x 0 + (5/14) x 0.48

= 0.171 + 0 + 0.171 = 0.342
 classes

Temperature yes no total P(c) Pi(yes) Pi(no) GINIi

hot 2 2 4 0.286 0.5 0.5 0.5
cool 3 1 4 0.286 0.75 0.25 0.375
middle 4 2 6 0.429 0.667 0.333 0.444
W
TOTAL 9 5 14 GINI 0.44

Gini(Temp=Hot) = 1 – (2/4)2 – (2/4)2 = 0.5

Gini(Temp=Cool) = 1 – (3/4)2 – (1/4)2 = 1 – 0.5625 – 0.0625 = 0.375
Gini(Temp=Mild) = 1 – (4/6)2 – (2/6)2 = 1 – 0.444 – 0.111 = 0.445

WGini(Temp) = (4/14) x 0.5 + (4/14) x 0.375 + (6/14) x 0.445

= 0.142 + 0.107 + 0.190 = 0.439
 classes
Humidity yes no total Pc Pi(yes) Pi(no) GINIi
high 3 4 7 0.5 0.429 0.571 0.49
normal 6 1 7 0.5 0.857 0.143 0.245
TOTAL 9 5 14 W Gini 0.367

Gini(Humidity=High) = 1 – (3/7)2 – (4/7)2 = 1 – 0.183 – 0.326 = 0.489

Gini(Humidity=Normal) = 1 – (6/7)2 – (1/7)2 = 1 – 0.734 – 0.02 = 0.244

W Gini(Humidity) = (7/14) x 0.489 + (7/14) x 0.244 = 0.367

classes
Wind yes no total Pc Pi(yes) Pi(no) GINIi
FALSE 6 2 8 0.571 0.75 0.25 0.375
TRUE 3 3 6 0.429 0.5 0.5 0.5
TOTAL 9 5 14 W Gini 0.429

Gini(Wind=False) = 1 – (6/8)2 – (2/8)2 = 1 – 0.5625 – 0.062 = 0.375

Gini(Wind=True) = 1 – (3/6)2 – (3/6)2 = 1 – 0.25 – 0.25 = 0.5

W Gini(Wind) = (8/14) x 0.375 + (6/14) x 0.5 = 0.428

W Gini(Outlook) = 0.342
W Gini(Temp) = 0.439
W Gini(Humidity) = 0.367
W Gini(Wind) = 0.428

Outlook a l’indice de Gini le plus bas donc il va être

sélectionné comme nœud racine.

Outlook

sunny rainy
overcast
 Table: Outlook-sunny
Gini: exemple

Outlook-sunny Table
Outlook Temperature Humidity Wind Play
sunny hot high FALSE NO
sunny hot high TRUE NO
sunny mild high FALSE NO
sunny cool normal FALSE YES
sunny mild normal TRUE YES
 Table: Outlook-sunny
Gini: exemple
classes
Temperature yes no total P(c) Pi(yes) Pi(no) GINIi
hot 0 2 2 0.4 0 1 0
mild 1 1 2 0.4 0.5 0.5 0.5
cool 1 0 1 0.2 1 0 0
TOTAL 2 3 5 W GINI 0.2

Gini(Outlook=Sunny and Temp.=Hot) = 1 – (0/2)2 – (2/2)2 = 0

Gini(Outlook=Sunny and Temp.=Cool) = 1 – (1/1)2 – (0/1)2 = 0
Gini(Outlook=Sunny and Temp.=Mild) = 1–(1/2)2 –(1/2)2 = 1–0.25 – 0.25 = 0.5

W Gini(Outlook=Sunny and Temp.) = (2/5)x0 + (1/5)x0 + (2/5)x0.5 = 0.2

Gini: exemple Table : Outlook-sunny

classes
Humidity yes no total Pc Pi(yes) Pi(no) GINIi
High 0 3 3 0.6 0 1 0
Low 2 0 2 0.4 1 0 0
TOTAL 2 3 5 W Gini 0

Gini(Outlook=Sunny and Humidity=High) = 1 – (0/3)2 – (3/3)2 = 0

Gini(Outlook=Sunny and Humidity=Normal) = 1 – (2/2)2 – (0/2)2 = 0
W Gini(Outlook=Sunny and Humidity) = (3/5)x0 + (2/5)x0 = 0

classes
Wind yes no total Pc Pi(yes) Pi(no) GINIi
FALSE 1 2 3 0.6 0.333 0.667 0.444
TRUE 1 1 2 0.4 0.5 0.5 0.5
TOTAL 2 3 5 W Gini 0.467

Gini(Outlook=Sunny and Wind=Weak) = 1 – (1/3)2 – (2/3)2 = 0.266

Gini(Outlook=Sunny and Wind=Strong) = 1- (1/2)2 – (1/2)2 = 0.2
W Gini(Outlook=Sunny and Wind) = (3/5)x0.266 + (2/5)x0.2 = 0.466
 Table : Outlook-sunny
Gini: exemple
W Gini(Outlook=Sunny and Temp.) = 0.2
W Gini(Outlook=Sunny and Humidity) = 0
W Gini(Outlook=Sunny and Wind) = 0.466

L'humidité a la valeur la plus basse. Donc, le prochain nœud sera

l'humidité.

Outlook

sunny rainy
overcast
Humidity ? ?

high low
Outlook-sunny Humidity-high Table : Outlook-sunny
Outlook Temperature Humidity Wind Play Humidity

sunny hot high FALSE NO

sunny hot high TRUE NO
sunny mild high FALSE NO

Outlook-sunny Humidity-normal
Outlook Temperature Humidity Wind Play
sunny cool normal FALSE YES
sunny mild normal TRUE YES

Outlook

sunny rainy
overcast
Humidity ? ?

high normal
No Yes
 Table Outlook-overcast
Weather Data
Outlook Temperature Humidity Wind Play
overcast hot high FALSE YES
overcast cool normal TRUE YES
overcast mild high TRUE YES
overcast hot normal FALSE YES

Comme vous pouvez le voir dans le tableau ci-dessus,

toutes les décisions concernant la fonction de perspectives
couvertes sont toujours "Yes". Donc, l'indice de Gini pour
chaque fonctionnalité est 0, ce qui signifie qu'il s'agit d'un
nœud feuille. Outlook

sunny rainy
overcast
Humidity Yes ?

high low
No Yes
Table Outlook-rainy
Weather Data : Outlook-rainy
Outlook Temperature Humidity Wind Play
rainy mild high FALSE YES
rainy cool normal FALSE YES
rainy cool normal TRUE NO
rainy mild normal FALSE YES
rainy mild high TRUE NO

Weather Data : Outlook-rainy temperature-mild

Outlook Temperature Humidity Wind Play
rainy mild high FALSE YES
rainy mild normal FALSE YES
rainy mild high TRUE NO

Weather Data : Outlook-rainy temperature-cool

Outlook Temperature Humidity Wind Play
rainy cool normal FALSE YES
rainy cool normal TRUE NO
Temperature yes no total Pc Pi(yes) Pi(no) GINIi
cool 1 1 2 0.4 0.5 0.5 0.5 Table Outlook-rainy
mild 2 1 3 0.6 0.667 0.333 0.444
TOTAL 3 2 5 W Gini 0.467

Gini(Outlook=Rain and Temp.=Cool) = 1 – (1/2)2 – (1/2)2 = 0.5

Gini(Outlook=Rain and Temp.=Mild) = 1 – (2/3)2 – (1/3)2 = 0.444
W Gini(Outlook=Rain and Temp.) = (2/5)x0.5 + (3/5)x0.444 = 0.466
Humidity yes no total Pc Pi(yes) Pi(no) GINIi
high 1 1 2 0.4 0.5 0.5 0.5
normal 2 1 3 0.6 0.667 0.333 0.444
TOTAL 3 2 5 W Gini 0.467

Gini(Outlook=Rain and Humidity=High) = 1 – (1/2)2 – (1/2)2 = 0.5

Gini(Outlook=Rain and Humidity=Normal) = 1 – (2/3)2 – (1/3)2 = 0.444
Gini(Outlook=Rain and Humidity) = (2/5)x0.5 + (3/5)x0.444 = 0.466
Wind yes no total Pc Pi(yes) Pi(no) GINIi
FALSE 3 0 3 0.6 1 0 0
TRUE 0 2 2 0.4 0 1 0
TOTAL 3 2 5 W Gini 0

Gini(Outlook=Rain and Wind=Weak) = 1 – (3/3)2 – (0/3)2 = 0

Gini(Outlook=Rain and Wind=Strong) = 1 – (0/2)2 – (2/2)2 = 0
Gini(Outlook=Rain and Wind) = (3/5)x0 + (2/5)x0 = 0
 Outlook

sunny rainy
overcast
Humidity Yes Wind

high low false true

No Yes ? ?
 Weather Data : Outlook-rainy
Outlook Temperature Humidity Wind Play
rainy mild high FALSE YES
rainy cool normal FALSE YES
rainy cool normal TRUE NO
rainy mild normal FALSE YES
rainy mild high TRUE NO

Weather Data : Outlook-rainy wind-false

Outlook Temperature Humidity Wind Play
rainy mild high FALSE YES
rainy cool normal FALSE YES
rainy mild normal FALSE YES

Weather Data : Outlook-rainy

Outlook Temperature Humidity Wind Play
rainy cool normal TRUE NO
rainy mild high TRUE NO
 Outlook

sunny rainy
overcast
Humidity Yes Wind

high low false true

No Yes Yes No
 Arbres de décision :
avantages/inconvénients
 Avantages
1. Comparé à d'autres algorithmes, les arbres de
décision nécessitent moins d'efforts pour la
préparation des données lors du prétraitement.
2. Un arbre de décision ne nécessite pas de
normalisation des données.
3. Un arbre de décision ne nécessite pas non plus de
mise à l'échelle des données.
4. Les valeurs manquantes dans les données
n'affectent PAS non plus le processus de
construction d'un arbre de décision dans une
mesure considérable.
5. Un modèle d'arbre de décision est très intuitif et
facile à expliquer aux équipes techniques ainsi
qu'aux parties prenantes. 72
 Inconvénients
1. Le Overfitting peut devenir un problème si la
conception d'un arbre de décision est trop
complexe.
2. Ils ne sont pas bien adaptés aux variables
continues (c'est-à-dire les variables qui peuvent
avoir plus d'une valeur, ou un spectre de
valeurs.)
3. Ils sont instables , ce qui signifie qu'un petit
changement dans les données peut entraîner un
grand changement dans la structure de l'arbre
de décision optimal.
4. Ils sont souvent relativement imprécis .
5. Les arbres de décision impliquent souvent plus
de temps pour former le modèle. 73
 Quand utiliser les arbres de
décision ?
 Instances descriptibles par des paires attribut-valeur
 La fonction cible est à valeur discrète
 Données d'entraînement éventuellement bruyantes
 Valeurs d'attribut manquantes
 Exemples:
o Diagnostic médical
o Analyse du risque de crédit
o Classification d'objets pour robot manipulateur

74
SKLearn
 arbres de décision SKLearn
# Cet exemple provient du lien suivant
# https://scikit-learn.org/stable/modules/tree.html
from sklearn.datasets import load_iris
from sklearn import tree
import graphviz
# Charger les données d'iris
iris = load_iris()
# X contiendra les caractéristiques, y contiendra l'étiquette
X, y = iris.data, iris.target
print('La cible de classification:\ n',iris [‘target'])
print('Les noms des colonnes du jeu de données:\n',iris [' feature_names '])
print('Les noms des classes cibles:\n',iris [' target_names '])

La cible de classification:
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0000000000000111111111111111111111111
1111111111111111111111111122222222222
2222222222222222222222222222222222222
2 2]
Les noms des colonnes du dataset:
['sepal length (cm)', 'sepal width (cm)', 'petal length (cm)', 'petal width (cm)']
Les noms des classes cibles:
['setosa' 'versicolor' 'virginica']

76
 arbres de décision SKLearn
print('La description complète du dataset:\n',iris['DESCR'])
print('Le chemin vers l'emplacement du dataset:\n',iris['filename'])

**Data Set Characteristics:**

:Number of Instances: 150 (50 in each of three classes)

:Number of Attributes: 4 numeric, predictive attributes and the class
:Attribute Information:
- sepal length in cm
- sepal width in cm
- petal length in cm
- petal width in cm
- class:
- Iris-Setosa
- Iris-Versicolour
- Iris-Virginica

:Summary Statistics:

============== ==== ==== ======= ===== ====================

Min Max Mean SD Class Correlation
============== ==== ==== ======= ===== ====================
sepal length: 4.3 7.9 5.84 0.83 0.7826
sepal width: 2.0 4.4 3.05 0.43 -0.4194
petal length: 1.0 6.9 3.76 1.76 0.9490 (high!)
petal width: 0.1 2.5 1.20 0.76 0.9565 (high!)
============== ==== ==== ======= ===== ====================

77
 arbres de décision SKLearn
# Utilisez le classificateur d'arbres de décision pour ajuster les données
clf = tree.DecisionTreeClassifier()
clf = clf.fit(X, y)
# Tracer l'arbre
tree.plot_tree(clf)

78
Sommaire
 Sommaire
 Un arbre de décision est une structure semblable à un organigramme
dans laquelle :
• Chaque nœud interne représente un « test » sur un attribut, un
• Chaque branche représente le résultat du test, et
• Chaque nœud feuille représente une étiquette de classe (décision prise après
calcul de tous les attributs).
• Les chemins de la racine à la feuille représentent des règles de classification.
 Avantages :
o Sont simples à comprendre et à interpréter
o Avoir de la valeur même avec peu de données concrètes
o Aide à déterminer les pires, les meilleures et les valeurs attendues pour
différents scénarios
 Inconvénients :
o Ils sont instables, ce qui signifie qu'un petit changement dans les données
peut entraîner un changement important dans la structure de l'arbre de
décision optimal.
o Ils sont souvent relativement imprécis.
 On peut y remédier en remplaçant un arbre de décision unique par une
forêt aléatoire (Ensemble)
81
Ressources
 Divers Ressources
o Youtube:
 Introduction:
o https://www.youtube.com/watch?v=7VeUPuFGJHk
o https://www.youtube.com/watch?v=_L39rN6gz7Y
 Construire des arbres :
o https://www.youtube.com/watch?v=ZVR2Way4nwQ
 Sélection de fonctionnalités (données manquantes)
o https://www.youtube.com/watch?v=wpNl-JwwplA
 Tutoriel (arbres de décision en Python)
o https://www.youtube.com/watch?v=RmajweUFKvM
 Le classificateur d'arbre de décision :
o https://www.youtube.com/watch?v=ZVR2Way4nwQ
 Régression d'arbre de décision :
o https://www.youtube.com/watch?v=UhY5vPfQIrA
 Méthode de sélection des attributs (ASM)
o https://www.youtube.com/watch?v=5aIFgrrTqOw
o https://www.youtube.com/watch?v=-W0DnxQK1Eo

83
 Divers Ressources
o Tutoriels :
 Mesures de sélection d'attribut :
 https://www.kdnuggets.com/2020/01/decision-tree-algorithm-explained.html
 https://becominghuman.ai/decision-trees-in-machine-learning-f362b296594a
 https://www.datacamp.com/community/tutorials/decision-tree-classification-python
 https://stackabuse.com/decision-trees-in-python-with-scikit-learn/
 https://www.hackerearth.com/practice/machine-learning/machine-learning-algorithms/ml-decision-
tree/tutorial/
 https://towardsdatascience.com/understanding-decision-trees-for-classification-python-9663d683c952

o Documents :
 https://en.wikipedia.org/wiki/Decision_tree_learning
 https://scikit-learn.org/stable/modules/tree.html

84