Aprendizaje basado en árboles de decisión

De Wikipedia, la enciclopedia libre

Aprendizaje basado en árboles de decisión utiliza un árbol de decisión como un modelo predictivo que mapea observaciones sobre un artículo a conclusiones sobre el valor objetivo del artículo. Es uno de los enfoques de modelado predictivo utilizadas en estadísticas, minería de datos y aprendizaje automático. Los modelos de árbol, donde la variable de destino puede tomar un conjunto finito de valores se denominan árboles de clasificación. En estas estructuras de árbol, las hojas representan etiquetas de clase y las ramas representan las conjunciones de características que conducen a esas etiquetas de clase. Los árboles de decisión, donde la variable de destino puede tomar valores continuos (por lo general números reales) se llaman árboles de regresión. Los árboles de decisión se encuentran entre los algoritmos populares debido a su simplicidad.

En análisis de decisión, un árbol de decisión se puede utilizar para representar visualmente y de forma explícita decisiones y toma de decisiones. En minería de datos, un árbol de decisión describe datos, pero no las decisiones; más bien el árbol de clasificación resultante puede ser un usado como entrada para la toma de decisiones. Esta página se ocupa de los árboles de decisión en la minería de datos.[1]​[2]​

General[editar]

Un árbol que muestra la supervivencia de los pasajeros del Titanic ("sibsp" es el número de cónyuges o hermanos a bordo). Las cifras debajo de las hojas muestran la probabilidad de supervivencia y el porcentaje de observaciones en la hoja.
Un árbol que muestra la supervivencia de los pasajeros del Titanic ("sibsp" es el número de cónyuges o hermanos a bordo). Las cifras debajo de las hojas muestran la probabilidad de supervivencia y el porcentaje de observaciones en la hoja.

Aprendizaje basado en árboles de decisión es un método comúnmente utilizado en la minería de datos.[3]​ El objetivo es crear un modelo que predice el valor de una variable de destino en función de diversas variables de entrada. Un ejemplo se muestra a la derecha. Cada nodo interior corresponde a una de las variables de entrada; hay bordes a los niños para cada uno de los posibles valores de la variable de entrada. Cada hoja representa un valor de la variable de destino dados los valores de las variables de entrada representados por el camino desde la raíz a la hoja.

Un árbol de decisión es una representación simple para clasificar ejemplos. Aprendizaje basado en árboles de decisión es una de las técnicas más eficaces para la clasificación supervisada[cita requerida]. Para esta sección, se supone que todas las funciones tienen dominios discretos finitos, y existe una sola característica de destino llamado la clasificación. Cada elemento del dominio de la clasificación se llama clase. Un árbol de decisión o un árbol de clasificación es un árbol en el que cada nodo interno (no hoja) está etiquetado con una función de entrada. Los arcos procedentes de un nodo etiquetado con una característica están etiquetados con cada uno de los posibles valores de la característica. Cada hoja del árbol se marca con una clase o una distribución de probabilidad sobre las clases.

Un árbol puede ser "aprendido" mediante el fraccionamiento del conjunto inicial en subconjuntos basados en una prueba de valor de atributo. Este proceso se repite en cada subconjunto derivado de una manera recursiva llamada particionamiento recursivo. La recursividad termina cuando el subconjunto en un nodo tiene todo el mismo valor de la variable objetivo, o cuando la partición ya no agrega valor a las predicciones. Este proceso de inducción top-down de los árboles de decisión (ITDAD)[4]​ es un ejemplo de un algoritmo voraz, y es, con mucho, la estrategia más común para aprender árboles de decisión a partir de datos.

En minería de datos, los árboles de decisión se pueden describir también como la combinación de técnicas matemáticas y computacionales para ayudar a la descripción, la categorización y la generalización de un conjunto dado de datos.

Los datos provienen en registros de la forma:

La variable dependiente, Y, es la variable objetivo que estamos tratando de entender, clasificar o generalizar. El vector x se compone de las variables de entrada, x1, x2, x3 etc., que se utilizan para esa tarea.

Tipos[editar]

