1.1.1 Procedimento de crescimento da árvore

Para definir o procedimento para fazer crescer nossa árvore binária devemos responder as seguintes perguntas:

1. Como escolhemos as condições booleanas para dividir cada nó?
2. Qual critério usar para dividir um nó pai em seus dois nós filhos?
3. Como decidir quando um nó se torna folha?
4. Como atribuímos à classe ao nó folha?

1.2.1 Maximizar o ganho de informação

Com a finalidade de dividir os nós nas características mais informativas, devemos definir uma função objetivo que desejamos otimizar através do algoritmo de aprendizado da árvore. Neste caso, nossa função objetivo é maximizar o ganho de informação (\(IG\), do inglês Information Gain) em cada divisão \(d\) de uma variável \(X\), definida por \[IG(a_p,d) = I(a_p)-\sum_{j=1}^m \frac{n_j}{n_p}I(a_j),\]

em que \(a_p\) e \(a_j\) são o nó pai e nó filho \(j\), respectivamente; \(I\) é a nossa medida de impureza; \(n_p\) é o número total de amostras no nó pai, e \(n_j\) é o número de amostras no nó filho \(j\).

Note que o \(IG\) é a diferença entre a impureza do nó pai e a soma das impurezas dos nós filhos: quanto menor a impureza dos nós filhos, maior o ganho de informação.

Computacionalmente, é mais eficiente implementar árvores de decisão binárias. Isso siginifica que cada nó pai se divide em dois nós filhos \(a_{e}\) e \(a_{d}\): \[IG(a_p,d) = \Delta(a_p,d) = I(a_p) - \frac{n_{e}}{n_p}I(a_{e}) - \frac{n_{d}}{n_p} I(a_{d}),\] \(n_e/n_p\) e \(n_d/n_p\) são a proporção de observações que ficam no nó filho à esquerda e direita do nó pai \(a_p\), respectivamente.

Respondendo à segunda questão, para cada variável \(X_j\) escolhemos aquela divisão \(d\) que tenha o maior ganho de informação (ou seja, a maior redução de impureza).

A continuação, apresentamos três medidas de impureza comumnente utilizadas.

1.2.2 Impureza de Shanon (Entropia)

\[I_H(a)=-\sum_{k=1}^C p(k|a)\log p(k|a),\] em que \(p(k|a)\) é a proporção das amostras que pertencem à classe \(k\) para um determinado nó \(a\).

Quando temos duas classes a entropia se reduz a \[I_H(a) = -p\log(p) - (1-p)\log(1-p),\] em que \(p = p(1|a)\).

A entropia é, portanto, 0 se todas as amostras em um nó pertencem à mesma classe, e a entropia é máxima se temos uma distribuição de classes uniforme.

Por exemplo, suponha que temos um problema de classificação binária, a entropia é 0 se \(p(1|a) = 1\) ou \(p(2|a) = 1\). Se as classes estão distribuídas uniformemente com \(p(1|a) = 1/2\) e \(p(2|a) = 1/2\), a entropia é 1.

1.2.3 Impureza de Gini

\[I_G(a) = \sum_{k=1}^C p(k|a)(1-p(k|a)) = 1 - \sum_{k=1}^c p(k|a)^2.\] Quando temos duas classes a impureza de Gini se reduz a

\[I_G(a) = 2p(1-p),\]

em que \(p = p(1|a)\).

1.2.4 Impureza de erro de classificação

\[I_E(a) = 1 - \max_{k\in \{1, \ldots, C\}}\{p(k|a)\}.\] Quando temos duas classes a impureza de erro de classificação se reduz a

\[I_E(a) = 1-\max\{p,1-p\} = \min\{p,1-p\},\] em que \(p = p(1|a)\).

Observação. O coeficiente \(I_E\) não é recomendável para fazer crescer a árvore, pois é menos sensível às mudanças nas probabilidades de classe dos nós.

3. Como decidir quando um nó se torna folha?

Uma maneira de tornar um nó \(a\) em folha é quando ele é totalmente puro. Outra alternativa é fixar um número \(n_\min\) de modo que se o número de amostras no nó \(a\), \(n(a)\), for no máximo \(n_\min\), ou seja, \(n(a) \leq n_{\min}\).

Na prática, deixamos crescer a árvore até a saturação, ou seja, quando nenhum nó possa ser mais dividido e logo aplicamos uma poda.

4. Como atribuímos à classe ao nó folha?

Atribuímos aquela classe mais frequente, ou seja, se denotamos por \(n_k(a)\) o número de amostras da classe \(k = 1, \ldots, C\) no nó \(a\). Então, a classe de \(a\) será o \(k\) tal que \(n_k(a)\) sejá máximo.

Vamos mostrar com um exemplo como funciona o procedimento para criar uma árvore de decisão no seguinte conjunto de dados:

em que \[x_1 = \begin{cases} 1, & \text{apresenta vômito} \\ 0, & \text{não apresenta vômito} \end{cases}\]

\[x_1 = \begin{cases} 1, & \text{apresenta febre} \\ 0, & \text{não apresenta febre} \end{cases}\]

\[y= \begin{cases} 1, & \text{atendimento não urgente} \\ 2, & \text{atendimento urgente} \end{cases}\]

