Árvores de Decisão
Valmir Macário
Introdução
 Seres
humanos manipulam símbolos
em alto nível
 Tomamos
decisões a partir de regras
e modelos que generalizamos
 Realizamos
inferências a partir dos
dados que temos e do nosso
conhecimento explícito
Relembrando...
Aprendizagem Indutiva

Inferência de uma regra geral (hipótese) a
partir de exemplos particulares

Precisão diretamente proporcional à
quantidade / qualidade dos exemplos
Conhecimento Simbólico

Conhecimento adquirido pode ser
representado em linguagens de alto nível
◦ De forma legível e interpretável por humanos

Motivações
◦ Compreender um problema (mais do que
obter modelos precisos)
◦ Justificar decisões
◦ Incorporar novo conhecimento
Aprendizagem Indutiva
Classificação

Incremental: atualiza hipótese a cada
novo exemplo
◦ Mais flexível
◦ A ordem de apresentação é importante

Não incremental: gerada a partir de
todo conjunto de exemplo.
◦ Mais eficiente e prática
Árvore de Decisão
 Entrada:
◦ Conjunto de atributos
 Discretos
 Contínuos
 Saída
◦ Uma “decisão”
Árvore de Decisão

Uma árvore de decisão utiliza uma estratégia
de dividir-para-conquistar:
◦ Um problema complexo é decomposto em subproblemas mais simples.
◦ Recursivamente a mesma estratégia é aplicada a
cada sub-problema.

A capacidade de discriminação de uma
árvore tem origem na:
◦ Divisão do espaço definido pelos atributos em
sub-espaços.
◦ A cada sub-espaço é associada uma classe.
Árvores de Decisão

Cada nó interno (não-terminal)
contém um teste sobre os valores
de um dado atributo

Folhas da árvore (nós terminais) são
associadas às classes
Cores
Não
Filme
Ruim
(p = 0.7)
Musical
Filme
Ruim
(p = 1.0)
Sim
◦ Comumente, acompanhadas com graus
de confiança
Gênero
Ação
Filme
Bom
(p = 0.8)
Drama
Filme
Ruim
(p = 0.6)

Novas instâncias classificadas
percorrendo a árvore a partir da
raiz até as folhas
Árvores de Decisão
- Construção

Árvore de decisão construída de forma recursiva
da raiz para as folhas (top-down)
◦ A cada nó, é escolhido um teste que separe melhor
os exemplos de classes diferentes
 Maximização de critério de separação
◦ Nós terminais são criados ao atingir um critério de
parada
 Ex.: todos os exemplos do nó pertencem à uma só classe
Árvores de Decisão
- Construção

AD(Exemplos:E; Atributos:A; Alvo:C)
◦ Crie nó_raiz
◦ SE Critério_de_Parada
ENTÃO Crie nó terminal associada à classe
mais freqüente
◦ SENÃO Encontre atributo aj cujo teste de decisão
maximize a separação dos exemplos que
atinjem o nó
- PARA CADA valor v do teste
adicione nova sub-árvore
- Sub_arvore = AE(E[aj = v], A – {aj}, C)
Exemplo: Play Tennis
Day
D1
D2
D3
D4
D5
D6
D7
D8
D9
D10
D11
D12
D13
D14
Outlook
Sunny
Sunny
Overcast
Rain
Rain
Rain
Overcast
Sunny
Sunny
Rain
Sunny
Overcast
Overcast
Rain
Temperature Humidity
Hot
High
Hot
High
Hot
High
Mild
High
Cool
Normal
Cool
Normal
Cool
Normal
Mild
High
Cool
Normal
Mild
Normal
Mild
Normal
Mild
High
Hot
Normal
Mild
High
Wind
Weak
Strong
Weak
Weak
Weak
Strong
Strong
Weak
Weak
Weak
Strong
Weak
Weak
Strong
PlayTennis
No
No
Yes
Yes
Yes
No
Yes
No
Yes
Yes
Yes
Yes
Yes
No
Árvore de Decisão de Classificação
Próximos
Dias
Dados
(dias anteriores)
Aprendizado
Classificador
Play Tennis?
Árvore de Decisão:
Play Tennis
Tempo
Ensolarado
Chuvoso
Nublado
Humidade
Alta
Normal
Não
Sim
Yes
Vento
Forte
Não
Fraco
Sim
Árvore de Decisão:
Play Tennis
Atributos
Tempo
Ensolarado
Chuvoso
Nublado
Humidade
Alta
Normal
Não
Sim
Yes
Vento
Forte
Não
Fraco
Sim
Árvore de Decisão:
Play Tennis
Tempo
Valores
Ensolarado
Chuvoso
Nublado
Humidade
Alta
Normal
Não
Sim
Yes
Vento
Forte
Não
Fraco
Sim
Árvore de Decisão:
Play Tennis
Tempo
Ensolarado
Chuvoso
Nublado
Humidade
Yes
Alta
Normal
Não
Sim
Classificação
Vento
Forte
Não
Fraco
Sim
Play Tennis
Cada percurso na árvore (da raiz à folha)
corresponde a uma regra de classificação
 Se:

