Aprendizado de Maquina - Árvores de Decisão

Prévia do material em texto

LABIC
1MCM
Árvores de Decisão
Pode-se definir formalmente uma árvore de decisão 
como sendo:
1.um nó folha - ou nó resposta - que contém um nome 
de classe, ou
2.um nó não folha - ou nó de decisão - que contém um 
teste de atributo que, para cada um dos possíveis 
valores de atributo, tem um ramo para uma outra 
árvore de decisão
LABIC
2MCM
Representação da AD
1
Y
2X
falso
verdadeiro
falso verdadeiro
X
LABIC
3MCM
Árvores de Decisão (Cont)
Temperatura Região Tempo Barometro Predição
Acima 0°C Oeste Nublado Baixando Chuva
Abaixo 0°C Nublado Fixo Neve
Acima 0°C Leste Nublado Aumentando Sol
Acima 0°C Parcial Nubl. Fixo Sol
Limpo Fixo Sol
Acima 0°C Sul Limpo Baixando Chuva
0°C Norte Parcial Nubl. Fixo Neve
TemperaturaTemperatura RegiãoRegião TempoTempo BarometroBarometro PrediçãoPredição
Acima 0°CAcima 0°C OesteOeste NubladoNublado BaixandoBaixando ChuvaChuva
Abaixo 0°CAbaixo 0°C NubladoNublado FixoFixo NeveNeve
Acima 0°CAcima 0°C LesteLeste NubladoNublado Aumentando SolAumentando Sol
Acima 0°CAcima 0°C Parcial Parcial NublNubl. Fixo. Fixo SolSol
LimpoLimpo FixoFixo SolSol
Acima 0°CAcima 0°C SulSul LimpoLimpo BaixandoBaixando ChuvaChuva
0°C0°C NorteNorte Parcial Parcial NublNubl. Fixo. Fixo NeveNeve
Conjunto de exemplos experimentais observados
? Padrões no conjunto de amostras são 
identificados.
LABIC
4MCM
Árvores de Decisão (Cont)
Temperatura Região Tempo Barometro Predição
Acima 0°C Oeste Nublado Baixando Chuva
Abaixo 0°C Nublado Fixo Neve
Acima 0°C Leste Nublado Aumentando Sol
Acima 0°C Parcial Nubl. Fixo Sol
Limpo Fixo Sol
Acima 0°C Sul Limpo Baixando Chuva
0°C Norte Parcial Nubl. Fixo Neve
TemperaturaTemperatura RegiãoRegião TempoTempo BarometroBarometro PrediçãoPredição
Acima 0°CAcima 0°C OesteOeste NubladoNublado BaixandoBaixando ChuvaChuva
Abaixo 0°CAbaixo 0°C NubladoNublado FixoFixo NeveNeve
Acima 0°CAcima 0°C LesteLeste NubladoNublado Aumentando SolAumentando Sol
Acima 0°CAcima 0°C Parcial Parcial NublNubl. Fixo. Fixo SolSol
LimpoLimpo FixoFixo SolSol
Acima 0°CAcima 0°C SulSul LimpoLimpo BaixandoBaixando ChuvaChuva
0°C0°C NorteNorte Parcial Parcial NublNubl. Fixo. Fixo NeveNeve
BarômetroBarômetroBarômetro
Aumentando
Fixo
Baixando
TempoTempoTempo
Nublado
Parcial
Nubl.
Limpo
TempTempTemp
Acima 0°C 
0°C
Abaixo 0°C
Sol Neve Sol
Chuva Sol Sem dados
Neve
LABIC
5MCM
Árvores de Decisão (Cont)
Temperatura Região Tempo Barometro Predição
Acima 0°C Oeste Nublado Baixando Chuva
Abaixo 0°C Nublado Fixo Neve
Acima 0°C Leste Nublado Aumentando Sol
Acima 0°C Parcial Nubl. Fixo Sol
Limpo Fixo Sol
Acima 0°C Sul Limpo Baixando Chuva
0°C Norte Parcial Nubl. Fixo Neve
TemperaturaTemperatura RegiãoRegião TempoTempo BarometroBarometro PrediçãoPredição
Acima 0°CAcima 0°C OesteOeste NubladoNublado BaixandoBaixando ChuvaChuva
Abaixo 0°CAbaixo 0°C NubladoNublado FixoFixo NeveNeve
Acima 0°CAcima 0°C LesteLeste NubladoNublado Aumentando SolAumentando Sol
Acima 0°CAcima 0°C Parcial Parcial NublNubl. Fixo. Fixo SolSol
LimpoLimpo FixoFixo SolSol
Acima 0°CAcima 0°C SulSul LimpoLimpo BaixandoBaixando ChuvaChuva
0°C0°C NorteNorte Parcial Parcial NublNubl. Fixo. Fixo NeveNeve
BarômetroBarômetroBarômetro
Aumentando
Fixo
Baixando
TempoTempoTempo
Nublado
Parcial
Nubl.
Limpo
TempTempTemp
Acima 0°C 
0°C
Abaixo 0°C
Sol Neve Sol
Chuva Sol Sem dados
Neve
Escolhe atributo 
mais relevante 
primeiro
Escolhe atributo Escolhe atributo 
mais relevante mais relevante 
primeiroprimeiro
LABIC
6MCM
Árvores de Decisão (Cont)
Temperatura Região Tempo Barometro Predição
Acima 0°C Oeste Nublado Baixando Chuva
Abaixo 0°C Nublado Fixo Neve
Acima 0°C Leste Nublado Aumentando Sol
Acima 0°C Parcial Nubl. Fixo Sol
Limpo Fixo Sol
Acima 0°C Sul Limpo Baixando Chuva
0°C Norte Parcial Nubl. Fixo Neve
TemperaturaTemperatura RegiãoRegião TempoTempo BarometroBarometro PrediçãoPredição
Acima 0°CAcima 0°C OesteOeste NubladoNublado BaixandoBaixando ChuvaChuva
Abaixo 0°CAbaixo 0°C NubladoNublado FixoFixo NeveNeve
Acima 0°CAcima 0°C LesteLeste NubladoNublado Aumentando SolAumentando Sol
Acima 0°CAcima 0°C Parcial Parcial NublNubl. Fixo. Fixo SolSol
LimpoLimpo FixoFixo SolSol
Acima 0°CAcima 0°C SulSul LimpoLimpo BaixandoBaixando ChuvaChuva
0°C0°C NorteNorte Parcial Parcial NublNubl. Fixo. Fixo NeveNeve
BarômetroBarômetroBarômetro
Aumentando
Fixo
Baixando
TempoTempoTempo
Nublado
Parcial
Nubl.
Limpo
TempTempTemp
Acima 0°C 
0°C
Abaixo 0°C
Sol Neve Sol
Chuva Sol Sem dados
Neve
Escolhe atributo 
mais relevante 
primeiro
Escolhe atributo Escolhe atributo 
mais relevante mais relevante 
primeiroprimeiro
Exclui 
Fatores 
Irrelevantes 
(Região)
Exclui Exclui 
Fatores Fatores 
Irrelevantes Irrelevantes 
(Região)(Região)
LABIC
7MCM
Árvores de Decisão (Cont)
Temperatura Região Tempo Barometro Predição
Acima 0°C Oeste Nublado Baixando Chuva
Abaixo 0°C Nublado Fixo Neve
Acima 0°C Leste Nublado Aumentando Sol
Acima 0°C Parcial Nubl. Fixo Sol
Limpo Fixo Sol
Acima 0°C Sul Limpo Baixando Chuva
0°C Norte Parcial Nubl. Fixo Neve
TemperaturaTemperatura RegiãoRegião TempoTempo BarometroBarometro PrediçãoPredição
Acima 0°CAcima 0°C OesteOeste NubladoNublado BaixandoBaixando ChuvaChuva
Abaixo 0°CAbaixo 0°C NubladoNublado FixoFixo NeveNeve
Acima 0°CAcima 0°C LesteLeste NubladoNublado Aumentando SolAumentando Sol
Acima 0°CAcima 0°C Parcial Parcial NublNubl. Fixo. Fixo SolSol
LimpoLimpo FixoFixo SolSol
Acima 0°CAcima 0°C SulSul LimpoLimpo BaixandoBaixando ChuvaChuva
0°C0°C NorteNorte Parcial Parcial NublNubl. Fixo. Fixo NeveNeve
BarômetroBarômetroBarômetro
Aumentando
Fixo
Baixando
TempoTempoTempo
Nublado
Parcial
Nubl.
Limpo
TempTempTemp
Acima 0°C 
0°C
Abaixo 0°C
Sol Neve Sol
Chuva Sol Sem dados
Neve
Escolhe atributo 
mais relevante 
primeiro
Escolhe atributo Escolhe atributo 
mais relevante mais relevante 
primeiroprimeiro
Exclui 
Fatores 
Irrelevantes 
(Região)
Exclui Exclui 
Fatores Fatores 
Irrelevantes Irrelevantes 
(Região)(Região)
Nenhuma solução 
descoberta: (Mais 
exemplos requeridos)
Nenhuma solução Nenhuma solução 
descoberta: (Mais descoberta: (Mais 
exemplos requeridos)exemplos requeridos)
LABIC
8MCM
Regras de Decisão
Se Barômetro = Aumentando
então Sol.
Se Barômetro = Fixo e
Tempo = Nublado
então Neve.
Se Barômetro = Fixo e
Tempo = Parcialmente Nublado e
Temperatura = 0° C
então Neve.
LABIC
9MCM
Algoritmos da Família TDIDT
TDIDT TDIDT TTopop DDownown IInductionnduction ofof DDecisionecision
TTreesrees
Esta família agrupa os algoritmos e sistemas 
mais representativos que utilizam como 
algoritmo básico de aprendizado o ID3.
Algoritmos: ID3, ID3’, C4, C4.5, ID4, ID5, etc.
LABIC
10MCM
Estágios do Processo de 
Aprendizado da Família TDIDT
1.construção da árvore de decisão para 
classificar corretamente todos os 
exemplos
2.poda da árvore de decisão para eliminar 
subárvores não confiáveis
3.processamento da árvore podada para 
melhorar a sua legibilidade - construção 
de regras a partir da árvore
LABIC
11MCM
Árvores de Decisão
sexo cirurgia TSH TFI TT4 TI classe
f
f
m
f
m
...
f
f
v
f
f
...
5.8
7.3
8.8
6.9
5.4
...
66.2
70.2
60.2
65.4
65.2
...
156.2
152.9
148.4
132.7
150.9
...
f
v
f
f
f
...
neg
neg
hipo_prim
hipo_comp
neg
...
LABIC
12MCM
Árvores de Decisão (Cont)
TSH
neg FTI
hipo_prim TI
neg cirurgia
neg TT4
hipo_comp neg
<6.05 >6.05
<64.5 >64.5
v f
v f
<150.5>150.5
LABIC
13MCM
Regras de Decisão
1. Se
então
2. Se e
então
...
6. Se e
e
e
e
então
TSH < 6.05
neg
neg
hipo_prim
TSH > 6.05
TSH > 6.05
FTI < 64.5
FTI > 64.5
TI = f
cirurgia = f
TT4 > 150.5
LABIC
14MCM
Características Gerais dos 
Sistemas TDIDT
? Sistemas de propósito geral com o objetivo de classificar objetos: 
Eles produzem regras ou descrições de um determinado 
número de classes de objetos. Quando novos objetos são 
observados, estas regras devem predizer a qual classe cada 
um deles pertence.
? Representação do Conhecimento na forma de árvores de decisão. 
Em geral, realizam aprendizado não incremental.
? Constroem a árvore de decisão em forma top-down.
? Os exemplos, a partir dos quais são geradas as regras de 
classificação, são conhecidos somente através dos valores de um 
conjunto de atributos. Por sua vez, as árvores de decisão são 
construídas em função destes mesmos atributos.
LABIC
15MCM
Esquema Geral dos Algoritmos de 
Aprendizado por Exemplos
1. pré-processamento dos exemplos de aprendizado no qual 
deve ser considerado o tratamento de:
? atributos numéricos;
? atributos com valores desconhecidos;
? valores irrelevantes;
? valores sem significado.
O processo de aprendizado e classificação é dividido em:
2. construção de regras de classificação envolve:
? escolha do critério de seleção do melhor atributo na 
construção da árvore de decisão
? tratamento de domínios com ruído ou domínios 
incompletos
? poda na árvore de decisão
Existente para 
todos os paradigmas
Específico para 
Simbólico
LABIC
16MCM
Vantagens
? Podem adquirir e representar facilmente conceitos 
disjuntos
? Podem manusear dados com ruído
(dados com erros ou incertezas)
? Executam pouca busca
? A simplicidade do formato de representação é 
contrabalanceada por sua eficiência
? Têm obtido muito sucesso em diversas áreas de 
aplicação - vários deles estão disponíveis 
comercialmente
LABIC
17MCM
Desvantagens
? Um mesmo conceito pode ser representado por 
várias árvores de decisão 
? É difícil entender um conceito representado como 
uma árvore de decisão grande
? Limitados a uma linguagem descritiva baseada em 
atributos-valores
	Árvores de Decisão
	Representação da AD
	Árvores de Decisão (Cont)
	Árvores de Decisão (Cont)
	Árvores de Decisão (Cont)
	Árvores de Decisão (Cont)
	Árvores de Decisão (Cont)
	Regras de Decisão
	Algoritmos da Família TDIDT
	Estágios do Processo de Aprendizado da Família TDIDT
	Árvores de Decisão
	Árvores de Decisão (Cont)
	Regras de Decisão
	Características Gerais dos Sistemas TDIDT
	Esquema Geral dos Algoritmos de Aprendizado por Exemplos
	Vantagens
	Desvantagens