Aprendizaje del árbol de decisiones

(Extraido de: [1] "Python Machine Learning - Capitulo 3")

Los clasificadores de árboles de decisión son modelos atractivos si nos preocupamos por la interpretación. Se puede pensar en este modelo como un desglose de nuestros datos al tomar decisiones basadas en hacer una serie de preguntas.

Consideremos el siguiente ejemplo donde usamos un árbol de decisiones para decidir sobre una actividad en un día en particular:

El modelo de árbol de decisión aprende una serie de preguntas para inferir las etiquetas de clase de las muestras. Aunque la figura anterior ilustró el concepto de un árbol de decisiones basado en variables categóricas, el mismo concepto se aplica si nuestras características.

Esto también funciona si nuestras características son números reales como en el conjunto de datos de Lirios. Por ejemplo, definir un valor de corte a lo largo del eje de la característica del ancho del sépalo y hacer una pregunta binaria.

"¿ancho del sépalo ≥ 2.8 cm?"

Usando el algoritmo de decisión, comenzamos en la raíz del árbol y dividimos los datos en la característica que da como resultado la mayor ganancia de información (IG). En un proceso iterativo, podemos repetir este procedimiento de división en cada nodo hijo hasta que las hojas sean puras. Esto significa que todas las muestras de cada nodo pertenecen a la misma clase.

En la práctica puede resultar en un árbol muy profundo con muchos nodos esto puede conducir a un sobreajuste. Por lo tanto, queremos podar el árbol estableciendo un límite para la profundidad máxima del árbol.

Maximizar la obtención de información: obtener el máximo retorno de la inversión

Para dividir los nodos en las características más informativas, es necesario definir una función objetivo que queremos optimizar a través del algoritmo de aprendizaje de árboles. Aquí, nuestra función objetivo es maximizar la ganancia de información en cada división, que definimos de la siguiente manera: 

$IG(D_P,f)=I(D_P)-\sum_{j=1}^{m}\frac{N_j}{N_P }I(D_j)$

• $f$ es la característica para realizar la división
• $D_P$ y $D_j$ son el conjunto de datos del nodo padre y $j$ hijo.
• $I$ es nuestra medida de impureza. 
• $N_P$ es el número total de muestras en el nodo padre.
• $N_j$ es el número de muestras en el j-ésimo nodo hijo.

La ganancia de información es la diferencia entre la impureza del nodo principal y la suma de las impurezas del nodo secundario: cuanto menor es la impureza de los nodos secundarios, mayor es la ganancia de información. Por simplicidad y para reducir el espacio de búsqueda combinatoria, la mayoría de las bibliotecas (incluido scikit-learn) implementan árboles de decisión binarios. Esto significa que cada nodo principal se divide en dos nodos secundarios, $D_{izq}$ y $D_{der}$:

$IG(D_P,a)=I(D_P)-\frac{N_{izq}}{N_{der}}I(D_{izq})-\frac{N_{der}}{N_p}I(D_{der})$

Las tres medidas de impurezas o criterios de división que se usan comúnmente en los árboles de decisión binarios son el índice de Gini $(I_G)$, la entropía $(I_H)$ y el error de clasificación $(I_E)$. Comencemos con la definición de entropía para todas las clases no vacías $(𝑝(𝑖|𝑡) ≠ 0)$:

$I_H(t)=-\sum_{i=1}^{c}p(i|t)\log_2p(i|t)$

• $𝑝(𝑖|𝑡)$ es la proporción de muestras que pertenece a la clase $𝑐$ para un nodo $𝑡$ en particular.

La entropía es $0$ si todas las muestras de un nodo pertenecen a la misma clase, y la entropía es máxima si tenemos una distribución de clases uniforme. Por ejemplo, en una configuración de clase binaria:

• La entropía es $0$ si $𝑝(𝑖 = 1|𝑡) = 0$ o. $𝑝(𝑖 = 0|𝑡) = 0$.
• Si las clases se distribuyen uniformemente con $𝑝(𝑖 = 1|𝑡) = 0.5$ y $𝑝(𝑖 = 0|𝑡) = 0.5$, la entropía es $1$.
• Podemos decir que el criterio de entropía intenta maximizar la información mutua en el árbol.

