Á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 árbol 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 solo nuevas instancias de datos individuales, sin tener que volver a procesar instancias anteriores. Esto puede ser útil en situaciones en las que el conjunto de datos completo 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

• Aprendizaje en línea
• Flujos de datos
• Deriva conceptual
• Datos que pueden modelarse bien utilizando un modelo jerárquico.
• Sistemas en los que se desea una salida interpretable por el usuario.

Métodos

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

Familia CART

CART ^[1] (1984) es un inductor de árboles de decisión no incremental para problemas de clasificación y regresión. Fue desarrollado en las comunidades de matemáticas y estadísticas. 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 Sistema de aprendizaje de conceptos de Hunt (CLS, 1966) ^[6]. La familia ID3 de inductores de árboles se desarrolló en las comunidades de ingeniería y ciencias de la computación.

• Schlimmer y Fisher sugirieron ID3' (1986) ^{[7] . Se trataba de un método de fuerza bruta para hacer que ID3 fuera incremental; después de adquirir cada nueva instancia de datos, se inducía un árbol completamente nuevo utilizando ID3.}
• ID4 (1986) ^[7] podía incorporar datos de forma incremental. Sin embargo, ciertos conceptos no se podían 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 manejó 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 eficiente para inducir árboles de decisión de forma incremental. 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 admitir 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 incremental de conceptos que no construían árboles de decisión, pero que precedieron 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 aprendía conceptos disyuntivos de forma incremental. STAGGER se desarrolló para examinar conceptos que cambiaban 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, incluido el aprendizaje no supervisado estructurado en árboles incrementales, contribuyó a un marco conceptual para evaluar específicamente los aprendices de árboles de decisión incrementales 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 conocimiento, (2) la cantidad de observaciones que se requieren para converger en una base de conocimiento con características dadas, (3) el esfuerzo total (como función de las dos primeras dimensiones) que ejerce un sistema, y ​​(4) la calidad (a menudo la consistencia) de la base de conocimiento final. Parte del contexto histórico en el que surgieron los aprendices de árboles de decisión incrementales se proporciona 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 aprendizaje de árboles de decisión muy rápido reduce el tiempo de entrenamiento para grandes conjuntos de datos incrementales al realizar un submuestreo del flujo de datos entrantes.

• VFDT (2000) ^[17]
• CVFDT (2001) ^[18] puede adaptarse a la deriva conceptual mediante el uso de una ventana deslizante en los datos entrantes. Los datos antiguos que se encuentran fuera de la ventana se olvidan.
• 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 disponible en la web. [2] Fue desarrollado por los creadores de VFDT y CVFDT.

OLIN y IFN

• OLIN (2002) ^[20]
• IOLIN (2008) ^[21] — basado en la red Info-Fuzzy (IFN) ^[22]

GAENARI

• gaenari

Véase también

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

Referencias

1. Breiman, L.; Friedman, JH; Olshen, RA; Stone, CJ (1984). Árboles de clasificación y regresión. Belmont, CA: Wadsworth International. 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. Statist. Assoc . 58 (302): 415–434. doi :10.1080/01621459.1963.10500855.
3. Crawford, SL (1989). "Extensiones del 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 el aprendizaje automático. Elsevier. ISBN 978-1-55860-238-0.
6. Hunt, EB; Marin, J.; Stone, PJ (1966). Experimentos en inducción . Academic Press. ISBN 978-0-12-362350-8.
7. Schlimmer, JC; Fisher, D. (1986). "Un estudio de caso de inducción incremental de conceptos". AAAI'86: Actas de la Quinta Conferencia Nacional sobre Inteligencia Artificial. Morgan Kaufmann. 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 Kaufmann. 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, NC; 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 la clasificación de textos utilizando el algoritmo ID6NB". Knowledge-Based Systems . 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 los ejemplos de entrenamiento más representativos y generación incremental de hipótesis de aprendizaje virtual: 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 de lógica de valores variables VL1" (PDF) . IJCAI'73: Actas de la Tercera Conferencia Conjunta Internacional sobre Inteligencia Artificial. Stanford, CA: Morgan Kaufmann. págs. 162–172. hdl :1920/1515/73-01.
16. Fisher, 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). "Extracción de flujos de datos de alta velocidad" (PDF) . Actas de la sexta conferencia internacional ACM SIGKDD sobre descubrimiento de conocimiento y extracción de datos . ACM Press. págs. 71–80. doi :10.1145/347090.347107. ISBN. 1-58113-233-6.S2CID8810610  .​
18. Hulten, G.; Spencer, L.; Domingos, P. (2001). "Extracción de datos que cambian con el tiempo" (PDF) . Actas de la séptima conferencia internacional ACM SIGKDD sobre descubrimiento de conocimiento y extracción de datos . ACM Press. págs. 97–106. doi :10.1145/502512.502529. ISBN . 978-1-58113-391-2.S2CID6416602  .​
19. Gama, J.; Fernandes, R.; Rocha, R. (2006). "Árboles de decisión para la minería de flujos de datos". Análisis de datos inteligentes . 10 : 23–45. doi :10.3233/IDA-2006-10103.
20. Last, M. (2002). "Clasificación en línea de flujos de datos no estacionarios" (PDF) . Intell. Data Anal . 6 (2): 129–147. doi :10.3233/IDA-2002-6203.
21. Cohen, L.; Avrahami, G.; Last, M.; Kandel, A. (2008). "Algoritmos infodifusos para la minería de flujos de datos dinámicos" (PDF) . Applied Soft Computing . 8 (4): 1283–94. doi :10.1016/j.asoc.2007.11.003.
22. Maimon, O.; Last, M. (2000). La metodología de redes infodifusas (IFN). Descubrimiento de conocimiento y minería de datos . Kluwer. doi :10.1007/978-1-4757-3296-2. ISBN 978-1-4757-3296-2.S2CID41520652  .​

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 en C++. https://github.com/greenfish77/gaenari