56  CART: árboles binarios, índice de Gini y poda

Autor/a

Diego Villalba

CART (Classification and Regression Trees), propuesto por Breiman et al. (1984), es la versión de los árboles de decisión que domina la práctica: es el algoritmo de scikit-learn y el bloque de construcción de los bosques aleatorios y del gradient boosting. Comparte con ID3 la estrategia voraz y recursiva del capítulo anterior, pero cambia cuatro decisiones de diseño:

ID3 / C4.5 CART
Forma de las divisiones Multivía (una rama por valor) Siempre binaria
Impureza Entropía, razón de ganancia Índice de Gini (o entropía)
Variables numéricas C4.5: cortes binarios Cortes binarios, reutilizables
Control de complejidad Poda pesimista Poda de costo-complejidad con validación
Regresión No Sí (error cuadrático)
Tabla 56.1: Diferencias principales entre ID3/C4.5 y CART.

La restricción binaria parece una limitación, pero tiene ventajas: evita el sesgo hacia atributos con muchos valores (cada pregunta parte en solo dos grupos), permite agrupar categorías parecidas y produce árboles que, en el plano, son particiones en rectángulos. Este capítulo construye CART a mano con un ejemplo categórico, lo lleva al plano con variables numéricas y desarrolla su contribución más importante: la poda de costo-complejidad.

56.1 Intuición: ¿quién compra una laptop?

Catorce clientes de una tienda de electrónica, descritos por cuatro atributos categóricos (Han et al. 2011):

Id Edad Ingreso Estudiante Crédito ¿Compra?
1 joven alto no favorable no
2 joven alto no excelente no
3 adulto alto no favorable sí
4 mayor medio no favorable sí
5 mayor bajo sí favorable sí
6 mayor bajo sí excelente no
7 adulto bajo sí excelente sí
8 joven medio no favorable no
9 joven bajo sí favorable sí
10 mayor medio sí favorable sí
11 joven medio sí excelente sí
12 adulto medio no excelente sí
13 adulto alto sí favorable sí
14 mayor medio no excelente no
Tabla 56.2: Catorce clientes, 9 compran y 5 no.

CART no puede preguntar «¿qué edad tiene?» con tres respuestas. Debe preguntar algo de sí o no: «¿es adulto?», «¿es joven?» o «¿es joven o mayor?». La pregunta adecuada es la que deja los dos grupos más puros.

56.2 Construcción paso a paso

56.2.1 Paso 1. La impureza de Gini en la raíz

El índice de Gini de un nodo con proporciones de clase \(p_1, \ldots, p_K\) es

\[ G = 1 - \sum_{k=1}^{K} p_k^2. \tag{56.1}\]

Es la probabilidad de equivocarse si se etiqueta un ejemplo al azar según las proporciones del nodo1. En la raíz, con 9 «sí» y 5 «no»:

1 Si en un nodo hay una proporción \(p_k\) de cada clase y se etiqueta un ejemplo al azar con la clase \(k\) con probabilidad \(p_k\), la probabilidad de acertar es \(\sum_k p_k^2\) y la de equivocarse, \(1 - \sum_k p_k^2\). Es también la varianza de la variable indicadora de clase sumada sobre las clases.

\[ G_{\text{raíz}} = 1 - \left(\tfrac{9}{14}\right)^2 - \left(\tfrac{5}{14}\right)^2 = 1 - 0.413 - 0.128 = 0.459. \]

56.2.2 Paso 2. Las preguntas binarias de un atributo

Edad tiene tres valores, así que admite \(2^{3-1} - 1 = 3\) preguntas binarias distintas. Para «¿edad = adulto?»: los 4 adultos compran todos (Gini 0) y los otros 10 se reparten 5 y 5 (Gini 0.5). La impureza ponderada es

\[ \tfrac{4}{14}(0) + \tfrac{10}{14}(0.5) = 0.357, \qquad \Delta G = 0.459 - 0.357 = 0.102. \]

