Avaliação do Conhecimento Descoberto
Fábio Moura
orientado por
Francisco Carvalho
Avaliação do Conhecimento Descoberto



Motivação
Treinamento e teste
Estimando performance
• Cross-validation
• Leave-one-out cross-validation
• Bootstrap



Comparando esquemas de
aprendizado
Predizendo probabilidades
Contabilizando o custo de
previsões erradas
• Lift charts
• ROC curves



Avaliando previsões numéricas
Medidas de avaliação do
conhecimento descoberto
O princípio MDL
Motivação
Avaliação: a chave para o sucesso em data mining
 Qual o grau de confiabilidade do modelo aprendido?
 Performance no conjunto de treinamento não é um bom
indicador de performance em dados futuros
 Solução simples

• Utilize um amplo conjunto de dados para treinamento e teste

Quando dados não são facilmente disponíveis
• Utilização de técnicas mais sofisticadas
• Ex.: dados sobre consumo de energia dos últimos 15 anos
Tópicos em Avaliação do Conhecimento
Descoberto
Testes estatísticos para determinar a performance de
diferentes esquemas de aprendizado de máquina
 Escolha da medida de performance

• Número de classificações corretas
• Precisão da previsão de probabilidade em classes
• Erros em previsões numéricas

Custos associados a diferentes tipos de erros
• Muitas aplicações práticas envolvem custos
Avaliação do Conhecimento Descoberto



Motivação
Treinamento e teste
Estimando performance
• Cross-validation
• Leave-one-out cross-validation
• Bootstrap



Comparando esquemas de
aprendizado
Predizendo probabilidades
Contabilizando o custo de
previsões erradas
• Lift charts
• ROC curves



Avaliando previsões numéricas
Medidas de avaliação do
conhecimento descoberto
O princípio MDL
Treinamento e Teste

Medida natural para classificação de problemas: taxa de
erro
• Acerto: instância da classe é prevista corretamente
• Erro: instância da classe é prevista incorretamente
• Taxa de erro: proporção dos erros sobre todo o conjunto de
instâncias

Erro de resubstituição: taxa de erro obtida do conjunto
de treinamento
 Erro de resubstituição é (esperançosamente) otimista !
Treinamento e Teste

Conjunto de teste: conjunto de instâncias independentes
que não são utilizadas na formação do classificador
• Suposição: tanto o conjunto de dados para treinamento como o
conjunto de dados para teste são exemplos representativos do
problema em questão

Dados de teste e treinamento podem ser naturalmente
diferentes
• Exemplo: classificadores construidos utilizando-se dados de duas
cidades diferentes A e B

Estimar a performance de um classificador da cidade A e testá-lo
utilizando-se dados da cidade B
Observações sobre Ajuste de Parâmetros
É importante que os dados de teste não sejam utilizados
para criação do classificador
 Alguns esquemas de aprendizado operam em dois estágios

• Estágio 1: construção da estrutura básica
• Estágio 2: otimização dos parâmetros
Os dados de teste não podem ser utilizados para ajuste
dos parâmetros
 Procedimentos apropriados utilizam três conjuntos:
dados de treinamento, validação e teste

• Dados de validação são utilizados para otimização dos parâmetros
Aproveitando Melhor os Dados
Uma vez que a avaliação está completa, todos os dados
podem ser utilizados na construção do classificador final
 Geralmente, quanto maior o conjunto de dados para
treinamento, melhor o classificador
 Quanto maior o conjunto de dados para teste, mais
precisa a estimativa de erro
 Procedimento Holdout: método para divisão dos dados
originais nos conjuntos de treinamento e teste

• Dilema: idealmente queremos os dois, um grande conjunto de
dados para treinamento e para teste
Avaliação do Conhecimento Descoberto



Motivação
Treinamento e teste
Estimando performance
• Cross-validation
• Leave-one-out cross-validation
• Bootstrap



