Aprendizaje del árbol de decisión

Algoritmo de aprendizaje automático

El aprendizaje de árboles de decisión es un enfoque de aprendizaje supervisado que se utiliza en estadística , minería de datos y aprendizaje automático . En este formalismo, se utiliza un árbol de decisión de clasificación o regresión como modelo predictivo para sacar conclusiones sobre un conjunto de observaciones.

Los modelos de árbol en los que la variable objetivo 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 donde la variable objetivo puede tomar valores continuos (normalmente números reales ) se denominan árboles de regresión . De manera más general, el concepto de árbol de regresión se puede extender a cualquier tipo de objeto equipado con diferencias por pares, como secuencias categóricas. ^[1]

Los árboles de decisión se encuentran entre los algoritmos de aprendizaje automático más populares debido a su inteligibilidad y simplicidad. ^[2]

En el análisis de decisiones, se puede utilizar un árbol de decisiones para representar visual y explícitamente las decisiones y la toma de decisiones . En la minería de datos , un árbol de decisión describe los datos (pero el árbol de clasificación resultante puede ser un insumo para la toma de decisiones).

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: Tus posibilidades de supervivencia eran buenas si eras (i) una mujer o (ii) un hombre de como máximo 9,5 años y estrictamente menos de 3 hermanos.

El aprendizaje de árboles de decisión es un método comúnmente utilizado en la minería de datos. ^[3] El objetivo es crear un modelo que prediga el valor de una variable objetivo en función de varias variables de entrada.

Un árbol de decisión es una representación simple para clasificar ejemplos. Para esta sección, supongamos que todas las características de entrada tienen dominios discretos finitos y que hay una única característica objetivo llamada "clasificación". Cada elemento del dominio de la clasificación se denomina clase . Un árbol de decisión o árbol de clasificación es un árbol en el que cada nodo interno (que no es hoja) está etiquetado con una característica de entrada. Los arcos que provienen de un nodo etiquetado con una característica de entrada están etiquetados con cada uno de los valores posibles de la característica objetivo 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 conjunto de datos ha sido clasificado por el árbol 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 forma 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 arriba hacia abajo de árboles de decisión (TDIDT) ^[5] es un ejemplo de algoritmo codicioso y es, con diferencia, la estrategia más común para aprender árboles de decisión a partir de datos. ^[6]

En minería de datos , los árboles de decisión también pueden describirse 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 determinado de datos.

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 intentamos comprender, clasificar o generalizar. El vector se compone de 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 trama en perspectiva. Derecha Vista aérea de la parcela del medio. La probabilidad de cifosis después de la cirugía es mayor en las zonas más oscuras. (Nota: el tratamiento de la cifosis ha avanzado considerablemente desde que se recopiló este conjunto bastante pequeño de datos. ^{[ cita necesaria ]} )

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 se produce cuando el resultado previsto es la clase (discreta) a la que pertenecen los datos.
• El análisis de árbol de regresión se produce 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 cualquiera de los procedimientos anteriores, introducido por primera vez por Breiman et al. en 1984. ^[7] 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. ^[7]

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

• Árboles impulsados ​​Construir incrementalmente un conjunto entrenando cada nueva instancia para enfatizar las instancias de entrenamiento previamente modeladas incorrectamente. Un ejemplo típico es AdaBoost . Estos se pueden utilizar para problemas de tipo regresión y clasificación. ^{[8] [9]}
• Los árboles de decisión agregados (o en bolsas) de Bootstrap , un método de conjunto temprano, construye múltiples árboles de decisión remuestreando repetidamente los datos de entrenamiento con reemplazo y votando los árboles para una predicción de consenso. ^[10]
  • Un clasificador de bosque aleatorio es un tipo específico de agregación de arranque
• 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. ^[11]

Un caso especial de árbol de decisión es una lista de decisión , ^[12] 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 El único hijo es un nodo de una sola hoja). Si bien son menos expresivas, las listas de decisiones son posiblemente más fáciles de entender que los árboles de decisión generales debido a su escasez adicional ^{[ cita necesaria ]} , permiten imponer métodos de aprendizaje no codiciosos ^{[13] y restricciones monótonas. [14]}

