Aprendizaje mediante árboles de decisión

Se puede utilizar una métrica simple y eficaz para identificar en qué medida los verdaderos positivos superan a los falsos positivos (véase la matriz de confusión ). Esta métrica, denominada "Estimación de la corrección positiva", se define a continuación:

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

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

Incluye 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). Al sustituir estos números en la ecuación, podemos calcular la estimación:${\displaystyle E_{p}=TP-FP=8-2=6}$Esto significa que al usar la estimación en esta característica, obtendría una puntuación de 6.

Sin embargo, cabe destacar 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 mayor, esa característica se clasificaría mejor que la otra, ya que la estimación resultante al usar la ecuación daría un valor más alto. Esto podría generar imprecisiones al usar la métrica si algunas características tienen más muestras positivas que otras. Para contrarrestar esto, se podría usar 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 obtener la tasa real de verdaderos positivos (TPR). La diferencia entre estas métricas se muestra en el siguiente ejemplo:

En este ejemplo, la característica A tuvo una estimación de 6 y un TPR de aproximadamente 0,73, mientras que la característica B tuvo una estimación de 4 y un TPR de 0,75. Esto demuestra que, si bien 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. Dependiendo de la situación y del 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 al problema. Por otro lado, un usuario más experimentado probablemente preferiría utilizar el valor TPR para clasificar las características, ya que tiene en cuenta las proporciones de los datos y todas las muestras que deberían haberse clasificado como positivas.

La impureza de Gini , índice de diversidad de Gini ^{[ 26 ]} o índice de Gini-Simpson en la investigación de la biodiversidad, es utilizada por el algoritmo CART (árbol de clasificación y regresión) para árboles de clasificación. La impureza de Gini es la probabilidad de que un elemento elegido al azar de un conjunto sea etiquetado erróneamente si se etiquetara de forma aleatoria e independiente según la distribución de etiquetas en el conjunto. Alcanza su valor mínimo (cero) cuando todos los casos en el nodo pertenecen a una única categoría objetivo.

Para un conjunto de artículos con${\displaystyle J}$clases y frecuencias relativas${\displaystyle p_{i}}$,${\displaystyle i\in \{1,2,...,J\}}$, la probabilidad de elegir un artículo con etiqueta${\displaystyle i}$es${\displaystyle p_{i}}$y la probabilidad de clasificar erróneamente ese elemento es${\displaystyle \sum _{k\neq i}p_{k}=1-p_{i}}$. La impureza de Gini se calcula sumando los productos por pares de estas probabilidades para cada etiqueta de clase:

${\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.${\displaystyle q=2}$, que en física se asocia con la falta de información en sistemas cuánticos, disipativos, no extensivos y fuera de equilibrio. Para el límite${\displaystyle q\to 1}$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.

Utilizada 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 se indica 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}}$

dónde${\displaystyle p_{1},p_{2},\ldots }$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. ^{[ 27 ]}

$${\displaystyle \overbrace {IG(T,a)} ^{\text{ganancia de información}}=\overbrace {\mathrm {H} (T)} ^{\text{entropía (padre)}}-\overbrace {\mathrm {H} (T\mid a)} ^{\text{suma de entropías (hijos)}}}$$${\displaystyle =-\sum _{i=1}^{J}p_{i}\log _{2}p_{i}-\sum _{i=1}^{J}-\Pr(i\mid a)\log _{2}\Pr(i\mid a)}$

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

$${\displaystyle \overbrace {E_{A}(\operatorname {IG} (T,a))} ^{\text{ganancia de información esperada}}=\overbrace {I(T;A)} ^{{\text{información mutua entre }}T{\text{ y }}A}=\overbrace {\mathrm {H} (T)} ^{\text{entropía (padre)}}-\overbrace {\mathrm {H} (T\mid A)} ^{\text{suma ponderada de entropías (hijos)}}}$$${\displaystyle =-\sum _{i=1}^{J}p_{i}\log _{2}p_{i}-\sum _{a}p(a)\sum _{i=1}^{J}-\Pr(i\mid a)\log _{2}\Pr(i\mid a)}$

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 qué característica utilizar para la división en cada paso de la construcción del árbol. La simplicidad es fundamental, por lo que buscamos mantener nuestro árbol pequeño. Para ello, en cada paso debemos elegir la división que dé como resultado los nodos hijos más consistentes. Una medida de consistencia comúnmente utilizada se denomina información, la cual 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 ]}