◦ (Tempo = Ensolarado  Humidade = Normal)
◦  (Tempo = Nublado)
◦  (Tempo = Chuvoso  Vento = Fraco)

Então:
◦ Play Tennis? Sim
Regras

Na forma: if-then
IF Outlook=Sunny  Humidity=Normal
THEN PlayTennis=Yes
IF Outlook=Overcast THEN
PlayTennis=Yes
IF Outlook=Rain  Wind=Weak THEN
PlayTennis=Yes
IF Outlook=Sunny  Humidity=High THEN
PlayTennis=No
IF Outlook=Rain  Wind=Strong THEN
PlayTennis=Yes
Árvores de Decisão
Escolha de testes de atributos

Como escolher o melhor atributo?
◦ Quantidade de Informações
 (Shannon Weaver – 1949)
◦ Entropia(S) = especifica o número mínimo de
bits de informação necessário para codificar
uma classificação de um membro arbitrário de
S.
Entropia

S é uma amostra dos exemplos de treinamento

p é a proporção de exemplos positivos em S

p⊝ é a proporção de exemplos negativos em S

Entropia mede a “impureza” de S:
Entropia(S)= - p log2 p - p⊝ log2 p⊝
Árvores de Decisão
Escolha de testes de atributos

Quantidade de Informações de um
problema que pode tomar n valores:
n
I(P(v1 ), P(v2),...,P(vn))    P(vi ) log 2 P(vi )
i 1

Exemplo: no caso do lançamento de
uma moeda:
1
1 1
1
1 1
I  ,    log 2  log 2  1 bit
2
2 2
2
2 2
Árvores de Decisão
Escolha de testes de atributos

Para uma árvore de decisão com 2 possibilidades de
resposta:
 p
n 
p
p
n
n
  
I 
,
log 2

log 2
pn
pn pn
pn
 pn pn


Teste em um único atributo não nos dará informações
suficientes
A construção de uma árvore de decisão é guiada
pelo objetivo de diminuir a aleatoriedade ou dificuldade
de previsão, da variável que define as classes.
Árvores de Decisão
Escolha de testes de atributos

Um atributo escolhido A divide o conjunto de
treinamento em sub-conjuntos E1, E2,..Ev de
acordo com seus valores para A, onde A tem v
valores distintos
pi  ni  pi
ni 

Restante(A)  
I 
,
i 1 p  n  pi  ni pi  ni 
v

Ganho:
 p
n 
  Restante
Ganho( A)  I 
,
 pn pn
 Melhor atributo
Maior Ganho
Árvores de Decisão
Escolha de testes de atributos

Ganho de Informação (Information Gain)
◦ O ganho de um atributo/teste é definido pela redução
de Entropia proporcionada após a separação dos
exemplos do nó
InfoGain(a, C , E )  Ent (C , E )  
vi
Entropia do nó pai
E[ a vi ]
E
 Ent ( E , E[ a vi ] )
Entropia do nó filho
ponderada pelo número
de exemplos do nó
Árvores de Decisão
Escolha de testes de atributos
Propriedades da Entropia:
 Se todos os exemplos de E são da mesma classe então entropia
assume valor mínimo
 Ent(C,E) = 0
 Se todos as classes têm o mesmo número de exemplos em E
