¿Quién inventó el árbol de decisión?

Estoy tratando de rastrear quién inventó la estructura de datos del árbol de decisión y el algoritmo.

En la entrada de Wikipedia sobre el aprendizaje del árbol de decisión hay una afirmación de que "ID3 y CART se inventaron de forma independiente aproximadamente al mismo tiempo (entre 1970 y 1980)". ID3 se presentó más tarde en:

• Quinlan, JR 1986. Inducción de árboles de decisión. Mach. Aprender. 1, 1 (marzo de 1986), 81-106

así que no estoy seguro de que la afirmación sea cierta.

Al usar los libros de Google, encontré una referencia a una serie de decisiones estadísticas del libro de 1959 y una colección de documentos de trabajo de 1958 . El contexto no está claro y no parecen presentar un algoritmo. Sin embargo, no definen la estructura de datos y la tratan como si fuera bien conocida.

Usando Google Scholar, encontré citas que datan de 1853, pero estos eran errores de análisis y no citas reales de esa fecha.

Buena pregunta. @ G5W está en el camino correcto al hacer referencia al artículo de Wei-Yin Loh. El artículo de Loh discute el estadística antecedentes de los árboles de decisión y, correctamente, rastrea su ubicación hasta el artículo de Fisher (1936) sobre análisis discriminante, esencialmente regresión clasificando múltiples grupos como la variable dependiente, y desde allí, a través de AID, THAID, CHAID y Modelos de carro.

La respuesta breve es que el primer artículo que pude encontrar que desarrolla un enfoque de "árbol de decisión" data de 1959 y un investigador británico, William Belson, en un artículo titulado Matching and Prediction on the Principle of Biological Classification , ( JRSS , Serie C, Estadísticas aplicadas, Vol. 8, Núm. 2, junio de 1959, págs. 65-75), cuyo resumen describe su enfoque como una de emparejar muestras de población y desarrollar criterios para hacerlo:

En este artículo, el Dr. Belson describe una técnica para unir muestras de población. Esto depende de la combinación de predictores desarrollados empíricamente para proporcionar el mejor compuesto predictivo o coincidente disponible. El principio subyacente es bastante distinto del inherente al método de correlación múltiple.

