Impureza y ganancia de información

💡En simple: lee esto primero

Un árbol de decisión hace preguntas de sí/no sobre los datos, una tras otra, como el juego de «adivina quién».

Imagínalo así

«¿Tiene más de 30 años? → sí. ¿Gana más de 2000? → no. Entonces: no le damos el préstamo.» Cada pregunta busca dejar los grupos lo más «puros» posible (todos de la misma clase).

Lo que tienes que llevarte

• Un grupo es puro si todos sus ejemplos son de la misma clase; impuro si está mezclado.
• Gini y entropía son dos formas de medir qué tan mezclado está un grupo.
• La mejor pregunta es la que más reduce la mezcla: eso es la ganancia de información.

Palabras raras de esta página

nodo / hoja

nodo = una pregunta; hoja = el final del camino, donde se da la respuesta.

split

dividir un grupo en dos según una pregunta.

impureza

qué tan mezclado está un grupo.

entropía

medida de «desorden» o sorpresa: 0 si todo es igual, máxima si está 50/50.

Más abajo viene la versión completa, con fórmulas. Si una palabra aparece subrayada con puntos, pasa el mouse (o tócala) para ver qué significa.

Un modelo que se puede leer en voz alta

Las sesiones 02–07 ajustaron pesos a un score lineal (quizás kernelizado) $f(\mathbf{x})=\mathbf{w}^\top\phi(\mathbf{x})+b$; solo cambiaban la pérdida y el regularizador. Hoy cambia la familia de modelos: sin productos punto, sin gradientes, sin distancias y sin escalar features. Un árbol hace una secuencia de preguntas sí/no y predice una constante al final de cada camino. Es el modelo más interpretable del curso y el ladrillo de los random forests y el boosting.

Término	Significado
Raíz / nodo interno / hoja	la primera pregunta / una pregunta / una región final
Split $(j,t)$	test «$x_j\le t$?» que parte un nodo en dos
Impureza	qué tan mezcladas están las etiquetas (puro = una clase)
Ganancia de información	cuánto baja la impureza con un split (se maximiza)
Profundidad / nº de hojas $\lvert T\rvert$	el tamaño del árbol: su complejidad
Poda	recortar un árbol crecido para no sobreajustar

El modelo: constante a trozos sobre cajas

$$\hat f(\mathbf{x}) = \sum_{m\in\text{hojas}} c_m\,\mathbf{1}\{\mathbf{x}\in B_m\}$$

Un camino raíz→hoja es un AND de desigualdades; cada desigualdad es un semiplano y su intersección es una caja alineada a los ejes. Quedan dos preguntas: ¿qué constante $c_m$? (fácil) y ¿qué cajas $B_m$? (el trabajo real).

El ejemplo que llevaremos toda la lección

Diez puntos, dos features, cinco por clase. Clase 0: (1,4), (2,1), (3,9), (6,5), (8,3). Clase 1: (4,8), (5,10), (7,2), (9,6), (10,7). Ninguna recta logra más de 9/10; cuatro cajas logran 10/10:

[n₀, n₁] son los conteos por clase. Cada camino raíz→hoja es un AND de desigualdades, es decir, una caja alineada a los ejes. 10/10 correctos con 4 cajas, cuando ninguna recta consigue más de 9/10.

¿Qué constante predice una hoja?

Una hoja solo ve sus propios puntos: ¿qué constante $c$ minimiza $\sum_i\ell(y_i,c)$? Depende de la pérdida:

Pérdida	Mejor constante	Costo mínimo =
0/1	la clase mayoritaria	error $1-\max_k\hat p_k$
cuadrática	la media $\bar y_m$ ($J'(c) = -2\sum(y_i-c)=0$)	suma de cuadrados dentro del nodo
log-loss (prob.)	la frecuencia observada $\hat p$	entropía
Brier (cuadrática sobre prob.)	la frecuencia $\hat p$	Gini
absoluta	la mediana	—

Todo lo que un nodo sabe es su vector de conteos: raíz $[5,5]\Rightarrow\hat p=(0.5,0.5)$; nodo B $[2,5]\Rightarrow\hat p=(2/7,5/7)$. El árbol nunca mira dónde están los puntos dentro de la caja.

La idea clave

La impureza es «el costo de la mejor constante». No es una fórmula arbitraria: la entropía es la log-loss mínima de la hoja y el Gini su error cuadrático mínimo.

Tres medidas de impureza

$$\text{error} = 1-\max_k\hat p_k,\qquad \text{Gini} = 1-\sum_k\hat p_k^2,\qquad H = -\sum_k\hat p_k\log_2\hat p_k$$

Entropía = sorpresa promedio. ¿Qué tan sorprendente es un evento de probabilidad $p$? Queremos $s(1)=0$, $s$ decreciente, y que la sorpresa de eventos independientes se sume: $s(pq)=s(p)+s(q)$. La única solución continua es $s(p)=-\log p$. En bits: certeza 0 bits, moneda 1 bit, evento de 1/4 2 bits. La entropía es el promedio de preguntas sí/no necesarias para identificar la clase de un punto del nodo.

Gini = probabilidad de desacuerdo. Saca un punto del nodo y, independientemente, una etiqueta de la distribución del nodo: Gini es la probabilidad de que no coincidan, $\sum_k\hat p_k(1-\hat p_k) = 1-\sum_k\hat p_k^2$. Nodo B: $1-(2/7)^2-(5/7)^2 = 20/49\approx0.408$.

Pregunta del banco

«La entropía es la probabilidad de que dos extracciones pertenezcan a clases distintas, y el Gini es la sorpresa promedio» → Falso: están intercambiadas.

Las tres valen 0 en los extremos puros y son máximas en $p=1/2$ (binario: Gini 0.5, entropía 1 bit). Con $K$ clases el peor caso es $\hat p_k=1/K$: Gini $=1-1/K$, $H=\log_2K$. Un Gini de 0.667 con 3 clases no es un error: es el máximo. En el ejemplo: raíz G = 0.500, H = 1.000; B: G = 0.408, H = 0.863; D: G = 0.444, H = 0.918 (¡D no es menor que B! Solo el total ponderado baja garantizado).

Calcular Gini y entropía del nodo B = [2, 5]

1. Fracciones: $\hat p_0 = 2/7 \approx 0.286$, $\hat p_1 = 5/7 \approx 0.714$.
2. Error rate: $1 - \max(\hat p_k) = 1 - 5/7 = 2/7 \approx 0.286$ (predecir la mayoría, clase 1, falla 2 de 7).
3. Gini: $1 - (2/7)^2 - (5/7)^2 = 1 - 4/49 - 25/49 = 20/49 \approx 0.408$.
4. Entropía: $-\tfrac27\log_2\tfrac27 - \tfrac57\log_2\tfrac57 = 0.286\cdot1.807 + 0.714\cdot0.485 = 0.516 + 0.347 = 0.863$ bits.
5. Lectura: en promedio hacen falta 0.863 preguntas sí/no para adivinar la clase de un punto de B (menos de 1 porque está sesgado hacia la clase 1), y dos extracciones independientes discrepan con probabilidad 0.408.
6. Comparación: la raíz $[5,5]$ tiene Gini 0.5 y entropía 1 bit (el máximo con 2 clases).

← AnteriorSiguiente paso →Ver todoReiniciar

Puntuar un split: ganancia de información

$$\Delta I(j,t) = I(m) - \frac{n_L}{n_m}I(L) - \frac{n_R}{n_m}I(R)$$

«¿Cuántos bits (o cuánto Gini) me compró esta pregunta?». Los pesos $n_L/n_m$, $n_R/n_m$ no son decorativos: sin ellos, una hojita pura podría ganarle a un hijo enorme y mezclado. Ejemplo del spam: padre $[60,40]$, Gini 0.48; split «free»: 38 puntos con Gini 0.2659 y 62 con 0.2248 ⇒ ganancia $0.48-0.2404 = 0.2396$.

El hecho fundamental: concavidad ⇒ ganancia ≥ 0

La fracción del padre es un promedio ponderado de las de los hijos: $\hat p = \frac{n_L}{n_m}\hat p_L+\frac{n_R}{n_m}\hat p_R$. Así, la impureza ponderada de los hijos es la altura de la cuerda entre $(\hat p_L,I(\hat p_L))$ y $(\hat p_R,I(\hat p_R))$ evaluada en $\hat p$. Si $I$ es cóncava, la curva queda encima de toda cuerda (Jensen) ⇒ $\Delta I\ge0$. Un split nunca aumenta la impureza. Gini y entropía son estrictamente cóncavas: ganancia > 0 siempre que $\hat p_L\ne\hat p_R$.

La ganancia es el hueco entre la curva y la cuerda

Un split parte un nodo en dos hijos. La fracción del padre es un promedio ponderado de las de los hijos, así que la impureza ponderada de los hijos es la cuerda; si la impureza es cóncava, la curva queda encima y la ganancia ≥ 0.

Raíz: x₁ ≤ 3.5Nodo B: x₂ ≤ 6.5 (hoja pura)Ganancia cero: x₂ ≤ 2.5Nodo D: x₂ ≤ 2.5

hijo izquierdo · n = 3

clase 0 3clase 1 0

hijo derecho · n = 7

clase 0 2clase 1 5

Ginientropía (bits)error

Gini 1 − Σp̂²entropía −Σp̂ log₂p̂error 1 − max p̂cuerda (impureza ponderada de los hijos)

ganancia Gini0.2143

ganancia entropía0.3958

ganancia error0.3000

padre[5, 5]

Los pesos nL/n y nR/n no son decorativos: sin ellos, una hojita pura podría «ganarle» a un hijo grande y mezclado. Gini y entropía son estrictamente cóncavas, así que la ganancia es > 0 siempre que p̂L ≠ p̂R.

🚑

Caso de uso · saludTriage en urgencias: un árbol que una enfermera puede seguir

Un hospital quiere priorizar pacientes con dolor torácico usando 4 datos que se miden en minutos: presión sistólica, edad, frecuencia cardiaca y si hay cambios en el ECG. Un árbol de profundidad 3 se imprime como una tarjeta:

• «¿Presión sistólica ≤ 91? → alto riesgo.» «Si no: ¿edad ≤ 62.5? → bajo riesgo.» «Si no: ¿taquicardia? → alto riesgo; si no, bajo.»
• Cada pregunta se eligió porque producía la mayor ganancia de Gini sobre los datos históricos: separa mejor los pacientes que tuvieron un evento grave de los que no.
• Ventajas decisivas aquí: no hace falta una computadora, cada decisión se explica con un camino de 2–3 preguntas, y no hay que estandarizar nada.
• El riesgo: si se deja crecer, el árbol memoriza casos raros; por eso se limita la profundidad y se valida con pacientes de otro año.

Ganancia cero y el problema del error rate

• Ganancia cero: cortando en $x_2\le2.5$ en la raíz, los hijos $[1,1]$ y $[4,4]$ tienen la misma proporción que el padre: la cuerda toca la curva, ganancia 0 con las tres medidas. Separó puntos pero no aprendió nada.
• Por qué no crecer con el error rate: en el nodo B, cortar en $x_2\le6.5$ da hijos $[2,2]$ y $[0,3]$: ¡una hoja pura! Gini da $6/49\approx0.122$ de ganancia, pero el error rate da 0: ambos hijos mantienen la clase mayoritaria 1 y, en ese tramo, el error es una recta, así que la cuerda cae sobre la curva. Un algoritmo codicioso con error rate rechazaría el split y pararía. Crece con Gini o entropía; el error rate sirve para evaluar el árbol final.

¿Gini o entropía?

En la raíz ambos prefieren $x_1\le3.5$ (Gini 0.2143) sobre $x_2\le5.5$ (0.1800); el error rate los empata en 0.2 y no puede elegir. En la práctica Gini y entropía eligen el mismo split la inmensa mayoría de las veces; Gini es el default porque evita un logaritmo. No te angusties por esto; angústiate por el tamaño del árbol.

Ejercicio

Nodo $[6,4]$. Split A: $[5,0]$ y $[1,4]$. Split B: $[3,2]$ y $[3,2]$. Calcula la ganancia de Gini de cada uno.

Ver solución

Padre: $1-0.6^2-0.4^2 = 0.48$.

• A: izq. pura (0); der. $[1,4]$: $1-0.2^2-0.8^2 = 0.32$. Ponderado: $0.5\cdot0+0.5\cdot0.32 = 0.16$. Ganancia $= 0.32$.
• B: ambos hijos con la proporción del padre (0.48): ganancia 0.

Autoevaluación

0/6 correctas · 0 respondidas Reiniciar

1. En un árbol, una hoja es una región final y predice una constante $c_m$ igual para todos sus puntos.

a) Verdaderob) Falso

