Aprendizaje del árbol de decisiones - Decision tree learning

Parte de una serie sobre
Aprendizaje automático y minería de datos
Problemas Clasificación Agrupación Regresión Detección de anomalías Limpieza de datos AutoML reglas de asociación Aprendizaje reforzado Predicción estructurada Ingeniería de características Aprendizaje de funciones Aprender en línea Aprendizaje semi-supervisado Aprendizaje sin supervisión Aprendiendo a clasificar Inducción gramatical
Aprendizaje supervisado ( clasificación  • regresión ) Árboles de decisión Conjuntos Harpillera Impulsando Bosque aleatorio k -NN Regresión lineal Bayes ingenuo Redes neuronales artificiales Regresión logística Perceptrón Máquina de vectores de relevancia (RVM) Máquina de vectores de soporte (SVM)
Agrupación ABEDUL CURA Jerárquico k -significa Expectativa-maximización (EM) DBSCAN ÓPTICA Cambio medio
Reducción de dimensionalidad Análisis factorial CCA ICA LDA NMF PCA PGD t-SNE
Predicción estructurada Modelos graficos Red de Bayes Campo aleatorio condicional Markov oculto
Detección de anomalías k -NN Factor de valor atípico local
Red neuronal artificial Autoencoder Computación cognitiva Aprendizaje profundo DeepDream Perceptrón multicapa RNN LSTM GRU ESN Máquina de Boltzmann restringida GAN SOM Red neuronal convolucional U-Net Transformador Red neuronal en aumento Memtransistor RAM electroquímica (ECRAM)
Aprendizaje reforzado Q-aprendizaje SARSA Diferencia temporal (TD)
Teoría Compensación entre sesgo y varianza Teoría del aprendizaje computacional Minimización de riesgos empíricos Aprendizaje de Occam Aprendizaje PAC Aprendizaje estadístico Teoría de VC
Lugares de aprendizaje automático NeurIPS ICML ML JMLR ArXiv: cs.LG
Artículos relacionados Glosario de inteligencia artificial Lista de conjuntos de datos para la investigación de aprendizaje automático Esquema del aprendizaje automático
v t mi

El aprendizaje de árboles de decisiones o la inducción de árboles de decisiones es uno de los enfoques de modelado predictivo utilizados en estadística , minería de datos y aprendizaje automático . Utiliza un árbol de decisiones (como modelo predictivo ) para pasar de las observaciones sobre un elemento (representado en las ramas) a las conclusiones sobre el valor objetivo del elemento (representado en las hojas). Los modelos de árbol en los que la variable de destino puede tomar un conjunto discreto de valores se denominan árboles de clasificación ; en estas estructuras de árbol, las hojas representan etiquetas de clase y las ramas representan conjunciones de características que conducen a esas etiquetas de clase. Los árboles de decisión en los que la variable de destino puede tomar valores continuos (normalmente números reales ) se denominan árboles de regresión . Los árboles de decisión se encuentran entre los algoritmos de aprendizaje automático más populares dada su inteligibilidad y simplicidad.

En el análisis de decisiones, se puede utilizar un árbol de decisiones para representar de forma visual y explícita las decisiones y la toma de decisiones . En la minería de datos , un árbol de decisiones describe los datos (pero el árbol de clasificación resultante puede ser una entrada para la toma de decisiones ). Esta página trata sobre árboles de decisión en minería de datos .

General

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. Resumiendo: sus posibilidades de supervivencia eran buenas si era (i) una mujer o (ii) un hombre menor de 9,5 años con estrictamente menos de 3 hermanos.

El aprendizaje del árbol de decisiones es un método comúnmente utilizado en la minería de datos. El objetivo es crear un modelo que prediga el valor de una variable objetivo en función de varias variables de entrada.

Un árbol de decisiones es una representación simple para clasificar ejemplos. Para esta sección, suponga que todas las características de entrada tienen dominios discretos finitos y que hay una característica de destino única llamada "clasificación". Cada elemento del dominio de la clasificación se denomina 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 característica de entrada. Los arcos que provienen de un nodo etiquetado con una característica de entrada se etiquetan con cada uno de los posibles valores de la característica de destino o el arco conduce a un nodo de decisión subordinado en una característica de entrada diferente. Cada hoja del árbol está etiquetada con una clase o una distribución de probabilidad sobre las clases, lo que significa que el árbol ha clasificado el conjunto de datos en una clase específica o en una distribución de probabilidad particular (que, si el árbol de decisión está bien -construido, está sesgado hacia ciertos subconjuntos de clases).

