Random forests

Qué cubre este capítulo

La semana 3 terminó con una advertencia: nunca lleves a producción un solo árbol profundo, porque memoriza el set de entrenamiento y se desmorona con datos nuevos. Este capítulo es la solución, y es casi vergonzosamente simple. Toma el mismo árbol que ya construiste, cultiva unas cuantas docenas sobre vistas ligeramente distintas de los datos, y déjalos votar. La varianza que hacía frágil a un solo árbol se promedia y desaparece, y obtienes el modelo que, sin hacer ruido, gana más problemas tabulares que cualquier otro en un primer intento: el random forest.

Son dos trucos, ambos baratos. Cada árbol se entrena con una muestra bootstrap de las filas — muestrea el dataset con reemplazo, para que cada árbol vea un sorteo distinto. Y en cada split, en vez de buscar entre todas las features, el árbol solo puede mirar un puñado aleatorio. El primer truco es bagging; el segundo descorrelaciona los árboles para que sus errores no coincidan. Construimos ambos desde cero encima del best_split de la semana 3, luego le damos el mismo trabajo al RandomForestClassifier de scikit-learn y vemos cómo los números coinciden.

La pieza central es una animación: cultivamos el bosque un árbol a la vez y vemos la frontera de decisión del ensamble pasar de una escalera dentada de árbol único a una curva suave que abraza los datos, con un panel lateral que traza la accuracy subiendo y luego aplanándose conforme se acumulan los votos. Ese aplanamiento es toda la idea — reducción de varianza, dibujada con datos reales.

Un poco de historia

El árbol individual ya estaba maduro a mediados de los ochenta — CART en 1984, ID3 y C4.5 poco después — y todos conocían su debilidad. Un árbol es un modelo de alta varianza: reentrénalo con una muestra ligeramente distinta y puedes obtener un árbol completamente diferente. La idea que arregló esto, los random forests, llegó desde dos direcciones que se encontraron cerca del cambio de milenio.

En 1995 Tin Kam Ho, en Bell Labs, publicó "Random Decision Forests" y después el método de subespacios aleatorios: construye cada árbol sobre un subconjunto aleatorio de las features, para que no haya dos árboles mirando exactamente el mismo problema, y luego combínalos. De forma independiente, Leo Breiman — el mismo Breiman del libro de CART — venía trabajando en bagging (1996), abreviatura de bootstrap aggregating: entrena muchas copias de un modelo sobre remuestreos bootstrap de los datos y promédialas, lo cual demostró que reduce la varianza de predictores inestables como los árboles. En 2001 Breiman juntó las dos cosas en el paper que bautizó el método, "Random Forests". Su insight fue que el bagging por sí solo deja los árboles demasiado parecidos — todos se aferran a la misma feature fuerte en la raíz — así que agregó el submuestreo de features de Ho en cada split. Bootstrap de las filas, submuestreo de features, promedio de los votos. Esa receta, casi sin cambios, es la que trae hoy toda librería de random forest.

Lo que construimos aquí es el bosque de Breiman: el CART de la semana 3, con bagging sobre muestras bootstrap y descorrelacionado con subconjuntos de features por split. Vale la pena construirlo una vez a mano porque los mismos dos trucos — remuestrear y promediar, inyectar aleatoriedad para descorrelacionar — aparecen una y otra vez en machine learning.

La intuición

Un solo árbol dibuja cajas. Su frontera de decisión es una escalera de cortes horizontales y verticales, y sobre una frontera curva esa escalera es una aproximación burda que se dobla donde cayeron los puntos de entrenamiento. Mueve unos cuantos puntos y la escalera se reacomoda. Ese es el problema de la varianza, hecho visible.

Estos son los datos que usaremos para verlo: dos medias lunas entrelazadas, un set de juguete clásico con una frontera que ninguna línea recta ni ningún conjunto pequeño de cortes alineados a los ejes puede seguir limpiamente.

