Arbres de décision/Historique
Recherches
[modifier | modifier le wikicode]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
[modifier | modifier le wikicode]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
[modifier | modifier le wikicode]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
[modifier | modifier le wikicode]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
[modifier | modifier le wikicode]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
[modifier | modifier le wikicode]| 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 |