Un árbol se construye dividiendo el conjunto de fuentes , que constituye el nodo raíz del árbol, en subconjuntos, que constituyen los hijos sucesores. La división se basa en un conjunto de reglas de división basadas en características de clasificación. Este proceso se repite en cada subconjunto derivado de una manera recursiva denominada partición recursiva . La recursividad se completa cuando el subconjunto en un nodo tiene todos los mismos valores de la variable objetivo, o cuando la división ya no agrega valor a las predicciones. Este proceso de inducción de árboles de decisión de arriba hacia abajo (TDIDT) es un ejemplo de un algoritmo codicioso y es, con mucho, la estrategia más común para aprender árboles de decisión a partir de datos.

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

Los datos vienen en registros de la forma:

${\ Displaystyle ({\ textbf {x}}, Y) = (x_ {1}, x_ {2}, x_ {3}, ..., x_ {k}, Y)}$

La variable dependiente,, es la variable objetivo que estamos tratando de comprender, clasificar o generalizar. El vector está compuesto por las características, etc., que se utilizan para esa tarea. ${\ Displaystyle Y}$${\ Displaystyle {\ textbf {x}}}$${\ Displaystyle x_ {1}, x_ {2}, x_ {3}}$

Un árbol de ejemplo que estima la probabilidad de cifosis después de una cirugía de columna, dada la edad del paciente y la vértebra en la que se inició la cirugía. El mismo árbol se muestra de tres formas diferentes. Izquierda Las hojas coloreadas muestran la probabilidad de cifosis después de una cirugía de columna y el porcentaje de pacientes en la hoja. Medio El árbol como una trama en perspectiva. Derecha Vista aérea de la parcela intermedia. La probabilidad de cifosis después de la cirugía es mayor en las áreas más oscuras. (Nota: el tratamiento de la cifosis ha avanzado considerablemente desde que se recopiló este pequeño conjunto de datos).

Tipos de árboles de decisión

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

• El análisis del árbol de clasificación es cuando el resultado previsto es la clase (discreta) a la que pertenecen los datos.
• El análisis del árbol de regresión es cuando el resultado previsto puede considerarse un número real (por ejemplo, el precio de una casa o la duración de la estancia de un paciente en un hospital).

El término análisis de árbol de clasificación y regresión (CART) es un término general que se utiliza para referirse a cualquiera de los procedimientos anteriores, introducido por primera vez por Breiman et al. en 1984. Los árboles utilizados para la regresión y los árboles utilizados para la clasificación tienen algunas similitudes, pero también algunas diferencias, como el procedimiento utilizado para determinar dónde dividir.

Algunas técnicas, a menudo llamadas métodos de conjunto , construyen más de un árbol de decisión:

• Árboles potenciados Construyendo un conjunto de forma incremental entrenando cada nueva instancia para enfatizar las instancias de entrenamiento previamente mal modeladas. Un ejemplo típico es AdaBoost . Estos se pueden utilizar para problemas de tipo regresión y tipo clasificación.
• Árboles de decisión agregados (o empaquetados) de Bootstrap , un método de conjunto temprano, construye múltiples árboles de decisión volviendo a muestrear repetidamente los datos de entrenamiento con reemplazo y votando los árboles para obtener una predicción de consenso.
  • Un clasificador de bosque aleatorio es un tipo específico de
  agregación de bootstrap

Un caso especial de un árbol de decisión es una lista de decisiones , que es un árbol de decisión de un solo lado, de modo que cada nodo interno tiene exactamente 1 nodo hoja y exactamente 1 nodo interno como hijo (excepto el nodo más inferior, cuyo único hijo es un solo nodo de hoja). Aunque menos expresivas, las listas de decisiones son posiblemente más fáciles de entender que los árboles de decisiones generales debido a su escasez adicional, permiten que se impongan métodos de aprendizaje no codiciosos y restricciones monótonas.

Los algoritmos notables del árbol de decisión incluyen:

