ÁRVORES de DECISÃOpaginapessoal.utfpr.edu.br/kathya/Disciplinas/sistemas...12 ÁRVORES de DECISÃO • Método para inferência indutiva –Auxilia a predizer a classe de um objeto

1

• Inferência indutiva de fatos providos por um professor ou ambiente. – O estudo e modelagem desta forma de aprendizagem é um

dos tópicos centrais de aprendizagem de máquina.

– Em aprendizagem indutiva, um programa aprende a classificar objetos baseados nos rótulos que lhe são apresentados.

– Deve tentar recuperar a função desconhecida ou uma aproximação.

– Inferência de uma regra geral (hipótese) a partir de exemplos particulares

– Precisão diretamente proporcional à quantidade de exemplos

Aprendizagem indutiva

2

• Dada uma coleção de exemplos de f, retornar uma função h que se aproxime de f.

• A função h é chamada hipótese

– Não é fácil saber se uma h específica é uma boa aproximação de f

– Uma boa h irá generalizar bem – prever corretamente exemplos ainda não vistos

– Esse é o problema fundamental da indução

Aprendizagem indutiva

3

Aprendizagem Indutiva

• Atividade de um agente =

função f (percepção) ação

• Idéia:

–aprender, a partir de exemplos (x,f(x)), representação de uma função h que aproxima f

4

• Exemplo: Ajustar uma função de uma única variável a alguns pontos de dados – Exemplos são pares (x, f(x)) de números reais


5

• Exemplo:


6

• Exemplo:


7

• Exemplo:


8

• Exemplo:


A verdadeira f é desconhecida, mas existem muitas opções para h. Sem contar

com mais conhecimento, não há razão que nos faça preferir uma das opções.

9


• Aprender de uma vez ou aos poucos?

– Incremental (on-line): atualiza hipótese a cada novo exemplo

• mais flexível, ... Porém a ordem de apresentação é importante (backtracking)

–não incremental (off-line): gerada a partir de todo conjunto de exemplos

• mais eficiente e prática

• mais usado

10

Modelo do Agente Aprendiz (on-line)

t

sensores

efetuadores

Agente

Gerador de problemas

crítico

elemento de aprendizagem

avaliação

objetivos de

aprendizagem

elemento ator

trocas

conhecimento

a m

b i e

n t

e

t + 1

11

Modelo do Agente Aprendiz (off-line)

Algoritmo de Aprendizagem

elemento ator

exemplos

conhecimento

sensores

efetuadores a m

b i e

n t e

Tre

inam

ento

U

so

12

ÁRVORES de DECISÃO

• Método para inferência indutiva – Auxilia a predizer a classe de um objeto em estudo em base a

um treinamento prévio.

– Uma árvore representa uma função discreta para aproximar/representar os dados de treinamento

– Uma das formas mais simples de algoritmos de aprendizagem

– Árvores de decisão classificam instâncias ordenando-as da raiz para algúm nó folha.

• Entrada: um objeto ou situação descrito por um conjunto de propriedades ou atributos;

• Saída: uma decisão.

13



• Cada nó de decisão (ou nó não folha) contem um teste de atributo

• Cada ramo descendente corresponde a um possível valor deste atributo

• Cada nó folha (ou nó resposta) esta associada a uma classe

• Cada percurso na árvore (da raiz à folha) corresponde a uma regra de classificação

14

15

Árvores de decisão: Conceitos

• Exemplo - descrito pelos valores dos atributos e o valor do predicado meta(p).

• Valor do predicado meta é chamado classificação do exemplo.

• Se o predicado meta é verdadeiro para algum exemplo: é exemplo positivo(+), caso contrário é exemplo negativo(-).

• O conjunto completo de exemplos é chamado conjunto de treinamento.

• Classificação é a aplicação do predicado meta (p) a um exemplo

• Objetivo da aprendizagem

– gerar a descrição d de p segundo os atributos dados

– d deve ser consistente (cobre todos positivos e exclui todos negativos) e preditiva/geral (vai além da memorização)

– d deve ser a mais simples possível

16

Expressividade de árvores de decisão

• Qualquer função booleana pode ser escrita como uma árvore de decisão.

17

Exemplo do Restaurante: Esperar ou não uma mesa?