Pregunta Sí cumple (sí/no) No cumple (sí/no) Gini ponderado Reducción \(\Delta G\)
¿edad = adulto? 4 / 0 5 / 5 0.357 0.102
¿edad = joven? 2 / 3 7 / 2 0.394 0.066
¿edad = mayor? 3 / 2 6 / 3 0.457 0.002
Tabla 56.3: Las tres preguntas binarias para la edad.

56.2.3 Paso 3. Comparar atributos

Repitiendo el cálculo para cada atributo y quedándonos con su mejor pregunta:

Atributo Mejor pregunta Gini ponderado Reducción
Edad ¿adulto? 0.357 0.102
Estudiante ¿estudiante? 0.367 0.092
Crédito ¿excelente? 0.429 0.031
Ingreso ¿alto? 0.443 0.016
Tabla 56.4: Mejor pregunta de cada atributo en la raíz.

La raíz pregunta «¿edad = adulto?». La rama «sí» es pura (4 compras) y se vuelve hoja; la rama «no» (10 clientes, 5 y 5) se vuelve a dividir con el mismo procedimiento, donde la edad puede reaparecer con otra pregunta («¿joven?»), algo imposible en ID3.

56.2.4 Paso 4. Variables numéricas: cortes

Con una variable numérica, la pregunta es «¿\(x \le t\)?». Se ordenan los valores y se prueban los puntos medios entre valores consecutivos. Con cuatro clientes de edades 20 (sí), 25 (sí), 30 (no) y 40 (no):

Corte \(t\) Izquierda Derecha Gini ponderado
22.5 1 sí 1 sí, 2 no \(\frac{3}{4}\big(1 - \frac{1}{9} - \frac{4}{9}\big) = 0.333\)
27.5 2 sí 2 no 0
35.0 2 sí, 1 no 1 no \(\frac{3}{4}\big(1 - \frac{4}{9} - \frac{1}{9}\big) = 0.333\)
Tabla 56.5: Cortes candidatos para una variable numérica.

Con dos variables numéricas, cada corte es una recta vertical u horizontal, y el árbol completo parte el plano en rectángulos, cada uno con la clase mayoritaria de los puntos que contiene. El laboratorio de este capítulo lo muestra con 60 puntos.

56.2.5 Paso 5. Podar: el eslabón más débil

Un árbol que crece hasta tener hojas puras sobreajusta. En los datos del laboratorio, el árbol completo tiene 18 hojas, acierta el 100 % del entrenamiento y solo el 71.7 % de 300 puntos de prueba. CART propone crecer el árbol completo y después podarlo, cambiando cada subárbol por una hoja cuando la mejora que aporta no compensa su tamaño.

Para medir la mejora, sea \(R(t) = \frac{n_t}{n} G_t\) la impureza ponderada del nodo \(t\) si fuera una hoja, y \(R(T_t)\) la suma de esa cantidad sobre las hojas del subárbol que cuelga de \(t\). El costo por hoja de conservar el subárbol es

\[ g(t) = \frac{R(t) - R(T_t)}{|T_t| - 1}, \]

la reducción de impureza que aporta cada hoja adicional. Tomemos el árbol de cuatro hojas que aparece en la secuencia de poda del laboratorio:

Nodo Pregunta Ejemplos (0/1) \(G_t\) \(R(t)\) \(R(T_t)\) Hojas \(g(t)\)
raíz \(x_2 \le 5.70\) 33 / 27 0.495 0.495 0.224 4 0.090
izquierdo \(x_1 \le 4.05\) 15 / 19 0.493 0.279 0.164 2 0.115
derecho \(x_1 \le 2.30\) 18 / 8 0.426 0.185 0.060 2 0.125
Tabla 56.6: Costo por hoja de cada nodo interno del árbol de cuatro hojas.

Por ejemplo, para la raíz, las cuatro hojas tienen 13, 21, 6 y 20 puntos con impurezas 0.260, 0.308, 0 y 0.180, así que \(R(T) = \frac{13}{60}0.260 + \frac{21}{60}0.308 + 0 + \frac{20}{60}0.180 = 0.224\) y \(g = (0.495 - 0.224)/3 = 0.090\).

