Aprendizado de Maquina e Arvore de Decisão

Aprendizado de Máquina
Aprendizado de Conceito
Etapas do KDD – Abordagem Computacional
ã o de
a ra ç
p
Pre Dados
ã o de
a ra ç
p
Pre Dados
ã o de
x t r a ç to
E im e n
h e c
Con
Visualização
o de de Dados
ra çã
p a
Pre Dados
ã o de
x t r a ç to
E im e n
h e c
Con
Extração de Conhecimento –
• Definição (Mitchell, 1997):
– Pode-se dizer que um programa de computador aprende a
partir de uma experiência E com respeito a uma classe de
tarefas T e com medida de desempenho P, se seu
desempenho P na tarefa T melhora com a experiência E.
• 3 Componentes:
– Tarefa a ser realizada
– A fonte de experiência (arquivos?)
– A medida de desempenho (a ser otimizada)
Para a construção de um sistema de aprendizado estes 3

componentes devem ser definidos.
• Fonte de Experiência
– O tipo de experiência tem grande impacto no aprendizado
• Pode ser gerada automaticamente?
• Está correta?
• Está completa?
• Está ordenada de maneira adequada?
• O formato é adequado?
– Considera-se que a experiência representa exatamente a
distribuição real dos dados.
• Dados de treinamento
• Dados de teste
• Na prática está consideração é muitas vezes violada
• Distribuição dos dados de treinamento podem ser diferentes da
distribuição dos dados de teste
• Fonte de Experiência
– Dados de treinamento podem ser os mesmos usados
para teste?
– Uma porção dos dados de treinamento podem ser
utilizados para teste?
– Validação cruzada?
• Medida de Desempenho
– Na maioria das vezes espera-se um valor aproximado
– Função Objetivo ideal (V)
– Função Objetivo utilizada (V)
Aprendizado Supervisionado
25
20
Series1
15
Series2
10
5
0
0 5 10 15 20 25
25
20
Series1
15
Series2
10
5
0
0 5 10 15 20 25
25
20
Series1
15
Series2
10
5
0
0 5 10 15 20 25
25
20
Series1
15
Series2
10
5
0
0 5 10 15 20 25
25
20
Series1
15
Series2
10
5
0
0 5 10 15 20 25
25
20
Series1
15
Series2
10
5
0
0 5 10 15 20 25
25
20
Series1
15
Series2
10
5
0
0 5 10 15 20 25
25
20
Series1
15
Series2
10
5
0
0 5 10 15 20 25
Aprendizado Não Supervisionado
25
20
15
10
5
0
0 5 10 15 20 25
25
20
15
10
5
0
0 5 10 15 20 25
25
20
15
10
5
0
0 5 10 15 20 25
25
20
15
10
5
0
0 5 10 15 20 25
Aprendizado Semissupervisionado
25
20
15
Series1
Series2
10
Unlabeled
5
0
0 5 10 15 20 25
Semi-supervised Learning
25
20
15
Series1
Series2
10
Unlabeled
5
0
0 5 10 15 20 25
25
20
15
Series1
Series2
10
Unlabeled
5
0
0 5 10 15 20 25
25
20
15
Series1
Series2
10
Unlabeled
5
0
0 5 10 15 20 25
25
20
15
Series1
Series2
10
Unlabeled
5
0
0 5 10 15 20 25
25
20
15
Series1
Series2
10
Unlabeled
5
0
0 5 10 15 20 25
25
20
15
Series1
Series2
10
Unlabeled
5
0
0 5 10 15 20 25
25
20
15
Series1
Series2
10
Unlabeled
5
0
0 5 10 15 20 25
25
20
15
Series1
Series2
10
Unlabeled
5
0
0 5 10 15 20 25
25
20
15
Series1
Series2
10
Unlabeled
5
0
0 5 10 15 20 25
25
20
15
Series1
Series2
10
Unlabeled
5
0
0 5 10 15 20 25
25
20
15
Series1
Series2
10
Unlabeled
5
0
0 5 10 15 20 25
25
20
15
Series1
Series2
10
Unlabeled
5
0
0 5 10 15 20 25
25
20
15
Series1
Series2
10
Unlabeled
5
0
0 5 10 15 20 25
• É um problema de busca por uma
hipótese que melhor se ajusta a um
conjunto de treinamento. A busca é
realizada em um espaço (de busca)
predefinido contendo hipóteses
candidatas.
• Aquisição de conceitos gerais de
exemplos específicos de treinamento
• Um conceito pode ser a descrição de um
objeto ou objetos pertencentes a um
conjunto
– Carro, casa, pessoa, cachorro, saudável, etc.
– Um elemento pertence ou não a um conceito
• Função booleana
• Definição (Mitchell, 1997): inferência de
uma função booleana utilizando exemplos
de entradas e saídas.
• Exemplo contact-lenses
• Definições:
– Conjunto de itens que define um conceito é chamado
conjunto de instâncias X (arquivo de dados)
– O conceito (ou função) a ser aprendido é chamado
conceito alvo c. c: X → {0,1}
– Instâncias onde c(x) = 1 são chamadas exemplos
positivos
– Instâncias onde c(x) = 0 são chamadas exemplos
negativo
– O objetivo do aprendizado é encontrar uma hipótese h
tal que h(x) = c(x) para todo x em X.
• Qualquer hipótese considerada uma boa
aproximação da função objetivo obtida a
partir de um conjunto de treinamento
suficientemente grande, também será uma
boa aproximação para dados ainda não
observados (dados de teste).
• Viés indutivo: é o conjunto de considerações
iniciais feitas para que o algoritmo de
aprendizado realize o aprendizado de maneira
correta
• Nem sempre o viés indutivo é correto e nestes
casos o algoritmo poderá gerar resultados
também incorretos.
• Exemplo:
– a hipótese mais geral deve sempre ser preferida
– a hipótese mais específica deve sempre ser preferida
Árvore de Decisão
Árvore de Decisão
• Uma das formas de aprendizado indutivo
mais utilizadas
– Aplicações práticas
– Tarefas de Classificação (Aprendizado
supervisionado)
• Aproximação de funções discretas
robusta a ruídos
• Aprendizado de expressões disjuntivas
Árvore de Decisão
Árvore de Decisão
How would you represent boolean function AB ? A ∨ B?
How would you represent AB ∨ CD(∼E)