Los árboles de decisión utilizados en la minería de datos son de dos tipos principales:

  • Árboles de clasificación es cuando el resultado predicho es la clase a la que pertenecen los datos.
  • Árboles de regresión es cuando el resultado predicho se puede considerar un número real (por ejemplo, el precio de una casa, o el número de días de estancia de un paciente en un hospital).

El término Árboles de Clasificación y Regresión (ACR) es un término genérico utilizado para referirse a ambos de los procedimientos anteriores, introducido por primera vez por Breiman et al.[5]​ Los árboles utilizados para la regresión y los árboles utilizados para la clasificación tienen algunas similitudes - pero también algunos diferencias, tales como el procedimiento utilizado para determinar donde dividir.[5]​

Algunas técnicas, a menudo llamados métodos conjuntoshíbridos, construyen más de un árbol de decisión:

  • Bagging, un método de conjunto, construye múltiples árboles de decisión haciendo repetidamente remuestreo de los datos de entrenamiento con sustitución, y votando los árboles para hallar una predicción de consenso.[6]​
  • Un clasificador Random Forest utiliza una serie de árboles de decisión, con el fin de mejorar la tasa de clasificación.
  • Los Árboles Impulsados se pueden utilizar para problemas de regresión y de clasificación.[7]​[8]​
  • Rotation Forest En el que cada árbol de decisión es entrenado aplicando primero análisis de componentes principales (ACP) en un subconjunto aleatorio de las características de entrada.[9]​

Aprendizaje basado en árboles de decisión es la construcción de un árbol de decisión a partir de tuplas de entrenamiento, cada una etiquetada con su correspondiente clase. Un árbol de decisión es similar a una estructura de diagrama de flujo, donde cada nodo interno (no hoja) denota una prueba en un atributo, cada rama representa el resultado de una prueba, y cada hoja (o terminal) nodo tiene una etiqueta de clase. El nodo superior en un árbol es el nodo raíz.

Hay muchos algoritmos específicos de árbol de decisiones. Entre los más destacados están:

  • ID3 (Iterative Dichotomiser 3)
  • C4.5 (Sucesor de ID3)
  • ACR (Árboles de Clasificación y Regresión)
  • CHAID (Detector automático de Chi-cuadrado de interacción). Realiza divisiones de múltiples niveles al calcular los árboles de clasificación.[10]​
  • MARS: Extiende los árboles de decisión para manejar mejor datos numéricos.
  • Árboles de Inferencia Condicional. Enfoque que utiliza pruebas no paramétricas como criterios de división, corregidos para múltiples pruebas para evitar el sobreajuste. Este enfoque se traduce en la selección de un predictor imparcial y no requiere poda.[11]​[12]​

ID3 y ACR se inventaron de forma independiente en la misma época (entre 1970 y 1980)[cita requerida], pero ambos siguen un enfoque similar para el aprendizaje basado en árboles de decisión a partir de tuplas de entrenamiento.

Métricas[editar]

Los algoritmos para la construcción de árboles de decisión suelen trabajar de manera top-down, escogiendo en cada paso la variable que mejor divide el conjunto de elementos.[13]​ Diferentes algoritmos utilizan diferentes métricas para medir el "mejor". Estos miden generalmente la homogeneidad de la variable de destino dentro de los subconjuntos. Algunos ejemplos se dan a continuación. Estas métricas se aplican a cada subconjunto candidato, y los valores resultantes se combinan (por ejemplo, un promedio) para proporcionar una medida de la calidad de la división.

Impureza de Gini[editar]

No debe confundirse con el coeficiente de Gini.

Utilizado por el algoritmo de ACR (Árboles de Clasificación y Regresión), la impureza de Gini es una medida de cuán a menudo un elemento elegido aleatoriamente del conjunto sería etiquetado incorrectamente si fue etiquetado de manera aleatoria de acuerdo a la distribución de las etiquetas en el subconjunto. La impureza de Gini se puede calcular sumando la probabilidad de cada elemento siendo elegido multiplicado por la probabilidad de un error en la categorización de ese elemento. Alcanza su mínimo (cero) cuando todos los casos del nodo corresponden a una sola categoría de destino.