El nodo con el menor \(g(t)\) es el eslabón más débil: el primero que conviene podar cuando se penaliza el tamaño. Sorprendentemente, aquí es la raíz: con una penalización mayor que 0.090 por hoja, el árbol pasa de cuatro hojas a una sola. Ese valor de \(g\) es el \(\alpha\) al que ocurre la poda.

56.3 Formalización

56.3.1 Impureza y reducción de impureza

Para un nodo \(t\) con \(n_t\) ejemplos que una pregunta \(s\) divide en \(t_L\) y \(t_R\), CART elige

\[ s^{*} = \arg\max_{s} \; \Delta G(s, t) = G_t - \frac{n_{t_L}}{n_t} G_{t_L} - \frac{n_{t_R}}{n_t} G_{t_R}. \tag{56.2}\]

scikit-learn permite criterion="gini" o "entropy"; como se vio en el capítulo anterior, ambas son estrictamente cóncavas y casi siempre eligen la misma pregunta. Gini es algo más rápido de calcular porque no usa logaritmos.

Atributos categóricos. Un atributo con \(m\) valores admite \(2^{m-1} - 1\) preguntas binarias, número que explota con muchas categorías. Para dos clases, Breiman et al. (1984) demostraron un atajo: si se ordenan las categorías por su proporción de la clase positiva, la partición óptima es uno de los \(m - 1\) cortes de ese orden. En el ejemplo, las proporciones de compra son joven 0.40, mayor 0.60 y adulto 1.00; los cortes del orden son {joven} | {mayor, adulto} y {joven, mayor} | {adulto}, y el segundo es el óptimo de la Tabla 56.3.

Atributos numéricos. Tras ordenar los \(n_t\) valores, todos los cortes se evalúan en una pasada actualizando los conteos de cada lado. Una variable puede volver a usarse más abajo con otro corte. Como solo importa el orden de los valores, el árbol es invariante a transformaciones monótonas (logaritmos, escalamiento): no hace falta estandarizar.

56.3.2 Importancia de las variables

Sumando, para cada variable, las reducciones de impureza ponderadas \(\frac{n_t}{n}\Delta G\) de todos los nodos donde se usa, y normalizando para que sumen 1, se obtiene la importancia por disminución de impureza (MDI), el atributo feature_importances_ de scikit-learn. Es gratuita, pero sesgada a favor de variables numéricas o con muchas categorías, que ofrecen más cortes posibles. La importancia por permutación y los valores SHAP, que se estudian con los ensambles, son alternativas más fiables.

56.3.3 Poda de costo-complejidad

Para \(\alpha \ge 0\) se define el costo-complejidad de un subárbol \(T\) del árbol completo \(T_0\):

\[ R_\alpha(T) = R(T) + \alpha\,|T|, \tag{56.3}\]

donde \(R(T)\) es la impureza ponderada total de sus hojas (en la formulación original de Breiman et al. (1984), la tasa de error) y \(|T|\) su número de hojas. Con \(\alpha = 0\) gana el árbol completo; al crecer \(\alpha\), conviene ir cambiando subárboles por hojas. Un subárbol \(T_t\) deja de compensar justo cuando \(R(t) + \alpha = R(T_t) + \alpha|T_t|\), es decir, cuando \(\alpha = g(t)\).

Breiman et al. demostraron que los árboles óptimos para cada \(\alpha\) forman una secuencia anidada \(T_0 \supset T_1 \supset \cdots \supset \{\text{raíz}\}\), que se obtiene podando repetidamente el eslabón más débil. Los valores \(0 = \alpha_0 < \alpha_1 < \cdots\) en que cambia el árbol son la ruta de poda. Para elegir \(\alpha\) se usa validación cruzada: se evalúa cada \(\alpha\) de la ruta y se elige el de menor error (o el más grande dentro de un error estándar del mínimo).

56.3.4 Árboles de regresión

Con una respuesta numérica, la hoja predice el promedio de sus ejemplos y la impureza es la varianza (o la suma de cuadrados): CART elige el corte que minimiza \(\sum_{i \in t_L}(y_i - \bar{y}_L)^2 + \sum_{i \in t_R}(y_i - \bar{y}_R)^2\). Los árboles de regresión se desarrollan en el capítulo de ensambles, donde son la base del bagging y del boosting.

