Árbol de decisión incremental

Un algoritmo de árbol de decisión incremental es un algoritmo de aprendizaje automático en línea que genera un árbol de decisión . Muchos métodos de árboles de decisión , como C4.5 , construyen un árbol utilizando un conjunto de datos completo. Los métodos de árbol de decisión incremental permiten actualizar un árbol existente utilizando únicamente nuevas instancias de datos individuales, sin tener que volver a procesar instancias anteriores. Esto puede resultar útil en situaciones en las que todo el conjunto de datos no está disponible cuando se actualiza el árbol (es decir, los datos no se almacenaron), el conjunto de datos original es demasiado grande para procesarlo o las características de los datos cambian con el tiempo.

Aplicaciones

• Aprender en línea
• Flujos de datos
• Deriva conceptual
• Datos que se pueden modelar bien utilizando un modelo jerárquico.
• Sistemas donde se desea un resultado interpretable por el usuario.

Métodos

A continuación se muestra una breve lista de métodos de árboles de decisión incrementales, organizados por sus algoritmos principales (generalmente no incrementales).

familia de carritos

CART ^[1] (1984) es un inductor de árbol de decisión no incremental para problemas de clasificación y regresión. desarrollado en las comunidades de matemáticas y estadística. CART tiene sus raíces en AID (1963) ^[2]

• CART incremental (1989) ^[3] Crawford modificó CART para incorporar datos de forma incremental.

Familia ID3/C4.5

ID3 (1986) ^[4] y C4.5 (1993) ^[5] fueron desarrollados por Quinlan y tienen sus raíces en el Concept Learning System de Hunt (CLS, 1966) ^[6] La familia ID3 de inductores de árboles se desarrolló en los sectores de ingeniería e informática. comunidades científicas.

• ID3' (1986) ^[7] fue sugerido por Schlimmer y Fisher. Fue un método de fuerza bruta para hacer que ID3 fuera incremental; Después de adquirir cada nueva instancia de datos, se induce un árbol completamente nuevo utilizando ID3.
• ID4 (1986) ^[7] podría incorporar datos de forma incremental. Sin embargo, ciertos conceptos no se pudieron aprender porque ID4 descarta subárboles cuando se elige una nueva prueba para un nodo.
• ID5 (1988) ^[8] no descartó subárboles, pero tampoco garantizó que produciría el mismo árbol que ID3.
• ID5R (1989) ^[9] genera el mismo árbol que ID3 para un conjunto de datos independientemente del orden de entrenamiento incremental. Esto se logró actualizando recursivamente los subnodos del árbol. No manejaba variables numéricas, tareas de clasificación multiclase ni valores faltantes.
• ID6MDL (2007) ^[10] una versión extendida de los algoritmos ID3 o ID5R.
• ITI (1997) ^[11] es un método eficaz para inducir incrementalmente árboles de decisión. Se produce el mismo árbol para un conjunto de datos independientemente del orden de presentación de los datos o de si el árbol se induce de forma incremental o no incremental ( modo por lotes ). Puede acomodar variables numéricas, tareas multiclase y valores faltantes. El código está disponible en la web. [1]

nota: ID6NB (2009) ^[12] no es incremental.

Otros sistemas de aprendizaje incremental

Hubo varios sistemas de aprendizaje de conceptos incrementales que no construyeron árboles de decisión, pero que fueron anteriores e influyeron en el desarrollo de los primeros aprendices de árboles de decisión incrementales, en particular ID4. ^[7] Entre ellos destaca el STAGGER de Schlimmer y Granger (1986), ^[13] que aprendió conceptos disyuntivos de forma incremental. STAGGER fue desarrollado para examinar conceptos que cambiaron con el tiempo ( deriva de conceptos ). Antes de STAGGER, Michalski y Larson (1978) ^[14] investigaron una variante incremental de AQ (Michalski, 1973), ^[15] un sistema supervisado para aprender conceptos en forma normal disyuntiva (DNF). La experiencia con estos sistemas anteriores y otros, para incluir el aprendizaje incremental no supervisado con estructura de árbol, contribuyó a un marco conceptual para evaluar específicamente a los estudiantes del árbol de decisión incremental, y el aprendizaje incremental de conceptos en general, a lo largo de cuatro dimensiones que reflejan las compensaciones inherentes entre el costo y la calidad del aprendizaje: ^[7] (1) el costo de la actualización de la base de conocimientos, (2) el número de observaciones que se requieren para converger en una base de conocimientos con características dadas, (3) el esfuerzo total (en función de las dos primeras dimensiones) que un que ejerce el sistema y la (4) calidad (a menudo coherencia) de la base de conocimientos final. Parte del contexto histórico en el que surgieron los aprendices de árboles de decisión incremental se presenta en Fisher y Schlimmer (1988), ^[16] y que también amplía el marco de cuatro factores que se utilizó para evaluar y diseñar sistemas de aprendizaje incremental .

