Arbres de décision - LOG770 - Systèmes Intelligents

Ce document porte sur les arbres de décision, un sujet du cours LOG770 - Systèmes Intelligents. Il s'agit d'un exercice corrigé qui évalue la compréhension des principes de construction, d'interprétation et d'application des arbres de décision, ainsi que la maîtrise des notions d'entropie, de gain d'information et de variance dans ce contexte.

Exercice 1 : Classification d'un nouvel exemple

La classification d'un nouvel exemple s'effectue en parcourant l'arbre de la racine jusqu'à une feuille selon les résultats des tests.

Pour classifier un nouvel exemple, on commence à la racine de l'arbre et on descend jusqu'à une feuille. À chaque nœud interne, on applique le test associé à ce nœud sur l'exemple. Selon le résultat du test, on suit la branche correspondante vers un sous-nœud. Ce processus est répété jusqu'à atteindre une feuille. Une fois dans la feuille, on attribue à l'exemple la classe la plus fréquente parmi les exemples d'entraînement contenus dans cette feuille.

Réponse : La classification se fait en descendant l'arbre depuis la racine selon les résultats des tests, puis en assignant la classe majoritaire de la feuille atteinte.

Exercice 2 : Construction d'un arbre avec l'algorithme ID3

L'algorithme ID3 sélectionne à chaque étape l'attribut qui offre le gain d'entropie le plus élevé pour diviser l'ensemble d'exemples.

L'algorithme ID3 construit l'arbre en choisissant à chaque nœud le test sur l'attribut qui maximise le gain d'entropie. Le gain d'entropie pour un attribut A est défini par :

Gain(A) = Entropie(S) - ∑_{v ∈ val(A)} (|S_v| / |S|) × Entropie(S_v)

où S est l'ensemble des exemples au nœud, S_v est le sous-ensemble des exemples pour lesquels l'attribut A prend la valeur v, et Entropie(S) est donnée par :

Entropie(S) = - ∑_{i=1 à k} (N_i / |S|) × log₂(N_i / |S|)

avec N_i le nombre d'exemples de classe C_i dans S.

À la racine, les gains d'entropie pour les attributs sont calculés :

Attribut	Gain
Sexe	0,015
Âge	0,507
État civil	0,061
Revenu	0,375

Le plus grand gain est obtenu pour l'attribut Âge, qui est donc choisi pour la première séparation.

Les nœuds Âge < 18 et Âge > 35 sont purs (c'est-à-dire homogènes en termes de classe) et ne nécessitent pas de subdivision supplémentaire. Pour le nœud Âge ∈ [18-35], on calcule les gains d'entropie pour les attributs restants :

Attribut	Gain
Sexe	0,128
État civil	0,020
Revenu	0,592

L'attribut Revenu est choisi pour subdiviser ce nœud.

Les nœuds Revenu = Faible et Revenu = Élevé sont purs, il reste à subdiviser Revenu = Moyen. On calcule les gains pour Sexe et État civil :

Attribut	Gain
Sexe	0,918
État civil	0,252

On choisit Sexe, qui donne le meilleur gain. Les deux sous-nœuds obtenus ont une entropie nulle, donc la construction s'arrête.

L'arbre final est donc :

Âge ?
├─ < 18 : pure
├─ 18-35 ?
│  ├─ Revenu = Faible : pure
│  ├─ Revenu = Moyen ?
│  │  ├─ Sexe = Femme : pure
│  │  └─ Sexe = Homme : pure
│  └─ Revenu = Élevé : pure
└─ > 35 : pure

Pour exprimer la classe des acheteurs potentiels (classe positive), on identifie tous les chemins menant à une feuille positive. La classe s'exprime alors comme une disjonction (OU) de conjonctions (ET) :

AchatOui(x) ⇐ (Age(x) > 35) ∨ (Age(x) ∈ [18-35] ∧ Revenu(x) = Élevé) ∨ (Age(x) ∈ [18-35] ∧ Revenu(x) = Moyen ∧ Sexe(x) = Femme)

Réponse : L'attribut Âge est choisi en premier, suivi de Revenu et Sexe selon les gains d'entropie, ce qui conduit à l'arbre décrit ci-dessus et à l'expression booléenne de la classe positive.

Exercice 3 : Optimalité de l'algorithme ID3

L'algorithme ID3 n'offre pas la garantie de trouver l'arbre de décision globalement optimal en raison de sa démarche gloutonne.

La réponse est non. L'algorithme ID3 est une méthode gloutonne : à chaque nœud, il choisit le test qui maximise localement le gain d'entropie sans revenir sur ses choix précédents. Cela signifie qu'il peut passer à côté de combinaisons d'attributs qui, prises ensemble, seraient meilleures, mais qui ne sont pas optimales individuellement. Par conséquent, ID3 ne garantit pas de trouver l'arbre optimal global.

Réponse : Non, ID3 est une méthode gloutonne qui ne considère pas les combinaisons d'attributs et peut donc ne pas trouver l'arbre optimal.

Exercice 4 : Fonctionnement des arbres de régression

Les arbres de régression mesurent l'homogénéité des nœuds au moyen de la variance des valeurs numériques de sortie plutôt que de l'entropie.

Dans les arbres de régression, la construction est similaire à celle des arbres de classification, mais au lieu d'utiliser l'entropie pour mesurer la pureté d'un nœud, on utilise la variance des valeurs de sortie des exemples dans chaque sous-nœud.

Soit S_v le sous-nœud contenant les exemples pour lesquels l'attribut A prend la valeur v, et x_v la moyenne des valeurs de sortie dans S_v. Le critère pour choisir un test est de minimiser la variance totale :

∑_{v ∈ val(A)} ∑_{xt ∈ Sv} (x_t − x_v)²

Une fois l'arbre construit, pour prédire la valeur de sortie d'un nouvel exemple x, on descend dans l'arbre selon les tests jusqu'à une feuille, puis on prédit la valeur moyenne des exemples d'entraînement dans cette feuille.

Réponse : Les arbres de régression utilisent la variance comme critère de pureté et prédisent la moyenne des valeurs dans la feuille atteinte.

Méthode

La résolution de ces exercices requiert la présentation explicite des étapes de calcul d'entropie et de variance.

Ce devoir récompense la compréhension précise des notions d'entropie, de gain d'information, et de variance dans le contexte des arbres de décision. Il faut montrer clairement les calculs intermédiaires, notamment le calcul des gains d'entropie à chaque étape, et expliquer le choix des attributs en fonction de ces gains.

Il est important de respecter la définition donnée dans l'énoncé pour l'entropie et le gain, sans utiliser d'autres formules ou notations. La rigueur dans l'explication de la méthode gloutonne d'ID3 et dans la distinction entre arbres de classification et de régression est également essentielle.

Les erreurs fréquentes punies sont :

• Ne pas montrer les calculs de gain d'entropie ou de variance.
• Confondre la méthode de classification et celle de régression.
• Omettre d'expliquer pourquoi certains nœuds sont purs et ne sont pas subdivisés.
• Ne pas justifier le choix des attributs à chaque étape.

En résumé, ce travail valorise la clarté, la précision des calculs et la compréhension des principes fondamentaux des arbres de décision.