Hispanopedia Wiki
Articulo de referencia

Á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 C...

Hispanopedia WikiContenido en espanolLectura gratuita

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 árboles de decisión incrementales permiten actualizar un árbol existente utilizando solo nuevas instancias de datos individuales, sin tener que reprocesar las instancias anteriores. Esto puede ser útil en situaciones donde el conjunto de datos completo no está disponible al actualizar 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

Métodos

Aquí hay una breve lista de métodos de árboles de decisión incrementales, organizados según sus algoritmos padres (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. 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 (CLS, 1966) de Hunt [ 6 ]. La familia de inductores de árboles ID3 fue desarrollada en las comunidades de ingeniería y ciencias de la computación.

  • ID3' (1986) [ 7 ] fue sugerido por Schlimmer y Fisher. Era un método de fuerza bruta para hacer que ID3 fuera incremental; después de que se adquiere cada nueva instancia de datos, se induce un árbol completamente nuevo usando ID3.
  • ID4 (1986) [ 7 ] podía incorporar datos de forma incremental. Sin embargo, ciertos conceptos eran imposibles de aprender, porque ID4 descarta los subárboles cuando se elige una nueva prueba para un nodo.
  • ID5 (1988) [ 8 ] no descartaba subárboles, pero tampoco garantizaba que produciría el mismo árbol que ID3.
  • ID5R (1989) [ 9 ] generó 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 eficiente para la inducción incremental de árboles de decisión. Se genera el mismo árbol para un conjunto de datos, independientemente del orden de presentación de los datos o de si la inducción se realiza de forma incremental o no incremental ( modo por lotes ). Admite variables numéricas, tareas multicategoría y valores faltantes. El código está disponible en la web.

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

Otros sistemas de aprendizaje incremental

Hubo varios sistemas de aprendizaje de conceptos incrementales 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 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 conceptual ). 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 no supervisado incremental estructurado en árbol , contribuyó a un marco conceptual para evaluar los aprendices incrementales de árboles de decisión específicamente, 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) costo de actualización de la base de conocimiento , (2) el número de observaciones que se requieren para converger en una base de conocimiento con características dadas, (3) el esfuerzo total (en función de las dos primeras dimensiones) que ejerce un sistema, y ​​la (4) calidad (a menudo consistencia) de la base de conocimiento final. Parte del contexto histórico en el que surgieron los aprendices incrementales de árboles de decisión se da 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 algoritmo de aprendizaje Very Fast Decision Trees reduce el tiempo de entrenamiento para grandes conjuntos de datos incrementales mediante el submuestreo del flujo de datos entrante.

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

OLIN e IFN

GAENARI

  • gaenari

Véase también

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 al algoritmo CART" . International Journal of Man-Machine Studies . 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. ↑ Hunt, EB; Marin, J.; Stone, PJ (1966). Experimentos en inducción . Academic Press. ISBN 978-0-12-362350-8.
  7. 1 2 3 4 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 Machine Learning 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) . Machine Learning . 4 (2): 161– 186. Bibcode : 1989MLear...4..161U . doi : 10.1023/A:1022699900025 . S2CID 5293072 . 
  10. ↑ Kroon, M., Korzec, S., Adriani, P. (2007) ID6MDL: Árboles de decisión incrementales con poda posterior.
  11. ↑ Utgoff, PE; Berkman, NC; Clouse, JA (1997). "Inducción de árboles de decisión basada en la reestructuración eficiente de árboles" (PDF) . Machine Learning . 29 (1): 5– 44. Bibcode : 1997MLear..29....5U . doi : 10.1023/A:1007413323501 . S2CID 2743403 . 
  12. ↑ Appavu, S.; Rajaram, R. (2009). "Sistema basado en el conocimiento para la clasificación de texto utilizando el 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" . Machine Learning . 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 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 mediante el sistema lógico de valores variables VL1" (PDF) . IJCAI'73: Actas de la Tercera Conferencia Internacional Conjunta sobre Inteligencia Artificial . Stanford, CA: Morgan Kaufmann. pp. 162–172 . hdl : 1920/1515/73-01 . 
  16. ↑ Fisher, D.; Schlimmer, J. (1988). Modelos de aprendizaje incremental de conceptos: una propuesta de investigación conjunta (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 de KDD Actas de la sexta conferencia internacional ACM SIGKDD sobre descubrimiento de conocimiento y minería de datos . ACM Press. págs. 71–80 . doi : 10.1145/347090.347107 . ISBN  1-58113-233-6. S2CID 8810610 . 
  18. ↑ Hulten, G.; Spencer, L.; Domingos, P. (2001). «Minería de flujos de datos que cambian con el tiempo» (PDF) . Actas de la séptima conferencia internacional ACM SIGKDD sobre descubrimiento de conocimiento y minería de datos . ACM Press. págs. 97–106 . doi : 10.1145/502512.502529 . ISBN  978-1-58113-391-2. S2CID 6416602 . 
  19. ↑ Gama, J.; Fernandes, R.; Rocha, R. (2006). "Árboles de decisión para la minería de flujos de datos" . Análisis inteligente de datos . 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 info-fuzzy 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 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 . 
  • 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