Généralités sur l'apprentissage des arbres de décision

Idée centrale : Diviser récursivement les exemples de l'ensemble d'apprentissage par des tests définis à l'aide des attributs jusqu'à ce que l'on obtienne des sous-ensembles d'exemples ne contenant (presque) que des exemples appartenant tous à une même classe.

Dans toutes les méthodes, on trouve les trois opérateurs suivants :

1. Décider si un noeud est terminal. Par exemple : tous les exemples sont dans la même classe, il y a moins d'un certain nombre d'erreurs, ...
2. Sélectionner un test à associer à un noeud. Par exemple : aléatoirement, utiliser des critères statistiques, ...
3. Affecter une classe à une feuille. On attribue la classe majoritaire sauf dans le cas où l'on utilise des fonctions coût ou risque.

On peut alors calculer un arbre de décision dont l'erreur apparente est faible, voire nulle. Un arbre de décision parfait est un arbre de décision tel que tous les exemples de l'ensemble d'apprentissage soient correctement classifiés. Un tel arbre n'existe pas toujours (s'il existe deux exemples tels que à deux descriptions identiques correspondent deux classes différentes). Le meilleur arbre de décision est le plus petit arbre de décision parfait, une mesure de complexité étant choisie. Mais, on retrouve les problèmes signalés dans le chapitre précédent, c'est à dire,

le meilleur arbre de décision n'existe pas toujours, trouver le meilleur arbre de décision est, en général, un problème NP-complet, et enfin, l'erreur apparente est une vision très optimiste de l'erreur réelle.

  
Figure 2.2: Erreur réelle et erreur apparente pour des données réelles de reconnaissance de caractères (Breiman et al. [84])

Donc il faut faire le choix d'une mesure de complexité et rechercher le meilleur compromis complexité / adéquation aux données. Les méthodes procèdent toujours en deux phases. Dans une première phase, on calcule récursivement, après avoir défini les trois opérateurs ci-dessous, un ``bon'' arbre de décision (erreur apparente faible). Dans une seconde phase, on élague l'arbre obtenu pour essayer de faire diminuer l'erreur réelle. On procède en deux phases car il n'existe aucune heuristique satisfaisante permettant d'arrêter au ``bon'' moment la croissance de l'arbre de décision. En effet, il se peut que l'on choisisse un test qui fasse augmenter temporairement l'erreur mais qui permettra, par la suite, de faire diminuer nettement cette erreur (voir exercice 11). De plus, le risque d'arrêter trop tôt la croissance de l'arbre est plus important que de l'arrêter trop tard (voir Figure 2.2).