1
Árvores de Decisão
João Gama
Jgama@ncc.up.pt
2002 João Gama 2
Sumario
• Árvores de decisão
– Motivação
– Construção de uma árvore de decisão
• Critérios para seleccionar atributos
– Entropia
– Podar a árvore
• Estimativas de erro
– Extensões
• Árvores multivariadas
2
2002 João Gama 3
Árvores de Decisão
• Uma árvore de decisão utiliza uma estratégia de dividir-
para-conquistar:
– Um problema complexo é decomposto em sub-problemas mais
simples.
– Recursivamente a mesma estratégia é aplicada a cada sub-
problema.
• A capacidade de discriminação de uma árvore vem da:
– Divisão do espaço definido pelos atributos em sub-espaços.
– A cada sub-espaço é associada uma classe.
• Crescente interesse
– CART (Breiman, Friedman, et.al.)
– C4.5 (Quinlan)
–S
plus
, Statistica, SPSS
2002 João Gama 4
Árvores de decisão – Exemplo da partição do espaço dos atributos
3
2002 João Gama 5
O que é uma Arvore de Decisão?
• Representação por árvores de decisão:
– Cada nó de decisão contem um teste
num atributo.
– Cada ramo descendente corresponde a
um possível valor deste atributo.
– Cada Folha está associada a uma
classe.
– Cada percurso na arvore (da raiz à
folha) corresponde a uma regra de
classificação.
• No espaço definido pelos atributos:
– Cada folha corresponde a uma região
• Hiper-rectângulo
– A intersecção dos hiper-rectângulos é
vazio
– A união dos hiper-rectângulos é o
espaço completa.
2002 João Gama 6
Representação
• Uma árvore de decisão representa a disjunção de conjunções
de restrições nos valores dos atributos
– Cada ramo na árvore é uma conjunção de condições
– O conjunto de ramos na árvore são disjuntos
• DNF (disjuntive normal form)
– Qualquer função lógica pode ser representada por um árvore de
decisão.
•Exemplo a or b
b
a
-+
+
10
10
4
2002 João Gama 7
Construção de uma árvore de decisão
• A ideia base:
1. Escolher um atributo.
2. Estender a árvore adicionando um ramo para cada valor do
atributo.
3. Passar os exemplos para as folhas (tendo em conta o valor do
atributo escolhido)
4. Para cada folha
1. Se todos os exemplos são da mesma classe, associar essa classe à folha
2. Senão repetir os passos 1 a 4
2002 João Gama 8
Exemplos de Árvores de Decisão
• Atributos binários
1. And
1. Exercícios:
1. Representar Or, Xor
2.
A
0
0 1
1
1
0
111
001
010
000
BA ∧B
A
)()( D
C
B
A ∧∨∧
B
0
5
2002 João Gama 9
Exemplos:
Nã oSim9171Chuva
SimNã o7581Nublado
SimSim9072Nublado
SimSim7075Sol
SimNã o8075Chuva
SimNã o7069Sol
Nã oNã o9572Sol
SimSim6564Nublado
Nã oSim7065Chuva
SimNã o8068Chuva
SimNã o9670Chuva
SimNã o8683Nublado
Nã oSim9080Sol
Nã oNã o8585Sol
JogaventoHumidadeTempe ra t u.Tempo
Nã oSim9171Chuva
SimNã o7581Nublado
SimSim9072Nublado
SimSim7075Sol
SimNã o8075Chuva
SimNã o7069Sol
Nã oNã o9572Sol
SimSim6564Nublado
Nã oSim7065Chuva
SimNã o8068Chuva
SimNã o9670Chuva
SimNã o8683Nublado
Nã oSim9080Sol
Nã oNã o8585Sol
JogaventoHumidadeTempe ra t u.Tempo
Vento
Sim
Não
O conjunto de dados original:
Selecciona um atributo:
Qual o ‘melhor’ atributo?
2002 João Gama 10
Critérios para Escolha do Atributo
• Como medir a habilidade de um dado atributo discriminar
as classes?
• Existem muitas medidas.
Todas concordam em dois pontos:
– Uma divisão que mantêm as proporções de classes em todas as
partições é inútil.
– Uma divisão onde em cada partição todos os exemplos são da
mesma classe tem utilidade máxima.
10 / 10
10 / 10
5 / 5 5 / 5
10 / 0 0 / 10