Conclusion

Les méthodes à base d'arbres de décision les plus importantes sont :

• CART développée par Breiman et al. en 84. Cette méthode, développée par des statisticiens, construit des arbres de décision binaires. Cette méthode peut être étendue pour traiter le cas d'attributs continus. Le critère de Gini est utilisé pour associer un test à un noeud. L'élagage de l'arbre se fait par estimation de l'erreur réelle en utilisant un ensemble Test. La phase d'élagage peut être modifiée pour le cas d'échantillons de plus petite taille, on utilise alors la validation croisée.
• ID3 développée par Quinlan en 83, améliorée en 93 par une nouvelle version C4.5 (voir [13]). On ne se restreint pas à des attributs binaires. L'association d'un test à un noeud se fait en utilisant la fonction d'entropie. La méthode peut prendre en compte le cas où les valeurs de certains attributs sont non spécifiées. Elle prend également en compte le problème des attributs continus (on utilise la fonction entropie pour choisir un bon découpage en intervalles). Le choix du test associé à un noeud se fait à l'aide de la fonction gain basée sur la fonction entropie. Cette fonction gain utilisée par ID3 présente le défaut de privilégier les attributs ayant un grand nombre de modalités (voir exercice 10). C4.5 utilise en fait une version modifiée de cette fonction dans laquelle le nombre de modalités est pris en compte. La phase d'élagage est remplaçée par une simplification du système à base de règles qui correspond à l'arbre de décision obtenu à la fin de la première phase.
• Signalons une dernière méthode basée sur le principe MDL (Minimum Description Length) de Rissanen. Cette méthode a été développée par Quinlan et Rivest [15] en 87. Elle construit l'arbre de décision qui permet de coder de la façon la plus courte possible l'échantillon (on code l'arbre et les exceptions). Cette méthode permet de faire des ponts intéressants entre codages et probabilités et a des performances satisfaisantes.

Les arbres de décision fournissent des méthodes effectives qui obtiennent de bons résultats dans la pratique. Les arbres de décision possèdent l'avantage d'être compréhensible par tout utilisateur (si la taille de l'arbre produit est raisonnable) et d'avoir une traduction immédiate en terme de règles de décision. Pour le système à base de règles induit, les règles sont mutuellement exclusives et l'ordre dans lequel sont examinés les attributs est figé. Les méthodes sont non optimales : un arbre de décision à 10 feuilles produit n'est pas le meilleur des arbres de décision à 10 feuilles. En effet, les choix dans la construction des arbres ne sont jamais remis en question (pas de backtraking). De plus ces méthodes sont basées sur de nombreuses heuristiques (décider si un noeud est terminal, choix du test, choix de la classe par défaut, technique d'élagage). Pour ces algorithmes, il est possible de régler les choix de paramètre et il faut faire le bon choix des paramètres (ce qui n'est pas toujours facile). Les algorithmes cités dans ce cours possèdent de nombreuses variantes. La taille des échantillons influera sur les critères d'élagage à choisir (sur l'ensemble d'apprentissage, sur un ensemble test, validation croisée).