55  Árboles de decisión: ID3 y C4.5

Un árbol de decisión clasifica haciendo preguntas, una tras otra: «¿cómo está el cielo?», «si está soleado, ¿la humedad es alta?». Cada respuesta lleva a otra pregunta o a una conclusión. Es la forma en que un médico sigue un protocolo de diagnóstico o un analista de crédito revisa una solicitud, y por eso los árboles son el clasificador más fácil de explicar a quien no es especialista.

La pregunta técnica es qué preguntar y en qué orden. Este capítulo la responde con la idea de impureza de la teoría de la información (Shannon 1948) y con los algoritmos clásicos que la usan: la estrategia recursiva de Hunt et al. (1966), ID3 (Quinlan 1986) y su sucesor C4.5 (Quinlan 1993). El capítulo siguiente estudia CART (Breiman et al. 1984), la variante binaria que implementa scikit-learn.

55.1 Intuición: ¿se juega el partido?

Durante quince días se registró el estado del tiempo y si se jugó un partido de béisbol.

Día	Pronóstico	Temperatura	Humedad	Viento	¿Juega?
D1	Soleado	Caluroso	Alta	Débil	No
D2	Soleado	Caluroso	Alta	Fuerte	No
D3	Nublado	Caluroso	Alta	Débil	Sí
D4	Lluvia	Templado	Alta	Débil	Sí
D5	Lluvia	Fresco	Normal	Débil	Sí
D6	Lluvia	Fresco	Normal	Fuerte	No
D7	Nublado	Fresco	Normal	Fuerte	Sí
D8	Soleado	Templado	Alta	Débil	No
D9	Soleado	Fresco	Normal	Débil	Sí
D10	Lluvia	Templado	Normal	Débil	Sí
D11	Soleado	Templado	Normal	Débil	Sí
D12	Nublado	Templado	Alta	Fuerte	Sí
D13	Nublado	Caluroso	Normal	Débil	Sí
D14	Lluvia	Templado	Alta	Fuerte	No
D15	Soleado	Fresco	Alta	Débil	No

Tabla 55.1: Quince días, 9 con partido y 6 sin partido.

Si solo pudiéramos hacer una pregunta, ¿cuál haríamos? Preguntar por el pronóstico tiene una ventaja visible: los cuatro días nublados se jugó, así que esa respuesta resuelve el caso de inmediato. Preguntar por la temperatura, en cambio, deja grupos tan mezclados como al principio. Una buena pregunta es la que deja grupos puros, con una sola clase. Necesitamos una medida de qué tan mezclado está un grupo.

55.2 Construcción paso a paso

55.2.1 Paso 1. Medir la mezcla: la entropía

La entropía de un conjunto \(S\) con proporciones de clase \(p_1, \ldots, p_K\) es

\[ H(S) = -\sum_{k=1}^{K} p_k \log_2 p_k, \tag{55.1}\]

con la convención \(0 \log_2 0 = 0\). Vale 0 si el grupo es puro y es máxima cuando las clases están igualmente repartidas (1 bit en el caso binario)¹. Para los quince días, con 9 «Sí» y 6 «No»:

¹ Un bit es la información necesaria para resolver una pregunta de sí o no con dos respuestas igualmente probables. Si el grupo tiene 50 % de cada clase, adivinar la clase de un ejemplo requiere un bit completo; si es puro, no requiere ninguno.

\[ H(S) = -\tfrac{9}{15}\log_2\tfrac{9}{15} - \tfrac{6}{15}\log_2\tfrac{6}{15} = 0.6 \cdot 0.737 + 0.4 \cdot 1.322 \approx 0.971. \]

55.2.2 Paso 2. La ganancia de cada pregunta

Preguntar por el pronóstico divide los días en tres grupos:

Pronóstico	Días	Sí	No	Entropía del grupo
Soleado	6	2	4	\(-\frac{2}{6}\log_2\frac{2}{6} - \frac{4}{6}\log_2\frac{4}{6} = 0.918\)
Nublado	4	4	0	0
Lluvia	5	3	2	0.971