Los algoritmos de árboles de decisión notables incluyen:

• ID3 (dicotomizador iterativo 3)
• C4.5 (sucesor de ID3)
• CART (árbol de clasificación y regresión) ^[7]
• Detección automática de interacción chi-cuadrado (CHAID). Realiza divisiones de varios niveles al calcular árboles de clasificación. ^{[15] [16] [17]}
• MARS : amplía los árboles de decisión para manejar mejor los datos numéricos.
• Árboles de inferencia condicional. Enfoque basado en estadísticas que utiliza pruebas no paramétricas como criterio de división, corregido para pruebas múltiples para evitar el sobreajuste. Este enfoque da como resultado una selección de predictores imparcial y no requiere poda. ^{[18] [19]}

ID3 y CART se inventaron de forma independiente aproximadamente al mismo tiempo (entre 1970 y 1980) ^{[ cita necesaria ]} , pero siguen un enfoque similar para aprender un árbol de decisión 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). ^[20] En este tipo de clasificación difusa, generalmente, un vector de entrada está asociado con múltiples clases, cada una con un valor de confianza diferente. También se han investigado recientemente conjuntos potenciados de FDT y han mostrado rendimientos comparables a los de otros clasificadores difusos muy eficientes. ^[21] ${\displaystyle {\textbf {x}}}$

Métrica

Los algoritmos para construir árboles de decisión generalmente funcionan de arriba hacia abajo, eligiendo en cada paso una variable que mejor divida el conjunto de elementos. ^[6] Diferentes algoritmos utilizan diferentes métricas para medir "lo mejor". 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, se promedian) para proporcionar una medida de la calidad de la división. Dependiendo de la métrica subyacente, el rendimiento de varios algoritmos heurísticos para el aprendizaje de árboles de decisión puede variar significativamente. ^[22]

Estimación de la corrección positiva

Se puede utilizar una métrica simple y eficaz para identificar el grado en que los verdaderos positivos superan a los falsos positivos (consulte Matriz de confusión ). Esta métrica, "Estimación de corrección positiva", se define a continuación:

${\displaystyle E_{P}=TP-FP}$

En esta ecuación, el total de falsos positivos (FP) se resta del total de verdaderos positivos (TP). El número resultante proporciona una estimación de cuántos ejemplos positivos la característica podría identificar correctamente dentro de los datos, y los números más altos significan que la característica podría clasificar correctamente más muestras positivas. A continuación se muestra un ejemplo de cómo utilizar la métrica cuando se proporciona la matriz de confusión completa de una determinada característica:

Presentar una matriz de confusión

Aquí podemos ver que el valor de TP sería 8 y el valor de FP sería 2 (los números subrayados en la tabla). Cuando reemplazamos estos números en la ecuación, podemos calcular la estimación: . Esto significa que usar la estimación de esta característica le daría una puntuación de 6. ${\displaystyle E_{p}=TP-FP=8-2=6}$

Sin embargo, cabe señalar que esta cifra es sólo una estimación. Por ejemplo, si dos características tenían un valor de FP de 2 mientras que una de las características tenía un valor de TP más alto, esa característica se clasificaría más arriba que la otra porque la estimación resultante al usar la ecuación daría un valor más alto. Esto podría generar algunas imprecisiones al utilizar la métrica si algunas características tienen más muestras positivas que otras. Para combatir esto, se podría utilizar una métrica más potente conocida como Sensibilidad , que tiene en cuenta las proporciones de los valores de la matriz de confusión para dar la tasa de verdaderos positivos (TPR). La diferencia entre estas métricas se muestra en el siguiente ejemplo:

En este ejemplo, la Característica A tenía una estimación de 6 y una TPR de aproximadamente 0,73, mientras que la Característica B tenía una estimación de 4 y una TPR de 0,75. Esto muestra que aunque la estimación positiva para alguna característica puede ser mayor, el valor TPR más preciso para esa característica puede ser menor en comparación con otras características que tienen una estimación positiva más baja. Dependiendo de la situación y el conocimiento de los datos y los árboles de decisión, se puede optar por utilizar la estimación positiva para una solución rápida y sencilla a su problema. Por otro lado, un usuario más experimentado probablemente preferiría utilizar el valor TPR para clasificar las características porque tiene en cuenta las proporciones de los datos y todas las muestras que deberían haberse clasificado como positivas.

impureza de gini

La impureza de Gini , índice de diversidad de Gini , ^[23] o índice de Gini-Simpson en la investigación de la biodiversidad, lleva el nombre del matemático italiano Corrado Gini y lo utiliza el algoritmo CART (árbol de clasificación y regresión) para clasificar árboles. La impureza de Gini mide la frecuencia con la que un elemento de un conjunto elegido al azar sería etiquetado incorrectamente si se etiquetara de forma aleatoria e independiente según la distribución de etiquetas en el conjunto. Alcanza su mínimo (cero) cuando todos los casos del nodo caen en una única categoría objetivo.

Para un conjunto de elementos con clases y frecuencias relativas , la probabilidad de elegir un elemento con etiqueta es y la probabilidad de categorizar erróneamente ese elemento es . La impureza de Gini se calcula sumando los productos por pares de estas probabilidades para cada etiqueta de clase: ${\displaystyle J}$ ${\displaystyle p_{i}}$ ${\displaystyle i\in \{1,2,...,J\}}$ ${\displaystyle i}$ ${\displaystyle p_{i}}$ ${\displaystyle \sum _{k\neq i}p_{k}=1-p_{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}.}$

La impureza de Gini también es 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 fuera de equilibrio, 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 los árboles de decisión. ${\displaystyle q=2}$ ${\displaystyle q\to 1}$

Ganancia de información

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

La entropía se define como 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. ^[24] ${\displaystyle p_{1},p_{2},\ldots }$

$${\displaystyle \overbrace {IG(T,a)} ^{\text{information gain}}=\overbrace {\mathrm {H} (T)} ^{\text{entropy (parent)}}-\overbrace {\mathrm {H} (T\mid a)} ^{\text{sum of entropies (children)}}}$$

${\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 valores posibles de , ${\displaystyle A}$

$${\displaystyle \overbrace {E_{A}(\operatorname {IG} (T,a))} ^{\text{expected information gain}}=\overbrace {I(T;A)} ^{{\text{mutual information between }}T{\text{ and }}A}=\overbrace {\mathrm {H} (T)} ^{\text{entropy (parent)}}-\overbrace {\mathrm {H} (T\mid A)} ^{\text{weighted sum of entropies (children)}}}$$

${\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)}$

Donde la suma ponderada de entropías viene dada por,