então entropia assume valor máximo

Qual o melhor atributo?
◦
◦
◦
◦
Ganho(exemplos,Tempo)=0.246
MAX !
Ganho(exemplos,Humidade)=0.151
Ganho(exemplos,Vento)=0.048
Ganho(exemplos,Temperatura)=0.029
Árvores de Decisão
Escolha de testes de atributos

Lidando com atributos numéricos:
◦ Testes são da forma: atributo > valor
◦ Procedimento:
 Ordene os valores do atributo observados no conjunto de
treinamento
 Considere a média de valores adjacentes como possíveis
testes
 Por eficiência, considere apenas os valores onde são
observadas mudanças de classe
54
Temperatura:
Classe:
40
A
48
A
95
60
B
72
B
80
B
Valores candidatos
90
A
Árvores de Decisão - Exemplo

Raíz: [9+; 5-]
◦ Entropia = - 9/14*log2(9/14) - 5/14*log2(5/14) = 0.940

Considerando teste com atributo Outlook
◦ Outlook = Sunny: [2+;3-]
 Entropia = - 2/5*log2(2/5) - 3/5*log2(3/5) = 0.971
◦ Outlook = Overcast: [4+;0-]
 Entropia = - 4/4*log2(4/4) - 0/4*log2(0/4) = 0.0
◦ Outlook = Rain: [3+;2-]
 Entropia = - 3/5*log2(3/5) - 2/5*log2(2/5) = 0.971
◦ Média: 5/14*0.971 + 4/14*0.0 + 5/14*0.971 = 0.694
◦ Ganho de Informação: 0.940 - 0.694 = 0.246
Árvores de Decisão - Exemplo

Considerando os outros atributos:
◦
◦
◦
◦
Ganho(Outlook, D) = 0.246
Ganho(Humit., D) = 0.151
Ganho(Wind, D) = 0.048
Ganho(Temp., D) = 0.029
◦ Atributo Outlook é o escolhido na raíz
Árvores de Decisão - Exemplo
[9+; 5-]
Entropia: 0.940
Outlook
Rain
Sunny
[2+; 3-]
Entropia: 0.971
Overcast
?
Humit.?
Temp.?
Wind?
Yes
[4+; 0-]
[3+; 2-]
Entropia: 0.971
?
Humit.?
Temp.?
Wind?
Árvores de Decisão
Escolha de testes de atributos
Chuvoso
Tempo
{D4,D5,D6,D10,D14} [3+, 2-] E > 0 ???
Nublado
{D3,D7,D12,D13}
[4+, 0-] E = 0 OK – Classif.: Sim
{D1,D2,D8,D9,D11}
[2+, 3-] E > 0 ???
Sol
I(2/5, 3/5) = 0,97

Próximos atributos a serem testados

Ganho(exemplossol, Humidade) = 0.97-(3/5)0-(2/5)0 = 0.970
MAX !

Ganho(exemplossol,Temperatura) = 0.97-(2/5)0-(2/5)1-(1/5)0 = 0.570

Ganho(exemplossol,Vento) = 0.97-(2/5)1-(3/5)0.918 = 0.019
Árvores de Decisão
– Critérios de Parada

Totalidade (ou alternativamente, a maioria) do
exemplos do nó pertencem a mesma classe

Profundidade máxima para o nó

Número mínimo de exemplos no nó

Ganho pouco significativo no critério de separação
◦ Obs.: valores definidos como parâmetros do aprendizado
Avaliação do desempenho do algoritmo
de aprendizagem

Curva de Aprendizado:
Critérios para escolha da melhor
árvore

Obter estimativas confiáveis do erro a
partir do conjunto de treinamento.

Otimizar o erro num conjunto de
validação independente do utilizado para
construir a árvore.

Minimizar:
◦ erro no treinamento
◦ dimensão da árvore
Ruído e Superadaptação

Algoritmo tenta modelar ruído nos dados

Árvore gerada não funciona bem com
dados não conhecidos
◦ Não é suficientemente generalizada

Solução: Poda de atributos irrelevantes
Superadaptação (overfitting)