Comparando esquemas de
aprendizado
Predizendo probabilidades
Contabilizando o custo de
previsões erradas
• Lift charts
• ROC curves



Avaliando previsões numéricas
Medidas de avaliação do
conhecimento descoberto
O princípio MDL
Estimando Performance

Assuma uma taxa de erro estimada de 25%. O quão perto
esta taxa está da taxa de erro real?
• Depende do volume de dados para teste

Previsão é como jogar uma moeda viciada
• “Cara” é um “acerto”, “coroa” é um “erro”

Em estatística, uma sucessão de eventos independentes
como este é chamado de um processo Bernoulli
• A teoria estatística nos provê com intervalos de confidência que
mostra a proporção em que a verdade se fundamenta
Intervalos de Confidência
Nós podemos dizer: p possui um certo intervalo
especificado com uma certa confidência especificada
 Exemplo: S=750 acertos em N=1000 tentativas

• Taxa de acerto estimada: 75%
• O quão próximo esta taxa está da verdadeira taxa de acerto p?


Resposta: com 95% de confidência p  [73.3, 76.8]
Outro exemplo: S=75 e N=100
• Taxa de acerto estimada: 75%
• Com 95% de confidência p  [70.0, 81.0]
Média e Variância
Média e variância para um teste Bernoulli: p, p(1-p)
 Taxa de acerto esperada f =S/N
 Média e variância para f: p, p(1-p)/N
 Para um N suficientemente grande, f segue uma
distribuição normal
 c% intervalo de confidência [-z  X  z] para uma variável
aleatória com média 0 é dada por: Pr[-z  X  z] = c
 Dando uma distribuição simétrica:
Pr[-z  X  z] = 1 - (2*Pr[X  z])

Limites de Confidência



Limites de confidência para uma distribuição normal com
média 0 e variância 1:
Assim: Pr[-1,65  X  1,65] = 90%
Pr[X >= z]
0,1%
0,5%
1%
5%
10%
20%
40%
z
3,09
2,58
2,33
1,65
1,28
0,84
0,25
Para utilizar isto, temos que reduzir nossa variável
aleatória f para que tenha média 0 e variância unitária
Transformando f

Valor transformado para f:
f p
p(1  p) / N
(i.e. subtração da média e divisão pelo desvio padrão)

 Equação resultante: P r z 



f p
 z  c
p(1  p) / N

Resolvida para p:
2
2
2

z
f
f
z
p f 
z


2

2
N
N
N
4
N

  z2 
 / 1  

 
N


Exemplos
f=75%, N=1000, c=80% (então z=1.28):
p [0.732, 0.767]
 f=75%, N=100, c=80% (então z=1.28):
p [0.691, 0.801]

Note que a suposição de distribuição normal somente é
válida para um N “grande” (i.e. N > 100)
 f=75%, N=10, c=80% (então z=1.28):
p [0.549, 0.881]

Estimativa Holdout
O que devemos fazer se a quantidade de dados é
limitada?
 O método holdout reserva uma certa quantidade de
dados para teste e utiliza o restante para treinamento

• Normalmente: um terço para teste, o restante para treinamento

Problema: os exemplos podem não ser representativos
• Exemplo: classe faltando nos dados de teste

A versão avançada utiliza estratificação
• Garante que cada classe esteja representada com
aproximadamente a mesma proporção em ambos conjuntos
Método Holdout Repetitivo

A estimativa holdout pode se tornar mais confiável se
repetirmos o processo com diferentes subexemplos
• Em cada iteração, uma certa proporção é aleatoriamente
selecionada para treinamento (possivelmente com estratificação)
• Um média das taxas de erro nas diferentes iterações é calculada
para produção de uma taxa de erro geral

Continua não sendo ótimo: diferentes conjuntos de teste
se sobrepõem
• Podemos prevenir sobreposição?
Cross-validation

