D´EPARTEMENT DE GENIE´ LOGICIEL ET DES TI LOG770 - SYSTEMES` INTELLIGENTS ´ETE´ 2011

Chapitre 9 Arbres de d´ecision Solutions

1. Pour classifier un nouvel exemple, on traverse l’arbre depuis la racine jusqu’a une feuille. Pour chaque nœud interne rencontr´e, on emprunte la branche correspondant au r´esultat du test de ce nœud. Une fois dans la feuille, on assigne l’exemplea la classe la plus fr´equente 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_ ) _−_

v∈val ( A )

|Sv|

|S| [(] [)] [,]

o`u |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 :

Ni

(1)

|S| [2] |S| [,]

Entropie( S ) =

k

• −

|S

i =1

Ni ´etant le nombre d’exemples de S ayant la classe Ci . `A la racine, nous avons les gains d’entropie suivants :

Attribut	Gain
Sexe ˆAge ´Etat civil Revenu	1_ −[(7/14)(0.985) + (7/14)(0.985)] = 0.015 1 −[(3/14)(0) + (7/14)(0.985) + (4/14)(0)] = 0.507 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 Age [ˆ] et on choisit celui-ci pour s´eparer les exemples :

1

?

Les nœuds Age [ˆ] < 18 et Age [ˆ] > 35 sont purs et nous n’avons pas besoin de les subdiviser. Par ailleurs, pour le nœud Age [ˆ] = 18 − 15, nous testons le gain d’entropie pour les attributs restants :

Attribut	Gain
Sexe ´Etat civil Revenu	0.985_ −[(4/7)(0.811) + (3/7)(0.918)] = 0.128 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 :

Non

Oui

Oui

?

Encore une fois, les nœuds Revenu = Faible et Revenu = Elev´e [´] sont purs, il ne reste que le

Moyen `a subd	diviser :
Attribut	Gain
Sexe ´Etat civil	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´eparer les exemples. Enfin, comme les deux sous-nœud r´esultant ont une entropie de 0, on arrˆete la construction et on obtient l’arbre suivant :

2

Non

Oui

Oui

Pour exprimer la classe des acheteurs potentiels, on identifie tous les chemins depuis la racine de l’arbre jusqu’`a 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**_ ) _⇐_ _Age_ ( _**x**_ ) _>_ 35 _∨_ _Age_ ( _**x**_ ) _∈_ [18 _−_ 35] _∧_ _Revenu_ ( _**x**_ ) = _Eleve_ _∨_

 - _Age_ ( _**x**_ ) _∈_ [18 _−_ 35] _∧_ _Revenu_ ( _**x**_ ) = _Moyen_ _∧_ _Sexe_ = _Femme_ _._

3. Non. Il s’agˆıt d’une m´ethode gloutonne ou l’on choisit le meilleur test pour chaque nœud sans jamais revenir sur nos choix pr´ec´edents. Ainsi, il est possible que deux tests soient mauvais individuellement, mais tres bon si combin´es. Dans l’algorithme ID3, ces combinaisons ne seront pas consid´er´ees.

4. Dans les arbres de r´egression, comme pour la classification, on choisit pour un nœud le test menant `a 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 :

 - - _ _ [2]

v∈val ( A )

( x − x v ) [2] ,

x ∈Sv

ou _**x**_ _v_ est la moyenne des exemples de _Sv_ . Pour obtenir la valeur de sortie d’un nouvel exemple _**x**_, on traverse l’arbre de d´ecision depuis la racine jusqu’a une feuille en suivant les branches correspondant aux r´eponses des tests rencontr´es. Ensuite, on pr´edit la valeur de x comme la sortie moyenne des exemples d’entraˆınement contenus dans cette feuille.

3