Wer hat den Entscheidungsbaum erfunden?

Ich versuche zu verfolgen, wer die Datenstruktur und den Algorithmus des Entscheidungsbaums erfunden hat.

Im Wikipedia-Eintrag zum Entscheidungsbaum-Lernen heißt es, dass "ID3 und CART ungefähr zur gleichen Zeit (zwischen 1970 und 1980) unabhängig voneinander erfunden wurden". ID3 wurde später vorgestellt in:

• Quinlan, JR 1986. Induktion von Entscheidungsbäumen. Mach. Lernen. 1, 1 (März 1986), 81-106

Ich bin mir also nicht sicher, ob die Behauptung wahr ist.

Ich fand unter Verwendung von Google-Büchern einen Verweis auf eine statistische Entscheidungsserie aus dem Jahr 1959 und eine Sammlung von Arbeitspapieren aus dem Jahr 1958 . Der Kontext ist nicht klar und sie scheinen keinen Algorithmus zu präsentieren. Sie definieren jedoch nicht die Datenstruktur und behandeln sie wie bekannt.

Mit Google Scholar habe ich Zitate aus dem Jahr 1853 gefunden, bei denen es sich jedoch um Analysefehler und nicht um echte Zitate aus diesem Datum handelte.

Gute Frage. @ G5W ist auf dem richtigen Weg, um auf Wei-Yin Lohs Artikel zu verweisen. Lohs Artikel erörtert die statistischen Vorgeschichten von Entscheidungsbäumen und führt ihren Ort korrekterweise auf den Artikel von Fisher (1936) über Diskriminanzanalyse zurück - im Wesentlichen Regression, die mehrere Gruppen als abhängige Variable klassifiziert - und von dort über AID, THAID, CHAID und CART-Modelle.

Die kurze Antwort ist, dass der erste Artikel, den ich finden konnte, der einen "Entscheidungsbaum" -Ansatz entwickelt, aus dem Jahr 1959 stammt, und der britische Forscher William Belson in einem Artikel mit dem Titel " Matching and Prediction on the Principle of Biological Classification" ( JRSS) , Reihe C, Angewandte Statistik, Bd. 8, Nr. 2, Juni 1959, S. 65-75), dessen Zusammenfassung seinen Ansatz als einen der übereinstimmenden Stichproben von Populationen beschreibt und Kriterien dafür entwickelt:

In diesem Artikel beschreibt Dr. Belson eine Technik zum Abgleichen von Bevölkerungsproben. Dies hängt von der Kombination empirisch entwickelter Prädiktoren ab, um die beste verfügbare prädiktive oder übereinstimmende Zusammensetzung zu erhalten. Das zugrunde liegende Prinzip unterscheidet sich deutlich von dem der Mehrfachkorrelationsmethode.

Die "lange" Antwort lautet, dass andere, noch frühere Gedankenströme hier relevant erscheinen. Zum Beispiel bieten die einfachen Alters-Geschlechts-Kohorten-Ausbrüche, die in versicherungsmathematischen Sterbetafeln verwendet werden, einen Rahmen zum Nachdenken über Entscheidungen, die mehrere Jahrhunderte zurückreichen. Man könnte auch argumentieren, dass Bemühungen, die auf die Babylonier zurückgehen, quadratische Gleichungen verwendeten, die in den Variablen nichtlinear waren (nicht in den Parametern http://www-history.mcs.st-and.ac.uk/HistTopics/Quadratic_etc_equations). html ) haben Relevanz, zumindest insofern, als sie parametrische Modelle des logistischen Wachstums vorgeben (ich erkenne, dass dies eine Strecke istKommentar, lesen Sie bitte weiter, um eine umfassendere Begründung zu erhalten. Darüber hinaus haben Philosophen die Existenz hierarchisch geordneter, qualitativer Informationen seit langem erkannt und theoretisiert, z. B. Aristoteles 'Buch über Kategorien . Das Konzept und die Annahme einer Hierarchie sind hier entscheidend. Andere relevante, viel spätere Entdeckungen betrafen das Überschreiten der Grenzen des euklidischen 3D-Raums in David Hilberts Entwicklung von infinite, HilbertRaum, Kombinatorik, Entdeckungen in der Physik in Bezug auf 4-D-Minkowski-Raum, Abstand und Zeit, die statistische Mechanik hinter Einsteins Theorie der speziellen Relativitätstheorie sowie Neuerungen in der Wahrscheinlichkeitstheorie in Bezug auf Modelle von Markov-Ketten, Übergängen und Prozessen. Der Punkt hier ist, dass es eine signifikante Verzögerung zwischen jeder Theorie und ihrer Anwendung geben kann - in diesem Fall die Verzögerung zwischen Theorien über qualitative Informationen und Entwicklungen in Bezug auf ihre empirische Bewertung, Vorhersage, Klassifizierung und Modellierung.

Eine gute Vermutung ist, dass diese Entwicklungen mit der Geschichte der zunehmenden Verfeinerung von Statistikern, meist im 20. Jahrhundert, in Verbindung gebracht werden können, indem Modelle entwickelt werden, die andere als kontinuierliche Skalentypen (z. B. nominelle oder einfach kategoriale Informationen) und Zähldatenmodelle verwenden (poisson), klassifikationsübergreifende Kontingenztabellen, verteilungsfreie nichtparametrische Statistiken, mehrdimensionale Skalierung (z. B. JG Carroll), Modelle mit qualitativen abhängigen Variablen wie z. B. logistische Zwei-Gruppen-Regression sowie Korrespondenzanalyse (hauptsächlich in Holland und Frankreich) in den 70er und 80er Jahren).

