Aprendizaje mediante árboles de decisión

Algoritmo de aprendizaje automático

El aprendizaje mediante á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 extraer 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 en los que la variable objetivo puede tomar valores continuos (normalmente números reales ) se denominan árboles de regresión . De forma más general, el concepto de árbol de regresión se puede extender a cualquier tipo de objeto equipado con disimilitudes por pares, como las 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 decisiones 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: sus posibilidades de supervivencia eran buenas si usted era (i) una mujer o (ii) un hombre de 9,5 años como máximo 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 en función de varias variables de entrada.

Un árbol de decisión es una representación sencilla 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 de destino denominada "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 están etiquetados 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 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 de origen , 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 llamada partición recursiva . La recursión se completa cuando el subconjunto en un nodo tiene todos los mismos valores de la variable de destino, 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 un algoritmo voraz , y es por lejos 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 dado de datos.

Los datos vienen en registros del formato:

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

Ejemplo de árbol 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. Centro El árbol como un gráfico en perspectiva. Derecha Vista aérea del gráfico del medio. 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 conjunto de datos bastante pequeño. ^{[ 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 de á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 estadía de un paciente en un hospital).

El término análisis de árboles 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 potenciados Generación incremental de un conjunto mediante el entrenamiento de cada nueva instancia para enfatizar las instancias de entrenamiento que previamente se modelaron incorrectamente. Un ejemplo típico es AdaBoost . Estos pueden usarse para problemas de tipo regresión y tipo clasificación. ^{[8] [9]}
• Comités de árboles de decisión (también llamados k-DT ^[10] ), un método temprano que utilizaba algoritmos de árboles de decisión aleatorios para generar múltiples árboles diferentes a partir de los datos de entrenamiento y luego combinarlos mediante votación por mayoría para generar resultados. ^[11]
• Los árboles de decisión agregados (o empaquetados) de Bootstrap, un método de conjunto temprano, construyen múltiples árboles de decisión remuestreando repetidamente los datos de entrenamiento con reemplazo y votando los árboles para una predicción de consenso. ^[12]
  • Un clasificador de bosque aleatorio es un tipo específico de agregación 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. ^[13]

Un caso especial de un árbol de decisión es una lista de decisiones , ^[14] 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 bajo, cuyo único hijo es un nodo hoja único). 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 requerida ]} , permiten métodos de aprendizaje no voraces ^[15] y la imposición de restricciones monótonas. ^[16]

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]
• OC1 (Clasificador oblicuo 1). Primer método que creó divisiones multivariadas en cada nodo. ^[17]
• Detección automática de interacción de chi-cuadrado (CHAID). Realiza divisiones de múltiples niveles al calcular árboles de clasificación. ^{[18] [19] [20]}
• MARS : extiende 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 criterios de división, corregidos para pruebas múltiples a fin de evitar el sobreajuste. Este enfoque da como resultado una selección de predictores imparcial y no requiere poda. ^{[21] [22]}

ID3 y CART se inventaron independientemente 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). ^[23] 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. Recientemente también se han investigado conjuntos potenciados de FDT, y han demostrado rendimientos comparables a los de otros clasificadores difusos muy eficientes. ^[24] ${\displaystyle {\textbf {x}}}$

Métrica

Los algoritmos para construir árboles de decisión suelen funcionar de arriba hacia abajo, eligiendo una variable en cada paso que mejor divida el conjunto de elementos. ^[6] Diferentes algoritmos utilizan diferentes métricas para medir lo "mejor". Estas 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, 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. ^[25]

Estimación de la corrección positiva

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

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

En esta ecuación, los falsos positivos (FP) totales se restan de los verdaderos positivos (TP) totales. El número resultante proporciona una estimación de cuántos ejemplos positivos la característica podría identificar correctamente dentro de los datos; 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:

Matriz de confusión de la característica A

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 introducimos estos números en la ecuación, podemos calcular la estimación: . Esto significa que si se utiliza la estimación en esta función, se obtendrá una puntuación de 6. ${\displaystyle E_{p}=TP-FP=8-2=6}$

