Arbre de décision : construction, classification et élagage

Résumé du document

Arbre de décision est une technique de classification en apprentissage supervisé,
Utilisation dans le domaine de l'intelligence artificielle.

- L'arbre commence à un noeud représentant toutes les données.
. Si les objets sont de la même classe, alors le noeud devient une feuille libellée par le nom de la classe.
. Sinon, sélectionner les attributs qui séparent le mieux les objets en classes homogènes.
. La récursion s'arrête quand au moins l'un des critères d'arrêt est vérifié.

- Recherche à chaque niveau, l'attribut le plus discriminant.
- Partition (données T)
. Si tous les éléments de T sont dans la même classe alors retour ;
. Pour chaque attribut A, évaluer la qualité du partitionnement sur A ;
. Utiliser le meilleur partitionnement pour diviser T en T1, T2, ... Tk ;
. Pour i = 1 à k faire Partition(Ti) ;

- Nombre de bits nécessaires pour distinguer chaque boule parmi N :
. P bits permettent de coder 2P informations.
. log2(N) bits permettent de coder N informations.

- Si je tire une boule (parmi N boules) et que je ne connais que sa couleur (par exemple elle est rouge), l'information acquise sera :
log2(N) bits - log2(Nr) bits

(...)

- Si je tire une boule au hasard et qu'on me donne sa couleur, l'information acquise sera :
Prob(Bleue) (log2(N) - log2(Nb)) + Prob(Rouge)(log2(N)- log2(Nr)).

(...)

- Lorsqu'un attribut a plusieurs valeurs possibles, son gain peut être très élevé, car il classifie parfaitement les objets.
- Par contre, ça peut générer un arbre de décision d'une profondeur de 1 (ou faible) qui ne sera pas très bon pour les instances futures.

(...)

Extraits

[...] Ensemble d'apprentissage Attributs Revenu Propriété Crédit non Classes remboursé Elevé Supérieur Non C1 Elevé Supérieur Oui C2 Elevé Supérieur Non C1 Elevé Inférieur Oui C2 Moyen Supérieur Non C1 Moyen Supérieur Oui C2 Moyen Inférieur Non C2 Moyen Inférieur Oui C2 Faible Inférieur Non C3 Faible Inférieur Oui C3 Valeurs des attributs BOUCHAMIA BILEL < number > < number > Arbre de décision Propriété Elevé Crédit non remboursé Oui Non Revenu Inférieur C2 C1 C3 C2 Supérieur Moyen Faible C2 < number > Construction d'un arbre de décision Problème Apprendre un arbre de décision à partir d'un ensemble d'apprentissage. Objectif Être efficace en généralisation Être capable de classer correctement un nouvel objet (exemple). < number > Un algorithme horrible Générer tous les arbres de décision possibles. Tester combien chaque arbre décrit l'ensemble d'apprentissage. Choisir le meilleur arbre de décision. Trop coûteux voire impossible < number > Un meilleur Algorithme Choisir le meilleur attribut. Partitionner l'ensemble d'apprentissage. [...]

[...] Conclusion et perspectives Arbres de décision et élagage (Mingers, 1989). Arbres de décision et Bagging (Quinlan, 1997). Arbres de décision et Boosting (Quinlan, 1997) . < number > Conclusion et perspectives Arbres de décision et théories de l'incertain. Arbres de décision porbabilistes (Quinlan, 1990). Arbres de décision crédibilistes (Elouedi, Mellouli, Smets Denoeux, M. Skarstein-Bjanger, 2000). Arbres de décision possibilistes (Ben Amor, BenFerhat, Elouedi Jenhani et al. [...]

[...] Ce noeud devient une feuille et on lui attribue la valeur de classification qui revient le plus souvent. Des noeuds sont enlevés seulement si l'arbre résultant n'est pas pire que l'arbre initial sur les exemples de validation. On continue tant que l'arbre résultant offre de meilleurs résultats sur les exemples de validation. Réduire l'arbre en enlevant des branches qui auraient été ajoutées par une erreur dans les objets d'apprentissage. < number > Comment élaguer ? Pré-élagage (pre-pruning) Arrêter le développement d'un noeud. [...]

[...] Utgoff “Incremental induction of decision trees”, Machine Learning 161- Y. Yuan, M. J. Shaw “Induction of fuzzy decision trees”, Fuzzy sets and Systems 125-139, 1995. [...]

[...] On sélectionne l'attribut offrant le plus de ratio de gain. T Split Info(T, = -  Ti log2 iDA T Ti Gain Ratio(T, = Gain(T, Split Info(T, Proportion d'information génerée par T et utile pour la classification < number > Stratégie de partitionnement Pour chaque valeur de l'attribut, on va associer une branche dans l'arbre. Problème avec les attributs continus. Découper en sous-ensembles ordonnés < number > Quand s'arrêter ? Si tous les objets appartiennent à la même classe. S'il n'y a plus d'attributs à tester. [...]