Las dos lunas se enroscan una alrededor de la otra, y hay ruido, así que se traslapan en el centro. Un árbol puede partir esto, pero lo hará con una escalera de bloques que sobreajusta el ruido. Ahora imagina cultivar un segundo árbol sobre una muestra aleatoria distinta de estos puntos — dibuja una escalera ligeramente diferente, equivocada en lugares distintos. Un tercero, equivocado en otro lado más. Pregúntales a los tres dónde pertenece un punto nuevo y toma la respuesta mayoritaria, y los lugares donde cualquier árbol se equivoca quedan superados en votos por los dos que casualmente aciertan. Sigue agregando árboles y las fronteras dentadas individuales se difuminan en un consenso suave.

Ese es el bosque. Ningún árbol individual es mejor que los árboles de la semana 3 — la magia está por completo en el promedio.

La matemática

¿Por qué ayuda promediar? Empieza con la varianza. Supón que tenemos $B$ árboles, cada uno un predictor insesgado pero ruidoso de la respuesta correcta, y cada uno con varianza $\sigma^{2}$ alrededor de ella. Si los árboles fueran independientes, la varianza de su promedio sería

Más árboles, menos varianza, directo hacia cero. Ese es el sueño, y es la razón por la que el bagging funciona: los árboles individuales conservan su bajo sesgo (cada uno sigue ajustándose duro a los datos), pero el promedio lava el ruido que hacía poco confiable a cualquiera de ellos.

El detalle es que los árboles no son independientes. Se entrenan sobre remuestreos del mismo dataset, así que tienden a coincidir — sobre todo en la parte alta, donde todos agarran la feature más predictiva. Sea $\rho$ la correlación promedio por pares entre las predicciones de los árboles. Entonces la varianza del promedio es

Lee los dos términos. El segundo se desvanece cuando $B \to \infty$ — esa es la parte que el bagging mata agregando árboles. El primero, $\rho\sigma^{2}$, no: es un piso por debajo del cual ningún número de árboles te puede llevar. Si los árboles están muy correlacionados, promediarlos apenas ayuda. Justo por eso el bagging solo se queda corto. La solución es atacar $\rho$ directamente, y eso es lo que hace la selección aleatoria de features: al forzar que cada split elija de un subconjunto aleatorio de features, evitas que todos los árboles se anclen en la misma feature dominante, los árboles crecen con formas genuinamente distintas, $\rho$ baja, y el piso baja con ella. Pagas un poco de sesgo — cada split se hace con un menú peor de opciones — a cambio de mucha reducción de varianza. En la mayoría de los datos tabulares ese intercambio te favorece por mucho.

La predicción en sí es un voto. Con $B$ árboles, cada uno devolviendo una clase $T_b(x)$ para la entrada $x$, el bosque predice la clase en la que más árboles coinciden:

donde $\mathbb{1}[\cdot]$ vale 1 cuando el árbol vota por la clase $c$ y 0 en caso contrario. Esa es toda la regla de agregación — cuenta los votos, toma la pluralidad.

Un número más sale gratis. Cada muestra bootstrap deja fuera alrededor de $1 - (1 - 1/n)^{n} \to 1 - 1/e \approx 0.368$ de las filas — el conjunto out-of-bag. Cada fila queda out-of-bag para aproximadamente un tercio de los árboles, así que podemos calificar cada fila usando solo los árboles que nunca entrenaron con ella, y promediar eso sobre todas las filas. Es una estimación de accuracy en datos no vistos que no cuesta nada extra — sin split de test separado, sin loop de cross-validation.

En qué es bueno, en qué no

Un random forest es el default más confiable que conozco para datos tabulares. Hereda todo lo bueno de los árboles — sin escalado de features, entradas numéricas y categóricas mezcladas, fronteras no lineales, interacciones encontradas automáticamente — y tira lo único que hacía inutilizable a un árbol individual, la varianza salvaje. Apenas necesita tuning: pon el número de árboles tan alto como tu cómputo permita, deja el subconjunto de features en el default de raíz cuadrada, y ya recorriste casi todo el camino hacia lo mejor que vas a obtener. Te da una estimación de accuracy OOB gratis y un ranking de importancia de features casi gratis. Cuando alguien me entrega un dataset tabular desconocido y pregunta "¿hay señal aquí?", un random forest es lo primero que ajusto, porque llega rápido a una respuesta decente y casi nunca me deja mal.