El índice de Gini se puede entender como un criterio para minimizar la probabilidad de clasificación errónea:

$I_G(t)=\sum_{i=1}^{c}p(i|t)(-p(i|t))=1-\sum_{i=1}^{c}p(i|t)^2$

Similar a la entropía, el índice de Gini es máximo si las clases están perfectamente mezcladas, por ejemplo, en una configuración de clase binaria (𝑐 = 2):

$1-\sum_{i=1}^{c}0.5^2=0.5$

En la práctica, tanto el índice de Gini como la entropía suelen producir resultados muy similares y no vale la pena dedicar mucho tiempo a evaluar árboles utilizando diferentes criterios de impureza en lugar de experimentar con diferentes cortes de poda. 

Otra medida de impurezas es el error de clasificación:

$I_E=1-\max{p(i|t)}$

Este es un criterio útil para la poda, pero no se recomienda para hacer crecer un árbol de decisión, ya que es menos sensible a los cambios en las probabilidades de clase de los nodos. Se puede ilustrar esto observando ambos posibles escenarios de división:

Comenzamos con un conjunto de datos $D_P$ en el nodo principal $D_P$ que consta de 40 muestras de la clase 1 y 40 muestras de la clase 2 que dividimos en dos conjuntos de datos $D_{izq}$ y $D_{der}$, respectivamente. La ganancia de información usando el error de clasificación como criterio de división sería la misma $(IG_E= 0.25)$ en ambos escenarios $A$ y $B$:

Sin embargo, el índice de Gini favorecería la división en el escenario $𝐵(𝐼𝐺_𝐺 = 0.1\bar{6})$sobre el escenario $𝐴(𝐼𝐺_𝐺 = 0.125)$, que de hecho es más puro:

De manera similar, el criterio de entropía favorecería el escenario $𝐵(𝐼𝐺_𝐻 = 0.19)$ sobre el escenario $𝐴(𝐼𝐺_𝐻 = 0.31)$:

Trazando los índices de impureza para el rango de probabilidad $[0,1]$ para la clase 1. Tenga en cuenta que también agregaremos una versión escalada de la entropía (entropía/2) observar que el índice de Gini es una medida intermedia entre la entropía y el error de clasificación. El código es el siguiente:

Construyendo un árbol de decisiones

Los árboles de decisión pueden crear límites de decisión complejos al dividir el espacio de características en rectángulos.

Con scikit-learn, ahora entrenaremos un árbol de decisión con una profundidad máxima de 3 usando la entropía como criterio de impureza. Aunque se puede desear el escalado de características para fines de visualización, el escalado de características no es un requisito para los algoritmos de árbol de decisión.

Los límites de decisión típicos de eje paralelo del árbol de decisión:

Una buena característica de scikit-learn es que nos permite exportar el árbol de decisiones como un archivo .𝑑𝑜𝑡 después del entrenamiento (GraphViz). Este programa está disponible gratuitamente en http://www.graphviz.org y es compatible con Linux, Windows y Mac OS X.

Primero es necesario crear el archivo .𝑑𝑜𝑡 a través de scikit-learn con la función 𝑒𝑥𝑝𝑜𝑟𝑡_𝑔𝑟𝑎𝑝ℎ𝑣𝑖𝑧 del submódulo del árbol.

Después de haber instalado GraphViz en nuestra computadora, podemos convertir el archivo 𝑡𝑟𝑒𝑒.𝑑𝑜𝑡 en un 𝑃𝑁𝐺 ejecutando el siguiente comando desde la línea de comandos en la ubicación donde guardamos el archivo.

Ahora es posible rastrear muy bien las divisiones que el árbol de decisiones determinó a partir de nuestro conjunto de datos de entrenamiento. Comenzamos con 105 muestras en la raíz y la dividimos en dos nodos hijos con 34 y 71 muestras cada uno usando el pétalo con un corte $≤ 0,75 cm$.