Tabla 55.2: Partición por pronóstico.

La entropía después de preguntar es el promedio de las entropías de los grupos, ponderado por su tamaño:

\[ \tfrac{6}{15}(0.918) + \tfrac{4}{15}(0) + \tfrac{5}{15}(0.971) = 0.367 + 0 + 0.324 = 0.691. \]

La ganancia de información es cuánto bajó la entropía: \(0.971 - 0.691 = 0.280\) bits. Repitiendo el cálculo para los cuatro atributos:

Atributo	Entropía después	Ganancia
Pronóstico	0.691	0.280
Humedad	0.785	0.186
Viento	0.911	0.060
Temperatura	0.958	0.013

Tabla 55.3: Ganancia de información de cada atributo en la raíz.

El pronóstico es la mejor primera pregunta, como sugería la intuición; la temperatura casi no informa.

55.2.3 Paso 3. Repetir en cada rama

La rama Nublado es pura: se convierte en una hoja «Sí». Las otras dos siguen mezcladas y repetimos el procedimiento solo con sus días, sin volver a usar el pronóstico:

Rama	\(H\) de la rama	Ganancia Humedad	Ganancia Viento	Ganancia Temperatura
Soleado (6 días: 2 Sí, 4 No)	0.918	0.918	0.109	0.252
Lluvia (5 días: 3 Sí, 2 No)	0.971	0.020	0.971	0.020

Tabla 55.4: Ganancias dentro de cada rama impura.

En la rama Soleado, la humedad separa perfectamente: con humedad alta los cuatro días fueron «No» y con humedad normal los dos fueron «Sí». En la rama Lluvia, el viento separa perfectamente: con viento débil, tres «Sí»; con viento fuerte, dos «No». Cuando la ganancia es igual a la entropía de la rama, los hijos son puros.

55.2.4 Paso 4. El árbol y sus reglas

flowchart TD
    A[Pronóstico] -->|Nublado| B["Sí (4/0)"]
    A -->|Soleado| C[Humedad]
    A -->|Lluvia| D[Viento]
    C -->|Alta| E["No (0/4)"]
    C -->|Normal| F["Sí (2/0)"]
    D -->|Débil| G["Sí (3/0)"]
    D -->|Fuerte| H["No (0/2)"]

Figura 55.1: Árbol construido por ID3 con los quince días. Entre paréntesis, días Sí/No que llegan a cada hoja.

Cada camino de la raíz a una hoja es una regla:

1. SI Pronóstico = Nublado ENTONCES Juega = Sí.
2. SI Pronóstico = Soleado Y Humedad = Alta ENTONCES Juega = No.
3. SI Pronóstico = Soleado Y Humedad = Normal ENTONCES Juega = Sí.
4. SI Pronóstico = Lluvia Y Viento = Débil ENTONCES Juega = Sí.
5. SI Pronóstico = Lluvia Y Viento = Fuerte ENTONCES Juega = No.

El árbol usa tres de los cuatro atributos (la temperatura nunca fue útil) y clasifica bien los quince días. Son, casi literalmente, las reglas que encontró el clasificador CBA del capítulo de clasificación asociativa sobre datos parecidos: dos caminos distintos hacia las mismas regularidades.

55.3 Formalización

55.3.1 El algoritmo de Hunt

Sea \(D_t\) el conjunto de ejemplos que llegan al nodo \(t\) y \(A\) el conjunto de atributos disponibles. El esquema recursivo de Hunt et al. (1966), del que ID3, C4.5 y CART son casos particulares, es:

1. Si todos los ejemplos de \(D_t\) tienen la misma clase \(c\), \(t\) es una hoja con clase \(c\).
2. Si \(A\) está vacío o se cumple un criterio de parada, \(t\) es una hoja con la clase mayoritaria de \(D_t\).
3. Si no, se elige la prueba que mejor separa las clases, se divide \(D_t\) según su resultado y se aplica el procedimiento a cada hijo.

