View
109
Download
2
Category
Preview:
Citation preview
Marcus SampaioDSC/UFCG
Mineração de Dados
Marcus Sampaio
Pós-Graduação em Informática da UFCGhttp://www.dsc.ufcg.edu.br/~sampaio/cursos/2006.2/PosGraduacao/MineracaoDeDados/
Marcus SampaioDSC/UFCG
Marcus SampaioDSC/UFCGSumá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 SampaioDSC/UFCGContexto
• 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
Marcus SampaioDSC/UFCGMineração de Dados
• 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 semi-aberta– Consultas tradicionais são fechadas, ou completamente
definidas
Marcus SampaioDSC/UFCGMineração de Dados (2)
• 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
Marcus SampaioDSC/UFCGExemplo de Motivação
• 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 SampaioDSC/UFCG
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
Exemplo de Motivação (2)
Marcus SampaioDSC/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
Exemplo de Motivação (3)
Marcus SampaioDSC/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
Exemplo de Motivação (4)
Marcus SampaioDSC/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
Exemplo de Motivação (5)
Marcus SampaioDSC/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 (6)
Marcus SampaioDSC/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 (7)
Marcus SampaioDSC/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
Exemplo de Motivação (8)
Marcus SampaioDSC/UFCGModelos e Padrões
• 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
Marcus SampaioDSC/UFCGModelos ... (2)
• 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 SampaioDSC/UFCGModelos ... (3)
Modelo
Preditivo Descritivo
Classificação
Regressão
SérieTemporal
Clustering Síntese
Regras de AssociaçãoDescoberta de
Seqüências
Marcus SampaioDSC/UFCG
Algoritmos de Mineração de Dados
• 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
Marcus SampaioDSC/UFCGAlgoritmos ... (2)
• 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?
Marcus SampaioDSC/UFCGAlgoritmos ... (3)
– 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!
Marcus SampaioDSC/UFCGAlgoritmos ... (4)
• 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 SampaioDSC/UFCGAlgoritmos ... (5)
Aplicação noTempo
Rendimento
x
x
x
x
xx
x
x
xx x
x
Marcus SampaioDSC/UFCGAlgoritmos ... (6)
• 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
Marcus SampaioDSC/UFCGAlgoritmos ... (7)
Tempo
Nível deEstoque
Produto A
Produto B
Produto C
• 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
Marcus SampaioDSC/UFCGAlgoritmos ... (8)
• Algoritmos de “Clustering”– “Clustering” é similar a classificação, exceto que os grupos
(“clusters”) não são pré-definidos – classificação não-supervisionada
• 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
Marcus SampaioDSC/UFCGAlgoritmos ... (9)
• 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
Marcus SampaioDSC/UFCGAlgoritmos ... (10)
• 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
Marcus SampaioDSC/UFCGAlgoritmos ... (11)
• 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
Marcus SampaioDSC/UFCGAlgoritmos ... (12)
• 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)
Marcus SampaioDSC/UFCGAlgoritmos ... (13)
• 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
Marcus SampaioDSC/UFCGAlgoritmos ... (14)
• 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
Marcus SampaioDSC/UFCGAlgoritmos ... (15)
• 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
Marcus SampaioDSC/UFCG
Métricas de Mineração de Dados
• 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
Marcus SampaioDSC/UFCGMétricas ... (2)
• 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
Marcus SampaioDSC/UFCGQuestões em Aberto
• 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
Marcus SampaioDSC/UFCGQuestões em Aberto (2)
• 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
Marcus SampaioDSC/UFCGQuestões em Aberto (3)
• 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
Marcus SampaioDSC/UFCGSistema de Avaliação
• 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)
Recommended