Departement d’informatique
Les Arbres de Decision (Partie
1)
Master 1 MID S2
Enseignant:
Hadjila Fethallah
1
Exemple d’arbre de décision
climat
ensoléillé pluvieux
oui companie
petite grande
moyenne
non Taille bateau oui
petite grande
Definition:
A.D est un classifieur en forme d’arbre , ses feuilles
oui non
représentent les classes de sorties, les nœuds internes
représentent les tests à exécuter sur un attribut, et les
2 branches sont étiquetées avec les valeurs du test
Motivations
Traitement de données nominales
Ex: Variable Métier ={footballeur, enseignant,
étudiant, recteur...}
Traitement de données discrètes et continues
L’utilisation de plusieurs arbres de décision
simples peut améliorer les performance de
généralisation (réduction de la variance)
La connaissance induite par l’arbre de décision
peut être représentée avec des règles de
production .
Disjonction de règles (une règle est une
conjonction de conditions).
Grande capacité d’interprétation (par
opposition aux approches de type boite noire)
3
Classifieur de nature supervisée
test
climat
ensoléillé pluvieux
semantique de l’arbre de
decision oui companie
chaque noeud interne
petite grande
représente moyenne
o Une partie de la base
d’apprentissage non Taille bateau oui
o L’ attribut de division
courant petite grande
Chaque arc est etiqueté
avec la valeur de oui non
l’attribut de division
4
Difficultés
Le choix de la variable de division (quelle
heuristique)
Le traitement des variables continues.
Le traitement des valeurs manquantes.
Le traitement des variables (attributs)
ayant des couts différents.
La Presence de données bruitées ou
conflictuelles
La determination du nombre optimal de
noeuds
(methodes d’élagage de l’arbre)
5
l’apprentissage
Base d’apprentissage etiquetée
Chaque example est caractérisé
par ses attributs + sa Classe
Principe d’induction des arbres de
decision
Minimiser l’impurté des noeuds.
Partionnement recursive
6
Formalisation de l’apprentissage
Algorithme d’apprentissage general
Entrée: base etiquetée
Sortie: arbre de decision (AD)
1. noeud-courant= racine de l’arbre (tous les exemples)
2. Initialiser (AD, noeud-courant)
3. Repeter
1. Decider si Noeud-courant est un noeud terminal
a) Si oui affecter cette feuille à une classe donnée
b) Sinon : choisir un attribut de division selon la mesure
d’impurté et creer les enfants de Noeud-courant et mettre à
jour AD
2. MAJ du noeud courant (ie passer aux enfants non
explorés)
4. Jusqu’à ce que (plus d’enfants à diviser ou plus
d’attributs de division)
7
5. Retourner AD
Algorithmes d’apprentissage
ID3 (Quinlan 79)
CHAID (Kass 80)
CART (Brieman et al. 84)
Assistant (Cestnik et al. 87)
C4.5 (Quinlan 93)
C 5.0, See5 (Quinlan 97)
...
8
Critère de Selection d’
Attribut
principe
Selectionner l’attribut qui maximise la purté des
enfants
Plusieurs mesures d’impurté
Entropie (adoptée par ID3)
Index de Gini (adopté par CART)
X2 (adopté par de CHAID)
ReliefF
...
Plusieurs ameliorations possibles
9
Algorithme ID3 (Quinlan 79)
Signifie 3eme serie de “Iterative
dichotomizer”
Utilise uniquement les variables discretes
Les variables continues doivent etre
discretisées avec des intervalles
La mesure d’impurté employée est celle de
l’entropie
Pas de procedure d’élagage (possibilité
d’overfiting)
10
Algorithme ID3 (Quinlan 79)
Entrée :base d’apprentissage S
Sortie: arbre de decision noté AD
1. Si S est vide alors retourner un noeud nommé “echec”
Sinon
1.Si S contient des exemples de meme classe alors retourner
un seule feuille contenant la valeur de cette classe
2.Si l’ens des attributs est vide
1. alors retourner un seule feuille etiquetée par la classe
majoritaire
Sinon
1. Choisir un attribut qui maximise le gain d’information
2. Pour chaque enfant i du test precedant : SADi=ID3(i)
3. Mettre à jour AD (affecter le test au parent et ajouter
les sous arbres SADi à AD)
2.
11 Retourner (AD)
Algorithme ID3
• Resulting tree T is:
A Attribute A
v1 v2 vn A’s values
T1 T2 Tn Subtrees
12
Approche à base de theorie
d’information
Pour classer un objet on aura besoin d’une
certaine quantité d’information (nombre de
bits)
I represente cette quantité d’information
Apres l’utilisation de l’attribut A, on a besoin
seulement d’une quantité d’information
restante (ou résiduelle) pour classer l’objet
Ires, represente la quantité d’information résiduelle
Gain
Gain(A) = I – Ires(A)
L’attribut le plus ‘informatif’ est celui qui
minimise Ires, i.e., (ou maximise le Gain)
13
Entropie
C’est le degré de désordre d’un ensemble
C’est la quantité d’information moyenne que l’on
a besoin pour coder les elements d’un ensemble
Plus l’evenement est sur, plus sa quantité
d’information est faible et vice versa.
Pour un problème binaire (l’entropie de
l’ensemble X est notée H(x))
entropy
p(c1)
14
Information Residuelle
Aprés l’application de A, S est partitionné
en v sous ensembles (v est le nombre de
valeurs de A)
Ires =la moyenne des quantités
d’information des enfants
15
Triangles et carrés
Data Set:
A set of classified objects
. .
. .
. .
16
Entropie
• 5 triangles
• 9 carrés
. .
• Probabilités des classes
. .
. .
• entropie
17
. . .
.
. .
. .
red
Color? green
reduction .
de yellow .
l’entropie
.
.
18
. . .
.
. .
. .
red
Color? green
.
yellow .
.
.
19
. . .
.
. .
. .
red
Color? green
.
yellow .
.
.
20
Gain d’information Gain d’ un attribute
Attributs
Gain(Couleur) = 0.246
Gain(trait) = 0.151
Gain(point) = 0.048
Heuristique: on choisit l’attribut ayant le plus
grand gain
cette heuristique est locale (minimisation
locale de l’ impurté)
21
. .
. . .
.
. . red
Color?
green
. yellow
.
. .
Gain(trait) = 0.971 – 0 = 0.971 bits
Gain(point) = 0.971 – 0.951 = 0.020
bits
22
. .
. . .
.
. . red
Gain(trait) = 0.971 – 0.951 = 0.020
Color?
bits
green Gain(point) = 0.971 – 0 = 0.971 bits
. yellow
.
. .
solid
.
Outline?
dashed
.
23
. .
. . .
.
. . red
yes .
Dot? .
Color?
no
green
. yellow
.
. .
solid
.
Outline?
dashed
.
24
L’arbre de Decision
. .
. ..
. .
Couleur
rouge vert
jaune
point carré trait
oui non pointillé plein
triangle carré triangle carré
25
Les lacunes de l’entropie
Le gain d’information favorise les attributes
ayant plusieurs valeurs
Un attribut (ayant plusieurs valeurs) divise S en
plusieurs sous ensembles, et si ces derniers
sont petits, il auront une tendance à etre purs.
Le ratio de gain d’ information est
considéré comme un moyen de correction de
cette lacune.
26
Ratio de Gain d’Information
I(A) is quantité d’information necessaire
pour coder A
Ratio de gain d’Information
27
. . .
.
. .
. .
red
Color? green
.
yellow .
.
.
28
Le gain d’information et le Ratio de gain
d’information
29
L’Index de Gini
Constitue une autre mesure d’impurté
(i et j sont des classes)
Aprés l’application de A, l’index Gini du resultat
sera:
Gini signifie aussi l’esperance du taux d’erreur
30
L’Index de Gini vs l’entropie
Classification binaire
31
Mesure d’Impurté: GINI
L’Index Gini pour un noeud t :
2
GINI (t )=1−∑ [ p( j|t )]
j
(NOTE: p( j | t) la frequence de la classe j pour le noeud t).
Le maximum de gini est atteint lorsque les classes sont
équitablement réparties
Le Minimum est atteint lorsque tous les exemples
appartiennent à la meme classe
C1 0 C1 1 C1 2 C1 3
C2 6 C2 5 C2 4 C2 3
Gini=0.000 Gini=0.278 Gini=0.444 Gini=0.500
Exemples de calcul de GINI
2
GINI (t )=1−∑ [ p( j|t )]
j
C1 0 P(C1) = 0/6 = 0 P(C2) = 6/6 = 1
C2 6 Gini = 1 – P(C1)2 – P(C2)2 = 1 – 0 – 1 =
0
C1 1 P(C1) = 1/6 P(C2) = 5/6
C2 5 Gini = 1 – (1/6)2 – (5/6)2 = 0.278
C1 2 P(C1) = 2/6 P(C2) = 4/6
C2 4 Gini = 1 – (2/6)2 – (4/6)2 = 0.444
Division à base de GINI
Principe utilisé dans CART, SLIQ, SPRINT.
k
ni
GainGini=GINI ( parent )−( ∑ GINI (i))
i=1 n
avec, ni = la taille de l’enfant i,
n = la taille du parent.
Attributs binaires
On calcule le Gini du père
On calcule la moyenne des Gini des enfants
On fait la différence pour avoir le gain
Parent
B? C1 6
Oui Non C2 6
Gini = 0.500
Noeud N1 Noeud N2
Gini(N1)=
1 – (5/6)2 – (2/6)2 N1 N2 Gini(Enfant)
= 0.194 C1 5 1 = 7/12 * 0.194
Gini(N2)= C2 2 4 +
1 – (1/6)2 – (4/6)2 Gini=0.333 5/12 * 0.528
= 0.528 = 0.333
Attributs symboliques
Theoriquement on peut faire une division
binaire ou multi-label mais dans la pratique on
utilise toujours une division binaire
Gini(père)= 0.48
division interdite Two-way split
(find best partition of values)
CarType CarType
CarType
{Sports, {Family,
Family Sports Luxury {Family} {Sports}
Luxury} Luxury}
C1 1 2 1 C1 3 1 C1 2 2
C2 4 1 1 C2 2 4 C2 1 5
Gini 0.393 Gini 0.400 Gini 0.419
L’Index de variance (pour le
cas binaire)
. .
. .
. .
Index de variance = p(c1).p(c2)
Index de variance = 9/14 * 5/14
37
L’index de classification
erronée
. .
. .
. .
P ( i |t )
MiscalssificationIndex(t)=1- 9/14=5/14
38
conclusion
• L’arbre de décision constitue un classifieur pouvant traiter
des données continues, discrètes et symboliques
• L’apprentissage suit une approche gloutonne pour choisir les
variables de division
• La réduction du sur-apprentissage constitue un problème
majeur pour les arbres de décisions
• Les performances peuvent être boostées si on utilise des
approches aléatoires et coopératives (Bagging)
39