• ID3 (dicotomizador iterativo 3)
• C4.5 (sucesor de ID3)
• CART (árbol de clasificación y regresión)
• Detección automática de interacción chi-cuadrado (CHAID). Realiza divisiones de varios niveles al calcular árboles de clasificación.
• MARTE : extiende los árboles de decisión para manejar mejor los datos numéricos.
• Árboles de inferencia condicionales. Enfoque basado en estadísticas que utiliza pruebas no paramétricas como criterios de división, corregido para pruebas múltiples para evitar el sobreajuste. Este enfoque da como resultado una selección de predictores no sesgada y no requiere poda.

ID3 y CART se inventaron de forma independiente aproximadamente al mismo tiempo (entre 1970 y 1980), pero siguen un enfoque similar para aprender un árbol de decisiones a partir de tuplas de entrenamiento.

También se ha propuesto aprovechar los conceptos de la teoría de conjuntos difusos para la definición de una versión especial del árbol de decisión, conocida como árbol de decisión difuso (FDT). En este tipo de clasificación difusa, generalmente un vector de entrada se asocia con varias clases, cada una con un valor de confianza diferente. Los conjuntos potenciados de FDT también se han investigado recientemente y han mostrado rendimientos comparables a los de otros clasificadores difusos muy eficientes. ${\ Displaystyle {\ textbf {x}}}$

Métrica

Los algoritmos para construir árboles de decisión generalmente funcionan de arriba hacia abajo, eligiendo una variable en cada paso que mejor divide el conjunto de elementos. Los diferentes algoritmos utilizan diferentes métricas para medir "lo mejor". Estos generalmente miden la homogeneidad de la variable objetivo dentro de los subconjuntos. A continuación se ofrecen algunos ejemplos. Estas métricas se aplican a cada subconjunto candidato y los valores resultantes se combinan (por ejemplo, promediados) para proporcionar una medida de la calidad de la división.

Impureza de gini

Utilizado por el algoritmo CART (árbol de clasificación y regresión) para árboles de clasificación, la impureza de Gini (llamada así por el matemático italiano Corrado Gini ) es una medida de la frecuencia con la que un elemento elegido al azar del conjunto se etiquetaría incorrectamente si se etiquetara al azar de acuerdo con el distribución de etiquetas en el subconjunto. La impureza de Gini se puede calcular sumando la probabilidad de que un artículo con etiqueta sea ​​elegido multiplicado por la probabilidad de un error al clasificar ese artículo. Alcanza su mínimo (cero) cuando todos los casos del nodo caen en una única categoría objetivo. ${\ Displaystyle p_ {i}}$${\ Displaystyle i}$${\ Displaystyle \ sum _ {k \ neq i} p_ {k} = 1-p_ {i}}$

La impureza de Gini es también una medida teórica de la información y corresponde a la Entropía de Tsallis con coeficiente de deformación , que en física se asocia con la falta de información en sistemas desequilibrados, no extensivos, disipativos y cuánticos. Para el límite se recupera la entropía habitual de Boltzmann-Gibbs o Shannon. En este sentido, la impureza de Gini no es más que una variación de la medida de entropía habitual para árboles de decisión. ${\ Displaystyle q = 2}$${\ Displaystyle q \ to 1}$

Para calcular la impureza de Gini para un conjunto de elementos con clases, suponga y sea ​​la fracción de elementos etiquetados con clase en el conjunto. ${\ Displaystyle J}$${\ Displaystyle i \ in \ {1,2, ..., J \}}$${\ Displaystyle p_ {i}}$${\ Displaystyle i}$

${\ Displaystyle \ operatorname {I} _ {G} (p) = \ sum _ {i = 1} ^ {J} \ left (p_ {i} \ sum _ {k \ neq i} p_ {k} \ right ) = \ sum _ {i = 1} ^ {J} p_ {i} (1-p_ {i}) = \ sum _ {i = 1} ^ {J} (p_ {i} -p_ {i} ^ {2}) = \ sum _ {i = 1} ^ {J} p_ {i} - \ sum _ {i = 1} ^ {J} p_ {i} ^ {2} = 1- \ sum _ {i = 1} ^ {J} p_ {i} ^ {2}}$

Ganancia de información

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

La entropía se define a continuación

${\ Displaystyle \ mathrm {H} (T) = \ operatorname {I} _ {E} \ left (p_ {1}, p_ {2}, \ ldots, p_ {J} \ right) = - \ sum _ { i = 1} ^ {J} p_ {i} \ log _ {2} p_ {i}}$

donde son fracciones que suman 1 y representan el porcentaje de cada clase presente en el nodo hijo que resulta de una división en el árbol. ${\ Displaystyle p_ {1}, p_ {2}, \ ldots}$

