Arbres de décision

Notations

• N exemples d’apprentissage

• d variables explicatives

• (Y,X1,X2,…,Xd) les variables de la population

• (yi,xi) est le vecteur des réalisations de (Yi,Xi)

Principe des arbres de décisions (AD)

• À partir de ces exemples d’apprentissage, on construit un

arbre de décision, tel que:

 Un nœud correspond à un test sur la valeur d'un ou

plusieurs attributs;
 Une branche partant d'un nœud correspond à une ou
plusieurs valeurs de ce test;
 Une feuille est associée une valeur de l'attribut cible Y.

3
Principe des arbres de décisions (AD)

• L'arbre de décision est exploité de différentes manières :

1. En y classant de nouvelles données;

2. En faisant de l'estimation d'attributs;

3. En extrayant un jeu de règles de classification;

4. En interprétant la pertinence des attributs.

4
Construction d’un AD – Exemple

• Soit à un ensemble de jours (un jour = un exemple).

• Chaque jour est caractérisé par un numéro et ses conditions

météorologiques (ciel, température, humidité de l'air, force
du vent).

• L'attribut cible étant « jouer au tennis ? », dont les valeurs

possibles sont Y = {oui, non}.

• Une fois l'arbre de décision construit, on pourra classer une

nouvelle donnée pour savoir « si on joue ou non ce jour-là ».

5
Construction d’un AD – Exemple

6
Construction d’un AD – Exemple
• Soit un exemple d’AD:

• L’exemple de ligne 1 du tableau

sera classé comme «oui» ! 7

Construction d’un AD

• La construction d’un AD optimal (minimisant l'erreur de

classification) est un problème NP-complet.

• Au lieu de construire l'arbre de décision optimal pour un jeu

d'exemples donné, on se contente de construire un arbre de
décision ‘correct‘.

• Plusieurs algorithmes ont été proposés pour construire des

AD, dont CART, ID3 et C4.5 :
• ID3 ne prend en compte que des attributs nominaux.
• C4.5 prend également en charge des attributs quantitatifs.

8
Construction d’un AD

• Dans notre exemple, on suppose que tous les attributs sont

nominaux.
• ID3 et C4.5 fonctionnent récursivement comme suit :
Déterminer un attribut à placer en racine de l'arbre. La
racine possède autant de branches que de valeurs pour cet
attribut.
À chaque branche est associé un ensemble d'exemples
dont l'attribut prend la valeur qui étiquette cette branche.
On accroche alors au bout de cette branche l'arbre de
décision construit sur ce sous-ensemble d’exemples, en
considérant tous les attributs excepté celui qui vient d’être
mis à la racine.
9
Arbres de décision: Algorithmes ID3, C4.5

Nœud = racine;

1- att ← meilleur attribut de décision pour prochain nœud;

2- Assigner att comme attribut de décision au nœud;
3- Pour chaque valeur de att, créer un nœud descendant;
4- Trier les exemples d’entrainement dans les feuilles de l’arbre;
5- Si (les exemples sont parfaitement classés)
STOP;
sinon
Itérer sur le nœud feuille.
fin

10
Choix de l’attribut de décision

Soit un exemple de nœud pour lequel on doit choisir un attribut

de décision:
[29+, 35-] a1? [29+, 35-] a2?

[21+, 05-] [8+, 30-] [18+, 33-] [11+, 02-]

Quel attribut de décision choisir, a1 ou a2?

11
Choix de l’attribut de décision

• Les algorithmes de construction d’AD fonctionnent de haut

en bas, en choisissant à chaque étape une variable qui
divise le mieux l’ensemble des exemples.

• Les métriques utilisées pour choisir un meilleur attribut

mesurent en général l’homogénéité de la variable cible
dans les sous-ensembles résultants de la division de nœuds.

• Une autre mesure est le gain d’information, qui se base sur

le concept d’entropie de la théorie de l’information.

12
Choix de l’attribut de décision

Entropie (cas d’une variable avec un attribut x)

• Soit (x) la distribution de la variable x mesurant l’incertitude

sur la valeur de la variable.

• Certaines valeurs de variables sont moins sures que d’autres.

p(x) p(y)
x y

• L’entropie mesure le nombre de bits requis pour encoder x.

13
Choix de l’attribut de décision

• L’entropie (x) d’une variable aléatoire x est définie par:

(x)= - ∑ (x = ) log2( (x = ))
X =

• (x) est le nombre de bits attendu pour encoder les valeurs de

la variable aléatoire x.

• Un code efficace assigne - log2( (x = )) bits pour encoder

un message x = . La valeur attendu de la longueur du code
est alors définie par la formule en haut.
14
Choix de l’attribut de décision (cas binaire)

• Pour K = 2 (deux classes), les éléments de la classe C1 seront

dénotés par ⊕ et ceux de la classe C2 par ⊖. On aura:

x =− ⊕log2( ⊕) − ⊖log2( ⊖)

• ⊕ et ⊖ sont les proportions des deux classes dans le nœud,

avec ⊕ + ⊖ = 1.

On aura aussi:
• 0 ≤ (x)≤ 1.
• Si ⊕= 0 ou ⊖ = 0, alors (x)= 0.
• Si ⊕= ⊖ = 0.5, alors (x)= 1 (entropie maximale).

15
Choix de l’attribut de décision (cas binaire)

• Pour le cas de 2 classes, on aura le graphe suivant de x:

• L’entropie mesure le degré d’impureté d’un nœud.

16
Choix de l’attribut de décision (cas binaire)

• Soit une population d'exemples D . Le gain d'information de D

par rapport à un attribut donné est la variation d'entropie
causée par la partition de D selon .