Árvore de Decisão
• A função aprendida é representada por
uma árvore de decisão
• A árvore é facilmente convertida em
regras do tipo “Se..... Então.....”
– O número de folhas é igual ao número de
regras
– A profundidade da árvore define a quantidade
de antecedentes nas regras
• Facilidade para compreensão humana
Árvore de Decisão
• Se (Outlook=sunny) e
(Humidity=High) então
Play=no.
(Humidity=normal) então
Play=yes.
• Se (Outlook=overcast)
então Play=yes.
• Se (Outlook=rain) e
(Wind=strong) então
Play=no.
(Wind=weak) então
Play=yes.
Árvore de Decisão
Play=no.
Play=yes.
então Play=yes.
Play=no.
(Wind=weak) então
Play=yes.
Árvore de Decisão
Play=no.
Play=yes.
então Play=yes.
Play=no.
(Wind=weak) então
Play=yes.
Árvore de Decisão
Play=no.
Play=yes.
então Play=yes.
Play=no.
(Wind=weak) então
Play=yes.
Árvore de Decisão
Play=no.
Play=yes.
então Play=yes.
Play=no.
(Wind=weak) então
Play=yes.
Árvore de Decisão
Play=no.
Play=yes.
então Play=yes.
Play=no.
(Wind=weak) então
Play=yes.
Árvore de Decisão
• Como seriam
classificados as
seguintes instâncias?
– <Outlook=sunny,
Temperature=hot,
Humidity=high,
Wind=strong >
– <Outlook=overcast,
Temperature=hot,
Humidity=high,
Wind=strong >
– <Outlook=rain,
Temperature=hot,
Humidity=high,
Wind=strong >
Árvore de Decisão
• Como seriam
classificados as
– <Outlook=sunny,
Temperature=hot,
Humidity=high,
Wind=strong >
Temperature=hot,
Humidity=high,
Wind=strong >
– <Outlook=rain,
Temperature=hot,
Humidity=high,
Wind=strong >
Árvore de Decisão
• Como seriam
classificados as
– <Outlook=sunny,
Temperature=hot,
Humidity=high,
Wind=strong >
Temperature=hot,
Humidity=high,
Wind=strong >
– <Outlook=rain,
Temperature=hot,
Humidity=high,
Wind=strong >
Árvore de Decisão
• Como seriam
classificados as
– <Outlook=sunny,
Temperature=hot,
Humidity=high,
Wind=strong >
Temperature=hot,
Humidity=high,
Wind=strong >
– <Outlook=rain,
Temperature=hot,
Humidity=high,
Wind=strong >
Árvore de Decisão
• Como seriam
classificados as
– <Outlook=sunny,
Temperature=hot,
Humidity=high,
Wind=strong >
Temperature=hot,
Humidity=high,
Wind=strong >
– <Outlook=rain,
Temperature=hot,
Humidity=high,
Wind=strong >
Árvore de Decisão
• Como seriam
classificados as
– <Outlook=sunny,
Temperature=hot,
Humidity=high,
Wind=strong >
Temperature=hot,
Humidity=high,
Wind=strong >
– <Outlook=rain,
Temperature=hot,
Humidity=high,
Wind=strong >
Árvore de Decisão
• Como seriam
classificados as
– <Outlook=sunny,
Temperature=hot,
Humidity=high,
Wind=strong > = NO
Temperature=hot,
Humidity=high,
Wind=strong >
– <Outlook=rain,
Temperature=hot,
Humidity=high,
Wind=strong >
Árvore de Decisão
• Como seriam
classificados as
– <Outlook=sunny,
Temperature=hot,
Humidity=high,
Wind=strong >
Temperature=hot,
Humidity=high,
Wind=strong >
– <Outlook=rain,
Temperature=hot,
Humidity=high,
Wind=strong >
Árvore de Decisão
• Árvore representa uma disjunção de
conjunções de restrições
– Cada ramo é uma conjunção de testes
– A árvore é uma disjunção de ramos

