LOG770 - Systèmes Intelligents

Processus de classification

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.

Construction de l'arbre avec l'algorithme ID3

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.

Choix de l'attribut à la racine

À 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.

Premier niveau de séparation (Âge)

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).

Deuxième niveau de séparation (Revenu)

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.

Règle logique de classification

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)

Limites de l'algorithme ID3

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.

Les arbres de régression

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.

Méthode

Pour aborder ce type d'examen sur les arbres de décision, voici la stratégie à adopter :

1. Calcul des métriques de pureté : Maîtrisez parfaitement le calcul de l'entropie. Procédez étape par étape, sans omettre le calcul de l'entropie globale du nœud parent avant d'évaluer le gain d'entropie des attributs candidats.
2. Identification des nœuds purs : Dès qu'un nœud est pur (entropie de 0), il devient une feuille. Arrêtez de le subdiviser, cela vous fait gagner un temps précieux et évite les erreurs.
3. Mise à jour des échantillons : Lors d'une subdivision (par exemple "Âge = 18-35"), assurez-vous de recalculer vos fractions et vos entropies uniquement sur les données appartenant à cette branche (ici, 7 exemples sur 14), et non sur l'ensemble du jeu de données initial.
4. Distinction Classification / Régression : Rappelez-vous que la classification sépare des catégories en minimisant l'entropie, tandis que la régression prédit des valeurs continues en minimisant la variance.