Phase 02 - Lesson 04

Árboles de decisión y bosques aleatorios

This lesson includes a graded coding exercise that runs in your browser, unlocked with lifetime access.

Un árbol de decisiones es sólo un diagrama de flujo. Pero un bosque de ellos es una de las herramientas más poderosas del machine learning.

Tipo: Construcción Idioma: Python Requisitos previos: Fase 1 (Lecciones 09 Teoría de la inentrenamiento, 06 Probabilidad) Tiempo: ~90 minutos

Objetivos de aprendizaje

• Implementar cálculos de impureza, entropía y ganancia de inentrenamiento de Gini para encontrar divisiones óptimas en los árboles de decisión.
• Cree un clasificador de árbol de decisión desde cero con controles previos a la poda (profundidad máxima, muestras mínimas)
• Construir un random forest utilizando muestreo de arranque y aleatorización de características, y explicar por qué reduce la varianza.
• Compare la importancia de la característica del MDI con la importancia de la permutación e identifique cuándo el MDI está sesgado

El problema

Tienes datos tabulares. Las filas son muestras, las columnas son características y hay una columna de destino que desea predecir. Podrías lanzarle una red neuronal. Pero para los datos tabulares, los modelos basados ​​en árboles (árboles de decisión, bosques aleatorios, árboles impulsados ​​por gradiente) superan consistentemente al aprendizaje profundo. Kaggle las competiciones sobre datos estructurados están dominadas por XGBoost y LightGBM, no por transformadores.

¿Por qué? Los árboles manejan tipos de características mixtas (numéricas y categóricas) sin preprocesamiento. Manejan relaciones no lineales sin ingeniería de características. Son interpretables: puedes mirar el árbol y ver exactamente por qué se hizo una predicción. Y los bosques aleatorios, que tienen en promedio muchos árboles, son muy resistentes al sobreajuste en conjuntos de datos de tamaño moderado.

Esta lección crea árboles de decisión desde cero mediante división recursiva y luego construye un random forest encima. Implementará las matemáticas detrás de los criterios divididos (impureza de Gini, entropía, ganancia de inentrenamiento) y comprenderá por qué un conjunto de alumnos débiles se convierte en uno fuerte.

El concepto

Qué hace un árbol de decisiones

Un árbol de decisión divide el espacio de características en regiones rectangulares mediante una secuencia de preguntas de sí o no.

graph TD
    A["Age < 30?"] -->|Yes| B["Income > 50k?"]
    A -->|No| C["Credit Score > 700?"]
    B -->|Yes| D["Approve"]
    B -->|No| E["Deny"]
    C -->|Yes| F["Approve"]
    C -->|No| G["Deny"]

Cada nodo interno prueba una característica contra un umbral. Cada nodo hoja hace una predicción. Para clasificar un nuevo punto de datos, comienza en la raíz y sigue las ramas hasta llegar a una hoja.

El árbol se construye de arriba hacia abajo eligiendo, en cada nodo, la característica y el umbral que mejor separan los datos. "Mejor" se define mediante un criterio dividido.

Criterios de división: medición de impurezas

En cada nodo, tenemos un conjunto de muestras. Queremos dividirlos para que los nodos secundarios resultantes sean lo más "puros" posible, lo que significa que cada hijo contiene principalmente una clase.

La impureza de Gini mide la probabilidad de que una muestra elegida al azar se clasifique erróneamente si se etiquetara según la distribución de clases en ese nodo.

Gini(S) = 1 - sum(p_k^2)

where p_k is the proportion of class k in set S.

Para un nodo puro (todos de una clase), Gini = 0. Para una división binaria con clases 50/50, Gini = 0,5. Más bajo es mejor.

Example: 6 cats, 4 dogs

Gini = 1 - (0.6^2 + 0.4^2) = 1 - (0.36 + 0.16) = 0.48

Entropía mide el contenido de inentrenamiento (desorden) en un nodo. Cubierto en la Fase 1, Lección 09.

Entropy(S) = -sum(p_k * log2(p_k))

Para un nodo puro, entropía = 0. Para una división binaria 50/50, entropía = 1,0. Más bajo es mejor.

Example: 6 cats, 4 dogs

