Arbres de décision/Historique

Début de la boite de navigation du chapitre

fin de la boite de navigation du chapitre

Recherches

Les arbres de décision ont fait l’œuvre de beaucoup de recherches dans le domaine des mathématiques et de la programmation informatique, afin de trouver l’ algorithme le plus efficace de l’ordre de segmentation des options intermédiaires.

Un algorithme est une suite finie et non-ambiguë d’opérations ou instructions permettant de résoudre un problème.

Méthode Tree-Based

D’un point de vue mathématique, James N. Morgan et John A. Sonquist sont les premiers à avoir introduit l’arbre de décision, en 1963 avec la méthode « Tree-Based methods ».

Méthode CART

Breiman, Friedman, Olshen et Stone développent la méthode CART en 1984 qui consiste en la construction d’arbres de décisions binaires par division de l'échantillon en deux sous-ensemble. Elle se base sur une approche statistique et sur la suppression de branches contenant le moins d'informations. On considère généralement que cette approche a connu son apogée avec cette méthode Classification and Regression Tree. Dans leur monographie, Breiman et al. affirmaient que les performances d’un arbre de décision reposaient principalement sur la détermination de sa taille. Les arbres ont tendance à produire un « classifieur » trop complexe, collant exagérément aux données ; c’est le phénomène de « sur-apprentissage ». Les feuilles, même si elles sont pures, sont composées de trop peu d’individus pour être fiables lors de la prédiction.

Autres recherches

Un autre de ces contributeurs est J.Quinlan, un chercheur en informatique, qui fut l’un des premiers à étudier la théorie de la décision. Il a ainsi contribué au développement des algorithmes et des arbres de décision. ID3 est un algorithme développé par Quinlan en 1983, amélioré en 1993 par une nouvelle version C4.5 (suivie par les versions C5.0 et See5). Dans cette méthode, on ne se restreint pas à des attributs binaires. Le choix du test associé à un nœud se fait à l'aide de la fonction Gain ou de la fonction Gain Ratio fondées sur la fonction entropie. La méthode peut prendre en compte le cas où les valeurs de certains attributs seraient non spécifiées. Elle prend également en compte le problème des attributs continus. On peut choisir entre arbres et règles, l'élagage se faisant sur l'arbre ou sur le système de règles, et s’appuyant sur une estimation de l'erreur réelle, à partir de l’ensemble d'apprentissages.

Le Bagging

Le Bagging est appliqué à des arbres de décision avec un tirage aléatoire qui se fait parmi les variables explicatives. Dans ce cas, on aura un hasard double, on parle de forêts aléatoires, qui est un regroupement de plusieurs arbres de décision (Breiman 2001).

Les dates clés

Date	Auteur(s)	Apport
1963	Morgan et Sonquist	Arbres de régression dans un processus de prédiction et d’explication
1980	Gordon V. Kass	CHAID (CHi-squared Automatic Interaction Detector)
1983	Quinlan	Théorie de la décision : algorithmes et arbres de décision via ID3
1984	Breiman	CART (Classification And Regression Tree)
1993	Quinlan	Amélioration ID3
2001	Breiman	Forêts aléatoires