SUMÁRIO - AULA1
OO processo
Processo
de KDD de KDD
Interpretação
e Avaliação
Data Mining
Conhecimento
Seleção e
Pré-processamento
Consolidação
de dados
Padrões &
Modelos
Warehouse
Dados
Consolidados
Fontes de dados
p(x)=0.02
Dados Preparados
SUMÁRIO - Aula 2
Algoritmo ID3
usando
Medida de Entropia
e
Medida de Ganho
SUMÁRIO - Aula 3
Aprendizagem Indutiva
Definição de Hipótese
Representação da Hipótese por Árvore de Decisão
Expressividade das Árvores de Decisão
Avaliação da Eficiência de um Algoritmo
SUMÁRIO - Aula 4
Problemas Apropriados
Diferença entre lógica proposicional
e lógica e primeira ordem
Aplicações
Questões Práticas:
- Overfitting
- Atributos com valores contínuos
- Dados ausentes
- Atributos multivalorados
SUMÁRIO - AULA 5
- Como evitar “overfitting” - Poda da árvore
1. Abordagem do conjunto de validação e do
conjunto de teste:
- Reduced-Error Pruning
- Rule Post-Pruning
- Precisão de uma regra.
- Teoria da aprendizagem computacional
- número de exemplos do conjunto de treinamento.
SUMÁRIO - AULA 6
Avaliação de Hipóteses - Vamos discutir medidas para
avaliar hipóteses aprendidas.
1. Ao avaliar hipóteses aprendidas estaremos interessados
em estimar a precisão com que ela classificará futuros
exemplos.
2. Gostaríamos de saber os erros prováveis desta estimativa
de precisão.
Machine Learning - Tom M. Mitchell
Nomenclatura:
X = espaço de possíveis instâncias, ou exemplos (Ex. conjunto
de todas as pessoas) sobre o qual várias funções objetivos
podem ser definidas (Ex. pessoas que planejam comprar novos
eskis este ano).
Suponha que diferentes instâncias em X possam ser
encontradas com diferentes freqüências: existe alguma
distribuição de probabilidade desconhecida D que define a
probabilidade de encontrar cada instância em X. “D não diz
nada sobre se x é um exemplo positivo ou negativo”
A tarefa de aprendizagem consiste em aprender o
conceito ou função objetivo f considerando um espaço
H de possíveis hipóteses.
Exemplos de treino da função objetivo f são fornecidos
ao “aprendiz” por um “supervisor” que extrai cada
instância x independentemente, de acordo com a
distribuição D. Cada instância x junto com seu valor
objetivo f(x) correto é passado ao aprendiz.
Erro Amostral e Erro Verdadeiro
1. Taxa de erro da hipótese sobre a amostra disponível
de exemplos.
2. Taxa de erro da hipótese sobre o conjunto total de
exemplos que ocorrem com uma certa distribuição D.
Definição: O Erro amostral da hipótese h com relação
a função objetivo f e a amostra de dados S é:
1
erroS (h)    ( f ( x), h( x))
n xS
onde n é o número de exemplos em S, e a quantidade  ( f ( x), h( x))
é 1 se f ( x)  h( x) , e 0 caso contrário.
Definição: O Erro Verdadeiro da hipótese h com relação a
função objetivo f e a distribuição D, é a probabilidade que
h classifique errado uma instância retirada aleatoriamente de acordo
com a distribuição D:
erroD (h)  Pr [ f ( x)  h( x)]
xD
O que usualmente desejamos saber é o erro verdadeiro da hipótese,
porque este é o erro que podemos esperar ao aplicar a hipótese a
exemplos futuros.
Segundo Lavrac - 1999(Dissertação de Mestrado de Alan K. Gomes)
Passando uma árvore para regras e considerando as regras
na forma geral:
Co rp o  Ca b eça
ou
Bo d y  Hea d
Usaremos a abreviatura:
B H
Obs: Essas regras preditivas podem ser induzidas por
sistemas de aprendizado proposicional.
Medidas de avaliação de regras pretendem
dar uma indicação
da força(hipotética) de associação(entre Cabeça e Corpo)
expressa por uma regra.
Notações:
Na tabela a seguir B denota o_conjunto de exemplos para os quais
o corpo da regra é verdade e B denota o seu complemento,
ou seja, o conjunto
_ de exemplos para os quais o corpo da regra é
falso. H e H referem-se similarmente à cabeça da regra.
denota então H  B.
HB
| X | x denota a cardinalidade do conjunto X.
A frequência relativa f x é utilizada como uma estimativa da
probabilidade P(X ) , ou seja,
x
P( X )  f x 
n
Tabela de Contingência para uma regra R: B  H
Ela avalia cada regra que faz parte da hipótese induzida.
_
H
B
H
_
bh
bh
_ _
__
B bh
bh
_
h
h
b_
b
n
bh= número de exemplos do conjunto de teste
_
bh
para os quais B é verdade e H é verdade.
= número de exemplos para os quais B é verdade e H
é falso.
n
= número total de exemplos.
Exemplos de Estimativas Probabilidades
P( BH )  P( HB )  f bh
bh