Cross-validation evita sobreposição de conjuntos de
teste
• Primeiro passo: os dados são divididos em k subconjuntos de
tamanho igual
• Segundo passo: cada subconjunto, em fila, é utilizado para teste
e o restante para treinamento
Este processo é chamado k-fold cross-validation
 Geralmente os subconjuntos são estratificados antes que
a validação cruzada seja realizada
 Calcula-se a média dos erros estimados a fim de se
produzir uma estimativa de erro geral

Cross-validation
Método padrão de avaliação: ten-fold cross-validation
estratificado
 Por que dez? Experimentos extensivos mostraram que
esta é a melhor escolha a fim de se conseguir uma
estimativa precisa

• Também existem algumas evidências teóricas
Estratificação reduz a variação da estimativa
 Ainda melhor: cross-validation estratificado repetitivo

• Ten-fold cross-validation é repetido dez vezes e a média dos
resultados é calculada
Leave-one-out Cross-validation

É uma forma particular de cross-validation:
• O número de “folds” é fixado com o número de instâncias para
treinamento
• Um classificador tem que ser construído n vezes, onde n é o
número de instâncias para treinamento
Faz uso máximo dos dados
 Não envolve o uso de subexemplos aleatórios
 Computacionalmente muito caro

LOO-CV e Estratificação

Outra desvantagem do LOO-CV: não é possível
estratificação
• Há apenas uma instância no conjunto de teste

Exemplo extremo: conjunto de dados completamente
aleatório com duas classes em igual proporção
• Melhor indutor que prevê a classe majoritária (resulta em 50%)
• A estimativa LOO-CV para este indutor seria de uma taxa de
erro de 100%
Bootstrap

CV utiliza exemplos sem substituição
• A mesma instância, uma vez selecionada, não pode ser selecionada
novamente para um conjunto de treinamento/teste em particular

O bootstrap é um método de estimativa que utiliza
exemplos com substituição para formar o conjunto de
treinamento
• Um conjunto de dados com n instâncias é utilizado n vezes a fim
de formar um novo conjunto de dados com n instâncias
• Estes dados são utilizados como conjunto de treinamento
• As instâncias do conjunto de dados original que não ocorrem no
novo conjunto de treinamento são utilizadas para teste
0.632 Bootstrap

Este método também é conhecido como 0.632 bootstrap
• Uma particular instância tem a probabilidade de 1-1/n de não ser
utilizada
• Assim, sua probabilidade de terminar nos dados de teste é:
n
 1
1
1    e  0.368
 n
• Isto significa que o conjunto de dados para treinamento irá
conter aproximadamente 63.2% das instâncias
Estimando Erro Com o Bootstrap

O erro estimado nos dados de teste será muito
pessimista
• Ele contém apenas ~63% das instâncias

Assim, ele é combinado com o erro de resubstituição:
err  0.632 etest instances  0.368 etraininginstances
O erro de resubstituição tem menor peso que o erro nos
dados de teste
 O processo é repetido várias vezes, com diferentes
exemplos gerados, toma-se a média dos resultados

Observações sobre Bootstrap
É provavelmente a melhor maneira para estimativa de
performance em conjuntos de dados muito pequenos
 Entretanto, possui alguns problemas

• Considerando o conjunto de dados aleatório anterior
• Um perfeito memorizador alcançará 0% de erro de
resubstituição e ~50% de erro nos dados de teste
• Bootstrap estimará para este classificador:
err = 0.632 x 50% + 0.368 x 0% = 31.6%
• Verdadeira taxa de erro esperada: 50%
Avaliação do Conhecimento Descoberto



Motivação
Treinamento e teste
Estimando performance
• Cross-validation
• Leave-one-out cross-validation
• Bootstrap



Comparando esquemas de
aprendizado
Predizendo probabilidades
Contabilizando o custo de
previsões erradas
• Lift charts
• ROC curves