• Atributos disponíveis:

– Alternativa: há um outro restaurante apropriado por perto?

– Bar: o restaurante tem uma área de bar confortável para esperar?

– Sex/Sab: verdadeiro às sextas e sábados

– Faminto: Estamos com fome?

– Clientes: Quantas pessoas estão no restaurante?

– Preço: A faixa de preços do restaurante

– Chovendo: Está chovendo do lado de fora?

– Reserva: Fizemos uma reserva?

– Tipo: Qual o tipo do restaurante?

– Espera estimada: A espera estimada pelo gerente


18

Ex Alt Bar Sex Fam Cli Pre Chu Res Tipo Tem Meta

X1 Sim Não Não Sim Alg $$$ Não Sim Fra 0-10 Sim

X2 Sim Não Não Sim Che $ Não Não Tai 30-60 Não

X3 Não Sim Não Não Alg $ Não Não Ham 0-10 Sim

X4 Sim Não Sim Sim Che $ Sim Não Tai 10-30 Sim

X5 Sim Não Sim Não Che $$$ Não Sim Fra >60 Não

X6 Não Sim Não Sim Alg $$ Sim Sim Ita 0-10 Sim

X7 Não Sim Não Não Ne $ Sim Não Ham 0-10 Não

X8 Não Não Não Sim Alg $$ Sim Sim Tai 0-10 Sim

X9 Não Sim Sim Não Che $ Sim Não Ham >60 Não

X10 Sim Sim Sim Sim Che $$$ Não Sim Ita 10-30 Não

X11 Não Não Não Não Ne $ Não Não Tai 0-10 Não

X12 Sim Sim Sim Sim Che $ Não Não Ham 30-60 Sim

Conjunto de treinamento para o exemplo do restaurante

19

Clientes?

Tem Bar?

É Sex/Sab? Fiz Reserva?

Faminto? Alternativa:

Rest. Perto?

EsperaEstimada?

Chovendo?

Não Não

Não

Não

Não

Sim Sim Sim

Sim

Sim

Sim

Alternativa: Rest. Perto?

Sim Sim

Nenhum alguns cheio

>60 30-60 10-30 0-10

Não Sim Não Sim

Não Sim Não Sim Não Sim

Não Sim Não Sim

20


• Qualquer hipótese de árvore de decisão específica para o predicado meta VaiEsperar pode ser vista como uma asserção da forma:

∀x VaiEsperar(x) (P1(x) v P2(x) v ... v Pn(x))

• Cada condição Pi(x) é uma conjunção de testes que pode corresponder a um caminho da raiz até uma folha da árvore com resultado positivo.

• A árvore pode ser representada por um conjunto de conjunções que implicam uma conclusão positiva e estas correspondem aos caminhos que vão da raiz até o nó folha Sim.

∀rClientes (r, Cheio) TempoEsperaEstimado(r, 10-30) TerFome(r,N) Esperará(r)

21

Indução de árvores de decisão

• Algoritmo de aprendizagem em árvore de decisão:

– Top-down (dirigida a modelo) - conjunto de possíveis

generalizações na tentativa de encontrar as melhores hipóteses que satisfaçam certos requerimentos;

– A idéia é testar o atributo mais importante – aquele que faz a maior diferença para a classificação de um exemplo.

– Obter a classificação correta com pequeno nº de testes = caminhos curtos e árvore pequena.

Limitação: A árvore memoriza as observações. Ela não extrai

qualquer padrão dos exemplos e, assim, não podemos esperar que

ela esteja apta a extrapolar para exemplos não vistos antes.

22


A idéia base: 1. Começar com todos os exemplos de treino

2. Escolher o teste (atributo) que melhor divide os exemplos, ou seja agrupar exemplos da mesma classe ou exemplos semelhantes

3. Para o atributo escolhido adicionar um ramo (nó filho) para cada valor possível do atributo.

4. Passar os exemplos para as folhas (cada nó filho) tendo em conta o valor do atributo escolhido

5. Para cada folha • Se todos os exemplos são da mesma classe, associar essa classe à

folha (filhos “puros” pois cada atributo ‘x’ tem o mesmo valor em todos os exemplos)

• Senão repetir os passos 1 a 4 ( criar novos ramos para cada classe)

23