O algoritmo de partição recursiva do conjunto de
dados gera estruturas que podem obter um ajuste
aos exemplos de treinamento perfeito.
◦ Em domínios sem ruído o número de erros no conjunto
de treinamento pode ser 0.

Em problemas com ruído esta capacidade é
problemática:
◦ A partir de uma certa profundidade as decisões tomadas
são baseadas em pequenos conjuntos de exemplos.
◦ A capacidade de generalização para exemplos não
utilizados no crescimento da árvore diminui.
Variação do erro com o
número de nós
Superadaptação (overfitting)

Ockham’s razor: preferência pela hipótese
mais simples.
◦ Existem menos hipóteses simples do que
complexas.
◦ Se uma hipótese simples explica os dados é
pouco provável que seja uma coincidência.
◦ Uma hipótese complexa pode explicar os
dados apenas por coincidência.
Poda (Prunning)
Forma de simplificar a árvore
 Duas possibilidades:

◦ Pre-pruning
 Parar o crescimento da árvore mais cedo
◦ Post-pruning
 Costruir uma árvore completa e podar a árvore
 “Growing and pruning is slower but more reliable”
Algoritmo básico de poda
1.
Percorre a árvore em profundidade
2.
Para cada nó de decisão calcula:
◦
◦
3.
Erro no nó
Soma dos erros nos nós descendentes
Se o erro no nó é menor ou igual à
soma dos erros dos nós descendentes, o
nó é transformado em folha.
Um algoritmo básico de
pruning


Exemplo do nó B:
◦ Erro no nó = 2
◦ Soma dos erros nos
nós descendentes:
 2+0
◦ Transforma o nó em
folha
 Elimina os nós
descendentes.
Exemplo do nó B:
◦ Erro no nó = 2
◦ Soma dos erros nos
nós descendentes:
 2+0
◦ Transforma o nó em
folha
 Elimina os nós
descendentes.
Utilização Prática
As arvores de decisão costumam ser o
primeiro método experimentado quando
o método de classificação tem de ser
extraído de um conjunto de dados.
 A saída de uma árvore de decisão é de
fácil entendimento para um ser humano.

◦ Exigência legal para decisões financeiras.

Propriedade não compartilhada por redes
neurais.
Casos de sucesso

Sistema GASOIL (BP)
◦ Usado para determinar sistemas de separação
de gás, óleo e água
◦ Aproximadamente 2500 regras
◦ Se tivesse sido feito manualmente levaria 10
pessoa-anos
◦ Levou 100 pessoa-dias utilizando árvore de
decisão
Casos de sucesso

Pilotos Automáticos
◦ Mapeamentos de estados do sistema para as
ações corretas
◦ Testes realizados com simuladores do Cessna
◦ 20.000 exemplos criados a partir da
observação de pilotos treinados utilizando o
simulador
◦ O sistema gerado a partir da árvore de
decisão cometia menos erros que pilotos
humanos
Árvores de Decisão
- Discussão

Vantagens:
◦ Geram modelos dos dados (i.e., método eager)
◦ Conhecimento interpretável
◦ Pouca sensibilidade a atributos irrelevantes
 Uma vez que implementam seleção de atributos

Desvantagens:
◦ Em geral, menos precisos comparados com
algoritmos como redes neurais e SVMs
Árvores de Decisão

Diferentes versões de algoritmos podem ser
encontradas na literatura
◦ Algoritmo ID3 – versão básica de AD para atributos
categóricos, com InfoGain
◦ Algoritmo C4.5 – extensão do ID3 para atributos
categóricos e numéricos, com GainRatio
Árvores de Decisão
- no WEKA
Árvores de Decisão
- no WEKA
Parâmetros Importantes
• confidenceFactor: ?????
• minNumObj: número
mínimo de exemplos em uma
folha
• numFold: controla a
quantidade de exemplos de
validação usados para poda
Árvores de Decisão
- no WEKA
Árvore Gerada
Referências

T. Mitchell, Machine Learning, Cap. 3, 1997.

M. Monard, J. Baranauskas, Indução de Regras e
Árvores de Decisão, Sistemas Inteligentes, Cap.
5, 2005.

J. R. Quinlan, Induction of Decision Trees,
Machine Learning,Vol.1, N.1, 1986.