Aprendizaje del árbol de decisiones

Este artículo trata sobre los árboles de decisión en el aprendizaje automático. Para conocer el uso del término en el análisis de decisiones, consulte Árbol de decisiones .

Algoritmo de aprendizaje automático

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 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 del árbol 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 conjuncionesde 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. ^{[1] [2]}

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. ^[3] El objetivo es crear un modelo que prediga el valor de una variable objetivo basándose en 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 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 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 entre 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 fuente , 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. ^[4] 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) ^[5] es un ejemplo de un algoritmo codiciosoy es, con mucho, la estrategia más común para aprender árboles de decisiones a partir de datos. ^{[ cita requerida ]}

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. ^{[ Cita requerida ]} )

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 utilizado para referirse a los dos procedimientos anteriores, introducido por primera vez por Breiman et al. en 1984. ^{[6] 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. ^[6]

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. ^{[7] [8]}
• Á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. ^[9]
  • Un clasificador de bosque aleatorio es un tipo específico de agregación de bootstrap
• Bosque de rotación : en el que cada árbol de decisión se entrena aplicando primero el análisis de componentes principales (PCA) en un subconjunto aleatorio de las características de entrada. ^[10]

Un caso especial de un árbol de decisión es una lista de decisiones , ^[11] que es un árbol de decisión unilateral, 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 hijo único es un nodo de una sola 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 ^[12] y restricciones monótonas. ^[13]

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) ^[6]
• Detección automática de interacción chi-cuadrado (CHAID). Realiza divisiones de varios niveles al calcular árboles de clasificación. ^[14]
• 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. ^{[15] [16]}

ID3 y CART se inventaron de forma independiente aproximadamente al mismo tiempo (entre 1970 y 1980) ^{[ cita requerida ]} , 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). ^[17] En este tipo de clasificación difusa, generalmente un vector de entrada se asocia con múltiples 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. ^[18]${\displaystyle {\textbf {x}}}$

Métricas

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. ^[19] 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 dan 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

No confundir con el coeficiente de Gini .

Utilizado por el algoritmo CART (árbol de clasificación y regresión) para árboles de clasificación, la impureza de 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 la 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

Artículo principal: Ganancia de información en árboles de decisió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},...,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. ^[20]${\displaystyle p_{1},p_{2},...}$

$${\displaystyle \overbrace {IG(T,a)} ^{\text{Information Gain}}=\overbrace {\mathrm {H} (T)} ^{\text{Entropy (parent)}}-\overbrace {\mathrm {H} (T|a)} ^{\text{Sum of Entropy (Children)}}}$$

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

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

$${\displaystyle \overbrace {E_{A}\left(IG(T,a)\right)} ^{\text{Expected Information Gain}}=\overbrace {I(T;A)} ^{\text{Mutual Information between T and A}}=\overbrace {\mathrm {H} (T)} ^{\text{Entropy (parent)}}-\overbrace {\mathrm {H} (T|A)} ^{\text{Weighted Sum of Entropy (Children)}}}$$

