Capítulo 9 Arboles de decision

Los métodos basados en árboles para regresión y clasificación estratifican o segmentan el espacio predictor en varias regiones. Para hacer una predicción de una observación dada normalmente utiliza el valor de respuesta promedio de las observaciones de la base de entrenamiento en la región a la que pertenece. En el caso de clasificación se asigna a la categoría mayoritaria dentro del nodo terminal.

9.1 Classification and Regression Tree (CART)

En el caso de árboles de regresión, si $Y$ es la respuesta y $X_1$ y $X_2$ los inputs se parte el espacio $(X_1, X_2)$ en dos regiones, en base a una sola variable (partición horizontal o vertical). Dentro de cada región proponemos como predicción la media muestral de $Y$.

Se busca elegir la variable y el punto de partición de manera óptima (mejor ajuste global). Es computacionalmente inviable considerar cada posible partición del espacio de atributos en $J$ regiones. Por lo tanto, toma un enfoque top-down greedy que se conoce como división binaria recursiva. El enfoque es top-down porque comienza en la parte superior del árbol (en cuyo punto todas las observaciones pertenecen a una sola región) y luego divide sucesivamente el espacio predictor; cada división se indica a través de dos nuevas ramas más abajo en el árbol. Es greedy porque en cada paso del proceso de construcción del árbol, la mejor división se hace en ese paso en particular, en lugar de mirar hacia adelante y elegir una división que conducirá a un mejor árbol en algún paso futuro.

El panel izquierdo de la Figura 9.1 muestra un árbol de regresión para predecir el logaritmo del salario (en miles de dólares) de un jugador de béisbol, basado en la cantidad de años que ha jugado en las ligas mayores y la cantidad de hits que hizo en el año anterior. En un nodo interno dado, la etiqueta (de la forma $X_j < t_k$) indica la rama izquierda que sale de esa división, y la rama de la derecha corresponde a $X_j \ge t_k$. Por ejemplo, la división en la parte superior del árbol da como resultado dos ramas grandes. La rama izquierda corresponde a Years < 4,5, y la rama derecha corresponde a Years >= 4,5.²⁰ El árbol tiene dos nodos internos y tres nodos terminales u hojas. El número en cada hoja es la media de la variable de respuesta de las observaciones que caen allí. Por ejemplo, la predicción para el nodo terminal de la izquierda es $e^{5,107} \times 1.000 = \$165.174$. El panel derecho la Figura 9.1 muestra las regiones en función de Years y Hits.

Figura 9.1: Arbol de regresión

Notar:

Cada región tiene su propio modelo.
Ciertas variables importan en determinadas regiones y no en otras (Hits).

Dado $Y$ y $X$ un vector de $p$ variables con $n$ observaciones el algoritmo busca determinar cuál variable usar para la partición y que punto de esa variable usar para la partición. Si $j$ es la variable de partición y el punto de partición es $s$, se definen los siguientes semiplanos:

\[\begin{align*} R_1(j,s) = & {X \mid X_j < s} \\ R_2(j,s) = & {X \mid X_j \ge s} \end{align*}\]

Se trata de buscar la variable de partición $X_j$ y el punto de partición $s$ que resuelvan (minimizar el $EMC$ en cada región):

\[\begin{equation} \tag{9.1} \sum_{i: x_i \in R_1(j,s)} (y_i - \hat{y}_{R_1})^2 + \sum_{i: x_i \in R_2(j,s)} (y_i - \hat{y}_{R_2})^2 \end{equation}\]

Donde $\hat{y}_{R_1}$ y $\hat{y}_{R_2}$ es el promedio de la respuesta en las regiones $1$ y $2$, respectivamente. Para cada variable y punto de partición, la minimización interna se corresponde con la media dentro de cada región.²¹

¿Cuándo parar de realizar divisiones?

Un árbol demasiado extenso sobreajusta (overfit) los datos. Pero dado que el proceso es secuencial y cada corte no mira lo que puede suceder después, si se detiene el proceso demasiado pronto se puede perder un “gran” corte más abajo. Prunning: ajustar un árbol grande y luego podarlo (prune) usando un criterio de cost-complexity.

Classification tree

Un árbol de clasificación es muy similar a un árbol de regresión, excepto que se utiliza para predecir una respuesta cualitativa en lugar de una cuantitativa. Recordar que para un árbol de regresión, la respuesta predicha para una observación esta dada por la respuesta media de las observaciones de entrenamiento que pertenecen al mismo nodo terminal. En contraste, para un árbol de clasificación, predice que cada observación pertenece a la clase que ocurre más comúnmente en las observaciones de entrenamiento en la región a la que pertenece. Se basa en el error de clasificación o índice de Gini (pureza), análogo a $EMC$ en un árbol de regresión.

9.2 Bagging

Ventajas y desventajas de $CART$:

Forma inteligente de representar no linealidades.
Arriba quedan las variables más relevantes entonces es fácil de comunicar. Reproduce proceso decisorio humano.
Si la estructura es lineal, $CART$ no anda bien.
Poco robusto, variaciones en los datos modifican el resultado.

Un método de ensemble es un enfoque que combina muchos modelos simples en uno único y potencialmente muy poderoso. Los modelos simples se conocen como modelos de aprendizaje débil, ya que por sí mismos pueden generar predicciones mediocres.

Una posible solución es el bootstrap aggregation que consiste en tomar como predicción el promedio de las predicciones bootstrap.²²

\[\begin{equation} \tag{9.2} \hat{f}_{bag} = \frac{1}{B} \sum_{b=1}^{B} \hat{f}^{*b}(x) \end{equation}\]

Esta idea se basa en que la varianza del promedio es menor que la de una predicción sola. Bajo independencia si $V(x) = \sigma^2$ entonces $V(\overline{x}) = \frac{\sigma^2}{n}$. Pero existe el problema que si hay un predictor fuerte (siempre va a ser seleccionado primero), los distintos árboles son muy similares entre sí por lo que habrá alta correlación.

9.3 Random Forest

Busca bajar la correlación entre los árboles del bootstrap. Al igual que en bagging, construye una serie de árboles de decisión en muestras de entrenamiento bootstrap. Pero al construir estos árboles de decisión, cada vez que se considera una división en un árbol, se elige como candidatos de división una muestra aleatoria de $m$ predictores del conjunto completo de $p$ predictores ($m < p$).

Al estar arriba, Years es la variable más importante para explicar el salario.↩︎
Recordar que si se quiere predecir una variable aleatoria $Y$ con una constante $m$ el mejor predictor es su esperanza, es decir, $m = E(Y)$.↩︎
Es decir, muestreo con reemplazo.↩︎