Noções de algoritmos e estudo de
casos das principais tarefas de
Mineração de dados
HAC
1
MD -junho/2008
Tarefas de MD
Data
Mining
Atividade
Preditiva
Classifica
ção
HAC
Regressã
o
Atividade
Descritiva
Regras de
Associaçã
o
Clusterin
g
Sumariza
ção
2
MD -junho/2008
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
3
MD -junho/2008
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
xxx
exemplo
HAC
renda
50
tempo
sol
dívida
10
temperatura
2
humidade
72
classe
bom
vento
forte
classe
sim
4
MD -junho/2008
Relembrando conceitos...

Atributo:


Descreve uma característica ou um aspecto de um exemplo
Tipos:

nominal (categórico)


Contínuo


HAC
Vento forte, dia com sol, cliente bom, etc...
Temperatura, humidade, etc...
Símbolos especiais:

Desconhecido (representado normalmente pelo ?)

Não-se-aplica (representado normalmente pelo !)
5
MD -junho/2008
Relembrando conceitos...

HAC
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)
6
MD -junho/2008
Voltando à classificação:


HAC
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
7
MD -junho/2008
Conjunto de dados para classificação
Dívida
o
o
x
o
o
o
x
o
x x
x
x
x
x
x
x o
o
o o
o
o
o
Renda
Dados no formato atributo-valor:
Renda
Dívida
Status
HAC
8
MD -junho/2008
Classificação
Conjunto de
exemplos
atributos/classe
Paradigma de
Aprendizado
Sistema de
Aprendizado
Classificador específico de uma aplicação
HAC
9
MD -junho/2008
Classificação
Exemplo a ser
classificado
Classificador
Classe a que pertence
o exemplo
HAC
10
MD -junho/2008
Em que formato o classificador é representado
e como ele é usado para classificação?
a=5
sim


Árvores de decisão
Regras de decisão
não
c=2
b=7
sim
não
c=1
c=2
Se a = 5 e b = 7 então c = 1
senão c = 2
HAC
11
MD -junho/2008
Á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:


HAC
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.
12
MD -junho/2008
HAC
13
MD -junho/2008
Indutor de árvore de decisão
funçã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
14
MD -junho/2008
Seleção do melhor atributo


HAC
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
15
MD -junho/2008
Exemplo
HAC
exemplo
T1
T2
T3
T4
T5
T6
T7
T8
T9
T10
T11
T12
T13
T14
tempo
sol
sol
sol
sol
sol
nublado
nublado
nublado
nublado
nublado
chuva
chuva
chuva
chuva
T15
chuva
temperatura humidade
2
72
28
91
22
70
23
95
30
85
23
90
29
78
19
65
26
75
20
87
22
95
19
70
23
80
25
81
21
80
vento
forte
forte
fraco
fraco
fraco
forte
fraco
forte
fraco
forte
fraco
forte
forte
fraco
fraco
classe
sim
não
sim
não
não
sim
sim
não
sim
sim
sim
não
não
sim
sim
16
MD -junho/2008

atributo selecionado: tempo

tempo = sol


T2, T4, T5 (não)
tempo = nublado



HAC
T1, T3 (sim)
T6, T7, T9, T10 (sim)
T8 (não)
tempo = chuva
T11, T14, T15 (sim)
T12, T13 (não)
17
MD -junho/2008


HAC
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
18
MD -junho/2008

tempo = sol e umidade ≤ 78


tempo = sol e umidade > 78


T11, T14, T15 (sim)
tempo = chuva e vento = forte

HAC
T8 (não)
tempo = chuva e vento = fraco


T6, T7, T9, T10 (sim)
tempo = nublado e umidade ≤ 70


T2, T4, T5 (não)
tempo = nublado e umidade > 70


T1, T3 (sim)
T12, T13 (não)
19
MD -junho/2008

HAC
agora todos os subconjuntos de exemplos
definidos pelos testes pertencem a mesma
classe
20
MD -junho/2008
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


HAC
Pré-poda: ignora alguns exemplos
Pós-poda: corta alguns ramos da árvore
21
MD -junho/2008
Avaliação de algoritmos

A avaliação é uma parte da etapa de pósprocessamento:

Avaliação:




Interpretação e explanação:





documentado;
visualizado;
modificado;
comparado.
Filtragem do conhecimento:


HAC
precisão;
compreensibilidade;
interessabilidade.
restrição de atributos;
ordenação por métricas.
22
MD -junho/2008
Avaliação de algoritmos

Normalmente baseada na idéia de
amostragem
amostra 1
conjunto
de exemplos
distribuição D'
amostra 2
amostra n
HAC
23
MD -junho/2008
métodos de amostragem

resubstituição:


holdout:

HAC
construir o classificador e testar seu
desempenho no mesmo conjunto de exemplos
(medida aparente)
divide os exemplos em uma porcentagem fixa de
exemplos p para treinamento e (1-p) para teste,
considerando normalmente p > 1/2
24
MD -junho/2008
métodos de amostragem

Cross-validation:




HAC
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
25
MD -junho/2008
Erro e Precisão
HAC

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
26
MD -junho/2008
Erro e Precisão
• taxa de erro:
•
•
•
•
•
i
i
retorna 1 caso yi ≠h(xi)
e zero caso contrário
n número de exemplos de teste
xi vetor de atributos
h(xi) saída obtida
yi saída desejada
y  h( x )
precisão:
HAC
ce(h) = 1/n ∑ y  h( x )
i
i
ca(h) = 1 - ce(h)
27
MD -junho/2008

Exemplos de teste:
sol 23 95 fraco não
nublado 29 78 fraco sim
chuva 22 95 fraco não
HAC
28
MD -junho/2008