$${\ Displaystyle \ overbrace {IG (T, a)} ^ {\ text {ganancia de información}} = \ overbrace {\ mathrm {H} (T)} ^ {\ text {entropía (padre)}} - \ overbrace { \ mathrm {H} (T \ mid a)} ^ {\ text {suma de entropías (hijos)}}}$$

${\ Displaystyle = - \ sum _ {i = 1} ^ {J} p_ {i} \ log _ {2} p_ {i} - \ sum _ {i = 1} ^ {J} - \ Pr (i \ mid a) \ log _ {2} \ Pr (i \ mid a)}$

Promediando los posibles valores de , ${\ Displaystyle A}$

$${\ Displaystyle \ overbrace {E_ {A} (\ operatorname {IG} (T, a))} ^ {\ text {ganancia de información esperada}} = \ overbrace {I (T; A)} ^ {{\ text { información mutua entre}} T {\ text {y}} A} = \ overbrace {\ mathrm {H} (T)} ^ {\ text {entropy (parent)}} - \ overbrace {\ mathrm {H} (T \ mid A)} ^ {\ text {suma ponderada de entropías (hijos)}}}$$

${\ Displaystyle = - \ sum _ {i = 1} ^ {J} p_ {i} \ log _ {2} p_ {i} - \ sum _ {a} p (a) \ sum _ {i = 1} ^ {J} - \ Pr (i \ mid a) \ log _ {2} \ Pr (i \ mid a)}$

Es decir, la ganancia de información esperada es la información mutua, lo que significa que, en promedio, la reducción de la entropía de T es la información mutua.

La ganancia de información se utiliza para decidir en qué función dividir en cada paso de la construcción del árbol. La simplicidad es lo mejor, por eso queremos que nuestro árbol sea pequeño. Para hacerlo, en cada paso debemos elegir la división que resulte en los nodos secundarios más consistentes. Una medida de coherencia comúnmente utilizada se llama información que se mide en bits . Para cada nodo del árbol, el valor de información "representa la cantidad esperada de información que se necesitaría para especificar si una nueva instancia debe clasificarse como sí o no, dado que el ejemplo llegó a ese nodo".

Considere un conjunto de datos de ejemplo con cuatro atributos: perspectiva (soleado, nublado, lluvioso), temperatura (cálido, templado, fresco), humedad (alta, normal) y ventoso (verdadero, falso), con un binario (sí o no) variable de destino, juego y 14 puntos de datos. Para construir un árbol de decisión sobre estos datos, necesitamos comparar la ganancia de información de cada uno de los cuatro árboles, cada división en una de las cuatro características. La división con la mayor ganancia de información se tomará como la primera división y el proceso continuará hasta que todos los nodos secundarios tengan datos consistentes o hasta que la ganancia de información sea 0.

Para encontrar la ganancia de información de la división usando windy , primero debemos calcular la información en los datos antes de la división. Los datos originales contenían nueve sí y cinco no.

${\ Displaystyle I_ {E} ([9,5]) = - {\ frac {9} {14}} \ log _ {2} {\ frac {9} {14}} - {\ frac {5} { 14}} \ log _ {2} {\ frac {5} {14}} = 0,94}$

La división usando la característica windy da como resultado dos nodos secundarios, uno para un valor de viento verdadero y otro para un valor de viento falso. En este conjunto de datos, hay seis puntos de datos con un valor de viento real, tres de los cuales tienen un valor de juego (donde el juego es la variable objetivo) de sí y tres con un valor de juego de no. Los ocho puntos de datos restantes con un valor ventoso de falso contienen dos no y seis sí. La información del nodo ventoso = verdadero se calcula utilizando la ecuación de entropía anterior. Dado que hay un número igual de sí y no en este nodo, tenemos

${\ Displaystyle I_ {E} ([3,3]) = - {\ frac {3} {6}} \ log _ {2} {\ frac {3} {6}} - {\ frac {3} { 6}} \ log _ {2} {\ frac {3} {6}} = - {\ frac {1} {2}} \ log _ {2} {\ frac {1} {2}} - {\ frac {1} {2}} \ log _ {2} {\ frac {1} {2}} = 1}$

Para el nodo donde viento = falso, había ocho puntos de datos, seis sí y dos no. Así tenemos