¿Dónde pierde? En dos lugares. No es la cima del leaderboard: en un dataset que vas a exprimir a fondo, el gradient boosting — los próximos capítulos — casi siempre le gana por poco, porque el boosting construye árboles que corrigen los errores de los demás en vez de solo promediar árboles independientes. Y renuncia a lo único que un árbol individual tenía a su favor, la legibilidad. Puedes imprimir un árbol y discutir con él; no puedes imprimir trescientos. Un bosque es una caja negra en la que confías porque valida bien, no porque puedas leerla. Si tu razón para usar árboles era la interpretabilidad, el bosque te la quita.

Los datos

Dos datasets, dos trabajos, el mismo split que en los últimos dos capítulos. La animación conceptual usa las lunas 2-D de arriba — 200 puntos, dos medias lunas entrelazadas con ruido, generadas con una semilla fija y commiteadas como moons.csv. Dos dimensiones para que puedas ver la frontera de decisión directamente, y una frontera curva para que la historia de dentado-a-suave sea obvia.

Para el número honesto de accuracy regresamos a Pima Indians Diabetes: 768 pacientes, ocho mediciones cada uno, una etiqueta binaria de diabetes, el mismo split 70/30 de las semanas 1 y 3 — 537 pacientes para entrenar, 231 apartados. Es ruidoso y con traslape, que es exactamente donde un árbol individual sobreajusta y un bosque se gana su lugar.

Constrúyelo, una función a la vez

Casi todo esto es la semana 3. gini, majority, predict — sin cambios, así que no los repetiré aquí; el bosque se construye con árboles CART ordinarios. Lo que cambia es pequeño y quirúrgico. Aquí está en el orden en que lo agregarías.

Primero, la línea que convierte un árbol en un árbol de bosque. El best_split de la semana 3 buscaba en cada feature; ahora busca solo en un subconjunto que le pasa quien lo llama:

def best_split(X, y, feature_ids):
    """Search a given subset of features for the split that most reduces Gini.

    This is week 3's best-split search with exactly one change: the outer loop
    runs over `feature_ids` — the random feature subset handed in by the caller
    — instead of every column. For each candidate feature we take the midpoints
    between consecutive sorted unique values as thresholds, send rows with
    feature <= t left and the rest right, and score the split by its impurity
    decrease (parent impurity minus the size-weighted impurity of the two
    children). We return the (feature, threshold, gain) with the largest
    decrease, or None if no split in this subset helps.
    """
    n = X.shape[0]
    parent = gini(y)
    best_gain, best_f, best_t = 0.0, -1, 0.0
    for f in feature_ids:
        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, int(f), float(t)
    if best_f < 0:
        return None
    return best_f, best_t, best_gain

El cuerpo es idéntico al de la semana 3 — misma búsqueda de umbral, mismo score de reducción de impureza. El único cambio es que el loop exterior recorre feature_ids en vez de range(d). Ese es todo el truco de descorrelación, un iterable sustituido.

Ahora build_tree sortea ese subconjunto de nuevo en cada nodo, para que cada split se haga desde un menú aleatorio distinto de features:

def build_tree(X, y, max_depth, max_features, rng, depth=0):
    """Grow one CART tree, but pick each split from a fresh random feature
    subset.

    Same recursion as week 3, with the de-correlating twist: at every node we
    draw `max_features` columns at random (without replacement) and only let
    `best_split` look at those. Two trees that saw different bootstrap rows and
    different feature subsets at each node grow into genuinely different shapes,
    which is the whole point — their mistakes won't line up.
    """
    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
    d = X.shape[1]
    k = min(max_features, d)
    feature_ids = rng.choice(d, size=k, replace=False)
    split = best_split(X, y, feature_ids)
    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, max_features, rng, depth + 1),
        "right": build_tree(X[~left], y[~left], max_depth, max_features, rng, depth + 1),
    })
    return node