Consideremos un conjunto de datos de ejemplo con cuatro atributos: pronóstico (soleado, nublado, lluvioso), temperatura (caluroso, templado, fresco), humedad (alta, normal) y viento (verdadero, falso), con una variable objetivo binaria (sí o no), play , y 14 puntos de datos. Para construir un árbol de decisión con estos datos, debemos comparar la ganancia de información de cada uno de los cuatro árboles, cada uno dividido según 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 hijos tengan datos consistentes, o hasta que la ganancia de información sea 0.

Para hallar 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íes y cinco noes.

${\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 hijos, 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 = verdadero 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 función de la característica 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 el árbol esté completo. Este ejemplo está adaptado del ejemplo que aparece en Witten et al. ^{[ 27 ].}

En la investigación sobre biodiversidad, la ganancia de información también se conoce como índice de Shannon .

Introducida en CART, ^{[ 7 ]} la reducción de 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 requeriría primero una discretización antes de su aplicación. 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}|}{|S|}}{\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}|}{|S|}}{\frac {1}{|S_{f}|^{2}}}\sum _{i\in S_{f}}\sum _{j\in S_{f}}{\frac {1}{2}}(y_{i}-y_{j})^{2}\right)}$

dónde${\displaystyle S}$,${\displaystyle S_{t}}$, y${\displaystyle S_{f}}$son, respectivamente, el conjunto de índices de muestra previos a la división, el conjunto de índices de muestra para los cuales la prueba de división es verdadera y el conjunto de índices de muestra para los cuales la prueba de división es falsa. Cada uno de los sumandos anteriores son, en efecto, estimaciones de varianza , aunque escritas de una forma que no hace referencia directa a la media.

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

Utilizada por CART en 1984, ^{[ 28 ]} 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 de igual tamaño. Este proceso se repite para cada nodo impuro hasta que el árbol esté completo. La función${\displaystyle \varphi (s\mid t)}$, dónde${\displaystyle s}$es un candidato dividido en el nodo${\displaystyle t}$, se define como se indica a continuación

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

dónde${\displaystyle t_{L}}$y${\displaystyle t_{R}}$son los hijos izquierdo y derecho del nodo${\displaystyle t}$usando división${\displaystyle s}$, respectivamente;${\displaystyle P_{L}}$y${\displaystyle P_{R}}$son las proporciones de registros en${\displaystyle t}$en${\displaystyle t_{L}}$y${\displaystyle t_{R}}$, respectivamente; y${\displaystyle P(j\mid t_{L})}$y${\displaystyle P(j\mid t_{R})}$son las proporciones de clase${\displaystyle j}$registros en${\displaystyle t_{L}}$y${\displaystyle t_{R}}$, respectivamente.

Consideremos 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. ^{[ 28 ]} Los datos completos se presentan en la tabla siguiente. Para comenzar un árbol de decisión, calcularemos el valor máximo de${\displaystyle \varphi (s\mid t)}$utilizando cada característica para encontrar cuál dividirá el nodo raíz. Este proceso continuará hasta que todos los hijos sean puros o todos${\displaystyle \varphi (s\mid t)}$Los valores están por debajo de un umbral establecido.

Para encontrar${\displaystyle \varphi (s\mid t)}$De los ahorros de características , necesitamos anotar la cantidad de cada valor. Los datos originales contenían tres bajos, tres medios y dos altos. De los bajos, uno tenía un buen riesgo crediticio, mientras que de los medios y altos, 4 tenían un buen riesgo crediticio . Supongamos una división candidata${\displaystyle s}$De tal manera que los registros con pocos ahorros se colocarán en la cuenta del hijo izquierdo y todos los demás registros se colocarán en la cuenta del hijo derecho.

