Estou tentando rastrear quem inventou a estrutura de dados e o algoritmo da árvore de decisão.
Na entrada da Wikipedia sobre aprendizado de árvore de decisão, há uma alegação de que "ID3 e CART foram inventados de forma independente na mesma época (entre 1970 e 1980)". O ID3 foi apresentado posteriormente em:
- Quinlan, JR 1986. Indução de árvores de decisão. Mach. Aprender. 1, 1 (março de 1986), 81-106
portanto, não tenho certeza se a afirmação é verdadeira.
Encontrei usando os livros do Google uma referência a uma série de decisões estatísticas de livros de 1959 e a uma coleção de documentos de trabalho de 1958 . O contexto não é claro e eles não parecem apresentar um algoritmo. No entanto, eles não definem a estrutura de dados e a tratam como se fosse bem conhecida.
Usando o Google Scholar, encontrei citações que remontam a 1853, mas esses eram erros de análise e não citações reais a partir dessa data.
Classification and Regression Trees Leo Breiman, Jerome Friedman, Charles J. Stone, R.A. Olshen (1984)mas certamente não foi a primeira. Wei-Yin Loh, da Universidade de Wisconsin, escreveu sobre a história das árvores de decisão. Aqui estão um artigo e alguns slides da história.Respostas:
Boa pergunta. @ G5W está no caminho certo ao fazer referência ao artigo de Wei-Yin Loh. O artigo de Loh discute os antecedentes estatísticos das árvores de decisão e, corretamente, remonta ao artigo de Fisher (1936) sobre análise discriminante - essencialmente regressão classificando vários grupos como a variável dependente - e a partir daí, através de AID, THAID, CHAID e Modelos de carrinho.
A resposta curta é que o primeiro artigo que pude encontrar que desenvolve uma abordagem de "árvore de decisão" data de 1959 e um pesquisador britânico, William Belson, em um artigo intitulado Correspondência e Previsão sobre o Princípio da Classificação Biológica ( JRSS , Série C, Estatística Aplicada, Vol. 8, Nº 2, Junho de 1959, pp. 65-75), cujo resumo descreve sua abordagem como uma das amostras populacionais correspondentes e do desenvolvimento de critérios para fazê-lo:
A resposta "longa" é que outras correntes de pensamento anteriores ainda parecem relevantes aqui. Por exemplo, os simples rompimentos de coorte idade-sexo empregados em tabelas atuariais de mortalidade oferecem uma estrutura para pensar em decisões que remontam a vários séculos. Também se poderia argumentar que os esforços que remontam aos babilônios empregavam equações quadráticas, que não eram lineares nas variáveis (não nos parâmetros, http://www-history.mcs.st-and.ac.uk/HistTopics/Quadratic_etc_equations). html ) têm relevância, pelo menos na medida em que pressagiam modelos paramétricos de crescimento logístico (reconheço que esse é um trechocomentário, continue lendo para uma motivação mais completa). Além disso, os filósofos há muito reconhecem e teorizam sobre a existência de informações qualitativas e hierarquicamente organizadas, por exemplo, o livro de Aristóteles sobre categorias . O conceito e suposição de uma hierarquia é fundamental aqui. Outras descobertas relevantes e muito posteriores foram além das fronteiras do espaço euclidiano 3D no desenvolvimento do infinito, Hilbert , de David Hilbertespaço, combinatória, descobertas em física relacionadas ao espaço 4-D de Minkowski, distância e tempo, a mecânica estatística por trás da teoria da relatividade especial de Einstein, bem como inovações na teoria da probabilidade relacionada a modelos de cadeias, transições e processos de markov. O ponto aqui é que pode haver um atraso significativo entre qualquer teoria e sua aplicação - nesse caso, o atraso entre as teorias sobre informações qualitativas e desenvolvimentos relacionados à sua avaliação empírica, previsão, classificação e modelagem.
O melhor palpite é que esses desenvolvimentos podem ser associados ao histórico de sofisticação crescente dos estatísticos, principalmente no século XX, no desenvolvimento de modelos que utilizam tipos de escala diferentes de contínuos (por exemplo, informações nominais ou, mais simplesmente, categóricas), contam modelos de dados (poisson), tabelas de contingência cruzadas, estatísticas não paramétricas livres de distribuição, escala multidimensional (por exemplo, JG Carroll, entre outros), modelos com variáveis dependentes qualitativas, como regressão logística de dois grupos, bem como análise de correspondência (principalmente na Holanda e na França) nos anos 70 e 80).
Existe uma ampla literatura que discute e compara a regressão logística de dois grupos com a análise discriminante de dois grupos e, para características totalmente nominais, as encontra fornecendo soluções equivalentes (por exemplo, Multivariate Analysis , Dillon e Goldstein , 1984).
O artigo de JS Cramer sobre a história da regressão logística ( The History of Logistic Regression , http://papers.tinbergen.nl/02119.pdf ) o descreve como originário do desenvolvimento da função logística univariada ou da curva clássica em forma de S :
Os modelos determinísticos da curva logística se originaram em 1825, quando Benjamin Gompertz ( https://en.wikipedia.org/wiki/Benjamin_Gompertz ) publicou um artigo desenvolvendo o primeiro modelo logístico verdadeiramente não linear (não linear nos parâmetros e não apenas nas variáveis como em os babilônios) - o modelo e a curva de Gompertz.
Eu sugeriria que outro elo importante nessa cadeia que levou à invenção das árvores de decisão foi o trabalho do sociólogo da Columbia Paul Lazarsfeld sobre modelos de estruturas latentes. Seu trabalho começou nos anos 30, continuou durante a Segunda Guerra Mundial com sua análise de conteúdo de jornais alemães para o nascente OSS (mais tarde a CIA, como discutido no livro de John Naisbett, Megatrends ) e finalmente publicado em 1950. Andersen descreve desta maneira ( Análise de Estrutura Latente: A Survey , Erling B. Andersen, Scandinavian Journal of Statistics , Vol. 9, No. 1, 1982, pp. 1-12):
Há uma distinção útil que vale a pena fazer aqui, pois pode estar relacionada à progressão do AID para o CHAID (mais tarde CART), entre modelos baseados em tabelas de contingência (todas as variáveis no modelo são dimensionadas nominalmente) e modelos mais recentes de classes latentes (mais precisamente, modelos de mistura finita baseados em "misturas" de escalas e distribuições, por exemplo, Kamakura e Russell, 1989, Um Modelo de Escolha Probabilística para Segmentação de Mercado e Estrutura de Elasticidade) em como eles criam os resíduos do modelo. Para os modelos de tabela de contingência mais antigos, as contagens de células inerentes à tabela de classificação cruzada completa formaram a base para as "replicações" e, portanto, a heterogeneidade nos resíduos do modelo usados no particionamento em classes. Por outro lado, os modelos de mistura mais recentes contam com medidas repetidas em um único assunto como base para particionar a heterogeneidade nos resíduos. Esta resposta não ésugerindo uma conexão direta entre modelos de classes latentes e árvores de decisão. A relevância para o AID e o CHAID pode ser resumida nas estatísticas empregadas para avaliar os modelos; o AID usa uma distribuição F contínua, enquanto o CHAID usa a distribuição qui-quadrado, apropriada para informações categóricas. Antes, em sua análise e modelagem de tabelas de contingência, os LCMs constituem, na minha opinião, uma peça importante no quebra-cabeça ou narrativa que antecedeu o desenvolvimento de árvores de decisão, juntamente com muitas outras inovações já observadas.
O CHAID foi um desenvolvimento posterior, proposto pela primeira vez em uma dissertação de doutorado em 1980 pelo sul-africano Gordon Kass, conforme descrito neste artigo da Wiki sobre o CHAID ( https://en.wikipedia.org/wiki/CHAID ). Obviamente, a CART surgiu alguns anos depois nos anos 80 com Breiman et al., Agora famoso livro Classification and Regression Trees .
AID, CHAID e CART postulam estruturas arranjadas hierarquicamente em forma de árvore como a representação ideal da realidade. Eles apenas fazem isso usando algoritmos e métodos diferentes. Para mim, os próximos passos nesta cadeia progressiva de inovação são o surgimento de teorias heterárquicas de estrutura. Conforme definido neste artigo da Wiki, as heterarquias "são um sistema de organização em que os elementos da organização são desorganizados (não hierárquicos) ou onde eles possuem o potencial de serem classificados de várias maneiras diferentes" ( https: //en.wikipedia .org / wiki / Heterarquia ou para uma perspectiva mais profunda e filosófica sobre a heterarquia, consulte Kontopoulos, The Logics of Social Structure) Do ponto de vista empírico, a análise e modelagem das estruturas de rede são mais representativas desse desenvolvimento histórico no entendimento da estrutura (por exemplo, o livro de Freeman, The Development of Social Network Analysis ). Embora muitos analistas de rede tentem forçar um arranjo hierárquico na rede resultante, isso é mais uma expressão de suposições arraigadas e inconscientes do que uma declaração sobre a realidade empírica da estrutura de rede multiplex em um mundo complexo.
Essa resposta está sugerindo que o arco da evolução que levou ao desenvolvimento de árvores de decisão criou novas questões ou insatisfação com os métodos "de ponta" existentes em cada etapa ou fase do processo, exigindo novas soluções e novos modelos. Nesse caso, as insatisfações podem ser vistas nas limitações da modelagem de dois grupos (regressão logística) e no reconhecimento de uma necessidade de ampliar essa estrutura para mais de dois grupos. Insatisfações com suposições não representativas de uma distribuição normal subjacente (análise discriminante ou AID), bem como comparação com a "liberdade" relativa a ser encontrada no emprego de suposições e modelos não paramétricos e sem distribuição (por exemplo, CHAID e CART).
Como sugerido, as origens das árvores de decisão quase certamente têm uma longa história que remonta a séculos e está geograficamente dispersa. Múltiplos fluxos na história humana, ciência, filosofia e pensamento podem ser traçados no esboço da narrativa que levou ao desenvolvimento dos muitos sabores das árvores de decisão existentes hoje. Serei o primeiro a reconhecer as limitações significativas do meu breve esboço desta história.
/ ** Adendos ** /
Este artigo de 2014 no New Scientist é intitulado Por que amamos organizar o conhecimento em árvores? ( https://www.newscientist.com/article/mg22229630-800-why-do-we-love-to-organise-knowledge-into-trees/ ), é uma revisão do livro do guru da visualização de dados, Manuel Lima, The Book of Árvores que traçam o uso milenar de árvores como uma visualização e auxílio mnemônico para o conhecimento. Parece haver pouca dúvida, mas que os modelos e gráficos seculares e empíricos inerentes a métodos como AID, CHAID e CART representam a evolução contínua dessa tradição de classificação originalmente religiosa.
Neste vídeo (publicado on-line por Salford Systems, implementadores do software CART), um tributo a Leo Breiman , Breiman fala sobre o desenvolvimento de seu pensamento que levou à metodologia CART. Tudo começou com uma parede estampada com silhuetas de diferentes navios de guerra da Segunda Guerra Mundial.
https://www.salford-systems.com/videos/conferences/cart-founding-fathers/a-tribute-to-leo-breiman?utm_source=linkedin&utm_medium=social&utm_content=3599323
Ao ler a introdução da Teoria dos gráficos finitos e infinitos , de Denis Konig, de 1936 , amplamente vista como o primeiro fundamento rigoroso e matemático a um campo anteriormente visto como fonte de diversão e quebra-cabeças para crianças, Tutte observa (p. 13) esse capítulo. 4 (começando na p. 62) do livro de Konig é dedicado às árvores na teoria dos grafos. A explicação de Tutte da definição de árvore de Konig é "onde um gráfico 'acíclico' é um gráfico sem circuito, uma árvore é um gráfico acíclico finito conectado ... em outras palavras, em uma árvore existe um e apenas um caminho de um dado vértice a outro ... "Para mim (e eu não sou um teórico dos grafos nem um matemático), isso sugere que a teoria dos grafos e seus precursores nas análises Situs ou Veblen 'de Poincare " palestras sobre topologia combinatória, podem ter fornecido os antecedentes intelectuais e matemáticos para o que mais tarde se tornou um tópico para estatísticos.
A primeira Árvore do Conhecimento é amplamente atribuída ao filósofo neoplatônico Porfírio, que, por volta de 270 EC, escreveu uma Introdução à Lógica que usava uma árvore metafórica para descrever e organizar o conhecimento ... http://www.historyofinformation.com/expanded.php? id = 3857
Acabei de descobrir uma referência ainda mais antiga a uma Árvore do Conhecimento no Livro de Gênesis na Bíblia, discutida neste artigo da Wiki ... https://en.wikipedia.org/wiki/Tree_of_life_(biblical) . O Gênesis provavelmente remonta a 1.400 AEC, com base nessa referência ... https://www.biblica.com/bible/bible-faqs/when-was-the-bible-written/ Independentemente disso, o Livro do Gênesis veio muitos séculos antes Pórfiro.
fonte
A grande referência no CART é:
mas esse certamente não foi o primeiro trabalho sobre o assunto.
Em seu artigo de 1986, Induction of Decision Trees , o próprio Quinlan identifica o Hunt's Concept Learning System (CLS) como um precursor do ID3. Ele data o CLS em 1963, mas referências
Wei-Yin Loh, da Universidade de Wisconsin, escreveu sobre a história das árvores de decisão. Existe um documento
Há também um deck de slides de uma palestra que ele deu sobre o assunto.
fonte