2. La entropía es la probabilidad de desacuerdo y el Gini la sorpresa promedio.

a) Verdaderob) Falso

3. El Gini máximo con 3 clases es…

a) 0.5b) 0.667c) 1d) 1.585

4. ¿Por qué la ganancia con Gini nunca es negativa?

a) porque Gini ≤ 0.5b) porque Gini es cóncava (Jensen)c) porque se pondera por nd) porque el árbol es binario

5. ¿Por qué no se crece un árbol con el error rate?

a) es muy carob) es lineal a trozos y puede dar ganancia 0 a un split útilc) no está definido para 2 clasesd) da ganancias negativas

6. Con pérdida cuadrática, la mejor constante de una hoja de regresión es…

a) la medianab) la mediac) la modad) el máximo

↔ Conexiones con otros temas

Log-lossLa entropía es la cross-entropy de la mejor probabilidad constante.CARTCómo se usa la ganancia para elegir (j, t) y crecer el árbol.El split «free»El mismo ejemplo de spam de la sesión 05, ahora como split.Convexidad/concavidadJensen: una curva cóncava queda encima de sus cuerdas.

Para profundizar

interactivoMLU-Explain · Decision TreesEntropía, ganancia de información y crecimiento del árbol.interactivoR2D3 · A visual introduction to MLClásico: casas de SF vs NY clasificadas con un árbol, con scroll animado.videoStatQuest · Decision and Classification TreesGini, cómo elegir el primer split y cuándo parar.

Fuente ·ML_Course_Decision_Trees.pdf (Lecture 08, slides 3–27) · BANCO_DE_PREGUNTAS_ML_PART_1.pdf