Un deuxième algorithme : C4.5 (Quinlan 93)

On suppose toujours que 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). Pour les attributs continus, on utilise des heuristiques qui permettent de les discrétiser. On utilise pour celà des critères statistiques qui permettent d'atteindre les deux objectifs suivants : un nombre de classes pas trop important et une bonne répartition entre les différentes classes. On peut par exemple utiliser la fonction entropie pour atteindre ces objectifs. Nous supposons maintenant que les attributs ont été discrétisés.

Nous supposons prédéfini un ensemble de tests n-aires. Pour définir l'algorithme, nous allons définir les trois opérateurs utilisés par l'algorithme C4.5 pour calculer un bon arbre de décision (phase d'expansion), puis nous verrons la phase d'élagage. On suppose disposer d'un ensemble d'apprentissage A.

• Phase d'expansion. Construction de l'arbre de décision en divisant récursivement l'ensemble d'apprentissage A. On utilise la fonction entropie.
  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 n-aire. Si ce test devient l'étiquette du noeud à la position p, alors on appelle la proportion d'éléments de l'ensemble des exemples associés à p qui vont sur le noeud en position pi (i ème fils du noeud en position p). Le gain associé au choix du test T en position p est alors :
     
     où i est la fonction entropie. En position p (non maximale), on choisit le test qui maximise la quantité gain(p,T).
  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. C4.5 utilise l'ensemble d'apprentissage pour élaguer l'arbre obtenu. Le critère d'élagage est basé sur une heuristique permettant d'estimer l'erreur réelle sur un sous-arbre donné. Bien qu'il semble peu pertinent d'estimer l'erreur réelle sur l'ensemble d'apprentissage (problème du biais inductif), il semble que la méthode donne des résultats corrects. Citons Quinlan :

  Although this method does have the subtle flaw of ``indirecly training on test cases'' it performs quite well on large samples with at least 1000 test cases. With fewer cases, the risks of training on the test cases is greater.

  Une autre heuristique est proposée par C4.5. On construit le système à base de règles associé à l'arbre de décision produit en sortie de la phase d'expansion. On choisit alors un codage qui permet de coder le système et les exceptions (exemples mal classifiés par les règles). On choisit alors le système, obtenu en supprimant une règle, dont le codage est minimal en taille si le codage diminue en taille. On applique ce procédé de façon itérative tant que la taille des codages diminue. Cette méthode est une application du principe MDL (Minimum Description Length) qui consiste à choisir parmi plusieurs théories celle dont le codage (théorie plus exceptions) est minimal.