Después de la primera división, podemos ver que el nodo hijo izquierdo ya es puro y solo contiene muestras de la clase Iris-Setosa (entropía = 0). Las otras divisiones de la derecha se utilizan para separar las muestras de las clases Lirio-Versicolor e Lirio -Virginica.

Combinando estudiantes débiles a fuertes a través de bosques aleatorios

Los bosques aleatorios han ganado una gran popularidad debido a su buen rendimiento de clasificación, escalabilidad y facilidad de uso, se lo puede considerarse como un conjunto de árboles de decisión.

La idea detrás del aprendizaje en conjunto es combinar alumnos débiles para construir un modelo más robusto, un alumno fuerte, que tenga un mejor error de generalización y sea menos susceptible al sobreajuste. El algoritmo de bosque aleatorio se puede resumir en cuatro pasos simples:

1. Dibuje una muestra bootstrap aleatoria de tamaño $n$ (elija aleatoriamente n muestras del conjunto de entrenamiento con reemplazo).
2. Haga crecer un árbol de decisiones a partir de la muestra de arranque. En cada nodo:
1. Seleccione aleatoriamente funciones sin reemplazo.
2. Divida el nodo utilizando la función que proporcione la mejor división de acuerdo con la función objetivo, por ejemplo, maximizando la ganancia de información.
3. Repetir los pasos de $1$ a $2$ $𝑘$ veces.
4. Agregue la predicción por cada árbol para asignar la etiqueta de clase por mayoría de votos.

Hay una ligera modificación en el paso 2 cuando entrenamos los árboles de decisión individuales: en lugar de evaluar todas las características para determinar la mejor división en cada nodo, solo consideramos un subconjunto aleatorio de ellos.

Aunque los bosques aleatorios no ofrecen el mismo nivel de interpretabilidad que los árboles de decisión, una ventaja de ellos es que no hay necesidad de preocuparse tanto por elegir buenos valores de hiperparámetros. Por lo general, no es necesario podar el bosque aleatorio, ya que el modelo de conjunto es bastante robusto al ruido de los árboles de decisión individuales.

El único parámetro que debemos preocuparnos en la práctica es el número de árboles $𝑘$ que se elige para el bosque aleatorio, cuanto mayor sea el número de árboles, mejor será el rendimiento del clasificador de bosques aleatorio a expensas de un mayor costo computacional.

Otros hiperparámetros del clasificador de bosque aleatorio que se pueden optimizar, son:

$𝑛$ 

• Se controla la compensación de sesgo-varianza del bosque aleatorio.
• Al elegir un valor mayor para $n$, disminuimos la aleatoriedad y, por lo tanto, es más probable que el bosque se sobreajuste.
• Podemos reducir el grado de sobreajuste eligiendo valores más pequeños para $𝑛$ a expensas del rendimiento del modelo.
• El tamaño de la muestra de arranque se elige para que sea igual al número de muestras del conjunto de entrenamiento, implica una compensación de sesgo-varianza.

$𝑑$

• Para el número de características $𝑑$ en cada división, queremos elegir un valor que sea menor que el número total de características en el conjunto de entrenamiento.
• Un valor predeterminado razonable que se usa en scikit-learn y otras implementaciones es $𝑑=\sqrt{𝑚}$, donde $𝑚$ es el número de características en el conjunto de entrenamiento.

Convenientemente, no tenemos que construir nosotros mismos el clasificador de bosque aleatorio a partir de árboles de decisión individuales; ya existe una implementación en scikit-learn que podemos usar:

Usando el código anterior, entrenamos un bosque aleatorio de 10 árboles de decisión a través del parámetro 𝑛_𝑒𝑠𝑡𝑖𝑚𝑎𝑡𝑜𝑟𝑠 y usamos el criterio de entropía como medida de impureza para dividir los nodos.

Bibliografía:

[1]    Raschka, S. (2015). Python Machine Learning. Pensilvania : Packt Publishing