Para calcular la impureza de Gini de un conjunto de elementos, supongamos i toma valores en , y sea la fracción de artículos etiquetados con valor en el conjunto.

Ganancia de información[editar]

Utilizado por los algoritmos de generación de árboles ID3 , C4.5 y C5.0. Ganancia de información se basa en el concepto de entropía de la teoría de la información.

Reducción de la varianza[editar]

Introducido en ACR,[5]​ la reducción de la varianza se emplea a menudo en los casos en que la variable de destino es un árbol de regresión continuo, lo que significa que el uso de muchas otras métricas requeriría primero discretización antes de ser aplicada. La reducción de la varianza de un nodo se define como la reducción total de la varianza de la variable de destino debido a la partición en este nodo:

donde , , y son el conjunto de índices de la muestra de prepartición, conjunto de índices de la muestra para el que la prueba de partición es cierto y un conjunto de índices de la muestra para el que la prueba de partición es falsa, respectivamente.

Ventajas de los Árboles de Decisión[editar]

Entre otros métodos de minería de datos, los árboles de decisión tienen varias ventajas:

  • Fácil de entender e interpretar. Las personas son capaces de comprender los modelos de árboles de decisión después de una breve explicación.
  • Requiere poca preparación de los datos. Otras técnicas a menudo requieren la normalización de datos, utilización de variables ficticias necesitan ser creados y valores en blanco deben ser eliminados.
  • Capaz de manejar tanto datos numéricos y categorizados. Otras técnicas son generalmente especializadas en el análisis de conjuntos de datos que tienen sólo un tipo de variable. (Por ejemplo, las normas de relación sólo se pueden utilizar con variables nominales, mientras que las redes neuronales pueden ser utilizados sólo con variables numéricas.)
  • Utiliza un modelo de caja blanca. Si una situación dada es observable en un modelo entonces la condición se explica fácilmente por la lógica booleana. (Un ejemplo de un modelo de caja negro es una red neural artificial ya que la explicación de los resultados es difícil de entender.)
  • Es posible validar un modelo utilizando pruebas estadísticas. Eso hace que sea posible tener en cuenta la fiabilidad del modelo.
  • Robusto. Se desempeña bien incluso si sus suposiciones son violadas por el verdadero modelo a partir del cual se generaron los datos.
  • Funciona bien con grandes conjuntos de datos. Grandes cantidades de datos pueden ser analizados utilizando recursos informáticos estándar en un plazo razonable.

Limitaciones[editar]

  • El problema del aprendizaje de un árbol de decisión óptimo es conocido por ser NP-completo bajo varios aspectos de optimización e incluso para conceptos simples.[14]​[15]​ En consecuencia, los algoritmos prácticos de aprendizaje de árboles de decisiones se basan en heurísticas como el algoritmo voraz donde decisiones localmente óptimas se hacen en cada nodo. Tales algoritmos no pueden garantizar devolver el árbol de decisión globalmente óptimo. Para reducir el efecto codicioso de optimalidad local han sido propuestos algunos métodos tales como la distancia de doble información (DDI).[16]​ [1] Archivado el 4 de junio de 2016 en Wayback Machine.
  • Aprendices de árbol de decisiones pueden crear árboles excesivamente complejos que no generalizan bien a partir de los datos de entrenamiento. (Esto se conoce como sobreajuste.[17]​) Mecanismos tales como la poda son necesarios para evitar este problema (con la excepción de algunos algoritmos tales como el Enfoque de Inferencia Condicional, que no requiere la poda[11]​[12]​)).
  • Hay conceptos que son difíciles de aprender porque los árboles de decisión no expresan fácilmente, como XOR, paridad o problemas de multiplexor. En tales casos, el árbol de decisión se vuelve prohibitivamente grande. Enfoques para resolver el problema suponen el cambio de la representación del dominio del problema[18]​ o el uso de algoritmos de aprendizaje basado en representaciones más expresivas (como aprendizaje relacional estadística o programación lógica inductiva).
  • Para datos que incluyen variables categorizadas con diferente número de niveles, el aumento de la información en árboles de decisión se inclina a favor de esos atributos con más niveles.[19]​ Sin embargo, el tema de la selección de predicción sesgada se evita por el enfoque de inferencia condicional,.[11]​