n
___
P( BH )  1  P( BH )
_
__
b h bh
P( B)  P( B H )  P( BH ) 

n
n
__
__
____
_
___
b h bh
P( B )  P( B H )  P( BH )  
n
n
Medidas de Avaliação de Regras
Utilizam o conjunto de teste
Todas as medidas de avaliação de regras consideradas abaixo estão
definidas em termos de estimativas de probabilidade, que são
frequências relativas procedentes da tabela.
Definição 1. Precisão:
Acc( B  H )  P( H | B)
P( HB) f hb hb
P( H | B) 


P( B)
fb
b
A precisão de uma regra é uma medida do quanto uma regra é
específica para o problema.
A definição acima está dentro do framework proposto em
(Lavrac et al., 1999).
Mede a fração de exemplos predito positivos que são verdadeiros
positivos. Quanto maior o valor dessa medida, mais precisamente
a regra cobre corretamente os exemplos de sua classe.
__
Definição 2. Erro:
Err( R)  1  Acc( R)  P( H | B)
Quanto maior o erro menos precisamente a regra cobre corretamente
os exemplos da sua classe.
Outras medidas são:
Confiança negativa,
Sensitividade e Especificidade,
Cobertura e Suporte,
Novidade,
Satisfação.
Pode-se definir essas mesmas medidas como sendo relativas,
usando um peso.
Exemplo para o Conceito Objetivo: Viajar
Considerando as regras R1, R2 e
a precisão e o erro delas resulta em:
4
Acc( R1 )   0.8
5
3
Acc( R2 )   1.0
3
2
Acc( R3 )   1.0
2
R3
da Tabela 3.6 (ver cópia),
Err(R1 )  0.2
Err( R2 )  0.0
Err(R 3 )  0.0
Matriz de Confusão
O termo matriz de confusão refere-se ao classificador,
enquanto a tabela de contigência refere-se a uma única regra.
Ambos os conceitos são semelhantes mas, no primeiro
caso é considerada a hipótese induzida (classificador),
enquanto no segundo, somente cada regra que faz parte da
hipótese induzida.
A matriz de confusão mostra o número de
classificações corretas em oposição às
classificações preditas para cada classe.
Matriz de Confusão para problemas de Classificação Binária
Classe Preditos como C+ Preditos como CC+
Verdadeiros positivos
Tp
C-
Falsos positivos
Fp
Falsos negativos
Fn
Verdadeiros negativos
Tn
Precisão da Precisão
Classe
Total
Tp
T p  Fn
Tp  Tn
Tn
Fp  Tn
n
Onde: Tp é o número de exemplos corretamente classificados como
positivos, Fp é o número de exemplos erroneamente
classificados como positivos e similarmente se definem os
outros. n  Tp  Fn  Fp  Tn .
Matriz de Confusão
Quatro situações podem ocorrer:
1. O exemplo pertence à classe C+ e é predito pelo classificador
como pertencente à classe C+. Neste caso, o exemplo é um
verdadeiro positivo.
2. O exemplo pertence à classe C- e é predito pelo classificador
como pertencente à classe C-. Neste caso, o exemplo é um
verdadeiro negativo.
3. O exemplo pertence à classe C- e é predito pelo classificador
como pertencente à classe C+. Neste caso, o exemplo é um
falso positivo.
4. O exemplo pertence à classe C+ e é predito pelo classificador
como pertencente à classe C-. Neste caso, o exemplo é um
falso negativo.
No exemplo considerado(ver cópia), a hipótese (classificador) induzida
pelo C4.5 rules consiste do conjunto de 5 regras ilustrada na
Tabela3.4(ver copia), mais a regra defaut CLASS=go, que é utilizada
para classificar exemplos que não são cobertos pelas cinco regras
anteriores.
Matriz de Confusão
Classes
C1
Preditos como “go” Preditos como Precisão Precisão
“dont go”
da Classe Total
Tp=8
Fn=1
8/(8+1)
(8+5)/15=0.87
C2
Fp=1
Tn=5
5/(1+6)
Obs: A precisão do classificador(ou da hipótese) é 0.87.