56.4 Laboratorio: CART en el plano

El laboratorio entrena CART con 60 puntos de dos clases y lo evalúa con 300 puntos de prueba generados por la misma regla: la clase 1 es probable en dos zonas rectangulares (por eso un árbol es el modelo natural) y con un 12 % de etiquetas invertidas al azar. Con \(\alpha = 0.02\) se obtiene el árbol de la Tabla 56.6. Cuando dos cortes producen exactamente la misma reducción de Gini, el laboratorio elige el primero en un orden fijo, mientras que scikit-learn decide al azar; por eso el árbol completo puede diferir en algún corte profundo (exactitud en prueba 0.723 frente a 0.717), aunque los árboles podados coinciden.

Laboratorio · CART

¿Cuánto hay que podar?

Las regiones sombreadas son las hojas del árbol. Limita su crecimiento con la profundidad o el mínimo por hoja, o pódalo con α. Observa la ruta de poda y la exactitud en prueba.

Mostrar
Hojas
Exactitud entrenamiento
Exactitud prueba
Primer corte

Regiones del árbol

clase 1clase 0mal clasificadozonas reales

Ruta de poda

entrenamientopruebahojas (eje derecho)α actual

Búsqueda del primer corte

cortes en x₁cortes en x₂elegido

Nodos internos y su costo por hoja g(t)

Guía del laboratorio.

  1. Sin restricciones, cuenta las hojas y localiza las que rodean a un solo punto. ¿Qué exactitud tienen en prueba?
  2. En el panel de búsqueda del primer corte, comprueba que el máximo de la curva roja está en \(x_2 = 5.70\). ¿Cuál es el mejor corte en \(x_1\) y por qué pierde?
  3. Predice antes de mover: ¿con qué α aparece el árbol de cuatro hojas? Compruébalo en la ruta de poda y verifica la Tabla 56.6 en la tabla de nodos.
  4. Sube α poco a poco desde 0.02 hasta 0.09. ¿Por qué el árbol no cambia en todo ese intervalo y luego salta a una sola hoja?
  5. Con α = 0, usa solo el mínimo por hoja (por ejemplo 5) o la profundidad máxima (2). ¿Llegas a un árbol parecido al podado? ¿Qué ventaja tiene la poda sobre la pre-poda?
  6. Cambia a Prueba y compara las regiones con los rectángulos verdes (las zonas reales). ¿Qué parte de la estructura recuperó el árbol podado?

56.5 Implementación en Python

56.5.1 El ejemplo categórico

Las funciones siguientes enumeran todas las preguntas binarias de cada atributo y reproducen las Tabla 56.3 y Tabla 56.4.

Mostrar código 
import numpy as np
import pandas as pd
from itertools import combinations

laptop = pd.DataFrame({
    "edad": ["joven", "joven", "adulto", "mayor", "mayor", "mayor", "adulto", "joven", "joven", "mayor", "joven", "adulto", "adulto", "mayor"],
    "ingreso": ["alto", "alto", "alto", "medio", "bajo", "bajo", "bajo", "medio", "bajo", "medio", "medio", "medio", "alto", "medio"],
    "estudiante": ["no", "no", "no", "no", "sí", "sí", "sí", "no", "sí", "sí", "sí", "no", "sí", "no"],
    "crédito": ["favorable", "excelente", "favorable", "favorable", "favorable", "excelente", "excelente", "favorable", "favorable", "favorable", "excelente", "excelente", "favorable", "excelente"],
    "compra": ["no", "no", "sí", "sí", "sí", "no", "sí", "no", "sí", "sí", "sí", "sí", "sí", "no"],
}, index=range(1, 15))

def gini(etiquetas):
    p = pd.Series(etiquetas).value_counts(normalize=True)
    return float(1 - (p ** 2).sum())

