Tema 09 - Métodos basados en árboles

Pedro Albarrán

Dpto. de Fundamentos del Análisis Económico. Universidad de Alicante

Estratificación para asociaciones no lineales

  • Ejemplo: relación no lineal entre las ventas y la edad

  • Cuantos más particiones, mejor ajuste.

  • PERO ¿dónde dividimos?, ¿cuántas particiones?

  • Esta cuestión también aplica a las interacciones entre variables para capturar heterogeneidad del efecto de una variable: ¿cuántas interacciones? ¿con cuántos intervalos?

Árboles de decisión

  • Un árbol de decisión es un diagrama de flujo con reglas para segmentar el espacio de regresores en regiones más simples y clasificar observaciones

Árboles de Regresión

  • ¿Cómo construimos estos árboles para una variable cuantitativa?

    1. Dividir el espacio de predicción, \(\small x_1, x_2, \dots, x_p\) en regiones \(\small J\) distintas y no superpuestas, \(\small R_1, R_2, \dots, R_J\)

      • cada vez más homogéneas o “puras”: como todos los modelos, mismas características, mismo valor esperado de \(y\)

    2. Cada observación que caiga en la región \(\small R_j\) tiene el mismo valor predicho: la media de \(\small y\) para las observaciones de entrenamiento en \(\small R_j\), \(\small \widehat{y}_{i\in R_j}= \bar{y}_{R_j}\)

  • Es INVIABLE considerar todas las particiones en \(\small J\) regiones

  • Alternativas heurísticas: un algoritmo “voraz” elige una opción localmente óptima en cada paso con la esperanza de llegar a una solución general óptima

    • (en lugar de elegir la mejor partición para un paso futuro)

Partición binaria recursiva

  1. En la parte alta, todas las observaciones pertenecen a una sola región

  2. Se divide sucesivamente cada región en dos ramas: \(\small R_1(j,s) = \{X|X_j < s\}\) y \(\small R_2(j,s) = \{X|X_j \geq s\}\)

    • En cada nodo, se consideran todos los regresores \(\small X_j\) y todos los umbrales \(s\)

    • Se calcula el error de predicción por particionar de esa manera \(\small SCR_{j,s} = \sum_{i\in R_1(j,s)}(y_i-\widehat{y}_{R_1})^2 + \sum_{i\in R_2(j,s)}(y_i-\widehat{y}_{R_2})^2\)

    • SOLO una partición en cada iteración: se elige \(\small j\) y \(\small s\) con menor \(\small SCR_{j,s}\)

  3. Repetimos el proceso particionando cada región de la iteración anterior

  4. Se continua hasta que se cumpla un criterio de parada; p.e., ninguna región contiene más de \(5\) observaciones

Podar un árbol (pruning)

  • Evitar árboles demasiados complejos (“overfitting”)

  • Hacer crecer un árbol “grande” con \(\small T_0\) nodos terminales y podarlo para quedarnos con un sub-árbol con \(\small T\) nodos terminales \[ \small min \sum_{m=1}^T \sum_{i \in R_m} (y_i-\widehat{y}_{R_m})^2 + \alpha |T| \] donde \(\small R_m\) es la región de \(\small m\)-nodo terminal

  • \(\small \alpha\) es el hiperparámetro de coste de complejidad de la poda, elegido por validación cruzada

  • Disyuntiva entre más o menos nodos finales: mejor ajuste (menor SCR) frente a mayor penalización por complejidad

Árboles de clasificación

  • Para un árbol de clasificación, se predice que cada observación pertenece a la clase más común en la región a la que pertenece en entrenamiento

  • También se pueden obtener la proporción de una clase \(\small k\) dentro de una región particular \(\small m\) de nodos terminales: \(\small \widehat{p}_{mk}\)

  • La métrica usada para hacer crecer los árboles NO puede ser SCR

  1. Índice de Gini: medida de la varianza entre clases \(\small G=\sum_{k=1}^{K}\widehat{p}_{mk}(1-\widehat{p}_{mk})\)

  2. Entropía (cruzada) \(\small D=\sum_{k=1}^{K}\widehat{p}_{mk}log(\widehat{p}_{mk})\)

  • Ambos son medidas de “pureza” del nodo: un valor pequeño indica que la región contiene en su mayoría observaciones de una sola clase.