Avaliando previsões numéricas
Medidas de avaliação do
conhecimento descoberto
O princípio MDL
Comparando Esquemas de Aprendizado
Situação freqüente: queremos saber entre dois esquemas
de aprendizado qual o de melhor performance
 Nota: isto é dependente do domínio
 Caminho óbvio: compare estimativas 10-fold CV
 Problema: variação na estimativa
 A variação pode ser reduzida utilizando-se CV repetitivo
 Entretanto, ainda não sabemos se os resultados são
confiáveis

Testes de Significância
Testes de significância nos diz o quão confidentes
podemos ser que realmente existe uma diferença
 Hipótese nula: não há diferença “real”
 Hipótese alternativa: há uma diferença
 Um teste de significância mede quanta evidência existe
em favor de rejeitar-se a hipótese nula
 Se estivermos utilizando 10-fold CV 10 vezes
 Então nós queremos saber se as duas médias das
estimativas do 10 CV são significantemente diferentes

Paired t-test

Student´s t-test nos diz se a média de dois exemplos são
significantemente diferentes
 Os exemplos individuais são tomados do conjunto de
todos as estimativas cross-validation possíveis
 Nós utilizamos o paired t-test porque os exemplos
individuais são casados
• O mesmo CV é aplicado duas vezes, uma para cada esquema

Fazendo x1, x2, ..., xk e y1, y2, ..., yk serem os 2k
exemplos para um k ten-fold CV
Distribuição das Médias
Sendo mx e my as médias dos respectivos exemplos
 Se existirem exemplos suficientes, a média de um
conjunto independente de exemplos é normalmente
distribuída
 As variâncias estimadas das médias são x2/k e y2/k
 Se x e y são as verdadeiras médias então
mx   x m y   y

 x2 / k
 y2 / k
são aproximações normalmente distribuídas com média 0
e variância unitária
Distribuição Student
Com exemplos pequenos (k < 100) a média segue a
distribuição student com k -1 graus de liberdade
 Limites de confidência para 9 graus de liberdade
(esquerda), comparado a limites para uma distribuição
normal (direita):

Pr[X>=z]
0,1%
0,5%
1%
5%
10%
20%
z
4,30
3,25
2,82
1,83
1,38
0,88
Pr[X>=z]
0,1%
0,5%
1%
5%
10%
20%
z
3,09
2,58
2,33
1,65
1,28
0,84
Distribuição das Diferenças
Seja md = mx - my
 A diferença das médias (md) também tem uma
distribuição student com k-1 graus de liberdade
 Seja d2/k a variância da diferença
 A versão padronizada de md é chamada t-statistic:
md
t
 d2 / k


Nós utilizamos t para realizar o t-teste
Realizando o Teste

Fixe um nível de significância 
• Se a diferença está significantemente no nível % há uma chance
de (100 - )% de que realmente exista uma diferença

Divida o nível de significância por dois já que o teste é
“two-tailed”
• A verdadeira diferença pode ser positiva ou negativa
Verifique o valor de z que corresponde a /2
 Se t  -z ou t  z então a diferença é significante

• A hipótese nula pode ser rejeitada
Observações
Se as CV estimadas forem de diferentes sorteios, não há
mais “casamento”
 Talvez nós ainda usemos k-fold CV para um esquema e
j-fold CV para outro
 Então devemos utilizar o t-teste unpaired com min(k,j)-1
graus de liberdade
 A t-statistic se torna:

t
mx  my
 x2
k

 y2
l
Notas sobre a Interpretação do Resultado
Toda estimativa cross-validation é baseada no mesmo
conjunto de dados
 Portanto, o teste apenas nos diz quando um completo
k-fold CV para este conjunto de dados irá mostrar uma
diferença

• Um k-fold CV completo irá gerar todas as possíveis partições dos
dados em k conjuntos e calcular a média dos resultados

Idealmente, nós queremos conjuntos de dados de
exemplo diferentes para cada estimativa k-fold CV
usando o teste para julgar a performance através de
diferentes conjuntos de treinamento
Avaliação do Conhecimento Descoberto



Motivação
Treinamento e teste
Estimando performance
• Cross-validation
• Leave-one-out cross-validation
• Bootstrap