${\displaystyle =-\sum _{i=1}^{J}p_{i}\log _{2}{p_{i}}-\sum _{a}{p(a)\sum _{i=1}^{J}-\Pr(i|a)\log _{2}{\Pr(i|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". ^[20]

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 verdadero valor de viento , 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{windy or not}})={\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 IG({\text{windy}})=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. ^[20]

Reducción de la varianza

Introducida en CART, ^{[6] la} reducción de la varianza se emplea a menudo en casos donde 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 ser aplicada. 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\in S_{t}}\sum _{j\in 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, ^[21] la medida de "bondad" es una función que busca optimizar el equilibrio de la capacidad de una división candidata 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 \phi (s|t)}$${\displaystyle s}$${\displaystyle t}$

${\displaystyle \phi (s|t)=2P_{L}P_{R}\sum _{j=1}^{ClassCount}|P(j|t_{L})-P(j|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|t_{L})}$${\displaystyle P(j|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. ^[21] Los datos completos se presentan en el cuadro siguiente. 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 \phi (s|t)}$${\displaystyle \phi (s|t)}$

Cliente	Ahorros	Activos	Ingresos ($ 1000)	Riesgo crediticio
1	Medio	Elevado	75	Bien
2	Bajo	Bajo	50	Malo
3	Elevado	Medio	25	Malo
4	Medio	Medio	50	Bien
5	Bajo	Medio	100	Bien
6	Elevado	Elevado	25	Bien
7	Bajo	Bajo	25	Malo
8	Medio	Medio	75	Bien

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 manera que los registros con pocos ahorros se colocarán en el hijo izquierdo y todos los demás registros se colocarán en el hijo derecho.${\displaystyle \phi (s|t)}$${\displaystyle s}$

${\displaystyle \phi (s|root)=2{\frac {3}{8}}*{\frac {5}{8}}*(|({\frac {1}{3}}-{\frac {4}{5}})|+|({\frac {2}{3}}-{\frac {1}{5}})|)=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. ^[22]
• Capaz de manejar datos tanto numéricos como categóricos . ^[22] Otras técnicas suelen estar especializadas en el análisis de 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. ^[2]
• 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 . ^[22]
• Utiliza un modelo de caja blanca o caja abierta ^[2] . 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 estadístico 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. ^[22] Esto podría ser útil al modelar las decisiones y el comportamiento humanos.
• Robusto contra la colinealidad, particularmente potenciador
• En la selección de funciones integradas . 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. ^[23] Significa que las características en la parte superior son las más informativas. ^[24]
• Los árboles de decisión pueden aproximarse a cualquier función booleana, por ejemplo, XOR . ^[25]

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. ^[22]
• 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. ^{[26] [27]} 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). ^[28]
• 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 . ^[29] ) 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). ^{[15] [16]}
• 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. ^[30]
• 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. ^[31] Sin embargo, el problema de la selección sesgada de predictores se evita mediante el enfoque de inferencia condicional, ^[15] un enfoque de dos etapas, ^[32] o la selección adaptativa de características de dejar uno fuera. ^[33]

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), ^[6]
• 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). ^[34] 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. ^[35] 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. ^{[ cita requerida ]} 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 . ^{[36] [37]}

También es posible muestrear un árbol utilizando MCMC . ^[38]

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

Ver también

• Poda de árboles de decisión
• Diagrama de decisión binaria
• CHAID
• CARRO
• Algoritmo ID3
• Algoritmo C4.5
• Tocones de decisión , utilizados en, por ejemplo, AdaBoosting
• Lista de decisiones
• Árbol de decisión incremental
• Árbol de decisión alterno
• Análisis de datos estructurados (estadísticas)
• Árbol modelo logístico
• Agrupación jerárquica