${\displaystyle {\mathrm {H} (T\mid A)}=\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 en la entropía de T es la información mutua.

La ganancia de información se utiliza para decidir en qué característica dividirse en cada paso de la construcción del árbol. La simplicidad es lo mejor, por eso queremos mantener nuestro árbol pequeño. Para hacerlo, en cada paso debemos elegir la división que dé como resultado los nodos secundarios más consistentes. Una medida de coherencia comúnmente utilizada se llama información y 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 sí o no, dado que el ejemplo llegó a ese nodo". ^[24]

Considere un conjunto de datos de ejemplo con cuatro atributos: perspectiva (soleado, nublado, lluvioso), temperatura (caliente, templada, fría), humedad (alta, normal) y viento (verdadero, falso), con un binario (sí o no). variable objetivo, juego y 14 puntos de datos. Para construir un árbol de decisión con estos datos, necesitamos comparar la ganancia de información de cada uno de los cuatro árboles, cada uno dividido 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 utilizando la característica windy da como resultado dos nodos secundarios, uno para un valor windy de verdadero y otro para un valor windy de falso. En este conjunto de datos, hay seis puntos de datos con un valor de viento verdadero , 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 windy =true 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 windy =false 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 al dividir la función de viento .

${\displaystyle \operatorname {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. ^[24]

La ganancia de información también se conoce como índice de Shannon en la investigación de la biodiversidad.

Reducción de varianza

Introducida en CART, ^[7] la reducción de la varianza se emplea a menudo en casos en los 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\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 muestrales predivididos, el conjunto de índices muestrales para los cuales la prueba dividida es verdadera y el conjunto de índices muestrales para los cuales la prueba dividida es falsa, respectivamente. Sin embargo , cada uno de los sumandos anteriores son de hecho estimaciones de la varianza , escritas en una forma sin hacer referencia directa a la media. ${\displaystyle S}$ ${\displaystyle S_{t}}$ ${\displaystyle S_{f}}$

Al reemplazar en la fórmula anterior con la disimilitud entre dos objetos y , el criterio de reducción de la varianza se aplica a cualquier tipo de objeto para el cual se puedan calcular disimilitudes por pares. ^[1] ${\displaystyle (y_{i}-y_{j})^{2}}$ ${\displaystyle d_{ij}}$ ${\displaystyle i}$ ${\displaystyle j}$

Medida de "bondad"

Utilizada por CART en 1984, ^[25] la medida de "bondad" es una función que busca optimizar el equilibrio entre la capacidad de una división candidata para crear hijos puros y su capacidad para crear hijos del mismo tamaño. Este proceso se repite para cada nodo impuro hasta que se completa el árbol. La función , donde hay un candidato dividido 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{class count}}|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 in y , respectivamente; y y son las proporciones de los 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. ^[25] Los datos completos se presentan en el cuadro siguiente. Para iniciar un árbol de decisión, calcularemos el valor máximo de uso de 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 el ahorro de funciones , debemos anotar la cantidad de cada valor. Los datos originales contenían tres mínimos, tres medios y dos máximos. De los niveles bajos, uno tenía un buen riesgo crediticio , mientras que de los niveles medio y alto, 4 tenían un buen riesgo crediticio . Supongamos que un candidato se divide de manera que los registros con ahorros bajos se colocarán en el hijo izquierdo y todos los demás registros se colocarán en el hijo derecho. ${\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 consistente. Sin embargo, sacrifica cierta prioridad para crear hijos puros, lo que puede llevar a divisiones adicionales que no están presentes en 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. ^[26]
• Capaz de manejar datos tanto numéricos como categóricos . ^[26] 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 solo se pueden usar 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 eran capaces de manejar variables categóricas, pero las versiones más recientes, como como C4.5, no tienen esta limitación. ^[3]
• Requiere poca preparación de datos. Otras técnicas suelen requerir la normalización de los datos. Dado que los árboles pueden manejar predictores cualitativos, no es necesario crear variables ficticias . ^[26]
• Utiliza un modelo de caja blanca o de caja abierta ^[3] . Si una situación dada es observable en un modelo, la explicación de la condición se explica fácilmente mediante la 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 .
• Es posible validar un modelo mediante pruebas estadísticas. Eso permite dar cuenta de la confiabilidad 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.
• Precisión con modelado flexible . Estos métodos pueden aplicarse a la investigación sanitaria con mayor precisión. ^[27]
• Refleja la toma de decisiones humana más fielmente que otros enfoques. ^[26] Esto podría ser útil al modelar decisiones/comportamientos humanos.
• Robusto contra la colinealidad, particularmente el impulso.
• 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 decisión refleja la importancia de los atributos. ^[28] Significa que las funciones de arriba son las más informativas. ^[29]
• Los árboles de decisión pueden aproximarse a cualquier función booleana, por ejemplo, XOR . ^[30]

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. ^[26]
• Se sabe que el problema de aprender un árbol de decisión óptimo es NP-completo en varios aspectos de optimización e incluso para conceptos simples. ^{[31] [32]} En consecuencia, los algoritmos prácticos de aprendizaje de árboles de decisiones se basan en heurísticas como el algoritmo codicioso donde se toman decisiones localmente óptimas en cada nodo. Dichos algoritmos no pueden garantizar que se devuelva el árbol de decisión globalmente óptimo. Para reducir el efecto codicioso de la optimización local, se propusieron algunos métodos como el árbol de distancia de información dual (DID). ^[33]
• Los estudiantes de árboles de decisiones pueden crear árboles demasiado complejos que no se generalizan bien a partir de los datos de entrenamiento. (Esto se conoce como sobreajuste . ^[34] ) 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). ^{[18] [19]}
• 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 según varios criterios de división. ^[35]
• Para datos que incluyen variables categóricas con diferente número de niveles, la ganancia de información en los árboles de decisión está sesgada a favor de atributos con más niveles. ^[36] Para contrarrestar este problema, en lugar de elegir el atributo con mayor ganancia de información , se puede elegir el atributo con la mayor proporción de ganancia de información entre los atributos cuya ganancia de información es mayor que la ganancia de información media. ^[37] Esto desvía el árbol de decisión para que no considere atributos con una gran cantidad de valores distintos, sin dar una ventaja injusta a los atributos con muy baja ganancia de información. Alternativamente, el problema de la selección sesgada de predictores se puede evitar mediante el enfoque de inferencia condicional, ^[18] un enfoque de dos etapas, ^[38] o la selección adaptativa de características de dejar una fuera. ^[39]

Implementaciones

Muchos paquetes de software de minería de datos proporcionan implementaciones de uno o más algoritmos de árboles de decisión (por ejemplo, bosque aleatorio).

Los ejemplos de código abierto incluyen:

• ALGLIB , una biblioteca de análisis numérico de C++, C# y Java con funciones de análisis de datos (bosque aleatorio)
• KNIME , una plataforma de análisis, generación de informes e integración de datos gratuita y de código abierto (árboles de decisión, bosque aleatorio)
• Orange , un conjunto de herramientas de visualización de datos, aprendizaje automático y minería de datos de código abierto (bosque aleatorio)
• R (un entorno de software de código abierto para computación estadística, que incluye varias implementaciones CART, como los paquetes rpart, party y randomForest),
• scikit-learn (una biblioteca de aprendizaje automático gratuita y de código abierto para el lenguaje de programación Python ).
• Weka (una suite de minería de datos gratuita y de código abierto que contiene muchos algoritmos de árboles de decisión),

Software comercial notable:

• MATLAB ,
• Microsoft SQL Server y
• minero rápido ,
• Minero empresarial SAS ,
• Modelador IBM SPSS ,

Extensiones

Gráficos de decisión

En un árbol de decisión, todas las rutas desde el nodo raíz hasta el nodo hoja proceden mediante una conjunción o AND . En un gráfico de decisión, es posible utilizar disyunciones (OR) para unir dos rutas más utilizando la longitud mínima del mensaje (MML). ^[40] 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. ^[41] 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 necesaria ]} En general, los gráficos de decisión infieren modelos con menos hojas que los árboles de decisión.