Comparando esquemas de
aprendizado
Predizendo probabilidades
Contabilizando o custo de
previsões erradas
• Lift charts
• ROC curves



Avaliando previsões numéricas
Medidas de avaliação do
conhecimento descoberto
O princípio MDL
Predizendo Probabilidades
Medida de performance: taxa de acerto
 Também chamada função de perda 0-1:


i
0 se a prediçãoé correta
1 se a prediçãoé incorreta
Muitos classificadores produzem classes de
probabilidades
 Dependendo da aplicação, nós podemos querer checar a
precisão das estimativas de probabilidade
 Perda 0-1 não é o modelo correto a ser utilizado nestes
casos

Função de Perda Quadrática
p1, ..., pk são probabilidades estimadas para uma instância
 Seja c o índice da classe atual da instância
 a1, ..., ak = 0, exceto para ac, que é 1
 A “perda quadrática” é: 
 


2
2
E   p j  a j      p 2j   1  pc 
 j
  j c 

Justificativa:


2
E  ( p j  a j )    E p 2j  2 E p j a j  E a 2j
 j
 j
 



  p  2pj p  p   pj  p
j
2
j
*
j
*
j
j
  


* 2
j

 p *j 1  p*j

Função de Perda Informacional
A “informational loss function” é –log(pc), onde c é o
índice da classe atual da instância
 Número de bits necessários para comunicar a classe atual

• Ex.: “cara ou coroa” - log2 1/2 = 1
Sejam p1*, ..., pk* as probabilidades verdadeiras das
classes
 Então o valor esperado para a “função de perda” é:

 p1* log2 p1   pk* log2 pk
Justificativa: minimizado para pj = pj*
 Dificuldade: problema da freqüência zero

• Se a probabilidade é zero, o valor da função é -
Observações

Qual “função de perda” deveríamos escolher?
• A “quadratic loss function” leva em conta todas as probabilidades
de classes estimadas para uma instância
• A “informational loss” foca somente na probabilidade estimada
para a classe atual
• A “quadratic loss” é restringida por 1 
p 2j

Nunca poderá exceder a 2

• A “informational loss” poderã ser infinita

j
A “informational loss” está relacionada ao princípio MDL
Avaliação do Conhecimento Descoberto



Motivação
Treinamento e teste
Estimando performance
• Cross-validation
• Leave-one-out cross-validation
• Bootstrap



Comparando esquemas de
aprendizado
Predizendo probabilidades
Contabilizando o custo de
previsões erradas
• Lift charts
• ROC curves



Avaliando previsões numéricas
Medidas de avaliação do
conhecimento descoberto
O princípio MDL
Contabilizando os Custos
Na prática, diferentes tipos de erros de classificação
geralmente incorrem em diferentes custos
 Exemplos:

•
•
•
•
Decisões de empréstimo
Detecção de vazamento de óleo
Diagnóstico de falha
Cartas promocionais

enviar carta p/ família q ñ responderá x ñ enviar carta p/ família q
responderá
Mantendo Custos em Conta

A matriz “confusão”:
Classe
Atual
Yes
No

Predicted class
Yes
No
True
False
positive
negative
False
True
positive
negative
Há muitos outros tipos de custos
• Custos de coleta de dados para treinamento
Lift Charts
Na prática, custos raramente são desconhecidos
 Decisões são tomadas geralmente pela comparação de
cenários possíveis
 Exemplo: cartas promocionais

• Situação 1: classificador prevê que 0,1% de todos as famílias irão
responder = 1.000 respostas
• Situação 2: classificador prevê que 0,4% das 10.000 famílias mais
promissoras irão responder = 400 respostas
• Situação 3: classificador prevê que 0,2% de 400.000 famílias
irão responder = 800 respostas

Um lift chart permite uma comparação visual
Gerando um Lift Chart

Instâncias são classificadas de acordo com suas
probabilidades previstas de serem um “true positive”:
Rank
1
2
3
4
...

