Kto wynalazł drzewo decyzyjne?

Próbuję ustalić, kto wynalazł strukturę danych i algorytm drzewa decyzyjnego.

We wpisie w Wikipedii dotyczącym uczenia się drzewa decyzyjnego jest twierdzenie, że „ID3 i CART zostały wynalezione niezależnie mniej więcej w tym samym czasie (między 1970 a 1980)”. ID3 został zaprezentowany później w:

• Quinlan, JR 1986. Indukcja drzew decyzyjnych. Mach. Uczyć się. 1, 1 (marzec 1986), 81-106

więc nie jestem pewien, czy twierdzenie to jest prawdziwe.

Za pomocą książek Google znalazłem odniesienie do serii decyzji statystycznych z 1959 roku oraz zbioru dokumentów roboczych z 1958 roku . Kontekst nie jest jasny i wydaje się, że nie przedstawiają algorytmu. Jednak nie definiują struktury danych i traktują ją tak, jak jest dobrze znana.

Korzystając z Google Scholar, znalazłem cytaty z 1853 roku, ale były to błędy analizy, a nie prawdziwe cytaty z tej daty.

Dobre pytanie. @ G5W jest na dobrej drodze, odwołując się do artykułu Wei-Yin Loha. Artykuł Loha omawia statystyczne poprzedniki drzew decyzyjnych i, właściwie, śledzi ich umiejscowienie z powrotem do pracy Fishera (1936) na temat analizy dyskryminacyjnej - zasadniczo regresji klasyfikującej wiele grup jako zmienną zależną - a następnie poprzez AID, THAID, CHAID i Modele CART.

Krótka odpowiedź jest taka, że ​​pierwszy artykuł, który udało mi się znaleźć, który rozwija podejście oparte na „drzewku decyzyjnym”, pochodzi z 1959 r., A brytyjski badacz William Belson w artykule zatytułowanym „ Dopasowywanie i przewidywanie zasady klasyfikacji biologicznej” ( JRSS , Series C, Applied Statistics, Vol. 8, No. 2, June 1959, ss. 65-75), których streszczenie opisuje swoje podejście jako jedno z dopasowywania próbek populacji i opracowanie kryteriów:

W tym artykule dr Belson opisuje technikę dopasowywania próbek populacji. Zależy to od kombinacji opracowanych empirycznie predyktorów w celu uzyskania najlepszego dostępnego kompozytu predykcyjnego lub dopasowania. Zasada leżąca u jej podstaw różni się od zasady wielokrotnej korelacji.