# Calculando o ganho de informação de dividir a raiz pela X1
# proporção de observações de c/classe (nó pai)
prob_1 = c(4,3)/7 
# proporção de observações de c/classe (nó filho esquerdo X1 = 0)
prob_2 = c(3,2)/5 
# proporção de observações de c/classe (nó filho direito X1 = 1)
prob_3 = c(1,1)/2

# Usaremos a impureza de Gini
imp_gini <- function(p){
  2*p[1]*p[2]
}

gini1 = imp_gini(prob_1)
gini2 = imp_gini(prob_2)
gini3 = imp_gini(prob_3)

# Ganho de informação de fazer a divisão pela X1
inf_gain_X1 <- gini1 - (5/7)*gini2 - (2/7)*gini3


# Calculando o ganho de informação de dividir a raiz pela X2
# proporção de observações de c/classe (nó pai)
prob_1 = c(4,2)/6 
# proporção de observações de c/classe (nó filho esquerdo X2 = 0)
prob_2 = c(4,1)/5 
# proporção de observações de c/classe (nó filho direito X2 = 1)
prob_3 = c(0,2)/2

gini1 = imp_gini(prob_1)
gini2 = imp_gini(prob_2)
gini3 = imp_gini(prob_3)

# Ganho de informação de fazer a divisão pela X2
inf_gain_X2 <- gini1 - (5/7)*gini2 - (2/7)*gini3
cbind(inf_gain_X1,inf_gain_X2) 

##      inf_gain_X1 inf_gain_X2
## [1,] 0.004081633    0.215873

Como o maior ganho de informação foi obtido ao fazer a divisão pela variável \(X_2\). A árvore fica:

Voltando ao banco de dados loan_ data vamos treinar uma árvores de decisão usando a função train():

library(caret)
set.seed(12345)
index_train <- createDataPartition(y = loan_data$outcome, p = 0.8, list = F)
training <- loan_data[index_train, ]
testing <- loan_data[-index_train, ]

# Treinando a árvore
set.seed(12345)
model_rpart <- train(outcome ~ borrower_score + payment_inc_ratio,
                     data = training,
                     method = "rpart")
model_rpart

## CART 
## 
## 2400 samples
##    2 predictor
##    2 classes: 'default', 'paid_off' 
## 
## No pre-processing
## Resampling: Bootstrapped (25 reps) 
## Summary of sample sizes: 2400, 2400, 2400, 2400, 2400, 2400, ... 
## Resampling results across tuning parameters:
## 
##   cp           Accuracy   Kappa    
##   0.005190311  0.6055740  0.2109504
##   0.023356401  0.6069965  0.2136775
##   0.174740484  0.5745355  0.1415658
## 
## Accuracy was used to select the optimal model using the largest value.
## The final value used for the model was cp = 0.0233564.

# Fazendo predições no conjunto teste
predictions <- predict(model_rpart, testing)

# Avaliando o desempenho 
confusionMatrix(predictions, testing$outcome)

## Confusion Matrix and Statistics
## 
##           Reference
## Prediction default paid_off
##   default      233      189
##   paid_off      56      122
##                                           
##                Accuracy : 0.5917          
##                  95% CI : (0.5511, 0.6313)
##     No Information Rate : 0.5183          
##     P-Value [Acc > NIR] : 0.0001813       
##                                           
##                   Kappa : 0.1953          
##                                           
##  Mcnemar's Test P-Value : < 2.2e-16       
##                                           
##             Sensitivity : 0.8062          
##             Specificity : 0.3923          
##          Pos Pred Value : 0.5521          
##          Neg Pred Value : 0.6854          
##              Prevalence : 0.4817          
##          Detection Rate : 0.3883          
##    Detection Prevalence : 0.7033          
##       Balanced Accuracy : 0.5993          
##                                           
##        'Positive' Class : default         
## 

Finalmente, a árvore resultante é apresentada a seguir:

rpart.plot(model_rpart$finalModel)

Ajustamos o hiperparâmetro cp para fazer crescer mais a árvore:

# Alterando o parâmetro de controle
tuneGrid <- expand.grid(cp = 0.005)
tuneGrid

##      cp
## 1 0.005

model_rpart <- train(outcome ~ borrower_score + payment_inc_ratio,
                     data = training,
                     method = "rpart",
                     tuneGrid = tuneGrid)

rpart.plot(model_rpart$finalModel)

# Fazendo predições no conjunto teste
predictions <- predict(model_rpart, testing)

# Avaliando o desempenho 
confusionMatrix(predictions, testing$outcome)

## Confusion Matrix and Statistics
## 
##           Reference
## Prediction default paid_off
##   default      176      119
##   paid_off     113      192
##                                           
##                Accuracy : 0.6133          
##                  95% CI : (0.5731, 0.6525)
##     No Information Rate : 0.5183          
##     P-Value [Acc > NIR] : 1.743e-06       
##                                           
##                   Kappa : 0.2262          
##                                           
##  Mcnemar's Test P-Value : 0.7427          
##                                           
##             Sensitivity : 0.6090          
##             Specificity : 0.6174          
##          Pos Pred Value : 0.5966          
##          Neg Pred Value : 0.6295          
##              Prevalence : 0.4817          
##          Detection Rate : 0.2933          
##    Detection Prevalence : 0.4917          
##       Balanced Accuracy : 0.6132          
##                                           
##        'Positive' Class : default         
##