INE5644 – Data Mining
Tarefas de DCBD
Prof. Luis Otavio [email protected]
Apresentação adaptada do material do livro
Introduction to Data Mining – Tan, Steinbach e Kumar
e de slides do prof. José Leomar Todesco (UFSC)
Enormes quantidades de dados
são coletadas e armazenadas
– Dados da Web, e-commerce
– Compras em supermercados,
lojas de departamentos, etc.
– Transações bancárias e de
cartões de crédito
Os computadores se tornaram baratos e mais poderosos
A pressão competitiva é muito forte
Porque DCBD? Ponto de vista comercial
prof. Luis Otavio Alvares
Porque DCBD? Ponto de vista científico
Dados captados e armazenados em grande velocidade (GB/hora)
– sensores remotos em satélites
– telescópios varrendo o firmamento
– microarrays gerando dados de expressão gênica
– simulações científicas gerando terabytes
de dados
Técnicas tradicionais de anáilise são
inviáveis para estes dados brutos
prof. Luis Otavio Alvares
Motivação para minerar grandes bases de dados
Freqüentemente há informação “escondida” nos dados, que não é evidente
Analistas humanos podem levar semanas para descobrir informação útil
Muitos dados nunca são analisados
0
500.000
1.000.000
1.500.000
2.000.000
2.500.000
3.000.000
3.500.000
4.000.000
1995 1996 1997 1998 1999
The Data Gap
Total new disk (TB) since 1995
Number of analysts
From: R. Grossman, C. Kamath, V. Kumar, “Data Mining for Scientific and Engineering Applications”, Kluwer, 2001
O que é DCBD?
Muitas definições– Extração não-trivial de informação implícita,
previamente desconhecida e potencialmente útil de um conjunto de dados
– Exploração e análise, de modo automático ou semi-automático, de grandes quantidades de dados para descobrir padrões úteis
prof. Luis Otavio Alvares
O que (não) é DCBD?
O que é DCBD:
– descobrir que certos nomes são mais comuns em alguns lugares (O’Brien, O’Rurke, O’Reilly… na área de Boston)
– Agrupar documentos similares recuperados por um motor de busca de acordo com o seu contexto (ex: Amazon rainforest, Amazon.com,)
O que não é:
– buscar um nome e número de telefone em um arquivo de clientes
– Consultar um motor de busca na web sobre “Amazon”
prof. Luis Otavio Alvares
Exemplo: um proprietário de uma pequena loja de vinhos conhece tudo sobre vinhos, por exemplo, o tipo de uva, a região onde a uva foi cultivada, o clima, o solo, a altitude dos parreirais, aroma, sabor, cor, o processo de fabricação. Os clientes gostam de visitar sua loja pois, também, aprendem muito sobre vinhos. Porém, só isto não basta, o proprietário precisa conhecê-los, como por exemplo, qual o tipo de vinho que o cliente gosta? Qual o poder aquisitivo? Assim, ele poderá dar um atendimento diferenciado (um a um) aos clientes. Temos, portanto, duas necessidades:
conhecimento e aprendizado
Uma pequena loja poucos clientes atendimento personalizado
Uma grande empresa milhares de clientes dificuldade em dar um atendimento dedicado
Observando e Aprendendo
prof. Luis Otavio Alvares
Qual a tendência nos dias atuais?
Ter clientes leais, através de um relacionamento pessoal, um-para-
um, entre a empresa e o cliente.
Dentro desta tendência, as empresas desejam identificar os
clientes cujos valores e necessidades sejam compatíveis com o
uso prolongado de seus produtos, e nos quais é válido o risco de
investir em promoções com descontos, pacotes, brindes e outras
formas de criar essa relação pessoal.
Esta mudança de foco requer mudanças em toda a empresa, mas
principalmente nos setores de marketing, vendas e atendimento ao
cliente.
Observando e Aprendendo
prof. Luis Otavio Alvares
Memória e Inteligência
Na pequena empresa, o proprietário com sua inteligência e memória aprende, conhece o cliente.
prof. Luis Otavio Alvares
Para criar relações um-para-um em uma grande empresa, o proprietário humano
precisa ser substituído por uma máquina capaz de tratar grandes números, o
computador. A memória do proprietário é substituída por um grande banco de dados
denominado de Data Warehouse, enquanto a capacidade de aprendizado é
substituída por técnicas de inteligência artificial e estatística genericamente
denominadas de Data Mining.
Diariamente gera-se dados, por exemplo, considere que gera-se e armazena-se
atributos tais como: o número do telefone, a duração da chamada telefônica, o
número do cartão de crédito, o endereço da entrega, o produto escolhido, renda do
consumidor, escolaridade do consumidor, gasto com lazer, etc.
Certamente, só armazenar dados não significa aprender sobre o cliente.
Data Warehouse: a memória da empresa
prof. Luis Otavio Alvares
Dados armazenados
Fonte de informaçõespreciosas para a empresa
Memória da empresa
prof. Luis Otavio Alvares
Para o aprendizado ocorrer, uma série de informações de diferentes
formatos e fontes precisa ser organizada de maneira consistente na
grande memória empresarial. Após isto, métodos de análise
estatística e inteligência artificial precisam ser aplicados sobre esses
dados e relações novas e úteis à empresa devem ser descobertas, ou
seja, os dados devem ser minerados. A mineração dos dados
consiste mais especificamente em descobrir relações entre produtos,
classificar consumidores, prever vendas, localizar áreas geográficas
potencialmente lucrativas para novas filiais, inferir necessidades,
entre outras.
Data Mining: a inteligência da empresa
prof. Luis Otavio Alvares
Data Warehouse
Data Mining
Na grande empresa, a memória é o
data warehouse, enquanto a
inteligência é o data mining
Na grande empresa, a memória é o
data warehouse, enquanto a
inteligência é o data mining
prof. Luis Otavio Alvares
Data Mining and BI
Aumento do potencialPara suportar decisões do negócio Diretor
Analistade negócios
Analistade dados
DBA
MakingDecisions
Data Presentation
Visualization Techniques
Data Mining
Knowledge Discovery
Data Exploration
OLAP, MDA
Statistical Analysis, Querying and Reporting
Data Warehouses / Data Marts
Data SourcesPapel, Arquivos, Provedores de informação, Database Systems, OLTP
prof. Luis Otavio Alvares
prof. Luis Otavio Alvares
Tipos de descobertas (tarefas de DCBD)
Os dois principais objetivos de alto nível da DCBD são a descrição e a predição
a descrição se concentra em encontrar padrões que descrevem os dados de forma compreensível para o usuário
a predição envolve usar valores conhecidos de campos ou variáveis para predizer o valor desconhecido ou futuro de variáveis de interesse
para isso, utiliza-se vários tipos de descoberta ou tarefas de DCBD
Principais Tarefas de DCBD ...
Classificação [Preditiva]
Clustering [Descritiva]
Descoberta de regras de associação [Descritiva]
Descoberta de padrões seqüenciais [Descritiva]
Regressão [Preditiva]
Detecção de desvios [Preditiva]
prof. Luis Otavio Alvares
Classificação
prof. Luis Otavio Alvares
Classificação: exemplos
O professor classifica o desempenho do aluno em A, B, C, D ou E
Identificar um cogumelo como sendo venenoso ou não
Reconhecimento de caracteres
Classificação: definição
Dada uma coleção de registros (conjunto de treinamento)– Cada registro contém um
conjunto de atributos, e um dos atributos é a classe.
Encontre um modelo para o atributo classe como uma função dos valores dos outros atributos
Objetivo: definir a classe para novos registros tão acuradamente quanto possível.
prof. Luis Otavio Alvares
Id
Casa própria
EstCivil
Rendim.
Mau Pagador
1 S Solteiro 125K NÃO
2 N Casado 100K NÃO
3 N Solteiro 70K NÃO
4 S Casado 120K NÃO
5 N Divorc. 95K SIM
6 N Casado 60K NÃO
7 S Divorc. 220K NÃO
8 N Solteiro 85K SIM 10
Model
Casa própria
EstCivil
Rendim.
Mau Pagador
N Solteiro 75K ?
S Casado 50K ?
N Casado 150K ?
S Divorciado 90K ? 10
Classificação: Aplicação 1
Marketing direto
– Objetivo: Reduzir o custo na oferta para um conjunto alvo de consumidores mais prováveis de comprar um novo produto.
– Abordagem: Usar os dados de um produto similar oferecido anteriormente.
Sabemos quais consumidores compraram e quais não compraram. Esta decisão {compra, não compra} forma o atributo classe.
Coletar várias informações pessoais, de estilo de vida e de interações com a empresa de todos estes clientes.
– Tipo de atividade, local da moradia, rendimentos, estado civil, compras anteriores, etc.
Usar esta informação como atributos de entrada para gerar um modelo de classificação.
From [Berry & Linoff] Data Mining Techniques, 1997
prof. Luis Otavio Alvares
Classificação: Aplicação 2
Detecção de fraudes– Objetivo: identificar casos de fraude em transações com
cartão de crédito.– Abordagem:
Usar as transações do cartão de crédito e as informações do proprietário como atributos.
– Quando um consumidor compra, o que ele compra, onde ele compra, compra a vista ou a prazo, valor da compra, etc
Rotular as transações passadas como fraude ou não. Isto forma o atributo classe.
Gerar um modelo de classificação para as transações. Usar este modelo para detectar fraudes observando as novas
transações .
prof. Luis Otavio Alvares
Classificação: Aplicação 3
Conservação de clientes:– Objetivo: prever se é provável que um cliente de uma
empresa de telefone celular passe para um concorrente.
– Abordagem: Usar um registro detalhado das transações de cada cliente
antigo e atual para obter os atributos.– Com que freqüência o cliente faz ligações, para quem ele liga, a
que horas ele liga mais freqüentemente, sua renda, estado civil, desde quando é cliente, etc.
Rotular os clientes como fiéis ou infiéis a empresa. Gerar um modelo.
From [Berry & Linoff] Data Mining Techniques, 1997
prof. Luis Otavio Alvares
Classificação: Aplicação 4
Análise de objetos celestes
– Objetivo: predizer a classe (estrela ou galáxia) de objetos celestes, especialmente de pouco brilho, baseado em imagens do telescópio do Monte Palomar
– 3000 imagens com 23.040 x 23.040 pixels por imagem.
– Abordagem: Segmentar a imagem. Medir os atributos da imagem (40 por objeto) Gerar um modelo baseado nestes atributos. Resultado: foram descobertos 16 novos quasars, alguns dos
mais distantes objetos já identificados!
From [Fayyad, et.al.] Advances in Knowledge Discovery and Data Mining, 1996
prof. Luis Otavio Alvares
Classificando Galáxias
Early
Intermediate
Late
dados: • 72 milhões de estrelas, 20 milhões de galáxias• Object Catalog: 9 GB• Image Database: 150 GB
Classe: • Estágio da
formação
Atributos:• Image features, • Characteristics of
light waves received, etc.
Courtesy: http://aps.umn.edu
prof. Luis Otavio Alvares
Clustering (formação de agrupamentos)
Clustering (formação de agrupamentos)
Dado um conjunto de dados, cada um com um conjunto de atributos, e uma medida de similaridade entre eles, encontre clusters (grupos) tais que:– Dados de um grupo são mais similares entre si que
com dados de outros grupos– Dados de grupos diferentes são menos similares entre
si.
Medidas de similaridade:– Distância Euclidiana, para atributos contínuos– Outras medidas específicas do problema.
prof. Luis Otavio Alvares
Clustering: exemplo
Clustering em espaço 3-D baseado em distância euclidiana.
Distâncias intraclustersão minimizadas
Distâncias intraclustersão minimizadas
Distâncias interclustersão maximizadas
Distâncias interclustersão maximizadas
prof. Luis Otavio Alvares
Clustering: Aplicação 1
Segmentação de mercado:
– Objetivo: subdividir um mercado em diferentes subconjuntos de clientes onde cada subconjunto possa ser selecionado como objetivo específico de marketing a ser alcançado.
– Abordagem:
Obter diferentes atributos de clientes baseado em informações cadatrais e de estilo de vida dos clientes
Encontrar grupos (clusters) de clientes similares.
Medir a qualidade dos clusters observando padrões de compra entre clientes do mesmo cluster versus entre clientes de outros clusters
prof. Luis Otavio Alvares
Clustering: Aplicação 2
Clustering de documentos:– Objetivo: encontrar grupos de documentos que são
similares entre si baseado em termos importantes que aparecem nos documentos.
– Abordagem: identificar termos que ocorrem freqüentemente em cada documento. Criar uma medida de similaridade baseada na freqüência dos diferentes termos. Usar esta medida para a formação dos grupos.
– Ganho: os clusters podem ser usados em Recuperação de Informações para relacionar um novo documento ou termo de pesquisa a clusters de documentos.
prof. Luis Otavio Alvares
Clustering de ações da bolsa
Discovered Clusters Industry Group
1Applied-Matl-DOW N,Bay-Network-Down,3-COM-DOWN,
Cabletron-Sys-DOWN,CISCO-DOWN,HP-DOWN,DSC-Comm-DOW N,INTEL-DOWN,LSI-Logic-DOWN,
Micron-Tech-DOWN,Texas-Inst-Down,Tellabs-Inc-Down,Natl-Semiconduct-DOWN,Oracl-DOWN,SGI-DOW N,
Sun-DOW N
Technology1-DOWN
2Apple-Comp-DOW N,Autodesk-DOWN,DEC-DOWN,
ADV-Micro-Device-DOWN,Andrew-Corp-DOWN,Computer-Assoc-DOWN,Circuit-City-DOWN,
Compaq-DOWN, EMC-Corp-DOWN, Gen-Inst-DOWN,Motorola-DOW N,Microsoft-DOWN,Scientific-Atl-DOWN
Technology2-DOWN
3Fannie-Mae-DOWN,Fed-Home-Loan-DOW N,MBNA-Corp-DOWN,Morgan-Stanley-DOWN Financial-DOWN
4Baker-Hughes-UP,Dresser-Inds-UP,Halliburton-HLD-UP,
Louisiana-Land-UP,Phillips-Petro-UP,Unocal-UP,Schlumberger-UP
Oil-UP
Observe os movimentos das ações a cada dia.
Dados: ação-{UP/DOWN}
Medida de similaridade: Duas ações são similares se os eventos descritos por elas freqüentemente acontecem juntos no mesmo dia.
prof. Luis Otavio Alvares
Associação
prof. Luis Otavio Alvares
Dependência (associação) entre atributos
Exemplos: – determinados procedimentos médicos aparecem
sempre juntos
– determinados procedimento médicos aparecem mais associados a homens e outros a mulheres
– compradores de leite geralmente compram pão na mesma transação
prof. Luis Otavio Alvares
Exemplo: vendas casadas
PRODUTO APRODUTO A
PRODUTO APRODUTO A
PRODUTO BPRODUTO B
Oferta deproduto relacionado
Compra deproduto
Sei que quem compra o produto A também compra o B.
prof. Luis Otavio Alvares
Regras de associação: Definição
Dado um conjunto de registros, cada um com um conjunto de itens de uma certa coleção;
– Produza regras de dependência que vão predizer a ocorrência de um item baseado na ocorrência de outros.
TID Items
1 guaraná, leite, pão
2 cerveja, pão
3 cerveja, fralda, guaraná, leite
4 cerveja, fralda, leite, pão
5 fralda, guaraná, leite
Regras descobertas: {leite} --> {guaraná} {fralda, leite} --> {cerveja}
Regras descobertas: {leite} --> {guaraná} {fralda, leite} --> {cerveja}
prof. Luis Otavio Alvares
Regras de associação: Aplicação 1
Gerenciamento de prateleiras de supermercado.
– Objetivo: identificar itens que são comprados juntos por um grande número de clientes.
– Abordagem: processar os dados das transações de compra obtidos com os códigos de barras para encontrar dependências entre itens.
– Uma regra clássica-- Se um cliente compra fralda e leite ele tem uma boa
probabilidade de comprar também cerveja. Portanto, não fique surpreso de encontrar pacotes de cerveja
próximo das fraldas!
prof. Luis Otavio Alvares
Regras de associação: Aplicação 2
Gerência de inventário:
– Objetivo: uma empresa de consertos de eletrodomésticos quer antecipar a natureza dos consertos nos aparelhos dos seus clientes de forma a ter em seus veículos de serviço peças de reposição, de modo a poder realizar o conserto na hora, sem precisar voltar à casa dos clientes
– Abordagem: Analisar os dados de consertos anteriores em termos de ferramentas e peças necessárias para descobrir padrões de co-ocorrência.
prof. Luis Otavio Alvares
Padrões sequenciais
Padrões sequenciais
Definição:Dado um conjunto de objetos, com cada objeto associado com a sua
linha de eventos, encontre regras com forte dependência seqüencial entre diferentes eventos.
(A B) (C) (D E)
prof. Luis Otavio Alvares
Detecção de dependências temporais entre eventos.
Exemplos: determinado procedimento médico sempre precede outroturistas que visitam o museu do Louvre depois visitam a Notre Dame
Padrões seqüenciais: exemplos
Em transações de vendas
– Livraria de informática:
(Intro_To_Visual_C) (C++_Primer) (Perl_for_dummies,Tcl_Tk)
– Loja de artigos esportivos:
(tenis) (raquete, bolas) (moleton)
prof. Luis Otavio Alvares
Regressão
Regressão
Prediz o valor de uma variável contínua baseado no valor de outras variáveis, considerando um modelo de dependência linear ou não linear.
Bastante estudado em estatística e redes neurais Exemplos:
– Previsão da quantidade de vendas de um novo produto baseado nos gastos com propaganda
– Previsão da velocidade do vento em função da temperatura, humidade, pressão atmosférica, etc.
– Previsão da evolução do índice de bolsa de valores.
prof. Luis Otavio Alvares
Detecção de desvios
Detecção de desvios
Determinar desvios significativos do comportamento normal
Aplicações:– Detecção de fraudes em
cartões de crédito
– Detecção de
invasão em redes
de computadores
– Detecção de eventos
através de mensagens
do Twitter
Typical network traffic at University level may reach over 100 million connections per day
prof. Luis Otavio Alvares
prof. Luis Otavio Alvares
exemplo: sistema de mortalidade
Doenças “P” – Algumas afecções originadas no período perinatal:
– Uruguaiana apresenta um desvio significativo em relação a esta classe de doenças, pois foram registrados muito mais casos de morte do que o esperado.
– Porto Alegre registrou menos mortes do que a quantidade esperada, para esta classe de doenças.
Caxias do Sul apresenta um desvio em relação às doenças “Q- malformação congênita, deformidades e anomalias cromossômicas”. Foi registrado um número de mortes significativamente maior do que o esperado para a cidade.
Principais Tarefas de DCBD ...
Classificação [Preditiva]
Clustering [Descritiva]
Descoberta de regras de associação [Descritiva]
Descoberta de padrões seqüenciais [Descritiva]
Regressão [Preditiva]
Detecção de desvios [Preditiva]
Exercício
Especifique a tarefa de DCBD em cada um dos casos abaixo:
1 agrupar proteínas com funcionalidades similares
2 predizer a quantidade de vendas de um novo produto baseado nos gastos com propaganda
3 prever se é provável que um cliente de uma empresa de telefone celular passe para um concorrente
4 identificar itens que são comprados juntos por um grande número de clientes
Desafios para Data Mining
Escalabilidade Dimensionalidade Dados complexos e heterogêneos Qualidade dos dados Propriedade e distribuição dos dados Preservação da privacidade Dados em fluxo contínuo
Próxima aula
O processo de KDD