Capítulo 20 de 37 · intermedio

Árboles de decisión

Qué cubre este capítulo

En la semana 1 dibujamos una línea sobre un feature y le llamamos clasificador. Este capítulo es lo que pasa cuando una línea no alcanza: dibujas otra, y otra más, cada una partiendo un pedazo del espacio que ya habías recortado. Apila suficientes y obtienes un árbol de decisión — el modelo que se lee como un diagrama de flujo, se dobla alrededor de fronteras curvas y multiclase que un solo stump no puede tocar, y al que no le importa en qué unidades vienen tus features.

Construimos todo desde cero en NumPy — impureza de Gini, la búsqueda del mejor split, el crecimiento recursivo, la predicción caminando el árbol — y luego le pasamos el mismo trabajo a scikit-learn para verificar que los números coincidan. La pieza central es una animación: ves crecer el árbol un split a la vez y observas cómo el plano 2-D se va picando en cajas, cada caja pintada con la clase que predice. Al final las cajas abrazan los datos casi a la perfección, que es exactamente donde empieza el problema. Un árbol que ajusta perfectamente los datos de entrenamiento casi siempre los memorizó, y también vamos a ver eso suceder.

Quédate con una idea de la semana 1: un árbol de profundidad uno es un decision stump, el clasificador de umbral que ya construimos. Todo lo que sigue es ese mismo split, aplicado una y otra vez.

Un poco de historia

La idea de partir recursivamente es más vieja que la frase "machine learning". En 1963 James Morgan y John Sonquist, dos científicos sociales de Michigan, construyeron AID — Automatic Interaction Detection — para encontrar estructura en datos de encuestas dividiendo repetidamente a los encuestados en subgrupos que explicaran mejor el resultado. Corría en un mainframe y era, en espíritu, un árbol de regresión.

Dos corrientes llevaron la idea al machine learning moderno. En estadística, Leo Breiman, Jerome Friedman, Richard Olshen y Charles Stone publicaron Classification and Regression Trees en 1984 — el libro de CART — que fijó la versión que seguimos usando: splits binarios, impureza de Gini y poda para combatir el overfitting. En paralelo, del lado de la IA, Ross Quinlan construyó ID3 (1986) y luego C4.5 (1993), que usaban ganancia de información y entropía en lugar de Gini y manejaban cosas como valores faltantes. Las dos tradiciones convergieron en casi el mismo algoritmo. Lo que construimos aquí es CART: Gini, splits binarios, crecimiento greedy. Es el árbol que trae debajo del cofre cada librería de random forests y gradient boosting que vas a usar después, así que vale la pena construirlo una vez a mano.

La intuición

Olvídate de la diabetes por un segundo y mira flores. El dataset iris son 150 flores de tres especies, y si graficas dos mediciones — largo y ancho del pétalo — las especies casi se separan solas.

Mira el grupo de setosa abajo a la izquierda. Está completamente separado — un corte horizontal en un ancho de pétalo de más o menos 0.8 lo aísla de todo lo demás, sin errores. Eso es un stump, y te regala un tercio del camino. Las otras dos especies se traslapan arriba a la derecha, y ninguna línea sola las separa. Pero una línea que atraviese justo esa región sí, y luego quizá una línea más para limpiar los rezagados.

Esa es toda la idea de un árbol. Haz una pregunta de sí/no sobre un feature, divide los datos según la respuesta, y luego haz una pregunta nueva dentro de cada mitad. Cada pregunta es un stump. El árbol es lo que obtienes al seguir preguntando, dejando que cada región del espacio se gane su propia secuencia de cortes. Donde un stump solitario tiene que comprometerse con una línea para todo el dataset, un árbol gasta sus splits donde hacen falta.

La matemática

Un split solo vale la pena si deja los datos más puros de lo que los encontró, así que necesitamos medir pureza. CART usa la impureza de Gini. Para un conjunto de etiquetas donde la clase $k$ representa una fracción $p_k$ de las filas, la impureza es

G = 1 - \sum_{k} p_k^{2}

