DÉPARTEMENT DE GENIE´ LOGICIEL ET DES TI LOG770 - SYSTEMES` INTELLIGENTS ÉTE´ 2011

Chapitre 9 Arbres de décision Solutions

1. Pour classifier un nouvel exemple, on traverse l’arbre depuis la racine jusqu’a 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’exemplea 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_ ) _−_

v∈val ( A )

|Sv|

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

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 :

Ni

(1)

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

Entropie( S ) =

k

• −

|S

i =1

Ni étant le nombre d’exemples de S ayant la classe Ci . À la racine, nous avons les gains d’entropie suivants :

Attribut	Gain
Sexe Âge État 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éparer 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 État 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é [´] sont purs, il ne reste que le

Moyen à subd	diviser :
Attribut	Gain
Sexe État 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é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

Non

Oui

Oui

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**_ ) _⇐_ _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éthode gloutonne ou 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 tres bon si combinés. Dans l’algorithme ID3, ces combinaisons 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 :

 - - _ _ [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écision depuis la racine jusqu’a 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