Métodos de búsqueda alternativos

Se han utilizado algoritmos evolutivos para evitar decisiones óptimas locales y buscar en el espacio del árbol de decisiones con poco sesgo a priori . ^{[42] [43]}

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

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

Ver también

• Poda de árboles de decisión
• Diagrama de decisión binaria
• chaid
• CARRO
• algoritmo ID3
• Algoritmo C4.5
• Elementos de decisión , utilizados, por ejemplo, en 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. Studer, Matías; Ritschard, Gilbert; Gabadinho, Alexis; Müller, Nicolás S. (2011). "Análisis de discrepancia de secuencias de estados". Investigación y métodos sociológicos . 40 (3): 471–510. doi :10.1177/0049124111415372. ISSN  0049-1241. S2CID  13307797.
2. 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). "Los 10 mejores algoritmos en minería de datos". Sistemas de Conocimiento y Información . 14 (1): 1–37. doi :10.1007/s10115-007-0114-2. hdl : 10983/15329 . ISSN  0219-3116. S2CID  2367747.
3. Rokach, Lior; Maimón, O. (2014). Minería de datos con árboles de decisión: teoría y aplicaciones, 2ª Edición . World Scientific Pub Co Inc. doi :10.1142/9097. ISBN 978-9814590075. S2CID  44697571.
4. Shalev-Shwartz, Shai; Ben-David, Shai (2014). "18. Árboles de decisión". Comprender el 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. 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. 
7. Breiman, Leo; Friedman, JH; Olshen, RA; Piedra, CJ (1984). Árboles de clasificación y regresión . Monterey, CA: Wadsworth & Brooks/Cole Advanced Books & Software. ISBN 978-0-412-04841-8.
8. Friedman, JH (1999). Impulso del gradiente estocástico Archivado el 28 de noviembre de 2018 en Wayback Machine . Universidad Stanford.
9. 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.
10. Breiman, L. (1996). "Predictores de embolsado". Aprendizaje automático . 24 (2): 123-140. doi : 10.1007/BF00058655 .
11. Rodríguez, JJ; Kuncheva, LI ; Alonso, CJ (2006). "Bosque de rotación: un nuevo método de conjunto de clasificadores". Transacciones IEEE sobre análisis de patrones e inteligencia artificial . 28 (10): 1619-1630. CiteSeerX 10.1.1.156.8277 . doi :10.1109/TPAMI.2006.211. PMID  16986543. S2CID  6847493. 
12. 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.
13. Letham, Ben; Rudin, Cynthia ; McCormick, Tyler; Madigan, David (2015). "Clasificadores interpretables que utilizan reglas y análisis bayesiano: creación de un mejor modelo de predicción de accidentes cerebrovasculares". Anales de Estadística Aplicada . 9 (3): 1350-1371. arXiv : 1511.01644 . doi :10.1214/15-AOAS848. S2CID  17699665.
14. Wang, Fulton; Rudin, Cynthia (2015). "Listas de reglas decrecientes" (PDF) . Revista de investigación sobre aprendizaje automático . 38 . Archivado desde el original (PDF) el 28 de enero de 2016 . Consultado el 22 de enero de 2016 .
15. 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.
16. Biggs, David; De Ville, Barry; Suen, Ed (1991). "Un método para elegir particiones multidireccionales para árboles de clasificación y decisión". Revista de Estadística Aplicada . 18 (1): 49–62. Código Bib : 1991JApSt..18...49B. doi :10.1080/02664769100000005. ISSN  0266-4763.
17. Ritschard, G. (2013), " CHAID and Early Supervised Tree Methods", en JJ McArdle y G. Ritschard (eds), Contemporary Issues in Exploratory Data Mining in the Behavioral Sciences , Quantitative Methodology Series, Nueva York: Routledge, páginas 48-74. Preimpresión
18. Hothorn, T.; Hornik, K.; Zeileis, A. (2006). "Partición recursiva 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. 
19. Strobl, C.; Malley, J.; Tutz, G. (2009). "Una introducción a la partición recursiva: 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. 
20. Janikow, CZ (1998). "Árboles de decisión difusos: cuestiones 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.
21. Barsacchi, M.; Bechini, A.; Marcelloni, F. (2020). "Un análisis de conjuntos potenciados de árboles de decisión binarios difusos". Sistemas Expertos con Aplicaciones . 154 : 113436. doi : 10.1016/j.eswa.2020.113436. S2CID  216369273.
22. Najmann, Oliver (1992). Técnicas y heurísticas para la adquisición de conocimiento simbólico a partir de ejemplos (Tesis). Tesis doctoral.
23. "Árboles de decisión en crecimiento". Trabajos de matemáticas .
24. Witten, Ian; Frank, Eibe; Salón, Mark (2011). Procesamiento de datos . Burlington, MA: Morgan Kaufmann. págs. 102-103. ISBN 978-0-12-374856-0.
25. Larose, Daniel T.; Larose, Chantal D. (2014). Descubriendo conocimiento en datos: una introducción a la minería de datos . Hoboken, Nueva Jersey: John Wiley & Sons, Inc. ISBN 9781118874059.
26. Gareth, James; Witten, Daniela; Hastie, Trevor; Tibshirani, Robert (2015). Una introducción al aprendizaje estadístico . Nueva York: Springer. págs.315. ISBN 978-1-4614-7137-0.
27. Hu, Liangyuan; Li, Lihua (1 de diciembre de 2022). "Uso del aprendizaje automático basado en árboles para estudios de salud: revisión de la literatura y series de casos". Revista Internacional de Investigación Ambiental y Salud Pública . 19 (23): 16080. doi : 10.3390/ijerph192316080 . ISSN  1660-4601. PMC 9736500 . PMID  36498153. 
28. Preboste, 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.{{cite book}}: CS1 maint: multiple names: authors list (link) CS1 maint: numeric names: authors list (link)
29. Piryonesi S. Madeh; El-Diraby Tamer E. (1 de junio de 2020). "Papel del análisis de datos en la gestión de activos de infraestructura: superar los problemas de calidad y tamaño de los datos". Revista de Ingeniería del Transporte, Parte B: Pavimentos . 146 (2): 04020022. doi : 10.1061/JPEODX.0000175. S2CID  216485629.
30. Mehtaa, Dinesh; Raghavan, Vijay (2002). "Aproximaciones de árboles de decisión de funciones booleanas". Informática Teórica . 270 (1–2): 609–623. doi : 10.1016/S0304-3975(01)00011-1 .
31. Hyafil, Laurent; Rivest, RL (1976). "La construcción de árboles de decisión binaria óptimos es NP-completa". Cartas de procesamiento de información . 5 (1): 15-17. doi :10.1016/0020-0190(76)90095-8.
32. Murthy S. (1998). "Construcción automática de árboles de decisión a partir de datos: una encuesta multidisciplinar". Minería de datos y descubrimiento de conocimientos
33. Ben-Gal I. Dana A., Shkolnik N. y Singer (2014). «Construcción eficiente de árboles de decisión mediante 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. Archivado desde el original (PDF) el 4 de junio de 2016 . Consultado el 13 de febrero de 2014 .
34. Principios de minería de datos . 2007.doi : 10.1007 /978-1-84628-766-4. ISBN 978-1-84628-765-7. S2CID  45746.
35. Ben-Gal I. y Trister C. (2015). "Construcción paralela 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. Archivado desde el original (PDF) el 5 de febrero de 2021 . Consultado el 30 de enero de 2021 .{{cite web}}: CS1 maint: numeric names: authors list (link)
36. Deng, H.; Runger, G.; Tuv, E. (2011). Medidas de sesgo de importancia para atributos y soluciones multivaluados. Actas de la 21ª Conferencia Internacional sobre Redes Neuronales Artificiales (ICANN). págs. 293–300.
37. Quinlan, J. Ross (1986). "Inducción de árboles de decisión". Aprendizaje automático . 1 (1): 81–106. doi : 10.1007/BF00116251 .
38. 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. 
39. Doloroso, 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 artificial . 39 (11): 2142-2153. arXiv : 1512.03444 . doi :10.1109/TPAMI.2016.2636831. PMID  28114007. S2CID  5381516.
40. "CiteSeerX".
41. Bronceado y Dowe (2003)
42. Papagelis, A.; Kalles, D. (2001). "Mejoramiento de árboles de decisión utilizando técnicas evolutivas" (PDF) . Actas de la Decimoctava Conferencia Internacional sobre Aprendizaje Automático, 28 de junio al 1 de julio de 2001 . págs. 393–400.
43. Barros, Rodrigo C.; Basgalupp, diputado; Carvalho, ACPLF; Freitas, Alex A. (2012). "Un estudio de algoritmos evolutivos para la inducción de árboles 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. 
44. Chipman, Hugh A.; Jorge, Eduardo I.; McCulloch, Robert E. (1998). "Búsqueda de modelo CART 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. 
45. Barros, RC; Cerri, R.; Jaskowiak, Pensilvania; Carvalho, ACPLF (2011). "Un algoritmo de inducción de árbol de decisión oblicuo ascendente". Actas de la 11ª 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.

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.