Entropy = -(0.6 * log2(0.6) + 0.4 * log2(0.4))
        = -(0.6 * -0.737 + 0.4 * -1.322)
        = 0.442 + 0.529
        = 0.971 bits

Ganancia de inentrenamiento es la reducción de impurezas (entropía o Gini) después de una división.

IG(S, feature, threshold) = Impurity(S) - weighted_avg(Impurity(S_left), Impurity(S_right))

where the weights are the proportions of samples in each child.

El algoritmo codicioso en cada nodo: pruebe todas las funciones y todos los umbrales posibles. Elija el par (característica, umbral) que maximice la ganancia de inentrenamiento.

Cómo funciona la división

Para un conjunto de datos con n características ym muestras en el nodo actual:

1. Para cada característica j (j = 1 an):
   • Ordenar las muestras por característica j.
   • Pruebe cada punto medio entre valores distintos consecutivos como umbral
   • Calcular la ganancia de inentrenamiento para cada umbral.
2. Seleccione la característica y el umbral con la mayor ganancia de inentrenamiento.
3. Divida los datos en izquierda (característica <= umbral) y derecha (característica > umbral)
4. Recurrencia en cada niño.

Este enfoque codicioso no garantiza el árbol globalmente óptimo. Encontrar el árbol óptimo es NP-difícil. Pero la división codiciosa funciona bien en la práctica.

Condiciones de parada

Sin condiciones de parada, el árbol crece hasta que cada hoja sea pura (una muestra por hoja). Este memoriza perfectamente los datos del entrenamiento y generaliza terriblemente.

La poda previa detiene el árbol antes de que crezca por completo:

• Profundidad máxima: deja de dividirse cuando el árbol alcanza una profundidad establecida
• Muestras mínimas por hoja: detener si un nodo tiene menos de k muestras
• Ganancia mínima de inentrenamiento: detenerse si la mejor división mejora la impureza en menos de un umbral
• Máximo de nodos de hojas: limita el número total de hojas.

Después de la poda hace crecer el árbol completo y luego lo recorta:

• Poda de coste-complejidad (utilizada por scikit-learn): añade una penalización proporcional al número de hojas. Aumenta la penalización para conseguir árboles más pequeños.
• Poda de errores reducida: elimine un subárbol si el error de validación no aumenta

La poda previa es más sencilla y rápida. La pospoda a menudo produce mejores árboles porque no detiene prematuramente las divisiones que podrían conducir a otras divisiones útiles.

Árboles de decisión para la regresión

Para la regresión, la predicción de la hoja es la media de los valores objetivo en esa hoja. El criterio de división también cambia:

La reducción de la variación reemplaza la ganancia de inentrenamiento:

VR(S, feature, threshold) = Var(S) - weighted_avg(Var(S_left), Var(S_right))

Elija la división que reduzca más la variación. El árbol divide el espacio de entrada en regiones y predice una constante (la media) en cada región.

Bosques aleatorios: el poder de los conjuntos

Un único árbol de decisión tiene una alta varianza. Pequeños cambios en los datos pueden producir árboles completamente diferentes. Los bosques aleatorios solucionan este problema promediando muchos árboles.

graph TD
    D["Training Data"] --> B1["Bootstrap Sample 1"]
    D --> B2["Bootstrap Sample 2"]
    D --> B3["Bootstrap Sample 3"]
    D --> BN["Bootstrap Sample N"]
    B1 --> T1["Tree 1<br>(random feature subset)"]
    B2 --> T2["Tree 2<br>(random feature subset)"]
    B3 --> T3["Tree 3<br>(random feature subset)"]
    BN --> TN["Tree N<br>(random feature subset)"]
    T1 --> V["Aggregate Predictions<br>(majority vote or average)"]
    T2 --> V
    T3 --> V
    TN --> V

Dos fuentes de aleatoriedad hacen que los árboles sean diversos:

Bagging (agregación de arranque): Cada árbol se entrena con una muestra de arranque, una muestra aleatoria con reemplazo a partir de los datos de entrenamiento. Aproximadamente el 63% de las muestras originales aparecen en cada arranque (el resto son muestras listas para usar que se pueden usar para la validación).