• Exemplo Cachaçaria

• predicado-objetivo: vaiACachaçaria

– Atributos considerados:

• Sono: Estou com sono?

• Transporte: Tenho como ir de carro? Carona? etc.

• UTFPR: Devo estar amanhã cedo na UTFPR?

• Álcool: Estou precisando de álcool?

• Sair: Quero sair de casa?

• Fome: Estou com fome?

24


• Atributos: (Sono, Transporte, UTFPR, Álcool, Sair, Fome)-> propriedade-objetivo – E01: (Pouco,Carro,Sim,Sim,Não,Sim) -> Sim! – E02: (Pouco,Carona,Não,Não,Sim,Sim) -> Sim! – E03: (Sim,Carro,Não,Sim,Sim,Sim) -> Não. – E04: (Pouco,Carona,Não,Não,Sim,Não) -> Sim! – E05: (Sim,Outros,Sim,Sim,Sim,Não) -> Não. – E06: (Pouco,Outros,Não,Sim,Não,Sim) -> Não. – E07: (Pouco,Carro,Sim,Não,Sim,Sim) -> Sim! – E08: (Pouco,Carona,Não,Não,Não,Sim) -> Não. – E09: (Sim,Carro,Não,Sim,Sim,Não) -> Não. – E10: (Não,Outros,Sim,Sim,Sim,Sim) -> Sim! – E11: (Não,Carro,Não,Sim,Sim,Não) -> Sim! – E12: (Não,Carona,Não,Sim,Sim,Sim) -> Sim!

25


Sono?

UTFPR? Não. UTFPR?

Carona

Sim. Não.

Quer sair? Não.

Sim. Meio de

transporte?

Não.

Sim. Precisa de

álcool?

Sim. Não.

26


• Escolha do melhor atributo

– O que discrimina o maior número de exemplos

• Candidatos:

– Transporte: Não classifica imediatamente nenhum dos exemplos

– Sono: Classifica de imediato 6 dos 12 exemplos

– ...

27

Indução de árvores de decisão atributo Transporte

Transporte?

carro outros

+:E01,E02,E04,E07,E10,E11,E12

- :E03,E05,E06,E08,E09

carona

+: E10

-: E05,E06

+: E01,E07,E11

-: E03,E09

+: E02,E04,E12

-: E08

28

Indução de árvores de decisão atributo Sono

Sono?

sim pouco não

+:E01,E02,E04,E07,E10,E11,E12

- :E03,E05,E06,E08,E09

+: E1,E2,E4, E7

-: E6,E8

+: - - -

-: E3, E5, E9

+: E10,E11,E12

-: - - -

Escolha dos atributos preditivos para os nós da árvore

• Como medir a habilidade de um dado atributo discriminar as classes?

• Existem muitas medidas e 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.

30

• Como escolher o melhor atributo?

– Entropia

– Ganho


31

Entropia

• A entropia de um conjunto pode ser definida como sendo uma medida do grau de impureza do conjunto.

• Este conceito define a medida de "falta de informação", mais precisamente o número de bits necessários, em média, para representar a informação em falta, usando codificação ótima.

• Entropia é uma medida da aleatoriedade de uma variável.


32

Entropia

• Dado um conjunto S, com instâncias pertencentes à classe i, com probabilidade pi, tem-se:

• Pode-se ter:

– S é o conjunto de exemplo de treino;

– p+ é a porção de exemplos positivos;

– p- é a porção de exemplos negativos.


c

i iippSE

