D ÉPARTEMENT DE G ÉNIE LOGICIEL ET DES TI
LOG770 - SYST ÈMES INTELLIGENTS
ÉT É 2011
Chapitre 9
Arbres de décision
Solutions
1. Pour classifier un nouvel exemple, on traverse l’arbre depuis la racine jusqu’à une feuille.
Pour chaque nœud interne rencontré, on emprunte la branche correspondant au résultat du
test de ce nœud. Une fois dans la feuille, on assigne l’exemple à la classe la plus fréquente
des exemples d’entraˆınement contenus dans cette feuille.
2. L’algorithme ID3 construit en choisissant pour chaque nœud, un test sur l’attribut menant au
meilleur gain d’entropie :
Gain(A) = Entropie(S) −
(cid:88)
v∈val(A)
|Sv|
|S|
Entropie(Sv),
où |S| est le nombre d’exemples dans S, et Sv est un nœud contenant les exemples de S dont
la valeur pour l’attribut A vaut v. Rappelons que l’entropie d’un nœud S vaut :
Entropie(S) =
k
(cid:88)
i=1
−
Ni
|S|
log2
Ni
Publicité
|S|
,
(1)
Ni étant le nombre d’exemples de S ayant la classe Ci.
À la racine, nous avons les gains d’entropie suivants :
Attribut
Sexe
Âge
État civil
Revenu
Gain
= 0.015
1 − [(7/14)(0.985) + (7/14)(0.985)]
= 0.507
1 − [(3/14)(0) + (7/14)(0.985) + (4/14)(0)]
1 − [(8/14)(0.954) + (6/14)(0.918)]
= 0.061
1 − [(4/14)(0.811) + (6/14)(0.918) + (4/14)(0)] = 0.375
Le plus gros gain provient de l’attribut Âge et on choisit celui-ci pour séparer les exemples :
1
Les nœuds Âge < 18 et Âge > 35 sont purs et nous n’avons pas besoin de les subdiviser.
Par ailleurs, pour le nœud Âge = 18 − 15, nous testons le gain d’entropie pour les attributs
restants :
Attribut
Sexe
État civil
Revenu
Gain
= 0.128
Publicité
0.985 − [(4/7)(0.811) + (3/7)(0.918)]
0.985 − [(3/7)(0.918) + (4/7)(1)]
= 0.020
0.985 − [(2/7)(0) + (3/7)(0.918) + (2/7)(0)] = 0.592
On choisit donc l’attribut Revenu pour subdiviser les exemples :
Encore une fois, les nœuds Revenu = Faible et Revenu = Élevé sont purs, il ne reste que le
nœud Revenu = Moyen à subdiviser :
Attribut
Sexe
État civil
Gain
0.918 − [(2/3)(0) + (1/3)(0)] = 0.918
0.918 − [(1/3)(0) + (2/3)(1)] = 0.252
L’attribut Sexe donne le meilleur gain d’entropie et on choisit celui-ci pour séparer les
exemples. Enfin, comme les deux sous-nœud résultant ont une entropie de 0, on arrête la
construction et on obtient l’arbre suivant :
2
Âge ?2,4,10< 183,9,11,12> 3518-35NonOui1,5,6,7,8,13,14?Âge ?Revenu ?2,4,10< 183,9,11,12> 3518-35FaibleMoyenÉlevé7,136,8NonNonOuiOui1,5,14?Pour exprimer la classe des acheteurs potentiels, on identifie tous les chemins depuis la
racine de l’arbre jusqu’à une feuille de l’arbre contenant des exemples positifs. La classe des
exemples positifs s’exprime ensuite comme une disjonction (OU - ∨) de conjonctions (ET -
∧) pour chaque chemin :
AchatOui(x) ⇐
(cid:16)
(cid:16)
Age(x) > 35
(cid:17)
(cid:16)
∨
Age(x) ∈ [18 − 35] ∧ Revenu(x) = Eleve
Publicité
(cid:17)
(cid:17)
∨
Age(x) ∈ [18 − 35] ∧ Revenu(x) = M oyen ∧ Sexe = F emme
.
3. Non. Il s’agˆıt d’une méthode gloutonne où l’on choisit le meilleur test pour chaque nœud
sans jamais revenir sur nos choix précédents. Ainsi, il est possible que deux tests soient
mauvais individuellement, mais très bon si combinés. Dans l’algorithme ID3, ces combinai-
sons ne seront pas considérées.
4. Dans les arbres de régression, comme pour la classification, on choisit pour un nœud le test
menant à la partition la plus pure des exemples de ce nœud. Cependant, au lieu d’utiliser
l’entropie, on utilise la variance de la valeur de sortie des exemples dans chaque sous-nœud.
Soit Sv le sous-nœud contenant les exemples ayant la valeur v pour un attribut A, on cherche
le test minimisant la variance totale :
(cid:88)
(cid:88)
(xt − xv)2,
v∈val(A)
xt∈Sv
où xv est la moyenne des exemples de Sv.
Pour obtenir la valeur de sortie d’un nouvel exemple x, on traverse l’arbre de décision de-
puis la racine jusqu’à une feuille en suivant les branches correspondant aux réponses des
tests rencontrés. Ensuite, on prédit la valeur de x comme la sortie moyenne des exemples
d’entraˆınement contenus dans cette feuille.
3
Âge ?Revenu ?Sexe ?2,4,10< 183,9,11,12> 3518-35FaibleMoyenÉlevé7,136,81,5HommeFemme14NonNonNonOuiOuiOui