Aleatorización de funciones: En cada división, solo se considera un subconjunto aleatorio de funciones. Para la clasificación, el valor predeterminado es sqrt(n_features). Para regresión, n_features/3. Esto evita que todos los árboles se divida en la misma característica dominante.

La idea clave: promediar muchos árboles no correlacionados reduce la varianza sin aumentar el sesgo. Cada árbol individual puede ser mediocre. El conjunto es fuerte.

Importancia de la característica

Los bosques aleatorios naturalmente proporcionan puntuaciones de importancia de las características. El método más común:

Disminución media de impurezas (MDI): Para cada característica, sume la reducción total de impurezas en todos los árboles y todos los nodos donde se utiliza esa característica. Las características que producen mayores reducciones de impurezas en divisiones anteriores son más importantes.

importance(feature_j) = sum over all nodes where feature_j is used:
    (n_samples_at_node / n_total_samples) * impurity_decrease

Esto es rápido (se calcula durante el entrenamiento) pero está sesgado hacia características de alta cardinalidad y características con muchos posibles puntos de división.

Importancia de la permutación es la alternativa: mezclar los valores de una característica y medir cuánto cae la precisión del modelo. Más fiable pero más lento.

Cuando los árboles vencen a las redes neuronales

Los árboles y los bosques dominan las redes neuronales en datos tabulares. Varias razones:

Las redes neuronales ganan cuando los datos tienen una estructura espacial o secuencial (imágenes, texto, audio). Para tablas planas de entidades, los árboles son los predeterminados.

Constrúyelo

Paso 1: impureza y entropía de Gini

Cree ambos criterios de división desde cero y verifique que coincidan en qué divisiones son buenas.

import math

def gini_impurity(labels):
    n = len(labels)
    if n == 0:
        return 0.0
    counts = {}
    for label in labels:
        counts[label] = counts.get(label, 0) + 1
    return 1.0 - sum((c / n) ** 2 for c in counts.values())

def entropy(labels):
    n = len(labels)
    if n == 0:
        return 0.0
    counts = {}
    for label in labels:
        counts[label] = counts.get(label, 0) + 1
    return -sum(
        (c / n) * math.log2(c / n) for c in counts.values() if c > 0
    )

Paso 2: Encuentra la mejor división

Pruebe todas las funciones y todos los umbrales. Devuelve el que tenga la mayor ganancia de inentrenamiento.

def information_gain(parent_labels, left_labels, right_labels, criterion="gini"):
    measure = gini_impurity if criterion == "gini" else entropy
    n = len(parent_labels)
    n_left = len(left_labels)
    n_right = len(right_labels)
    if n_left == 0 or n_right == 0:
        return 0.0
    parent_impurity = measure(parent_labels)
    child_impurity = (
        (n_left / n) * measure(left_labels) +
        (n_right / n) * measure(right_labels)
    )
    return parent_impurity - child_impurity

Paso 3: construir la clase DecisionTree

División recursiva, predicción y seguimiento de la importancia de las características.

class DecisionTree:
    def __init__(self, max_depth=None, min_samples_split=2,
                 min_samples_leaf=1, criterion="gini",
                 max_features=None):
        self.max_depth = max_depth
        self.min_samples_split = min_samples_split
        self.min_samples_leaf = min_samples_leaf
        self.criterion = criterion
        self.max_features = max_features
        self.tree = None
        self.feature_importances_ = None

    def fit(self, X, y):
        self.n_features = len(X[0])
        self.feature_importances_ = [0.0] * self.n_features
        self.n_samples = len(X)
        self.tree = self._build(X, y, depth=0)
        total = sum(self.feature_importances_)
        if total > 0:
            self.feature_importances_ = [
                fi / total for fi in self.feature_importances_
            ]

    def predict(self, X):
        return [self._predict_one(x, self.tree) for x in X]

Paso 4: construir la clase RandomForest

Muestreo bootstrap, aleatorización de funciones y votación mayoritaria.