La respuesta "larga" es que otras corrientes de pensamiento, incluso anteriores, parecen relevantes aquí. Por ejemplo, los desgloses simples de cohortes de edad y género empleados en tablas actuariales de mortalidad ofrecen un marco para pensar sobre decisiones que datan de varios siglos. También se podría argumentar que los esfuerzos que se remontan a los babilonios empleaban ecuaciones cuadráticas, que no eran lineales en las variables (no en los parámetros, http://www-history.mcs.st-and.ac.uk/HistTopics/Quadratic_etc_equations. html ) tienen relevancia, al menos en la medida en que presagian modelos paramétricos de crecimiento logístico (reconozco que esto es una exageración jerarquía.comentario, sigue leyendo para obtener una motivación más completa). Además, los filósofos han reconocido y teorizado durante mucho tiempo acerca de la existencia de información cualitativa ordenada jerárquicamente, por ejemplo, el libro de Aristóteles sobre Categorías . El concepto y la suposición de a es clave aquí. Otros descubrimientos relevantes, mucho más tarde, fueron empujar más allá de los límites del espacio euclidiano 3-D en el desarrollo del infinito de David Hilbert, Hilbertespacio, combinatoria, descubrimientos en física relacionados con el espacio 4-D Minkowski, la distancia y el tiempo, la mecánica estadística detrás de la teoría de la relatividad especial de Einstein, así como las innovaciones en la teoría de la probabilidad relacionadas con modelos de cadenas de markov, transiciones y procesos. El punto aquí es que puede haber un retraso significativo entre cualquier teoría y su aplicación; en este caso, el retraso entre las teorías sobre la información cualitativa y los desarrollos relacionados con su evaluación empírica, predicción, clasificación y modelado.

Una mejor suposición es que estos desarrollos se pueden asociar con la historia de la creciente sofisticación de los estadísticos, principalmente en el siglo XX, en el desarrollo de modelos que aprovechan tipos de escala que no sean continuos (por ejemplo, información nominal o, más simplemente, categórica), modelos de datos de conteo (poisson), tablas de contingencia clasificadas cruzadas, estadísticas no paramétricas sin distribución, escalamiento multidimensional (p. ej., JG Carroll, entre otros), modelos con variables dependientes cualitativas como la regresión logística de dos grupos, así como el análisis de correspondencia (principalmente en Holanda y Francia en los años 70 y 80).

Existe una amplia literatura que discute y compara la regresión logística de dos grupos con el análisis discriminante de dos grupos y, para características completamente nominales, los encuentra proporcionando soluciones equivalentes (por ejemplo, Análisis multivariado de Dillon y Goldstein , 1984).

El artículo de JS Cramer sobre la historia de la regresión logística ( The History of Logistic Regression , http://papers.tinbergen.nl/02119.pdf ) lo describe como originario del desarrollo de la función logística univariada o la clásica curva en forma de S :

La supervivencia del término logístico y la amplia aplicación del dispositivo han sido determinadas decisivamente por las historias personales y las acciones individuales de algunos estudiosos ...

Los modelos deterministas de la curva logística se originaron en 1825, cuando Benjamin Gompertz ( https://en.wikipedia.org/wiki/Benjamin_Gompertz ) publicó un documento que desarrolla el primer modelo logístico verdaderamente no lineal (no lineal en los parámetros y no solo las variables como con los babilonios): el modelo y la curva de Gompertz.

Sugeriría que otro eslabón importante en esta cadena que condujo a la invención de los árboles de decisión fue el trabajo del sociólogo de Columbia Paul Lazarsfeld sobre modelos de estructuras latentes. Su trabajo comenzó en los años 30, continuó durante la Segunda Guerra Mundial con su análisis de contenido de periódicos alemanes para el naciente OSS (más tarde la CIA, como se discute en el libro Megatrends de John Naisbett ) y finalmente publicado en 1950. Andersen lo describe de esta manera ( Análisis de estructura latente: A Survey , Erling B. Andersen, Scandinavian Journal of Statistics , Vol. 9, No. 1, 1982, pp. 1-12):

La base de la teoría clásica del análisis de la estructura latente fue desarrollada por Paul Lazarsfeld en 1950 en un estudio sobre el etnocentrismo de los soldados estadounidenses durante la Segunda Guerra Mundial. Lazarsfeld estaba principalmente interesado en desarrollar la base conceptual de los modelos de estructura latente ... Los métodos estadísticos desarrollados por Lazarsfeld fueron, sin embargo, bastante primitivos ... El colega de Lazarsfeld de la Universidad de Columbia hizo un intento temprano de obtener métodos de estimación eficientes y procedimientos de prueba. , TW Anderson, quien en un artículo ( Psychometrika , marzo de 1954, Volumen 19, Número 1, págs. 1-10, Sobre la estimación de parámetros en el análisis de estructura latente), desarrolló un método de estimación eficiente para los parámetros del modelo de clase latente ... Para introducir el marco (de los modelos de clase latente) describiremos brevemente los conceptos básicos ... y utilizaremos un sistema de notación desarrollado mucho más tarde por Goodman (1974a) ... Los datos se dan en forma de una tabla de contingencia múltiple ...

Hay una distinción útil que vale la pena hacer aquí, ya que puede relacionarse con la progresión de AID a CHAID (luego CART), entre modelos basados ​​en tablas de contingencia (todas las variables en el modelo tienen una escala nominal) y modelos de clase latente más recientes (más precisamente, modelos de mezclas finitas basadas en "mezclas" de escalas y distribuciones, por ejemplo, Kamakura y Russell, 1989, Un modelo de elección probabilística para la segmentación del mercado y la estructura de elasticidad.) en cómo crean los residuos del modelo. Para los modelos de tablas de contingencia más antiguos, los recuentos de células inherentes a la tabla de clasificación cruzada completa formaron la base para las "replicaciones" y, por lo tanto, la heterogeneidad en los residuos del modelo utilizados en la división en clases. Por otro lado, los modelos de mezcla más recientes se basan en medidas repetidas en un solo sujeto como base para dividir la heterogeneidad en los residuos. Esta respuesta es nosugiriendo una conexión directa entre los modelos de clase latentes y los árboles de decisión. La relevancia para AID y CHAID se puede resumir en las estadísticas empleadas para evaluar los modelos, AID usa una distribución F continua mientras que CHAID usa la distribución de chi-cuadrado, apropiada para información categórica. Más bien en su análisis y modelado de tablas de contingencia, los MCM constituyen, en mi opinión, una pieza importante en el rompecabezas o la narrativa que conducen al desarrollo de los árboles de decisión, junto con las muchas otras innovaciones ya mencionadas.

CHAID fue un desarrollo posterior, propuesto por primera vez en una tesis doctoral de 1980 por el sudafricano Gordon Kass como se describe en este artículo de Wiki sobre CHAID ( https://en.wikipedia.org/wiki/CHAID ). Por supuesto, CART llegó unos años más tarde en los años 80 con Breiman, et al., Ahora famoso libro Clasificación y árboles de regresión .

AID, CHAID y CART postulan estructuras jerárquicas en forma de árbol como la representación óptima de la realidad. Simplemente hacen esto usando diferentes algoritmos y métodos. Para mí, los próximos pasos en esta cadena progresiva de innovación son el surgimiento de teorías de estructura heterarquicas. Como se define en este artículo de Wiki, las heterarquías "son un sistema de organización donde los elementos de la organización están sin clasificar (no jerárquicos) o donde poseen el potencial de ser clasificados de diferentes maneras" ( https: //en.wikipedia .org / wiki / Heterarchy o para una perspectiva más profunda y filosófica sobre la heterarquía ver Kontopoulos, The Logics of Social Structure) Desde un punto de vista empírico, el análisis y la modelización de las estructuras de red son los más representativos de este desarrollo histórico en la comprensión de la estructura (por ejemplo, el libro de Freeman El desarrollo del análisis de redes sociales ). Si bien muchos analistas de redes intentarán forzar un arreglo jerárquico en la red resultante, esto es más una expresión de suposiciones arraigadas e inconscientes que una declaración sobre la realidad empírica de la estructura de red multiplex en un mundo complejo.

Esta respuesta sugiere que el arco de la evolución que condujo al desarrollo de los árboles de decisión creó nuevas preguntas o insatisfacción con los métodos "de vanguardia" existentes en cada paso o fase del proceso, lo que requiere nuevas soluciones y nuevos modelos. En este caso, pueden observarse insatisfacciones en las limitaciones de modelar dos grupos (regresión logística) y reconocer la necesidad de ampliar ese marco a más de dos grupos. Insatisfacción con los supuestos no representativos de una distribución normal subyacente (análisis discriminante o AID), así como la comparación con la relativa "libertad" que se encuentra en el empleo de supuestos y modelos no paramétricos, libres de distribución (por ejemplo, CHAID y CART).

Como se sugirió, los orígenes de los árboles de decisión casi seguramente tienen una larga historia que se remonta a siglos y está geográficamente dispersa. Se pueden rastrear múltiples corrientes en la historia humana, la ciencia, la filosofía y el pensamiento al delinear la narrativa que conduce al desarrollo de los muchos sabores de los árboles de decisión existentes hoy en día. Seré el primero en reconocer las limitaciones significativas de mi breve esbozo de esta historia.

/ ** Addendums ** /

1. Este artículo de 2014 en New Scientist se titula ¿Por qué nos encanta organizar el conocimiento en árboles? ( https://www.newscientist.com/article/mg22229630-800-why-do-we-love-to-organise-knowledge-into-trees/ ), es una revisión del libro del gurú de visualización de datos Manuel Lima El libro de Árboles que rastrean el uso milenario de los árboles como visualización y ayuda mnemónica para el conocimiento. Parece que hay pocas dudas, pero que los modelos y gráficos seculares y empíricos inherentes a métodos como AID, CHAID y CART representan la evolución continua de esta tradición de clasificación originalmente religiosa.

2. En este video (publicado en línea por Salford Systems, implementadores del software CART), A Tribute to Leo Breiman , Breiman habla sobre el desarrollo de su pensamiento que condujo a la metodología CART. Todo comenzó con un muro cubierto con las siluetas de diferentes acorazados de la 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

3. Al leer la introducción a la Teoría de los gráficos finitos e infinitos de 1936 de Denis Konig , ampliamente visto como el primer fundamento matemático riguroso para un campo previamente visto como una fuente de diversión y rompecabezas para los niños, Tutte señala (p. 13) ese capítulo 4 (comenzando en la página 62) del libro de Konig está dedicado a los árboles en la teoría de grafos. La explicación de Tutte de la definición de Konig de un árbol es "donde un gráfico 'acíclico' es un gráfico sin circuito, un árbol es un gráfico acíclico finito conectado ... en otras palabras, en un árbol hay un único camino desde un dado vértice a otro ... "Para mí (y no soy ni un teórico de gráficos ni un matemático), esto sugiere que la teoría de gráficos y sus precursores en el Análisis de Poincare Situs o Veblen ' Las conferencias sobre topología combinatoria pueden haber proporcionado los primeros antecedentes intelectuales y matemáticos de lo que más tarde se convirtió en un tema para los estadísticos.

4. El primer árbol del conocimiento se atribuye ampliamente al filósofo neoplatónico Pórfido que, alrededor del año 270 CE, escribió una Introducción a la lógica que utilizaba un árbol metafórico para describir y organizar el conocimiento ... http://www.historyofinformation.com/expanded.php? id = 3857

5. Acabo de descubrir una referencia incluso anterior a un Árbol del Conocimiento en el Libro del Génesis en la Biblia, discutida en este artículo de Wiki ... https://en.wikipedia.org/wiki/Tree_of_life_(biblical) . Génesis probablemente data de 1.400 a. C. según esta referencia ... https://www.biblica.com/bible/bible-faqs/when-was-the-bible-written/ Independientemente, el Libro de Génesis apareció muchos siglos antes Pórfido.

La gran referencia en CART es:

Árboles de clasificación y regresión
Leo Breiman, Jerome Friedman, Charles J. Stone, RA Olshen (1984)

pero ese ciertamente no fue el primer trabajo sobre el tema.

En su artículo de 1986, Induction of Decision Trees , el propio Quinlan identifica el Sistema de Aprendizaje Conceptual (CLS) de Hunt como precursor de ID3. Sale con CLS en 1963, pero hace referencia a

EB Hunt, J.Marin, PJ Stone,
Experimentos en Induction
Academic Press, Nueva York, 1966

Wei-Yin Loh, de la Universidad de Wisconsin, ha escrito sobre la historia de los árboles de decisión. Hay un papel

Cincuenta años de árboles de clasificación y regresión Revisión estadística internacional de Wei-Yin Loh (2014), 82, 3, 329–348 doi: 10.1111 / insr.12016

También hay una presentación de diapositivas de una charla que dio sobre el tema.