Árvore de Decisão
• Aprendizado é adequado:
– Instâncias são descritas por atributos e seus
valores (discretos ou contínuos)
– Função objetivo é discreta (classificação)
• Pode ser adaptada para predição
– Necessidade de disjunções
– Dados com ruídos
Árvore de Decisão
• Algoritmos de aprendizado
– A base é a busca top-down por todas as

possíveis árvores;
– Normalmente é utilizada uma busca “gulosa”
– A idéia clássica está definida no ID3 (Quilan,
1986)
Árvore de Decisão – ID3
• ID3 (Mitchell, 1997)
• ID3
– Cria um ranking dos atributos mais
adequados
– Insere (com base no ranking) os atributos na
árvore
– Utiliza o ganho de informação (information
gain) para criar o ranking
• Método com base na entropia
• Entropia
– Medida definida na teoria da informação
– Define a pureza de um conjunto de instâncias
– Precisa de um conjunto de instâncias
positivas e negativas
Entropia(S) = - (p+ log2 p+) - (p- log2 p-)
p+: proporção de instâncias positivas
p-: proporção de instâncias negativas
• Entropia
Seja S um conjunto de com 16 instâncias referentes a um
conceito booleano. Considere ainda que em S exitem 9
instâncias positivas e 7 negativas. Calcule a entropia
de S.
Para facilitar, pode usar:
log2(X) = log10(X)/log10(2)
Entropia(S) = - ((9/16) * log2 (9/16)) – ((7/16) * log2 (7/16))