class RandomForest:
    def __init__(self, n_trees=100, max_depth=None,
                 min_samples_split=2, max_features="sqrt",
                 criterion="gini"):
        self.n_trees = n_trees
        self.max_depth = max_depth
        self.min_samples_split = min_samples_split
        self.max_features = max_features
        self.criterion = criterion
        self.trees = []

    def fit(self, X, y):
        n = len(X)
        for _ in range(self.n_trees):
            indices = [random.randint(0, n - 1) for _ in range(n)]
            X_boot = [X[i] for i in indices]
            y_boot = [y[i] for i in indices]
            tree = DecisionTree(
                max_depth=self.max_depth,
                min_samples_split=self.min_samples_split,
                max_features=self.max_features,
                criterion=self.criterion,
            )
            tree.fit(X_boot, y_boot)
            self.trees.append(tree)

    def predict(self, X):
        all_preds = [tree.predict(X) for tree in self.trees]
        predictions = []
        for i in range(len(X)):
            votes = {}
            for preds in all_preds:
                v = preds[i]
                votes[v] = votes.get(v, 0) + 1
            predictions.append(max(votes, key=votes.get))
        return predictions

Consulte code/trees.py para ver la implementación completa con todos los métodos auxiliares.

Úsalo

Con scikit-learn, entrenar un random forest son tres líneas:

from sklearn.ensemble import RandomForestClassifier
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split

X, y = load_iris(return_X_y=True)
X_train, X_test, y_train, y_test = train_test_split(X, y, random_state=42)

rf = RandomForestClassifier(n_estimators=100, random_state=42)
rf.fit(X_train, y_train)
print(f"Accuracy: {rf.score(X_test, y_test):.4f}")
print(f"Feature importances: {rf.feature_importances_}")

En la práctica, los árboles potenciados por gradiente (XGBoost, LightGBM, CatBoost) suelen ser más fuertes que los bosques aleatorios porque construyen árboles de forma secuencial, y cada árbol corrige los errores de los anteriores. Pero los bosques aleatorios son más difíciles de configurar mal y casi no requieren ajuste de hiperparámetros.

Envíalo

Esta lección produce outputs/prompt-tree-interpreter.md, un mensaje que interpreta las divisiones del árbol de decisiones para las partes interesadas del negocio. Aliméntelo con la estructura de un árbol entrenado (profundidad, características, umbrales de división, precisión) y traduce el modelo en reglas de lenguaje sencillo, clasifica la importancia de las características, señala el sobreajuste o las fugas y recomienda los siguientes pasos. Úselo cada vez que necesite explicar un modelo basado en árbol a alguien que no lee código.

Ejercicios

1. Entrene un árbol de decisión único en un conjunto de datos 2D con 3 clases. Trace manualmente las divisiones y dibuje los límites de decisión rectangulares. Compare los límites en max_profundidad = 2 con max_profundidad = 10.

2. Implementar división de reducción de varianza para árboles de regresión. Genere y = sin(x) + ruido para 200 puntos y ajuste su árbol de regresión. Trazar las predicciones constantes por partes del árbol contra la curva verdadera.

3. Construye un random forest con 1, 5, 10, 50 y 200 árboles. Trazar la precisión del entrenamiento y probar la precisión frente al número de árboles. Observe que la precisión de la prueba se estabiliza pero no disminuye (los bosques resisten el sobreajuste).

4. Compare la impureza de Gini con la entropía como criterio dividido en 5 conjuntos de datos diferentes. Mida la precisión y la profundidad del árbol. En la mayoría de los casos, producen resultados casi idénticos. Explique por qué.

5. Implementar la importancia de la permutación. Compárelo con la importancia del MDI en un conjunto de datos donde una característica es ruido aleatorio pero tiene una cardinalidad alta. MDI dará una alta calificación a la característica de ruido. La importancia de la permutación no lo hará.

Términos clave

Lectura adicional

• Breiman: Random Forests (2001) - el artículo original sobre bosques aleatorios
• Grinsztajn et al.: ¿Por qué los modelos basados en árboles aún superan al aprendizaje profundo en datos tabulares? (2022): comparación rigurosa de árboles frente a redes neuronales en tareas tabulares
• scikit-learn Documentación de árboles de decisión - guía práctica con herramientas de visualización
• XGBoost: Un árbol escalable Boosting System (Chen & Guestrin, 2016): el papel que mejora el gradiente que domina Kaggle