Aula 12: Poda da árvore de classificação
1 Árvores de classificação: Estimando o erro de classificação
Seja \(T\) uma árvore de classificação e \(\widetilde{T} = \{a_1, \ldots,a_L\}\) o conjunto dos nós folhas de \(T\). O erro de classificação errada (ou de resubstituição) da árvore \(T\) é definido por: \[R(T) = \sum_{l=1}^L I_E(a_l)p(a_l) = \sum_{l=1}^L R(a_l),\] em que \(\displaystyle I_E(a_l) = 1- \max_{k}p(k|a_l)\) e \(p(a_l)\) é a proporção de todas as observações que pertencem ao nó \(a_l\). A medida \(R(T)\) pode ser vista como a impureza da árvore \(T\).
Voltemos aos dados de inadimplência vistos na Aula 11. A árvore
ajustada para esse conjunto de dados, usando a função
rpart::rpart() é mostrada a continuação:
A matriz de confusão é apresentada a seguir:
## Verdadeiros
## Preditos default paid_off
## default 855 515
## paid_off 590 1040Das 3000 observações no conjunto de dados de inadimplência, a árvore
de classificação acima, classifica erradamente 515 das 1555 aplicações
pagas (paid_off) como não pagas (default), ao
passo que das 1445 aplicações não pagas, 590 foram classificadas
erradamente como pagas. Portanto, a impureza estimada da árvore \(T\) é \(R(T) =
1105/3000 = 0,3683\).
Observação. A função rpart()
internamente faz uma VC, ou seja, uma parte do conjunto de dados é usada
para contruir a árvore e a outra para validação. A saída do ajuste
segue:
##
## Classification tree:
## rpart::rpart(formula = outcome ~ borrower_score + payment_inc_ratio,
## data = loan_data, method = "class", control = rpart.control(cp = 0.005))
##
## Variables actually used in tree construction:
## [1] borrower_score payment_inc_ratio
##
## Root node error: 1445/3000 = 0.48167
##
## n= 3000
##
## CP nsplit rel error xerror xstd
## 1 0.170242 0 1.00000 1.00000 0.018940
## 2 0.021799 1 0.82976 0.82976 0.018567
## 3 0.010727 3 0.78616 0.81315 0.018502
## 4 0.005000 5 0.76471 0.82145 0.018535Root node error (erro da raiz): taxa de erro de
classificação obtida quando classificamos todas as observações como
paid_off.
rel error: erro de classificação relativo àquele da raiz
(para o qual o valor é paid_off) para os dados de
treinamento.
xerror: erro de classificação relativo àquele da raiz
(para o qual o valor é paid_off) para os dados de validação
por meio de VC.
xstd: erro padrão associado à taxa
xerror.
O erro de resubsituição pode ser obtido pelo produto de
Root node error e rel error, ou seja, \(0,48167 \times 0,76471 = 0,3683\).
Similarmente, podemos obter uma medida mais objetiva usando os dados de
validação, isto é, calculando o produto de Root node error
e xerror, ou seja, \(0,48167
\times 0,79931 = 0,3850\). Portanto, teriamos uma acurácia de
\(0,6150\).
2 Poda da árvore
Um dos problemas com as árvores de decisão é o sobreajuste. Se não impusermos um critério de parada, a árvore pode crescer até ter tantos nós folhas como observações, resultando em uma árvore em que cada observação é classificado perfeitamente.
Uma maneira de contornar esse problema é aplicar uma poda. A ideia é criar uma árvore muito grande e logo limitar o número de nós folhas, e portanto obtemos um modelo com menos variância. Porém, temos um aumento no viés do modelo resultante.
# Árvore máxima
model_tree_max <- rpart::rpart(outcome ~ borrower_score + payment_inc_ratio,
data = loan_data,
minsplit = 10,
cp = 0.002,
method = "class")
# model_tree
rpart.plot(model_tree_max, extra = 101, type = 4)
Para fazer a poda da árvore examinamos o parâmetro de complexidade que serve para controlar o tamanho da árvore e corresponde ao menor incremento no custo do modelo necessário para a consideração de uma nova subdivisão.
Procuramos o nível para o qual o cp é mínimo. Vemos no
gráfico acima que esse valor está entre 0,005 e 0,010, o que sugere que
a árvore ajustada deve ser podada, de modo que fiquem entre 5 e 7 nós
folhas.
model_tree_max_poda <- prune(model_tree_max, cp = 0.005, "CP", minsplit = 20, xval = 25)
rpart.plot(model_tree_max_poda, extra=101, type = 4)
Algoritmo de poda
Deixe crescer uma árvore grande, \(T_\max\), em que mantemos as divisões até que cada nó contenha menos de \(n_\min\) observações;
Calcule uma estimativa de \(R(a)\) para cada nó \(a \in T_\max\);
Pode \(T_\max\) de baixo para cima, em direção à raiz, tal que a cada etapa da poda, a estimativa \(R(T)\) seja minimizada.
Vamos supor os seguintes valores para o erro estimado \(R(a)\), para cada \(a\) folha:
Folha 1: R = 0.1
Folha 2: R = 0.2
Folha 3: R = 0.15
Então, o custo da subárvore de A é:
\[ R(A_{\text{subárvore}}) = 0{,}1 + 0{,}2 = 0{,}3 \]
Se substituirmos o nó A por uma única folha (podar A), e supondo que o erro estimado como uma folha única é:
\[ R(A_{\text{podado}}) = 0{,}25, \]
vale a pena podar o nó, pois \(0.25 < 0.3\).
Na prática, ao invés de usar \(R(T)\), o modificamos por uma versão regularizada. Isto é, usamos para cada nó \(a\) a seguinte medida: \[R_\alpha(a) = R(a) + \alpha,\] em que \(\alpha \ge 0\) é um parâmetro de complexidade. E definimos uma medida do custo de complexidade da poda para uma árvore \(T\) como segue: \[R_\alpha(T) = \sum_{l=1}^L R_\alpha(a_l) = R(T) + \alpha |\widetilde{T}|,\] em que \(|\widetilde{T}| = L\) é o número de nós folhas na sub-árvore \(T\) de \(T_\max\).
O termo \(\alpha |\widetilde{T}|\) pode ser visto como uma penalidade para o tamanho da árvore, de modo que \(R_\alpha(T)\) penaliza \(R(T)\) por gerar uma árvore muito grande. Para cada \(\alpha\), escolhemos a sub-árvore \(T(\alpha)\) de \(T_\max\) que minimize \(R_\alpha(T)\): \[R_\alpha(T(\alpha)) = \min_T R_{\alpha}(T).\]
Considere, por exemplo, duas árvores \(T_1\) e \(T_2\), de modo que \(R(T_1) = 0,10\) e \(|T_1| = 20\). Por outro lado, \(R(T_2) = 0,12\) e \(|T_2| = 5\). Logo, para \(\alpha = 0,005\) \[\begin{align} R_\alpha(T_1) &= 0,10 + 0,005\times 20 = 0,10 + 0,10 = 0,20\\ R_\alpha(T_2) &= 0,12 + 0,005\times 5 = 0,12+0,025 = 0,145. \end{align}\] Neste caso, selecionamos a árvore \(T_2\), embora ele tenha um erro de classificação maior, pois tem um custo total menor.
OBSERVAÇÕES:
Se \(T(\alpha)\) satisfaz a expressão acima, então é chamada de uma subárvore minimizadora de \(T_\max\). Para qualquer \(\alpha\), podem existir mais de uma subárvore minimizadora de \(T_\max\).
O valor de \(\alpha\) determina o tamanho da árvore:
- Quando \(\alpha\) é muito pequeno, então \(T(\alpha)\) é muito grande.
- Quando \(\alpha\) é muito grande, então \(T(\alpha)\) é muito pequena.