Marcus Sampaio
DSC/UFCG
Alguns slides foram adaptados, traduzidos ou copiados de
Pang-Ning Tan (ver Bibliografia)
Sumário
Contexto
Outro Exemplo de Motivação
Modelos de Conhecimento
Algoritmos de Mineração de Dados
Métricas de Mineração de Dados
Questões em Aberto
Marcus Sampaio
DSC/UFCG
Sumário
Contexto
Outro Exemplo de Motivação
Modelos de Conhecimento
Algoritmos de Mineração de Dados
Métricas de Mineração de Dados
Questões em Aberto
Marcus Sampaio
DSC/UFCG
O Que É / Não É Mineração de
Dados?

O que não é?

Marcus Sampaio
DSC/UFCG
O que é?
– Achar um número de
– Certos nomes são mais freqüentes em
telefone em um
catálogo
certas regiões do Brasil (Cacciola, Armani,
Gutierrez… na Grande São Paulo) Probabilidade
– Procurar numa máquina
de busca informação
sobre “Amazônia”
– Agrupar documentos por similaridade de
contexto (p.e. Amazônia) – Reconhecimento
de Padrões (“Pattern Recognition”)
Marcus Sampaio
DSC/UFCG
• Confluência de várias disciplinas
Machine
Learning
Probability /
Pattern
Recognition
Data Mining
Database
Marcus Sampaio
DSC/UFCG
• Machine Learning
– O conhecimento é induzido (treinado) de um
conjunto de dados de treinamento (ctrein)
• O histórico de mudanças de classes de software é um
exemplo de conjunto de treinamento
– O conhecimento induzido é validado com o auxílio
de um conjunto de teste (ctest)  ctrein  ctest = 
• Se X  Y foi induzido de um conjunto de treinamento,
esta regra deve ser confirmada por um conjunto de teste
– Uma vez validado, o conhecimento pode ser
usado em diferentes aplicações
• Análise de Impacto de Mudança de Software
Marcus Sampaio
DSC/UFCG
• Padrão (“Pattern”)
– A regra X  Y é um padrão
– A qualidade de um padrão é diretamente
proporcional a seu suporte (repetição)
• Banco de Dados (BD)
– Desnormalizados
• A repetição facilita o reconhecimento de padrões
– O histórico de mudanças de classes de software é um BD
desnormalizado
– A conclusão é que os BDs relacionais
normalizados não podem ser usados diretamente
em MD
Sumário
Contexto
Outro Exemplo de Motivação
Modelos de Conhecimento
Algoritmos de Mineração de Dados
Métricas de Mineração de Dados
Questões em Aberto
Marcus Sampaio
DSC/UFCG
Marcus Sampaio
DSC/UFCG
• Um robot que prescreve lentes de contato
– Oftalmologista: quais as condições gerais – padrões – pelas
quais eu sempre tenho receitado lentes de contato duras? ou
gelatinosas? ou não tenho recomendo o uso de lentes?
Caracterização do Problema:
Classificatório
Tid
10
Idade
Idade
Acuidad Astigma Tipo
e Visual
tismo Lente
Marcus Sampaio
DSC/UFCG
Acuidad Astigma Tipo
e Visual
tismo Lente
1
Jovem
Míope
Sim
1
Jovem
Míope
Não
?
2
Jovem
Míope
Sim
1
Jovem
Hiperm
Não
?
3
Velho
Hiperm
Não
2
Jovem
Hiperm
Sim
?
4
Velho
Hiperm
Não
2
Velho
Míope
Não
?
5
Velho
Míope
Não
2
Maduro Míope
Não
?
6
Maduro Míope
Não
1
Maduro Hiperm
Sim
?
7
Jovem
Hiperm
Sim
3
8
Maduro Hiperm
Não
3
9
Jovem
Não
1
10
Maduro Míopr
Sim
2
Hiperm
10
Conj.
Treinamento
Clasificador
Induzido
Conj.
Teste
Modelo
Marcus Sampaio
DSC/UFCG
Conjunto de Treinamento
idade
acuidade visual
astigmatismo
taxa de
produção de
lágrima
tipo de lente
jovem
míope
não
reduzida
nenhum
jovem
míope
não
normal
gelatinosa
jovem
míope
sim
reduzida
nenhum
jovem
míope
sim
normal
dura
jovem
hipermétrope
não
reduzida
nenhum
jovem
hipermétrope
não
normal
gelatinosa
Marcus Sampaio
DSC/UFCG
jovem
hipermétrope
sim
reduzida
nenhum
jovem
hipermétrope
sim
normal
dura
maduro
míope
não
reduzida
nenhum
maduro
míope
não
normal
gelatinosa
maduro
míope
sim
reduzida
nenhum
maduro
míope
sim
normal
dura
maduro
hipermétrope
não
reduzida
nenhum
Marcus Sampaio
DSC/UFCG
maduro
hipermétrope
não
normal
gelatinosa
maduro
hipermétrope
sim
reduzida
nenhum
maduro
hipermétrope
sim
normal
nenhum
idoso
míope
não
reduzida
nenhum
idoso
míope
não
normal
nenhum
idoso
míope
sim
reduzida
nenhum
idoso
míope
sim
normal
dura
Marcus Sampaio
DSC/UFCG
idoso
hipermétrope
não
reduzida
nenhum
idoso
hipermétrope
não
normal
gelatinosa
idoso
hipermétrope
sim
reduzida
nenhum
idoso
hipermétrope
sim
normal
nenhum
Conhecimento Induzido
Marcus Sampaio
DSC/UFCG
• se taxa_de_produção_de_lágrima = ‘reduzida’ então
tipo_de_lente = ‘nenhum’
– Padrão expressado em forma de regra de classificação se
... então classe
• Regra de Classificação é um dentre outros modelos
de conhecimento
– Um outro: Regra de Associação
• A regra se verifica em todos os casos em que a taxa
de produção de lágrima é reduzida?
– Via de regra, não há certeza, apenas probabilidade
• Quantas e quais são as outras regras para não
receitar lente de contato (somente do ctrein, podemos
extrair mais três regras – verifique)
Marcus Sampaio
DSC/UFCG
• Quão confiável é uma regra de classificação?
– se idade = ‘maduro’ e acuidade_visual =
‘hipermétrope’ e astigmatismo = ‘sim’ e
taxa_de_produção_de_lágrima = ‘normal’ então
tipo_de_lente = ‘nenhum’
• Ela se verifica em somente um caso do ctrein
– Provavelmente, não tem validade estatística
• Qual a freqüência mínima estatisticamente
aceitável?
– O conhecimento deve ser validado via o conjunto
de teste
Sobre os Conjuntos de
Treinamento e Teste
Marcus Sampaio
DSC/UFCG
• Note que os conjuntos de treinamento e teste
apresentados certamente não têm validade
estatística
– Um exemplo de ‘brincadeira’
• Necessidade de um processo rigoroso de MD
– Último item da disciplina
Sumário
Contexto
Outro Exemplo de Motivação
Modelos de Conhecimento
Algoritmos de Mineração de Dados
Métricas de Mineração de Dados
Questões em Aberto
Marcus Sampaio
DSC/UFCG
Marcus Sampaio
DSC/UFCG
• Tipos de modelo
– Preditivo
• Faz predição acerca de valores de dados usando
resultados conhecidos de outros dados
• Em geral, a modelagem é baseada em dados históricos,
para fazer predição (ou previsão) sobre novos dados
– Descritivo
• Identifica padrões ou relacionamentos em dados,
históricos ou não
– Importante para se conhecer os dados
Marcus Sampaio
DSC/UFCG
Modelo
Preditivo
Classificação
Regressão
Série
Temporal
Descritivo
Clustering
Síntese
Regra de Associação
Modelos em verde: o foco da disciplina
Descoberta de
Seqüência
Marcus Sampaio
DSC/UFCG
• Modelos de classificação que serão vistos
– Regra de Classificação
– Árvore de Decisão
– Bayes Simples (“Naive Bayes”)
• Modelos de Classificação que não serão
vistos
– Rede Neural
– ...
• Modelo de Regra de Associação
Sumário
Contexto
Outro Exemplo de Motivação
Modelos de Conhecimento
Algoritmos de Mineração de Dados
Métricas de Mineração de Dados
Questões em Aberto
Marcus Sampaio
DSC/UFCG
Marcus Sampaio
DSC/UFCG
• Os algoritmos diferem segundo os modelos
de conhecimento que eles induzem
Modelo
Algoritmo
Regra de Associação Apriori
Árvore de Decisão
Id3, J48
Naive Bayes
NaiveBayeSimple
Regra de
Classificação
Prism
Sumário
Contexto
Outro Exemplo de Motivação
Modelos de Conhecimento
Algoritmos de Mineração de Dados
Métricas de Mineração de Dados
Questões em Aberto
Marcus Sampaio
DSC/UFCG
Marcus Sampaio
DSC/UFCG
• Dado um problema de mineração, há potencialmente
uma grande quantidade de processos de MD que
podem resolver o problema
– Um processo de MD é, simplificadamente, uma tripla
<preparação de dados, execução de um algoritmo de
mineração de dados, avaliação dos resultados>
• Processo de MD será visto no final da disciplina
– Total possível de processos: No. de técnicas de preparação
X no. de algoritmos de MD
• Qual o melhor processo de MD para o problema?
– A resposta depende das métricas de desempenho
escolhidas
Marcus Sampaio
DSC/UFCG
• Métricas
– As tradicionais, como as de espaço e tempo, baseadas em
análise de complexidade de algoritmo
– Para algoritmos de classificação, a acurácia do
conhecimento induzido
• Acurácia de uma regra = No.de acertos treinamento (teste) / No.
de casos cobertos de treinamento (teste)
• Acurácia de um modelo (conjunto de regras) = No.de acertos
treinamento (teste) / Tamanho do conjunto de treinamento
(teste)
• Precisão
• “Recall”
– Para algoritmos de análise de associação
• Suporte
• Confiança
Sumário
Contexto
Outro Exemplo de Motivação
Modelos de Conhecimento
Algoritmos de Mineração de Dados
Métricas de Mineração de Dados
Questões em Aberto
Marcus Sampaio
DSC/UFCG
Marcus Sampaio
DSC/UFCG
• Integração com SGBDs
– Os algoritmos de MD não lêem diretamente de SGBDs
• Dados são extraídos de um BD, via comandos SQL, e
armazenados em um arquivo "flat", desnormalizado
• O arquivo "flat"é a entrada para os algoritmos de mineração
– Note que desnormalização (repetição) favorece a descoberta de
padrões
– BDOR é desnormalizado  implicações?
• Termos relacionais (<atributo1> <opcomp>
<atributo2>)
– Os termos dos modelos de MD são da forma <atributo>
<opcomp> valor
• Uma enorme simplificação
– Objetivo: produzir algoritmos de complexidade baixa
• Porém, limitados
Marcus Sampaio
DSC/UFCG
• Escala
– Algoritmos de MD sem escala são de limitada utilidade
• Minas de Dados são Impuras
– Dados do mundo real têm muita ‘sujeira’, e muito valor
faltando (“null values”). Algoritmos de MD têm que ser
capazes de trabalhar com minas impuras
• Dinâmica dos Dados
– Muitos algoritmos de MD trabalham com dados estáticos
(comportamento invariável, ao longo do tempo). Isto pode
não ser um modus operandi realista
Marcus Sampaio
DSC/UFCG
• Facilidade de Assimilação
– Embora alguns algoritmos possam trabalhar bem,
eles podem induzir modelos muito complexos, de
difícil assimilação mesmo por especialistas
• Conhecimento inútil misturado com conhecimento útil
• Padrões complexos
• Padrões não sintetizados