Clasificación por árbol de decisión

Introducción

Los árboles de decisión (DT) son un método de aprendizaje supervisado no paramétrico que se utiliza para la clasificación y la regresión. El objetivo es crear un modelo que prediga el valor de una variable de destino mediante el aprendizaje de reglas de decisión simples deducidas de las características de los datos.

Entropía

El objetivo del entrenamiento es encontrar las mejores divisiones en los nodos para encontrar el árbol más óptimo. Las divisiones se realizan utilizando algunos criterios como: Entropía.

Existen muchas definiciones de entropía tales como:

La entropía corresponde a la cantidad de información contenida en una fuente de información.
La entropía también puede verse como la aleatoriedad o la medida de la sorpresa en un conjunto.
La entropía es una métrica que mide la imprevisibilidad o impureza en el sistema.

En árboles de decisión, consideraremos la entropía como la medida de la pureza dentro de un nodo. El objetivo del modelo de árbol de decisión es reducir la entropía de los nodos en cada división:

Por lo tanto, queremos maximizar la diferencia entre la entropía del nodo principal y la entropía de los nodos secundarios. Esta diferencia se denomina Ganancia de información.

La Entropía $H$ de un conjunto $X$ se formula matemáticamente de la siguiente manera:

H(X) = - \sum\limits\_{x \in X} p(x) \log p(x)

Ganancia de información

La ganancia de información es la diferencia entre la entropía del nodo principal y la suma ponderada de las entropías de los nodos secundarios y, por lo tanto, se puede formular de la siguiente manera:

$IG(Y, X) = H(Y) - \sum_{x \in unique(X)} P(x|X) \times H(Y | X = x)$

$= H(Y) - \sum_{x \in unique(X)} \frac{X.count(x)}{len(X)} \times H(Y[X == x])$

where:

$H(.)$ es la entropía.
$Y$ es la población antes de la división, representa el nodo padre.
$X$ es la variable que queremos usar para la división.
$x$ es un valor único de X.
$Y[X==x]$ es una lista dividida con solo valores de $x$ .

tomemos un ejemplo apropiado:

Vamos a calcular la ganancia de información cuando dividimos el nodo principal usando los valores de X:

$IG(parent, X) = H(parent) - \sum_{x \in unique(X)} P(x|X) \times H(parent | X = x)$

Primero, calculamos la entropía del nodo padre:

$H(parent) = - P(Y=Blue) \times \log P(Y=Blue) - P(Y=Yellow) \times \log P(Y=Yellow)$

$= - \frac{11}{21} \times \log(\frac{11}{21}) - \frac{10}{21} \times \log(\frac{10}{21}) = 0.3$

Luego, vamos a calcular la probabilidad interna de cada nodo secundario después de la división usando los valores únicos de X:

$unique(X) = [Circle, Square]$

$\sum\_{x \in unique(X)} P(x|X) \times H(Y | X = x) = P(Square|X) \times H(Y | X = Square)$

$+ P(Circle|X) \times H(Y | X = Circle)$

$= \frac{9}{21} \times H(Y | X = Square) + \frac{12}{21} \times H(Y | X = Circle)$

Como:

$H(Y | X = Square)$ :representa la entropía del primer nodo hijo.
$H(Y | X = Circle)$ : representa la entropía del segundo nodo hijo.

Empezamos con el primer nodo hijo:

$H(Y | X = Square) = - P(Y=Blue | X = Square) \times \log P(Y=Blue| X = Square)$

$- P(Y=Yellow| X = Square) \times \log P(Y=Yellow| X = Square)$

$= - \frac{7}{9} \times \log\frac{7}{9} - \frac{2}{9} \times \log\frac{2}{9} = 0.23$

Y luego el segundo nodo hijo:

$H(Y | X = Circle) = - P(Y=Blue | X = Circle) \times \log P(Y=Blue| X = Circle)$

$- P(Y=Yellow| X = Circle) \times \log P(Y=Yellow| X = Circle)$

$= - \frac{4}{12} \times \log\frac{4}{12} - \frac{8}{12} \times \log\frac{8}{12} = 0.28$

Finalmente, sustituimos las entropías en la fórmula de ganancia de información:

$IG(parent, X) = H(parent) - \sum_{x \in unique(X)} P(x|X) \times H(parent | X = x)$

$= 0.3 - \frac{9}{21} \times 0.23 - \frac{12}{21} \times 0.28 = 0.041$

Como se indicó anteriormente, el objetivo de la división de un nodo es maximizar la ganancia de información y, por lo tanto, minimizar la entropía en el nodo secundario resultante. Para hacer esto, debemos intentar dividir el nodo con diferentes conjuntos de entradas $X_1, X_2, \ldots, Xn$ y solo mantenemos la división que maximiza la ganancia de información:

$X^{\*} = \underset{X_i}{\operatorname{argmax}} IG(Y, X_i)$

Cuándo dejar de dividir

La división de nodos en los árboles de decisión es recursiva, por lo que debe haber un criterio que podamos usar para detener la división. Estos son algunos de los criterios más implementados:

Cuando el nodo es puro: H(node) = 0. No tiene sentido dividir más el nodo.
Número máximo de profundidad: Podemos establecer una profundidad máxima que puede alcanzar el modelo, lo que significa que incluso si el nodo no es puro, la división se detiene.
Número mínimo de muestras por nodo: También podemos establecer un número mínimo de $N$ de muestras por nodo. Si el número de muestras por nodo es igual a $N$ , dejamos de dividir incluso si el nodo no es puro.

Al final del entrenamiento (la división), cada nodo que se basa en el final del árbol de decisión se denomina "Hoja", porque no es la raíz de ningún subárbol. Cada hoja representará el rendimiento de la clase con la mayor cantidad de muestras.

Conclusión

El árbol de decisión es uno de los algoritmos de aprendizaje automático más famosos debido a su eficiencia, su fondo intuitivo y su implementación simple. Este algoritmo se puede utilizar además con variables independientes numéricas (Árbol de decisión de Gauss), y también se puede ampliar para resolver tareas de regresión.