${\ Displaystyle I_ {E} ([6,2]) = - {\ frac {6} {8}} \ log _ {2} {\ frac {6} {8}} - {\ frac {2} { 8}} \ log _ {2} {\ frac {2} {8}} = - {\ frac {3} {4}} \ log _ {2} {\ frac {3} {4}} - {\ frac {1} {4}} \ log _ {2} {\ frac {1} {4}} = 0.81}$

Para encontrar la información de la división, tomamos el promedio ponderado de estos dos números en función de cuántas observaciones cayeron en cada nodo.

${\ displaystyle I_ {E} ([3,3], [6,2]) = I_ {E} ({\ text {ventoso o no}}) = {\ frac {6} {14}} \ cdot 1 + {\ frac {8} {14}} \ cdot 0.81 = 0.89}$

Ahora podemos calcular la ganancia de información lograda dividiendo en la característica de viento .

${\ Displaystyle \ operatorname {IG} ({\ text {ventoso}}) = I_ {E} ([9,5]) - I_ {E} ([3,3], [6,2]) = 0,94- 0,89 = 0,05}$

Para construir el árbol, sería necesario calcular la ganancia de información de cada posible primera división. La mejor primera división es la que proporciona la mayor ganancia de información. Este proceso se repite para cada nodo impuro hasta que se completa el árbol. Este ejemplo está adaptado del ejemplo que aparece en Witten et al.

Reducción de la varianza

Introducida en CART, la reducción de la varianza a menudo se emplea en los casos en que la variable objetivo es continua (árbol de regresión), lo que significa que el uso de muchas otras métricas primero requeriría discretización antes de aplicarse. La reducción de la varianza de un nodo N se define como la reducción total de la varianza de la variable objetivo Y debido a la división en este nodo:

${\ Displaystyle I_ {V} (N) = {\ frac {1} {| S | ^ {2}}} \ sum _ {i \ in S} \ sum _ {j \ in S} {\ frac {1 } {2}} (y_ {i} -y_ {j}) ^ {2} - \ left ({\ frac {| S_ {t} | ^ {2}} {| S | ^ {2}}} { \ frac {1} {| S_ {t} | ^ {2}}} \ sum _ {i \ en S_ {t}} \ sum _ {j \ en S_ {t}} {\ frac {1} {2 }} (y_ {i} -y_ {j}) ^ {2} + {\ frac {| S_ {f} | ^ {2}} {| S | ^ {2}}} {\ frac {1} { | S_ {f} | ^ {2}}} \ sum _ {i \ in S_ {f}} \ sum _ {j \ in S_ {f}} {\ frac {1} {2}} (y_ {i } -y_ {j}) ^ {2} \ right)}$

donde , y son el conjunto de índices de muestra pre-divididos, el conjunto de índices de muestra para los que la prueba de división es verdadera y el conjunto de índices de muestra para los que la prueba de división es falsa, respectivamente. Sin embargo, cada uno de los sumandos anteriores son estimaciones de varianza , escritas en una forma sin referirse directamente a la media. ${\ Displaystyle S}$${\ Displaystyle S_ {t}}$${\ Displaystyle S_ {f}}$

Medida de "bondad"

Utilizada por CART en 1984, la medida de "bondad" es una función que busca optimizar el equilibrio de la capacidad de una división de candidatos para crear niños puros con su capacidad para crear niños del mismo tamaño. Este proceso se repite para cada nodo impuro hasta que se completa el árbol. La función , donde es una división candidata en el nodo , se define a continuación ${\ Displaystyle \ varphi (s \ mid t)}$${\ Displaystyle s}$${\ Displaystyle t}$

${\ Displaystyle \ varphi (s \ mid t) = 2P_ {L} P_ {R} \ sum _ {j = 1} ^ {\ text {recuento de clases}} | P (j \ mid t_ {L}) - P (j \ mid t_ {R}) |}$

donde y son los hijos izquierdo y derecho del nodo que usa split , respectivamente; y son las proporciones de registros en y , respectivamente; y y son las proporciones de registros de clase en y , respectivamente. ${\ Displaystyle t_ {L}}$${\ Displaystyle t_ {R}}$${\ Displaystyle t}$${\ Displaystyle s}$${\ Displaystyle P_ {L}}$${\ Displaystyle P_ {R}}$${\ Displaystyle t}$${\ Displaystyle t_ {L}}$${\ Displaystyle t_ {R}}$${\ Displaystyle P (j \ mid t_ {L})}$${\ Displaystyle P (j \ mid t_ {R})}$${\ Displaystyle j}$${\ Displaystyle t_ {L}}$${\ Displaystyle t_ {R}}$

