Clasificación da árbore de decisións

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.