1 2log)(

ppppSE

22loglog)(

33

Entropia

– A Entropia(S) tem máximo (log2 i) se pi = pj para qualquer i j

– A Entropia(S) = 0 se existe um i tal que pi = 1

– É assumido que 0 * log2 0 = 0


c

i iippSE

1 2log)(

ppppSE

22loglog)(

34


Entropia

ppppSEntropia 22 loglog)(

Variação da Entropia a medida que a proporção de positivos e negativos se altera.

35

Exemplo:

• Se p é 1, o destinatário sabe que o exemplo selecionado será positivo – Nenhuma mensagem precisa ser enviada – Entropia é 0 (mínima)

• Se p é 0.5, um bit é necessário para indicar se o exemplo

selecionado é ou – Entropia é 1 (máxima)


36

Ganho • Define a redução na entropia.

• Ganho(S,A) significa a redução esperada na entropia de S, ordenado pelo atributo A.

• Para responder à pergunta anterior, "Como escolher o melhor atributo?" é usado o ganho.

– Em cada iteração do algoritmo é escolhido o atributo que apresente uma maior ganho.


)(

)( ),( Avaloresv v

v SES

SSEASGanho

Obs.: valores(A) é o conjunto de todos possíveis valores para o atributo A, e Sv é o subconjunto de S para qual o atributo A tem valor v.

37

• Entropia - medida da impureza do conjunto de treino. – Assumindo o valor máximo (1) quando existem tantos elementos

positivos como negativos, e o valor mínimo (0) quando todos os elementos são da mesma classe.

• Ganho de informação - redução esperada no valor da Entropia, devido à ordenação do conjunto de treino segundo os valores do atributo A.


38

Exemplo

Conjunto de dados

Fonte: GFBioinfo

Dia Aspecto Temp. Umidade Vento Jogar Tênis

D1 Sol Quente Elevada Fraco Não

D2 Sol Quente Elevada Forte Não

D3 Nuvens Quente Elevada Fraco Sim

D4 Chuva Ameno Elevada Fraco Sim

D5 Chuva Fresco Normal Fraco Sim

D6 Chuva Fresco Normal Forte Não

D7 Nuvens Fresco Normal Fraco Sim

D8 Sol Ameno Elevada Fraco Não

D9 Sol Fresco Normal Fraco Sim

D10 Chuva Ameno Normal Forte Sim

D11 Sol Ameno Normal Forte Sim

D12 Nuvens Ameno Elevada Forte Sim

D13 Nuvens Quente Normal Fraco Sim

D14 Chuva Ameno Elevada Forte Não

39

• Primeiro passo: são analisados todos os atributos, começando pela Umidade.

Exemplo

940,014

5log14

514

9log14

9)(

]5 ,9[

22

EntropiaE

S

Umidade ?

Elevada Normal

[3+, 4-] [6+, 1-]

E=0,985 E=0,592

151,0),(

592,014

7985,014

7940,0),(

UmidadeSGanho

UmidadeSGanho Obs.:

40

• Calculando o ganho para todos os atributos o que o tem maior ganho é o Aspecto.

Exemplo

940,0

]5 ,9[

E

S

247,0),(

971,014

50,014

4971,014

5940,0),(

AspectoSGanho

AspectoSGanho

Aspecto

Sol Nuvens Chuva

[2+, 3-] [4+, 0-]

E=0,971 E=0 E=0,971

[3+, 2-]

029,0.),(

247,0),(

048,0),(

151,0),(

TempSGanho

AspectoSGanho

VentoSGanho

UmidadeSGanho

MAX

41

• No próximo passo o atributo Aspecto já não é considerado.

Exemplo

Aspecto

Sol Nuvens Chuva

? ? Sim

[2+, 3-] [4+, 0-] [3+, 2-]

[9+, 5-]

[D1, D2, ..., D14]

SSol =[D1, D2, D8, D9, D11] SNuvens =[D3, D7, D12, D13] SChuva =[D4, D5, D6, D10, D14]

019,0918,05

30,15

2971,0),(

570,00,05

10,15

20,05

2971,0.),(

971,00,05

20,05

3971,0),(

VentoSGanho

TempSGanho

UmidadeSGanho

MAX

Sol

Sol

Sol

42

• Quando em todos os nós a entropia for nula, o algoritmo para e obtêm-se a seguinte Árvore de decisão:

Exemplo

Aspecto

Sol Nuvens Chuva

Umidade

Elevada Normal

Vento

Fraco Forte

Não Não Sim

Sim

Sim

[D1, D2, ..., D14]

SNuvens =[D3, D7, D12, D13]

SSol,Elevada=[D1, D2, D8] SSol,Normal=[D9, D11] SChuva,Fraco=[D6, D14] SChuva,Forte=[D4, D5, D10]

Documents

ÁRVORES de DECISÃOpaginapessoal.utfpr.edu.br/kathya/Disciplinas/sistemas...12 ÁRVORES de DECISÃO • Método para inferência indutiva –Auxilia a predizer a classe de um objeto