Sin embargo, cabe señalar que este número es solo una estimación. Por ejemplo, si dos características tuvieran un valor FP de 2 mientras que una de ellas tuviera un valor TP más alto, esa característica se clasificaría más alta que la otra porque la estimación resultante al utilizar 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) real. 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 un TPR de aproximadamente 0,73, mientras que la característica B tenía una estimación de 4 y un TPR de 0,75. Esto demuestra 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 menor. Según la situación y el conocimiento de los datos y los árboles de decisión, uno 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 ^[26] o índice de Gini-Simpson en la investigación sobre biodiversidad, recibe su nombre del matemático italiano Corrado Gini y es utilizado por el algoritmo CART (árbol de clasificación y regresión) para árboles de clasificación. La impureza de Gini mide la frecuencia con la que un elemento elegido aleatoriamente de un conjunto sería etiquetado incorrectamente si se etiquetara aleatoriamente e independientemente de acuerdo con la distribución de etiquetas en el conjunto. Alcanza su mínimo (cero) cuando todos los casos en el nodo caen en una sola 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 incorrectamente ese elemento es . La impureza de Gini se calcula sumando 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 es también una medida de la teoría de la información y corresponde a la entropía de Tsallis con coeficiente de deformación , que en física se asocia a la falta de información en sistemas fuera de equilibrio, no extensivos, disipativos y cuánticos. Para el límite se recupera la habitual entropía de Boltzmann-Gibbs o de Shannon. En este sentido, la impureza de Gini no es otra cosa que una variación de la medida habitual de entropía para á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 de la siguiente manera