• Entropia
de S.

= -((0,5625) * -(0,8300)) – ((0,4375) * -(1,1926))
• Entropia
de S.

= -((0,5625) * -(0,8300)) – ((0,4375) * -(1,1926))
= - (-0,4669) – (-0,5217) = 0,9886
• Entropia
• O que acontece com a entropia quando
existe a mesma quantidade de instâncias
positivas e negativas?
• Entropia
Seja S um conjunto de com 16 instâncias referentes a
um conceito booleano. Considere ainda que em S
exitem 8 instâncias positivas e 8 negativas. Calcule a
entropia de S.
• Entropia
entropia de S.
• Entropia
entropia de S.
= -((0,5) * (-1)) – ((0,5) * (-1))
• Entropia
entropia de S.
= -((0,5) * (-1)) – ((0,5) * (-1))
= 0,5 + 0,5 = 1
• Entropia
todas as instâncias são positivas?
• Entropia
exitem 16 instâncias positivas e 0 negativas. Calcule
a entropia de S.
• Entropia
a entropia de S.
• Entropia
a entropia de S.
= -((1) * 0) – ((0) * (log2 (0/16)))
• Entropia
a entropia de S.
= -((1) * 0) – ((0) * (log2 (0/16)))
=0+0=0
• Entropia
todas as instâncias são negativas?
• Entropia
a entropia de S.
• Entropia
a entropia de S.
• Entropia
a entropia de S.
= -((0) * (log2 (0/16))) – (1 * 0)
• Entropia
a entropia de S.
= -((0) * (log2 (0/16))) – (1 * 0)
=0+0=0
• Entropia para um conceito booleano:
• Entropia para uma variável alvo que pode
assumir c classes:
Entropia(S) ≡
• O ganho de informação de um atributo é a
redução esperada na entropia causada pelo
particionamento das instâncias de acordo com
este atributo. Ou seja, o quanto se espera que
a entropia seja reduzida quando se sabe o
valor do atributo A.
Ganho(S,A) ≡

Valores(A): conjunto de todos os valores possíveis do atributo A

Sv: subconjunto de S, no qual o atributo A possui valor v.
• Considere o exemplo (Mitchell, 1997):
• Para o atributo Wind tem-se:
• Calcule agora o ganho de informação para os
outros atributos (Outlook, Temperature e
Humidity)
• Calcule agora o ganho de informação para os
outros atributos (Outlook, Temperature e
Humidity)
• Após o cálculo do ganho de informação tem-
se:
• Agora o processo se
repete retirando-se o
atributo já selecionado e
utilizando-se apenas as
instâncias que obedecem
as restrições impostas por
cada um dos ramos.
Exercícios
• 1)Gere agora a árvore completa para o exemplo dado
no slide 87!
• 2)Utilizando o algoritmo ID3 gere a árvore de decisão
para a seguinte base de dados:
age,spectacle, astigmatism, tear-rate, contact-lenses
young,myope,no,reduced,none
young,myope,no,normal,soft
young,myope,yes,reduced,none
young,hypermetrope,no,reduced,none
young,hypermetrope,no,normal,soft
young,hypermetrope,yes,reduced,none
pre-presbyopic,myope,no,reduced,none
pre-presbyopic,myope,no,normal,soft
pre-presbyopic,myope,yes,reduced,none
pre-presbyopic,hypermetrope,no,reduced,none
pre-presbyopic,hypermetrope,no,normal,soft
pre-presbyopic,hypermetrope,yes,reduced,none
presbyopic,myope,no,reduced,none
presbyopic,myope,yes,reduced,none
presbyopic,hypermetrope,no,reduced,none
• Características do ID3
– Espaço de busca completo: todas as
possíveis árvores de decisão
• O que isto significa?
– Mantém uma única hipótese válida durante o

