Classificação da árvore de decisão

Introdução

Árvores de decisão (DTs) são um método de aprendizagem supervisionado não paramétrico usado para classificação e regressão. O objetivo é criar um modelo que preveja o valor de uma variável alvo, aprendendo regras de decisão simples inferidas a partir dos recursos dos dados.

Entropia

O objetivo do treinamento é encontrar as melhores divisões nos nós para encontrar a árvore ideal. As divisões são feitas usando alguns critérios como: Entropia.

Existem muitas definições de entropia, como:

A entropia corresponde à quantidade de informação contida numa fonte de informação.
A entropia também pode ser vista como a aleatoriedade ou a medição da surpresa num conjunto.
A entropia é uma métrica que mede a imprevisibilidade ou impureza do sistema.

Nas árvores de decisão, consideraremos a entropia como a medida da pureza dentro de um nó. O objetivo do modelo de árvore de decisão é reduzir a entropia dos nós em cada divisão:

Assim, queremos maximizar a diferença entre a entropia do nó pai e a entropia dos nós filhos. Essa diferença é chamada de Ganho de informação.

A Entropia $H$ de um conjunto $X$ é formulada matematicamente da seguinte forma:

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

Ganho de informações

Ganho de informação é a diferença entre a entropia do nó pai e a soma ponderada das entropias dos nós filhos e, portanto, pode ser formulado da seguinte forma:

$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 entropia.
$Y$ é a população anterior à divisão, representa o nó pai.
$X$ é a variável que queremos usar para a divisão.
$x$ é um valor único de X.
$Y[X==x]$ é uma lista dividida com apenas valores $x$ .

vamos dar um exemplo adequado:

Vamos calcular o ganho de informação quando dividimos o nó 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 entropia do nó 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$

Em seguida, calcularemos a probabilidade interna de cada nó filho após a divisão 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)$

Como:

$H(Y | X = Square)$ : representa a entropia do primeiro nó filho.
$H(Y | X = Circle)$ : representa a entropia do segundo nó filho.

Começamos com o primeiro nó filho:

$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 então o segundo nó filho:

$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$

Por fim, substituímos as entropias na fórmula de Ganho de Informação:

$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$

Conforme afirmado anteriormente, o objetivo de uma divisão de nó é maximizar o ganho de informação e, assim, minimizar a entropia no nó filho resultante. Para fazer isso, precisamos tentar dividir o nó com diferentes conjuntos de entradas $X_1, X_2, \ldots, Xn$ e mantemos apenas a divisão que maximiza o ganho de informação:

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

Quando parar de dividir

A divisão de nós nas árvores de decisão é recursiva, portanto deve haver um critério que possamos usar para interromper a divisão. Estes são alguns dos critérios mais implementados:

Quando o nó é puro: H(nó) = 0. É inútil dividir ainda mais o nó.
Número máximo de profundidade: Podemos definir uma profundidade máxima que o modelo pode atingir, isso significa que mesmo que o nó não seja puro a divisão é interrompida.
Número mínimo de amostras por nó: Também podemos definir um número mínimo $N$ de amostras por nó. Se o número de amostras por nó for igual a $N$ então paramos de dividir mesmo que o nó não seja puro.

Ao final do treinamento (a divisão), cada nó que depende do final da árvore de decisão é chamado de “Folha”, pois não é raiz de nenhuma subárvore. Cada folha representará o rendimento da classe com maior número de amostras.

Conclusão

A árvore de decisão é um dos algoritmos de aprendizado de máquina mais famosos devido à sua eficiência, experiência intuitiva e implementação simples. Este algoritmo pode ainda ser usado com variáveis numéricas independentes (árvore de decisão gaussiana) e também pode ser estendido para resolver tarefas de regressão.