def preguntas_binarias(valores):
    """Todos los subconjuntos S con S y su complemento contados una sola vez."""
    valores = sorted(valores)
    vistos, salida = set(), []
    for r in range(1, len(valores)):
        for S in combinations(valores, r):
            clave = frozenset([frozenset(S), frozenset(valores) - frozenset(S)])
            if clave not in vistos:
                vistos.add(clave)
                salida.append(set(S))
    return salida

def evaluar(datos, atributo, objetivo="compra"):
    filas, g0, n = [], gini(datos[objetivo]), len(datos)
    for S in preguntas_binarias(datos[atributo].unique()):
        m = datos[atributo].isin(S)
        gp = m.sum() / n * gini(datos.loc[m, objetivo]) + (~m).sum() / n * gini(datos.loc[~m, objetivo])
        filas.append({"atributo": atributo, "pregunta": f"¿{atributo} ∈ {sorted(S)}?", "gini ponderado": gp, "reducción": g0 - gp})
    return pd.DataFrame(filas)

print(f"Gini en la raíz: {gini(laptop['compra']):.3f}")
todas = pd.concat([evaluar(laptop, a) for a in ["edad", "ingreso", "estudiante", "crédito"]])
todas.sort_values("reducción", ascending=False).round(3).head(8)
Gini en la raíz: 0.459
atributo pregunta gini ponderado reducción
0 edad ¿edad ∈ ['adulto']? 0.357 0.102
0 estudiante ¿estudiante ∈ ['no']? 0.367 0.092
1 edad ¿edad ∈ ['joven']? 0.394 0.066
0 crédito ¿crédito ∈ ['excelente']? 0.429 0.031
0 ingreso ¿ingreso ∈ ['alto']? 0.443 0.016
1 ingreso ¿ingreso ∈ ['bajo']? 0.450 0.009
2 edad ¿edad ∈ ['mayor']? 0.457 0.002
2 ingreso ¿ingreso ∈ ['medio']? 0.458 0.001

DecisionTreeClassifier no acepta categorías directamente: hay que codificarlas. Con one-hot, cada pregunta es «¿categoría = valor?», que en este ejemplo basta para encontrar la misma raíz:

Mostrar código 
from sklearn.tree import DecisionTreeClassifier, export_text

X_oh = pd.get_dummies(laptop.drop(columns="compra"), prefix_sep="=").astype(int)
arbol = DecisionTreeClassifier(criterion="gini", random_state=0).fit(X_oh, laptop["compra"])
print(export_text(arbol, feature_names=list(X_oh.columns)))
|--- edad=adulto <= 0.50
|   |--- estudiante=sí <= 0.50
|   |   |--- edad=joven <= 0.50
|   |   |   |--- crédito=excelente <= 0.50
|   |   |   |   |--- class: sí
|   |   |   |--- crédito=excelente >  0.50
|   |   |   |   |--- class: no
|   |   |--- edad=joven >  0.50
|   |   |   |--- class: no
|   |--- estudiante=sí >  0.50
|   |   |--- crédito=favorable <= 0.50
|   |   |   |--- ingreso=bajo <= 0.50
|   |   |   |   |--- class: sí
|   |   |   |--- ingreso=bajo >  0.50
|   |   |   |   |--- class: no
|   |   |--- crédito=favorable >  0.50
|   |   |   |--- class: sí
|--- edad=adulto >  0.50
|   |--- class: sí

56.5.2 El ejemplo numérico y la ruta de poda

Generamos los mismos datos del laboratorio: dos zonas rectangulares donde la clase 1 tiene probabilidad 0.88 y, fuera de ellas, 0.12.

Mostrar código 
def zonas(X):
    return ((X[:, 0] > 4) & (X[:, 1] < 6)) | ((X[:, 0] < 2.5) & (X[:, 1] > 7))

def generar(n, semilla):
    rng = np.random.default_rng(semilla)
    X = rng.uniform(0, 10, size=(n, 2)).round(1)
    y = (rng.uniform(size=n) < np.where(zonas(X), 0.88, 0.12)).astype(int)
    return X, y

X_tr, y_tr = generar(60, 7)
X_te, y_te = generar(300, 6)