Extensiones[editar]

Grafos de decisión[editar]

En un árbol de decisión, todos los caminos desde el nodo raíz al nodo hoja proceden por medio de la conjunción, o AND. En un gráfico de decisiones, es posible utilizar disyunciones (OR) para unir dos caminos más utilizando la Longitud del mensaje Mínimo (MML).[20]​ Los grafos de decisión se han ampliado para permitir nuevos atributos previamente no declarados que pueden ser aprendidos dinámicamente y utilizado en diferentes lugares dentro del grafo.[21]​ Los esquemas de predicción más generales resultan en una mayor precisión predictiva y puntuación de la probabilidad log-pérdida.[cita requerida] En general, los grafos de decisión infieren modelos con menos hojas que árboles de decisión x.

Métodos de búsqueda alternativos[editar]

Los algoritmos evolutivos se han utilizado para evitar decisiones óptimas locales y buscar en el espacio del árbol de decisiones con poco un sesgo priori.[22]​[23]​

También es posible para un árbol ser muestreado utilizando MCMC.[24]​

El árbol puede ser recorrido de forma bottom-up.[25]​

Véase también[editar]

Implementaciones[editar]

Muchos paquetes de software de minería de datos proporcionan implementaciones de uno o varios algoritmos de árboles de decisión. Varios ejemplos incluyen ACR de Sistemas Salford (que licenció el código propietario de los autores originales de ACR[5]​ ), IBM SPSS Modeler, RapidMiner, SAS Enterprise Miner, MATLAB, R (un entorno de software de código abierto para el cálculo estadístico que incluye varias implementaciones ACR tales como los paquetes rpart, party y randomForest), Weka (una suite libre y de código abierto para minería de datos, contiene muchos algoritmos de árboles de decisión), Orange (una suite libre de minería de datos de software, que incluye el módulo de árbol orngTree), KNIME, Microsoft SQL Server [2], y scikit-learn (una biblioteca de aprendizaje automático libre y de código abierto para el lenguaje de programación Python).