Predicted probability
0,95
0,93
0,93
0,88
...
Actual class
Yes
Yes
No
Yes
...
Em um lift chart, o eixo x é o tamanho do exemplo e o
eixo y é o número de “true positives”
Exemplo de um Lift Chart
ROC Curves

Curvas ROC são similares a lifit charts
• “ROC” vem de “receiver operating characteristic”
• Utiliza um sinal de detecção para mostrar o tradeoff entre a
taxa de acerto (hit rate) e a taxa de alarme falso (false alarm
rate) acima do canal de ruído (noisy channel)

Diferenças do lift chart:
• O eixo y mostra o percentual de true positives em um exemplo
(em vez do valor absoluto)
• O eixo x mostra o percentual de false positives em um exemplo
(em vez do tamanho do exemplo)
Exemplo de uma ROC Curve
Cross-validation e Roc Curves

Método simples para criar uma curva Roc utilizando
cross-validation:
• Coletar probabilidades de instâncias em conjuntos de teste
• Classificar as instâncias de acordo com as probabilidades
Este método é implementado no WEKA
 Entretanto, esta é apenas uma possibilidade

• O método descrito no livro gera uma curva ROC para cada
conjunto e calcula a média entre eles
Roc Curves para Dois Esquemas
Convex Hull
Dados dois esquemas de aprendizado, podemos alcançar
qualquer ponto no convex hull
 Taxas TP e FP para o esquema 1: t1 e f1
 Taxas TP e FP para o esquema 2: t2 e f2
 Se o esquema 1 é utilizado para prever 100 x q% dos
casos e o esquema 2 para o restante, então tomamos:

• Taxa TP para o esquema combinado: q x t1 + (1-q) x t2
• Taxa FP para o esquema combinado: q x f1 + (1-q) x f2
Aprendizado Sensível ao Custo

A maioria dos esquemas de aprendizado não realizam
aprendizado sensível ao custo
• Eles geram o mesmo classificador não importando qual o custo
associado a diferentes classes
• Exemplo: aprendizado de árvore de decisão padrão

Métodos simples para aprendizado sensível ao custo:
• Reutilização de instâncias de acordo com os custos
• Utilização de pesos para instâncias de acordo com os custos

Alguns esquemas são sensíveis ao custo de forma
inerente, ex. naive Bayes
Medidas de Retorno da Informação
Percentual dos documentos retornados que são
relevantes: precision = TP/TP+FP
 Percentual dos documentos relevantes que são
retornados: recall = TP/TP+FN
 A curva precision/recall tem a forma hiperbólica
 Sumário das medidas: precisão média de 20%, 50% e
80% recall (three-point average recall)
 F-measure = (2 x recall x precision)/(recall + precision)

Sumário das Medidas
Lift chart
Domain
Marketing
ROC curve Communications
Recallprecision
curve
Information
retrieval
Plot
TP
Subset
size
TP rate
FP rate
Recall
Precision
Explanation
TP
(TP+FP)/
(TP+FP+TN+FN)
TP/(TP+FN)
FP/(FP+TN)
TP/(TP+FN)
TP/(TP+FP)
Avaliação do Conhecimento Descoberto



Motivação
Treinamento e teste
Estimando performance
• Cross-validation
• Leave-one-out cross-validation
• Bootstrap



Comparando esquemas de
aprendizado
Predizendo probabilidades
Contabilizando o custo de
previsões erradas
• Lift charts
• ROC curves



Avaliando previsões numéricas
Medidas de avaliação do
conhecimento descoberto
O princípio MDL
Avaliando Previsões Numéricas
Algumas estratégias: conjunto de teste independente,
cross-validation, testes de significância, etc.
 Diferença: medidas de erro
 Valores alvo atuais: a1, a2, ..., an
 Valores alvo previstos: p1, p2, ..., pn
 Medida mais popular: erro do quadrado da média (meansquared error)
 p1  a1 2     pn  an 2