Si un hijo queda vacío (o, al predecir, aparece un valor no visto en el entrenamiento), se usa la clase mayoritaria del padre. Es una estrategia voraz (greedy): elige la mejor pregunta local sin volver atrás, lo que la hace rápida pero no garantiza el árbol óptimo global, cuyo cálculo es NP-difícil.

55.3.2 Ganancia de información (ID3)

Para un atributo \(A\) con valores \(v \in \operatorname{Valores}(A)\) y \(S_v = \{x \in S : A(x) = v\}\),

\[ \operatorname{Gan}(S, A) = H(S) - \sum_{v \in \operatorname{Valores}(A)} \frac{|S_v|}{|S|} H(S_v). \tag{55.2}\]

El segundo término es la entropía condicional \(H(Y \mid A)\), la incertidumbre que queda sobre la clase cuando se conoce \(A\); la ganancia es la información mutua entre \(A\) y la clase². ID3 elige en cada nodo \(\arg\max_A \operatorname{Gan}(S, A)\) y crea una rama por cada valor del atributo (partición multivía).

² La información mutua \(I(A; Y) = H(Y) - H(Y \mid A)\) mide cuánto se reduce la incertidumbre sobre \(Y\) al conocer \(A\). Es simétrica y vale 0 solo si \(A\) y \(Y\) son independientes, la misma idea que mide la prueba \(\chi^2\) del capítulo de selección de variables.

55.3.3 Otras medidas de impureza

La entropía no es la única medida razonable. Para una proporción \(p\) de la clase positiva en un problema binario:

Medida	Fórmula	Máximo (\(p = 0.5\))
Entropía	\(-p\log_2 p - (1-p)\log_2(1-p)\)	1
Índice de Gini	\(1 - p^2 - (1-p)^2 = 2p(1-p)\)	0.5
Error de clasificación	\(1 - \max(p, 1-p)\)	0.5

Tabla 55.5: Medidas de impureza para dos clases.

Las tres valen 0 en nodos puros y son máximas con clases balanceadas. La entropía y Gini son estrictamente cóncavas, lo que hace que cualquier división que separe las proporciones produzca una ganancia positiva; el error de clasificación no lo es, y por eso puede no ver mejoras reales³. Gini es el criterio de CART y se estudia en el capítulo siguiente; en la práctica, entropía y Gini producen árboles muy parecidos.

³ Si un nodo con 40 % de positivos se divide en un hijo pequeño con 10 % de positivos (la séptima parte de los ejemplos) y otro con 45 %, ambos hijos siguen teniendo mayoría negativa y el error de clasificación sigue siendo 0.40, aunque el primer hijo es mucho más puro. La entropía y Gini, por ser estrictamente cóncavas, sí registran esa mejora.

55.4 El sesgo hacia atributos con muchos valores: C4.5

Agreguemos a la Tabla 55.1 la columna Día (D1, …, D15) como si fuera un atributo más. Al dividir por Día, cada grupo tiene un solo ejemplo, es puro, y la entropía después de dividir es 0. Su ganancia es la máxima posible, \(0.971\), muy por encima del pronóstico. ID3 elegiría como raíz un identificador que no sirve para predecir nada: un día nuevo tendrá un valor de Día nunca visto.

El problema es general: un atributo con muchos valores parte los datos en grupos pequeños que, por azar, tienden a ser puros. C4.5 corrige la ganancia dividiéndola entre la información de la partición, la entropía de los propios tamaños de los grupos:

\[ \operatorname{SplitInfo}(S, A) = -\sum_{v} \frac{|S_v|}{|S|}\log_2\frac{|S_v|}{|S|}, \qquad \operatorname{RazónGan}(S, A) = \frac{\operatorname{Gan}(S, A)}{\operatorname{SplitInfo}(S, A)}. \tag{55.3}\]