Referencias

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 algoritmos en minería de datos". Sistemas de conocimiento e información . 14 (1): 1–37. doi : 10.1007 / s10115-007-0114-2 . hdl : 10983/15329 . ISSN  0219-3116 . S2CID  2367747 .
2. Piryonesi S. Madeh; El-Diraby Tamer E. (1 de marzo de 2020). "Análisis de datos en la gestión de activos: predicción rentable del índice de condición del pavimento". Revista de sistemas de infraestructura . 26 (1): 04019036. doi : 10.1061 / (ASCE) IS.1943-555X.0000512 .
3. Rokach, Lior; Maimón, O. (2008). Minería de datos con árboles de decisión: teoría y aplicaciones . World Scientific Pub Co Inc. ISBN 978-9812771711.
4. Shalev-Shwartz, Shai; Ben-David, Shai (2014). "18. Árboles de decisión". Comprensión del aprendizaje automático . Prensa de la Universidad de Cambridge.
5. Quinlan, JR (1986). "Inducción de árboles de decisión" (PDF) . Aprendizaje automático . 1 : 81-106. doi : 10.1007 / BF00116251 . S2CID 189902138 .  
6. Breiman, Leo; Friedman, JH; Olshen, RA; Stone, CJ (1984). Árboles de clasificación y regresión . Monterey, CA: Wadsworth & Brooks / Cole Advanced Books & Software. ISBN 978-0-412-04841-8.
7. Friedman, JH (1999). Impulso del gradiente estocástico . Universidad Stanford.
8. Hastie, T., Tibshirani, R., Friedman, JH (2001). Los elementos del aprendizaje estadístico: minería de datos, inferencia y predicción. Nueva York: Springer Verlag.
9. Breiman, L. (1996). "Predictores de embolsado" . Aprendizaje automático . 24 (2): 123–140. doi : 10.1007 / BF00058655 .
10. Rodríguez, JJ; Kuncheva, LI; Alonso, CJ (2006). "Bosque de rotación: un nuevo método de conjunto clasificador". Transacciones IEEE sobre análisis de patrones e inteligencia de máquinas . 28 (10): 1619-1630. CiteSeerX 10.1.1.156.8277 . doi : 10.1109 / TPAMI.2006.211 . PMID 16986543 . S2CID 6847493 .   
11. Rivest, Ron (noviembre de 1987). "Listas de decisiones de aprendizaje" (PDF) . Aprendizaje automático . 3 (2): 229–246. doi : 10.1023 / A: 1022607331053 . S2CID 30625841 .  
12. Letham, Ben; Rudin, Cynthia ; McCormick, Tyler; Madigan, David (2015). "Clasificadores interpretables usando reglas y análisis bayesiano: construcción de un mejor modelo de predicción de trazos". Annals of Applied Statistics . 9 (3): 1350-1371. arXiv : 1511.01644 . doi : 10.1214 / 15-AOAS848 . S2CID 17699665 . 
13. Wang, Fulton; Rudin, Cynthia (2015). "Listas de reglas descendentes" (PDF) . Revista de investigación sobre aprendizaje automático . 38 .
14. Kass, GV (1980). "Una técnica exploratoria para investigar grandes cantidades de datos categóricos". Estadísticas aplicadas . 29 (2): 119-127. doi : 10.2307 / 2986296 . JSTOR 2986296 . 
15. Hothorn, T .; Hornik, K .; Zeileis, A. (2006). "Particionamiento recursivo imparcial: un marco de inferencia condicional". Revista de Estadística Computacional y Gráfica . 15 (3): 651–674. CiteSeerX 10.1.1.527.2935 . doi : 10.1198 / 106186006X133933 . JSTOR 27594202 . S2CID 6074128 .   
16. Strobl, C .; Malley, J .; Tutz, G. (2009). "Una introducción al particionamiento recursivo: fundamento, aplicación y características de los árboles de clasificación y regresión, ensacado y bosques aleatorios" . Métodos psicológicos . 14 (4): 323–348. doi : 10.1037 / a0016973 . PMC 2927982 . PMID 19968396 .  
17. Janikow, CZ (1998). "Árboles de decisión difusos: problemas y métodos". Transacciones IEEE sobre sistemas, hombre y cibernética, parte B (cibernética) . 28 (1): 1-14. doi : 10.1109 / 3477.658573 . PMID 18255917 . 
18. Barsacchi, M .; Bechini, A .; Marcelloni, F. (2020). "Un análisis de conjuntos potenciados de árboles de decisión difusa binarios" . Sistemas expertos con aplicaciones . 154 : 113436. doi : 10.1016 / j.eswa.2020.113436 .
19. Rokach, L .; Maimón, O. (2005). "Inducción de arriba hacia abajo de clasificadores de árboles de decisión-una encuesta". Transacciones IEEE sobre sistemas, hombre y cibernética - Parte C: Aplicaciones y revisiones . 35 (4): 476–487. CiteSeerX 10.1.1.458.7031 . doi : 10.1109 / TSMCC.2004.843247 . S2CID 14808716 .  
20. Witten, Ian; Frank, Eibe; Hall, Mark (2011). Minería de datos . Burlington, MA: Morgan Kaufmann. pp.  102 -103. ISBN 978-0-12-374856-0.
21. Larose, Daniel T .; Larose, Chantal D. (2014). Descubriendo el conocimiento en los datos: una introducción a la minería de datos . Hoboken, Nueva Jersey: John Wiley & Sons, Inc. ISBN 9781118874059.
22. Gareth, James; Witten, Daniela; Hastie, Trevor; Tibshirani, Robert (2015). Introducción al aprendizaje estadístico . Nueva York: Springer. págs.  315 . ISBN 978-1-4614-7137-0.
23. Provost, Foster, 1964- (2013). Ciencia de datos para empresas: [lo que necesita saber sobre la minería de datos y el pensamiento analítico de datos] . Fawcett, Tom. (1ª ed.). Sebastopol, California: O'Reilly. ISBN 978-1-4493-6132-7. OCLC  844460899 .
24. Piryonesi S. Madeh; El-Diraby Tamer E. (1 de junio de 2020). "Papel de la analítica de datos en la gestión de activos de infraestructura: superación de problemas de calidad y tamaño de datos". Revista de Ingeniería de Transporte, Parte B: Pavimentos . 146 (2): 04020022. doi : 10.1061 / JPEODX.0000175 .
25. Mehtaa, Dinesh; Raghavan, Vijay (2002). "Aproximaciones de árbol de decisión de funciones booleanas". Informática Teórica . 270 (1–2): 609–623. doi : 10.1016 / S0304-3975 (01) 00011-1 .
26. Hyafil, Laurent; Rivest, RL (1976). "La construcción de árboles de decisión binaria óptimos es NP-completo". Cartas de procesamiento de información . 5 (1): 15-17. doi : 10.1016 / 0020-0190 (76) 90095-8 .
27. Murthy S. (1998). "Construcción automática de árboles de decisión a partir de datos: una encuesta multidisciplinaria" . Minería de datos y descubrimiento de conocimientos
28. Ben-Gal I. Dana A., Shkolnik N. y Singer (2014). "Construcción eficiente de árboles de decisión por el método de distancia de información dual" (PDF) . Tecnología de calidad y gestión cuantitativa . 11 (1): 133-147. doi : 10.1080 / 16843703.2014.11673330 . S2CID 7025979 .  
29. Principios de minería de datos . 2007. doi : 10.1007 / 978-1-84628-766-4 . ISBN 978-1-84628-765-7.
30. Ben-Gal I. y Trister C. (2015). "Construcción en paralelo de árboles de decisión con un número esperado de pruebas que no aumenta constantemente" (PDF) . Modelos estocásticos aplicados en los negocios y la industria, vol. 31 (1) 64-78.
31. Deng, H .; Runger, G .; Tuv, E. (2011). Medidas de sesgo de importancia para atributos y soluciones de valores múltiples . Actas de la 21ª Conferencia Internacional sobre Redes Neuronales Artificiales (ICANN). págs. 293–300.
32. Brandmaier, Andreas M .; Oertzen, Timo von; McArdle, John J .; Lindenberger, Ulman (2012). "Árboles modelo de ecuaciones estructurales" . Métodos psicológicos . 18 (1): 71–86. doi : 10.1037 / a0030001 . hdl : 11858 / 00-001M-0000-0024-EA33-9 . PMC 4386908 . PMID 22984789 .  
33. Painsky, Amichai; Rosset, Saharon (2017). "La selección de variables con validación cruzada en métodos basados ​​en árboles mejora el rendimiento predictivo". Transacciones IEEE sobre análisis de patrones e inteligencia de máquinas . 39 (11): 2142–2153. arXiv : 1512.03444 . doi : 10.1109 / TPAMI.2016.2636831 . PMID 28114007 . S2CID 5381516 .  
34. "CiteSeerX" .
35. Tan y Dowe (2003)
36. Papagelis, A .; Kalles, D. (2001). "Reproducción de árboles de decisión mediante técnicas evolutivas" (PDF) . Actas de la Decimoctava Conferencia Internacional sobre Aprendizaje Automático, del 28 de junio al 1 de julio de 2001 . págs. 393–400.
37. Barros, Rodrigo C .; Basgalupp, MP; Carvalho, ACPLF; Freitas, Alex A. (2012). "Una encuesta de algoritmos evolutivos para la inducción del árbol de decisión". Transacciones IEEE sobre sistemas, hombre y cibernética . Parte C: Aplicaciones y revisiones. 42 (3): 291–312. CiteSeerX 10.1.1.308.9068 . doi : 10.1109 / TSMCC.2011.2157494 . S2CID 365692 .  
38. Chipman, Hugh A .; George, Edward I .; McCulloch, Robert E. (1998). "Búsqueda de modelos de CARRITO Bayesiano". Revista de la Asociación Estadounidense de Estadística . 93 (443): 935–948. CiteSeerX 10.1.1.211.5573 . doi : 10.1080 / 01621459.1998.10473750 . 
39. Barros, RC; Cerri, R .; Jaskowiak, PA; Carvalho, ACPLF (2011). "Un algoritmo de inducción de árbol de decisión oblicua de abajo hacia arriba". Actas de la XI Conferencia Internacional sobre Diseño y Aplicaciones de Sistemas Inteligentes (ISDA 2011) . págs. 450–456. doi : 10.1109 / ISDA.2011.6121697 . ISBN 978-1-4577-1676-8. S2CID  15574923 .

Lectura adicional

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