Referencias[editar]

  1. ↑ Wu, Xindong; Kumar, Vipin; Ross Quinlan, J.; Ghosh, Joydeep; Yang, Qiang; Motoda, Hiroshi; McLachlan, Geoffrey J.; Ng, Angus; Liu, Bing; Yu, Philip S.; Zhou, Zhi-Hua (1 de enero de 2008). «Top 10 algorithms in data mining». Knowledge and Information Systems (en inglés) 14 (1): 1-37. ISSN 0219-3116. doi:10.1007/s10115-007-0114-2. 
  2. ↑ Piryonesi S. Madeh; El-Diraby Tamer E. (1 de marzo de 2020). «Data Analytics in Asset Management: Cost-Effective Prediction of the Pavement Condition Index». Journal of Infrastructure Systems 26 (1): 04019036. doi:10.1061/(ASCE)IS.1943-555X.0000512. 
  3. ↑ Rokach, Lior; Maimon, O. (2008). Data mining with decision trees: theory and applications. World Scientific Pub Co Inc. ISBN 978-9812771711. 
  4. ↑ Quinlan, J. R., (1986). Induction of Decision Trees. Machine Learning 1: 81-106, Kluwer Academic Publishers
  5. ↑ a b c d Breiman, Leo; Friedman, J. H.; Olshen, R. A.; Stone, C. J. (1984). Classification and regression trees. Monterey, CA: Wadsworth & Brooks/Cole Advanced Books & Software. ISBN 978-0-412-04841-8. 
  6. ↑ Breiman, L. (1996). Bagging Predictors. "Machine Learning, 24": pp. 123-140.
  7. ↑ Friedman, J. H. (1999). Stochastic gradient boosting. Stanford University.
  8. ↑ Hastie, T., Tibshirani, R., Friedman, J. H. (2001). The elements of statistical learning : Data mining, inference, and prediction. New York: Springer Verlag.
  9. ↑ Rodriguez, J.J. and Kuncheva, L.I. and Alonso, C.J. (2006), Rotation forest: A new classifier ensemble method, IEEE Transactions on Pattern Analysis and Machine Intelligence, 28(10):1619-1630.
  10. ↑ Kass, G. V. (1980). «An exploratory technique for investigating large quantities of categorical data». Applied Statistics 29 (2): 119-127. JSTOR 2986296. doi:10.2307/2986296. 
  11. ↑ a b c Hothorn, T.; Hornik, A.; Zeileis (2006). «Unbiased Recursive Partitioning: A Conditional Inference Framework». Journal of Computational and Graphical Statistics 15 (3): 651-674. JSTOR 27594202. doi:10.1198/106186006X133933. 
  12. ↑ a b Strobl, C.; Malley, G.; Tutz (2009). «An Introduction to Recursive Partitioning: Rationale, Application and Characteristics of Classification and Regression Trees, Bagging and Random Forests». Psychological Methods 14 (4): 323-348. doi:10.1037/a0016973. 
  13. ↑ Rokach, L.; Maimon, O. (2005). «Top-down induction of decision trees classifiers-a survey». IEEE Transactions on Systems, Man, and Cybernetics, Part C 35 (4): 476-487. doi:10.1109/TSMCC.2004.843247. 
  14. ↑ Hyafil, Laurent; Rivest, RL (1976). «Constructing Optimal Binary Decision Trees is NP-complete». Information Processing Letters 5 (1): 15-17. doi:10.1016/0020-0190(76)90095-8. 
  15. ↑ Murthy S. (1998). Automatic construction of decision trees from data: A multidisciplinary survey. Data Mining and Knowledge Discovery
  16. ↑ Ben-Gal I. Dana A., Shkolnik N. and Singer (20). Efficient Construction of Decision Trees by the Dual Information Distance Method. Quality Technology & Quantitative Management (QTQM), 11( 1), 133-147. Archivado desde el original el 4 de junio de 2016. Consultado el 19 de diciembre de 2014. 
  17. ↑ Bramer, Max (2007). Principles of data mining (en inglés) (Online-Ausg. edición). London: Springer. ISBN 978-1-84628-766-4. 
  18. ↑ Horváth, Tamás,; Akihiro, Yamamoto (2003). Inductive logic programming 13th international conference, ILP 2003, Szeged, Hungary, September/October, 2003 : proceedings (en inglés). Berlin: Springer. ISBN 978-3-540-20144-1. doi:10.1007/b13700. 
  19. ↑ Deng,H.; Runger, G.; Tuv, E. (2011). Bias of importance measures for multi-valued attributes and solutions. Proceedings of the 21st International Conference on Artificial Neural Networks (ICANN) (en inglés). pp. 293-300. 
  20. ↑ http://citeseer.ist.psu.edu/oliver93decision.html
  21. ↑ Tan & Dowe (2003)
  22. ↑ Papagelis A., Kalles D.(2001). Breeding Decision Trees Using Evolutionary Techniques, Proceedings of the Eighteenth International Conference on Machine Learning, p.393-400, June 28-July 01, 2001
  23. ↑ Barros, Rodrigo C., Basgalupp, M. P., Carvalho, A. C. P. L. F., Freitas, Alex A. (2011). A Survey of Evolutionary Algorithms for Decision-Tree Induction. IEEE Transactions on Systems, Man and Cybernetics, Part C: Applications and Reviews, vol. 42, n. 3, p. 291-312, May 2012.
  24. ↑ Chipman, Hugh A., Edward I. George, and Robert E. McCulloch. "Bayesian CART model search." Journal of the American Statistical Association 93.443 (1998): 935-948.
  25. ↑ Barros R. C., Cerri R., Jaskowiak P. A., Carvalho, A. C. P. L. F., A bottom-up oblique decision tree induction algorithm. Proceedings of the 11th International Conference on Intelligent Systems Design and Applications (ISDA 2011).
Obtenido de «https://es.wikipedia.org/w/index.php?title=Aprendizaje_basado_en_árboles_de_decisión&oldid=155824634»