completo = DecisionTreeClassifier(random_state=0).fit(X_tr, y_tr)
print(f"Árbol completo: {completo.get_n_leaves()} hojas, entrenamiento {completo.score(X_tr, y_tr):.3f}, prueba {completo.score(X_te, y_te):.3f}")

ruta = completo.cost_complexity_pruning_path(X_tr, y_tr)
filas = []
for a in ruta.ccp_alphas:
    m = DecisionTreeClassifier(random_state=0, ccp_alpha=a).fit(X_tr, y_tr)
    filas.append({"α": a, "hojas": m.get_n_leaves(), "entrenamiento": m.score(X_tr, y_tr), "prueba": m.score(X_te, y_te)})
pd.DataFrame(filas).round(4)
Árbol completo: 18 hojas, entrenamiento 1.000, prueba 0.717
α hojas entrenamiento prueba
0 0.0000 18 1.0000 0.7167
1 0.0141 14 0.9667 0.7433
2 0.0148 12 0.9500 0.7567
3 0.0152 10 0.9333 0.7733
4 0.0172 7 0.9000 0.8433
5 0.0188 4 0.8667 0.8533
6 0.0902 1 0.5500 0.5433

El árbol de cuatro hojas y el costo por hoja de sus nodos internos (Tabla 56.6) se obtienen de la estructura interna tree_:

Mostrar código 
podado = DecisionTreeClassifier(random_state=0, ccp_alpha=0.02).fit(X_tr, y_tr)
print(export_text(podado, feature_names=["x1", "x2"], show_weights=True))

t, n = podado.tree_, podado.tree_.n_node_samples[0]
def hojas(i):
    return [i] if t.children_left[i] == -1 else hojas(t.children_left[i]) + hojas(t.children_right[i])
R = lambda i: t.n_node_samples[i] / n * t.impurity[i]
filas = []
for i in range(t.node_count):
    if t.children_left[i] != -1:
        h = hojas(i)
        filas.append({"nodo": i, "pregunta": f"x{t.feature[i] + 1} <= {t.threshold[i]:.2f}", "G": t.impurity[i],
                      "R(t)": R(i), "R(T_t)": sum(R(j) for j in h), "hojas": len(h),
                      "g(t)": (R(i) - sum(R(j) for j in h)) / (len(h) - 1)})
pd.DataFrame(filas).round(4)
|--- x2 <= 5.70
|   |--- x1 <= 4.05
|   |   |--- weights: [11.00, 2.00] class: 0
|   |--- x1 >  4.05
|   |   |--- weights: [4.00, 17.00] class: 1
|--- x2 >  5.70
|   |--- x1 <= 2.30
|   |   |--- weights: [0.00, 6.00] class: 1
|   |--- x1 >  2.30
|   |   |--- weights: [18.00, 2.00] class: 0
nodo pregunta G R(t) R(T_t) hojas g(t)
0 0 x2 <= 5.70 0.4950 0.4950 0.2243 4 0.0902
1 1 x1 <= 4.05 0.4931 0.2794 0.1643 2 0.1151
2 4 x1 <= 2.30 0.4260 0.1846 0.0600 2 0.1246

56.5.3 Elegir α con validación cruzada

En la práctica no hay un conjunto de prueba grande para elegir α: se usa validación cruzada sobre el entrenamiento con los valores de la ruta.

Mostrar código 
import plotly.graph_objects as go
from sklearn.model_selection import RepeatedStratifiedKFold, cross_val_score

cv = RepeatedStratifiedKFold(n_splits=10, n_repeats=5, random_state=0)
alfas = ruta.ccp_alphas[:-1]                      # el último deja solo la raíz
cv_media = [cross_val_score(DecisionTreeClassifier(random_state=0, ccp_alpha=a), X_tr, y_tr, cv=cv).mean() for a in alfas]
tabla = pd.DataFrame([
    {"α": a,
     "entrenamiento": DecisionTreeClassifier(random_state=0, ccp_alpha=a).fit(X_tr, y_tr).score(X_tr, y_tr),
     "validación cruzada": c,
     "prueba": DecisionTreeClassifier(random_state=0, ccp_alpha=a).fit(X_tr, y_tr).score(X_te, y_te)}
    for a, c in zip(alfas, cv_media)])