La misma recursión de la semana 3, con dos líneas agregadas: elige k columnas aleatorias sin reemplazo, y pásalas a best_split. Un árbol cultivado así es un poco peor por sí solo — a veces se ve forzado a hacer split sobre una feature mediocre porque la buena no salió en el sorteo — pero ese es el precio de la descorrelación, y el promedio lo va a pagar con creces.

Sigue el bootstrap. Muestrea n índices de fila con reemplazo para armar la bolsa de entrenamiento de un árbol, y registra qué filas quedaron fuera:

def bootstrap_sample(n, rng):
    """Draw n row indices with replacement (the bag), and return the indices
    left out (the out-of-bag rows).

    About a third of the rows never make it into any given bag — those are the
    tree's private test set. `1 - (1 - 1/n)^n -> 1 - 1/e ~= 0.632` of the rows
    are in-bag, so ~36.8% are OOB. That free held-out set is what makes OOB
    accuracy possible.
    """
    in_bag = rng.integers(0, n, size=n)
    mask = np.zeros(n, dtype=bool)
    mask[in_bag] = True
    oob = np.where(~mask)[0]
    return in_bag, oob

Los índices out-of-bag son el ~36.8% de filas que este árbol nunca vio. Los usaremos en un momento para la estimación gratuita de accuracy. Esta es la otra fuente de aleatoriedad: cada árbol se entrena con un sorteo bootstrap distinto.

Con esas dos piezas, el bosque es solo un loop. Cultiva n_trees árboles, cada uno sobre su propia muestra bootstrap, cada split desde un subconjunto aleatorio de features, y guarda el conjunto OOB de cada árbol junto a él:

def build_forest(X, y, n_trees, max_depth, max_features, seed=0):
    """Grow a forest: n_trees CART trees, each on its own bootstrap sample,
    each split drawn from a random feature subset.

    We return the trees alongside each tree's OOB indices so we can score the
    forest on rows every tree was never trained on. One rng, seeded once,
    drives every random choice — bootstrap rows and feature subsets — so the
    whole forest is reproducible.
    """
    rng = np.random.default_rng(seed)
    n = len(y)
    trees, oob_sets = [], []
    for _ in range(n_trees):
        bag, oob = bootstrap_sample(n, rng)
        tree = build_tree(X[bag], y[bag], max_depth, max_features, rng)
        trees.append(tree)
        oob_sets.append(oob)
    return trees, oob_sets

Un solo rng, sembrado una vez, maneja cada sorteo bootstrap y cada subconjunto de features, así que todo el bosque es reproducible — vuélvelo a correr y obtienes los mismos árboles. No hay ajuste más allá de cultivar árboles; un random forest no tiene gradiente, ni iteración hasta convergencia, nada que afinar a media corrida. Cultivas los árboles y terminaste.

La predicción es el voto. Cada árbol predice cada fila; gana la clase con más votos:

def forest_vote(trees, X, n_classes):
    """Predict X by majority vote across every tree.

    Each tree casts one vote per row; the class with the most votes wins. This
    averaging is where the variance goes: a single tree is noisy, but the
    consensus of many de-correlated trees is stable.
    """
    votes = np.zeros((X.shape[0], n_classes), dtype=int)
    for tree in trees:
        preds = predict(tree, X)
        votes[np.arange(X.shape[0]), preds] += 1
    return votes.argmax(axis=1)

Y la recompensa por haber guardado los conjuntos OOB — una estimación de accuracy sobre datos no vistos sin apartar datos. Para cada fila, cuenta los votos solo de los árboles que nunca entrenaron con ella, y compara la mayoría con la verdad:

def oob_score(trees, oob_sets, X, y, n_classes):
    """Out-of-bag accuracy: for each row, tally votes only from the trees that
    never saw it, then compare the majority vote to the truth.

    This is a held-out accuracy estimate that costs nothing — no separate test
    split, no cross-validation. Every row is scored by the subset of trees for
    which it was out-of-bag.
    """
    votes = np.zeros((len(y), n_classes), dtype=int)
    for tree, oob in zip(trees, oob_sets):
        if len(oob) == 0:
            continue
        preds = predict(tree, X[oob])
        votes[oob, preds] += 1
    scored = votes.sum(axis=1) > 0
    pred = votes.argmax(axis=1)
    return float((pred[scored] == y[scored]).mean())

Ese es todo el modelo. Dos trucos atornillados al árbol de la semana 3 — remuestrea las filas, submuestrea las features — más un voto y una boleta de calificaciones gratis.

Míralo trabajar

Aquí está la animación a la que apunta todo el capítulo. Este es el bosque real de build_forest creciendo sobre las lunas 2-D, un árbol agregado por frame. El panel izquierdo sombrea el plano según el voto mayoritario del ensamble — cian para la clase 0, morado para la clase 1 — con la opacidad siguiendo qué tan seguro es el voto, así que una región donde todos los árboles coinciden se ve sólida y una región disputada cerca de la frontera se ve tenue. El panel derecho traza dos accuracies mientras el bosque crece: la accuracy de test sobre puntos apartados, y la estimación OOB gratuita.

Dale play y observa la frontera. El primer frame es un árbol — una escalera de bloques, puros bordes duros, exactamente el tipo de frontera sobreajustada contra la que advirtió la semana 3, y su accuracy de test es 0.750. Conforme se apilan los árboles, pasan dos cosas a la vez. Los bordes duros se suavizan: donde un árbol dibujó una esquina afilada, los siguientes la dibujaron un poco distinto, y el voto difumina esos desacuerdos en una curva suave que sigue las lunas. Y la banda tenue disputada a lo largo de la frontera — la región donde los árboles dividen sus votos — se estrecha conforme el consenso se afirma. A los treinta árboles la frontera es un arco limpio a través del hueco entre las lunas, la accuracy de test se estabilizó alrededor de 0.883, y la OOB la sigue justo por debajo en 0.850. La curva de accuracy sube rápido durante el primer puñado de árboles, rebota un poco por el test set pequeño, y luego se aplana — esa meseta es el término de reducción de varianza $\tfrac{1-\rho}{B}\sigma^{2}$ yéndose a cero. Pasadas un par de docenas de árboles, más árboles no te compran casi nada. Reinicia y córrela otra vez; es determinista.

Para ver la descorrelación directamente, aquí están las fronteras de tres de los árboles individuales junto al ensamble completo. Mismos datos, mismo código, distintos sorteos bootstrap y subconjuntos de features:

Mira qué distintos son los tres árboles individuales. Cada uno es un tallado dentado y sobreconfiado del plano, y están dentados en lugares distintos — los errores del árbol 1 no son los errores del árbol 2. Esa diferencia es todo el punto; así se ve $\rho < 1$. El ensamble del cuarto panel es lo que obtienes al promediarlos: los dientes idiosincráticos se cancelan y sobrevive una frontera suave. Ninguno de los árboles individuales sirve por sí solo. Juntos son el mejor modelo de la página.

La implementación completa

Todo, sin librería, de arriba a abajo — las funciones de árbol de la semana 3 más el puñado que les aplica bagging y las descorrelaciona. Este es el archivo que corrió la animación:

"""A random forest classifier, built from scratch.

A random forest is week 3's decision tree, bagged and de-correlated. We grow
many trees; each one is trained on a bootstrap sample of the rows (sample n
rows with replacement) and, crucially, each split is chosen from a random
subset of the features instead of all of them. Prediction is a majority vote
across the trees. The rows a tree never saw — its out-of-bag set — give a free
held-out accuracy estimate with no separate test split.

The tree code below is the week-3 CART with one change: `best_split` searches
a caller-supplied subset of features rather than every feature. That single
change is what turns a pile of near-identical trees into a forest whose errors
cancel. Pure NumPy — no ML library anywhere in this file (pandas only loads
the CSV).

Every function 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), climbing toward 1 - 1/K as
    the K classes even out. This is the number a split tries to drive down —
    identical to week 3, because a forest's trees are ordinary CART trees.
    """
    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 (and how the forest votes): the most common
    class. Ties break toward the lower class index, so results are
    deterministic given a fixed seed."""
    return int(np.argmax(np.bincount(y)))
# endregion


# region: best_split
def best_split(X, y, feature_ids):
    """Search a given subset of features for the split that most reduces Gini.

    This is week 3's best-split search with exactly one change: the outer loop
    runs over `feature_ids` — the random feature subset handed in by the caller
    — instead of every column. For each candidate feature we take the midpoints
    between consecutive sorted unique values as thresholds, send rows with
    feature <= t left and the rest right, and score the split by its impurity
    decrease (parent impurity minus the size-weighted impurity of the two
    children). We return the (feature, threshold, gain) with the largest
    decrease, or None if no split in this subset helps.
    """
    n = X.shape[0]
    parent = gini(y)
    best_gain, best_f, best_t = 0.0, -1, 0.0
    for f in feature_ids:
        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, int(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, max_features, rng, depth=0):
    """Grow one CART tree, but pick each split from a fresh random feature
    subset.

    Same recursion as week 3, with the de-correlating twist: at every node we
    draw `max_features` columns at random (without replacement) and only let
    `best_split` look at those. Two trees that saw different bootstrap rows and
    different feature subsets at each node grow into genuinely different shapes,
    which is the whole point — their mistakes won't line up.
    """
    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
    d = X.shape[1]
    k = min(max_features, d)
    feature_ids = rng.choice(d, size=k, replace=False)
    split = best_split(X, y, feature_ids)
    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, max_features, rng, depth + 1),
        "right": build_tree(X[~left], y[~left], max_depth, max_features, rng, depth + 1),
    })
    return node
# endregion


# region: predict
def predict_one(node, x):
    """Walk one sample from the root of a single tree to a leaf."""
    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 with one tree."""
    return np.array([predict_one(tree, x) for x in X])
# endregion


# region: bootstrap
def bootstrap_sample(n, rng):
    """Draw n row indices with replacement (the bag), and return the indices
    left out (the out-of-bag rows).

    About a third of the rows never make it into any given bag — those are the
    tree's private test set. `1 - (1 - 1/n)^n -> 1 - 1/e ~= 0.632` of the rows
    are in-bag, so ~36.8% are OOB. That free held-out set is what makes OOB
    accuracy possible.
    """
    in_bag = rng.integers(0, n, size=n)
    mask = np.zeros(n, dtype=bool)
    mask[in_bag] = True
    oob = np.where(~mask)[0]
    return in_bag, oob
# endregion


# region: build_forest
def build_forest(X, y, n_trees, max_depth, max_features, seed=0):
    """Grow a forest: n_trees CART trees, each on its own bootstrap sample,
    each split drawn from a random feature subset.

    We return the trees alongside each tree's OOB indices so we can score the
    forest on rows every tree was never trained on. One rng, seeded once,
    drives every random choice — bootstrap rows and feature subsets — so the
    whole forest is reproducible.
    """
    rng = np.random.default_rng(seed)
    n = len(y)
    trees, oob_sets = [], []
    for _ in range(n_trees):
        bag, oob = bootstrap_sample(n, rng)
        tree = build_tree(X[bag], y[bag], max_depth, max_features, rng)
        trees.append(tree)
        oob_sets.append(oob)
    return trees, oob_sets
# endregion