Léela como la probabilidad de equivocarte si adivinaras una etiqueta sacando una al azar del conjunto. Un nodo puro — todas las filas de la misma clase — tiene un $p_k = 1$ y el resto en cero, así que $G = 0$ . Un nodo de dos clases perfectamente balanceado tiene $p_0 = p_1 = 0.5$ , lo que da $G = 1 - 0.25 - 0.25 = 0.5$ . La raíz de iris con tres clases, 50 de cada especie, queda en $G = 1 - 3(1/3)^2 = 0.667$ , lo peor posible para tres clases.

Un split en el umbral $t$ sobre el feature $j$ manda las filas a un conjunto izquierdo $L$ (feature $\le t$ ) y uno derecho $R$ . Su calidad es la impureza con la que empezamos menos la impureza de los dos hijos ponderada por tamaño — la disminución de impureza:

\Delta(j, t) = G(\text{parent}) - \frac{|L|}{N}\,G(L) - \frac{|R|}{N}\,G(R)

Los pesos $|L|/N$ y $|R|/N$ importan: un split que deja perfectamente pura una esquinita mientras el grueso queda intacto no debería puntuar tan alto como uno que limpia todo el conjunto. Entrenar un nodo es elegir el feature y el umbral que maximizan esta disminución:

(j^{*}, t^{*}) = \arg\max_{j,\,t}\; \Delta(j, t)

Ese argmax es exactamente la búsqueda de la semana 1 — prueba cada línea candidata, quédate con la mejor — solo que ahora corre sobre todos los features a la vez, y vuelve a correr dentro de cada hijo. La disminución de impureza en la raíz de iris es $0.667 - 0.333 = 0.333$ : separar setosa reduce la impureza a la mitad con un solo corte.

En qué es bueno, en qué no

Los árboles son el modelo más legible para humanos en machine learning. La salida es un diagrama de flujo que puedes imprimir y entregarle a un experto del dominio que nunca ha oído hablar de gradientes, y puede discutirlo split por split. No les importa la escala de los features — Gini no cambia si mides el ancho del pétalo en centímetros o en pulgadas — así que no hay que normalizar ni estandarizar, nada del preprocesamiento que hace tropezar a la gente. Manejan features numéricos y categóricos juntos, encuentran interacciones por su cuenta anidando splits, y dibujan fronteras no lineales y multiclase que una sola línea jamás podría.

El problema es la varianza. Un árbol crecido a profundidad completa recorta los datos de entrenamiento en cajas tan ajustadas que cada una contiene un solo punto, alcanzando 100% de accuracy en entrenamiento a base de memorizar ruido. Mueve un punto y todo el árbol por encima de él puede reacomodarse. Esa inestabilidad es la debilidad definitoria del árbol, y es la razón por la que nadie lleva un solo árbol profundo a producción. La solución no es abandonar los árboles — es crecer muchos y promediar el ruido, que es bagging y random forests, o crecerlos en secuencia corrigiendo los errores del anterior, que es boosting. Ambos son los siguientes capítulos. Un árbol solo es el átomo; los modelos útiles se construyen con montones de ellos.

Los datos

Dos datasets hacen dos trabajos aquí. La animación conceptual usa iris en dos dimensiones — largo y ancho del pétalo, las tres especies, 150 flores — lo bastante pequeño y limpio como para que veas cada split caer sobre puntos que puedes ver.

Para los números honestos de accuracy regresamos al conjunto Pima Indians Diabetes de la semana 1: 768 pacientes, ocho mediciones cada uno, una etiqueta binaria de diabetes. Es ruidoso y traslapado de una forma en que iris no lo es, lo que lo convierte en el lugar correcto para ver a un árbol caer en overfitting. Los mismos datos, el mismo split 70/30 de la semana 1 — 537 pacientes para entrenar, 231 apartados para probar — para que los números sean comparables entre capítulos.

Constrúyelo, una función a la vez

Cuatro ideas, en el orden en que las escribirías. Primero la pureza, porque todo lo demás es una búsqueda para mejorarla.

Impureza de Gini de un conjunto de etiquetas — una línea de NumPy una vez que cuentas las clases:

def gini(y):
    """Gini impurity of a set of labels: 1 - sum_k p_k^2.

    0 when every label is the same (a pure node), and it climbs toward
    1 - 1/K as the K classes even out. This is the number a split tries to
    drive down.
    """
    if len(y) == 0:
        return 0.0
    counts = np.bincount(y)
    p = counts / counts.sum()
    return float(1.0 - np.sum(p * p))

np.bincount cuenta cuántas filas caen en cada clase; eleva al cuadrado las fracciones, suma y resta de uno. Una hoja tiene que adivinar una sola etiqueta, y adivina la más común del nodo:

def majority(y):
    """The label a leaf predicts: the most common class in the node.

    Ties break toward the lower class index (np.argmax keeps the first max),
    which is what makes a wrong dataset fail the checkpoints identically.
    """
    return int(np.argmax(np.bincount(y)))

Ahora el corazón del asunto: la búsqueda del mejor split. Este es el argmax de la semana 1 pero crecido — recorre cada feature, cada umbral candidato (los puntos medios entre valores únicos ordenados), califica cada split por su disminución de impureza y quédate con el ganador.

def best_split(X, y):
    """Search every feature and every candidate threshold for the split that
    most reduces Gini impurity.

    For each feature we take the midpoints between consecutive sorted unique
    values as candidate thresholds. A split sends rows with feature <= t left
    and the rest right; its quality is the parent impurity minus the
    size-weighted impurity of the two children (the impurity decrease). We
    return the (feature, threshold, gain) with the largest decrease, or None
    if no split helps.
    """
    n, d = X.shape
    parent = gini(y)
    best_gain, best_f, best_t = 0.0, -1, 0.0
    for f in range(d):
        values = np.unique(X[:, f])
        thresholds = (values[:-1] + values[1:]) / 2.0
        for t in thresholds:
            left = X[:, f] <= t
            n_left = int(left.sum())
            if n_left == 0 or n_left == n:
                continue
            child = (n_left / n) * gini(y[left]) + \
                    ((n - n_left) / n) * gini(y[~left])
            gain = parent - child
            if gain > best_gain:
                best_gain, best_f, best_t = gain, f, float(t)
    if best_f < 0:
        return None
    return best_f, best_t, best_gain

Fíjate en su forma: un split por umbral es esa misma comparación feature <= t del stump, y la lógica interna es calificar un corte. Lo único nuevo es el ciclo exterior sobre los features — el árbol puede elegir sobre qué medición partir, no solo dónde. Si ningún split reduce la impureza, devuelve None, y esa es la señal para detenerse.

Con una forma de encontrar un split, el árbol es ese split aplicado recursivamente. Construye un nodo, y si no es puro y no hemos llegado al límite de profundidad, pártelo y construye un hijo en cada mitad:

def build_tree(X, y, max_depth, depth=0):
    """Recursively grow a CART tree to a maximum depth.

    A node is a dict. A leaf carries its predicted class; an internal node
    carries the feature index and threshold to split on plus its two
    children. Recursion stops when the node is pure, the depth cap is hit, or
    no split reduces impurity — at which point the node becomes a leaf.
    """
    node = {"n": int(len(y)), "gini": gini(y), "prediction": majority(y)}
    if depth >= max_depth or node["gini"] == 0.0:
        node["leaf"] = True
        return node
    split = best_split(X, y)
    if split is None:
        node["leaf"] = True
        return node
    f, t, gain = split
    left = X[:, f] <= t
    node.update({
        "leaf": False, "feature": int(f), "threshold": t, "gain": gain,
        "left": build_tree(X[left], y[left], max_depth, depth + 1),
        "right": build_tree(X[~left], y[~left], max_depth, depth + 1),
    })
    return node

Cada nodo es un dict simple — una hoja carga su predicción, un nodo interno carga el feature y el umbral a evaluar más sus dos hijos. La recursión toca fondo de tres maneras: el nodo ya es puro, llegamos a max_depth, o ningún split ayuda. Pon max_depth=1 y esto construye un solo split — un stump, la semana 1 exacta.

La predicción es la mitad fácil. Suelta una muestra en la raíz y deja que la pregunta de cada nodo la mande a la izquierda o a la derecha hasta que aterrice en una hoja:

def predict_one(node, x):
    """Walk one sample from the root to a leaf, following each split."""
    while not node["leaf"]:
        node = node["left"] if x[node["feature"]] <= node["threshold"] \
            else node["right"]
    return node["prediction"]


def predict(tree, X):
    """Predict every row of X by walking the tree from the root."""
    return np.array([predict_one(tree, x) for x in X])

Sin aritmética, sin productos punto — solo una caminata por una cadena de comparaciones. Por eso los árboles predicen rápido y se leen con claridad.

Míralo trabajar

Aquí viene la recompensa. Este es el best_split real corriendo sobre los datos 2-D de iris, un split por frame, crecido best-first — en cada paso aplica el único split, en cualquier parte del árbol construido hasta entonces, que compra la mayor caída de impureza total. Mira cómo el plano se va recortando en cajas. Cada caja se sombrea con la clase que predeciría, la línea del split más reciente brilla en naranja, y los puntos quedan encima para que veas cuándo una caja se vuelve pura. El pie nombra el split y la accuracy de entrenamiento acumulada.

Dale play. El primer corte es el regalado — una línea horizontal en ancho de pétalo 0.8 aísla a setosa (cian) en su propia caja, y la accuracy salta de 0.33 (adivinar una sola clase para todos) a 0.67. De ahí en adelante los splits se ponen a trabajar en el traslape versicolor/virginica de arriba a la derecha, cada uno rebanando un rectángulo más pequeño para limpiar un puñado de puntos mal clasificados. Para el séptimo split las cajas abrazan las clases y la accuracy de entrenamiento es 0.993. Reinicia y córrelo otra vez.

Fíjate en cómo se comportan los splits tardíos. Recortan tiras delgadas para capturar uno o dos puntos tercos cerca de la frontera. En iris eso casi no importa. En datos más sucios es el comienzo del overfitting — el árbol contorsionándose alrededor de puntos individuales de entrenamiento que no van a generalizar. Para verlo con claridad necesitas datos más ruidosos y un conjunto de prueba apartado, así que aquí está sobre Pima. Esta gráfica muestra la accuracy de entrenamiento y la de prueba conforme dejamos que el árbol crezca más profundo:

Esta es la imagen con la que hay que quedarse. La accuracy de entrenamiento (cian) sube todo el camino — de 0.754 en profundidad 1 a 0.998 para la profundidad 12, un ajuste casi perfecto. La accuracy de prueba (morado) hace algo completamente distinto: llega a su pico de 0.736 en profundidad 4, luego da la vuelta y cae, hasta 0.662 en profundidad 12. Esa brecha que se abre entre las dos líneas es el overfitting, dibujado con datos reales. Cada split después de la profundidad 4 hace que el árbol se vea mejor en datos que ya vio y peor en datos que no. El árbol ya no está aprendiendo; está memorizando. La profundidad 4 es donde este árbol debería detenerse, y elegir ese punto de paro — con poda, con un tope de profundidad, con cross-validation — es la mitad de usar bien los árboles.

La implementación completa

Todo el asunto, sin librería, de arriba abajo. Cuatro funciones centrales y un par de helpers — este es el archivo que corrió la animación:

"""A classification decision tree (CART), built from scratch.

Grow a tree by repeatedly asking "which single yes/no question about one
feature splits this data into the two purest groups?", then recurse on each
group until the labels run out or a depth limit stops you. Prediction is a
walk from the root to a leaf, one comparison per node. Pure NumPy — no ML
library anywhere in this file (pandas only loads the CSV).

A depth-1 tree is exactly the decision stump from week 1: one feature, one
threshold, one split. Everything here is that idea, applied over and over.

Every function below appears in the chapter one step at a time (the
`# region:` markers are what the book's include directives pull in).
"""

import numpy as np
import pandas as pd


# region: gini
def gini(y):
    """Gini impurity of a set of labels: 1 - sum_k p_k^2.

    0 when every label is the same (a pure node), and it climbs toward
    1 - 1/K as the K classes even out. This is the number a split tries to
    drive down.
    """
    if len(y) == 0:
        return 0.0
    counts = np.bincount(y)
    p = counts / counts.sum()
    return float(1.0 - np.sum(p * p))
# endregion


