Mineração de dados
Classificação: avaliação de modelos
André Salvaro Furtado
Prof. Vania Bogorny
Parte desta apresentação é baseada em material do
prof. Paulo Engel (II/UFRGS)
Relembrando Classificação
Tid
Attrib1
Attrib2
Attrib3
Class
1
Yes
Large
125K
No
2
No
Medium
100K
No
3
No
Small
70K
No
4
Yes
Medium
120K
No
5
No
Large
95K
Yes
6
No
Medium
60K
No
7
Yes
Large
220K
No
8
No
Small
85K
Yes
9
No
Medium
75K
No
10
No
Small
90K
Yes
Learning
algorithm
Induction
Learn
Model
Model
10
Training Set
Tid
Attrib1
Attrib2
11
No
Small
55K
?
12
Yes
Medium
80K
?
13
Yes
Large
110K
?
14
No
Small
95K
?
15
No
Large
67K
?
10
Test Set
Attrib3
Apply
Model
Class
Deduction
Exemplo de dados para concessão de empréstimo
bancário
caso
1
2
3
4
5
6
7
8
9
10
11
12
13
14
montante
médio
médio
baixo
alto
alto
alto
baixo
médio
médio
alto
médio
baixo
baixo
alto
idade
sênior
sênior
sênior
média
jovem
jovem
jovem
média
jovem
média
média
jovem
sênior
média
salário
baixo
baixo
baixo
baixo
alto
alto
alto
baixo
alto
alto
alto
baixo
alto
baixo
conta
sim
não
sim
sim
sim
não
não
sim
sim
sim
não
não
sim
não
empréstimo
não
não
sim
sim
sim
não
sim
não
sim
sim
sim
sim
sim
não
Exemplo de dados para concessão de empréstimo
bancário
caso
1
2
3
4
5
6
7
8
9
10
11
12
13
14
montante
médio
médio
baixo
alto
alto
alto
baixo
médio
médio
alto
médio
baixo
baixo
alto
idade
sênior
sênior
sênior
média
jovem
jovem
jovem
média
jovem
média
média
jovem
sênior
média
salário
baixo
baixo
baixo
baixo
alto
alto
alto
baixo
alto
alto
alto
baixo
alto
baixo
conta
sim
não
sim
sim
sim
não
não
sim
sim
sim
não
não
sim
não
empréstimo
não
não
sim
sim
sim
não
sim
não
sim
sim
sim
sim
sim
não
ID3 – Passo 1: Calcular a entropia do conjunto
caso
1
2
3
4
5
6
7
8
9
10
11
12
13
14
montante
médio
médio
baixo
alto
alto
alto
baixo
médio
médio
alto
médio
baixo
baixo
alto
idade
sênior
sênior
sênior
média
jovem
jovem
jovem
média
jovem
média
média
jovem
sênior
média
salário
baixo
baixo
baixo
baixo
alto
alto
alto
baixo
alto
alto
alto
baixo
alto
baixo
conta
sim
não
sim
sim
sim
não
não
sim
sim
sim
não
não
sim
não
empréstimo
não
não
sim
sim
sim
não
sim
não
sim
sim
sim
sim
sim
não
Entropia (S) = - (p+ * log2 p+ + p- * log2 p-)
Entropia (S) = - ((9/14 * log29/14) + (5/14 * log25/14)) = 0.940
ID3 – Passo 2: Calcular a entropia dos valores dos
atributos
caso
1
2
3
4
5
6
7
8
9
10
11
12
13
14
montante
médio
médio
baixo
alto
alto
alto
baixo
médio
médio
alto
médio
baixo
baixo
alto
idade
sênior
sênior
sênior
média
jovem
jovem
jovem
média
jovem
média
média
jovem
sênior
média
salário
baixo
baixo
baixo
baixo
alto
alto
alto
baixo
alto
alto
alto
baixo
alto
baixo
conta
sim
não
sim
sim
sim
não
não
sim
sim
sim
não
não
sim
não
empréstimo
não
não
sim
sim
sim
não
sim
não
sim
sim
sim
sim
sim
não
Entropia(montante=médio) = - ((2/5 * log22/5) + (3/5 * log23/5)) = 0,971
ID3 – Passo 2: Calcular a entropia dos valores dos
atributos
caso
1
2
3
4
5
6
7
8
9
10
11
12
13
14
montante
médio
médio
baixo
alto
alto
alto
baixo
médio
médio
alto
médio
baixo
baixo
alto
idade
sênior
sênior
sênior
média
jovem
jovem
jovem
média
jovem
média
média
jovem
sênior
média
salário
baixo
baixo
baixo
baixo
alto
alto
alto
baixo
alto
alto
alto
baixo
alto
baixo
conta
sim
não
sim
sim
sim
não
não
sim
sim
sim
não
não
sim
não
empréstimo
não
não
sim
sim
sim
não
sim
não
sim
sim
sim
sim
sim
não
Entropia(montante=médio) = - ((2/5 * log22/5) + (3/5 * log23/5)) = 0,971
Entropia(montante=baixo) = - ((4/4 * log24/4) + (0/4 * log20/4)) = 0
ID3 – Passo 2: Calcular a entropia dos valores dos
atributos
caso
1
2
3
4
5
6
7
8
9
10
11
12
13
14
montante
médio
médio
baixo
alto
alto
alto
baixo
médio
médio
alto
médio
baixo
baixo
alto
idade
sênior
sênior
sênior
média
jovem
jovem
jovem
média
jovem
média
média
jovem
sênior
média
salário
baixo
baixo
baixo
baixo
alto
alto
alto
baixo
alto
alto
alto
baixo
alto
baixo
conta
sim
não
sim
sim
sim
não
não
sim
sim
sim
não
não
sim
não
empréstimo
não
não
sim
sim
sim
não
sim
não
sim
sim
sim
sim
sim
não
Entropia(montante=médio) = - ((2/5 * log22/5) + (3/5 * log23/5)) = 0,971
Entropia(montante=baixo) = - ((4/4 * log24/4) + (0/4 * log20/4)) = 0
Entropia(montante=alto) = - ((3/5 * log23/5) + (2/5 * log22/5)) = 0,971
ID3 – Passo 2: Calcular a entropia dos valores dos
atributos
Entropia(montante=médio) = - 2/5 log2 (2/5) - 3/5 log 2 (3/5) = 0,971
Entropia(montante=baixo) = - 4/4 log2 (4/4) - 0/4 log2 (0/4) = 0
Entropia(montante=alto) = - 3/5 log2 (3/5) - 2/5 log2 (2/5) = 0,971
Entropia (idade = senior)= - 2/4 log2 (2/4) - 2/4 log2 (2/4) = 1
Entropia (idade = média)= - 3/5 log2 (3/5) - 2/5 log2 (2/5) = 0,971
Entropia (idade = jovem)= - 4/5 log2 (4/5) - 1/5 log2 (1/5) = 0,722
...
ID3 – Passo 3: Calcular o ganho de informação dos
atributos
Entropia(montante=médio) = - 2/5 log2 (2/5) - 3/5 log 2 (3/5) = 0,971
Entropia(montante=baixo) = - 4/4 log2 (4/4) - 0/4 log2 (0/4) = 0
Entropia(montante=alto) = - 3/5 log2 (3/5) - 2/5 log2 (2/5) = 0,971
Entropia (idade = senior)= - 2/4 log2 (2/4) - 2/4 log2 (2/4) = 1
Entropia (idade = média)= - 3/5 log2 (3/5) - 2/5 log2 (2/5) = 0,971
Entropia (idade = jovem)= - 4/5 log2 (4/5) - 1/5 log2 (1/5) = 0,722
...
Entropia (S) = - ((9/14 * log29/14) + (5/14 * log25/14)) = 0.940
Ganho (S,montante) = 0,940 - (5/14). 0,971 - (4/14). 0 - (5/14). 0,971 = 0,246
Ganho (S,idade) = 0,940 - (4/14). 1 - (5/14). 0,971 - (5/14). 0,722 = 0,049
Ganho (S,salário) = 0,940 - (7/14). 0,592 - (7/14). 0,985 = 0,151
Ganho (S,conta) = 0,940 - (8/14). 0,811 - (6/14). 1 = 0,047
ID3 – Passo 4: Selecionar o melhor atributo
Entropia(montante=médio) = - 2/5 log2 (2/5) - 3/5 log 2 (3/5) = 0,971
Entropia(montante=baixo) = - 4/4 log2 (4/4) - 0/4 log2 (0/4) = 0
Entropia(montante=alto) = - 3/5 log2 (3/5) - 2/5 log2 (2/5) = 0,971
Entropia (idade = senior)= - 2/4 log2 (2/4) - 2/4 log2 (2/4) = 1
Entropia (idade = média)= - 3/5 log2 (3/5) - 2/5 log2 (2/5) = 0,971
Entropia (idade = jovem)= - 4/5 log2 (4/5) - 1/5 log2 (1/5) = 0,722
...
Entropia (S) = - ((9/14 * log29/14) + (5/14 * log25/14)) = 0.940
Ganho (S,montante) = 0,940 - (5/14). 0,971 - (4/14). 0 - (5/14). 0,971 = 0,246
Ganho (S,idade) = 0,940 - (4/14). 1 - (5/14). 0,971 - (5/14). 0,722 = 0,049
Ganho (S,salário) = 0,940 - (7/14). 0,592 - (7/14). 0,985 = 0,151
Ganho (S,conta) = 0,940 - (8/14). 0,811 - (6/14). 1 = 0,047
Escolha do próximo atributo
casos
{C1,C2,...C14}
[9+, 5-]
proporção dos casos
montante
médio
{C1,C2,C8,C9,C11}
[2+, 3-]
?
baixo
{C3,C7,C12,C13}
[4+, 0-]
E=sim
alto
{C4,C5,C6,C10,C14}
[3+, 2-]
?
Qual atributo será colocado aqui?
Repetir os passos 1, 2, 3 e 4 para os outros atributos
considerando o conjunto de dados S = {C1,C2,C8,C9,C11}
Resultado: modelo de classificação
montante
médio baixo
E=sim
salário
baixo
E=não
alto
alto
E=sim
conta
não
E=não
sim
E=sim
Avaliação da Árvore de Decisão
Como avaliar as regras utilizadas na árvore de decisão na
tarefa de classificação?
• Taxa de Acertos: número de casos classificados
corretamente dividido pelo número total de casos
• taxa_de_acertos = Nacertos / Ntotal
• Taxa de Erros: número de casos classificados de forma
incorreta dividido pelo número total de casos
• taxa_de_erros = Nerros / Ntotal
Avaliação da árvore de decisão
caso
1
2
3
4
5
6
7
8
9
10
11
12
13
14
montante
médio
médio
baixo
alto
alto
alto
baixo
médio
médio
alto
médio
baixo
baixo
alto
idade
sênior
sênior
sênior
média
jovem
jovem
jovem
média
jovem
média
média
jovem
sênior
média
salário
baixo
baixo
baixo
baixo
alto
alto
alto
baixo
alto
alto
alto
baixo
alto
baixo
conta
sim
não
sim
sim
sim
não
não
sim
sim
sim
não
não
sim
não
empréstimo
não
não
sim
sim
sim
não
sim
não
sim
sim
sim
sim
sim
não
Avaliação através da taxa de acertos/erros:
taxa_de_erros = Nerros / Ntotal
taxa_de_acertos = Nacertos / Ntotal
montante
médio baixo
Utilizando o conjunto de treinamento:
proporção_de_acertos = 14 / 14 = 100%
proporção_de_erros = 0 / 14 = 0%
E=sim
salário
baixo
E=não
alto
alto
E=sim
conta
não
E=não
sim
E=sim
Conjunto de teste
caso montante idade
salário
conta
empréstimo
15
16
17
18
19
20
21
alto
alto
alto
alto
alto
alto
alto
sim
não
sim
não
não
sim
sim
sim
não
sim
não
não
sim
sim
médio
médio
baixo
baixo
alto
alto
médio
sênior
sênior
jovem
sênior
média
jovem
jovem
empréstimo
(predito)
sim
sim
sim
sim
não
sim
sim
Proporção de acertos/erros
Utilizando o conjunto de teste:
 proporção_de_acertos = Nacertos / Ntotal