„Długa” odpowiedź brzmi, że inne, nawet wcześniejsze nurty myśli wydają się tutaj istotne. Na przykład proste rozbicie kohortowe według wieku i płci zastosowane w aktuarialnych tabelach umieralności stanowi podstawę do myślenia o decyzjach sprzed kilku stuleci. Można również argumentować, że wysiłki sięgające Babilończyków wykorzystywały równania kwadratowe, które były nieliniowe w zmiennych (nie w parametrach, http://www-history.mcs.st-and.ac.uk/HistTopics/Quadratic_etc_equations. html ) mają znaczenie, przynajmniej w zakresie, w jakim zapowiadają parametryczne modele wzrostu logistycznego (zdaję sobie sprawę, że jest to odcinekkomentarz, proszę przeczytać dalej, aby uzyskać pełniejszą motywację). Ponadto filozofowie od dawna uznają i teoretyzują istnienie hierarchicznie ułożonych informacji jakościowych, np. Książka Arystotelesa na temat kategorii . Kluczowa jest tutaj koncepcja i założenie hierarchii . Inne istotne, znacznie późniejsze odkrycia polegały na przekraczaniu granic trójwymiarowej przestrzeni euklidesowej w rozwoju nieskończoności Davida Hilberta, Hilbertaprzestrzeń, kombinatoryka, odkrycia w fizyce związane z przestrzenią, odległością i czasem 4-D Minkowskiego, mechanika statystyczna stojąca za teorią szczególnej teorii względności Einsteina, a także innowacje w teorii prawdopodobieństwa odnoszące się do modeli łańcuchów, przejść i procesów Markowa. Chodzi o to, że może istnieć znaczne opóźnienie między dowolną teorią a jej zastosowaniem - w tym przypadku opóźnienie między teoriami na temat informacji jakościowych i zmian związanych z ich oceną empiryczną, prognozowaniem, klasyfikacją i modelowaniem.

Można przypuszczać, że zmiany te można powiązać z historią rosnącego wyrafinowania statystyk, głównie w XX wieku, w opracowywaniu modeli wykorzystujących typy skal inne niż ciągłe (np. Informacje nominalne lub, prościej, kategoryczne), modele danych (Poissona), krzyżowe tabele kontyngencji, statystyki nieparametryczne bez rozkładu, skalowanie wielowymiarowe (np. JG Carroll), modele z jakościowymi zmiennymi zależnymi, takimi jak regresja logistyczna dwóch grup, a także analiza korespondencji (głównie w Holandii i Francji w latach 70. i 80.).

Istnieje obszerna literatura, która omawia i porównuje regresję logistyczną dwóch grup z dwiema grupowymi analizami dyskryminacyjnymi i, dla cech w pełni nominalnych, stwierdza, że ​​zapewniają one równoważne rozwiązania (np. Analiza wielowymiarowa Dillona i Goldsteina , 1984).

Artykuł JS Cramera o historii regresji logistycznej ( Historia regresji logistycznej , http://papers.tinbergen.nl/02119.pdf ) opisuje ją jako powstającą wraz z rozwojem uniwariatu, funkcji logistycznej lub klasycznej krzywej w kształcie litery S. :

O przetrwaniu terminu logistycznego i szerokim zastosowaniu urządzenia decydowały decydujące historie osobiste i indywidualne działania kilku uczonych ...

Deterministyczne modele krzywej logistycznej powstały w 1825 roku, kiedy Benjamin Gompertz ( https://en.wikipedia.org/wiki/Benjamin_Gompertz ) opublikował artykuł opracowujący pierwszy prawdziwie nieliniowy model logistyczny (nieliniowy w parametrach, a nie tylko zmienne jak w przypadku Babilończycy) - model i krzywa Gompertza.

Sugerowałbym, że innym ważnym ogniwem w tym łańcuchu prowadzącym do wynalezienia drzew decyzyjnych była praca socjologa z Kolumbii Paula Lazarsfelda nad modelami ukrytej struktury. Jego praca rozpoczęła się w latach 30., kontynuowano podczas II wojny światowej, analizując treść niemieckich gazet dla rodzącego się OSS (później CIA, jak omówiono w książce Johna Naisbetta Megatrends ) i ostatecznie opublikowano ją w 1950 r. Andersen tak to opisuje ( Latent Structure Analysis: A Survey , Erling B. Andersen, Scandinavian Journal of Statistics , t. 9, nr 1, 1982, s. 1-12):

Podstawę klasycznej teorii analizy struktury utajonej opracował Paul Lazarsfeld w 1950 r. W badaniu etnocentryzmu amerykańskich żołnierzy podczas II wojny światowej. Lazarsfeld był przede wszystkim zainteresowany opracowaniem koncepcyjnych podstaw ukrytych modeli struktur ... Metody statystyczne opracowane przez Lazarsfeld były jednak dość prymitywne ... Wczesną próbę uzyskania skutecznych metod szacowania i procedur testowych podjął kolega Lazarsfelda z Columbia University , TW Anderson, który w pracy ( Psychometrika , marzec 1954 r., Tom 19, wydanie 1, s. 1–10, O estymacji parametrów w analizie struktury utajonej) opracował wydajną metodę estymacji parametrów modelu klasy utajonej ... Aby wprowadzić ramy (modeli klasy utajonej), pokrótce opiszemy podstawowe pojęcia ... i zastosujemy system notacyjny opracowany znacznie później przez Goodmana (1974a) ... Dane są podane w formie tabeli wielu zdarzeń awaryjnych ...

Warto tu wprowadzić przydatne rozróżnienie, ponieważ można je powiązać z przejściem z AID do CHAID (późniejszy CART), między modelami opartymi na tabeli kontyngencji (wszystkie zmienne w modelu są nominalnie skalowane) a nowszymi modelami klas ukrytych (więcej właśnie modele skończonej mieszanki oparte na „mieszankach” skal i rozkładów, np. Kamakura i Russell, 1989, model wyboru probabilistycznego dla segmentacji rynku i struktury elastyczności) w sposobie tworzenia reszt modelu. W starszych modelach tabeli kontyngencji liczby komórek nieodłącznie związane z tabelą w pełni sklasyfikowaną stanowiły podstawę „replikacji”, a zatem niejednorodności reszt modelu zastosowanych w podziale na klasy. Z drugiej strony, nowsze modele mieszanin opierają się na powtarzanych pomiarach u jednego pacjenta jako podstawy do podziału heterogeniczności na reszty. Ta odpowiedź nie jestsugerując bezpośrednie połączenie między modelami klas ukrytych a drzewami decyzyjnymi. Istotność dla AID i CHAID można podsumować w statystykach zastosowanych do oceny modeli, AID wykorzystuje ciągły rozkład F, podczas gdy CHAID stosuje rozkład chi-kwadrat, odpowiedni dla informacji kategorycznych. Zamiast tego w ich analizie i modelowaniu tabel awaryjnych LCM stanowią, moim zdaniem, ważny element układanki lub narracji prowadzącej do rozwoju drzew decyzyjnych, a także wiele innych innowacji, które już zauważyłem.

CHAID był późniejszym opracowaniem, po raz pierwszy zaproponowanym w rozprawie doktorskiej z 1980 roku przez południowoafrykańskiego Gordona Kassa, jak opisano w tym fragmencie Wiki na CHAID ( https://en.wikipedia.org/wiki/CHAID ). Oczywiście, CART pojawił się kilka lat później w latach 80. wraz z Breimanem i innymi, słynną książką Klasyfikacja i drzewa regresji .

AID, CHAID i CART stawiają hierarchiczne struktury przypominające drzewa, jako optymalne odwzorowanie rzeczywistości. Po prostu zajmują się tym przy użyciu różnych algorytmów i metod. Dla mnie następnymi krokami w tym postępowym łańcuchu innowacji są pojawienie się heterarchicznych teorii struktury. Jak zdefiniowano w tym artykule na Wiki, heterarchie „są systemem organizacji, w którym elementy organizacji są nierankingowe (niehierarchiczne) lub w których mają potencjał, aby być klasyfikowanym na wiele różnych sposobów” ( https: //en.wikipedia .org / wiki / Heterarchy lub głębsze, bardziej filozoficzne spojrzenie na heterarchię, patrz Kontopoulos, The Logics of Social Structure). Z empirycznego punktu widzenia analiza i modelowanie struktur sieciowych jest najbardziej reprezentatywne dla tego historycznego rozwoju w rozumieniu struktury (np. Książka Freemana The Development of Social Network Analysis ). Podczas gdy wielu analityków sieci będzie próbowało narzucić hierarchiczną strukturę wynikowej sieci, jest to bardziej wyraz zakorzenionych i nieświadomych założeń, niż stwierdzenie o empirycznej rzeczywistości struktury sieci multipleksowej w złożonym świecie.

Ta odpowiedź sugeruje, że łuk ewolucji prowadzący do rozwoju drzew decyzyjnych stworzył nowe pytania lub niezadowolenie z istniejących „nowoczesnych” metod na każdym etapie lub etapie procesu, wymagając nowych rozwiązań i nowych modeli. W tym przypadku niezadowolenie można zaobserwować w ograniczeniach modelowania dwóch grup (regresja logistyczna) i uznaniu potrzeby rozszerzenia tych ram na więcej niż dwie grupy. Niezadowolenia z niereprezentatywnych założeń leżących u podstaw rozkładu normalnego (analiza dyskryminacyjna lub AID), a także porównanie z względną „swobodą”, jaką można znaleźć w stosowaniu nieparametrycznych założeń i modeli bez rozkładu (np. CHAID i CART).

Jak sugerowano, początki drzew decyzyjnych prawie na pewno mają długą historię, która sięga wieków i jest rozproszona geograficznie. Wiele strumieni w historii ludzkości, nauce, filozofii i myśli można prześledzić w zarysie narracji prowadzącej do rozwoju wielu smaków drzew decyzyjnych, które istnieją dzisiaj. Będę pierwszym, który uzna znaczące ograniczenia mojego krótkiego szkicu tej historii.

/ ** Dodatki ** /

1. Artykuł z 2014 r. W New Scientist nosi tytuł Dlaczego lubimy organizować wiedzę w drzewa? ( https://www.newscientist.com/article/mg22229630-800-why-do-we-love-to-organise-knowledge-into-trees/ ), Jest to przegląd książki guru wizualizacji Manuela Limy The Book of Drzewa, które śledzą tysiąclecia wykorzystania drzew jako wizualizacji i mnemonicznej pomocy wiedzy. Wydaje się mało pytań, ale że świeckie i empiryczne modele i grafika związane z metodami takimi jak AID, CHAID i CART stanowią kontynuację ewolucji tej pierwotnie religijnej tradycji klasyfikacji.

2. W tym filmie (opublikowanym online przez Salford Systems, wdrażającym oprogramowanie CART), w hołdzie dla Leo Breimana , Breiman opowiada o rozwoju swojego sposobu myślenia, który doprowadził do metodologii CART. Wszystko zaczęło się od ściany oblepionej sylwetkami różnych pancerników z czasów II wojny światowej.

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. Czytając wprowadzenie do Teorii grafów skończonych i nieskończonych Denisa Koniga z 1936 r. , Powszechnie uważanej za zapewniającą pierwsze rygorystyczne, matematyczne uziemienie dla pola wcześniej postrzeganego jako źródło rozrywki i zagadek dla dzieci, zauważa Tutte (s. 13) ten rozdział 4 (od str. 62) książki Koniga poświęcono drzewom w teorii grafów. Wyjaśnienie Tigte'a definicji drzewa Koniga brzmi „tam, gdzie wykres„ acykliczny ”jest wykresem bez obwodu, drzewo jest skończonym połączonym wykresem acyklicznym ... innymi słowy, w drzewie istnieje tylko jedna ścieżka od przekazano wierzchołek innemu ... „Dla mnie (i nie jestem teoretykiem grafów ani matematykiem), to sugeruje, że teoria grafów i jej prekursory w analizie Poincare'a Situs lub Veblen” wykłady na temat kombinatorycznej topologii mogły dostarczyć wczesnych intelektualnych i matematycznych poprzedników tego, co później stało się tematem dla statystyków.

4. Pierwsze Drzewo Wiedzy jest szeroko przypisywane neoplatońskiemu filozofowi Porphyry'emu, który około 270 roku ne napisał Wprowadzenie do logiki, które wykorzystywało drzewo metaforyczne do opisywania i organizowania wiedzy ... http://www.historyofinformation.com/expanded.php? id = 3857

5. Właśnie odkryłem jeszcze wcześniejsze odniesienie do Drzewa Wiedzy w Księdze Rodzaju w Biblii, omówione w tym artykule Wiki ... https://en.wikipedia.org/wiki/Tree_of_life_(biblical) . Genesis prawdopodobnie pochodzi z 1400 pne na podstawie tego odniesienia ... https://www.biblica.com/bible/bible-faqs/when-was-the-bible-written/ Bez względu na to, Księga Rodzaju pojawiła się wiele wieków wcześniej Porfir.

Najważniejsze informacje na temat CART to:

Drzewa klasyfikacji i regresji
Leo Breiman, Jerome Friedman, Charles J. Stone, RA Olshen (1984)

ale z pewnością nie była to najwcześniejsza praca na ten temat.

W swojej pracy z 1986 r. Indukcja drzew decyzyjnych sam Quinlan identyfikuje Hunt's Concept Learning System (CLS) jako prekursora ID3. Umawia się z CLS w 1963 roku, ale referencje

EB Hunt, J.Marin, PJ Stone,
Experiments in Induction
Academic Press, Nowy Jork, 1966

Wei-Yin Loh z University of Wisconsin napisał o historii drzew decyzyjnych. Jest papier

Pięćdziesiąt lat drzew klasyfikacji i regresji Wei-Yin Loh International Statistics Review (2014), 82, 3, 329–348 doi: 10.1111 / insr.12016

Jest też talia Slide z przemówienia, które wygłosił na ten temat.