# region: forest_vote
def forest_vote(trees, X, n_classes):
    """Predict X by majority vote across every tree.

    Each tree casts one vote per row; the class with the most votes wins. This
    averaging is where the variance goes: a single tree is noisy, but the
    consensus of many de-correlated trees is stable.
    """
    votes = np.zeros((X.shape[0], n_classes), dtype=int)
    for tree in trees:
        preds = predict(tree, X)
        votes[np.arange(X.shape[0]), preds] += 1
    return votes.argmax(axis=1)
# endregion


# region: oob_score
def oob_score(trees, oob_sets, X, y, n_classes):
    """Out-of-bag accuracy: for each row, tally votes only from the trees that
    never saw it, then compare the majority vote to the truth.

    This is a held-out accuracy estimate that costs nothing — no separate test
    split, no cross-validation. Every row is scored by the subset of trees for
    which it was out-of-bag.
    """
    votes = np.zeros((len(y), n_classes), dtype=int)
    for tree, oob in zip(trees, oob_sets):
        if len(oob) == 0:
            continue
        preds = predict(tree, X[oob])
        votes[oob, preds] += 1
    scored = votes.sum(axis=1) > 0
    pred = votes.argmax(axis=1)
    return float((pred[scored] == y[scored]).mean())
# endregion


def accuracy(trees, X, y, n_classes):
    """Fraction of rows the forest's majority vote classifies correctly."""
    return float((forest_vote(trees, X, n_classes) == y).mean())


def n_features_sqrt(d):
    """The classic feature-subset size: floor(sqrt(d)), at least 1. Two
    features (moons) -> 1; eight features (diabetes) -> 2."""
    return max(1, int(np.sqrt(d)))


def load_moons(path="../data/moons.csv"):
    """The 2-D toy set: two interleaving half-moons, a curved boundary a single
    axis-aligned tree can only approximate with a staircase."""
    df = pd.read_csv(path)
    X = df[["x1", "x2"]].to_numpy(float)
    y = df["label"].to_numpy(int)
    return X, y, df


def load_diabetes(path="../data/diabetes.csv"):
    """Pima Indians Diabetes: 768 patients, 8 features, binary Outcome — the
    real dataset for the honest accuracy number, same file as weeks 1 and 3."""
    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 arma un bosque a mano en producción. El RandomForestClassifier de scikit-learn es el mismo algoritmo — muestras bootstrap, subconjuntos de features por split, voto mayoritario — escrito en C y paralelizado entre núcleos:

def sk_forest(X_train, y_train, X_test, y_test,
              n_trees, max_depth, seed=0):
    """Fit a random forest and return (train_acc, test_acc, oob_acc, clf).

    `max_features="sqrt"` is the de-correlating feature subset — the same
    floor(sqrt(d)) our scratch forest uses. `bootstrap=True` and majority vote
    are defaults, so this is the library twin of build_forest + forest_vote.
    `oob_score=True` asks sklearn for the same out-of-bag accuracy we compute
    by hand.
    """
    clf = RandomForestClassifier(
        n_estimators=n_trees, max_depth=max_depth,
        max_features="sqrt", bootstrap=True, oob_score=True,
        random_state=seed, n_jobs=-1,
    )
    clf.fit(X_train, y_train)
    train_acc = float(clf.score(X_train, y_train))
    test_acc = float(clf.score(X_test, y_test))
    oob_acc = float(clf.oob_score_)
    return train_acc, test_acc, oob_acc, clf

max_features="sqrt" es el mismo subconjunto de $\lfloor\sqrt{d}\rfloor$ features que sortea nuestro bosque desde cero, bootstrap=True y el voto mayoritario son defaults, y oob_score=True le pide a sklearn la misma estimación out-of-bag que calculamos a mano. Las diferencias son velocidad y perillas, no la idea: sklearn paraleliza los árboles entre n_jobs, expone min_samples_leaf y compañía para controlar el tamaño de los árboles, y te regresa feature_importances_ acumuladas a lo largo del bosque. El mismo bosque, más maquinaria.

Desde cero contra librería