proporção_de_acertos = 5 / 7 = 71,4%
 proporção_de_erros = Nerros / Ntotal
proporção_de_erros = 2 / 7 = 28,6%
caso montante idade
salário
conta
empréstimo
15
16
17
18
19
20
21
alto
alto
alto
alto
alto
alto
alto
sim
não
sim
não
não
sim
sim
sim
não
sim
não
não
sim
sim
médio
médio
baixo
baixo
alto
alto
médio
sênior
sênior
jovem
sênior
média
jovem
jovem
empréstimo
(predito)
sim
sim
sim
sim
não
sim
sim
Métricas para avaliação de desempenho
• O foco deve estar na capacidade preditiva do modelo
– E não no tempo que leva para classificar ou criar um modelo, na
escalabilidade, etc.
• Baseadas na Matriz de Confusão (exemplo com duas classes):
Classe prevista
Classe
real
Sim
Não
Sim
Verdadeiro
Positivo (VP)
Falso
Negativo (FN)
Não
Falso
Positivo (FP)
Verdadeiro
Negativo (VN)
Métricas para avaliação de desempenho...
Classe prevista
Classe
real
Sim
Não
Sim
Verdadeiro
Positivo (VP)
Falso
Negativo (FN)
Não
Falso
Positivo (FP)
Verdadeiro
Negativo (VN)
• Métricas mais usadas:
– Acurácia (mais usada), Erro
Acurácia:
VP  VN
100 %
n
Erro:
FP  FN
100 %
n
n  VP  VN  FP  FN
Métricas para avaliação de desempenho...
Classe prevista
Classe
real
Acurácia:
Sim
Não
Sim
Verdadeiro
Positivo (VP)
Falso
Negativo (FN)
Não
Falso
Positivo (FP)
Verdadeiro
Negativo (VN)
VP  VN
100 %
n
Erro:
FP  FN
100 %
n
n  VP  VN  FP  FN
Métricas para avaliação de desempenho...
Classe prevista
Classe
real
Acurácia:
Sim
Não
Sim
Verdadeiro
Positivo (VP)
Falso
Negativo (FN)
Não
Falso
Positivo (FP)
Verdadeiro
Negativo (VN)
VP  VN
100 %
n
Erro:
FP  FN
100 %
n
n  VP  VN  FP  FN
Exercício em sala
Casa
Própria
Est.Civil
Renda
Mau
Pagador
sim
solteiro
125
Não
não
casado
100
Não
não
solteiro
70
Não
sim
casado
120
Não
não
separado
95
Sim
não
casado
60
Não
sim
separado
220
Não
não
solteiro
85
Sim
não
casado
75
Não
não
solteiro
90
sim
Casa
Própria
sim
não
1
Est.Civil
separado
casado
solteiro
2
3
4
1. Complete a árvore de decisão colocando no lugar dos números das folhas, a
classe, de forma a minimizar os erros de classificação.
2. Faça a matriz de confusão correspondente.
Outras métricas para avaliação de desempenho
Taxa de VP :
VP
(sensibilidade,
100 %
abrangência, VP  FN
recall)
VN
Taxa de VN
100 %
VN

