Marcus SampaioDSC/UFCG
Vários slides foram adaptados, traduzidos ou copiados dePang-Ning Tan (ver Bibliografia)
Marcus SampaioDSC/UFCGEtapas do Processo
Marcus SampaioDSC/UFCG
• Seleção• Pré-Processamento• Transformação• Garimpagem• Análise e Assimilação
Marcus SampaioDSC/UFCGSeleção + Pré-processamento
• Macro etapa Preparação de Dados– Seleção
• Identificação dos bancos de dados • Seleção de atributos• ‘Discretização’ de valores de atributos numéricos
– Pré-processamento• Limpeza• Amostragem
Marcus SampaioDSC/UFCGSeleção de Atributos
• Existem algoritmos que selecionam automaticamente, de um banco de dados, os atributos relevantes para compor as instâncias ou exemplos de mineração– Para Seleção de Atributos, consultar o livro texto,
ou qualquer bom livro de MD• Banco de Dados, no contexto de MD, é
qualquer coleção desnormalizada de documentos– MD e BD Relacional: “Impedance mismatching”
Marcus SampaioDSC/UFCG
‘Discretização’ de Atributos
• Para diminuir a complexidade de um modelo de conhecimento, atributos com domínio devem ser ‘discretizados’– WEKA possui vários algoritmos de ‘discretização’– Alguns algoritmos de MD simplesmente não
trabalham com domínios – Algoritmos que ‘trabalham’ com domínios na
verdade embutem algoritmos de ‘discretização’
Marcus SampaioDSC/UFCG
• Uma verdadeira ‘praga’ em aplicações de mineração de dados é a pobre qualidade dos dados de entrada dos algoritmos
• Uma maneira de resolver ou minimizar o problema é fazer uma inspeção manual nos arquivos de dados. Para arquivos grandes, isto pode ser impraticável
Pré-Processamento: Limpeza
Marcus SampaioDSC/UFCG
• Felizmente, as próprias técnicas de mineração de dados podem ajudar a resolver o problema
• Considere um problema de classificação, e duas espécies de ‘sujeira’: no atributo de classificação, e nos atributos que não são de classificação
• ‘Sujeira’ em atributos de classificação– Remover as instâncias concernentes do conjunto de
treinamento. Como? • Rodando um algoritmo de classificação que procure ser espelho
do conjunto de treinamento 100% de acurácia de treinamento– As instâncias que caem em classes ‘sujas’ são identificadas,
podendo ser fisicamente retiradas
Marcus SampaioDSC/UFCG
• ’Sujeira’ em atributos que não são de classificação – Alguns algoritmos são capazes de descobrir
atributos não confiáveis, logicamente removendo a ‘sujeira’ do conjunto de treinamento
• Exemplo: algoritmo WEKA J48 (Árvores de Decisão)– Pressuposição: ‘sujeiras’ são pouco freqüentes,
comparadas com valores ‘limpos’
• Existem diversas ferramentas para limpeza automática– Remoção lógica– Remoção física
Marcus SampaioDSC/UFCGAmostragem
• A idéia é escolher somente uma parte do conjunto de treinamento ou corpus, mas que seja representativa do conjunto inteiro
• Estado-da-arte em amostragem– Diversas técnicas– Tecnologia relativamente consolidada– Diversas ferramentas existentes no mercado
Marcus SampaioDSC/UFCGEtapas do Processo
• Seleção• Pré-Processamento• Transformação• Garimpagem• Análise e Assimilação
Marcus SampaioDSC/UFCG
• Cada algoritmo de mineração de dados necessita de uma entrada específica
• A finalidade da transformação é então de transformar os dados preparados, de modo a torná-los compatíveis com as entradas dos diversos algoritmos de mineração de dados
• Exemplo 1– Gerar arquivos .arff para usar os algoritmos da
biblioteca WEKA
Transformação
Marcus SampaioDSC/UFCG
WEKA only deals with “flat” files
@relation heart-disease-simplified
@attribute age numeric@attribute sex { female, male}@attribute chest_pain_type { typ_angina, asympt, non_anginal, atyp_angina}@attribute cholesterol numeric@attribute exercise_induced_angina { no, yes}@attribute class { present, not_present}
@data63,male,typ_angina,233,no,not_present67,male,asympt,286,yes,present67,male,asympt,229,yes,present38,female,non_anginal,?,no,not_present...
Marcus SampaioDSC/UFCG
• Exemplo 2– A maioria dos algoritmos de MD implementa
consultas abertas, ou não parametrizadas• Vantagens: o minerador pode dizer “algoritmo, vire-se:
não vou ajudá-lo em nada!”• Desvantagens: muitas vezes, restrições ou parâmetros
são importantes– O minerador pode querer rodar um algoritmo indutor de um
modelo descritivo, para descrever os exemplos de treinamento somente de uma certa classe X
• Restrições ou parâmetros podem ser simulados com uma conveniente transformação dos arquivos de entrada
Marcus SampaioDSC/UFCGEtapas do Processo
• Seleção• Pré-Processamento• Transformação• Garimpagem• Análise e Assimilação
Marcus SampaioDSC/UFCG
• Uma vez os dados preparados e transformados, aplicam-se os algoritmos de mineração de dados, dependendo do problema– Associação– Classificação Supervisionada– Classificação Não-Supervisionada– Série Temporal– Regressão– ...
• Análise estatística da qualidade dos modelos induzidos (ver adiante)
Garimpagem ou Mineração
Marcus SampaioDSC/UFCGEtapas do Processo
• Seleção• Pré-Processamento• Transformação• Garimpagem• Análise e Assimilação
Marcus SampaioDSC/UFCG
• Nesta etapa, a seguinte questão deve ser respondida: o conhecimento induzido é relevante e acionável?– Relevância: conhecimento não trivial– Modelo acionável: que não seja muito complexo,
ou que possa ser assimilado por um especialista • Se a resposta não for satisfatória, então será
necessário repetir todo ou parte do processo de MD (processo iterativo)– Por exemplo, usar um outro algoritmo de indução
de conhecimento
Análise e Assimilação
Marcus SampaioDSC/UFCG
• Métricas de Desempenho dos Algoritmos Indutores
• “Underfitting” e “Overfitting” de Modelos• Fragmentação: Geração de Conjunto-
treinamento e Conjunto-teste• Valores Faltando em Dados para Mineração
Análise Estatística da Qualidade dos Modelos Induzidos
Marcus SampaioDSC/UFCGMétricas de Desempenho
• Acurácia– Aplicável a problemas de classificação– Sinônimo de taxa de acerto (ou de erro)– Em geral, um algoritmo é treinado com um
conjunto-treinamento• Acurácia de treinamento (actrein)
– O modelo induzido é testado com um conjunto-teste• Acurácia de teste (acteste)
– O modelo aprovado é usado para predição• Acurácia de execução estimada, e função da acurácia de
teste (acexec)
Marcus SampaioDSC/UFCG“Overfitting” e “Underfitting”
• Um bom modelo deve ter– Alta acurácia de treinamento– Alta acurácia de teste
• Pode ocorrer que alta actrein baixa acteste
– “Overfitting”• “Underfitting” de um modelo
– Baixa actrein e baixa acteste
• Modelos com “underfitting” e “overfitting” devem ser descartados– Obs: note a importância de acteste
Marcus SampaioDSC/UFCG
Overfitting
Underfitting: quando o modelo é muito simples, tanto as acurácias de treinamento quanto as de teste são baixas
Number of nodesindica o tamanhodo modeloinduzido
Underfitting
Marcus SampaioDSC/UFCG
• Vamos raciocinar agora com taxas de acerto: Quais as causas de “underfitting” e “overfitting”? Note que um e outro conduzem a baixas acurácias de teste
• Considere que um algoritmo trabalha para obter, se for possível, 100% de actrein
– Má distribuição das classes– Ruído ou ‘sujeira’– Falta de representatividade das classes
Conjunto deTreinamento
Marcus SampaioDSC/UFCG
Duas classes
Representações
Pontos circulares
Pontos triangulares
Má Distribuição
Conjunto de Treinamento
Pode conduzir apadrões muito dispersospara as classes (várias regiõesazuis) poucovalor estatístico
Marcus SampaioDSC/UFCGPouca Representatividade
NomeTemp.
do Corpo
Nasc. Uterino
4 Pernas
Hiber-na
Classe
Salamandra
fria não sim sim Não mamífero
“Guppy” fria sim não não Não mamífero
Águia quente não não não Não mamífero
“Poorwill” quente não não sim Não mamífero
“Platypus”
quente não sim sim Mamífero
Marcus SampaioDSC/UFCG
• No exemplo, o conjunto de treinamento não tem erro
• Um classificador* poderia induzir a regra se temperatura do corpo é quente e não hiberna então não é mamífero– Assim, humanos, elefantes e golfinhos seriam
classificados como não mamíferos!– O problema é a falta de representatividade da
regra: só casa com as águias– Assim, teríamos por exemplo 100% de actrein e
70% de acteste, caracterizando “overfitting” *- Um algoritmo indutor de modelos de classificação
Marcus SampaioDSC/UFCG
Note que um padrão para o ponto ‘sujo’ não tem
valor estatístico
Ruído ou ‘Sujeira’
Marcus SampaioDSC/UFCG
Solução para“Underfitting”• O problema de “underfitting” pode ser
resolvido com um conjunto de treinamento de bom tamanho– Técnicas de amostragem ajudam
Marcus SampaioDSC/UFCG
• “Overfitting” resulta de modelos de treinamento que são mais complexos do que o necessário– Regras sem valor estatístico
• Acurácia de treinamento deve ser vista com muita reserva
• Necessidade de novos métodos de estimar acurácia– Acurácia de teste– Acurácia de execução
“Overfitting”: AlgumasConclusões
Marcus SampaioDSC/UFCG
• Conjunto de Treinamento– Treina um algoritmo de mineração– Acurácia de Treinamento
• Conjunto de Teste– Testa o modelo induzido pelo algoritmo– Acurácia de Teste
• Conjunto de Execução (também, Previsão)– Conjunto sobre o qual o modelo é aplicado, para fazer
previsão– Acurácia de Execução (também, Previsão)
• Acurácia de Execução– Acurácia de Execução (estimativa) = f(Acurácia de Teste)
Acurácia Revisitada
Marcus SampaioDSC/UFCG
• Como a acurácia de execução é diretamente proporcional à acurácia de teste, sua estimativa de cálculo pode ser esquecida
Marcus SampaioDSC/UFCG
• “Holdout”• Validação Cruzada (Cross-validation”)• “Bagging”
Métodos deFragmentação de Amostra
Marcus SampaioDSC/UFCG
• “Holdout”– Partição de uma amostra em conjunto de
treinamento e conjunto de teste• Tipicamente, 2/3 para treinamento e 1/3 para teste
– O modelo é induzido do conjunto de treinamento– O modelo induzido é testado com o conjunto de
teste– Principal problema
• Uma classe pode ficar super-representada em um conjunto, e sub-representada em outro; ou
• O modelo pode ser fortemente dependente da composição dos conjuntos
Marcus SampaioDSC/UFCG
• Validação Cruzada (“Cross Validation”)
treinamento
testetreinamento
Marcus SampaioDSC/UFCG
– O algoritmo é treinado com todos os dados• O modelo a ser considerado, se passar pelos testes
– Para calcular a acurácia de teste• Calcula-se a média ou a soma dos acertos dos três testes
realizados• Note que os modelos podem variar pouco, ou até muito! ,
em relação ao modelo induzido para todos os dados • Usa-se cada vez mais "stratified ten-fold cross-
validation“– Estratificação: classes igualmente representadas em todos
os fragmentos– Os dados são aleatoria e estratificadamente divididos em
dez fragmentos – Como consequência da estratificação, os 10 modelos da
iteração são supostamente iguais ao modelo do treinamento do algoritmo
Marcus SampaioDSC/UFCG
• “Bagging” – Técnica de Meta Modelagem– Usa um modelo classificador de modelos
Indução dos ModelosPara cada uma das t iterações (“stratified t-fold cross-validation”)
Aplique um algoritmoSalve o modelo induzido pelo algoritmo
Previsão (ou Predição)Para cada um dos modelos aprovados
Classificar uma instância de execução Retornar a classe mais votada
Marcus SampaioDSC/UFCG
PREDICTED CLASS
ACTUALCLASS
Class=Yes Class=No
Class=Yes a(TP)
b(FN)
Class=No c(FP)
d(TN)
FNFPTNTPTNTP
dcbada
Accuracy
Mais Sobre Acurácia
Marcus SampaioDSC/UFCG
• Note que o cálculo da acurácia no slide anterior é limitado ao caso de duas classes “two-class problem”
• É comum um conjunto de treinamento ter muitas classes
• De qualquer maneira, o valor da acurácia se confunde sempre com a taxa de acerto
Marcus SampaioDSC/UFCG
• Considere um “2-class problem”– Número de instâncias (ou exemplos) de
treinamento da Classe 0 = 9990– Número de exemplos da Classe 1 = 10
• Se um modelo prediz que tudo é da Classe 0 instância de execução 0 , então a acurácia é 9990/10000 = 99.9 %– O valor é enganoso porque o modelo não prevê
qualquer exemplo da Classe 1
Acurácia: Limitações
Marcus SampaioDSC/UFCG
• For large test sets (N > 30), – acc has a normal distribution
with mean p and variance p(1-p)/N
• Confidence Interval for p:
1
)/)1(
(2/12/
ZNpp
paccZP
Area = 1 -
Z/2 Z1- /2
)(2442
2
2/
22
2/
2
2/
ZNaccNaccNZZaccN
p
Intervalo de Confiançapara Acurácia
Marcus SampaioDSC/UFCG
• Consider a model that produces an accuracy of 80% when evaluated on 100 test instances:– N=100, acc = 0.8– Let 1- = 0.95 (95% confidence)
– From probability table, Z/2=1.96
1- Z
0.99 2.58
0.98 2.33
0.95 1.96
0.90 1.65
N 50 100 500 1000 5000
p(lower) 0.670 0.711 0.763 0.774 0.789
p(upper) 0.888 0.866 0.833 0.824 0.811
Marcus SampaioDSC/UFCG
Outras Métricas de Desempenho
spredictionpositivenumberspredictionpositivecorrectnumberprecision
cestaninspositivenumberspredictionpositivecorrectnumber
recall
recallprecisionmeasureF
/1/12
Marcus SampaioDSC/UFCG
• Exemplos– A percentagem de todas as instâncias da classe esporte que
foram classificadas corretamente é o “recall”, ou a cobertura – A percentagem de instâncias corretamente classificadas
como esporte é a precisão– F-measure: média harmônica de precisão e “recall”
• Alta precisão é sempre muito importante, mas muitas instâncias esporte podem ser deixadas de lado (isto é medido por “recall”)
– Programa que identifica “spam e-mail” com alta precisão e baixo “recall
• Deixa “spam” na caixa de entrada (baixo “recall”)• Geralmente acerta quando joga um “spam” no lixo (alta
precisão)– Minha experiência com Google: alta média harmônica
• Alta precisão e alta cobertura
Marcus SampaioDSC/UFCG
• Considere que um sistema de e-mail marcou corretamente 20 e-mails como spam, mas não detectou 5 emails que são spams– Precisão = 20 / 20 = 100%– Recall = 20 / 25 = 80%– F-measure = 2 / (1 + 1 / 0,8) = 0,89
• Interpretação de F-measure– Valor alto: altas precisão e cobertura– Valor baixo: pelo menos uma das medidas
componentes é baixa, comparativamente
Marcus SampaioDSC/UFCG
• Valores faltando são valores NULL• Convivência com valores NULL
– Diversos algoritmos trabalham com valores NULL• É preciso saber como
– Por exemplo, alguns algoritmos smplesmente removem logicamente atributos com pelo menos um valor NULL
• Não convivência com valores NULL– A solução ‘crua’ é remover aquelas instâncias do
conjunto de treinamento com valores NULL• Pode ser muito restritiva, ou mesmo inviável
– Soluções mais sofisticadas permitem estimar os valores faltando de atributos
Valores Faltando
Marcus SampaioDSC/UFCG
Tid Refund Marital Status
Taxable Income Class
1 Yes Single 125K No
2 No Married 100K No
3 No Single 70K No
4 Yes Married 120K No
5 No Divorced 95K Yes
6 No Married 60K No
7 Yes Divorced 220K No
8 No Single 85K Yes
9 No Married 75K No 10
RefundYes No
Class=Yes 0 Class=No 3
Class=Yes 2 Class=No 4
RefundYes
Tid Refund Marital Status
Taxable Income Class
10 ? Single 90K Yes 10
No
Class=Yes 2 + 6/ 9 Class=No 4
Probability that Refund=Yes is 3/9
Probability that Refund=No is 6/9
Assign record to the left child with weight = 3/9 and to the right child with weight = 6/9
Class=Yes 0 + 3/ 9 Class=No 3
Estimativa de Valor