Ajusta ambos bosques — 60 árboles, max_depth=8, subconjuntos de features de raíz cuadrada — sobre la mitad de entrenamiento de 537 pacientes de Pima, y califica sobre los 231 apartados. Y para rematar el punto sobre el bagging, pon un árbol individual de la semana 3 junto a ellos:

Los dos bosques caen juntos: nuestro bosque desde cero saca 0.758 en el test set apartado, el de sklearn saca 0.740. Difieren por menos de dos puntos, que es lo que quieres — sorteos aleatorios distintos cultivan árboles distintos, pero los ensambles coinciden, porque todo el método está diseñado para ser insensible a cualquier árbol individual. Nuestra estimación OOB, 0.767, queda un pelo por encima del número de test y no necesitó nada de datos apartados — esa es la boleta gratuita haciendo su trabajo.

Ahora el número que importa. El árbol individual — profundidad 8, todas las features, exactamente el modelo de la semana 3 — saca 0.667 en este test set. Aplicarle bagging a ese mismo árbol sesenta veces lo llevó de 0.667 a 0.758, nueve puntos, sin algoritmo nuevo y sin tuning. Ese es todo el pitch de los random forests en una comparación: el mismo árbol, apilado, descorrelacionado y votado. Como contraste, el árbol de la semana 3 con profundidad cuidadosamente limitada sacó 0.736 recortando la profundidad para pelear contra el overfitting; el bosque le gana cultivando sus árboles a profundidad 8 y dejándolos sobreajustar individualmente, porque el promedio limpia el overfitting gratis. Dejas de podar y empiezas a votar.

Aquí están la accuracy OOB y la de test subiendo conforme agregamos árboles sobre los datos reales, que es la meseta de la animación, dibujada sobre Pima:

Ambas curvas empiezan accidentadas — un árbol es ruidoso — suben con pendiente durante los primeros diez árboles más o menos, y luego se aplanan. Ese aplanamiento es el método completo diciéndote cuándo parar: pasadas unas cuantas docenas de árboles el término de varianza ya se agotó y estás pagando cómputo por nada. La OOB (naranja) sigue de cerca a la accuracy de test (morado) todo el camino, y por eso en la práctica confías en ella y te saltas el split de validación separado.

Conclusiones

Un random forest es el árbol de la semana 3, con bagging y descorrelacionado. Eso es todo. Ya tenías el átomo — un árbol CART con splits de Gini — y este capítulo le agregó dos líneas de aleatoriedad encima: bootstrap de las filas para que cada árbol vea una muestra distinta, y submuestreo de las features en cada split para que los árboles no piensen todos igual. Promedia sus votos y la varianza que hacía inutilizable a un solo árbol se lava. Sin gradientes, sin iteración, casi sin tuning.

Tómalo como tu default en datos tabulares. Cuando te llegue un dataset nuevo y quieras saber si hay señal, ajusta primero un random forest: maneja tipos de features mezclados sin escalar, encuentra interacciones por su cuenta, te da una estimación de accuracy OOB sin apartar datos, y rankea tus features por importancia, todo en un solo fit y casi sin configuración. Pon el número de árboles tan alto como tu cómputo permita — la accuracy se aplana, no sobreajusta con más árboles — deja el subconjunto de features en el default de raíz cuadrada, y sigue adelante. Es el baseline honesto que cualquier otro modelo tiene que superar.

Conoce también dónde se detiene. Si vas a exprimir un dataset hasta el último punto, el gradient boosting suele ganar, porque cultiva árboles que corrigen los errores de los demás en vez de promediar árboles independientes — ese es el siguiente tramo del curso, AdaBoost y luego gradient boosting y XGBoost. Y si necesitabas un árbol porque un humano tenía que leerlo, el bosque te lo quita; trescientos árboles son una caja negra. Pero para el amplio término medio — la mayoría de los problemas tabulares, la mayor parte del tiempo, cuando quieres una respuesta fuerte rápido y no puedes darte el lujo de cuidar un modelo — el random forest es el primero que agarro, y normalmente sigue de pie al final.