${\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 "calidad" de todas las posibles divisiones del nodo raíz. La candidata 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 "calidad" busca crear un árbol más equilibrado, lo que se traduce en un tiempo de decisión más consistente. Sin embargo, esto implica sacrificar cierta prioridad para crear nodos hijos puros, lo que puede generar bifurcaciones adicionales que no se presentan con otras métricas.

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

• Fácil de entender e interpretar. Las personas pueden comprender los modelos de árboles de decisión tras una breve explicación. Los árboles también se pueden representar gráficamente de forma que resulten fáciles de interpretar para quienes no son expertos. ^{[ 29 ]}
• Capaz de manejar datos numéricos y 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 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 podían 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 suelen requerir la normalización de datos. Dado que los árboles pueden manejar predictores cualitativos, no es necesario 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 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. Esto permite determinar la fiabilidad del modelo.
• Enfoque no paramétrico que no hace suposiciones sobre los datos de entrenamiento o los residuos de predicción; por ejemplo, no hace suposiciones sobre la distribución, la independencia o la 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 en el ámbito de la salud con mayor precisión. ^{[ 30 ]}
• Refleja la toma de decisiones humanas con mayor precisión que otros enfoques. ^{[ 29 ]} Esto podría ser útil al modelar decisiones/comportamiento humanos.
• Resistente frente a la colinealidad, en particular al boosting.
• Selección de características integrada . Las características irrelevantes adicionales se usará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. ^{[ 31 ]} Esto significa que las características superiores son las más informativas. ^{[ 32 ]}
• Los árboles de decisión pueden aproximar cualquier función booleana, por ejemplo, XOR . ^{[ 33 ]}

• 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, por consiguiente, 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 locales en cada nodo. Dichos algoritmos no pueden garantizar que se obtenga el árbol de decisión óptimo 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 algoritmos de aprendizaje basados ​​en árboles de decisión pueden crear árboles excesivamente complejos que no 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 ]}
• La profundidad promedio del árbol, definida por el número de nodos o pruebas hasta la clasificación, no está garantizada para ser mínima o pequeña bajo diversos criterios de división. ^{[ 38 ]}
• Para 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. ^{[ 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 razó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 un gran número de valores distintos, sin dar una ventaja injusta a los atributos con una ganancia de información muy baja. Alternativamente, el problema de la selección sesgada de predictores puede evitarse mediante el enfoque de inferencia condicional, ^{[ 21 ]} un enfoque de dos etapas, ^{[ 41 ]} o la selección adaptativa de características de dejar uno fuera. ^{[ 42 ]}

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

Algunos ejemplos de código abierto son:

• 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 gratuita y de código abierto para análisis, generación de informes e integración de datos (árboles de decisión, bosques aleatorios).
• Orange , un conjunto de herramientas de código abierto para visualización de datos, aprendizaje automático y 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 (un conjunto de herramientas de minería de datos gratuito y de código abierto, que contiene muchos algoritmos de árboles de decisión),

Software comercial destacado:

• MATLAB
• Servidor Microsoft SQL
• RapidMiner
• Minero empresarial SAS
• Modelador IBM SPSS

En un árbol de decisión, todos los caminos desde el nodo raíz hasta el nodo hoja proceden mediante conjunción, o AND . En un grafo de decisión, es posible usar disyunciones (OR) para unir dos o más caminos usando la longitud mínima del mensaje (MML). ^{[ 43 ]} Los grafos de decisión se han extendido aún más para permitir que nuevos atributos no declarados previamente se aprendan dinámicamente y se usen en diferentes lugares dentro del grafo. ^{[ 44 ]} El esquema de codificación más general da como resultado una mejor precisión predictiva y puntuación probabilística de pérdida logarítmica. En general, los grafos de decisión infieren modelos con menos hojas que los árboles de decisión.

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

También es posible muestrear un árbol usando 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 ]}