n

• Fácil para manipulação matemática
Outras Medidas

A raiz do erro do quadrado da média:
 p1  a1 2     pn  an 2
n

O erro médio absoluto é menos sensível a outliers que o
erro do quadrado da média:
p1  a1    pn  an
n
 Às vezes valores de erros relativos são mais apropriados
que valores absolutos
• 10% corresponde a um erro de 50 quando prevendo 500
• 10% corresponde a um erro de 0,2 quando prevendo 2
Aprimoramento da Média
Sempre queremos saber quanto o esquema é aprimorado
simplesmente prevendo a média
 O erro quadrado relativo é (ā é a média):

 p1  a1 2     pn  an 2
a  a1 2    a  an 2

O erro absoluto relativo é:
p1  a1    pn  an
a  a1    a  an
O Coeficiente de Correlação

Mede a correlação estatística entre os valores previstos
e os valores atuais
S PA
SP S A
S PA 
 ( pi  p)(ai  a )
i
n 1
SP 
2
(
p

p
)
 i
i
n 1
SA 
Escala independente, entre –1 e +1
 Boa performance leva a grandes valores

 (a  a )
i
i
n 1
2
Qual a melhor medida?
Melhor verificar todas elas
 Geralmente não importa
 Exemplo:

Raiz do erro da média quadrada
Erro da média absoluta
Raiz do erro relativo quadrado
Erro relativo absoluto
Coeficiente de correlação
A
67,8
41,3
42,2%
43,1%
0,88
B
91,7
38,5
57,2%
40,1%
0,88
C
63,3
33,4
39,4%
34,8%
0,89
D
57,4
29,2
35,8%
30,4%
0,91
Avaliação do Conhecimento Descoberto



Motivação
Treinamento e teste
Estimando performance
• Cross-validation
• Leave-one-out cross-validation
• Bootstrap



Comparando esquemas de
aprendizado
Predizendo probabilidades
Contabilizando o custo de
previsões erradas
• Lift charts
• ROC curves



Avaliando previsões numéricas
Medidas de avaliação do
conhecimento descoberto
O princípio MDL
Medidas de Avaliação do Conhecimento
Descoberto

Piatetsky-Shapiro’s Rule-Interest Function
• É usada para quantificar a correlação entre atributos em um
classificador de regras simples
• Uma regra de classificação simples é aquela em que os lados
esquerdo e direito de uma implicação lógica (X  Y) corresponde
a um atributo simples
XY
RI  X  Y 
N
• Quando RI = 0, então X e Y são estatisticamente independentes
e a regra não é interessante
• Quando RI > 0 (RI < 0), então X é positivamente (negativamente)
correlacionado a Y
Medidas de Avaliação do Conhecimento
Descoberto

Smyth and Goodman’s J-Measure
• É utilizado para encontrar as melhores regras relacionando
atributos de valores discretos

Major and Mangano’s Rule Refinement
• É uma estratégia usada para induzir regras de classificação
interessantes de um banco de dados de regras de classificação
• Consiste em três fases: identificar regras potencialmente
interessantes, identificar regras tecnicamente interessantes, e
remover regras que não sejam genuinamente interessantes

Agrawal and Srikant’s Itemset Measures
• Utilizada para identificar regras de classificação que ocorrem
com freqüência de conjuntos de itens em grandes bancos de
dados
Medidas de Avaliação do Conhecimento
Descoberto

Klemettinen et al. Rule Templates
• Utilizada para descrever um padrão para os atributos que podem
aparecer no lado esquerdo ou direito em uma regra de associação

Matheus and Piatetsky-Shapiro’s Projected Savings
• Avalia o impacto financeiro dos custos de desvios de valores
esperados

Hamilton and Fudger’s I-Measures
• Usadas para quantificar a significância do conhecimento
descoberto, apresentadas na forma de relações generalizadas ou
sumários
• Baseada na estrutura das hierarquias conceituais associadas aos
atributos na relação original não generalizada
Medidas de Avaliação do Conhecimento
Descoberto