Un atributo que parte en muchos grupos pequeños tiene un \(\operatorname{SplitInfo}\) grande y queda penalizado. Para el pronóstico (grupos de 6, 4 y 5 días), \(\operatorname{SplitInfo} = 1.566\); para Día (15 grupos de 1), \(\log_2 15 = 3.907\):

Atributo	Ganancia	SplitInfo	Razón de ganancia
Día	0.971	3.907	0.249
Humedad	0.186	0.997	0.186
Pronóstico	0.280	1.566	0.179
Viento	0.060	0.918	0.065
Temperatura	0.013	1.566	0.008

Tabla 55.6: Ganancia y razón de ganancia en la raíz, con el atributo Día incluido.

Dos lecciones honestas salen de esta tabla:

1. La razón de ganancia atenúa el sesgo, pero no lo elimina. Con 15 ejemplos la penalización \(\log_2 15\) no alcanza y Día sigue ganando. Los identificadores, códigos postales finos o claves de producto deben excluirse antes de entrenar; ningún criterio de impureza los detecta por sí solo.
2. Criterios distintos eligen raíces distintas. Sin Día, la razón de ganancia prefiere la humedad (0.186) al pronóstico (0.179), porque la humedad parte en dos grupos y no en tres.

¿Cuál árbol es mejor? Lo decide la validación, no el criterio. Con validación cruzada dejando uno fuera sobre los quince días (calculada en la sección de Python), el árbol de ganancia de información acierta 14 de 15, el de razón de ganancia 12 y el de Gini 13; con Día incluido, cualquiera de ellos acierta solo 9, exactamente lo mismo que responder siempre la clase mayoritaria.

55.4.1 Atributos continuos

ID3 solo maneja atributos categóricos; C4.5 trata los numéricos con preguntas binarias «\(A \le t\)». Supongamos que la humedad se midió en porcentaje. Se ordenan los valores y se evalúan cortes en los puntos medios entre valores consecutivos:

Humedad (%)	65	70	70	70	75	80	80	85	86	88	90	90	91	95	96
Juega	Sí	No	Sí	Sí	Sí	Sí	Sí	No	Sí	No	No	Sí	No	No	Sí

Tabla 55.7: Humedad numérica ordenada.

Corte \(t\)	\(\le t\) (Sí/No)	\(> t\) (Sí/No)	Ganancia
77.5	4 / 1	5 / 5	0.064
82.5	6 / 1	3 / 5	0.186
85.5	6 / 2	3 / 4	0.078
87.0	7 / 2	2 / 4	0.145

Tabla 55.8: Ganancia de algunos cortes candidatos.

El mejor corte es 82.5 %. Con \(m\) valores distintos hay \(m - 1\) cortes posibles, pero Fayyad y Irani (1992) demostraron que el óptimo de la entropía siempre está en un punto frontera, entre dos valores consecutivos de clases distintas, así que basta evaluar esos. Tras ordenar una vez (\(O(n \log n)\)), todas las ganancias se calculan en una pasada actualizando conteos. A diferencia de un atributo categórico, un atributo numérico puede volver a usarse más abajo con otro corte.

55.4.2 Valores faltantes

C4.5 no descarta los ejemplos con un valor faltante en el atributo evaluado. Calcula la ganancia con los ejemplos que sí lo tienen y la multiplica por la fracción de ejemplos conocidos; al dividir, envía cada ejemplo con valor faltante a todas las ramas con un peso proporcional al tamaño de cada rama. Al predecir hace lo mismo y combina las distribuciones de las hojas alcanzadas. CART usa en cambio divisiones sustitutas (surrogate splits), y scikit-learn (desde la versión 1.3) aprende en cada corte hacia qué hijo enviar los faltantes.

55.4.3 Criterios de parada y poda

Un árbol que crece hasta que todas sus hojas son puras memoriza: con datos ruidosos termina creando una hoja para cada excepción, como el 1-NN del capítulo introductorio. Hay dos formas de controlarlo:

• Pre-poda: detener el crecimiento antes, con una profundidad máxima, un mínimo de ejemplos por hoja o por nodo a dividir, o una ganancia mínima. Es barata, pero miope: una división poco útil puede habilitar otra muy útil debajo (el caso del XOR).
• Post-poda: hacer crecer el árbol completo y después reemplazar subárboles por hojas cuando eso no empeora el error. La poda por error reducido lo decide con un conjunto de validación (Quinlan 1987); C4.5 usa una estimación pesimista del error de cada hoja (el extremo superior de un intervalo de confianza) para podar sin datos adicionales; CART usa la poda de costo-complejidad, que se desarrolla en el capítulo siguiente.

55.5 Laboratorio: construye el árbol

El laboratorio construye el árbol con los quince días de la Tabla 55.1 y el criterio elegido. Haz clic en cualquier nodo para ver los puntajes de cada atributo en ese nodo; la profundidad máxima permite recorrer la construcción nivel por nivel. El estado inicial reproduce la Tabla 55.3 y el árbol de la Figura 55.1.

Laboratorio · Árboles de decisión

¿Qué pregunta hacer primero?

Cambia el criterio, incluye el atributo Día y limita la profundidad. Haz clic en un nodo para inspeccionar sus puntajes.

Criterio

Atributo Día

Profundidad máxima:

Hojas

Exactitud en entrenamiento

Exactitud LOOCV

Referencia (siempre «Sí»)9/15

Árbol (Sí/No en cada nodo)

hoja «Sí»hoja «No»nodo de decisiónnodo seleccionado

Puntajes en el nodo

Reglas

Guía del laboratorio.

1. Con profundidad 1, comprueba la Tabla 55.3 en la tabla del nodo raíz. Después sube a 2 y haz clic en el nodo Humedad de la rama Soleado: ¿coinciden los puntajes con la Tabla 55.4?
2. Predice antes de mover: si cambias a Razón de ganancia, ¿qué atributo quedará en la raíz? Compruébalo y explica el papel de SplitInfo.
3. Incluye el atributo Día con cada uno de los tres criterios. ¿Alguno lo evita? ¿Qué le pasa a la exactitud de entrenamiento y a la de LOOCV?
4. Con Gini y sin Día, compara el árbol con el de ganancia de información. ¿Son iguales? ¿Por qué la LOOCV no es la misma si el árbol completo es igual?
5. Explica con la profundidad máxima qué es la pre-poda y qué se pierde con profundidad 1.

55.6 Implementación en Python

55.6.1 Entropía, ganancia y razón de ganancia

Las funciones siguientes reproducen las tablas de la sección anterior.

import numpy as np
import pandas as pd

dias = pd.DataFrame({
    "Pronóstico": ["Soleado", "Soleado", "Nublado", "Lluvia", "Lluvia", "Lluvia", "Nublado", "Soleado",
                   "Soleado", "Lluvia", "Soleado", "Nublado", "Nublado", "Lluvia", "Soleado"],
    "Temperatura": ["Caluroso", "Caluroso", "Caluroso", "Templado", "Fresco", "Fresco", "Fresco", "Templado",
                    "Fresco", "Templado", "Templado", "Templado", "Caluroso", "Templado", "Fresco"],
    "Humedad": ["Alta", "Alta", "Alta", "Alta", "Normal", "Normal", "Normal", "Alta",
                "Normal", "Normal", "Normal", "Alta", "Normal", "Alta", "Alta"],
    "Viento": ["Débil", "Fuerte", "Débil", "Débil", "Débil", "Fuerte", "Fuerte", "Débil",
               "Débil", "Débil", "Débil", "Fuerte", "Débil", "Fuerte", "Débil"],
    "Juega": ["No", "No", "Sí", "Sí", "Sí", "No", "Sí", "No", "Sí", "Sí", "Sí", "Sí", "Sí", "No", "No"],
}, index=[f"D{i}" for i in range(1, 16)])

def entropia(etiquetas):
    p = pd.Series(etiquetas).value_counts(normalize=True)
    return float(-(p * np.log2(p)).sum())

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

