Qui a inventé l'arbre de décision?

Bonne question. @ G5W est sur la bonne voie en faisant référence au document de Wei-Yin Loh. L'article de Loh examine les antécédents statistiques des arbres de décision et, à juste titre, retrace leur locus dans l'article de Fisher (1936) sur l'analyse discriminante - essentiellement une régression classant plusieurs groupes comme variable dépendante - et à partir de là, via AID, THAID, CHAID et Modèles CART.

La réponse courte est que le premier article que j'ai pu trouver qui développe une approche "d'arbre de décision" date de 1959 et un chercheur britannique, William Belson, dans un article intitulé Matching and Prediction on the Principle of Biological Classification , ( JRSS , Série C, Statistiques appliquées, vol. 8, n ° 2, juin 1959, pp. 65-75), dont l'abrégé décrit son approche comme l'un des appariements d' échantillons de population et l'élaboration de critères pour ce faire:

Dans cet article, le Dr Belson décrit une technique de mise en correspondance d'échantillons de population. Cela dépend de la combinaison de prédicteurs développés empiriquement pour donner le meilleur composite prédictif ou d'appariement disponible. Le principe sous-jacent est tout à fait distinct de celui inhérent à la méthode de corrélation multiple.

La réponse "longue" est que d'autres courants de pensée, même antérieurs, semblent pertinents ici. Par exemple, les simples ventilations par cohorte âge-sexe utilisées dans les tables actuarielles de mortalité offrent un cadre de réflexion sur les décisions qui remonte à plusieurs siècles. On pourrait également faire valoir que les efforts remontant aux Babyloniens ont utilisé des équations quadratiques, qui étaient non linéaires dans les variables (pas dans les paramètres, http://www-history.mcs.st-and.ac.uk/HistTopics/Quadratic_etc_equations. html ) ont la pertinence, au moins dans la mesure où ils présagent modèles paramétriques de croissance logistique (je reconnais que c'est un tronçoncommentaire, lisez la suite pour une motivation plus complète). De plus, les philosophes reconnaissent et théorisent depuis longtemps l'existence d'informations qualitatives hiérarchisées, par exemple le livre d'Aristote sur les catégories . Le concept et l'hypothèse d'une hiérarchie sont essentiels ici. D' autres découvertes pertinentes, beaucoup plus tard étaient en poussant au - delà des limites de l' espace euclidien 3-D dans le développement de David Hilbert de l' infini, Hilbertespace, combinatoire, découvertes en physique liées à l'espace, à la distance et au temps de Minkowski 4-D, la mécanique statistique derrière la théorie d'Einstein de la relativité restreinte ainsi que les innovations dans la théorie des probabilités relatives aux modèles de chaînes, transitions et processus markoviens. Le point ici est qu'il peut y avoir un décalage significatif entre n'importe quelle théorie et son application - dans ce cas, le décalage entre les théories sur les informations qualitatives et les développements liés à leur évaluation empirique, prédiction, classification et modélisation.

Une meilleure supposition est que ces développements peuvent être associés à l'histoire de la sophistication croissante des statisticiens, principalement au 20e siècle, dans le développement de modèles utilisant des types d'échelle autres que continus (par exemple, des informations nominales ou, plus simplement, catégoriques), des modèles de données de comptage (poisson), tableaux de contingence croisés, statistiques non paramétriques sans distribution, mise à l'échelle multidimensionnelle (par exemple, JG Carroll, entre autres), modèles avec des variables dépendantes qualitatives telles que la régression logistique à deux groupes ainsi que l'analyse des correspondances (principalement aux Pays-Bas et en France dans les années 70 et 80).

Il existe une vaste littérature qui discute et compare la régression logistique à deux groupes avec l'analyse discriminante à deux groupes et, pour des caractéristiques entièrement nominales, les trouve fournissant des solutions équivalentes (par exemple, l' analyse multivariée de Dillon et Goldstein , 1984).

