Árbol de decisión

Un árbol de decisión (también llamado árbol de clasificación o árbol de regresión) es una herramienta de apoyo a la toma de decisiones que se utiliza en el aprendizaje automático , el análisis de datos y las estadísticas . La estructura de un árbol es "hojas" y "ramas". En las aristas (“ramas”) del árbol de decisión se escriben las características de las que depende la función objetivo, en las “hojas” se escriben los valores de la función objetivo , y en los nodos restantes se encuentran las características por las cuales los casos difieren. Para clasificar un nuevo caso, se debe bajar por el árbol hasta una hoja y devolver el valor correspondiente.

Dichos árboles de decisión se utilizan ampliamente en la minería de datos. El objetivo es crear un modelo que prediga el valor de la variable objetivo en función de múltiples variables de entrada.

Cada hoja representa el valor de la variable de destino a medida que cambia desde la raíz a lo largo de los bordes del árbol hasta la hoja. Cada nodo interno se asigna a una de las variables de entrada.

El árbol también se puede "aprender" dividiendo los conjuntos originales de variables en subconjuntos en función de la verificación de los valores de las características. Esta acción se repite en cada uno de los subconjuntos resultantes. La recursión finaliza cuando un subconjunto en un nodo tiene los mismos valores de variable de destino, por lo que no agrega valor a las predicciones. El proceso de arriba hacia abajo, la inducción del árbol de decisión (TDIDT) [1] , es un ejemplo de un algoritmo codicioso absorbente y es, con mucho, la estrategia de árbol de decisión más común para los datos, pero no es la única estrategia posible.

En la minería de datos, los árboles de decisión se pueden utilizar como técnicas matemáticas y computacionales para ayudar a describir, clasificar y generalizar un conjunto de datos, que se pueden escribir de la siguiente manera:

La variable dependiente Y es la variable objetivo a analizar, clasificar y resumir. El vector consta de las variables de entrada , , etc., que se utilizan para completar esta tarea.

Definiciones básicas

El análisis del árbol de decisiones utiliza una herramienta de soporte de decisiones visual y analítica para calcular los valores esperados (o los beneficios esperados) de las alternativas competidoras.

El árbol de decisión consta de tres tipos de nodos:

• Nodos de decisión: generalmente representados por cuadrados
• Nodos de probabilidad - representados como un círculo
• Nodos de cierre - representados como un triángulo

En la figura anterior, el árbol de decisión debe leerse de izquierda a derecha. El árbol de decisión no puede contener elementos cíclicos, es decir, cada nueva hoja puede dividirse posteriormente, no hay caminos convergentes. Por lo tanto, al construir un árbol manualmente, podemos encontrarnos con el problema de su dimensión, por lo que, por regla general, podemos obtener un árbol de decisión utilizando un software especializado. Por lo general, un árbol de decisiones se presenta en forma de dibujo esquemático, lo que facilita su comprensión y análisis.

Tipología de árboles

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

• Un árbol para clasificar cuando el resultado predicho es la clase a la que pertenecen los datos;
• Árbol de regresión cuando el resultado predicho se puede considerar como un número real (por ejemplo, el precio de una casa o la duración de la estadía de un paciente en un hospital).

Los términos mencionados anteriormente fueron introducidos por primera vez por Breiman et al [2] Los tipos enumerados tienen algunas similitudes (algoritmos de construcción recursivos), así como algunas diferencias, como los criterios para elegir una partición en cada nodo. [2]

Algunos métodos le permiten construir más de un árbol de decisión (conjuntos de árboles de decisión):

1. Embolsado sobre árboles de decisión, el enfoque más temprano . Construye varios árboles de decisión, interpolando repetidamente los datos con reemplazo ( bootstrap ), y como respuesta de consenso da el voto de los árboles (su predicción promedio); [3]
2. El clasificador Random Forest se basa en bagging , sin embargo, además de eso, selecciona aleatoriamente un subconjunto de características en cada nodo para hacer que los árboles sean más independientes;
3. Tree boosting se puede utilizar tanto para problemas de regresión como de clasificación. [4] Una implementación de la potenciación de árboles, el algoritmo XGBoost , ha sido utilizada repetidamente por los ganadores de concursos de análisis de datos.
4. "Rotación forestal": árboles en los que cada árbol de decisión se analiza mediante la primera aplicación del análisis de componentes principales (PCA) en subconjuntos aleatorios de características de entrada. [5]

Algoritmos de construcción de árboles

Hay varias formas de seleccionar la siguiente característica:

• Algoritmo ID3 , donde la elección de una característica se produce sobre la base de la ganancia de información ( ing.  Gain ), o sobre la base del criterio de Gini .
• Algoritmo C4.5 (versión mejorada de ID3), donde la selección de funciones se basa en la ganancia de información normalizada ( Ratio de ganancia ) . 
• Algoritmo CART y sus modificaciones — IndCART, DB-CART.
• Detector automático de interacción chi-cuadrado (CHAID). Realiza una separación de varios niveles al calcular la clasificación de árboles; [6]
• MARS: amplía los árboles de decisión para mejorar el procesamiento de datos digitales.

En la práctica, como resultado de estos algoritmos, los árboles a menudo son demasiado detallados, lo que, cuando se aplica más, genera muchos errores. Esto se debe al fenómeno del sobreajuste . Para reducir los árboles se utiliza la poda ( poda inglesa  ).

Ventajas del método

A diferencia de otros métodos de minería de datos, el método del árbol de decisión tiene varias ventajas:

• Fácil de entender e interpretar.
• No requiere una preparación de datos especial, como la normalización de datos, la adición de variables ficticias y la eliminación de datos faltantes.
• Capaz de trabajar con variables categóricas y de intervalo. (Otros métodos funcionan solo con datos donde solo hay un tipo de variable. Por ejemplo, el método de razón solo se puede aplicar a variables nominales y el método de red neuronal solo a variables medidas en una escala de intervalo).
• Utiliza un modelo de "caja blanca", es decir, si se observa una determinada situación en el modelo, entonces se puede explicar utilizando la lógica booleana. Un ejemplo de "caja negra" puede ser una red neuronal artificial , ya que los resultados obtenidos son difíciles de explicar.
• Le permite evaluar el modelo mediante pruebas estadísticas. Esto permite evaluar la fiabilidad del modelo.
• El método funciona bien incluso si se han violado los supuestos originales incluidos en el modelo.
• Le permite trabajar con una gran cantidad de información sin procedimientos preparatorios especiales. Este método no requiere equipo especial para trabajar con grandes bases de datos.

Desventajas del método

• El problema de obtener un árbol de decisión óptimo es un problema NP-completo , en términos de algunos aspectos de optimización incluso para problemas simples [7] [8] . Así, la aplicación práctica del algoritmo del árbol de decisión se basa en algoritmos heurísticos, como el algoritmo "codicioso", donde la única solución óptima se elige localmente en cada nodo. Dichos algoritmos no pueden garantizar la optimización de todo el árbol como un todo.
• El proceso de construcción de un árbol de decisiones puede crear estructuras demasiado complejas que no representan completamente los datos. Este problema se llama sobreajuste [9] . Para evitarlo, es necesario utilizar el método de "ajuste de la profundidad del árbol".
• Hay conceptos que son difíciles de entender del modelo, porque el modelo los describe de manera compleja. Este fenómeno puede ser causado por problemas de XOR, paridad o multiplexor. En este caso, estamos tratando con árboles prohibitivamente grandes. Hay varios enfoques para resolver este problema, por ejemplo, un intento de cambiar la representación del concepto en el modelo (elaboración de nuevos juicios) [10] , o el uso de algoritmos que describen y representan más completamente el concepto (por ejemplo , el método de las relaciones estadísticas, lógica de programación inductiva).
• Para los datos que incluyen variables categóricas con un gran conjunto de niveles (cierres), se asigna más peso informativo a aquellas características que tienen más niveles [11] .

Control de profundidad del árbol

La limitación de profundidad de árbol es una técnica que le permite reducir el tamaño de un árbol de decisión eliminando partes del árbol que tienen poco peso.

Una de las preguntas que surge en el algoritmo del árbol de decisión es el tamaño óptimo del árbol final. Por lo tanto, un árbol pequeño puede no capturar una u otra información importante sobre el espacio muestral. Sin embargo, es difícil decir cuándo debe detenerse el algoritmo, porque es imposible predecir qué nodo adicional reducirá significativamente el error. Este problema se conoce como el "efecto horizonte". Sin embargo, se conserva la estrategia general de restricción de árboles, es decir, se implementa la eliminación de nodos si no proporcionan información adicional [12] .

El ajuste de profundidad del árbol debería reducir el tamaño del modelo de árbol de entrenamiento sin reducir su precisión de predicción o mediante validación cruzada. Hay muchos métodos para ajustar la profundidad de un árbol que difieren en la medida de la optimización del rendimiento.

Métodos de regulación