processo de busca
• Não define quantas árvores são consistentes com
o conjunto de treinamento
– Utiliza-se do Hill-climbing (complexidade
crescente)
• Não faz bactracking
• Ótimo local
– Analisa todo o conjunto de treinamento para
tomar cada decisão
• Uma instância “errada” não influencia diretamente
o resultado do algoritmo
– Viés Indutivo:
• Árvores mais curtas (rasas)
• Atributos com maior ganho de informação estão
mais próximos da raiz
– Nem sempre a árvore é mais curta (rasa)
• Compare com a busca em largura
• ID3 versão heurística da busca em largura
– Viés indutivo aproximado
– Viés Indutivo do ID3:
• É dado pelo método de busca e não pelo espaço
de busca
• Viés de busca (ou viés de preferência)
• Viés de linguagem (ou viés de restrição): é dado
pela forma de representação do espaço de busca
(espaço de versões). Não é o caso do ID3.
• Podem existir algoritmos com viés de
busca e de linguagem?
• Como estes vieses podem ser
comparados?
– Existe um menos prejudicial ao resultado do
aprendizado?
• Occam’s Razor: deve-se preferir sempre a
menor hipótese consistente com os dados
(o menor modelo)
• Why Prefer Short Hypotheses? (Occam’s Razor)
Argument in favor:
• Fewer short hypotheses than long ones
 a short hypothesis that fits the data is
less likely to be a statistical coincidence
 highly probable that a sufficiently complex
