Un premier algorithme : CART (Breiman et al 84)

Cette méthode permet d'inférer des arbres de décision binaires, i.e. tous les tests étiquetant les noeuds de décision sont binaires. Le langage de représentation est constitué d'un certain nombre d'attributs. Ces attributs peuvent être binaires, qualitatifs (à valeurs dans un ensemble fini de modalités) ou continus (à valeurs réelles). Le nombre de tests à explorer va dépendre de la nature des attributs. A un attribut binaire correspond un test binaire. A un attribut qualitatif ayant n modalités, on peut associer autant de tests qu'il y a de partitions en deux classes, soit tests binaires possibles. Enfin, dans le cas d'attributs continus, il y a une infinité de tests envisageables. Dans ce cas, on découpe l'ensemble des valeurs possibles en segments, ce découpage peut être fait par un expert ou fait de façon automatique.

Nous supposons prédéfini un ensemble de tests binaires. Pour définir l'algorithme, nous allons définir les trois opérateurs utilisés par la méthode CART pour calculer un bon arbre de décision (phase d'expansion), puis nous verrons la phase d'élagage. Nous nous plaçons dans le cas d'un échantillon S ``assez grand'' qui peut être découpé en un ensemble d'apprentissage A et un ensemble Test T.

• Phase d'expansion. Construction de l'arbre de décision en divisant récursivement l'ensemble d'apprentissage A. On utilise la fonction de Gini (ou indice d'impureté de Gini) défini précédemment. En remarquant que , on peut démontrer que :
  
  où p est une position.
  1. Décider si un noeud est terminal. Un noeud p est terminal si ou , où et sont des paramètres à fixer.
  2. Sélectionner un test à associer à un noeud. Soit p une position et soit T un test. Si ce test devient l'étiquette du noeud à la position p, alors on appelle (respectivement ) la proportion d'éléments de l'ensemble des exemples associés à p qui vont sur le noeud en position p1 (respectivement p2). La réduction d'impureté définie par le test T est alors :
     
     En position p (non maximale), on choisit le test qui maximise la quantité .
  3. Affecter une classe à une feuille. On attribue la classe majoritaire.

  Soit t l'arbre obtenu en sortie de la phase d'expansion.

• Phase d'élagage. L'estimation de l'erreur réelle est l'erreur apparente sur l'ensemble Test T. Un élagué de t est obtenu en remplaçant un sous-arbre de t par une feuille. Une première solution serait d'estimer l'erreur réelle pour tous les élagués de t. Cette méthode est trop couteuse en temps de calcul. On va donc utiliser une heuristique permettant de limiter le nombre d'élagués de t sur lesquels on va estimer l'erreur réelle.
  1. construction de la suite des arbres. On construit une suite telle que soit l'arbre obtenu à la fin de la phase d'expansion, pour tout i, est un élagué de et le dernier arbre de la suite est réduit à une feuille. Il nous faut définir le procédé de construction de à partir de . Pour toute position p de , on note le sous-arbre de en position p. On calcule la quantité
     
     où est la variation d'erreur apparente mesurée sur l'ensemble d'apprentissage A lorsqu'on élague t en position p et est la taille de . On peut remarquer que
     
     où N(p) est le cardinal de l'ensemble des exemples de A associé à la position p de , MC(p) est le nombre d'éléments de A mal classés à la position p lorsqu'on élague en position p et est le nombre d'éléments de A associés à la position p de mal classés par .

     On considère alors la position p pour laquelle g(p) est minimale et est l'élagué de en position p.

  2. choix final. On calcule pour chaque arbre de la suite construite au point précédent l'erreur apparente sur l'ensemble Test T. Cette valeur est prise comme estimation de l'erreur réelle. On retourne donc l'arbre qui minimise l'erreur apparente sur T.