Algoritmo VFDT

El alumno de Very Fast Decision Trees reduce el tiempo de capacitación para grandes conjuntos de datos incrementales al submuestrear el flujo de datos entrante.

• VFDT (2000) ^[17]
• CVFDT (2001) ^[18] puede adaptarse a la deriva de conceptos mediante el uso de una ventana deslizante en los datos entrantes. Se olvidan los datos antiguos fuera de la ventana.
• VFDTc (2006) ^[19] extiende VFDT para datos continuos, deriva de conceptos y aplicación de clasificadores Naive Bayes en las hojas.
• VFML (2003) es un conjunto de herramientas y está disponible en la web. [2]. Fue desarrollado por los creadores de VFDT y CVFDT.

Algoritmo EFDT

El alumno de árbol de decisión extremadamente rápido ^[20] es estadísticamente más potente que VFDT, lo que le permite aprender árboles más detallados a partir de menos datos. Se diferencia de VFDT en el método para decidir cuándo insertar una nueva rama en el árbol. VFDT espera hasta estar seguro de que la mejor sucursal disponible es mejor que cualquier alternativa. Por el contrario, EFDT se divide tan pronto como confía en que la mejor sucursal disponible es mejor que la alternativa actual. Inicialmente, la alternativa actual es no tener sucursal. Esto permite a EFDT insertar ramas mucho más rápidamente que VFDT. Durante el aprendizaje incremental, esto significa que EFDT puede implementar árboles útiles mucho antes que VFDT.

Sin embargo, el nuevo método de selección de sucursales aumenta en gran medida la probabilidad de seleccionar una sucursal subóptima. En consecuencia, EFDT sigue monitoreando el desempeño de todas las sucursales y reemplazará una sucursal tan pronto como esté seguro de que existe una alternativa mejor.

OLIN y IFN

• OLÍN (2002) ^[21]
• IOLIN (2008) ^[22] - basado en Info-Fuzzy Network (IFN) ^[23]

GAENARI

• gaenari

Ver también

• Deriva conceptual
• Árbol de decisión
• Aprendizaje automático
• Aprender en línea

Referencias

