M2 - MP2L: Machine Deep Learning - Arbres de Décision - Corrigé

-

-

1. A partir de ces données, construisez l'arbre de décision en utilisant la fonction gain basée

sur l'entropie de Shannon. Vous indiquerez la valeur d’entropie de chaque nœud, et le gain

d’information

attribut.

Sur l’arbre, vous indiquerez à côté de chaque nœud le nombre d’individus de chaque

classe. Le critère d’arrêt de construction de l’arbre est l’obtention de nœuds homogènes.

chaque

obtenu

choix

par

de

le

A la racine

On remarque que sur les 8 lignes des données d'apprentissage, 3 correspondent à la classe "+" et 5 à la classe

"-".

L'entropie de l'ensemble S (à la racine de l'arbre) est donc égale à :

Entropie (S)= -(3/8)log2(3/8)-(5/8)log2(5/8) =0.954

Pour connaître quel attribut on doit choisir comme test au niveau de la racine de l'arbre, il faut calculer le

gain d'entropie sur chacun des attributs : "Taille", "Cheveux" et "Yeux".

Calcul du gain d'entropie sur l'attribut " Taille " :

Gain(S, Taille) = Entropie(S) - Entropie(S/Taille)

Entropie(S/Taille)= 3/8 Entropie(Spetir) + 5/8 Entropie(Sgrand)=0,950 (entropie conditionnelle)

avec Entropie(Spetit)= -(1/3)log2(1/3)- (2/3)log2(2/3) (3 exemples répartis en 1+ et 2-)

et Entropie(Sgrand)= -(2/5)log2(2/5)- (3/5)log2(3/5) (5 exemples répartis en 2+ et 3-)

d’où Gain(S, Taille) =0.954-0.950=0.004

1/4

Calcul du gain d'entropie sur l'attribut " Cheveux " :

Gain(S, Cheveux) = Entropie(S) - Entropie(S/ Cheveux)

Entropie(S/ Cheveux)= 4/8 Entropie(Sblond) + 1/8 Entropie(Sroux) + 3/8 * Entropie(Snoir)=0.5

et Entropie(Sroux)= -1/1*log2(1/1) =0

avec Entropie(Sblond)= -(2/4)log2(2/4)- (2/4)log2(2/4)= 1 (4 exemples répartis en 2+ et 2-)

(répartition équitable : entropie maximale)

(1 exemples de classe+)

(nœud homogène : entropie minimale)

(3 exemples de classe-)

(nœud homogène : entropie minimale)

et Entropie(Sbrun)=0

d’où Gain(S, Cheveux) = 0.954-0.5=0.454

Calcul du gain d'entropie sur l'attribut " Yeux " :

Gain(S, Yeux) = Entropie(S) - Entropie(S/ Yeux)

Entropie(S/ Yeux)= 5/8 Entropie(Sbleu) + 3/8 Entropie(Sbrun)= 0.607

avec Entropie(Sbleu)= -(3/5)log2(3/5)- (2/5)log2(2/5) (5 exemples répartis en 3+ et 2-)

et Entropie(Sbrun)= -3/3*log2(3/3) =0

(3 exemples de classe-)

(nœud homogène : entropie minimale)

d’où Gain(S, Yeux) =0.954- 0.607 =0.347

On constate que le plus grand gain d'entropie est obtenu sur l'attribut "Cheveux". C'est donc cet attribut qui

est choisi comme test à la racine de l'arbre. Nous obtenons l'arbre partiel suivant :

On voit que mettre l'attribut "Cheveux" à la racine de l'arbre permet d'obtenir 3 branches dont 2 ("Cheveux =

roux" et "Cheveux=noir") produisent des nœuds purs (homogènes). Ces nœuds vérifient donc la condition

d’arrêt et deviennent des feuilles (finaux).

La branche "Cheveux = roux" conduit à la feuille étiquetée "+" et la branche "Cheveux=noir" conduit à la

feuille étiquetée "-". La décision dans les sous-groupes (les feuilles) est celle de la classe la plus fréquente.

Il ne reste à traiter que le noeud présentant un mélange correspondant à la branche "Cheveux=blond". Ce

nœud comporte un ensemble (que nous noterons S2) ayant 2 individus appartenant à la classe "+" et 2

individu de la classe "-".

2/4

Au nœud "Cheveux=blond"

Le processus suivi à la racine pour choisir le meilleur attribut de segmentation est réitéré ici avec la sous base

d’exemples "Cheveux=blond". Cette sous base notée S2, contient 4 lignes des données d'apprentissage, 2

correspondent à la classe "+" et 2 à la classe "-". Ces exemples sont décrits par les 2 attributs restant : Taille et

Yeux.

L'entropie de l'ensemble S2 (au nœud "Cheveux=blond") est donc égale à :

Entropie (S2)= -(2/4)log2(2/4)-(2/4)log2(2/4)=1 (répartition équitable)

Pour connaître quel attribut on doit choisir comme test au niveau du noeud "Cheveux=blond", il faut calculer

le gain d'entropie sur chacun des attributs restants : "Taille" et "Yeux".

Calcul du gain d'entropie sur l'attribut " Taille " :

Gain(S2, Taille) = Entropie(S2) - Entropie(S2/Taille)

Entropie(S2/Taille)= 2/4 Entropie(Spetir) + 2/4 Entropie(Sgrand)=1 (entropie conditionnelle)

avec Entropie(Spetit)= -(1/2)log2(1/2)- (1/2)log2(1/2)=1 (2 exemples répartis en 1+ et 1-)

(répartition équitable : entropie maximale)

et Entropie(Sgrand)= 1 (2 exemples répartis en 1+ et 1-) (répartition équitable : entropie maximale)

d’où Gain(S2, Taille) =1-1=0

Calcul du gain d'entropie sur l'attribut " Yeux " :

Gain(S2, Yeux) = Entropie(S2) - Entropie(S2/ Yeux)

Entropie(S2/ Yeux)= 2/4 Entropie(Sbleu) + 2/4 Entropie(Sbleu)= 0 (entropie conditionnelle)

avec Entropie(Sbleu)= 0 ( 2 exemples répartis en 2+ et 0-) (nœud homogène : entropie minimale)

et Entropie(Sbrun)= 0 ( 2 exemples répartis en 0+ et 2-) (nœud homogène : entropie minimale)

d’où Gain(S2, Yeux) =1-0 =1

On constate que le plus grand gain d'entropie est obtenu sur l'attribut "Yeux". C'est donc cet attribut qui est

choisi comme test du noeud "Cheveux=blond". Nous obtenons l'arbre suivant :

On voit que mettre l'attribut "Yeux" au noeud "Cheveux=blond permet d'obtenir 2 branches qui produisent

des nœuds homogènes. Ces nœuds vérifient donc la condition d’arrêt et deviennent des feuilles (finaux).

La décision dans les sous-groupes (les feuilles) est celle de la classe la plus fréquente.

3/4

2. Rappelez la définition de l’erreur empirique en apprentissage supervisé. Calculez cette

erreur pour l’arbre de décision que vous avez construit.

Echantillon W ={(xi,yi)}1..m de m exemples + classe. Chaque ex. X comporte p attributs

(X1,…, Xp)

xi: iième exemple (ou instance, vecteur)

yi: iième étiquette (ou attribut de décision, classe)

But : trouver le modèle f(x) qui soit le plus proche de y

err

emp

=

1

m

m



=

1

i

(

xf

(

i

)

i

)

y

Taux d’erreur en resubstitution ou erreur empririque : Proportion d’individus mal classés

appliqué sur l’échantillon d’apprentissage.

Sur notre exemple : tous les exemples d’apprentissage sont bien classés par l’arbre construit.

C’est un arbre parfait.

Erremp=0

Cela peut être vu directement sur l’arbre construit : toutes les feuilles sont homogènes.

3. Rappelez la définition de l’erreur de prédiction en apprentissage supervisé. Estimez ce

taux d’erreur sur l'ensemble test T (schéma apprentissage-validation).

num T : Taille Ch : Cheveux Y : Yeux Classe Classe

9 grand

10 Petit

11 Petit

12 Petit

blond

blond

roux

noir

bleu

brun

brun

brun

+

+

+

-

err pred

=

Pr[

xf

)(

y

]

Estimation sur l’ensemble de test : errpred = ¼=25%

prédite par

l’arbre

+

-

+

-

4/4

„

„