Silbershatz and Tuzhilin’s Interestingness
• Determina a extensão em que uma crença “suave” é mudada como
resultado da descoberta de uma nova evidência

Kamber and Shinghal’s Interestingness
• Determina o nível de interesse de uma regra de classificação
baseada na necessidade e suficiência

Hamilton et al. Credibility
• Determina a extensão com que um classificador provê decisões
para todos ou quase todos valores possíveis dos atributos de
condição, baseada em evidência adequadamente suportada

Liu et al. General Impressions
• Usada para avalia a importância de regras de classificação pela
comparação das regras descobertas com uma descrição
aproximada ou vaga do que é considerado ser interessante
Medidas de Avaliação do Conhecimento
Descoberto

Gago and Bento’s Distance Metric
• Mede a distância entre duas regras e é usada para determinar as
regras que provêm a mais alta cobertura para os dados
fornecidos

Freita’s Surprisingness
• Medida que determina o interesse do conhecimento descoberto
via detecção explícita de ocorrências do paradoxo de Simpson

Gray and Orlowska’s Interestingness
• Usada para avaliar o poder de associações entre conjuntos de
intens em transações a varejo (i.e., regras de associação)

Dong and Li’s Interestingness
• Usada para avaliar a importância de uma regra de associação por
considerar sua “não expectativa” em termos de outras regras de
associação em sua vizinhança
Medidas de Avaliação do Conhecimento
Descoberto

Liu et al. Reliable Exceptions
• Uma exceção confiável é uma regra frágil que tenha suporte
relativamente pequeno e confidência relativamente alta

Zhong et al. Peculiarity
• Usada para determinar a extensão com que um objeto de dado
difere de outros objetos de dado similares
Avaliação do Conhecimento Descoberto



Motivação
Treinamento e teste
Estimando performance
• Cross-validation
• Leave-one-out cross-validation
• Bootstrap



Comparando esquemas de
aprendizado
Predizendo probabilidades
Contabilizando o custo de
previsões erradas
• Lift charts
• ROC curves



Avaliando previsões numéricas
Medidas de avaliação do
conhecimento descoberto
O princípio MDL
O Princípio MDL
MDL se origina de minimum description length (mínimo
tamanho da descrição)
 O tamanho da descrição é definido como:

espaço necessário para descrever a teoria
+
espaço necessário para descrever os erros da teoria
Em nosso caso a teoria é o classificador e os erros da
teoria são os erros nos dados de treinamento
 Alvo: queremos classificar com o mínimo DL
 Princípio MDL é um critério para seleção do modelo

Critérios para Seleção do Modelo

O critério para seleção do modelo tenta encontrar um
bom compromisso entre:
• A complexidade de um modelo
• Sua precisão de predição nos dados de treinamento
Conclusão: um bom modelo é um modelo simples que
alcança alta precisão nos dados fornecidos
 Também conhecido como Occam’s Razor: a melhor teoria
é a menor delas que descreve todos os fatos

Elegância x Erros
Teoria 1: muito simples, teoria elegante que explica a
maioria dos dados perfeitamente
 Teoria 2: uma teoria significantemente mais complexa
que reproduz os dados sem erros
 A teoria 1 é provavelmente a preferida
 Exemplo clássico: as três leis de Kepler no movimento
planetário

• Menos precisa que o último refinamento de Copérnico da teoria
Ptolemaica de epicicles
Observações
Vantagem: faz uso total dos dados de treinamento
quando selecionando um modelo
 Desvantagem 1: esquema de codificação apropriado/
probabilidades prévias para as teorias são cruciais
 Desvantagem 2: não há garantia de que a teoria MDL é
aquela que minimiza os erros esperados
 Nota: Occam’s Razor é um axioma
 Princípio de Epicuro de múltiplas explicações: pegue
todas as teorias que são consistentes com os dados