# region: majority
def majority(y):
    """The label a leaf predicts: the most common class in the node.

    Ties break toward the lower class index (np.argmax keeps the first max),
    which is what makes a wrong dataset fail the checkpoints identically.
    """
    return int(np.argmax(np.bincount(y)))
# endregion


# region: best_split
def best_split(X, y):
    """Search every feature and every candidate threshold for the split that
    most reduces Gini impurity.

    For each feature we take the midpoints between consecutive sorted unique
    values as candidate thresholds. A split sends rows with feature <= t left
    and the rest right; its quality is the parent impurity minus the
    size-weighted impurity of the two children (the impurity decrease). We
    return the (feature, threshold, gain) with the largest decrease, or None
    if no split helps.
    """
    n, d = X.shape
    parent = gini(y)
    best_gain, best_f, best_t = 0.0, -1, 0.0
    for f in range(d):
        values = np.unique(X[:, f])
        thresholds = (values[:-1] + values[1:]) / 2.0
        for t in thresholds:
            left = X[:, f] <= t
            n_left = int(left.sum())
            if n_left == 0 or n_left == n:
                continue
            child = (n_left / n) * gini(y[left]) + \
                    ((n - n_left) / n) * gini(y[~left])
            gain = parent - child
            if gain > best_gain:
                best_gain, best_f, best_t = gain, f, float(t)
    if best_f < 0:
        return None
    return best_f, best_t, best_gain
# endregion


# region: build_tree
def build_tree(X, y, max_depth, depth=0):
    """Recursively grow a CART tree to a maximum depth.

    A node is a dict. A leaf carries its predicted class; an internal node
    carries the feature index and threshold to split on plus its two
    children. Recursion stops when the node is pure, the depth cap is hit, or
    no split reduces impurity — at which point the node becomes a leaf.
    """
    node = {"n": int(len(y)), "gini": gini(y), "prediction": majority(y)}
    if depth >= max_depth or node["gini"] == 0.0:
        node["leaf"] = True
        return node
    split = best_split(X, y)
    if split is None:
        node["leaf"] = True
        return node
    f, t, gain = split
    left = X[:, f] <= t
    node.update({
        "leaf": False, "feature": int(f), "threshold": t, "gain": gain,
        "left": build_tree(X[left], y[left], max_depth, depth + 1),
        "right": build_tree(X[~left], y[~left], max_depth, depth + 1),
    })
    return node
# endregion


# region: predict
def predict_one(node, x):
    """Walk one sample from the root to a leaf, following each split."""
    while not node["leaf"]:
        node = node["left"] if x[node["feature"]] <= node["threshold"] \
            else node["right"]
    return node["prediction"]


def predict(tree, X):
    """Predict every row of X by walking the tree from the root."""
    return np.array([predict_one(tree, x) for x in X])
# endregion


def accuracy(tree, X, y):
    """Fraction of rows the tree classifies correctly."""
    return float((predict(tree, X) == y).mean())


def count_leaves(node):
    """Number of leaves in the tree — its effective complexity."""
    if node["leaf"]:
        return 1
    return count_leaves(node["left"]) + count_leaves(node["right"])


def load_iris_2d(path="../data/iris.csv"):
    """Iris with just two features (petal length, petal width) and the 3-class
    target. Two dimensions so the axis-aligned splits are visible as boxes."""
    df = pd.read_csv(path)
    X = df[["petal_length", "petal_width"]].to_numpy(float)
    y = df["target"].to_numpy(int)
    return X, y, df


def load_diabetes(path="../data/diabetes.csv"):
    """Pima Indians Diabetes: 768 patients, 8 features, binary Outcome."""
    df = pd.read_csv(path)
    features = [c for c in df.columns if c != "Outcome"]
    X = df[features].to_numpy(float)
    y = df["Outcome"].to_numpy(int)
    return X, y, features

La versión de librería

Nadie escribe un árbol a mano en producción, y tú tampoco deberías una vez que ya construiste uno. El DecisionTreeClassifier de scikit-learn es el mismo algoritmo — Gini, mejor split greedy, crecimiento recursivo hasta un tope de profundidad — escrito en C y listo para podar:

def sk_tree(X_train, y_train, X_test, y_test, max_depth):
    """Fit a CART tree at a given depth and return (train_acc, test_acc).

    criterion="gini" and the greedy best-split search are sklearn's defaults,
    so this is the library twin of build_tree — same objective, same
    axis-aligned splits, same depth stop.
    """
    clf = DecisionTreeClassifier(
        criterion="gini", max_depth=max_depth, random_state=0,
    )
    clf.fit(X_train, y_train)
    train_acc = float(clf.score(X_train, y_train))
    test_acc = float(clf.score(X_test, y_test))
    return train_acc, test_acc, clf

criterion="gini" y la búsqueda greedy son los valores por defecto, así que esto de verdad es el gemelo de nuestro build_tree. Busca los mismos umbrales candidatos que nosotros y parte con feature <= threshold de la misma manera, por eso los dos coinciden tan de cerca. Las diferencias son las que importan en la práctica, no en la matemática: la versión de sklearn es órdenes de magnitud más rápida, expone poda de verdad (ccp_alpha, min_samples_leaf) que a nuestra versión le falta, y en la raíz de un random forest agrega submuestreo de features. El mismo árbol, más perillas.

Desde cero contra librería

Ajusta ambos con max_depth=4 sobre la mitad de entrenamiento de Pima con 537 pacientes, evalúa sobre los 231 apartados. Aquí está el cara a cara:

Las barras son idénticas: 0.736 de accuracy en prueba, ambos árboles, ambos con 16 hojas y 0.823 de accuracy en entrenamiento. Ese es el resultado que quieres — nuestra recursión escrita a mano y la implementación en C de sklearn crecieron el mismo árbol, porque con estos datos y esta profundidad solo hay un árbol greedy de Gini que crecer. Las cifras exactas viven en results.json, regenerado cada vez que el código cambia, para que la prosa y la gráfica no puedan desviarse de lo que el código produjo.

Dos notas honestas. Primero, 0.736 no es ningún triunfo — el stump de la semana 1 sacó 0.732 en este mismo split, así que tres niveles extra de árbol compraron cuatro milésimas de punto. Pima es un dataset difícil y ruidoso donde un árbol poco profundo apenas le gana a una línea, lo cual es una lección en sí misma: la profundidad no es accuracy gratis. Segundo, ese es el número de prueba. En los datos de entrenamiento el árbol de profundidad 4 saca 0.823 y uno profundo saca 0.998, y si citaras esos te estarías mintiendo a ti mismo. La brecha es todo el punto de la curva de overfitting de arriba.

Conclusiones

Un árbol de decisión es un stump que no dejaste de construir. Ese es el hilo conductor desde la semana 1: un split es un clasificador de umbral, y un árbol es la misma búsqueda greedy corrida recursivamente dentro de cada región que recorta. Todo lo que aprendiste del stump — que es interpretable, que no necesita escalado, que dibuja fronteras alineadas a los ejes — sigue siendo cierto, excepto que ahora las fronteras pueden doblarse alrededor de los datos porque tienes tantos cortes como quieras.

Esa libertad es todo el intercambio. Recurre a un árbol cuando quieras un modelo que un humano pueda leer, cuando tus features sean una mezcla de tipos y unidades que no quieres normalizar, o cuando la frontera sea no lineal de una forma que una línea no puede seguir. No confíes en un solo árbol profundo: va a memorizar tu conjunto de entrenamiento y se va a desmoronar con datos nuevos, exactamente como mostró la curva de Pima después de la profundidad 4. Ponle tope a la profundidad, pódalo, y trata a un árbol solo como diagnóstico y no como modelo final.

La razón por la que los árboles importan tanto no es el árbol individual — es lo que construyes a partir de él. Crece cientos sobre muestras bootstrap y promédialos, y la varianza que hace frágil a un árbol se diluye: eso es un random forest, el siguiente capítulo. Crécelos en secuencia, cada uno arreglando los errores del anterior, y obtienes gradient boosting, un par de capítulos después. Los dos modelos clásicos más fuertes en datos tabulares son solo árboles, apilados y coordinados. Construye bien el átomo y el resto del curso es apilarlo.