FP
(especificidade):
Classe prevista
Classe
real
Sim
Não
Sim
VP
FN
Não
FP
VN
Precisão:
VP
100 %
VP  FP
F-measure:
2. precisão.recall (Média harmônica entre precisão e recall)
precisão recall
Limitação da acurácia
• Considere um problema de 2 classes
– Número de exemplos da classe 0 = 9.990
– Número de exemplos da classe 1 = 10
• Se o modelo predizer que qualquer amostra é da classe 0,
a acurácia é 9990/10000 = 99,9 %
– A acurácia é enganosa porque o modelo não detecta nenhum
exemplo da classe 1!
• Solução: levar em consideração custos por classe para
erros de classificação
Exemplo: Previsão de culpa em julgamento:
positivo  pena de morte
Matriz de custo
Classe prevista
C(i|j)
Classe
real
Sim
Não
Sim
C(Sim|Sim)
C(Não|Sim)
Não
C(Sim|Não)
C(Não|Não)
• C(i|j): custo de classificar exemplos da classe j, como
sendo da classe i
Cálculo de custos de classificação
Matriz de Custo
C(i|j)
Classe
real
Modelo
M1
Classe
real
Sim
Não
Sim
-1
100
Não
1
0
Classe prevista
Sim
Não
Sim
150
40
Não
60
250
Acurácia = 80%
Custo = 3910
Classe prevista
Modelo
M2
Classe
real
Classe prevista
Sim
Não
Sim
250
45
Não
5
200
Acurácia = 90%
Custo = 4255
Métodos para avaliação de modelos
• Quão preditivo é o modelo aprendido?
• Erro sobre os dados de treinamento não é um bom
indicador de desempenho sobre dados futuros: é muito
otimista
• Solução simples pode ser usada se existirem muitos
dados rotulados:
– Dividir dados em conjuntos de treinamento e de teste
• Mas: normalmente o número de dados rotulados é limitado
– São necessárias técnicas mais sofisticadas de avaliação
Avaliação de modelos
1
0.9
x < 0.43?
0.8
0.7
Yes
No
y
0.6
y < 0.33?
y < 0.47?
0.5
0.4
Yes
0.3
0.2
:4
:0
0.1
0
0
0.1
0.2
0.3
0.4
0.5
x
0.6
0.7
0.8
0.9
1
No
:0
:4
Yes
:0
:3
No
:4
:0
Avaliação de modelos
Avaliação de modelos
Treinamento e teste …
• Conjunto de treinamento: conjunto de exemplos (registros)
que foram usados na geração do modelo
• Conjunto de teste: conjunto de exemplos (registros)
independentes que não foram usados na geração do
modelo
– Suposição: os dados de treinamento e os dados de teste são
amostras representativas do problema
• Arquivos de teste e de treinamento podem ter naturezas
diferentes
– Exemplo: classificadores construídos usando dados de consumidores
de duas cidades diferentes A e B
– Para estimar o desempenho do classificador, gerado com os dados da
cidade A, numa cidade diferente, testá-lo com dados de B
Tirando o máximo dos dados
• Geralmente, quanto maior o arquivo de treinamento
melhor o classificador
• Quanto maior o arquivo de teste mais exata será a
estimativa de erro
• Procedimento holdout (retenção): dividir os dados originais
em conjuntos de treinamento e de teste
– Dilema: queremos tanto um grande arquivo de treinamento quanto
um grande arquivo de teste
Estimação por retenção (holdout)
• O que fazer se a quantidade de dados é limitada?
• Método holdout reserva uma certa quantidade dos dados
para teste e usa o resto para o treinamento
– Usualmente 1/3 para teste, o resto para treinamento
• Mas: as amostras podem não ser representativas
– Exemplo: pode não haver amostras de uma classe nos dados de
teste
• Versão avançada usa estratificação
– Assegura que cada classe esteja representada com proporções
aproximadamente iguais em ambos os conjuntos
• IMPORTANTE: Após a avaliação, todos os dados podem
ser usados para construir o classificador final !!!!
Validação cruzada (cross-validation)
• Validação cruzada evita superposição dos conjuntos de teste
– Primeiro passo: conjunto de dados é dividido em k subconjuntos de tamanhos
iguais
– Segundo passo: um subconjunto é usado para teste e os demais para
treinamento.
– O segundo passo é repetido k vezes, variando o subconjunto usado para teste
– Esta é a chamada validação cruzada por k vezes
• Muitas vezes os subconjuntos são estratificados antes de
realizar a validação cruzada
• A estimativa de erro global é calculada como a média das k
estimativas de erro (uma para cada iteração)
four-fold-cross-validation
subconj 1
Conjunto
de
Exemplos
subconj 2
subconj 3
subconj 4
Modelo 1
Modelo 4
Modelo 3
Modelo 2
treino
subconj 1
treino
subconj 1
treino
subconj 1
teste
subconj 1
treino
subconj 2
treino
subconj 2
teste
subconj 2
treino
subconj 2
treino
subconj 3
teste
subconj 3
treino
subconj 3
treino
subconj 3
teste
subconj 4
treino
subconj 4
treino
subconj 4
treino
subconj 4
Mais sobre validação cruzada
• Método padrão de avaliação: validação cruzada por dez
vezes estratificada
• Por que dez? Experimentos demonstraram que esta é uma
boa escolha para se obter uma estimativa precisa
• Estratificação reduz a variância da estimativa
• Melhor ainda: validação cruzada estratificada repetida
– P. ex. se repete dez vezes a validação cruzada por dez vezes e se
calcula a média (reduz variância)
Validação cruzada deixando um fora
• Validação cruzada deixando um fora (leave-one-out c-v):
– O número de vezes é escolhido como o número de exemplos de
treinamento
– Isto é, deve-se construir n classificadores, onde n é o número de
exemplos de treinamento
• Aproveita ao máximo os dados
• Não envolve sub-amostragem aleatória
• Computacionalmente muito custoso
Navalha de Occam

Dados dois modelos com mesma taxa de erros, o
modelo mais simples é melhor (preferível)
Exercício em sala
lágrimas astigma- pressão prescrição LENTES
tismo
normal
sim
normal
hipermetr.
NÃO
normal
não
normal
miopia
GELAT.
normal
sim
normal
miopia
DURA
reduzida
sim
alta
miopia
NÃO
reduzida
não
normal
hipermetr.
NÃO
normal
não
alta
hipermetr.
NÃO
normal
não
alta
miopia
GELAT.
normal
sim
normal
miopia
DURA
normal
sim
alta
hipermetr.
NÃO
normal
sim
alta
miopia
DURA
normal
sim
normal
miopia.
DURA
lágrimas
reduzida
normal
1
astigmat.
sim
não
2
prescrição
miopia
4
hipermetr.
3
1. Complete a árvore de decisão colocando no lugar dos números das folhas, a
classe, de forma a minimizar os erros de classificação.
2. Faça a matriz de confusão correspondente.