La poda de árboles se puede hacer de arriba hacia abajo o de abajo hacia arriba. De arriba a abajo: la poda comienza desde la raíz, de abajo hacia arriba, se reduce la cantidad de hojas del árbol. Uno de los métodos de control más simples es reducir el error de restricción del árbol. Comenzando con las hojas, cada nodo se reemplaza por la clase más popular. Si el cambio no afecta la precisión de la predicción, se guarda.

Ejemplo de problema

Supongamos que estamos interesados ​​en saber si nuestro equipo de fútbol favorito ganará el próximo partido. Sabemos que esto depende de una serie de parámetros; enumerarlos a todos es una tarea imposible, por lo que nos limitaremos a los principales:

• si el oponente está más alto en la clasificación;
• si el partido se juega en casa;
• si alguno de los jefes de equipo se pierde el partido;
• esta lloviendo.

Tenemos algunas estadísticas al respecto:

Me gustaría saber si nuestro equipo ganará en el próximo partido.

Véase también

• Bosque aleatorio  : un clasificador basado en el uso de comités de árboles de decisión
• reentrenamiento
• El aprendizaje automático  es una clase de métodos de inteligencia artificial , cuyo rasgo característico no es la solución directa del problema, sino el aprendizaje en el proceso de aplicar soluciones a muchos problemas similares.
• Tabla de decisiones

Notas

1. ↑ Quinlan, JR Inducción de árboles de decisión  //  Aprendizaje automático. - Editorial Académica Kluwer, 1986. - No. 1 . - P. 81-106 . Archivado desde el original el 20 de enero de 2022.
2. ↑ 1 2 Breiman, Leo; Friedman, JH, Olshen, RA y Stone, CJ Árboles de clasificación y regresión  . - Monterey, CA: Wadsworth & Brooks/Cole Advanced Books & Software, 1984. - ISBN 978-0-412-04841-8 .
3. ↑ Breiman, L. Predictores de embolsado  //  Aprendizaje automático. - 1996. - No. 24 . - P. 123-140 .
4. ↑ Friedman, JH Aumento de gradiente  estocástico . — Universidad de Stanford, 1999.
5. ↑ Hastie, T., Tibshirani, R., Friedman, JH Los elementos del aprendizaje estadístico : minería de datos, inferencia y predicción  . — Nueva York: Springer Verlag, 2001.
6. ↑ Kas ,  GV _  Serie C (Estadística Aplicada). — vol. 29 , núm. 2 . - pág. 119-127 . -doi : 10.2307/ 2986296 . Archivado desde el original el 2 de abril de 2022.
7. ↑ Hyafil, Laurent; Rivest, R. L. La construcción de árboles de decisión binarios óptimos es NP-completo  //  Cartas de procesamiento de información. - 1976. - vol. 5 , núm. 1 . - P. 15-17 . - doi : 10.1016/0020-0190(76)90095-8 .
8. ↑ Murthy S. Construcción automática de árboles de decisión a partir de datos: una encuesta multidisciplinaria  //  Minería de datos y descubrimiento de conocimiento. - 1998. - No. 2 . - Pág. 345-389 . Archivado desde el original el 2 de abril de 2022.
9. ↑ Max Bramer. Principios de  Minería de Datos . - Springer, 2007. - ISBN 978-1-84628-765-7 .
10. ↑ Programación Lógica Inductiva  / Horváth, Tamás; Yamamoto, Akihiro, editores - Springer, 2003. - ISBN 978-3-540-20144-1 .
11. ↑ Deng, H., Runger, G., Tuv, E. Bias of Importance Measures for Multi-valued Attributes and Solutions // Artificial Neural Networks and Machine Learning - ICANN 2011. ICANN 2011. Lecture Notes in Computer Science, vol 6792  ( ( inglés) / Honkela, T., Duch, W., Girolami, M., Kaski, S. (eds). - Berlín, Heidelberg: Springer, 2011. - ISBN 978-3-642-21737-1 .
12. ↑ Algoritmo de poda de árbol de decisiones rápido y ascendente

Enlaces

• Apuntes de clase sobre árboles de decisión
• El subprograma de árboles de decisión proporciona varios conjuntos de datos de muestra de ejemplos para aprender y clasificar

Literatura

• Levitin A. V. Capítulo 10. Límites de potencia de los algoritmos: árboles de decisión // Algoritmos. Introducción al desarrollo y análisis - M .: Williams , 2006. - S. 409-417. — 576 pág. — ISBN 978-5-8459-0987-9
• Paklin N.B., Oreshkov V.I. Capítulo 9. // Business Analytics: De los Datos al Conocimiento (+CD): Tutorial. 2ª ed.- San Petersburgo. : Pedro, 2013. - S. 428-472. - ISBN 978-5-459-00717-6 .