Considere un conjunto de datos de ejemplo con tres atributos: ahorros (bajo, medio, alto), activos (bajo, medio, alto), ingresos (valor numérico) y una variable objetivo binaria de riesgo crediticio (bueno, malo) y 8 puntos de datos. Los datos completos se presentan en la siguiente tabla. Para iniciar un árbol de decisión, calcularemos el valor máximo de usar cada característica para encontrar cuál dividirá el nodo raíz. Este proceso continuará hasta que todos los niños sean puros o todos los valores estén por debajo de un umbral establecido. ${\ Displaystyle \ varphi (s \ mid t)}$${\ Displaystyle \ varphi (s \ mid t)}$

Para encontrar los ahorros de funciones , debemos anotar la cantidad de cada valor. Los datos originales contenían tres bajos, tres medios y dos altos. De los mínimos, uno tenía un buen riesgo crediticio, mientras que entre los medios y altos, 4 tenían un buen riesgo crediticio . Suponga que un candidato se dividió de tal manera que los registros con pocos ahorros se colocarán en el hijo de la izquierda y todos los demás registros se colocarán en el hijo de la derecha. ${\ Displaystyle \ varphi (s \ mid t)}$${\ Displaystyle s}$

${\ Displaystyle \ varphi (s \ mid {\ text {root}}) = 2 \ cdot {\ frac {3} {8}} \ cdot {\ frac {5} {8}} \ cdot \ left (\ left | \ left ({\ frac {1} {3}} - {\ frac {4} {5}} \ right) \ right | + \ left | \ left ({\ frac {2} {3}} - { \ frac {1} {5}} \ right) \ right | \ right) = 0.44}$

Para construir el árbol, es necesario calcular la "bondad" de todas las divisiones candidatas para el nodo raíz. El candidato con el valor máximo dividirá el nodo raíz y el proceso continuará para cada nodo impuro hasta que se complete el árbol.

En comparación con otras métricas, como la ganancia de información, la medida de "bondad" intentará crear un árbol más equilibrado, lo que conducirá a un tiempo de decisión más coherente. Sin embargo, sacrifica cierta prioridad para crear hijos puros, lo que puede conducir a divisiones adicionales que no están presentes con otras métricas.

Usos

Ventajas

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

• Sencillo de entender e interpretar. Las personas pueden comprender los modelos de árboles de decisión después de una breve explicación. Los árboles también se pueden mostrar gráficamente de una manera que sea fácil de interpretar para los no expertos.
• Capaz de manejar datos tanto numéricos como categóricos . Otras técnicas suelen estar especializadas en analizar conjuntos de datos que tienen un solo tipo de variable. (Por ejemplo, las reglas de relación se pueden usar solo con variables nominales, mientras que las redes neuronales solo se pueden usar con variables numéricas o categóricas convertidas a valores 0-1). Los primeros árboles de decisión solo podían manejar variables categóricas, pero las versiones más recientes, como como C4.5, no tienen esta limitación.
• Requiere poca preparación de datos. Otras técnicas a menudo requieren la normalización de datos. Dado que los árboles pueden manejar predictores cualitativos, no es necesario crear variables ficticias .
• Utiliza un modelo de caja blanca o caja abierta. Si una situación dada es observable en un modelo, la explicación de la condición se explica fácilmente mediante lógica booleana. Por el contrario, en un modelo de caja negra , la explicación de los resultados suele ser difícil de entender, por ejemplo, con una red neuronal artificial .
• Posible validar un modelo mediante pruebas estadísticas. Eso permite tener en cuenta la fiabilidad del modelo.
• Enfoque no paramétrico que no hace suposiciones sobre los datos de entrenamiento o los residuos de predicción; por ejemplo, sin supuestos distributivos, de independencia o de varianza constante
• Funciona bien con grandes conjuntos de datos. Se pueden analizar grandes cantidades de datos utilizando recursos informáticos estándar en un tiempo razonable.
• Refleja la toma de decisiones humanas más de cerca que otros enfoques. Esto podría ser útil al modelar las decisiones y el comportamiento humanos.
• Robusto contra la colinealidad, particularmente reforzando
• En la selección de funciones incorporadas . Las funciones adicionales irrelevantes se utilizarán menos para que puedan eliminarse en ejecuciones posteriores. La jerarquía de atributos en un árbol de decisiones refleja la importancia de los atributos. Significa que las características en la parte superior son las más informativas.
• Los árboles de decisión pueden aproximarse a cualquier función booleana, por ejemplo, XOR .

