Árvores de Decisão
CARACTERÍSTICAS O que é uma árvore de decisão?
- Aprendizado supervisionado.
- Usada principalmente em classificação (mas também em regressão).
- Estratégia “dividir para conquistar”: o problema é quebrado em subproblemas menores.
- Produz regras do tipo SE–ENTÃO.
- Divide o espaço das variáveis em subespaços.
- Abordagem “de cima para baixo” (top-down).
- Gulosa: em cada passo, olha apenas para a melhor divisão atual.
ESTRUTURA Representação de uma árvore de decisão
- Nó raiz: toda a amostra.
- Nó de decisão: um teste sobre um atributo.
- Folha (nó terminal): uma classe ou um valor contínuo.
Cada percurso da raiz até uma folha corresponde a uma regra.
ESTRUTURA A árvore divide o espaço em retângulos
- As regiões são disjuntas (interseção vazia) e sua união é todo o espaço.
- Atributos testados perto da raiz costumam ser os mais importantes.
CONSTRUÇÃO Como construir uma árvore de decisão
Objetivo: uma sequência de divisões, de cima para baixo, até criar folhas em que as classes estão bem separadas (classificação) ou o erro quadrático médio é pequeno (regressão).
CONSTRUÇÃO O que é uma boa divisão?
O critério é a utilidade do atributo para a classificação/regressão.
Inútil: mantém as mesmas proporções de classes em todas as partições.
Utilidade máxima: cada partição contém exemplos de uma só classe.
GANHO DE INFORMAÇÃO Entropia: quão misturado está um nó?
A entropia mede a aleatoriedade (o grau de impureza) da variável resposta:
\[\text{Entropia}(X) = -\sum_{i} p_i \log_2 p_i\]
em que \(p_i\) é a proporção de exemplos da classe \(i\).
- 0 → nó puro (uma só classe).
- Máxima (= 1, com duas classes) → nó heterogêneo (50% / 50%).
- Convenção: \(\lim_{p \to 0^+} p \log p = 0\).
EXEMPLO Jogar tênis: qual atributo vai na raiz?
| Dia | Aparência | Jogar tênis |
|---|---|---|
| 1 | Ensolarado | Não |
| 2 | Ensolarado | Não |
| 3 | Nublado | Sim |
| 4 | Chuva | Sim |
| 5 | Chuva | Sim |
| 6 | Chuva | Não |
| 7 | Nublado | Sim |
| 8 | Ensolarado | Não |
| 9 | Ensolarado | Sim |
| 10 | Chuva | Sim |
| 11 | Ensolarado | Sim |
| 12 | Nublado | Sim |
| 13 | Nublado | Sim |
| 14 | Chuva | Não |
Começamos pelo atributo Aparência:
| Ensolarado | Nublado | Chuva | |
|---|---|---|---|
| Sim | 2 | 4 | 3 |
| Não | 3 | 0 | 2 |
| Total | 5 | 4 | 5 |
No total: 9 Sim e 5 Não.
EXEMPLO Passo 3: ganho e escolha do atributo
\[\text{Ganho}(\text{Aparência}) = 0{,}940 - 0{,}694 = 0{,}247\]
Definido o atributo de maior ganho, ele inicia a partição. O processo se repete em cada nó filho até o fim da construção.
EXEMPLO Temperatura (°F)
| Temperatura | Jogar tênis |
|---|---|
| 64 | Sim |
| 65 | Não |
| 68 | Sim |
| 69 | Sim |
| 70 | Sim |
| 71 | Não |
| 72 | Não |
| 72 | Sim |
| 75 | Sim |
| 75 | Sim |
| 80 | Não |
| 81 | Sim |
| 83 | Sim |
| 85 | Não |
Exemplo de candidato: Temperatura < 70,5
| < 70,5 | ≥ 70,5 | |
|---|---|---|
| Sim | 4 | 5 |
| Não | 1 | 4 |
Ganho de 70,5: 0,045. Todos os candidatos são avaliados; vence o de maior ganho.
ÍNDICE GINI Entropia ou Gini?
- As duas medidas quase sempre levam à mesma árvore.
- O Gini é um pouco mais rápido de calcular (não usa logaritmo) — é o critério do CART.
EXEMPLO SDR: horas jogadas
| Dia | Aparência | Horas |
|---|---|---|
| 1 | Ensolarado | 45 |
| 2 | Ensolarado | 52 |
| 3 | Nublado | 46 |
| 4 | Chuva | 25 |
| 5 | Chuva | 30 |
| 6 | Chuva | 35 |
| 7 | Nublado | 43 |
| 8 | Ensolarado | 23 |
| 9 | Ensolarado | 46 |
| 10 | Chuva | 38 |
| 11 | Ensolarado | 30 |
| 12 | Nublado | 52 |
| 13 | Nublado | 44 |
| 14 | Chuva | 48 |
\(sd(Exs) = 9{,}32 \quad (\bar{y} = 39{,}8)\)
\(\tfrac{5}{14}\,sd_{\text{chuva}} + \tfrac{4}{14}\,sd_{\text{nublado}} + \tfrac{5}{14}\,sd_{\text{sol}} = 7{,}66\)
\(SDR_{\text{Aparência}} = 9{,}32 - 7{,}66 = 1{,}66\)
EXEMPLO SDR para todos os atributos
- Mesmos dias, outra resposta: a melhor divisão depende do alvo — Aparência era a melhor para jogar ou não, mas Temperatura é a melhor para quantas horas.
REGRESSÃO A árvore de regressão prevê em “degraus”
Quanto mais profunda a árvore, mais degraus — e mais perto de decorar os dados de treino.
PARADA Critérios de parada
Quando parar de dividir?
- Número mínimo de observações em um nó para que ele possa ser dividido.
- Número mínimo de observações em uma folha (nó terminal).
- Profundidade máxima da árvore (profundidade vertical).
- Número máximo de folhas (pode substituir a profundidade).
- Medida de partição (ganho, redução do Gini, SDR) menor que um valor pré-definido.
PODA Por que árvores sem restrição sofrem overfitting?
Sem restrições, a árvore cresce até decorar o treino — inclusive o ruído.
PODA Por que podar? A visão gulosa
Relembrando: o algoritmo é guloso → escolhe a melhor divisão naquele instante e avança até que um critério de parada seja atingido.
Com critérios de parada, a árvore não vê o caminhão à frente e vira à esquerda de forma gananciosa. Com a poda, olhamos alguns passos à frente antes de decidir.
PODA Pré-poda × pós-poda
Métodos de poda detectam e excluem ramos e subárvores para melhorar a taxa de acerto em novos exemplos — e a árvore podada fica mais simples de interpretar.
PÓS-PODA Métodos de pós-poda
A pós-poda busca o tamanho adequado da árvore depois que ela foi induzida por completo: avalia a confiabilidade de cada subárvore e poda os ramos não confiáveis.
- Redução de erros (Reduced Error Pruning) ← veremos
- Custo-complexidade (Cost-Complexity Pruning) ← veremos
- Erro pessimista (Pessimistic Error Pruning)
- Valor crítico (Critical Value Pruning)
- Erro mínimo (Minimum Error Pruning)
- Poda por estimativa de erro (Error-Based Pruning)
PÓS-PODA Redução de erros (Reduced Error Pruning)
Método simples e rápido, de orientação bottom-up. Antes de tudo, separamos o treino em crescimento (para construir a árvore) e validação (para decidir as podas).
Testar a poda de um nó = trocar temporariamente a subárvore abaixo dele por uma folha com a classe majoritária e medir a acurácia na validação.
PÓS-PODA Escolhendo o tamanho da árvore
α grande → árvores pequenas (pouco ajuste); α pequeno → árvores grandes (overfitting). A validação escolhe o meio-termo.
USO PRÁTICO Vantagens
- Fácil de entender.
- Representação gráfica intuitiva.
- Útil na exploração de dados.
- Faz seleção de variáveis (só usa as que ajudam a dividir).
- Sensibilidade reduzida a outliers.
- Manipula variáveis numéricas e categóricas, sem precisar padronizar.
- Método não paramétrico (não assume uma distribuição para os dados).
USO PRÁTICO Desvantagens
- Overfitting: exige restrições nos parâmetros do modelo e poda.
- Instabilidade: uma pequena mudança nos dados pode causar uma grande mudança na árvore final.
- Menor acurácia que modelos mais complexos.
- Fronteiras sempre paralelas aos eixos (regiões retangulares).
Próximos passos
Instabilidade e baixa acurácia motivam os comitês de árvores: bagging, random forest e boosting combinam muitas árvores para obter previsões mais estáveis.
Resumo
- Algoritmo de aprendizado supervisionado, usado principalmente em classificação.
- Funciona com variáveis de entrada e saída categóricas e contínuas.
- Divide a amostra em conjuntos cada vez mais homogêneos, escolhendo em cada nó o atributo mais informativo (ganho de informação, Gini ou SDR).
- Cresce de forma gulosa e precisa de critérios de parada e poda para evitar overfitting.
- Tipo de árvore mais comum: CART.
Referências
- BREIMAN, L.; FRIEDMAN, J.; OLSHEN, R.; STONE, C. Classification and Regression Trees. Wadsworth, 1984.
- FACELI, K. et al. Inteligência Artificial: uma abordagem de aprendizado de máquina. Rio de Janeiro: LTC, 2011.
- HASTIE, T.; TIBSHIRANI, R.; FRIEDMAN, J. The Elements of Statistical Learning. 2. ed. New York: Springer, 2009.
- JAMES, G.; WITTEN, D.; HASTIE, T.; TIBSHIRANI, R. An Introduction to Statistical Learning. 2. ed. New York: Springer, 2021.
- QUINLAN, J. R. C4.5: Programs for Machine Learning. Morgan Kaufmann, 1993.
- WITTEN, I. H.; FRANK, E.; HALL, M. A. Data Mining: Practical Machine Learning Tools and Techniques. 3. ed. Morgan Kaufmann, 2011.