def puntajes(datos, atributo, objetivo="Juega"):
    n = len(datos)
    grupos = [g[objetivo] for _, g in datos.groupby(atributo)]
    ganancia = entropia(datos[objetivo]) - sum(len(g) / n * entropia(g) for g in grupos)
    split_info = entropia(datos[atributo])
    return {"ganancia": ganancia, "split_info": split_info,
            "razón": ganancia / split_info if split_info > 0 else 0.0,
            "Δ gini": gini(datos[objetivo]) - sum(len(g) / n * gini(g) for g in grupos)}

print(f"H(S) = {entropia(dias['Juega']):.3f}")
con_dia = dias.assign(Día=dias.index)
pd.DataFrame({a: puntajes(con_dia, a) for a in ["Día", "Pronóstico", "Temperatura", "Humedad", "Viento"]}).T.round(3)

H(S) = 0.971

	ganancia	split_info	razón	Δ gini
Día	0.971	3.907	0.249	0.480
Pronóstico	0.280	1.566	0.179	0.142
Temperatura	0.013	1.566	0.009	0.009
Humedad	0.186	0.997	0.186	0.116
Viento	0.060	0.918	0.065	0.040

Las ganancias dentro de las ramas Soleado y Lluvia (Tabla 55.4):

pd.DataFrame({rama: {a: puntajes(dias[dias["Pronóstico"] == rama], a)["ganancia"]
                     for a in ["Humedad", "Viento", "Temperatura"]}
              for rama in ["Soleado", "Lluvia"]}).T.round(3)

	Humedad	Viento	Temperatura
Soleado	0.918	0.109	0.252
Lluvia	0.020	0.971	0.020

55.6.2 ID3 desde cero

La implementación recursiva sigue el algoritmo de Hunt. El árbol se representa con diccionarios; cada nodo interno guarda su clase mayoritaria para responder ante valores no vistos.

from collections import Counter

def mayoritaria(etiquetas):
    conteo = Counter(etiquetas)
    maximo = max(conteo.values())
    return sorted(c for c, v in conteo.items() if v == maximo)[0]

def id3(datos, atributos, criterio="ganancia", objetivo="Juega", prof=0, prof_max=10):
    y = list(datos[objetivo])
    if len(set(y)) == 1 or not atributos or prof == prof_max:
        return mayoritaria(y)                                         # hoja
    mejor = max(atributos, key=lambda a: (round(puntajes(datos, a, objetivo)[criterio], 12), -atributos.index(a)))
    resto = [a for a in atributos if a != mejor]
    return {"atributo": mejor, "mayoritaria": mayoritaria(y),
            "hijos": {v: id3(g, resto, criterio, objetivo, prof + 1, prof_max) for v, g in datos.groupby(mejor)}}

def predecir(arbol, fila):
    while isinstance(arbol, dict):
        arbol = arbol["hijos"].get(fila[arbol["atributo"]], arbol["mayoritaria"])
    return arbol

def reglas(arbol, condiciones=()):
    if not isinstance(arbol, dict):
        yield " ∧ ".join(condiciones) or "(siempre)", arbol
        return
    for valor, hijo in arbol["hijos"].items():
        yield from reglas(hijo, condiciones + (f"{arbol['atributo']} = {valor}",))

base = ["Pronóstico", "Temperatura", "Humedad", "Viento"]
arbol = id3(dias, base)
for condicion, clase in reglas(arbol):
    print(f"SI {condicion}  ⇒  {clase}")

SI Pronóstico = Lluvia ∧ Viento = Débil  ⇒  Sí
SI Pronóstico = Lluvia ∧ Viento = Fuerte  ⇒  No
SI Pronóstico = Nublado  ⇒  Sí
SI Pronóstico = Soleado ∧ Humedad = Alta  ⇒  No
SI Pronóstico = Soleado ∧ Humedad = Normal  ⇒  Sí

La validación dejando uno fuera compara criterios y muestra el efecto del atributo Día:

def loocv(datos, atributos, criterio):
    return sum(predecir(id3(datos.drop(i), atributos, criterio), datos.loc[i]) == datos.loc[i, "Juega"]
               for i in datos.index)

filas = []
for criterio in ["ganancia", "razón", "Δ gini"]:
    for nombre, attrs, d in [("sin Día", base, dias), ("con Día", ["Día"] + base, con_dia)]:
        a = id3(d, attrs, criterio)
        filas.append({"criterio": criterio, "atributos": nombre, "raíz": a["atributo"],
                      "entrenamiento": sum(predecir(a, f) == f["Juega"] for _, f in d.iterrows()),
                      "LOOCV": loocv(d, attrs, criterio)})
pd.DataFrame(filas)

	criterio	atributos	raíz	entrenamiento	LOOCV
0	ganancia	sin Día	Pronóstico	15	14
1	ganancia	con Día	Día	15	9
2	razón	sin Día	Humedad	15	12
3	razón	con Día	Día	15	9
4	Δ gini	sin Día	Pronóstico	15	13
5	Δ gini	con Día	Día	15	9

55.6.3 Atributos continuos

humedad_pct = pd.Series([85, 90, 86, 96, 80, 70, 65, 95, 70, 80, 70, 90, 75, 91, 88], index=dias.index)

def mejor_corte(x, y):
    orden = np.argsort(x.values, kind="stable")
    xs, ys = x.values[orden], y.values[orden]
    candidatos = []
    for i in range(len(xs) - 1):
        if xs[i] != xs[i + 1]:
            t = (xs[i] + xs[i + 1]) / 2
            izq, der = ys[xs <= t], ys[xs > t]
            g = entropia(ys) - len(izq) / len(ys) * entropia(izq) - len(der) / len(ys) * entropia(der)
            candidatos.append({"corte": t, "ganancia": round(g, 3), "frontera": ys[i] != ys[i + 1]})
    return pd.DataFrame(candidatos)

cortes = mejor_corte(humedad_pct, dias["Juega"])
print(cortes.loc[cortes["ganancia"].idxmax()].to_dict())
cortes.sort_values("ganancia", ascending=False).head(5)

{'corte': 82.5, 'ganancia': 0.186, 'frontera': True}

	corte	ganancia	frontera
3	82.5	0.186	True
5	87.0	0.145	True
4	85.5	0.078	True
2	77.5	0.064	False
6	89.0	0.060	False

55.6.4 Árboles con scikit-learn

DecisionTreeClassifier implementa CART: con criterion="entropy" usa la entropía, pero siempre hace divisiones binarias. Con variables categóricas codificadas one-hot, cada pregunta es del tipo «¿Pronóstico = Nublado?», de modo que el árbol puede tener una forma distinta aunque represente reglas equivalentes.

import matplotlib.pyplot as plt
from sklearn.tree import DecisionTreeClassifier, plot_tree, export_text

X_oh = pd.get_dummies(dias.drop(columns="Juega"), prefix_sep="=").astype(int)
clf = DecisionTreeClassifier(criterion="entropy", random_state=0).fit(X_oh, dias["Juega"])
print(export_text(clf, feature_names=list(X_oh.columns)))

fig, ax = plt.subplots(figsize=(11, 5.5))
plot_tree(clf, feature_names=list(X_oh.columns), class_names=list(clf.classes_), filled=True, rounded=True,
          impurity=True, ax=ax, fontsize=9)
plt.show()

|--- Pronóstico=Nublado <= 0.50
|   |--- Humedad=Alta <= 0.50
|   |   |--- Viento=Fuerte <= 0.50
|   |   |   |--- class: Sí
|   |   |--- Viento=Fuerte >  0.50
|   |   |   |--- class: No
|   |--- Humedad=Alta >  0.50
|   |   |--- Pronóstico=Soleado <= 0.50
|   |   |   |--- Viento=Débil <= 0.50
|   |   |   |   |--- class: No
|   |   |   |--- Viento=Débil >  0.50
|   |   |   |   |--- class: Sí
|   |   |--- Pronóstico=Soleado >  0.50
|   |   |   |--- class: No
|--- Pronóstico=Nublado >  0.50
|   |--- class: Sí