Es gibt eine breite Literatur, in der zwei gruppenlogistische Regressionen mit zwei gruppendiskriminanten Analysen diskutiert und verglichen werden und die für vollständig nominale Merkmale gleichwertige Lösungen liefern (z. B. Dillon und Goldsteins Multivariate Analysis , 1984).

JS Cramers Artikel über die Geschichte der logistischen Regression ( The History of Logistic Regression , http://papers.tinbergen.nl/02119.pdf ) beschreibt sie als Ursprung der Entwicklung der univariaten, logistischen Funktion oder der klassischen S-förmigen Kurve :

Das Überleben des Begriffs Logistik und die breite Anwendung des Geräts wurden entscheidend durch die persönlichen Geschichten und individuellen Handlungen einiger Gelehrter bestimmt ...

Deterministische Modelle der Logistikkurve entstanden 1825, als Benjamin Gompertz ( https://en.wikipedia.org/wiki/Benjamin_Gompertz ) eine Veröffentlichung veröffentlichte, in der das erste wirklich nichtlineare logistische Modell (nicht linear in den Parametern und nicht nur in den Variablen wie mit) entwickelt wurde die Babylonier) - das Gompertz-Modell und die Kurve.

Ich würde vorschlagen, dass ein weiteres wichtiges Glied in dieser Kette, das zur Erfindung von Entscheidungsbäumen führte, die Arbeit des Kolumbiensoziologen Paul Lazarsfeld über latente Strukturmodelle war. Seine Arbeit begann in den 30er Jahren, setzte sich während des Zweiten Weltkriegs mit seiner Inhaltsanalyse deutscher Zeitungen für die aufkommende OSS (später die CIA, wie in John Naisbett's Buch Megatrends diskutiert ) fort und wurde schließlich 1950 veröffentlicht. Andersen beschreibt dies so ( Latent Structure Analysis: Eine Übersicht , Erling B. Andersen, Scandinavian Journal of Statistics , Bd. 9, Nr. 1, 1982, S. 1-12):

Die Grundlage für die klassische Theorie der latenten Strukturanalyse wurde 1950 von Paul Lazarsfeld in einer Studie zum Ethnozentrismus amerikanischer Soldaten während des Zweiten Weltkriegs entwickelt. Lazarsfeld war in erster Linie daran interessiert, die konzeptionelle Grundlage für latente Strukturmodelle zu entwickeln ... Die von Lazarsfeld entwickelten statistischen Methoden waren jedoch eher primitiv ... Ein früher Versuch, effiziente Schätzmethoden und Testverfahren abzuleiten, wurde von Lazarsfelds Kollegen an der Columbia University unternommen , TW Anderson, der in einem Aufsatz ( Psychometrika , März 1954, Band 19, Ausgabe 1, S. 1–10, Zur Abschätzung von Parametern in der Latentstrukturanalyse), eine effiziente Schätzmethode für die Parameter des Latentklassenmodells entwickelt ... Um das Framework (der Latentklassenmodelle) einzuführen, werden wir kurz die Grundkonzepte skizzieren ... und ein viel später von Goodman entwickeltes Notationssystem verwenden (1974a) ... Die Daten werden in Form einer Mehrfachkontingenztabelle angegeben ...

Es lohnt sich, hier eine nützliche Unterscheidung zu treffen, da dies mit dem Übergang von AID zu CHAID (später CART) zusammenhängt, und zwar zwischen auf Kontingenztabellen basierenden Modellen (alle Variablen im Modell sind nominal skaliert) und neueren Modellen latenter Klassen (mehr) präzise, ​​endliche Mischungsmodelle, die auf "Mischungen" von Maßstäben und Verteilungen basieren, z. B. Kamakura und Russell, 1989, Ein probabilistisches Auswahlmodell für Marktsegmentierung und Elastizitätsstruktur), wie sie die Residuen des Modells erzeugen. Bei den älteren Kontingenztabellenmodellen bildeten die in der vollständig kreuzklassifizierten Tabelle enthaltenen Zellenzahlen die Grundlage für die "Replikationen" und daher die Heterogenität der bei der Unterteilung in Klassen verwendeten Modellreste. Andererseits beruhen die neueren Mischungsmodelle auf wiederholten Messungen über ein einzelnes Subjekt hinweg als Grundlage für die Aufteilung der Heterogenität in die Residuen. Diese Antwort ist nichteine direkte Verbindung zwischen latenten Klassenmodellen und Entscheidungsbäumen vorschlagen. Die Relevanz für AID und CHAID kann in den zur Bewertung der Modelle verwendeten Statistiken zusammengefasst werden. AID verwendet eine kontinuierliche F-Verteilung, während CHAID die Chi-Quadrat-Verteilung verwendet, die für kategoriale Informationen geeignet ist. LCMs bilden meines Erachtens eher in der Analyse und Modellierung von Kontingenztabellen einen wichtigen Teil des Puzzles oder der Erzählung, die zur Entwicklung von Entscheidungsbäumen führen, zusammen mit den vielen anderen bereits erwähnten Neuerungen.

CHAID war eine spätere Entwicklung, die erstmals 1980 in einer Dissertation des Südafrikaners Gordon Kass vorgeschlagen wurde, wie in diesem Wiki-Artikel über CHAID ( https://en.wikipedia.org/wiki/CHAID ) beschrieben. Natürlich kam CART einige Jahre später in den 80er Jahren mit Breiman et al. Heraus, dem mittlerweile berühmten Buch Classification and Regression Trees .

AID, CHAID und CART setzen alle baumartige, hierarchisch angeordnete Strukturen als optimale Darstellung der Realität ein. Sie gehen einfach mit unterschiedlichen Algorithmen und Methoden vor. Die nächsten Schritte in dieser fortschreitenden Innovationskette sind für mich die Entstehung heterarchischer Strukturtheorien. Wie in diesem Wiki-Artikel definiert, sind Heterarchien "ein Organisationssystem, bei dem die Elemente der Organisation nicht in eine Rangfolge eingereiht sind (nicht hierarchisch) oder das Potenzial haben, auf verschiedene Arten in eine Rangfolge eingestuft zu werden" ( https://en.wikipedia) .org / wiki / Heterarchie oder für eine tiefere, philosophischere Perspektive der Heterarchie siehe Kontopoulos, The Logics of Social Structure). Aus empirischer Sicht sind die Analyse und Modellierung von Netzwerkstrukturen für diese historische Entwicklung im Strukturverständnis am repräsentativsten (z. B. Freemans Buch The Development of Social Network Analysis ). Während viele Netzwerkanalysten versuchen werden, dem resultierenden Netzwerk eine hierarchische Anordnung aufzuzwingen, ist dies eher ein Ausdruck tief verwurzelter und unbewusster Annahmen als eine Aussage über die empirische Realität der Multiplex-Netzwerkstruktur in einer komplexen Welt.

Diese Antwort deutet darauf hin, dass der Evolutionsbogen, der zur Entwicklung von Entscheidungsbäumen führte, in jedem Schritt oder jeder Phase des Prozesses neue Fragen oder Unzufriedenheit mit bestehenden "State-of-the-Art" -Methoden aufwirft und neue Lösungen und Modelle erfordert. In diesem Fall kann Unzufriedenheit in den Einschränkungen der Modellierung von zwei Gruppen (logistische Regression) und der Anerkennung der Notwendigkeit, diesen Rahmen auf mehr als zwei Gruppen zu erweitern, gesehen werden. Unzufriedenheit mit nicht repräsentativen Annahmen einer zugrunde liegenden Normalverteilung (Diskriminanzanalyse oder AID) sowie Vergleich mit der relativen "Freiheit" bei der Verwendung nichtparametrischer, verteilungsfreier Annahmen und Modelle (z. B. CHAID und CART).

Wie bereits erwähnt, hat der Ursprung von Entscheidungsbäumen mit ziemlicher Sicherheit eine lange Geschichte, die Jahrhunderte zurückreicht und geografisch verstreut ist. Mehrere Strömungen in der Geschichte, Wissenschaft, Philosophie und dem Denken der Menschen lassen sich nachvollziehen, um die Erzählung zu skizzieren, die zur Entwicklung der vielen Arten von Entscheidungsbäumen geführt hat, die heute existieren. Ich werde die ersten sein, die die signifikanten Einschränkungen meiner kurzen Skizze dieser Geschichte anerkennen.

/ ** Nachträge ** /

1. Dieser Artikel im New Scientist 2014 trägt den Titel Warum lieben wir es, Wissen in Bäumen zu organisieren? ( https://www.newscientist.com/article/mg22229630-800-why-do-we-love-to-organise-knowledge-into-trees/ ). Es handelt sich um eine Übersicht über das Buch The Book of von Datenvisualisierungsguru Manuel Lima Bäume, die die jahrtausendealte Verwendung von Bäumen als Visualisierungs- und Erinnerungshilfe für Wissen nachzeichnen. Es scheint keine Frage zu sein, dass die säkularen und empirischen Modelle und Grafiken, die Methoden wie AID, CHAID und CART innewohnen, die Weiterentwicklung dieser ursprünglich religiösen Klassifikationstradition darstellen.

2. In diesem Video (online gestellt von Salford Systems, Implementierer von CART-Software), Ein Tribut an Leo Breiman , spricht Breiman über die Entwicklung seines Denkens, das zur CART-Methodik führte. Alles begann mit einer Mauer, die mit den Silhouetten verschiedener Schlachtschiffe aus der Zeit des Zweiten Weltkriegs verkleidet war.

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

3. In der Einleitung zu Denis Konigs Theorie der endlichen und unendlichen Graphen von 1936 , die allgemein als die erste rigorose mathematische Grundlage für ein Feld angesehen wird, das zuvor als Quelle der Unterhaltung und der Rätsel für Kinder angesehen wurde, merkt Tutte in diesem Kapitel an (S. 13) 4 (ab S. 62) von Konigs Buch widmet sich den Bäumen in der Graphentheorie. Tuttes Erklärung für Konigs Definition eines Baums lautet: "Wo ein 'azyklischer' Graph ein Graph ohne Kreis ist, ein Baum ein endlicher zusammenhängender azyklischer Graph ist ... mit anderen Worten, in einem Baum gibt es einen und nur einen Pfad von einem "Für mich (und ich bin weder Graphentheoretiker noch Mathematiker) legt dies nahe, dass die Graphentheorie und ihre Vorläufer in Poincares Analysis Situs oder Veblen ' Vorlesungen über kombinatorische Topologie haben möglicherweise die ersten intellektuellen und mathematischen Grundlagen für das geliefert, was später zu einem Thema für Statistiker wurde.

4. Der erste Baum des Wissens wird weitgehend dem neoplatonischen Philosophen Porphyr zugeschrieben, der um 270 n. Chr. Eine Einführung in die Logik verfasste , in der Wissen anhand eines metaphorischen Baums beschrieben und organisiert wurde ... http://www.historyofinformation.com/expanded.php? id = 3857

5. Habe gerade einen noch früheren Verweis auf einen Baum des Wissens im Buch Genesis in der Bibel entdeckt, der in diesem Wiki-Artikel behandelt wird ... https://en.wikipedia.org/wiki/Tree_of_life_(biblical) . Genesis stammt wahrscheinlich aus dem Jahr 1.400 v. Chr., Basierend auf dieser Referenz ... https://www.biblica.com/bible/bible-faqs/when-was-the-bible-written/ Ungeachtet dessen kam das Buch Genesis viele Jahrhunderte zuvor Porphyr.

Die große Referenz auf CART ist:

Klassifikations- und Regressionsbäume
Leo Breiman, Jerome Friedman, Charles J. Stone, RA Olshen (1984)

aber das war sicherlich nicht die früheste Arbeit zu diesem Thema.

In seinem 1986 erschienenen Aufsatz Induction of Decision Trees identifiziert Quinlan selbst das Concept Learning System (CLS) von Hunt als Vorläufer von ID3. Er datiert CLS um 1963, bezieht sich jedoch auf Referenzen

EB Hunt, J. Marin, PJ Stone,
Experimente in Induction
Academic Press, New York, 1966

Wei-Yin Loh von der University of Wisconsin hat über die Geschichte der Entscheidungsbäume geschrieben. Es gibt ein Papier

Fünfzig Jahre Klassifikations- und Regressionsbäume Wei-Yin Loh International Statistical Review (2014), 82, 3, 329–348 doi: 10.1111 / insr.12016

Es gibt auch ein Dia-Deck aus einem Vortrag, den er zu diesem Thema gehalten hat.