|D aj=v |
! D, = D − ∑ D aj=v
|D|
∈ %&'()( )

• D aj=v ⊂ D est l’ensemble des exemples ayant = .

• |D|indique la cardinalité de l’ensemble D .

17
Choix de l’attribut de décision (cas binaire)

• Si prends par exemple 3 valeurs ∈ { 1, 2, 3} , la partition

de D va former 3 parties: D aj=v1 ,Daj=v2 ,Daj=v3. Le gain
d’information est donné par:

D aj=v1 |D aj=v2 | D aj=v3

D − D aj=v1 − D aj=v2 − D aj=v3
|D| |D| |D|

• On peut dire donc que le gain est la différence entre

l'entropie moyenne des exemples D et l'entropie moyenne
une fois que D a été partitionné selon les valeurs de .

• On notera que plus cette différence (le gain) est grande, plus
l’homogénéisation est grande.
18
Choix de l’attribut de décision (cas binaire)

Exercice:
a y
6 ⊕  faible
2 ⊖  faible 9⊕
3 ⊕  fort 5⊖
3 ⊖  fort

• Dans cet exemple, il existe 9 ⊕ et 5 ⊖. Parmi ces exemples,

6 ⊕ et 2 ⊖ prennent la valeur «faible» pour l'attribut a,
tandis que les autres exemples prennent la valeur «fort»
pour cet attribut.
• Calculer le gain d’information !(D , ) pour l’attribut , si
on choisi de le placer en racine. 19
Solution:
a y
6 ⊕  faible
2 ⊖  faible 9⊕
3 ⊕  fort 5⊖
3 ⊖  fort

− 8 D − 6 D
! D, = - =faible =fort
14 14
9 9 5 5
- =− log2 − log2 = 0.940
14 14 14 14
6 6 2 2
D =faible = − log2 − log2 = 0.811
8 8 8 8
3 3 3 3
D =fort = − log2 − log2 =1
6 6 6 6
8 6
! D, = 0.940 − 0.811 − 1 = 0.940 − 0.8920 = 0.048
14 14 20
Choix de l’attribut de décision (cas binaire)

• Le principe de l'algorithme ID3 pour déterminer l'attribut à

placer à la racine de l’AD est de:

Chercher l'attribut qui possède le gain d'information

maximum, le placer en racine.

 Itérer pour chaque fils, c.à.d. pour chaque valeur de

l'attribut.

Arrêter l'algorithme quand le gain est négligeable.

21
Étude d’un exemple d’AD

Pour notre exemple: « jouer au tennis?»,

• les exemples n’étant ni tous ⊕, ni tous ⊖, l'ensemble des

attributs n’étant pas vide, on calcule les gains d’information
pour chaque attribut:

• Donc, la racine de l’AD est l’attribut « Ciel ».

22
Étude d’un exemple d’AD

• L'attribut « Ciel » peut prendre 3 valeurs: Ensoleillé, Pluie et

Couvert.
• La branche « Ensoleillé »: ID3, appelé récursivement avec 5
exemples: (1), (2), (8), (9) , (11).

23
Étude d’un exemple d’AD

• L'attribut « Ciel » peut prendre 3 valeurs: Ensoleillé, Pluie et

Couvert.
• La branche « Ensoleillé »: ID3, appelé récursivement avec 5
exemples: (1), (2), (8), (9) , (11).
• Les gains d'information des 3 attributs restants sont alors :

• L'attribut « Humidité » sera donc choisi ;

• on continue la construction de l’AD récursivement.

24
Étude d’un exemple d’AD

• La branche « Pluie »: partant de la racine, ID3 est appelé

récursivement avec 5 exemples: (4), (5), (6), (10), (14).

• On continue la construction de l’AD récursivement .

• La branche « Couvert »: partant de la racine, ID3 est appelé

récursivement avec 4 exemples: (3), (7), (12), (13).

• Dans ce dernier cas, tous les exemples sont ⊕ : on affecte

donc tout de suite la classe « oui » à cette feuille.

25
Étude d’un exemple d’AD

• L’arbre final sera donné par le graphe:

26
Étude d’un exemple d’AD

On peut faire les remarques suivantes sur le graphe:

• L'attribut « Température », n’est pas utilisé dans l’AD, signifie

que cet attribut n'est pas pertinent pour déterminer la classe.

• Si l’attribut « Ciel » vaut « Ensoleillé» , l'attribut « Vent » n'est

pas pertinent.

• Si l'attribut « Ciel » vaut « Pluie », l'attribut « Humidité» n'est

pas pertinent.

27
Classification par AD

En ayant un AD construit à partir d’exemples d’apprentissage D ,

la classification d’une nouvelle donnée x se fait par l’algorithme
suivant:
Algorithme: entrées (AD, x)
• Nc = racine (AD)
• Tant-que (Nc ≠ feuille) faire:
- En fonction de l'attribut testé dans Nc et de sa valeur
dans x, suivre l'une des branches de Nc.
- Le nœud atteint devient Nc.
• Fin tant-que
• Retourner Étiquette (Nc).

28
Classification par AD

Exercice: Classer les exemples suivants:

= (Ensoleillé, Fraîche, Elevée, Fort) ;

= (Ensoleillé, Fraîche, Normale, Fort) ;

= (Pluie, Chaude, Normale, Faible);

= (Pluie, Fraîche, Elevée, Fort).

29
Classification par AD

Exercice: Classer les exemples suivants:

= (Ensoleillé, Fraîche, Elevée, Fort) ;

Non
= (Ensoleillé, Fraîche, Normale, Fort) ;
Oui
= (Pluie, Chaude, Normale, Faible);
Oui
= (Pluie, Fraîche, Elevée, Fort).
Non

30