Classificação da árvore de decisão
Atualizado em September 24, 2024 5 Minutos Leia

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.