Exploration de données - Induction d'arbre de décision

Un arbre de décision est une structure qui comprend un nœud racine, des branches et des nœuds feuilles. Chaque nœud interne indique un test sur un attribut, chaque branche indique le résultat d'un test et chaque nœud feuille détient une étiquette de classe. Le nœud le plus haut de l'arborescence est le nœud racine.

L'arbre de décision suivant concerne le concept buy_computer qui indique si un client d'une entreprise est susceptible d'acheter un ordinateur ou non. Chaque nœud interne représente un test sur un attribut. Chaque nœud feuille représente une classe.

Les avantages d'avoir un arbre de décision sont les suivants -

Il ne nécessite aucune connaissance du domaine.
C'est facile à comprendre.
Les étapes d'apprentissage et de classification d'un arbre de décision sont simples et rapides.

Algorithme d'induction d'arbre de décision

Un chercheur en machine nommé J. Ross Quinlan en 1980 a développé un algorithme d'arbre de décision connu sous le nom d'ID3 (Iterative Dichotomiser). Plus tard, il a présenté C4.5, qui était le successeur d'ID3. ID3 et C4.5 adoptent une approche gourmande. Dans cet algorithme, il n'y a pas de retour arrière; les arbres sont construits selon une méthode de division et de conquête récursive descendante.

Generating a decision tree form training tuples of data partition D
Algorithm : Generate_decision_tree

Input:
Data partition, D, which is a set of training tuples 
and their associated class labels.
attribute_list, the set of candidate attributes.
Attribute selection method, a procedure to determine the
splitting criterion that best partitions that the data 
tuples into individual classes. This criterion includes a 
splitting_attribute and either a splitting point or splitting subset.

Output:
 A Decision Tree

Method
create a node N;

if tuples in D are all of the same class, C then
   return N as leaf node labeled with class C;
   
if attribute_list is empty then
   return N as leaf node with labeled 
   with majority class in D;|| majority voting
   
apply attribute_selection_method(D, attribute_list) 
to find the best splitting_criterion;
label node N with splitting_criterion;

if splitting_attribute is discrete-valued and
   multiway splits allowed then  // no restricted to binary trees

attribute_list = splitting attribute; // remove splitting attribute
for each outcome j of splitting criterion

   // partition the tuples and grow subtrees for each partition
   let Dj be the set of data tuples in D satisfying outcome j; // a partition
   
   if Dj is empty then
      attach a leaf labeled with the majority 
      class in D to node N;
   else 
      attach the node returned by Generate 
      decision tree(Dj, attribute list) to node N;
   end for
return N;

Élagage des arbres

L'élagage des arbres est effectué afin d'éliminer les anomalies dans les données d'entraînement dues au bruit ou aux valeurs aberrantes. Les arbres taillés sont plus petits et moins complexes.

Approches d'élagage des arbres

Il existe deux approches pour élaguer un arbre -

Pre-pruning - L'arbre est élagué en arrêtant sa construction tôt.
Post-pruning - Cette approche supprime un sous-arbre d'un arbre complètement développé.

Complexité des coûts

La complexité des coûts est mesurée par les deux paramètres suivants -

Nombre de feuilles dans l'arbre, et
Taux d'erreur de l'arbre.