Marcus Sampaio
DSC/UFCG
Mineração de Dados
Marcus Sampaio
Pós-Graduação em Informática da UFCG
http://www.dsc.ufcg.edu.br/~sampaio/cursos/2006.2/PosGraduacao/Mineracao
DeDados/
Marcus Sampaio
DSC/UFCG
Sumário
Contexto
Mineração de Dados
Exemplo de Motivação
Modelos e Padrões
Algoritmos de Mineração de Dados
Métricas de Mineração de Dados
Questões em Aberto
Avaliação da Disciplina
Marcus Sampaio
DSC/UFCG
Contexto
Marcus Sampaio
DSC/UFCG
• Empresas mantêm grandes bancos de dados (BD),
contendo verdadeiras minas de informação
• Informação é a alma do negócio
• Muita informação jamais é recuperada
– Os usuários não se lembram de perguntar, ou não sabem
como pergundar
• Os modernos SGBDs incorporam algumas técnicas
de mineração de dados (MD)
– A integração SGBD-MD é ainda incipiente
Mineração de Dados
Marcus Sampaio
DSC/UFCG
• Mineração de Dados é uma tecnologia capaz de
descobrir padrões de informação ‘escondidos’ em um
BD
– Padrão  Freqüência, Repetição  BD desnormalizado
• Outras denominações
– Análise de Dados Exploratória
– Descoberta Dirigida a Dados
– Aprendizagem Indutiva
• Implementa o conceito de consulta aberta ou semiaberta
– Consultas tradicionais são fechadas, ou completamente
definidas
Mineração de Dados (2)
Marcus Sampaio
DSC/UFCG
• Consultas Abertas ou Semi-Abertas
– Consulta: Pode não ser bem formada, ou
formulada imprecisamente. O minerador pode nem
mesmo saber exatamente o que ele quer ver
– Dados: Como se trata de descobrir padrões
(repetições), dados normalizados (sem repetições)
não facilitam a tarefa de mineração. A solução é
gerar arquivos intermediários não normalizados do
BD operacional normalizado
– Saída: Não é um subconjunto do BD. Em vez
disso, é o resultado de alguma análise sobre o
conteúdo do BD
Exemplo de Motivação
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?
Marcus Sampaio
DSC/UFCG
Exemplo de Motivação (2)
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
Exemplo de Motivação (3)
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
Exemplo de Motivação (4)
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
Exemplo de Motivação (5)
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
Exemplo de Motivação (6)
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 se ... então
– Regra se ... então é um modelo de conhecimento
• Existem muitos modelos de conhecimento
• 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 da amostra,
podemos extrair mais três regras – verifique)
Exemplo de Motivação (7)
Marcus Sampaio
DSC/UFCG
• Quão confiável é uma regra?
• 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 da amostra
• “Overfitting”
• Qual a freqüência mínima aceitável?
Exemplo de Motivação (8)
Marcus Sampaio
DSC/UFCG
• Modelos são induzidos (ou inferidos) por
algoritmos de mineração
– Existem muitos algoritmos de mineração
• Não existe o melhor algoritmo
– Que fazer?
– Diversos algoritmos poderiam implementar o
nosso robô
– Experimentemos alguns deles
• Biblioteca WEKA
Modelos e Padrões
Marcus Sampaio
DSC/UFCG
• Outra definição de Mineração de Dados
– Tecnologia que visa extrair automaticamente conhecimento
útil, confiável e não trivial  ‘minério’  de um banco de
dados  ‘mina’
• O conhecimento deve ser apresentado segundo um
modelo formal
– Modelo de regras de classificação: se <condição> então
<classificação>
– Instância do modelo: se taxa_de_produção_de_lágrima =
‘reduzida’ então tipo_de_lente = ‘nenhum’
• Não faremos mais distinção entre modelo e instância
• Um modelo é confiável na medida em que ele possa
ser considerado um padrão
– Padrão  freqüência significativa no banco de dados
Modelos ... (2)
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
Modelos ... (3)
Modelo
Preditivo
Classificação
Regressão
Série
Temporal
Descritivo
Clustering
Síntese
Regras de Associação
Descoberta de
Seqüências
Algoritmos de Mineração
de Dados
Marcus Sampaio
DSC/UFCG
• Os algoritmos diferem segundo os modelos
de conhecimento que eles induzem (ou
inferem)
–
–
–
–
–
–
–
Classificação
Regressão
Série Temporal
“Clustering”
Síntese
Regras de Associação
Descoberta de Seqüências
Algoritmos ... (2)
Marcus Sampaio
DSC/UFCG
• Algoritmos de Classificação
– Mapeia dados em classes, ou grupos pré-definidos
• Classes são valores de atributos, chamados de atributos
de classificação
– Classificação supervisionada
– Exemplo 1 (Concessão de crédito bancário)
- Suponha que, com base em informações históricas sobre
clientes, cada cliente é colocado em uma de quatro
classes: (c1) OK, (c2) pedir mais informações, (c3) ñOK e
(c4) chamar a polícia.
Um algoritmo de classificação trabalha em duas fases:
Fase 1: induzir um modelo para as classes
Fase 2: Aplicar o modelo a um novo cliente
- Problema: se a base não fosse classificada?
Algoritmos ... (3)
Marcus Sampaio
DSC/UFCG
– Exemplo 2 (Reconhecimento de padrões)
- Em um aeroporto, características dos passageiros –
distância entre os olhos, tamanho e formato da boca,
formato da cabeça, etc. -- são examinadas. Essas
características são comparadas com entradas em um
banco de dados, para verificar se casam com padrões
associados com diferentes classes de criminalidade
- Concordo que o exemplo é horrível, para não dizer
racista!
Algoritmos ... (4)
Marcus Sampaio
DSC/UFCG
• Algoritmos de Regressão
– Um problema estatístico clássico é experimentar
determinar o relacionamento entre duas variáveis
aleatórias, X e Y, por meio de uma linha reta,
aproximada.
O modelo de regressão linear postula que
Y= a+bX+e
onde e é um resíduo e os coeficientes a and b are
determinados de modo que o resíduo seja o menor
possível
Marcus Sampaio
DSC/UFCG
Algoritmos ... (5)
Rendimento
x
x
x x
x
x
x
x
x
x
x
x
Aplicação no
Tempo
Algoritmos ... (6)
Marcus Sampaio
DSC/UFCG
• Algoritmos de Série Temporal
– Uma série temporal é a variação, com o tempo, do
valor de um certo atributo
• A freqüência das medições pode ser diária, semanal,
horária, etc.
– Pelo exame de um conjunto de séries temporais,
algoritmos podem determinar
• Séries similares
• Predição (como para regressão)
• Propriedades de séries
Algoritmos ... (7)
Marcus Sampaio
DSC/UFCG
Nível de
Estoque
Produto B
Produto A
Produto C
Tempo
• Produto C é menos volátil do que produtos A e B
• Mesma política de estoque para A e B
• Com boa certeza, pode-se fazer predição para C
Algoritmos ... (8)
Marcus Sampaio
DSC/UFCG
• Algoritmos de “Clustering”
– “Clustering” é similar a classificação, exceto que os grupos
(“clusters”) não são pré-definidos – classificação nãosupervisionada
• Segmentação dos dados em grupos, não necessariamente
disjuntos
– Dados similares são agrupados em um mesmo grupo
– Como os grupos não são pré-definidos, um especialista do
domínio da aplicação deve interpretar o significado dos
grupos induzidos
• Classificação supervisionada (cada dado é classificado com o
número de seu grupo) pode ajudar a identificar os grupos
– Indução de um modelo de classificação em que as classes são os
grupos
– Uma possível solução para o problema apontado no exemplo
1
Algoritmos ... (9)
Marcus Sampaio
DSC/UFCG
• Exemplo (Mala Direta)
– Uma cadeia nacional de lojas deseja criar
catálogos específicos, baseados em atributos tais
como renda, localização, características físicas,
etc. Para determinar o público-alvo dos catálogos,
bem como identificar novos e desconhecidos
grupos visando à criação de outros catálogos
específicos, ou ainda catálogos mais específicos
do que os inicialmente pensados, um algoritmo de
“clustering” agrupa os clientes (potenciais) da
cadeia de lojas, segundo certos atributos dos
clientes. Desta forma, um eficiente sistema de
mala direta pode ser construído
Algoritmos ... (10)
Marcus Sampaio
DSC/UFCG
• Algoritmos de Síntese
– Síntese mapeia dados em subconjuntos, segundo
critérios previamente escolhidos
– Também chamada de Caracterização ou
Generalização
– De forma sucinta, caracteriza o conteúdo de um
banco de dados
Algoritmos ... (11)
Marcus Sampaio
DSC/UFCG
• Exemplo (Ranking de Universidades)
– Um dos muitos critérios usados para comparar
universidades por um instituto de pesquisa
americano é o chamado escore ACT. Trata-se de
uma síntese usada para estimar o tipo e o nível
intelectual do corpo estudantil
Algoritmos ... (12)
Marcus Sampaio
DSC/UFCG
• Algoritmos de Regras de Associação
– Uma regra de associação é um modelo que
identifica tipos específicos de associação entre
dados
– Formalmente, é uma extensão de regra de
classificação, em que vários pares atributo-valor
podem aparecer no conseqüente (isto é, o que
vem depois do então)
Algoritmos ... (13)
Marcus Sampaio
DSC/UFCG
• Exemplo (Gerência de Vendas)
– O dono de um mercadinho está decidindo se
coloca um produto X em promoção. A fim de
determinar o impacto dessa decisão, o proprietário
usa um algoritmo que infere regras de associação
que mostram que outros produtos são
freqüentemente comprados junto com o produto X.
Baseado nesses fatos, ele toma algumas
decisões:
• Aproximar, nas prateleiras, os produtos associados
• Não colocar em promoção, ao mesmo tempo, mais de
um produto associado
Algoritmos ... (14)
Marcus Sampaio
DSC/UFCG
• Algoritmos de Descoberta de Seqüências
– Descobrem padrões seqüenciais ou temporais
– Os padrões são similares a associações, porém as
associações são temporais
– Exemplo 1
• Pessoas que compram CD-players, também compram
CDs no espaço de uma semana
– Note que, para que este conhecimento seja válido, é
preciso que seja um padrão (número de repetições acima
de um valor mínimo aceitável)
• Isto vale para qualquer modelo
– O que não é trivial no exemplo é o espaço de uma semana
Algoritmos ... (15)
Marcus Sampaio
DSC/UFCG
• Exemplo 2
– O webmaster de uma companhia X
periodicamente usa um algoritmo que analisa os
dados do log da Web, para saber como os
usuários do site da empresa navegam nele – que
seqüência de páginas são freqüentemente
acessadas?) Desta maneira, ele fica sabendo que
70% dos usuários da página A seguem um dos
seguintes padrões de comportamento: <A,B,C> ou
<A,D,B,C> ou <A,E,B,C>. Ele então determina
criar um link diretamente da página A para a
página C
Métricas de Mineração de
Dados
Marcus Sampaio
DSC/UFCG
• Note que, 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çã dos resultados>
– 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
Métricas ... (2)
Marcus Sampaio
DSC/UFCG
• Métricas
– As tradicionais, como as de espaço e tempo,
baseadas em análise de complexidade
– Para algoritmos de classificação, a acurácia do
conhecimento induzido
• Veremos mais tarde uma definição formal de acurácia
Questões em Aberto
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
• Termos relacionais (<atributo1> <opcomp>
<atributo2>)
– Os termos dos modelos de MD são da forma <atributo>
<opcomp> valor
• Uma enorme simpificação
– Objetivo: produzir algoritmos de complexidade baixa
Questões em Aberto (2)
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 não é um modus operandi realista
Questões em Aberto (3)
Marcus Sampaio
DSC/UFCG
• Facilidade de Assimilação
– Embora alguns algoritmos possam trabalhar bem,
eles podem não ser bem recebidos pelos usuários
se eles produzem conhecimento verborrágico
• Conhecimento inútil misturado com conhecimento útil
• Padrões complexos
• Padrões não sintetizados
Sistema de Avaliação
Marcus Sampaio
DSC/UFCG
• Tarefas Laboratoriais (por equipe)
– Caracterização de um problema de mineraçao
– Solução do problema
• Utilização de algoritmos da biblioteca free WEKA, ou de
outros algoritmos
• Interpretação dos resultados dos algoritmos
• Prova (individual)