Limitaciones

• Los árboles pueden ser muy poco robustos. Un pequeño cambio en los datos de entrenamiento puede resultar en un gran cambio en el árbol y, en consecuencia, en las predicciones finales.
• Se sabe que el problema de aprender un árbol de decisiones óptimo es NP-completo en varios aspectos de la optimalidad e incluso para conceptos simples. En consecuencia, los algoritmos prácticos de aprendizaje del árbol de decisiones se basan en heurísticas, como el algoritmo codicioso, en el que se toman decisiones localmente óptimas en cada nodo. Dichos algoritmos no pueden garantizar la devolución del árbol de decisiones globalmente óptimo. Para reducir el efecto codicioso de la optimalidad local, se propusieron algunos métodos como el árbol de distancia de información dual (DID).
• Los aprendices de árboles de decisión pueden crear árboles demasiado complejos que no se generalizan bien a partir de los datos de entrenamiento. (Esto se conoce como sobreajuste .) Mecanismos como la poda son necesarios para evitar este problema (con la excepción de algunos algoritmos como el enfoque de inferencia condicional, que no requiere poda).
• No se garantiza que la profundidad promedio del árbol que se define por el número de nodos o pruebas hasta la clasificación sea mínima o pequeña bajo varios criterios de división.
• Para los datos que incluyen variables categóricas con diferentes números de niveles, la ganancia de información en los árboles de decisión está sesgada a favor de los atributos con más niveles. Sin embargo, el problema de la selección sesgada de predictores se evita mediante el enfoque de inferencia condicional, un enfoque de dos etapas o la selección de características adaptativa de dejar uno fuera.

Implementaciones

Muchos paquetes de software de minería de datos proporcionan implementaciones de uno o más algoritmos de árbol de decisión.

Ejemplos incluyen

• Salford Systems CART (que obtuvo la licencia del código de propiedad de los autores originales de CART),
• IBM SPSS Modeler ,
• RapidMiner ,
• SAS Enterprise Miner ,
• Matlab ,
• R (un entorno de software de código abierto para la computación estadística, que incluye varias implementaciones CART como los paquetes rpart, party y randomForest),
• Weka (una suite de minería de datos gratuita y de código abierto, contiene muchos algoritmos de árboles de decisión),
• naranja ,
• KNIME ,
• Microsoft SQL Server [1] y
• scikit-learn (una biblioteca de aprendizaje automático de código abierto y gratuita para el lenguaje de programación Python ).

Extensiones

Gráficos de decisión

En un árbol de decisión, todos los caminos desde el nodo raíz hasta el nodo hoja proceder por la vía de conjunción, o Y . En un gráfico de decisión, es posible usar disyunciones (OR) para unir dos rutas más usando la longitud mínima del mensaje (MML). Los gráficos de decisión se han ampliado aún más para permitir que nuevos atributos no declarados previamente se aprendan dinámicamente y se utilicen en diferentes lugares dentro del gráfico. El esquema de codificación más general da como resultado una mejor precisión predictiva y una puntuación probabilística de pérdida logarítmica. En general, los gráficos de decisión infieren modelos con menos hojas que árboles de decisión.

Métodos de búsqueda alternativos

Se han utilizado algoritmos evolutivos para evitar decisiones locales óptimas y buscar en el espacio del árbol de decisiones con poco sesgo a priori .

También es posible muestrear un árbol utilizando MCMC .

El árbol se puede buscar de abajo hacia arriba. O se pueden construir varios árboles en paralelo para reducir el número esperado de pruebas hasta la clasificación.

Ver también

Referencias

Otras lecturas

• James, Gareth; Witten, Daniela; Hastie, Trevor; Tibshirani, Robert (2017). "Métodos basados ​​en árboles" (PDF) . Una introducción al aprendizaje estadístico: con aplicaciones en R . Nueva York: Springer. págs. 303–336. ISBN 978-1-4614-7137-0.

enlaces externos

• Aprendizaje evolutivo de árboles de decisión en C ++
• Una explicación muy detallada de la ganancia de información como criterio de división.