Upload
internet
View
102
Download
0
Embed Size (px)
Citation preview
HAC MD -junho/2008
1
Noções de algoritmos e estudo de casos das principais
tarefas de Mineração de dados
HAC MD -junho/2008
2
Tarefas de MD
Data Mining
AtividadeDescritiv
a
Sumarização
Regras de
Associação
Clustering
AtividadePreditiva
Regressão
Classificação
HAC MD -junho/2008
3
Classificação
Tarefa preditiva em que as classes são
discretas (nominais, categóricas)
Tarefa de aprendizado supervisionado:
exemplos são rotulados ou etiquetados (classes
são conhecidas)
HAC MD -junho/2008
4
Relembrando conceitos...
No aprendizado indutivo supervisionado:
• Exemplo (caso, registro ou dado)– É uma tupla (conjunto ordenado) de valores de atributos– Descreve o objeto de interesse: um paciente, cliente de
uma companhia... Cliente 1 renda dívida classe xxx 50 10 bom exemplo tempo temperatura humidade vento classe sol 2 72 forte sim
HAC MD -junho/2008
5
Relembrando conceitos... Atributo:
Descreve uma característica ou um aspecto de um exemplo
Tipos:
nominal (categórico)
Vento forte, dia com sol, cliente bom, etc...
Contínuo
Temperatura, humidade, etc...
Símbolos especiais:
Desconhecido (representado normalmente pelo ?)
Não-se-aplica (representado normalmente pelo !)
HAC MD -junho/2008
6
Relembrando conceitos...
No aprendizado supervisionado, um dos
atributos é considerado especial, chamado
de atributo-meta ou classe, que indica o
conceito que se deseja aprender:
Categoria do cliente (bom/mau)
Decisão de sair (sim/não)
Consumo do carro (km/l)
HAC MD -junho/2008
7
Consiste em aprender um padrão a partir de
um conjunto de dados, na forma de árvore
ou regras, tal que, dado um exemplo
desconhecido (de classe desconhecida),
classifica esse exemplo.
Extrair um padrão de classificação significa
ser capaz de descrever um número grande
de casos de uma maneira concisa
Voltando à classificação:
HAC MD -junho/2008
8
Conjunto de dados para classificação
x
xx
x x x
x x
x
x
o
o
o
o o
o
o
o
o
o
o
o
o
Renda
Dívida
Dados no formato atributo-valor:Renda Dívida Status
HAC MD -junho/2008
9
Classificação
Sistema de Aprendizado
Paradigma de Aprendizado
Conjunto deexemplos
atributos/classe
Classificador específico de uma aplicação
HAC MD -junho/2008
10
Classificação
Classificador
Exemplo a ser classificado
Classe a que pertence o exemplo
HAC MD -junho/2008
11
Em que formato o classificador é representado
e como ele é usado para classificação?
Árvores de decisão
Regras de decisão
a=5
b=7 c=2
c=1 c=2
sim não
sim não
Se a = 5 e b = 7 então c = 1senão c = 2
HAC MD -junho/2008
12
Árvores de decisão
Muitos algoritmos de AM são indutores de
árvores de decisão
Árvore de Decisão: estrutura de dados definida
como:
um nó folha que corresponde a uma classe ou
um nó de decisão que contém um teste sobre um
atributo. Para cada resultado do teste existe um ramo
para uma sub-arvore que tem a mesma estrutura que
a árvore.
HAC MD -junho/2008
13
HAC MD -junho/2008
14
Indutor de árvore de decisãofunção ARVORE (exemplos, atributos, default) retorna arvore
1. se não há exemplos então retorne valor default
2. se todos os exemplos tem a mesma classe então retorne a classe
3. best = escolha_atributo( atributos, exemplos);
4. arvore = nova arvore de decisão com atributo best na raiz
5. para todo valor vi de best faça
6. exemplos i = {elementos de exemplos com best = vi}
7. subarvore = ARVORE (exemplos i , atributos – best, valor_maioria(exemplos)
8. adicione um ramo para arvore com rótulo vi e subárvore subarvore
9. fim-para
10. retorne arvore
HAC MD -junho/2008
15
Seleção do melhor atributo
O sucesso do algoritmo de geração de AD
depende do critério utilizado para escolher o
atributo que particiona o conjunto de
exemplos em cada iteração
alguns métodos: aleatório, atributo com
menos valores, atributo com mais valores,
atributo de ganho máximo
HAC MD -junho/2008
16
exemplo tempo temperatura humidade vento classeT1 sol 2 72 forte simT2 sol 28 91 forte nãoT3 sol 22 70 fraco simT4 sol 23 95 fraco nãoT5 sol 30 85 fraco nãoT6 nublado 23 90 forte simT7 nublado 29 78 fraco simT8 nublado 19 65 forte nãoT9 nublado 26 75 fraco simT10 nublado 20 87 forte simT11 chuva 22 95 fraco simT12 chuva 19 70 forte nãoT13 chuva 23 80 forte nãoT14 chuva 25 81 fraco simT15 chuva 21 80 fraco sim
Exemplo
HAC MD -junho/2008
17
atributo selecionado: tempo
tempo = sol T1, T3 (sim)
T2, T4, T5 (não)
tempo = nublado T6, T7, T9, T10 (sim)
T8 (não)
tempo = chuva T11, T14, T15 (sim)
T12, T13 (não)
HAC MD -junho/2008
18
cada subconjunto ainda tem exemplos
pertencentes a mais de uma classe
é necessário selecionar outro teste baseado
em outro atributo
tempo = sol >> umidade
tempo = nublado >> umidade
tempo = chuva >> vento
HAC MD -junho/2008
19
tempo = sol e umidade ≤ 78
T1, T3 (sim)
tempo = sol e umidade > 78
T2, T4, T5 (não)
tempo = nublado e umidade > 70
T6, T7, T9, T10 (sim)
tempo = nublado e umidade ≤ 70
T8 (não)
tempo = chuva e vento = fraco
T11, T14, T15 (sim)
tempo = chuva e vento = forte
T12, T13 (não)
HAC MD -junho/2008
20
agora todos os subconjuntos de exemplos
definidos pelos testes pertencem a mesma
classe
HAC MD -junho/2008
21
Poda de AD
apenas um exemplo satisfaz a condição
“ tempo = nublado e umidade ≤ 70 ““overfitting”
A poda em geral melhora o desempenho do classificador para exemplos não vistos
a poda elimina erros provenientes de ruídos em vez de descartar informação relevante Pré-poda: ignora alguns exemplos Pós-poda: corta alguns ramos da árvore
HAC MD -junho/2008
22
Avaliação de algoritmos A avaliação é uma parte da etapa de pós-
processamento:
Avaliação: precisão; compreensibilidade; interessabilidade.
Interpretação e explanação: documentado; visualizado; modificado; comparado.
Filtragem do conhecimento: restrição de atributos; ordenação por métricas.
HAC MD -junho/2008
23
Avaliação de algoritmos
Normalmente baseada na idéia de
amostragem
conjunto de exemplos
distribuição D'
amostra 1
amostra 2
amostra n
HAC MD -junho/2008
24
métodos de amostragem
resubstituição:
construir o classificador e testar seu
desempenho no mesmo conjunto de exemplos
(medida aparente)
holdout:
divide os exemplos em uma porcentagem fixa de
exemplos p para treinamento e (1-p) para teste,
considerando normalmente p > 1/2
HAC MD -junho/2008
25
métodos de amostragem
Cross-validation: r-fold cross validation: exemplos são aleatoriamente
divididos em r partições mutuamente exclusivas
(folds) de tamanhao aproximadamente igual a n/r
os exemplos nos r-1 folds são usados para
treinamento e o fold remanescente é usado para
teste
o treinamento é repetido r vezes, cada vez com um
fold como teste
o erro é a média dos erros de cada treinamento
HAC MD -junho/2008
26
Erro e Precisão
a meta do aprendizado supervisionado é
generalizar conceitos de forma a predizê-lo em
exemplos não utilizados no treinamento
A precisão da hipótese de um classificador
avalia a porcentagem de acertos durante o
processo de classificação
HAC MD -junho/2008
27
Erro e Precisão
• taxa de erro: ce(h) = 1/n ∑
• retorna 1 caso yi ≠h(x
i)
e zero caso contrário• n número de exemplos de teste• x
i vetor de atributos
• h(xi) saída obtida
• yi saída desejada
precisão: ca(h) = 1 - ce(h)
)( iixhy
)( iixhy
HAC MD -junho/2008
28
Exemplos de teste:
sol 23 95 fraco não
nublado 29 78 fraco sim
chuva 22 95 fraco não