Introdución
As árbores de decisión (DT) son un método de aprendizaxe supervisado non paramétrico utilizado para a clasificación e a regresión. O obxectivo é crear un modelo que prediga o valor dunha variable obxectivo aprendendo regras de decisión sinxelas que se deducen das características dos datos.
Entropía
O obxectivo do adestramento é atopar as mellores divisións nos nodos para atopar a árbore máis óptima. As divisións realízanse utilizando algúns criterios como: Entropía.
Existen moitas definicións de entropía como:
-
A entropía corresponde á cantidade de información contida nunha fonte de información.
-
A entropía tamén se pode ver como a aleatoriedade ou a medición da sorpresa nun conxunto.
-
A entropía é unha métrica que mide a imprevisibilidade ou impureza do sistema.
Nas árbores de decisión, consideraremos a entropía como a medida da pureza no interior dun nodo. O obxectivo do modelo da árbore de decisión é reducir a entropía dos nodos en cada división:
Así, queremos maximizar a diferenza entre a entropía do nodo pai e a entropía dos nodos fillos. Esta diferenza chámase Ganancia de información.
A Entropía $H$ dun conxunto $X$ formúlase matematicamente como segue:
$$ H(X) = - \sum\limits_{x \in X} p(x) \log p(x) $$
Ganancia de información
A ganancia de información é a diferenza entre a entropía do nodo pai e a suma ponderada das entropías dos nodos dos criados, polo que pódese formular como segue:
$$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])$$
onde:
-
$H(.)$ é a entropía.
-
$Y$ é a poboación anterior á división, representa o nodo pai.
-
$X$ é a variable que queremos usar para a división.
-
$x$ é un valor único de X.
-
$Y[X==x]$ é unha lista dividida con só valores de $x$.
pomos un exemplo axeitado:
Imos calcular a ganancia de información cando dividimos o nodo pai usando os valores de X:
$$IG(parent, X) = H(parent) - \sum_{x \in unique(X)} P(x|X) \times H(parent | X = x)$$
\
Primeiro, calculamos a entropía do nodo pai:
$$ 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 $$
\
Entón, imos calcular a probabilidade interna de cada nodo fillo despois da división usando os 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) $$
Tales como:
-
$H(Y | X = Cadrado)$ : representa a entropía do primeiro nodo fillo.
-
$H(Y | X = Círculo)$ : representa a entropía do segundo nodo fillo.
\
Comezamos co primeiro nodo fillo:
$$ 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 $$
\
E despois o segundo nodo fillo:
$$ 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, substituímos as entropías na 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 dixo antes, o obxectivo dunha división de nodos é maximizar a ganancia de información e, polo tanto, minimizar a Entropía no nodo fillo resultante. Para iso, debemos tentar dividir o nodo con diferentes conxuntos de entradas $ X_1, X_2, \ldots, Xn $ e só mantemos a división que maximiza a ganancia de información:
$$ X^{*} = \underset{X_i}{\operatorname{argmax}} IG(Y, X_i) $$
Cando deixar de dividir
A división de nodos nas árbores de decisión é recursiva, polo que debe haber un criterio que poidamos utilizar para deter a división. Estes son algúns dos criterios máis aplicados:
-
Cando o nodo é puro: H(nodo) = 0. Non ten sentido dividir o nodo máis.
-
Número máximo de profundidade: Podemos establecer unha profundidade máxima que pode alcanzar o modelo, isto significa que aínda que o nodo non sexa puro a división está detida.
-
Número mínimo de mostras por nodo: Tamén podemos establecer un número mínimo de $N$ de mostras por nodo. Se o número de mostras por nodo é igual a $N$ entón deixamos de dividir aínda que o nodo non sexa puro.
Ao final do adestramento (a división), cada nodo que depende do final da árbore de decisión chámase "Folla", porque non é unha raíz de ningunha subárbore. Cada folla representará o rendemento da clase con máis mostras.
Conclusión
A árbore de decisións é un dos algoritmos de aprendizaxe automática máis famosos pola súa eficiencia, o seu fondo intuitivo e a súa sinxela implementación. Este algoritmo tamén se pode usar con variables numéricas independentes (Árbore de decisión gaussiana) e tamén se pode estender para resolver tarefas de regresión.