1. Breiman, L.; Friedman, JH; Olshen, RA; Piedra, CJ (1984). Árboles de clasificación y regresión. Belmont, CA: Wadsworth Internacional. ISBN 978-1-351-46048-4.
2. Morgan, JN; Sondquist, JA (1963). «Problemas en el análisis de datos de encuestas, y una propuesta» (PDF) . J.Amer. Estadístico. Asociación . 58 (302): 415–434. doi :10.1080/01621459.1963.10500855.
3. Crawford, SL (1989). "Extensiones al algoritmo CART". Revista Internacional de Estudios Hombre-Máquina . 31 (2): 197–217. doi :10.1016/0020-7373(89)90027-8.
4. Quinlan, JR (1986). «Inducción de Árboles de Decisión» (PDF) . Aprendizaje automático . 1 (1): 81–106. doi :10.1007/BF00116251. S2CID  13252401.
5. Quinlan, JR (2014) [1993]. C4.5: Programas para aprendizaje automático. Elsevier. ISBN 978-1-55860-238-0.
6. Caza, EB; Marín, J.; Piedra, PJ (1966). Experimentos de inducción . Prensa académica. ISBN 978-0-12-362350-8.
7. Schlimmer, JC; Pescador, D. (1986). "Un estudio de caso de inducción de conceptos incrementales". AAAI'86: Actas de la Quinta Conferencia Nacional sobre Inteligencia Artificial. Morgan Kaufman. págs. 496–501.
8. Utgoff, PE (1988). "ID5: un ID3 incremental" (PDF) . Actas de aprendizaje automático 1988 Actas de la Quinta Conferencia Internacional sobre Aprendizaje Automático . Morgan Kaufman. págs. 107-120. doi :10.1016/B978-0-934613-64-4.50017-7. ISBN 978-0-934613-64-4.Editores.
9. Utgoff, PE (1989). «Inducción incremental de árboles de decisión» (PDF) . Aprendizaje automático . 4 (2): 161–186. doi :10.1023/A:1022699900025. S2CID  5293072.
10. Kroon, M., Korzec, S., Adriani, P. (2007) ID6MDL: árboles de decisión incrementales posteriores a la poda.
11. Utgoff, PE; Berkman, Carolina del Norte; Clouse, JA (1997). "Inducción de árboles de decisión basada en una reestructuración eficiente de árboles" (PDF) . Aprendizaje automático . 29 : 5–44. doi :10.1023/A:1007413323501. S2CID  2743403.
12. Appavu, S.; Rajaram, R. (2009). "Sistema basado en conocimiento para clasificación de textos mediante algoritmo ID6NB]". Sistemas basados ​​en el conocimiento . 22 (1): 1–7. doi :10.1016/j.knosys.2008.04.006.
13. Schlimmer, JC; Granger, Jr., RH (1986). "Aprendizaje incremental a partir de datos ruidosos". Aprendizaje automático . 1 (3): 317–354. doi : 10.1007/BF00116895 . S2CID  33776987.
14. Michalski, RS; Larson, JB (1978). Selección de ejemplos de formación más representativos y generación incremental de hipótesis de VL: La metodología subyacente y la descripción de los programas ESEL y AQ11 (PDF) (Informe técnico). Universidad de Illinois, Departamento de Ciencias de la Computación. hdl :1920/1544/78-03. UIUCDCS-R-78-867.
15. Michalski, RS (1973). "Descubrimiento de reglas de clasificación utilizando el sistema lógico de valores variables VL1" (PDF) . IJCAI'73: Actas de la Tercera Conferencia Internacional Conjunta sobre Inteligencia Artificial. Stanford, California: Morgan Kaufmann. págs. 162-172. hdl :1920/1515/73-01.
16. Pescador, D.; Schlimmer, J. (1988). Modelos de aprendizaje incremental de conceptos: una propuesta de investigación acoplada (Informe técnico). Universidad de Vanderbilt. CS-88-05.
17. Domingos, P.; Hulten, G. (2000). "Minería de flujos de datos de alta velocidad" (PDF) . Actas KDD Actas de la sexta conferencia internacional ACM SIGKDD sobre descubrimiento de conocimiento y minería de datos . Prensa ACM. págs. 71–80. doi :10.1145/347090.347107. ISBN 1-58113-233-6. S2CID  8810610.
18. Hulten, G.; Spencer, L.; Domingos, P. (2001). "Extracción de flujos de datos que cambian en el tiempo" (PDF) . Actas de la séptima conferencia internacional ACM SIGKDD sobre descubrimiento de conocimiento y minería de datos . Prensa ACM. págs. 97-106. doi :10.1145/502512.502529. ISBN 978-1-58113-391-2. S2CID  6416602.
19. Gama, J.; Fernández, R.; Rocha, R. (2006). "Árboles de decisión para extraer flujos de datos". Análisis inteligente de datos . 10 : 23–45. doi :10.3233/IDA-2006-10103.
20. Manapragada, C.; Webb, GI; Salehi, M. (2018). "Árbol de decisiones extremadamente rápido". KDD '18: Actas de la 24.ª Conferencia internacional ACM SIGKDD sobre descubrimiento de conocimientos y minería de datos . Prensa ACM. págs. 1953–62. arXiv : 1802.08780 . doi :10.1145/3219819.3220005. ISBN 978-1-4503-5552-0. S2CID  3513409.
21. Por último, M. (2002). "Clasificación online de flujos de datos no estacionarios" (PDF) . Intel. Análisis de datos . 6 (2): 129-147. doi :10.3233/IDA-2002-6203.
22. Cohen, L.; Avrahami, G.; Por último, M.; Kandel, A. (2008). "Algoritmos de información difusa para extraer flujos de datos dinámicos" (PDF) . Computación blanda aplicada . 8 (4): 1283–94. doi :10.1016/j.asoc.2007.11.003.
23. Maimón, O.; Por último, M. (2000). La metodología de la red info-difusa (IFN). Descubrimiento de conocimiento y minería de datos . Kluwer. doi :10.1007/978-1-4757-3296-2. ISBN 978-1-4757-3296-2. S2CID  41520652.

enlaces externos

• Código ITI. http://www-lrn.cs.umass.edu/iti/index.html
• Código VFML. http://www.cs.washington.edu/dm/vfml/
• Árbol de decisión incremental de C++. https://github.com/greenfish77/gaenari