Algoritmos para árboles e hiperparámetros

  • Motores para árboles: rpart (defecto), spark y C5.0 (solo clasificación)

  • Depende de varios hiperparámetros elegidos por tuning

    • min_n: mínimo número de observaciones en un nodo parar dividirse más

    • tree_depth: máx. número de niveles de profundidad del árbol (no C5.0)

    • cost_complexity: coste de complejidad (sólo rpart)

modelo_arbol  <- decision_tree(mode = "classification", 
                               engine = "rpart", 
                               cost_complexity = .01)
  • Podemos visualizar un modelo árbol estimado con la biblioteca rpart.plot
library(rpart.plot)
arbol <- flujo_arbol_est %>% extract_fit_parsnip() 
rpart.plot(arbol$fit)

Comentarios

  • Predicción: media o clase mayoritaria de las observaciones de entrenamiento en el nodo terminal que corresponde a una observación nueva

  • Importancia de las variables: la biblioteca vip proporciona métricas sobre la influencia de cada predictor en las predicciones del modelo

    • algunas son específicas de un modelo: en árboles, la reducción total de la SCR o Gini debida a las particiones que usan una variable

    • otras generales: basadas en permutaciones, o en medidas de Shapley

  • Ventajas de los árboles de decisión:
    • ajusta (no paramétricamente) relaciones no lineales/complejas
    • no requieren dummies ni transformaciones no lineales
    • fáciles de explicar y visualizar
  • Desventajas: overfit (no robustos a cambios en los datos) y bajo poder de predicción

Bagging

  • Agregación de Bootstrap (bagging): procedimiento general para reducir la varianza, promediando \(\small \{x_i\}_{i=1}^n iid \sim (\mu, \sigma^2) \Rightarrow \bar{x} \sim (\mu, \sigma^2/n)\)

  • Podemos tomar \(B\) re-muestras del único conjunto de entrenamiento

  • En lugar de un único árbol complejo, se combinan muchos árboles diversos que pueden reflejar patrones sutiles

  • La variación muestral en las condiciones de “entrenamiento” se genera mediante “bootstrap”

“Random forest”

  • Es un algoritmo específico de agregación de árboles que introduce aleatorización para eliminar correlación entre los árboles.

    • Se construyen varios árboles en muestras de entrenamiento de bootstrap

    • En cada partición de un árbol, se seleccionan aleatoriamente \(\small m \approx \sqrt{k}\quad\) regresores del total

    • Se mitiga la influencia de regresores fuertes, permitiendo una mayor diversidad en los árboles agregados

  • Mejor predicción a costa de la interpretación \(\Longrightarrow\) métodos de interpretabilidad ex-post para aprendizaje automático: importancia, Shapley values, partial dependence plots (PDP)

    • La importancia se puede calcular como una media en los distintos árboles.

  • De manera similar a los p-valores o LASSO, la importacia destaca qué variables considerar en modelos más interpretables, como regresión o árboles

Algoritmos para RF e hiperparámetros

  • Motores principales para RF en R: ranger, randomForest y spark

  • Depende de trees, números de árboles, a considerar en la agregación (no genera “overfitting”) y de dos hiperparámetros

    • mtry: número de variables a considerar en cada partición

    • min_n: igual que en árboles

library(ranger)
modelo_RF  <- rand_forest(mode = "regression", trees = 100,
                          mtry = 3, min_n = 5) %>% 
              set_engine("ranger", importance = "permutation")
              # importance = "impurity" en clasificación

RF <- flujo_RF_est %>% extract_fit_parsnip()
library(vip)
RF %>% vi()
RF %>% vip()