${\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 secundario que resulta de una división en el árbol. ^[27] ${\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 de la entropía de T es la información mutua.

La ganancia de información se utiliza para decidir en qué característica dividir en cada paso de la construcción del árbol. La simplicidad es lo mejor, por lo que queremos mantener nuestro árbol pequeño. Para ello, en cada paso debemos elegir la división que dé como resultado los nodos secundarios más consistentes. Una medida de consistencia que se utiliza habitualmente se denomina 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". ^[27]

Considere un conjunto de datos de ejemplo con cuatro atributos: perspectiva (soleado, nublado, lluvioso), temperatura (caliente, templado, fresco), humedad (alta, normal) y viento (verdadero, falso), con una variable de destino binaria (sí o no), play 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 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 utilizando windy , primero debemos calcular la información en los datos antes de la división. Los datos originales contenían nueve respuestas afirmativas y cinco negativas.

${\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 mediante la función 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 windy verdadero , tres de los cuales tienen un valor play (donde play es la variable objetivo) de sí y tres con un valor play de no. Los ocho puntos de datos restantes con un valor windy 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íes y noes 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. Por lo tanto, 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 en la característica ventosa .

${\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, se debe calcular la ganancia de información de cada primera división posible. 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 es una adaptación del ejemplo que aparece en Witten et al. ^[27].

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

Reducción de la varianza

Introducida en CART, ^[7] la reducción de 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 requeriría primero la discretización antes de ser aplicadas. La reducción de 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 previos a la división, el conjunto de índices de muestra para los cuales la prueba dividida es verdadera y el conjunto de índices de muestra para los cuales la prueba dividida es falsa, respectivamente. Cada uno de los sumandos anteriores son, de hecho, estimaciones de varianza , aunque escritas en una forma que no hace referencia directa a la media. ${\displaystyle S}$ ${\displaystyle S_{t}}$ ${\displaystyle S_{f}}$

Al reemplazar en la fórmula anterior la disimilitud entre dos objetos y , el criterio de reducción de 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 la "bondad"

Utilizada por CART en 1984, ^[28] la medida de "bondad" es una función que busca optimizar el equilibrio de la capacidad de una división candidata para crear hijos puros con su capacidad para crear hijos de igual tamaño. Este proceso se repite para cada nodo impuro hasta que el árbol esté completo. La función , donde es una división candidata en el nodo , se define como sigue ${\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 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}}$

Consideremos un conjunto de datos de ejemplo con tres atributos: ahorros (bajos, medios, altos), activos (bajos, medios, altos), ingresos (valor numérico) y una variable objetivo binaria, el riesgo crediticio (bueno, malo) y 8 puntos de datos. ^[28] Los datos completos se presentan en la tabla a continuación. Para iniciar un árbol de decisiones, 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 hijos 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 la característica de ahorro , necesitamos anotar la cantidad de cada valor. Los datos originales contenían tres valores bajos, tres valores medios y dos valores altos. De los valores bajos, uno tenía un buen riesgo crediticio , mientras que de los valores medios y altos, 4 tenían un buen riesgo crediticio . Supongamos que un candidato se divide de tal manera que los registros con un ahorro bajo 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, se debe 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 el árbol esté completo.

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 dará como resultado un tiempo de decisión más consistente. Sin embargo, sacrifica cierta prioridad para crear árboles hijos puros, lo que puede generar 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:

• Fácil 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. ^[29]
• Capaz de manejar tanto datos numéricos como categóricos ^{. [29]} 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 utilizar solo con variables nominales, mientras que las redes neuronales se pueden utilizar solo 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 C4.5, no tienen esta limitación. ^[3]
• 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 hay necesidad de crear variables ficticias . ^[29]
• Utiliza un modelo de caja blanca o 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, lo que 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, no hace suposiciones de distribución, independencia o 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. ^[30]
• Refleja la toma de decisiones humanas más de cerca que otros enfoques. ^[29] Esto podría ser útil al modelar decisiones y comportamientos humanos.
• Robusto frente a la colinealidad, especialmente frente al boosting.
• Selección de características incorporada . Las características irrelevantes adicionales se utilizarán menos, por lo que se pueden eliminar en ejecuciones posteriores. La jerarquía de atributos en un árbol de decisiones refleja la importancia de los atributos. ^[31] Esto significa que las características en la parte superior son las más informativas. ^[32]
• Los árboles de decisión pueden aproximarse a cualquier función booleana, por ejemplo, XOR . ^[33]

Limitaciones

• Los árboles pueden ser muy poco robustos. Un pequeño cambio en los datos de entrenamiento puede dar como resultado un gran cambio en el árbol y, en consecuencia, en las predicciones finales. ^[29]
• Se sabe que el problema de aprender un árbol de decisión óptimo es NP-completo bajo varios aspectos de optimalidad e incluso para conceptos simples. ^{[34] [35]} En consecuencia, los algoritmos prácticos de aprendizaje de árboles de decisión se basan en heurísticas como el algoritmo voraz donde se toman decisiones óptimas a nivel local en cada nodo. Dichos algoritmos no pueden garantizar que se devuelva el árbol de decisión óptimo a nivel global. Para reducir el efecto voraz de la optimalidad local, se propusieron algunos métodos como el árbol de distancia de información dual (DID). ^[36]
• 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 ^[37] ) . Se necesitan mecanismos como la poda para evitar este problema (con la excepción de algunos algoritmos como el enfoque de inferencia condicional, que no requiere poda). ^{[21] [22]}
• No se garantiza que la profundidad promedio del árbol, definida por el número de nodos o pruebas hasta la clasificación, sea mínima o pequeña según diversos criterios de división. ^[38]
• En el caso de datos que incluyen variables categóricas con diferentes cantidades de niveles, la ganancia de información en los árboles de decisión está sesgada a favor de los atributos con más niveles. ^[39] Para contrarrestar este problema, en lugar de elegir el atributo con la mayor ganancia de información , se puede elegir el atributo con la mayor relación de ganancia de información entre los atributos cuya ganancia de información es mayor que la ganancia de información media. ^[40] Esto sesga el árbol de decisión en contra de considerar atributos con una gran cantidad de valores distintos, mientras que no da una ventaja injusta a los atributos con una ganancia de información muy baja. Alternativamente, el problema de la selección sesgada de predictores se puede evitar mediante el enfoque de inferencia condicional, ^[21] un enfoque de dos etapas, ^[41] o la selección de características adaptativa de dejar uno fuera. ^[42]

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

Algunos ejemplos de código abierto incluyen:

• ALGLIB , una biblioteca de análisis numérico en 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 código abierto para la visualización de datos, el aprendizaje automático y la minería de datos (bosque aleatorio)
• R (un entorno de software de código abierto para computación estadística, que incluye varias implementaciones de 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 destacado:

• MATLAB ,
• Microsoft SQL Server y
• Minero rapido ,
• Minero empresarial SAS
• Modelador IBM SPSS ,

Extensiones

Gráficos de decisión

En un árbol de decisión, todos los caminos desde el nodo raíz hasta el nodo hoja proceden por medio de conjunción, o AND . En un gráfico de decisión, es posible utilizar disyunciones (OR) para unir dos caminos más utilizando la longitud mínima del mensaje (MML). ^[43] Los gráficos de decisión se han ampliado aún más para permitir que se aprendan de forma dinámica nuevos atributos no establecidos previamente y se utilicen en diferentes lugares dentro del gráfico. ^[44] 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 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 . ^{[45] [46]}

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

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

Véase también

• Poda de árboles de decisión
• Diagrama de decisión binaria
• CHAÍN
• CARRO
• Algoritmo ID3
• Algoritmo C4.5
• Troncos 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
• Agrupamiento jerárquico

Referencias

1. Studer, Matthias; Ritschard, Gilbert; Gabadinho, Alexis; Müller, Nicolas S. (2011). "Análisis de discrepancias de secuencias de estados". Métodos sociológicos e investigación . 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". Conocimiento y sistemas de información . 14 (1): 1–37. doi :10.1007/s10115-007-0114-2. hdl : 10983/15329 . ISSN  0219-3116. S2CID  2367747.
3. Rokach, Lior; Maimon, 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.S2CID44697571  .​
4. Shalev-Shwartz, Shai; Ben-David, Shai (2014). "18. Árboles de decisión". Comprender el aprendizaje automático. Cambridge University Press.
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.; Maimon, O. (2005). "Inducción descendente de clasificadores de árboles de decisión: un estudio". IEEE Transactions on Systems, Man, and Cybernetics - Part C: Applications and Reviews . 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; Stone, 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 de gradiente estocástico Archivado el 28 de noviembre de 2018 en Wayback Machine . Universidad de 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. Heath, D., Kasif, S. y Salzberg, S. (1993). k-DT: Un método de aprendizaje de múltiples árboles. En Actas del Segundo Taller Internacional sobre Aprendizaje Multiestrategia , págs. 138-149.
11. Heath, D., Kasif, S. y Salzberg, SL (1996). Comités de árboles de decisión. En B. Gorayska y J. Mey (Eds.), Cognitive Technology: In Search of a Humane Interface (págs. 305-317). Ámsterdam: Elsevier Science BV
12. Breiman, L. (1996). "Predictores de ensacado". Aprendizaje automático . 24 (2): 123–140. doi : 10.1007/BF00058655 .
13. Rodríguez, JJ; Kuncheva, LI ; Alonso, CJ (2006). "Bosque de rotación: un nuevo método de conjunto de clasificadores". IEEE Transactions on Pattern Analysis and Machine Intelligence . 28 (10): 1619–1630. CiteSeerX 10.1.1.156.8277 . doi :10.1109/TPAMI.2006.211. PMID  16986543. S2CID  6847493. 
14. 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.
15. 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.
16. Wang, Fulton; Rudin, Cynthia (2015). "Falling Rule Lists" (PDF) . Journal of Machine Learning Research . 38 . Archivado desde el original (PDF) el 28 de enero de 2016 . Consultado el 22 de enero de 2016 .
17. Murthy, SK (1994). "Un sistema para la inducción de árboles de decisión oblicuos". Revista de investigación en inteligencia artificial . 2 (1): 1–32. doi : 10.1613/jair.63 .
18. Kass, GV (1980). "Una técnica exploratoria para investigar grandes cantidades de datos categóricos". Applied Statistics . 29 (2): 119–127. doi :10.2307/2986296. JSTOR  2986296.
19. Biggs, David; De Ville, Barry; Suen, Ed (1991). "Un método para elegir particiones multidireccionales para árboles de clasificación y decisión". Journal of Applied Statistics . 18 (1): 49–62. Bibcode :1991JApSt..18...49B. doi :10.1080/02664769100000005. ISSN  0266-4763.
20. Ritschard, G. (2013), " CHAID y métodos de árboles supervisados ​​anteriores", en JJ McArdle y G. Ritschard (eds), Problemas contemporáneos en la minería de datos exploratoria en las ciencias del comportamiento , Serie de metodología cuantitativa, Nueva York: Routledge, páginas 48-74. Preimpresión
21. 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. 
22. Strobl, C.; Malley, J.; Tutz, G. (2009). "Introducción al particionamiento recursivo: fundamento, aplicación y características de los árboles de clasificación y regresión, bagging y bosques aleatorios". Métodos psicológicos . 14 (4): 323–348. doi :10.1037/a0016973. PMC 2927982 . PMID  19968396. 
23. Janikow, CZ (1998). "Árboles de decisión difusos: problemas y métodos". IEEE Transactions on Systems, Man, and Cybernetics - Part B: Cybernetics . 28 (1): 1–14. doi :10.1109/3477.658573. PMID  18255917.
24. 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.
25. Najmann, Oliver (1992). Técnicas y heurísticas para la adquisición de conocimiento simbólico a partir de ejemplos (Tesis). Tesis doctoral.
26. "Crecimiento de árboles de decisión". MathWorks .
27. Witten, Ian; Frank, Eibe; Hall, Mark (2011). Minería de datos . Burlington, MA: Morgan Kaufmann. págs. 102–103. ISBN 978-0-12-374856-0.
28. Larose, Daniel T.; Larose, Chantal D. (2014). Descubrimiento de conocimiento en los datos: una introducción a la minería de datos . Hoboken, NJ: John Wiley & Sons, Inc. ISBN 9781118874059.
29. Gareth, James; Witten, Daniela; Hastie, Trevor; Tibshirani, Robert (2015). Introducción al aprendizaje estadístico . Nueva York: Springer. pp. 315. ISBN. 978-1-4614-7137-0.
30. 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. 
31. Provost, Foster, 1964- (2013). Ciencia de datos para empresas: [lo que necesita saber sobre minería de datos y 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)
32. Piryonesi S. Madeh; El-Diraby Tamer E. (1 de junio de 2020). "El papel del análisis de datos en la gestión de activos de infraestructura: cómo superar los problemas de tamaño y calidad de los datos". Journal of Transportation Engineering, Parte B: Pavements . 146 (2): 04020022. doi :10.1061/JPEODX.0000175. S2CID  216485629.
33. Mehtaa, Dinesh; Raghavan, Vijay (2002). "Aproximaciones de funciones booleanas mediante árboles de decisión". Ciencias de la Computación Teórica . 270 (1–2): 609–623. doi : 10.1016/S0304-3975(01)00011-1 .
34. Hyafil, Laurent; Rivest, RL (1976). "La construcción de árboles de decisión binarios óptimos es NP-completo". Information Processing Letters . 5 (1): 15–17. doi :10.1016/0020-0190(76)90095-8.
35. Murthy S. (1998). "Construcción automática de árboles de decisión a partir de datos: un estudio multidisciplinario". Minería de datos y descubrimiento de conocimiento
36. Ben-Gal I. Dana A., Shkolnik N. y Singer (2014). "Construcción eficiente de árboles de decisión mediante el método de la distancia de información dual" (PDF) . Quality Technology & Quantitative Management . 11 (1): 133–147. doi :10.1080/16843703.2014.11673330. S2CID  7025979. Archivado desde el original (PDF) el 2016-06-04 . Consultado el 2014-02-13 .
37. Principios de minería de datos . 2007. doi :10.1007/978-1-84628-766-4. ISBN 978-1-84628-765-7.S2CID 45746  .
38. 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) . Applied Stochastic Models in Business and Industry, vol. 31(1) 64-78. Archivado desde el original (PDF) el 2021-02-05 . Consultado el 2021-01-30 .{{cite web}}: CS1 maint: numeric names: authors list (link)
39. 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.
40. Quinlan, J. Ross (1986). "Inducción de árboles de decisión". Aprendizaje automático . 1 (1): 81–106. doi : 10.1007/BF00116251 .
41. Brandmaier, Andreas M.; Oertzen, Timo von; McArdle, John J.; Lindenberger, Ulman (2012). "Árboles de modelos 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. 
42. Painsky, Amichai; Rosset, Saharon (2017). "La selección de variables con validación cruzada en métodos basados ​​en árboles mejora el rendimiento predictivo". IEEE Transactions on Pattern Analysis and Machine Intelligence . 39 (11): 2142–2153. arXiv : 1512.03444 . doi :10.1109/TPAMI.2016.2636831. PMID  28114007. S2CID  5381516.
43. "CiteSeerX".
44. Tan y Dowe (2003)
45. Papagelis, A.; Kalles, D. (2001). "Breeding Decision Trees Using Evolutionary Techniques" (PDF) . Actas de la Decimoctava Conferencia Internacional sobre Aprendizaje Automático, 28 de junio–1 de julio de 2001. págs. 393–400.
46. Barros, Rodrigo C.; Basgalupp, MP; Carvalho, ACPLF; Freitas, Alex A. (2012). "Un estudio de algoritmos evolutivos para la inducción de árboles de decisión". IEEE Transactions on Systems, Man, and Cybernetics . Parte C: Aplicaciones y revisiones. 42 (3): 291–312. CiteSeerX 10.1.1.308.9068 . doi :10.1109/TSMCC.2011.2157494. S2CID  365692. 
47. Chipman, Hugh A.; George, Edward I.; McCulloch, Robert E. (1998). "Búsqueda de modelos CART bayesianos". 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. 
48. 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  .

Lectura adicional

• James, Gareth; Witten, Daniela; Hastie, Trevor; Tibshirani, Robert (2017). "Métodos basados ​​en árboles" (PDF) . Introducción al aprendizaje estadístico: con aplicaciones en R. Nueva York: Springer. pp. 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