LOG770 - Systèmes Intelligents
LOG770 - Systèmes Intelligents
Programming, Decision Trees, Entropy · exam
Fiche de révisionCorrigé
Rédigée à partir de ce document, puis vérifiée avant publication.
Pour classifier un nouvel exemple à l'aide d'un arbre de décision, on traverse l'arbre depuis sa racine jusqu'à l'une de ses feuilles. À chaque nœud interne rencontré lors de la descente, on emprunte la branche qui correspond au résultat du test évalué à ce nœud.
Une fois arrivé dans une feuille, on assigne à l'exemple la classe qui est la plus fréquente parmi les exemples d'entraînement contenus dans cette feuille.
L'algorithme ID3 construit l'arbre en choisissant, pour chaque nœud, le test sur l'attribut qui mène au meilleur gain d'entropie.
Le document définit les formules suivantes :
Gain(A) = Entropie(S) - Σ (pour v ∈ val(A)) de ( |Sv| / |S| ) × Entropie(Sv), où |S| est le nombre total d'exemples dans S, et Sv représente un nœud contenant les exemples de S dont la valeur pour l'attribut A vaut v.
L'entropie d'un nœud S est calculée ainsi :
Entropie(S) = Σ (pour i=1 à k) de - (Ni / |S|) × log2(Ni / |S|), où Ni est le nombre d'exemples de S appartenant à la classe Ci.
À la racine (où l'entropie initiale du système est de 1), nous évaluons les gains d'entropie pour les quatre attributs :
| Attribut | Calcul du gain | Gain |
|---|---|---|
| Sexe | 1 - [ (7/14)×(0.985) + (7/14)×(0.985) ] | 0.015 |
| Âge | 1 - [ (3/14)×(0) + (7/14)×(0.985) + (4/14)×(0) ] | 0.507 |
| État civil | 1 - [ (8/14)×(0.954) + (6/14)×(0.918) ] | 0.061 |
| Revenu | 1 - [ (4/14)×(0.811) + (6/14)×(0.918) + (4/14)×(0) ] | 0.375 |
Le plus gros gain provient de l'attribut Âge. On choisit donc celui-ci pour séparer les exemples initiaux.
Suite à cette séparation, les nœuds "Âge < 18" et "Âge > 35" ont une entropie de 0. Ils sont purs et nous n'avons pas besoin de les subdiviser.
En revanche, le nœud "Âge = 18 - 35" nécessite une subdivision. Son entropie locale est de 0.985. Nous testons le gain d'entropie pour les attributs restants sur ce sous-ensemble :
| Attribut | Calcul du gain | Gain |
|---|---|---|
| Sexe | 0.985 - [ (4/7)×(0.811) + (3/7)×(0.918) ] | 0.128 |
| État civil | 0.985 - [ (3/7)×(0.918) + (4/7)×(1) ] | 0.020 |
| Revenu | 0.985 - [ (2/7)×(0) + (3/7)×(0.918) + (2/7)×(0) ] | 0.592 |
On choisit donc l'attribut Revenu pour subdiviser ces exemples, car il offre le meilleur gain (0.592).
Encore une fois, les nœuds "Revenu = Faible" et "Revenu = Élevé" s'avèrent purs. Il ne reste que le nœud "Revenu = Moyen" à subdiviser, dont l'entropie est de 0.918 :
| Attribut | Calcul du gain | Gain |
|---|---|---|
| Sexe | 0.918 - [ (2/3)×(0) + (1/3)×(0) ] | 0.918 |
| État civil | 0.918 - [ (1/3)×(0) + (2/3)×(1) ] | 0.252 |
L'attribut Sexe donne le meilleur gain d'entropie (0.918) et est choisi. Les deux sous-nœuds résultants ont alors une entropie de 0. L'arbre est complètement pur, la construction s'arrête.
Pour exprimer la classe des acheteurs potentiels, on identifie tous les chemins depuis la racine jusqu'aux feuilles contenant des exemples positifs (Oui). La classe s'exprime comme une disjonction (OU logique, noté ∨) de conjonctions (ET logique, noté ∧) :
AchatOui(x) ⇐ (Âge(x) > 35) ∨ (Âge(x) ∈ [18 - 35] ∧ Revenu(x) = Élevé) ∨ (Âge(x) ∈ [18 - 35] ∧ Revenu(x) = Moyen ∧ Sexe = Femme)
L'algorithme ID3 ne garantit pas de trouver l'arbre optimal. Il s'agit d'une méthode gloutonne (greedy).
À chaque étape, on choisit le meilleur test pour le nœud courant sans jamais revenir sur nos choix précédents. Par conséquent, il est possible que deux tests soient mauvais s'ils sont évalués individuellement, mais s'avèrent très bons s'ils sont combinés. Ces combinaisons ne seront jamais considérées par l'approche purement descendante de l'algorithme ID3.
Dans les arbres de régression, comme pour la classification, l'objectif est de choisir pour un nœud le test menant à la partition la plus pure. Toutefois, au lieu d'utiliser l'entropie (utilisée pour des classes discrètes), 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 définie par :
Σ (pour v ∈ val(A)) de Σ (pour xt ∈ Sv) de (xt - xv)², où xv est la moyenne des valeurs des exemples de Sv.
Pour prédire la valeur de sortie d'un nouvel exemple x, on effectue la même traversée de l'arbre depuis la racine jusqu'à une feuille, en suivant les branches validant les tests. La prédiction finale pour x correspond à la sortie moyenne des exemples d'entraînement contenus dans cette feuille.
Pour aborder ce type d'examen sur les arbres de décision, voici la stratégie à adopter :