Figura 55.2: Árbol de scikit-learn con criterio de entropía sobre las variables codificadas one-hot. Las divisiones son binarias y el árbol tiene otra forma que el de ID3, aunque también clasifica bien los quince días.

55.7 Complejidad, ventajas y limitaciones

En cada nodo, evaluar un atributo categórico cuesta \(O(n_t)\) con \(n_t\) ejemplos en el nodo; un atributo numérico, \(O(n_t \log n_t)\) por el ordenamiento (o \(O(n_t)\) si se ordena una sola vez al inicio). Como cada nivel del árbol reparte los \(n\) ejemplos entre sus nodos, construir un árbol de profundidad \(d\) con \(p\) atributos cuesta del orden de \(O(p\, n\, d)\), y predecir cuesta \(O(d)\): recorrer un camino.

Ventajas.

• Se leen como reglas y se explican sin matemáticas.
• Aceptan variables categóricas y numéricas, no necesitan escalamiento y son invariantes ante transformaciones monótonas de las variables.
• Seleccionan variables automáticamente y capturan interacciones (la humedad importa solo si está soleado).
• Predicen muy rápido.

Limitaciones.

• Inestabilidad: un cambio pequeño en los datos puede cambiar la raíz y, con ella, todo el árbol. Es alta varianza, la misma que los métodos de ensamble aprovecharán para promediar.
• Sin poda, sobreajustan.
• Las fronteras son escalones paralelos a los ejes: una frontera diagonal requiere muchos escalones.
• La búsqueda voraz no ve interacciones que no se anuncian con una ganancia individual (el XOR).
• El sesgo hacia atributos con muchos valores obliga a revisar las variables de entrada.

55.8 Resumen

• Un árbol de decisión parte los datos con preguntas sucesivas hasta llegar a grupos casi puros; se construye de forma voraz y recursiva (algoritmo de Hunt).
• ID3 mide la mezcla con la entropía y elige la pregunta de mayor ganancia de información, la información mutua entre el atributo y la clase.
• La ganancia favorece atributos con muchos valores; C4.5 la divide entre la información de la partición (razón de ganancia), lo que atenúa pero no elimina el problema. Los identificadores deben excluirse.
• C4.5 maneja atributos continuos con cortes binarios (basta evaluar los puntos frontera), valores faltantes con pesos fraccionarios y poda pesimista.
• Un árbol completo memoriza; la pre-poda y la post-poda controlan su complejidad, y la validación decide entre criterios y tamaños.

Referencias

Breiman, Leo, Jerome H. Friedman, Richard A. Olshen, y Charles J. Stone. 1984. Classification and Regression Trees. Wadsworth International Group.

Fayyad, Usama M., y Keki B. Irani. 1992. «On the Handling of Continuous-Valued Attributes in Decision Tree Generation». Machine Learning 8 (1): 87-102. https://doi.org/10.1007/BF00994007.

Hunt, Earl B., Janet Marin, y Philip J. Stone. 1966. Experiments in Induction. Academic Press.

Quinlan, J. Ross. 1986. «Induction of Decision Trees». Machine Learning 1 (1): 81-106. https://doi.org/10.1007/BF00116251.

Quinlan, J. Ross. 1987. «Simplifying Decision Trees». International Journal of Man-Machine Studies 27 (3): 221-34. https://doi.org/10.1016/S0020-7373(87)80053-6.

Quinlan, J. Ross. 1993. C4.5: Programs for Machine Learning. Morgan Kaufmann.

Shannon, Claude E. 1948. «A Mathematical Theory of Communication». The Bell System Technical Journal 27 (3): 379-423. https://doi.org/10.1002/j.1538-7305.1948.tb01338.x.