02-arboles.Rmd

# Árboles de decisión {#trees}

<!-- 
---
title: "Árboles de decisión"
author: "Aprendizaje Estadístico (MTE, USC)"
date: "Curso 2021/2022"
bibliography: ["packages.bib", "aprendizaje_estadistico.bib"]
link-citations: yes
output: 
  bookdown::html_document2:
    pandoc_args: ["--number-offset", "1,0"]
    toc: yes 
    # mathjax: local            # copia local de MathJax, hay que establecer:
    # self_contained: false     # las dependencias se guardan en ficheros externos 
  bookdown::pdf_document2:
    keep_tex: yes
    toc: yes 
---

bookdown::preview_chapter("02-arboles.Rmd")
knitr::purl("02-arboles.Rmd", documentation = 2)
knitr::spin("02-arboles.R",knit = FALSE)
-->

```{r , child = '_global_options.Rmd'}
```

Los *árboles de decisión* son uno de los métodos más simples y fáciles de interpretar para realizar predicciones en problemas de clasificación y de regresión. 
Se desarrollan a partir de los años 70 del siglo pasado como una alternativa versátil a los métodos clásicos de la estadística, fuertemente basados en las hipótesis de linealidad y de normalidad, y enseguida se convierten en una técnica básica del aprendizaje automático. 
Aunque su calidad predictiva es mediocre (especialmente en el caso de regresión), constituyen la base de otros métodos altamente competitivos (bagging, bosques aleatorios, boosting) en los que se combinan múltiples árboles para mejorar la predicción, pagando el precio, eso sí, de hacer más difícil la interpretación del modelo resultante.

La idea de este método consiste en la segmentación (partición) del *espacio predictor* (es decir, del conjunto de posibles valores de las variables predictoras) en regiones tan simples que el proceso se pueda representar mediante un árbol binario. 
Se parte de un nodo inicial que representa a toda la muestra (se utiliza la muestra de entrenamiento), del que salen dos ramas que dividen la muestra en dos subconjuntos, cada uno representado por un nuevo nodo. 
Como se muestra en la Figura \@ref(fig:arbol) este proceso se repite un número finito de veces hasta obtener las hojas del árbol, es decir, los nodos terminales, que son los que se utilizan para realizar la predicción.
Una vez construido el árbol, la predicción se realizará en cada nodo terminal utilizando, típicamente, la media en un problema de regresión y la moda en un problema de clasificación. 

```{r arbol, fig.cap="Ejemplo de un árbol de decisión obtenido al realizar una partición binaria recursiva de un espacio bidimensional.", echo=FALSE}
# El árbol tiene cuatro nodos terminales u hojas.
# En un nodo interno, si  $X_j < t_k$  se genera una rama a la rama izquierda, en caso contrario se crea la rama derecha corresponde a $X_j \ge t_k$.

library(rpart)

n <- 100
set.seed(1)
x1 <- runif(n)
x2 <- runif(n)
y <- x1 - 0.5*x2 + x2^2 + rnorm(n, 0, 1) 
data <- data.frame(x1, x2, y)
tree <- rpart(y ~ ., data = data, maxdepth = 3)
# Representar árbol
old.par <- par(xpd = TRUE, mar = c(2, 4, 1, 2) + 0.1)
plot(tree)
xy <- rpart:::rpartco(tree)
x <- xy$x
y <- xy$y
cxy <- par("cxy")
nodes <- row.names(tree$frame)
leaves <- tree$frame$var == "<leaf>"
cond <- c(expression(X[1] < s[1]), expression(X[1] < s[2]), expression(X[2] < s[3]))
text(x[!leaves], y[!leaves] + 0.5 * cxy[2], cond)
reg <- c(expression(R[1]), expression(R[2]), expression(R[3]), expression(R[4]))
text(x[leaves], y[leaves] - 0.5 * cxy[2], adj = 0.5, reg)
par(old.par)
```

<!-- 
Pendiente:
Incluir figuras en dos columnas? 
fig.cap="Izquierda: ejemplo de un árbol obtenido al realizar una partición binaria recursiva de un espacio bidimensional. Derecha: superficie de predicción correspondiente."
-->


Al final de este proceso iterativo el espacio predictor se ha particionado en regiones de forma rectangular en la que la predicción de la respuesta es constante  `r citefig("predictor")`. 
Si la relación entre las variables predictoras y la variable respuesta no se puede describir adecuadamente mediante rectángulos, la calidad predictiva del árbol será limitada. 
Como vemos, la simplicidad del modelo es su principal argumento, pero también su talón de Aquiles.

```{r predictor, echo=FALSE, fig.cap="Ejemplo de la superficie de predicción correspondiente a un árbol de decisión."}
#Ejemplo de la superficie de predicción correspondiente a un árbol obtenido al realizar una partición binaria recursiva de un espacio bidimensional
library(plotmo)
# Superficie de predicción
plotmo(tree, degree1 = FALSE, caption ="", main="", zlab = "y")
```

Como se ha dicho antes, cada nodo padre se divide, a través de dos ramas, en dos nodos hijos. 
Esto se hace seleccionando una variable predictora y dando respuesta a una pregunta dicotómica sobre ella.
Por ejemplo, ¿es el sueldo anual menor que 30000 euros?, o ¿es el género igual a *mujer*? 
Lo que se persigue con esta partición recursiva es que los nodos terminales sean homogéneos respecto a la variable respuesta $Y$. 

Por ejemplo, en un problema de clasificación, la homogeneidad de los nodos terminales significaría que en cada uno de ellos sólo hay elementos de una clase (categoría), y diríamos que los nodos son *puros*. 
En la práctica, esto siempre se puede conseguir construyendo árboles suficientemente profundos, con muchas hojas. 
Pero esta solución no es interesante, ya que va a dar lugar a un modelo excesivamente complejo y por tanto sobreajustado y de difícil interpretación. 
Será necesario encontrar un equilibrio entre la complejidad del árbol y la pureza de los nodos terminales.


En resumen:

- Métodos simples y fácilmente interpretables.

- Se representan mediante árboles binarios.

- Técnica clásica de apendizaje automático (computación).

- Válidos para regresión y para clasificación.

- Válidos para predictores numéricos y categóricos.

La metodología CART [Classification and Regresion Trees, @breiman1984classification] es la más popular para la construcción de árboles de decisión y es la que se va a explicar con algo de detalle en las siguientes secciones. 

En primer lugar se tratarán los *árboles de regresión* (árboles de decisión en un problema de regresión, en el que la variable respuesta $Y$ es numérica) y después veremos los *árboles de clasificación* (respuesta categórica) que son los más utilizados en la práctica (los primeros se suelen emplear únicamente como métodos descriptivos o como base de métodos más complejos).
Las variables predictoras $\mathbf{X}=(X_1, X_2, \ldots, X_p)$ pueden ser tanto numéricas como categóricas.
Además, con la metodología CART, las variables explicativas podrían contener datos faltantes.
Se pueden establecer "particiones sustitutas" (*surrogate splits*), de forma que cuando falta un valor en una variable que determina una división, se usa una variable alternativa que produce una partición similar. 


## Árboles de regresión CART

Como ya se comentó, la construcción del modelo se hace a partir de la muestra de entrenamiento, y 
consiste en la partición del espacio predictor en $J$ regiones 
$R_1, R_2, \ldots, R_J$, para cada una de las cuales se va a calcular una constante: 
la media de la variable respuesta $Y$ para las observaciones de entranamiento que 
caen en la región. Estas constantes son las que se van a utilizar para 
la predicción de nuevas observaciones; para ello solo hay que comprobar cuál es 
la región que le corresponde.

La cuestión clave es cómo se elige la partición del espacio predictor, para lo 
que vamos a utilizar como criterio de error el RSS (suma de los residuos al cuadrado). 
Como hemos dicho, vamos a modelizar la respuesta en cada región como una constante, 
por tanto en la región $R_j$ nos interesa el 
$min_{c_j} \sum_{i\in R_j} (y_i - c_j)^2$, que se alcanza en la media de las 
respuestas $y_i$ (de la muestra de entrenamiento) en la región $R_j$, 
a la que llamaremos $\widehat y_{R_j}$.
Por tanto, se deben seleccionar las regiones $R_1, R_2, \ldots, R_J$ que minimicen 

$$RSS = \sum_{j=1}^{J} \sum_{i\in R_j} (y_i - \widehat y_{R_j})^2$$ 
(Obsérvese el abuso de notación $i\in R_j$, que significa las observaciones 
$i\in N$ que verifican $x_i \in R_j$).

Pero este problema es, en la práctica, intratable y vamos a tener que simplificarlo. 
El método CART busca un compromiso 
entre rendimiento, por una parte, y sencillez e interpretabilidad, por otra, y por ello 
en lugar de hacer una búsqueda por todas las particiones posibles sigue un proceso 
iterativo (recursivo) en el que va realizando cortes binarios. En la primera iteración 
se trabaja con todos los datos:

- Una variable explicativa $X_j$ y un punto de corte $s$ definen dos hiperplanos
$R_1 = \{ X \mid X_j \le s \}$ y $R_2 = \{ X \mid X_j > s \}$.

- Se seleccionan los valores de $j$ y $s$ que minimizen 

$$ \sum_{i\in R_1} (y_i - \widehat y_{R_1})^2 + \sum_{i\in R_2} (y_i - \widehat y_{R_2})^2$$

A diferencia del problema original, este se soluciona de forma muy rápida. A continuación 
se repite el proceso en cada una de las dos regiones $R_1$ y $R_2$, y así sucesivamente 
hasta alcanzar un criterio de parada.

Fijémonos en que este método hace dos concesiones importantes: no solo restringe la forma 
que pueden adoptar las particiones, sino que además sigue un criterio de error *greedy*: 
en cada iteración busca minimizar el RSS de las dos regiones resultantes, sin preocuparse 
del error que se va a cometer en iteraciones sucesivas. Y fijémonos también en que este 
proceso se puede representar en forma de árbol binario (en el sentido de que de cada nodo 
salen dos ramas, o ninguna cuando se llega al final), de ahí la terminología de *hacer 
crecer* el árbol.

¿Y cuándo paramos? Se puede parar cuando se alcance una profundidad máxima, aunque lo 
más habitual es, para dividir un nodo (es decir, una región), exigirle un número mínimo 
de observaciones.

- Si el árbol resultante es demasiado grande, va a ser un modelo demasiado complejo, 
por tanto va a ser difícil de interpretar y, sobre todo, 
va a provocar un sobreajuste de los datos. Cuando se evalúe el rendimiento utilizando 
la muestra de validación, los resultados van a ser malos. Dicho de otra manera, tendremos un 
modelo con poco sesgo pero con mucha varianza y en consecuencia inestable (pequeños 
cambios en los datos darán lugar a modelos muy distintos). Más adelante veremos que esto 
justifica la utilización del *bagging* como técnica para reducir la varianza.

- Si el árbol es demasiado pequeño, va a tener menos varianza (menos inestable) a costa 
de más sesgo. Más adelante veremos que esto justifica la utilización del *boosting*. Los 
árboles pequeños son más fáciles de interpretar ya que permiten identificar las variables 
explicativas que más influyen en la predicción.

Sin entrar por ahora en métodos combinados (métodos *ensemble*, tipo *bagging* o *boosting*), 
vamos a explicar cómo encontrar un equilibrio entre sesgo y varianza. Lo que se hace es 
construir un árbol grande para a continuación empezar a *podarlo*. Podar un árbol significa 
colapsar cualquier cantidad de sus nodos internos (no terminales), dando lugar a otro árbol más 
pequeño al que llamaremos *subárbol* del árbol original. Sabemos que el árbol completo es 
el que va a tener menor error si utilizamos la muestra de entrenamiento, pero lo que 
realmente nos interesa es encontrar el subárbol con un menor error al utilizar la muestra 
de validación. Lamentablemente, no es una buena estrategia el evaluar todos los subárboles: 
simplemente, hay demasiados. Lo que se hace es, mediante un 
hiperparámetro (*tuning parameter* o parámetro de ajuste) controlar el tamaño del árbol, 
es decir, la complejidad del modelo, seleccionando el subárbol *óptimo* (para los datos 
de los que disponemos, claro). Veamos la idea.

Dado un subárbol $T$ con $R_1, R_2, \ldots, R_t$ nodos terminales, consideramos como 
medida del error el RSS más una penalización que depende de un hiperparámetro 
no negativo $\alpha \ge 0$

\begin{equation} 
RSS_{\alpha} = \sum_{j=1}^t \sum_{i\in R_j} (y_i - \widehat y_{R_j})^2 + \alpha t
(\#eq:rss-alpha)
\end{equation} 

Para cada valor del parámetro $\alpha$ existe un único subárbol *más pequeño* 
que minimiza este error (obsérvese que aunque hay un continuo de valores 
distinos de $\alpha$, sólo hay una cantidad finita de subárboles). 
Evidentemente, cuando $\alpha = 0$, ese subárbol será el árbol completo, algo que 
no nos interesa. Pero a medida que se incrementa $\alpha$ se penalizan los subárboles 
con muchos nodos terminales, dando lugar a una solución más pequeña. 
Encontrarla puede parecer muy costoso computacionalmente, pero lo 
cierto es que no lo es. El algoritmo consistente en ir colapsando nodos de forma 
sucesiva, de cada vez el nodo que produzca el menor incremento en el RSS (corregido por 
un factor que depende del tamaño), da 
lugar a una sucesión finita de subárboles que contiene, para todo $\alpha$, la 
solución.

Para finalizar, sólo resta seleccionar un valor de $\alpha$. 
Para ello, como se comentó en la Sección \@ref(entrenamiento-test), se podría dividir la muestra en tres subconjuntos: datos de entrenamiento, de validación y de test. 
Para cada valor del parámetro de complejidad $\alpha$ hemos utilizado la muestra de entrenamiento para obtener un árbol 
(en la jerga, para cada valor del hiperparámetro $\alpha$ se entrena un modelo). 
Se emplea la muestra independiente de validación para seleccionar el valor de $\alpha$ (y por tanto el árbol) con el que nos quedamos. 
Y por último emplearemos la muestra de test (independiente de las otras dos) para evaluar el rendimiento del árbol seleccionado. 
No obstante, lo más habitual para seleccionar el valor del hiperparámetro $\alpha$ es emplear validación cruzada (o otro tipo de remuestreo) en la muestra de entrenamiento en lugar de considerar una muestra adicional de validación.

Hay dos opciones muy utilizadas en la práctica para seleccionar el valor de $\alpha$: 
se puede utilizar directamente el valor que minimice el error; o se puede forzar 
que el modelo sea un poco más sencillo con la regla *one-standard-error*, que selecciona 
el árbol más pequeño que esté a una distancia de un error estándar del árbol obtenido 
mediante la opción anterior.


También es habitual escribir la Ecuación \@ref(eq:rss-alpha) reescalando el parámetro de complejidad como $\tilde \alpha = \alpha / RSS_0$, siendo $RSS_0 = \sum_{i=1}^{n} (y_i - \bar y)^2$ la variabilidad total (la suma de cuadrados residual del árbol sin divisiones):
$$RSS_{\tilde \alpha}=RSS + \tilde \alpha RSS_0 t$$

De esta forma se podría interpretar el hiperparámetro $\tilde \alpha$ como una penalización en la proporción de variabilidad explicada, ya que dividiendo la expresión anterior por $RSS_0$ obtendríamos la proporción de variabilidad residual y a partir de ella podríamos definir:
$$R^2_{\tilde \alpha}=R^2 - \tilde \alpha  t$$


## Árboles de clasificación CART

En un problema de clasificación la variable respuesta puede tomar los valores 
$1, 2, \ldots, K$, etiquetas que identifican las $K$ categorías del problema. 
Una vez construido el árbol, se comprueba cuál es la categoría modal de cada 
región: considerando la muestra de entrenamiento, la categoría más frecuente. 
Dada una observación, se predice que pertenece a la categoría modal de la 
región a la que pertenece.

El resto del proceso es idéntico al de los árboles de regresión ya explicado, 
con una única salvedad: no podemos utilizar RSS como medida del error. Es 
necesario buscar una medida del error adaptada a este contexto. 
Fijada una región, vamos a denotar por 
$\widehat p_{k}$, con $k = 1, 2, \ldots, K$, a la proporción de observaciones 
(de la muestra de entrenamiento) en la región que pertenecen a la categoría $k$. 
Se utilizan tres medidas distintas del error en la región:

- Proporción de errores de clasificación:
    $$1 - max_{k} (\widehat p_{k})$$

- Índice de Gini:
    $$\sum_{k=1}^K \widehat p_{k} (1 - \widehat p_{k})$$

- Entropía^[La entropía es un concepto básico de la teoría de la información [@shannon1948mathematical] y se mide en *bits* (cuando en la definición se utilizan $log_2$).] (*cross-entropy*):
    $$- \sum_{k=1}^K \widehat p_{k} \text{log}(\widehat p_{k})$$

Aunque la proporción de errores de clasificación es la medida del error más intuitiva, en la práctica sólo se utiliza para la fase de poda. Fijémonos que en el cálculo de esta medida sólo interviene $max_{k} (\widehat p_{k})$, mientras que en las medidas alternativas intervienen las proporciones $\widehat p_{k}$ de todas las categorías. Para la fase de crecimiento se utilizan indistintamente el índice de Gini o la entropía. Cuando nos interesa el error no en una única región sino en varias (al romper un nodo en dos, o al considerar todos los nodos terminales), se suman los errores de cada región previa ponderación por el número de observaciones que hay en cada una de ellas.

En la introducción de este tema se comentó que los árboles de decisión admiten tanto variables predictoras numéricas como categóricas, y esto es cierto tanto para árboles de regresión como para árboles de clasificación. Veamos brevemente como se tratarían los predictores categóricos a la hora de incorporarlos al árbol. El problema radica en qué se entiende por hacer un corte si las categorías del predictor no están ordenadas. Hay dos soluciones básicas:

- Definir variables predictoras *dummy*. Se trata de variables indicadoras, una por cada una de las categorías que tiene el predictor. Este criterio de *uno contra todos* tiene la ventaja de que estas variables son fácilmente interpretables, pero tiene el inconveniente de que puede aumentar mucho el número de variables predictoras.

- Ordenar las categorías de la variable predictora. Lo ideal sería considerar todas las ordenaciones posibles, pero eso es desde luego poco práctico: el incremento es factorial. El truco consiste en utilizar un único órden basado en algún criterio *greedy*. Por ejemplo, si la variable respuesta $Y$ también es categórica, se puede seleccionar una de sus categorías que resulte especialmente interesante y ordenar las categorías del predictor según su proporción en la categoría de $Y$. Este enfoque no añade complejidad al modelo, pero puede dar lugar a resultados de difícil interpretación.

## CART con el paquete `rpart`

La metodología CART está implementada en el paquete `r citepkg("rpart")` 
(Recursive PARTitioning)^[El paquete `r citepkg("tree")` es una traducción del original en S.]. 
La función principal es `rpart()` y habitualmente se emplea de la forma:

`rpart(formula, data, method, parms, control, ...)`  

* `formula`: permite especificar la respuesta y las variables predictoras de la forma habitual, 
  se suele establecer de la forma `respuesta ~ .` para incluir todas las posibles variables explicativas.
  
* `data`: `data.frame` (opcional; donde se evaluará la fórmula) con la muestra de entrenamiento.

* `method`: método empleado para realizar las particiones, puede ser `"anova"` (regresión), `"class"` (clasificación), 
  `"poisson"` (regresión de Poisson) o `"exp"` (supervivencia), o alternativamente una lista de funciones (con componentes 
  `init`, `split`, `eval`; ver la vignette [*User Written Split Functions*](https://cran.r-project.org/web/packages/rpart/vignettes/usercode.pdf)). 
  Por defecto se selecciona a partir de la variable respuesta en `formula`, 
  por ejemplo si es un factor (lo recomendado en clasificación) emplea `method = "class"`.

* `parms`: lista de parámetros opcionales para la partición en el caso de clasificación 
  (o regresión de Poisson). Puede contener los componentes `prior` (vector de probabilidades previas; 
  por defecto las frecuencias observadas), `loss` (matriz de pérdidas; con ceros en la diagonal y por defecto 1 en el resto) 
  y `split` (criterio de error; por defecto `"gini"` o alternativamente `"information"`).
  
* `control`: lista de opciones que controlan el algoritmo de partición, por defecto se seleccionan mediante la función `rpart.control`, 
  aunque también se pueden establecer en la llamada a la función principal, y los principales parámetros son:
  
    `rpart.control(minsplit = 20, minbucket = round(minsplit/3), cp = 0.01, xval = 10, maxdepth = 30, ...)`
  
    - `cp` es el parámetro de complejidad $\tilde \alpha$ para la poda del árbol, de forma que un valor de 1 se corresponde con un árbol sin divisiones y un valor de 0 con un árbol de profundidad máxima. 
      Adicionalmente, para reducir el tiempo de computación, el algoritmo empleado no realiza una partición si la proporción de reducción del error es inferior a este valor (valores más grandes simplifican el modelo y reducen el tiempo de computación).
      
    - `maxdepth` es la profundidad máxima del árbol (la profundidad de la raíz sería 0).
    
    - `minsplit` y `minbucket` son, respectivamente, los números mínimos de observaciones en un nodo intermedio para particionarlo 
      y en un nodo terminal.
    
    - `xval` es el número de grupos (folds) para validación cruzada.

Para más detalles consultar la documentación de esta función o la vignette [*Introduction to Rpart*](https://cran.r-project.org/web/packages/rpart/vignettes/longintro.pdf).

### Ejemplo: regresión

Emplearemos el conjunto de datos *winequality.RData* [ver @cortez2009modeling], que contiene información fisico-química 
(`fixed.acidity`, `volatile.acidity`, `citric.acid`, `residual.sugar`, `chlorides`, `free.sulfur.dioxide`, 
`total.sulfur.dioxide`, `density`, `pH`, `sulphates` y `alcohol`) y sensorial (`quality`) 
de una muestra de 1250 vinos portugueses de la variedad *Vinho Verde*.
Como respuesta consideraremos la variable `quality`  , mediana de al menos 3 evaluaciones de la calidad del vino realizadas por expertos, que los evaluaron entre 0 (muy malo) y 10 (muy excelente) como puede observarse en el gráfico de barras de la Figura \@ref(fig:barplot).

```{r barplot, fig.cap="Distribución de frecuencias de la calidad del vino (`winequality$quality`)."}
load("data/winequality.RData")
str(winequality)
barplot(table(winequality$quality))
```

En primer lugar se selecciona el 80\% de los datos como muestra de entrenamiento y el 20\% restante como muestra de test:
```{r}
set.seed(1)
nobs <- nrow(winequality)
itrain <- sample(nobs, 0.8 * nobs)
train <- winequality[itrain, ]
test <- winequality[-itrain, ]
```

Podemos obtener el árbol de decisión con las opciones por defecto con el comando:

```{r }
tree <- rpart(quality ~ ., data = train)
```

Al imprimirlo se muestra el número de observaciones e información
sobre los distintos nodos (número de nodo, condición que define la partición, 
número de observaciones en el nodo, función de pérdida y predicción), 
marcando con un `*` los nodos terminales.

```{r }
tree
```

Para representarlo se puede emplear las herramientas del paquete `r citepkg("rpart")`  `r citefig("arbolrpart")`.

```{r arbolrpart,fig.cap="Árbol de regresión para predecir `winequality$quality` (obtenido con las opciones por defecto de `rpart()`)."}
plot(tree)
text(tree)
```

Pero puede ser preferible emplear el paquete `r citepkg("rpart.plot")`  `r citefig("arbolrpartplot")`.

```{r arbolrpartplot,fig.cap="Representación del árbol de regresión obtenida con `rpart.plot()`."}
library(rpart.plot)
rpart.plot(tree)  
```

Nos interesa como se clasificaría a una nueva observación en los nodos terminales (en los nodos intermedios solo nos interesarían las condiciones, y el orden de las variables consideradas, hasta llegar a las hojas) y las correspondientes predicciones (la media de la respuesta en el correspondiente nodo terminal).
Para ello, puede ser de utilidad imprimir las reglas:

```{r }
rpart.rules(tree, style = "tall")
```

Por defecto se poda el árbol considerando `cp = 0.01`, que puede ser adecuado en muchos casos.
Sin embargo, para seleccionar el valor óptimo de este (hiper)parámetro se puede emplear validación cruzada.
En primer lugar habría que establecer `cp = 0` para construir el árbol completo, a la profundidad máxima 
(determinada por los valores de `minsplit` y `minbucket`, que se podrían seleccionar 
"a mano" dependiendo del número de observaciones o también considerándolos como hiperparámetos; esto último no está implementado en `rpart`, ni en principio en `caret`)^[Los parámetros `maxsurrogate`, `usesurrogate` y `surrogatestyle` serían de utilidad si hay datos faltantes.]. 

```{r }
tree <- rpart(quality ~ ., data = train, cp = 0)
```

Posteriormente podemos emplear las funciones `printcp()` (o `plotcp()`) para obtener (representar) 
los valores de CP para los árboles (óptimos) de menor tamaño junto con su error de validación cruzada 
`xerror` (reescalado de forma que el máximo de `rel error` es 1)^[Realmente en la tabla de texto se muestra el valor mínimo de CP, ya que se obtendría la misma solución para un rango de valores de CP (desde ese valor hasta el anterior, sin incluirlo), mientras que en el gráfico generado por `plotcp()` se representa la media geométrica de los extremos de ese intervalo `r citefig("cp")`.]:

```{r cp, fig.cap="Error de validación cruzada (reescalado) dependiendo del parámetro de complejidad CP empleado en el ajuste del árbol de decisión."}
printcp(tree)
plotcp(tree)
```

La tabla con los valores de las podas (óptimas, dependiendo del parámetro de complejidad) 
está almacenada en la componente `$cptable`:

```{r }
head(tree$cptable, 10)
```

A partir de la que podríamos seleccionar el valor óptimo de forma automática, 
siguiendo el criterio de un error estándar de @breiman1984classification: 

```{r }
xerror <- tree$cptable[,"xerror"]
imin.xerror <- which.min(xerror)
# Valor óptimo
tree$cptable[imin.xerror, ]
# Límite superior "oneSE rule" y complejidad mínima por debajo de ese valor
upper.xerror <- xerror[imin.xerror] + tree$cptable[imin.xerror, "xstd"]
icp <- min(which(xerror <= upper.xerror))
cp <- tree$cptable[icp, "CP"]
```

Para obtener el modelo final `r citefig("arbolpoda")` podamos el árbol con el valor de complejidad obtenido `r cp` que en este caso coincide con el valor óptimo).

```{r eval=F,echo=F}
tree <- prune(tree, cp = cp) #quitar este chunk
rpart.plot(tree, main="Regresion tree winequality") 
```

```{r arbolpoda,fig.cap="Árbol de regresión resultante después de la poda (modelo final)."}
tree <- prune(tree, cp = cp)
rpart.plot(tree) 
```


Podríamos estudiar el modelo final, por ejemplo mediante el método `summary()`, que entre otras cosas muestra una medida (en porcentaje) de la importancia de las variables explicativas para la predicción de la respuesta (teniendo en cuenta todas las particiones, principales y secundarias, en las que se emplea cada variable explicativa). 
Alternativamente podríamos emplear el siguiente código:

```{r }
# summary(tree)
importance <- tree$variable.importance # Equivalente a caret::varImp(tree) 
importance <- round(100*importance/sum(importance), 1)
importance[importance >= 1]
```

El último paso sería evaluarlo en la muestra de test siguiendo los pasos descritos en la Sección \@ref(eval-reg). A continuación se muestra el código necesario (la Figura \@ref(fig:obsXpred) muestra dicho rendimiento a través de remuestreo).

```{r obsXpred,fig.cap="Gráfico de observaciones frente a predicciones (`test$quality`; se añade una perturbación para mostrar la distribución de los valores)."}
obs <- test$quality
pred <- predict(tree, newdata = test)

# plot(pred, obs, main = "Observado frente a predicciones (quality)",
#      xlab = "Predicción", ylab = "Observado")
plot(jitter(pred), jitter(obs), xlab = "Predicción", ylab = "Observado")
abline(a = 0, b = 1)

# Empleando el paquete caret 
caret::postResample(pred, obs)

# Con la función accuracy()
accuracy <- function(pred, obs, na.rm = FALSE, 
                     tol = sqrt(.Machine$double.eps)) {
  err <- obs - pred     # Errores
  if(na.rm) {
    is.a <- !is.na(err)
    err <- err[is.a]
    obs <- obs[is.a]
  }  
  perr <- 100*err/pmax(obs, tol)  # Errores porcentuales
  return(c(
    me = mean(err),           # Error medio
    rmse = sqrt(mean(err^2)), # Raíz del error cuadrático medio 
    mae = mean(abs(err)),     # Error absoluto medio
    mpe = mean(perr),         # Error porcentual medio
    mape = mean(abs(perr)),   # Error porcentual absoluto medio
    r.squared = 1 - sum(err^2)/sum((obs - mean(obs))^2)
  ))
}
accuracy(pred, test$quality)
```

Como se puede observar el ajuste del modelo es bastante malo, como ya se comentó esto es habitual en árboles de regresión (especialmente si son tan pequeños) y normalmente solo se utilizan en un análisis exploratorio inicial (o como base para modelos más avanzados como los mostrados en el siguiente capítulo).
En problemas de clasificación es más habitual que se puedan llegar a obtener buenos ajustes con árboles de decisión.


```{exercise, label="efecto-semilla"}
```

Como se comentó en la introducción del Capítulo \@ref(intro-AE) al emplear el procedimiento habitual en AE de particionar los datos no se garantiza la reproducibilidad/repetibilidad de los resultados ya que dependen de la semilla. 
El modelo ajustado puede cambiar al variar la semilla (sobre todo si el conjunto de entrenamiento es pequeño; además, en algunos modelos el método de ajuste depende también de la semilla) pero normalmente no hay grandes cambios en las predicciones.

Podemos ilustrar el efecto de la semilla en los resultados empleando el ejemplo anterior. 
Habría que repetir el ajuste de un árbol de regresión considerando distintas semillas y comparar los resultados obtenidos.

La dificultad podría estar en como comparar los resultados. 
Una posible solución sería mantener fija la muestra de test (que forma que no dependa de las semillas). 
Por comodidad podríamos considerar las primeras `ntest` observaciones del conjunto de datos.
Posteriormente, para cada semilla, seleccionaríamos la muestra de entrenamiento de la forma habitual y ajustaríamos un árbol. Finalmente evaluaríamos los resultados en la muestra de test.

Como base se podría considerar el siguiente código:

```{r, eval=FALSE}
ntest <- 10
test <- winequality[1:ntest, ]
df <- winequality[-(1:ntest), ]
nobs <- nrow(df)

# Para las distintas semillas
set.seed(semilla)
itrain <- sample(nobs, 0.8 * nobs)
train <- df[itrain, ]

# tree <- ...
```

Como comentario final, en este caso el conjunto de datos no es muy grande y tampoco se obtuvo un buen ajuste con un árbol de regresión, por lo que sería de esperar que se observaran más diferencias.



```{exercise, label="train-validate-test-tree"}
```

Como ya se mostró, el paquete `rpart` implementa la selección del parámetro de complejidad mediante validación cruzada. 
Como alternativa, siguiendo la idea del Ejercicio \@ref(exr:train-validate-test), y considerando de nuevo el ejemplo anterior, particionar la muestra en datos de entrenamiento (70\%), de validación (15\%) y de test (15\%), para ajustar los árboles de decisión, seleccionar el parámetro de complejidad (el hiperparámetro) y evaluar las predicciones del modelo final, respectivamente.

```{exercise, label="train-boot-tree"}
```

Una alternativa a particionar en entrenamiento y validación sería emplear bootstrap.
La idea es emplear una remuestra bootstrap del conjunto de datos de entrenamiento para ajustar el modelo y utilizar las observaciones no seleccionadas (se suelen denominar datos *out of bag*) como conjunto de validación.


```{r }
set.seed(1)
nobs <- nrow(winequality)
itrain <- sample(nobs, 0.8 * nobs)
train <- winequality[itrain, ]
test <- winequality[-itrain, ]

# Indice muestra de entrenamiento bootstrap
set.seed(1)
ntrain <- nrow(train)
itrain.boot <- sample(ntrain, replace = TRUE)
train.boot <- train[itrain.boot, ]
```

La muestra bootstrap va a contener muchas observaciones repetidas y habrá observaciones no seleccionadas.
La probabilidad de que una observación no sea seleccionada es $(1 - 1/n)^n \approx e^{-1} \approx 0.37$.

```{r }
# Número de casos "out of bag"
ntrain - length(unique(itrain.boot))

# Muestra "out of bag"
# oob <- train[-unique(itrain.boot), ]
oob <- train[-itrain.boot, ]
```


El resto sería igual que el caso anterior cambiando `train` por `train.boot` y `validate` por `oob`.

Como comentario final, lo recomendable sería repetir el proceso un número grande de veces y promediar los errores (esto está relacionado con el método de *bagging* descrito en el siguiente capítulo), especialmente cuando el tamaño muestral es pequeño, pero por simplicidad consideraremos únicamente una muestra boostrap.


### Ejemplo: modelo de clasificación {#class-rpart}

Para ilustrar los árboles de clasificación CART, podemos emplear los datos anteriores de calidad de vino, considerando como respuesta una nueva variable `taste` que clasifica los vinos en "good" o "bad" dependiendo de si `winequality$quality >= 5` (este conjunto de datos está almacenado en el archivo *winetaste.RData*).

```{r}
# load("data/winetaste.RData")
winetaste <- winequality[, colnames(winequality)!="quality"]
winetaste$taste <- factor(winequality$quality < 6, labels = c('good', 'bad')) # levels = c('FALSE', 'TRUE')
str(winetaste)
table(winetaste$taste)
```

Como en el caso anterior, se contruyen las muestras de entrenamiento (80\%) y de test (20\%):

```{r }
# set.seed(1)
# nobs <- nrow(winetaste)
# itrain <- sample(nobs, 0.8 * nobs)
train <- winetaste[itrain, ]
test <- winetaste[-itrain, ]
```

Al igual que en el caso anterior podemos obtener el árbol de clasificación con las opciones por defecto (`cp = 0.01` y `split = "gini"`) con el comando:

```{r }
tree <- rpart(taste ~ ., data = train)
```

En este caso al imprimirlo como información de los nodos se muestra (además del número de nodo, la condición de la partición y el número de observaciones en el nodo) el número de observaciones mal clasificadas, la predicción y las proporciones estimadas (frecuencias relativas en la muestra de entrenamiento) de las clases:

```{r}
tree
```

También puede ser preferible emplear el paquete `r citepkg("rpart.plot")` para representarlo `r citefig("arbolclassif")`.

```{r arbolclassif,fig.cap="Árbol de clasificación de `winetaste$taste` (obtenido con las opciones por defecto)."}
library(rpart.plot)
rpart.plot(tree) # Alternativa: rattle::fancyRpartPlot
```


Nos interesa como se clasificaría a una nueva observación (como se llega a los nodos terminales) y su probabilidad estimada (la frecuencia relativa de la clase más frecuente en el correspondiente nodo terminal). Para ello se puede modificar la información que se muestra en cada nodo `r citefig("arbolextra")`.
```{r arbolextra,fig.cap="Representación del árbol de clasificación de `winetaste$taste` incluyendo información adicional en los nodos."}
rpart.plot(tree, 
           extra = 104,          # show fitted class, probs, percentages
           box.palette = "GnBu", # color scheme
           branch.lty = 3,       # dotted branch lines
           shadow.col = "gray",  # shadows under the node boxes
           nn = TRUE)            # display the node numbers 
```
Al igual que en el caso de regresión, puede ser de utilidad imprimir las reglas:

```{r }
rpart.rules(tree, style = "tall")
```

También se suele emplear el mismo procedimiento para seleccionar un valor óptimo del (hiper)parámetro de complejidad, se construye un árbol de decisión completo y se emplea validación cruzada para podarlo.
Además, si el número de observaciones es grande y las clases están más o menos balanceadas, 
se podría aumentar los valores mínimos de observaciones en los nodos intermedios y terminales^[Otra opción, más interesante para regresión, sería considerar estos valores como hiperparámetros.], por ejemplo:

```{r eval=FALSE}
tree <- rpart(taste ~ ., data = train, cp = 0, minsplit = 30, minbucket = 10)
```

En este caso mantenemos el resto de valores por defecto:

```{r }
tree <- rpart(taste ~ ., data = train, cp = 0)
```

Representamos los errores (reescalados) de validación cruzada `r citefig("errorclassif")`
```{r errorclassif,fig.cap="Evolución del error (reescalado) de validación cruzada en función del parámetro de complejidad."}
# printcp(tree)
plotcp(tree)
```

Para obtener el modelo final, seleccionamos el valor óptimo de complejidad siguiendo el criterio de un error estándar de @breiman1984classification y podamos el árbol `r citefig("arbolclassifpoda")`.

```{r arbolclassifpoda,fig.cap="Árbol de clasificación de `winetaste$taste` obtenido después de la poda (modelo final)."}
xerror <- tree$cptable[,"xerror"]
imin.xerror <- which.min(xerror)
upper.xerror <- xerror[imin.xerror] + tree$cptable[imin.xerror, "xstd"]
icp <- min(which(xerror <= upper.xerror))
cp <- tree$cptable[icp, "CP"]
tree <- prune(tree, cp = cp)
# tree
# summary(tree)
# caret::varImp(tree)
# importance <- tree$variable.importance
# importance <- round(100*importance/sum(importance), 1)
# importance[importance >= 1]
rpart.plot(tree) #, main="Classification tree winetaste"
```

El último paso sería evaluarlo en la muestra de test siguiendo los pasos descritos en la Sección \@ref(eval-class).
El método `predict()` por defecto (`type = "prob"`) devuelve una matriz con las probabilidades de cada clase, habrá que establecer `type = "class"` (para más detalles consultar la ayuda de `predic.rpart()`).

```{r }
obs <- test$taste
head(predict(tree, newdata = test))
pred <- predict(tree, newdata = test, type = "class")
table(obs, pred)

caret::confusionMatrix(pred, obs)
```


### Interfaz de `caret`

En `caret` podemos ajustar un árbol CART seleccionando `method = "rpart"`.
Por defecto emplea bootstrap de las observaciones para seleccionar el valor óptimo del hiperparámetro `cp` (considerando únicamente tres posibles valores).
Si queremos emplear validación cruzada como en el caso anterior podemos emplear la función auxiliar `trainControl()` y para considerar un mayor rango de posibles valores, el argumento `tuneLength` `r citefig("arbolclassifggplot")`.

```{r arbolclassifggplot,fig.cap="Evolución de la precisión (obtenida mediante validación cruzada) dependiendo del parámetro de complejidad."}

library(caret)
# names(getModelInfo()) # Listado de todos los métodos disponibles
# modelLookup("rpart")  # Información sobre hiperparámetros
set.seed(1)
# itrain <- createDataPartition(winetaste$taste, p = 0.8, list = FALSE)
# train <- winetaste[itrain, ]
# test <- winetaste[-itrain, ]
caret.rpart <- train(taste ~ ., method = "rpart", data = train, 
                     tuneLength = 20,
                     trControl = trainControl(method = "cv", number = 10)) 
caret.rpart
ggplot(caret.rpart)
```
El modelo final es el siguiente `r citefig("arbolfinalcaret")`
```{r arbolfinalcaret,fig.cap='Árbol de clasificación de `winetaste$taste`, obtenido con la complejidad "óptima" (empleando `caret`).'}
caret.rpart$finalModel
rpart.plot(caret.rpart$finalModel) #, main="Classification tree winetaste"
```

Para utilizar la regla de "un error estándar" se puede añadir `selectionFunction = "oneSE"`. A continuacióno se muestra dicho código y en la Figura \@ref(fig:arbolclassifoneSE) el árbol resultante.

```{r arbolclassifoneSE,fig.cap="Árbol de clasificación de `winetaste$taste`,  obtenido con la regla de un error estándar para seleccionar la complejidad (empleando `caret`)."}
set.seed(1)
caret.rpart <- train(taste ~ ., method = "rpart", data = train, 
                     tuneLength = 20,
                     trControl = trainControl(method = "cv", number = 10,
                                              selectionFunction = "oneSE")) 
caret.rpart
# ggplot(caret.rpart)
caret.rpart$finalModel
rpart.plot(caret.rpart$finalModel)#, main = "Classification tree winetaste"
```

```{r arbolImpor,fig.cap="Importancia de los (posibles) predictores según el modelo obtenido con la regla de un error estándar."}
var.imp <- varImp(caret.rpart)
plot(var.imp)
```

Para calcular las predicciones (o las estimaciones de las probabilidades) podemos emplear el método `predict.train()` y posteriormente `confusionMatrix()` para evaluar su precisión:

```{r}
pred <- predict(caret.rpart, newdata = test)
# p.est <- predict(caret.rpart, newdata = test, type = "prob")
confusionMatrix(pred, test$taste)
```

NOTA: En principio también se podría utilizar la regla de "un error estándar" seleccionando `method = "rpart1SE"` (pero `caret` implementa internamente este método y en ocasiones no se obtienen los resultados esperados).

```{r eval=FALSE}
set.seed(1)
caret.rpart <- train(taste ~ ., method = "rpart1SE", data = train) 
caret.rpart
printcp(caret.rpart$finalModel)
caret.rpart$finalModel
rpart.plot(caret.rpart$finalModel) #, main = "Classification tree winetaste"
varImp(caret.rpart)
```


Como alternativas al uso de la metodología CART desde `cartet` se  puede considerar las opciones de los metapaquetes:

* `r citepkg("mlr3", "https://mlr3book.mlr-org.com/mlr3book.pdf")`, que incorpora una llamada a `rpart::rpart()` desde sus **learners** `lrn("regr.rpart")` y `lrn("classif.rpart")`.
* `r citepkg("h2o", "https://www.h2o.ai/blog/finally-you-can-plot-h2o-decision-trees-in-r/")`, que aunque no ofrece una implementación de los árboles CART, sí ofrece dos alternativas más sofisticadas usando bosques aleatorios `h2o.randomForest()` y los procedimientos basados en el aumento del gradiente `h2o.gbm()`.


## Alternativas a los árboles CART

Una de las alternativas más populares es la metodología C4.5 [@quinlan1993c4], evolución de ID3 (1986), que en estos momentos se encuentra en la versión C5.0 (y es ya muy similar a CART). 
C5.0 se utiliza sólo para clasificación e incorpora *boosting* (que veremos en el tema siguiente).
Esta metodología está implementada en el paquete `r citepkg("C50", "https://topepo.github.io/C5.0/index.html")`. 

Ross Quinlan desarrolló también la metodologia M5 [@quinlan1992learning] para regresión. 
Su principal característica es que los nodos terminales, en lugar de contener un número, contienen un modelo (de regresión) lineal. 
El paquete `r citepkg("Cubist", "https://topepo.github.io/Cubist")` es una evolución de M5 que incorpora un método *ensemble* similar a *boosting*.

La motivación detrás de M5 es que, si la predicción que aporta un nodo terminal se limita a un único número (como hace la metodología CART), entonces el modelo va a predecir muy mal los valores que *realmente* son muy extremos, ya que el número de posibles valores predichos está limitado por el número de nodos terminales, y en cada uno de ellos se utiliza una media. 
Por ello M5 le asocia a cada nodo un modelo de regresión lineal, para cuyo ajuste se utilizan los datos del nodo y todas las variables que están en la ruta del nodo. 
Para evaluar los posibles cortes que conducen al siguiente nodo, se utilizan los propios modelos lineales para calcular la medida del error.

Una vez se ha construido todo el árbol, para realizar la predicción se puede utilizar el modelo lineal que está en el nodo terminal correspondiente, pero funciona mejor si se utiliza una combinación lineal del modelo del nodo terminal y de todos sus nodos ascendientes (es decir, los que están en su camino).

Otra opción es CHAID [CHi-squared Automated Interaction Detection, @kass1980exploratory], que se basa en una idea diferente. Es un método de construcción de árboles de clasificación que se utiliza cuando las variables predictoras son cualitativas o discretas; en caso contrario deben ser categorizadas previamente. 
Y se basa en el contraste chi-cuadrado de independencia para tablas de contingencia.

Para cada par $(X_i, Y)$, se considera su tabla de contingencia y se calcula el *p*-valor del contraste chi-cuadrado, seleccionándose la variable predictora que tenga un *p*-valor más pequeño, ya que se asume que las variables predictoras más relacionadas con la respuesta $Y$ son las que van a tener *p*-valores más pequeños y darán lugar a mejores predicciones. 
Se divide el nodo de acuerdo con los distintos valores de la variable predictora seleccionada, y se repite el proceso mientras haya variables *significativas*.
Como el método exige que el *p*-valor sea menor que 0.05 (o el nivel de significación que se elija), y hay que hacer muchas comparaciones es necesario aplicar una corrección para comparaciones múltiples, por ejemplo la de Bonferroni.

Lo que acabamos de explicar daría lugar a árboles no necesariamente binarios. 
Como se desea trabajar con árboles binarios (si se admite que de un nodo salga cualquier número de ramas, con muy pocos niveles de profundidad del árbol ya nos quedaríamos sin datos), es necesario hacer algo más: forzar a que las variables predictoras tengan sólo dos categorías mediante un proceso de fusión. 
Se van haciendo pruebas chi-cuadrado entre pares de categorías y la variable respuesta, y se fusiona el par con el *p*-valor más alto, ya que se trata de fusionar las categorías que sean más similares.

Para árboles de regresión hay metodologías que, al igual que CHAID, se basan en el cálculo de *p*-valores, en este caso de contrastes de igualdes de medias.
Una de las más utilizadas son los *conditional inference trees* [@hothorn2006unbiased]^[Otra alternativa es GUIDE (Generalized, Unbiased, Interaction Detection and Estimation; @loh2002regression).], implementada en la función `ctree()` del paquete `r citepkg("party")`.

Un problema conocido de los árboles CART es que sufren un sesgo de selección de variables: los predictores con más valores distintos son favorecidos. 
Esta es una de las motivaciones de utilizar estos métodos basados en contrastes de hipótesis. 
Por otra parte hay que ser conscientes de que los contrastes de hipótesis y la calidad predictiva son cosas distintas.


### Ejemplo

Siguiendo con el problema de clasificación anterior, podríamos ajustar un árbol de decisión empleando la metodología de *inferencia condicional* mediante el siguiente código:

```{r ctree-plot, fig.cap="Árbol de decisión para clasificar la calidad del vino (`winetaste$taste`) obtenido con el método condicional.", fig.height=8, fig.width=10}
library(party)
tree2 <- ctree(taste ~ ., data = train) 
plot(tree2)
```

Para más detalles ver la vignette del paquete [*party: A Laboratory for Recursive Partytioning*](https://cran.r-project.org/web/packages/party/vignettes/party.pdf).