hypothesis will fit the data
Argument opposed:
• What’s so special about “short” hypotheses?
Árvore de Decisão – C4.5
Definição (mitchell, 1997): considere um
espaço de hipóteses H. Uma hipótese h ∈ H,
superestima (overfits) um conjunto de dados
de treinamento (D) se existe alguma outra
hipótese h’ ∈ H, tal que, h possui um erro
menor que h’ em D, mas h’ possui um erro
menor que h no conjunto de dados completo.
• Overfitting pode prejudicar o desempenho
de algoritmos de aprendizado
• Overfitting acontece principalmente
quando:
– Há ruído nos dados
– A amostra de treinamento é muito pequena
(não reflete a distribuição dos dados).
• Existem basicamente duas linhas de
atuação para se minimizar Overfitting em
aprendizado de árvores de decisão:
– Parar de expandir um ramo antes de atingir a
classificação perfeita (entropia=zero)
• Dificuldade em se definir o ponto de parada
– Podar a árvore construída sem a
preocupação de se evitar overffiting
• Poda pela Redução do Erro (Quinlan,
1987)
– Todos os nós da árvores são candidatos à
poda
– Realiza-se a poda se a árvore resultante não
gera resultados de classificação piores que a
árvore original (no conjunto de teste)
– Um terceiro conjunto (de validação) de dados
(≠ do conjunto de teste e do conjunto de
treinamento pode ser usado)
• Poda pela Redução do Erro (Quinlan, 1987)
• Poda de Regras
– Converte-se a árvore em regras
– Poda-se cada regra removendo-se os antecedentes
que resultem em melhora na taxa de classificação
• Pode-se utilizar conjunto de validação ou não (como no C4.5)
– Ordena-se as regras de acordo com a precisão (taxa
de classificação) de cada uma
– As regras são utilizadas, para classificar novas
instâncias, na seqüência estabelecida no passo
anterior
• Poda de Regras
– A conversão da árvore em regras permite
que:
• a eliminação seja testada em sub-ramos de
maneira independente
• A eliminação de nós ocorra em qualquer sentido
(não necessariamente da raiz para as folhas
• Facilita a compreensão do modelo
• Atributos contínuos
– Considere um atributo contínuo
“temperature” (Mitchell, 1997) como abaixo:
– A idéia básica é convertê-lo em uma atributo

binário:
• Temperature < c
• Temprature >= c
– Para a conversão, pode-se considerar a
variação em relação a cada classe
– Tem-se:
• (48+60)/2 = 54
• (80+90)/2 = 85
– Calcula-se então o ganho de informação de
cada possibilidade
– Para este exemplo os atributos
Temperature>54
Temperature>85.
– A partir daí o novo atributo participa da
construção da árvore como se fosse um
atributo discreto
– Há ainda outros métodos para tornar o
atributo discreto e com mais de 2 valores
possíveis (veja Fayyad and Irani, 1993)
• Atributos com muitos valores possíveis
– Imagine um atributo data (dia/mês/ano)
• Cada valor possível refere-se a um único dia e

então classifica exatamente cada instância
• Seria escolhido como raiz. Isto é bom?
– Outra medida pode melhorar a escolha do
atributo
– Razão de ganho (GainRatio) utiliza o ganho
de informação, mas penaliza atributos com
muitos valores possíveis
– O GainRatio apresenta ainda alguns
problemas, como quando o valor
SplitInformation é zero ou muito pequeno
– Outras medidas foram criadas visando
minizar este problema. Mas o GainRatio é o
método utilizado no C4.5
Exercícios
1. Refaça o exercício 1 (transparência 25)
utilizando o C4.5 (utilize a poda de
regras e o GainRatio). Compare os
resultados obtidos.
2. Faça os exercícios 3.1, 3.2, 3.3 e 3.4
(itens a, b e c) do Mitchell.
Exercícios
Questions to think about (1)
• ID3 and C4.5 are heuristic algorithms that

search through the space of decision trees.
Why not just do an exhaustive search?
Exercício emprestado da aula de “Machine Learning” ministrado pelo professor Tom Mitchell na Carnegie Mellon University em
2009 com a participação do Professor Estevam.
Exercícios
• Consider target function f: <x1,x2>y, where x1 and
x2 are real-valued, y is boolean. What is the set of
decision surfaces describable with decision trees
that use each attribute at most once?
• Why use Information Gain to select attributes in
decision trees? What other criteria seem
reasonable, and what are the tradeoffs in making
this choice?
Exercício emprestado da aula de “Machine Learning”ministrado pelo professor Tom Mitchell na Carnegie Mellon University

Aprendizado de Maquina e Arvore de Decisão

Enviado por

Direitos autorais:

Formatos disponíveis

Aprendizado de Maquina e Arvore de Decisão

Enviado por

Dados do documento

Título original

Direitos autorais

Formatos disponíveis

Compartilhar este documento

Compartilhar ou incorporar documento

Opções de compartilhamento

Você considera este documento útil?

Este conteúdo é inapropriado?

Direitos autorais:

Formatos disponíveis

Aprendizado de Maquina e Arvore de Decisão

Enviado por

Direitos autorais:

Formatos disponíveis

Aprendizado de Máquina

Para a construção de um sistema de aprendizado estes 3

How would you represent boolean function AB ? A ∨ B?

How would you represent AB ∨ CD(∼E)

– Cada ramo é uma conjunção de testes

– A árvore é uma disjunção de ramos

– A base é a busca top-down por todas as

Entropia(S) = - ((9/16) * log2 (9/16)) – ((7/16) * log2 (7/16))

Entropia(S) = - ((9/16) * log2 (9/16)) – ((7/16) * log2 (7/16))

Entropia(S) = - ((9/16) * log2 (9/16)) – ((7/16) * log2 (7/16))

Valores(A): conjunto de todos os valores possíveis do atributo A

– Mantém uma única hipótese válida durante o

– A idéia básica é convertê-lo em uma atributo

– Imagine um atributo data (dia/mês/ano)

• Cada valor possível refere-se a um único dia e

• ID3 and C4.5 are heuristic algorithms that

Você também pode gostar