fig = go.Figure()
for col, color in [("entrenamiento", "#2563eb"), ("validación cruzada", "#ea580c"), ("prueba", "#7c3aed")]:
    fig.add_trace(go.Scatter(x=tabla["α"], y=tabla[col], mode="lines+markers", name=col, line=dict(color=color, shape="hv")))
fig.update_layout(xaxis_title="α", yaxis_title="exactitud", height=360, margin=dict(l=10, r=10, t=20, b=40))
fig.show()
mejor = tabla.loc[tabla["validación cruzada"].idxmax()]
print(f"α elegido por validación cruzada: {mejor['α']:.4f} → prueba {mejor['prueba']:.3f}")
Figura 56.1: Exactitud de entrenamiento, de validación cruzada (10 pliegues estratificados, repetida 5 veces) y de prueba a lo largo de la ruta de poda. La validación cruzada favorece árboles pequeños; el árbol completo (α = 0) es el peor en prueba. 
α elegido por validación cruzada: 0.0188 → prueba 0.853

56.5.4 Importancia de las variables

Mostrar código 
pd.DataFrame({"árbol completo": completo.feature_importances_, "árbol podado": podado.feature_importances_},
             index=["x1", "x2"]).round(3)
árbol completo árbol podado
x1 0.693 0.886
x2 0.307 0.114

En el árbol podado, \(x_1\) acumula casi el 90 % de la importancia aunque la primera pregunta sea sobre \(x_2\): ese primer corte reduce poco la impureza ponderada (\(0.495 - 0.279 - 0.185 = 0.031\)), porque solo separa las dos mitades del plano, y son los dos cortes en \(x_1\) los que aíslan las zonas (0.115 y 0.125). La importancia mide cuánto contribuye cada variable, no qué pregunta va primero.

56.6 Complejidad, ventajas y limitaciones

Con \(p\) variables numéricas ordenadas una vez al inicio, encontrar el mejor corte de un nodo con \(n_t\) ejemplos cuesta \(O(p\, n_t)\); como cada nivel reparte los \(n\) ejemplos, el árbol cuesta \(O(p\, n \log n)\) si está balanceado (profundidad \(\approx \log n\)) y hasta \(O(p\, n^2)\) en el peor caso. La ruta de poda se calcula después en tiempo proporcional al número de nodos.

Ventajas. Las del capítulo anterior (interpretabilidad, variables mixtas, sin escalamiento, interacciones automáticas), más un tratamiento uniforme de variables numéricas y categóricas, la poda con fundamento estadístico y la extensión directa a regresión.

Limitaciones.

  • Alta varianza: pequeños cambios en los datos cambian los cortes de arriba y, con ellos, todo el árbol. Es el problema que resuelven los bosques aleatorios.
  • Fronteras en escalones paralelos a los ejes: una frontera diagonal se aproxima con muchos cortes.
  • Las categorías con muchos niveles generan muchas preguntas posibles y favorecen el sobreajuste; conviene agruparlas o usar codificaciones por frecuencia u objetivo.
  • La importancia MDI está sesgada; para interpretar conviene usar permutación o SHAP.

56.7 Resumen

  • CART construye árboles binarios: preguntas «¿\(A \in S\)?» para categorías y «¿\(x \le t\)?» para números, elegidas por la mayor reducción del índice de Gini.
  • Un atributo categórico con \(m\) valores admite \(2^{m-1} - 1\) preguntas; para dos clases basta ordenar las categorías por su proporción de positivos y probar \(m - 1\) cortes.
  • En el plano, un árbol es una partición en rectángulos. Crecido hasta hojas puras, rodea el ruido.
  • La poda de costo-complejidad minimiza \(R(T) + \alpha|T|\); el eslabón más débil, \(\min_t g(t)\), define la ruta de poda, una secuencia anidada de árboles. \(\alpha\) se elige con validación cruzada.
  • La importancia por disminución de impureza es un subproducto útil pero sesgado.

Referencias