L'article de JS Cramer sur l'histoire de la régression logistique ( The History of Logistic Regression , http://papers.tinbergen.nl/02119.pdf ) le décrit comme provenant du développement de la fonction logistique univariée ou de la courbe en forme de S classique :

La survie du terme logistique et la large application de l'appareil ont été déterminées de manière décisive par les histoires personnelles et les actions individuelles de quelques chercheurs ...

Les modèles déterministes de la courbe logistique sont nés en 1825, lorsque Benjamin Gompertz ( https://en.wikipedia.org/wiki/Benjamin_Gompertz ) a publié un article développant le premier modèle logistique véritablement non linéaire (non linéaire dans les paramètres et pas seulement les variables comme avec les Babyloniens) - le modèle et la courbe de Gompertz.

Je dirais qu'un autre maillon important de cette chaîne menant à l'invention des arbres de décision était le travail du sociologue de Columbia Paul Lazarsfeld sur les modèles de structure latente. Son travail a commencé dans les années 30, a continué pendant la Seconde Guerre mondiale avec son analyse du contenu des journaux allemands pour l'OSS naissant (plus tard la CIA, comme discuté dans le livre Megatrends de John Naisbett ) et finalement publié en 1950. Andersen le décrit de cette façon ( Latent Structure Analysis: A Survey , Erling B. Andersen, Scandinavian Journal of Statistics , vol. 9, n ° 1, 1982, p. 1-12):

Les fondements de la théorie classique de l'analyse des structures latentes ont été développés par Paul Lazarsfeld en 1950 dans une étude de l'ethnocentrisme des soldats américains pendant la Seconde Guerre mondiale. Lazarsfeld était principalement intéressé à développer les fondements conceptuels des modèles de structure latente ... Les méthodes statistiques développées par Lazarsfeld étaient cependant plutôt primitives ... Une première tentative de dériver des méthodes d'estimation et des procédures de test efficaces a été faite par le collègue de Lazarsfeld à l'Université Columbia. , TW Anderson, qui dans un article ( Psychometrika , mars 1954, volume 19, numéro 1, pp 1–10, sur l'estimation des paramètres dans l'analyse de la structure latente), a développé une méthode d'estimation efficace des paramètres du modèle de classe latente ... Afin d'introduire le cadre (des modèles de classe latente), nous allons brièvement décrire les concepts de base ... et utiliser un système de notation développé beaucoup plus tard par Goodman (1974a) ... Les données sont présentées sous la forme d'un tableau de contingence multiple ...

Il y a une distinction utile à faire ici, car elle peut être liée à la progression de l'AID à CHAID (plus tard CART), entre les modèles basés sur une table de contingence (toutes les variables du modèle sont nominalement mises à l'échelle) et les modèles de classe latente plus récents (plus précisément, des modèles de mélange fini basés sur des «mélanges» d'échelles et de distributions, par exemple, Kamakura et Russell, 1989, A Probabilistic Choice Model for Market Segmentation and Elasticity Structure) dans la façon dont ils créent les résidus du modèle. Pour les anciens modèles de tableaux de contingence, le nombre de cellules inhérent au tableau entièrement croisé a constitué la base des «réplications» et, par conséquent, l'hétérogénéité des résidus du modèle utilisés dans le partitionnement en classes. D'un autre côté, les modèles de mélange les plus récents s'appuient sur des mesures répétées sur un même sujet comme base de partition de l'hétérogénéité des résidus. Cette réponse n'est passuggérant une connexion directe entre les modèles de classes latentes et les arbres de décision. La pertinence pour AID et CHAID peut être résumée dans les statistiques utilisées pour évaluer les modèles, AID utilise une distribution F continue tandis que CHAID utilise la distribution khi carré, appropriée pour les informations catégoriques. Plutôt dans leur analyse et leur modélisation des tableaux de contingence, les LCM constituent, à mon avis, une pièce importante du puzzle ou de la narration menant à l'élaboration d'arbres de décision, avec les nombreuses autres innovations déjà notées.

CHAID était un développement ultérieur, proposé pour la première fois dans une thèse de doctorat de 1980 par le sud-africain Gordon Kass, comme indiqué dans cet article Wiki sur CHAID ( https://en.wikipedia.org/wiki/CHAID ). Bien sûr, CART est venu quelques années plus tard dans les années 80 avec Breiman, et al's, désormais célèbre livre Classification and Regression Trees .

AID, CHAID et CART proposent tous des structures arborescentes, disposées hiérarchiquement comme la représentation optimale de la réalité. Ils s'y prennent simplement en utilisant différents algorithmes et méthodes. Pour moi, les prochaines étapes de cette chaîne d'innovation progressive sont l'émergence de théories hétérarchiques de la structure. Comme défini dans cet article Wiki, les hétérarchies "sont un système d'organisation où les éléments de l'organisation ne sont pas classés (non hiérarchiques) ou où ils peuvent être classés de différentes manières" ( https: //en.wikipedia .org / wiki / Heterarchy ou pour une perspective plus approfondie et plus philosophique de l'hétérarchie, voir Kontopoulos, The Logics of Social Structure). D'un point de vue empirique, l'analyse et la modélisation des structures de réseau sont les plus représentatives de ce développement historique dans la compréhension de la structure (par exemple, le livre de Freeman The Development of Social Network Analysis ). Bien que de nombreux analystes de réseaux tentent de forcer un arrangement hiérarchique sur le réseau résultant, il s'agit davantage d'une expression d'hypothèses ancrées et inconscientes que d'une déclaration sur la réalité empirique de la structure d'un réseau multiplex dans un monde complexe.

Cette réponse suggère que l'arc de l'évolution conduisant au développement d'arbres de décision a créé de nouvelles questions ou une insatisfaction à l'égard des méthodes "de pointe" existantes à chaque étape ou phase du processus, nécessitant de nouvelles solutions et de nouveaux modèles. Dans ce cas, les insatisfactions peuvent être vues dans les limites de la modélisation de deux groupes (régression logistique) et la reconnaissance de la nécessité d'élargir ce cadre à plus de deux groupes. Insatisfactions à l'égard d'hypothèses non représentatives d'une distribution normale sous-jacente (analyse discriminante ou AID) ainsi que comparaison avec la relative "liberté" que l'on trouve dans l'emploi d'hypothèses et de modèles non paramétriques sans distribution (par exemple, CHAID et CART).

Comme suggéré, l'origine des arbres de décision a presque certainement une longue histoire qui remonte à des siècles et est géographiquement dispersée. De multiples courants dans l'histoire humaine, la science, la philosophie et la pensée peuvent être tracés en décrivant le récit menant au développement des nombreuses saveurs d'arbres de décision qui existent encore aujourd'hui. Je serai le premier à reconnaître les limites importantes de mon bref aperçu de cette histoire.

/ ** Addendums ** /

Cet article de 2014 du New Scientist s'intitule Pourquoi aimons-nous organiser les connaissances en arbres? ( https://www.newscientist.com/article/mg22229630-800-why-do-we-love-to-organise-knowledge-into-trees/ ), il s'agit d'une revue du livre du gourou de la visualisation des données, Manuel Book Des arbres qui retracent l'utilisation millénaire des arbres comme visualisation et aide mnémonique à la connaissance. Il ne fait guère de doute que les modèles et graphiques laïques et empiriques inhérents à des méthodes telles que l'AID, la CHAID et le CART représentent l'évolution continue de cette tradition de classification à l'origine religieuse.
Dans cette vidéo (publiée en ligne par Salford Systems, implémenteurs du logiciel CART), A Tribute to Leo Breiman , Breiman parle du développement de sa pensée qui a conduit à la méthodologie CART. Tout a commencé avec un mur recouvert de silhouettes de différents cuirassés de la Seconde Guerre mondiale.

https://www.salford-systems.com/videos/conferences/cart-founding-fathers/a-tribute-to-leo-breiman?utm_source=linkedin&utm_medium=social&utm_content=3599323

Tutte note (p. 13) ce chapitre en lisant l'introduction à la théorie des graphes finis et infinis de 1936 de Denis Konig , largement considérée comme fournissant la première base mathématique rigoureuse à un domaine précédemment considéré comme une source d'amusement et d'énigmes pour les enfants. 4 (à partir de la page 62) du livre de Konig est consacré aux arbres dans la théorie des graphes. L'explication de Tutte de la définition de Konig d'un arbre est «où un graphique« acyclique »est un graphique sans circuit, un arbre est un graphique acyclique connecté fini ... en d'autres termes, dans un arbre il y a un et un seul chemin à partir d'un donné sommet à un autre ... "Pour moi (et je ne suis ni un théoricien des graphes ni un mathématicien), cela suggère que la théorie des graphes et ses précurseurs dans l' analyse Situs ou Veblen de Poincaré " des conférences sur la topologie combinatoire peuvent avoir fourni les premiers antécédents intellectuels et mathématiques de ce qui devint plus tard un sujet pour les statisticiens.
Le premier arbre de la connaissance est largement attribué au philosophe néoplatonicien Porphyre qui, vers 270 EC, a écrit une introduction à la logique qui a utilisé un arbre métaphorique pour décrire et organiser les connaissances ... http://www.historyofinformation.com/expanded.php? id = 3857
Je viens de découvrir une référence encore plus tôt à un arbre de la connaissance dans le livre de la Genèse dans la Bible, discuté dans cet article Wiki ... https://en.wikipedia.org/wiki/Tree_of_life_(biblical) . La Genèse remonte probablement à 1400 avant notre ère sur la base de cette référence ... https://www.biblica.com/bible/bible-faqs/when-was-the-bible-written/ Quoi qu'il en soit, le Livre de la Genèse est venu plusieurs siècles avant Porphyre.

Mike Hunter
la source

Que c'est une merveilleuse "brève esquisse de cette histoire". Je pensais que les racines devraient être plus profondes que 50 ans, mais je ne pensais pas qu'elles parviendraient à Aristote et aux Babyloniens. Vous avez très bien montré comment les méthodes se sont rapprochées d'un arbre de décision. Je manque encore un point d'émergence plus précis. J'espérais trouver une référence à un vieux livre dans lequel vous voyez un diagramme en nuage et dites: "eh bien, c'est un arbre de décision" ;-)

DaL

Je n'aime pas la nomenclature utilisée dans la question et dans certaines réponses. CART est des arbres de classification et de régression pour une raison. Un arbre de décision comme indiqué ci-dessus peut impliquer ou non une analyse statistique, et est souvent basé sur des heuristiques et non sur des données. La question d'origine aurait dû porter sur les arbres de classification .

Frank Harrell

Qui a inventé l'arbre de décision?

Réponses: