====== 12 - Modelos clasificación 4: - Árboles de decisión ======

Los árboles de decisión son modelos predictivos formados por reglas binarias (si/no) con las que se consigue repartir las observaciones en función de sus atributos y predecir así el valor de la variable respuesta.

Los árboles de decisión pueden utilizarse tanto en problemas de regresión como de clasificación.

Para entender como funcionan, vamos a crear un árbol de decisión para el conjunto de datos //iris// con [[https://scikit-learn.org/stable/modules/generated/sklearn.tree.DecisionTreeClassifier.html|DecisionTreeClassifier]] de //sklearn//:

<sxh python>
import pandas as pd
import numpy as np

from sklearn.datasets import load_iris

from sklearn.tree import DecisionTreeClassifier
from sklearn.model_selection import train_test_split

from sklearn.tree import export_graphviz
from pydotplus import graph_from_dot_data

import matplotlib.pyplot as plt
from sklearn.metrics import plot_confusion_matrix
from sklearn.model_selection import cross_val_score, cross_val_predict

# Configuración warnings
# ==============================================================================
import warnings
warnings.filterwarnings('ignore')
</sxh>

<sxh python>
iris = load_iris()

df = pd.DataFrame(data = iris.data, columns = iris.feature_names)
df['target'] = iris.target

X = df.drop(columns = ['target'], axis = 1)
y = df['target']
</sxh>

<sxh python>
tree_clf = DecisionTreeClassifier()
tree_clf.fit(X, y)
</sxh>

Con ésto habremos creado y entrenado nuestro modelo. Si queremos ver el árbol resultante, podemos usar el método [[https://scikit-learn.org/stable/modules/generated/sklearn.tree.export_graphviz.html|export_graphviz()]] y pasarlo al formato que queramos (png, jpeg...) con el método //graph_from_dot_data()// de la librería [[https://pydotplus.readthedocs.io/reference.html|pydotplus]]:
<sxh python>
dot_data = export_graphviz(decision_tree = tree_clf,
                           feature_names=iris.feature_names,
                           filled=True,
                           class_names=iris.target_names
                           )
graph = graph_from_dot_data(dot_data)
graph.write_png('iris_tree_1.png')
</sxh>

El árbol resultante debería tener un aspecto como éste:

{{ :clase:ia:saa:7_sml_clasificacion:iris_tree_1.png?600 |}}

===== Hacer predicciones =====

Para hacer predicciones, el modelo empieza por el nodo raíz (profundidad 0, el nodo de arriba). Este nodo tiene una comparación (//petal width (cm) < = 0.8//). Si la respuesta es //True//, pasaría al nodo hijo de la izquierda. Este nodo es un **nodo terminal** (o **nodo hoja**), lo que quiere decir que no tiene nodos hijos, así que no formula ninguna otra pregunta. Simplemente miraría la clase predicha para ese nodo y sería la predicción.

Por el contrario, si la respuesta es False, pasaría al nodo hijo de la derecha, que no es un nodo terminal, con lo que haría otra pregunta (//petal width (cm) < = 1.75//) y continuaría el proceso hasta alcanzar algún nodo terminal.

El atributo //samples// de cada nodo indica a cuantas instancias de entrenamiento se aplica (por ejemplo, 50 instancias tienen una longitud de pétalo menor o igual que 0.8). El atributo //value// indica cuantas instancias de entrenamiento de cada clase se aplica a cada nodo. Por último, el atributo //gini// mide la impureza de un nodo. Un nodo es puro (gini = 0) si todas las instancias de entrenamiento a las que se aplica pertenecen a la misma clase.

<note>Un árbol de decisión también puede devolver la probabilidad de que una instancia pertenezca a cada una de las clases. Cuando llega a un nodo terminal, en lugar de devolver la clase mayoritaria, devuelve el ratio de instancias de entrenamiento de cada clase en ese nodo.</note>

===== Impureza de los nodos =====

Existen varias formas de medir la impureza de los nodos. Las dos más utilizadas son:

  * **Índice Gini**
  * **Entropía**

El //índice Gini// calcula la probabilidad de que una característica específica se clasifique incorrectamente cuando se selecciona al azar.Se calcula de la siguiente manera:

;#;
<fs medium>$\displaystyle Gini = 1 - \sum_{k=1}^{K}(P_{i})²$</fs>
;#;

Donde $P_{i}$ es la probabilidad de que un elemento se clasifique en cada clase, y K el número de clases del nodo.

Por ejemplo, para nuestro primer nodo del árbol anterior, el índice gini sería:
 
;#;
<fs medium>$\displaystyle Gini = 1 - ((\frac{50}{150})² + (\frac{50}{150})² + (\frac{50}{150})²) = 1 - (0.1111 + 0.1111 + 0.1111) = 1 - 0.3333 = 0.6667$</fs>
;#;

Cuanto más pequeño sea el valor del índice Gini, más puro será el nodo. Los nodos donde todos sus elementos son de la misma clase tienen como índice Gini = 0.

La //entropía// es una forma de cuantificar el desorden de un sistema. En el caso de los nodos, el desorden se corresponde con la impureza. Si un nodo es puro, contiene únicamente observaciones de una clase, su entropía es cero. Por el contrario, si la frecuencia de cada clase es la misma, el valor de la entropía alcanza el valor máximo de 1. Se calcula con:

;#;
<fs medium>$\displaystyle Entropía = -\sum_{k=1}^{K}(P_{i} * \log_{2}{P_{i}})$</fs>
;#;

===== El algoritmo de entrenamiento CART =====

//sklearn// utiliza el algoritmo //Classification and Regression Tree// (CART) para entrenar los árboles de decisión. El algoritmo funciona de la siguiente forma:

  * El proceso se inicia en lo más alto del árbol, donde están todas las observaciones
  * Se identifican todos los posibles puntos de corte para cada uno de los predictores. En el caso de predictores cualitativos, los posibles puntos de corte son cada uno de sus niveles. Para predictores continuos, se ordenan de menor a mayor sus valores, el punto intermedio entre cada par de valores se emplea como punto de corte.
  * Se identifica el predictor y punto de corte que consigue nodos lo más puros/homogéneos posible (la mayoría de observaciones pertenecen a la misma clase). Si existen dos o más divisiones que consiguen la misma mejora, la elección entre ellas es aleatoria.
  * Se repiten de forma iterativa los pasos anteriores para cada una de las regiones que se han creado en la iteración anterior hasta que se alcanza alguna norma de parada.

Para encontrar la característica ($k$) y el punto de corte ($t_{k}$) que separa los datos en nodos lo más puros posible, el algoritmo intenta minimizar la siguiente función de pérdida:

;#;
<fs medium>$\displaystyle J(k, t_{k})= \frac{m_{izq}}{m}G_{izq} + \frac{m_{dcha}}{m}G_{dcha}$</fs>
;#;

donde G_{izq/dcha} mide la impureza del subconjunto izquierda/derecha y m_{izq/dcha} es el número de instancias del subconjunto izquierda/derecha.

Una vez el algoritmo encuentra la característica y el umbral de corte, repite el proceso hasta que se cumple una condición de parada. Más adelante veremos qué hiperparámetros definen esas condiciones de parada, aunque si no especificamos ninguno (como es el caso del árbol que hemos creado), el algoritmo parará cuando todos los nodos terminales sean puros (gini = 0).

<note important>El algoritmo CART es un //algoritmo voraz//. Busca en cada paso una división óptima, sin comprobar si esa división llevará o no a la mejor impureza posible en los niveles inferiores. Un algoritmo voraz produce con frecuencia una solución razonablemente buena, pero sin garantías de que sea la óptima.</note>
 
===== Condiciones de parada =====

Si creamos un árbol de decisión sin ajustar ningún hiperparámetro, crecerá hasta que sus nodos terminales sean completamente puros (tendrán todos gini = 0). De esta forma, el modelo se ajustará perfectamente a los datos de entrenamiento, pero lo más seguro es que no generalice bien, ya que estará sobreajustando los datos (está "aprendiendo de memoria" más que detectando patrones).

Para evitarlo, podemos indicar algunas condiciones de parada mediante hiperparámetros a la hora de crear el modelo que hará que el árbol deje de crecer en función de esos criterios. Estos hiperparámetros dependen del algoritmo utilizado. //DecisionTreeClassifier// de //sklearn// tiene, entre otros:

  * **max_depth**: restringe la profundidad máxima (número de divisiones de la rama más larga) del árbol.
  * **min_samples_splitt**: número mínimo de muestras que ha de tener un nodo antes de poder dividirse.
  * **min_samples_leaf**: número mínimo de muestras que debe tener un nodo terminal. 
  * **min_weight_fraction_left**: igual que //min_samples_leaf//, pero expresado como una fracción del número total de instancias ponderadas.
  * **max_features**: número máximo de características que se evalúan para dividir en cada nodo.

Vamos a crear el mismo árbol que al principio pero restringiendo su profundidad máxima a 2:

<sxh python>
tree_clf = DecisionTreeClassifier(max_depth=2)
tree_clf.fit(X, y)
</sxh>

Árbol resultante:

<sxh python>
dot_data = export_graphviz(decision_tree = tree_clf,
                           feature_names=iris.feature_names,
                           filled=True,
                           class_names=iris.target_names
                           )
graph = graph_from_dot_data(dot_data)
graph.write_png('iris_tree_2.png')
</sxh>

{{ :clase:ia:saa:7_sml_clasificacion:iris_tree_2.png?400 |}}

<note>Otros algoritmos funcionan entrenando primero el árbol sin restricciones y borrando (podando) después los nodos innecesarios. Un nodo cuyos hijos son todos nodos terminales se considera innecesario si la mejora de la pureza  que proporciona no es significativa estadísticamente.</note>

===== Regresión =====

Como hemos dicho, los árboles de decisión también se pueden utilizar para regresión. El algoritmo CART funciona básicamente igual que antes, excepto que, en lugar de intentar dividir el conjunto de entrenamiento de una forma que minimice la impureza, ahora intenta dividirlo de manera que minimice el ECM (error cuadrático medio). 

Además, el modelo ya no devuelve una clase en los nodos terminales. Ahora la predicción será el valor medio de las instancias de entrenamiento de ese nodo.

<sxh python>
from sklearn.datasets import load_boston

boston = load_boston()

df = pd.DataFrame(data = boston.data, columns = boston.feature_names)
df['target'] = boston.target

X = df.drop(columns = ['target'], axis = 1)
y = df['target']
</sxh>

<sxh python>
from sklearn.tree import DecisionTreeRegressor

tree_reg = DecisionTreeRegressor(max_depth=3)
tree_reg.fit(X, y)
</sxh>

<sxh python>
dot_data = export_graphviz(decision_tree = tree_reg,
                           feature_names=boston.feature_names,
                           filled=True
                           )
graph = graph_from_dot_data(dot_data)
graph.write_png('boston_tree_1.png')
</sxh>

{{ :clase:ia:saa:7_sml_clasificacion:boston_tree_1.png?400 |}}