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.

General derecha|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. 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. 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)Quinlan, J. R., (1986). Induction of Decision Trees. Machine Learning 1: 81-106, Kluwer Academic Publishers 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 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. 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.

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.Breiman, L. (1996). Bagging Predictors. "Machine Learning, 24": pp. 123-140. 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.Friedman, J. H. (1999). Stochastic gradient boosting. Stanford University.Hastie, T., Tibshirani, R., Friedman, J. H. (2001). The elements of statistical learning : Data mining, inference, and prediction. New York: Springer Verlag. 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.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.

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

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

Métricas 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. 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 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 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 Introducido en ACR, 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 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 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.Murthy S. (1998). Automatic construction of decision trees from data: A multidisciplinary survey. Data Mining and Knowledge Discovery 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).