Tema

Árboles de decisión

Machine Learning
Nivel base
Con simulador interactivo

Un árbol de decisión parte el conjunto de datos eligiendo en cada nodo el atributo que más reduce la impureza de las etiquetas, medida con entropía o con el índice de Gini, y detiene la partición con un criterio de parada o con una poda posterior.

Nombre en inglés

Decision trees

Intuición

Conviene verlo como un juego de preguntas donde cada pregunta debe separar lo más posible las respuestas. La entropía mide el desorden de una bolsa de etiquetas, de modo que vale 1 bit cuando la bolsa está repartida a la mitad y vale 0 cuando es pura. La ganancia de información es la entropía que había menos la entropía media que queda, o sea cuántos bits de incertidumbre compra esa pregunta.

Fórmula

H(S) = -sum_c p_c log2 p_c;  Ganancia(S, A) = H(S) - sum_v (|S_v| / |S|) * H(S_v)

Ejemplo resuelto

Un nodo tiene 8 ejemplos, 4 positivos y 4 negativos, de modo que su entropía vale 1. El atributo A lo parte en dos ramas de 4 ejemplos, la primera con 3 positivos y 1 negativo y la segunda con 1 positivo y 3 negativos. La entropía de cada rama vale menos 0.75 por log2 de 0.75 menos 0.25 por log2 de 0.25, o sea 0.811. La entropía media ponderada vale también 0.811 porque las ramas son iguales de tamaño, y la ganancia resulta 1 menos 0.811 = 0.189 bits.

Errores frecuentes

Usar la ganancia de información cruda con atributos de muchos valores, ya que un identificador único parte el conjunto en hojas puras y gana siempre sin generalizar nada, problema que corrige la razón de ganancia.
No podar el árbol y quedarse con hojas de un solo ejemplo, con lo que el modelo memoriza el ruido y la varianza se dispara.
Esperar que un árbol trace una frontera diagonal, cuando cada corte es perpendicular a un eje y una separación oblicua obliga a una escalera de muchos cortes.

Ejercicio

Un nodo contiene 8 ejemplos, 2 positivos y 6 negativos. Calcula su entropía en bits.

Ver la solución

Las proporciones valen 0.25 y 0.75. La entropía es menos 0.25 por log2 de 0.25, que aporta 0.25 por 2 = 0.5, menos 0.75 por log2 de 0.75, que aporta 0.75 por 0.415 = 0.311. La suma da 0.811 bits. Al comparar con el nodo equilibrado del ejemplo, que valía 1 bit, se aprecia que el desorden baja despacio al principio y solo cae de golpe cuando el nodo se acerca a la pureza.