Introdução à Descoberta de
Conhecimento e Mineração de
Dados
Professor Celso A A Kaestner, Dr. Eng.
1
Site:
http://www.dainf.ct.utfpr.edu.br/~kaestner/ls-dm.htm
2
Introdução
3
Introdução: por que Data Mining ?
• O problema da explosão da quantidade de dados
(data explosion):
– Ferramentas de armazenamento automático e a
maturidade da tecnologia de banco de dados,
bem como o advento da Internet, levaram à
criação de imensas massas de dados em data
bases, data warehouses e em outros repositórios.
4
Introdução: por que Data Mining ?
•
•
•
•
•
•
1 byte = 8 bits;
1 Kbyte = 1.024 bytes;
1 Mbyte ~= 1.000.000 bytes;
1 Gbyte ~= 1.000.000.000 bytes;
1 Terabyte ~= 1.000.000.000.000= 1012 bytes
1 EB = 1 exabyte ~= 1.000.000 Tbytes
• Qual o tamanho das bases de dados ?
• Qual o tamanho da internet ?
5
Introdução: por que Data Mining ?
Fonte: Curso de Piatetsky-Shapiro
6
Introdução: por que Data Mining ?
• Tamanho da Internet (2003, em Terabytes):
Surface Web
Deep Web
167
91.850
Email (originals)
Instant messaging
TOTAL
440.606
274
532.897
Fonte: How Much Information 2003
7
Introdução: por que Data Mining ?
• Tamanho da Internet indexada (2005): 11,5
bilhões de páginas;
• Ver:
1. http://www.cs.uiowa.edu/~asignori/websize/size-indexable-web.pdf
2. http://www.worldwidewebsize.com/
8
Introdução: por que Data Mining ?
– Estamos nos
afogando em
dados, mas
sedentos por
informação!
9
Introdução: por que Data Mining ?
• A solução: data warehousing e data mining:
– Data warehousing e on-line analytical processing
(OLAP);
– Extração de conhecimentos interessantes (regras,
regularidades, padrões, restrições) a partir das
grandes bases de dados.
10
Introdução: evolução da tecnologia
dos BD
• 1960s: Coleta de dados, criação de bancos de
dados, IMS e DBMS em rede;
• 1970s: Modelo de dados relacional, implementação
de DBMS relacionais;
• 1980s: RDBMS, modelos de dados avançados
(relacional estendido, OO, dedutivo, etc.) e DBMS
orientados à aplicação (espaciais, científicos, para
engenharia, etc.)
• 1990s—2000s: Data mining and data warehousing,
DBMS multimídia e Web DB.
11
Introdução: o que é data mining ?
•
Data mining (descoberta de conhecimento
em BD):
– Extração de padrões de informação de
interesse:
1. não-trivial,
2. implícita,
3. previamente desconhecida e
4. potencialmente útil,
de grandes DBs.
12
Introdução: o que é data mining ?
Dilbert explica ...
13
Introdução: o que é data mining ?
• Conceitos relacionados:
– Descoberta de conhecimento em BD (KDD),
extração de conhecimento, análise de padrões em
dados, information harvesting, business
intelligence, etc.
• O que não é data mining?
– Processamento dedutivo de consultas;
– Sistemas especialistas e pequenos programas
estatísticos e de aprendizagem de máquina.
14
Introdução: o que é data mining ?
Gartner Group:
• “Data mining is the process of discovering
meaningful new correlations, patterns and
trends by sifting through large amounts of
data stored in repositories, using pattern
recognition technologies as well as statistical
and mathematical techniques.”
15
Introdução: potenciais aplicações
• Análise de DB e suporte à decisão:
– Análise e gerenciamento de mercado:
• Marketing dirigido, gerenciamento de relações
com consumidores, análise de mercado,
vendas cruzadas, segmentação de mercado;
– Análise e gerenciamento de risco:
• Previsões, retenção de clientes, controle de
qualidade, análise de competitividade;
– Análise e gerenciamento de fraudes.
16
Introdução: potenciais aplicações
• Outras aplicações:
– Mineração de textos (documentos, emails, news)
e Web mining.
– Resposta inteligente a consultas.
17
Análise e gerenciamento de mercado
• Onde estão as fontes de dados para análise ?
– Transações com cartões de crédito, cartões de
fidelidade, cupons de desconto, requisições de
clientes e estudos sobre o estilo de vida dos
clientes.
• Marketing dirigido:
– Encontra grupos de clientes “modelo” que
compartilham as mesma características:
interesses, salário, hábitos de consumo, etc.
18
Análise e gerenciamento de mercado
• Determinação de padrões de compra ao longo do
tempo:
– Conversão de conta simples para conjunta,
casamento, etc.
• Análise de vendas cruzadas:
– Associações e correlações entre vendas de
produtos;
– Predição baseada na informação de associações.
19
Análise e gerenciamento de mercado
• Perfil do consumidor:
– data mining pode informar que tipos de
consumidores compram quais produtos
(agrupamento ou classificação);
• Identificação dos requisitos dos clientes:
– Identificação dos melhores produtos para os
diferentes clientes;
– Uso de predição para encontrar quais fatores
atrairão os consumidores;
20
Análise e gerenciamento de mercado
• Fornecimento de informação sumarizada:
– Relatórios multidimensionais sumarizados;
– Informações estatísticas sumarizadas (tendência
central e variação dos dados)
21
Análise corporativa e
gerenciamento de risco
• Planejamento financeiro e avaliação de crédito:
– Análise e previsão de fluxo de caixa;
– Análise contingente para avaliação de crédito;
– Análise seccional e temporal (razão financeira,
análise de tendência, etc.)
• Planejamento de recursos:
– Sumarização e comparação de recursos e gastos;
• Competição:
– Monitoramento de competidores e mercado;
– Agrupamento de clientes em classes e
procedimentos de preços baseados em classes;
– Estratégias para fixação de preços em mercado
competitivo.
22
Detecção e gerenciamento de
fraudes
• Aplicações:
– Amplamente utilizado em serviços de cartões de
crédito, telefonia celular, convênios de saúde, etc.
• Abordagem:
– Uso de dados históricos para construir modelos
do comportamento fraudulento e uso de data
mining para identificar instâncias similares;
23
Detecção e gerenciamento de
fraudes
• Exemplos:
– Seguros de automóveis: detectar um grupo de
pessoas que forjam acidentes para ganhar o
seguro;
– Lavagem de dinheiro: detecção de transações
suspeitas de dinheiro (US Treasury's Financial
Crimes Enforcement Network)
– Seguros médicos: detecção de
pacientes”profissionais” e grupos de doutores
coniventes.
24
Detecção e gerenciamento
de fraudes
• Detecção de tratamento médico inapropriado:
– A Australian Health Insurance Commission
identificou que em muitos casos exames
desnecessários eram solicitados (economia de
AD$1milhão /ano).
• Detecção de fraudes telefônicas:
– Modelo de chamadas telefônicas: destino da
chamada, duração, horário e dia da semana;
análise de padrões para detectar desvios;
– A British Telecom identificou grupos de clientes
com chamadas freqüentes dentro do grupo,
especialmente em telefones celulares, e detectou
uma fraude milionária.
25
Detecção e gerenciamento
de fraudes
• Venda a varejo:
– Analistas estimam que 38% das perdas no varejo
são devidas a empregados desonestos.
26
Outras aplicações
• Esportes:
– IBM Advanced Scout analisou as estatísticas dos
jogos da NBA (cestas, bloqueios, assistências,
faltas, etc) para auxiliar os times do New York
Knicks e do Miami Heat;
• Astronomia:
– JPL e o Observatório do Monte Palomar
descobriram 22 quasars com o auxílio de data
mining;
27
Outras aplicações
• Ajuda ao uso da Internet, comércio eletrônico:
– IBM Surf-Aid aplica algoritmos de data mining a
logs de acessos Web à páginas de vendas, de
forma a descobrir preferências e comportamentos
dos clientes e efetuar análise da efetividade do
Web marketing, melhorar a organização do site
Web, etc.
– (ex-) Blue Martini Company...
– Amazon, Google...
28
A Web como fonte de aplicações
• Num site de comércio eletrônico, serve canal
de negócios e laboratório;
• Limitado como canal de compra (valor do
bem, segurança, privacidade ...);
• Como laboratório serve para testar
campanhas, novos produtos, avaliar clientes,
etc.
29
A Web como fonte de aplicações
• A amostra de clientes de tendenciosa;
• O comportamento na internet não é o mesmo
do presencial;
• O custo de um site é elevado;
• Muitos robôs de busca ...
(fonte: palestra de Ron Kohavi)
30
Análise da Web
(fonte: palestra de Ron Kohavi)
• Tráfego na Web (10/46) por dia do mês;
• Por dia da semana (11/46);
• Exemplo por ponto de venda (POS) (12/46);
• Por hora (13/46);
• Um exemplo espúreo (14/46);
• Campanhas por emails (20/46);
• Estudos demográficos (25/46);
• Robôs de busca (28/46);
31
Análise da Web
(fonte: palestra de Ron Kohavi)
• Estatística por visita (29/46);
• Privacidade (32/46);
• Exemplos de melhorias (41/46).
32
KDD e DM
33
Data Mining e Business Intelligence
Increasing potential
to support
business decisions
Making
Decisions
Data Presentation
Visualization Techniques
Data Mining
Information Discovery
End User
Business
Analyst
Data
Analyst
Data Exploration
Statistical Analysis, Querying and Reporting
Data Warehouses / Data Marts
OLAP, MDA
Data Sources
Paper, Files, Information Providers, Database Systems, OLTP
DBA
34
KDD e Data Mining
Data mining é o coração
do processo KDD
Pattern Evaluation
Data Mining
Task-relevant Data
Data Warehouse
Selection
Data Cleaning
Data Integration
Databases
35
KDD e Data Mining
Data PreProcessing
Integração de Dados
Normalização
Seleção de atributos
Redução de
dimensionalidade
Data
Mining
Descoberta de padrões
Associação & correlação
Classificação
Agrupamento
Análise de desvios
PostProcessing
Avaliação,
Seleção,
Interpretação e
Visualização de padrões
Visão simplificada do processo de KDD
36
Passos do processo de KDD
• Estudo sobre o domínio de aplicação:
– Conhecimento relevante a priori e metas da
aplicação;
• Criação de um dataset alvo:
– Seleção de dados;
• Limpeza e pré-processamento dos dados:
– Pode corresponder a 60 % do esforço;
• Redução e transformação dos dados:
– Encontrar atributos relevantes, redução de
dimensionalidade, representação de invariantes;
37
Passos do processo de KDD
• Escolha da função de data mining:
– Sumarização, classificação, regressão,
associação, regressão, agrupamento...
• Escolha do algoritmo de mineração:
– Busca aos padrões de interesse;
• Avaliação dos padrões e apresentação do
conhecimento:
– Visualização, transformação, remoção de
redundâncias, etc.
• Uso do conhecimento descoberto.
38
Arquitetura de um sistema de DM típico
Graphical user interface
Pattern evaluation
Data mining engine
Knowledge-base
Database or data
warehouse server
Data cleaning & data integration
Databases
Filtering
Data
Warehouse
39
Alguns conceitos fundamentais
• Instância (item ou registro):
– Um exemplo, descrito por certo número de
atributos: um dia descrito por temperatura,
umidade e situação das nuvens;
• Atributo (característica ou campo):
– Medida de aspectos de uma instância,
como o valor da temperatura;
• Classe (Rótulo):
– Agrupamento de instâncias, e.g. dias bons
para jogar tênis
40
Alguns conceitos fundamentais
• Base de treinamento:
– Conjunto de exemplos utilizado para a
geração do procedimento / estrutura que
servirá para a aplicação em outros casos;
• Base de testes:
– Conjunto de exemplos que será utilizado
para verificar a “eficiência” do
procedimento de DM gerado.
41
Alguns conceitos fundamentais
• Desafio principal:
Encontrar padrões verdadeiros
nos dados
e evitar o “overfitting”
(padrões que parecem significantes mas são
aleatórios ou que só funcionam para o
conjunto de treinamento dado)
42
DM: em que dados?
•
•
•
•
•
•
•
•
•
•
DB relacionais:
Data warehouses;
DB tradicionais;
DB de transações;
DB avançados e repositórios de informação;
DB Orientados a Objeto e DB Objeto-Relacionais;
DB espaciais;
Séries temporais e dados temporais;
DB legados e heterogêneos;
A Web ...
43
DM: funcionalidades
• Associação (correlação e causalidade)
– Associação multi-dimensional x unidimensional;
– idade(X,“20..29”)^
ganhos(X,“20..29K”) =>
compra (X, “PC”)
[suporte = 2%, confiança = 60%]
44
DM: regras de associação
Transações
TID Produce
1
MILK, BREAD, EGGS
2
BREAD, SUGAR
3
BREAD, CEREAL
4
MILK, BREAD, SUGAR
5
MILK, CEREAL
6
BREAD, CEREAL
7
MILK, CEREAL
8
MILK, BREAD, CEREAL, EGGS
9
MILK, BREAD, CEREAL
Conjuntos de itens
frequentes
Milk, Bread (4)
Bread, Cereal (3)
Milk, Bread, Cereal (2)
…
Regras:
Milk => Bread (66%)
45
DM: funcionalidades
• Descrição de conceitos: caracterização
e discriminação:
– Dados podem ser associados em classes;
– A caracterização de uma classe ou sua
discriminação em relação a outras classes
é potencialmente útil;
– Generalização, sumarização, contraste
das características dos dados são os
objetivos.
46
DM: funcionalidades
• Classificação e predição:
– Encontrar modelos (funções) que descrevem e
distinguem classes ou conceitos para futura
predição;
– Ex: classificar países conforme o clima ou carros
conforme o consumo;
– Apresentação: árvore de decisão, regra de
classificação, rede neural;
– Predição: de valor numérico desconhecido ou
perdido;
47
DM: classificação
• Principais abordagens:
Estatísticas, Árvores de
decisão, redes neurais…
48
DM: funcionalidades
• Agrupamento (clustering):
– O rótulo (nome) da classe é desconhecido: devese agrupar os dados para formar classes;
– Ex: agrupamento de casas para encontrar
padrões de distribuição;
– O agrupamento é baseado na maximização da
similaridade intra-classe e minimização da
similaridade inter-classes.
49
DM: agrupamento
Encontrar agrupamentos“naturais” das
instâncias em dados não-rotulados
50
DM: funcionalidades
• Análise de desvios (outlier analysis):
– Desvio (outlier): objeto que não está em
conformidade com o comportamento geral
dos dados;
– Pode ser considerado como ruído ou
exceção mas é útil no caso da detecção de
fraudes, análise de eventos raros, etc.
51
DM: detecção de “outliers”
Encontrar instâncias
“inesperadas”
52
DM: funcionalidades
• Sumarização;
• Visualização;
• Análise de tendências e evolução:
– Tendência e desvio: análise de regressão
– DM seqüencial, análise de periodicidade;
– Análise baseada em similaridade;
• Outras análises estatísticas e de
reconhecimento de padrões.
53
DM: sumarização
n Descrição de
características de um
grupo;
n Usa de linguagem
natural e gráfica;
n Usualmente em
combinação com a
deteção de desvios ou
outros métodos.
54
DM: visualização
Visualizar
adequadamente
conjuntos de
dados,
facilitando a
análise
55
Todos os padrões descobertos são
interessantes ?
• Um sistema de DM pode gerar milhares de padrões,
nem todos interessantes;
– Abordagem sugerida: centrada no usuário, baseada em
consultas, dirigindo a mineração;
• Medidas do grau de interesse:
– Um padrão é interessante se for facilmente compreendido,
válido no conjunto de dados novo / de teste com certo grau
de certeza, potencialmente útil e anteriormente
desconhecido, ou validando alguma hipótese que se deseja
confirmar;
56
Todos os padrões descobertos são
interessantes ?
• Medidas de interesse objetivas e subjetivas:
– Objetivas: baseadas em estatísticas e na estrutura
doa padrões, e.g., suporte, confiança;
– Subjetivas: baseadas na crença do usuário nos
dados, e.g., novidade, não-expectativa, etc.
57
Todos os padrões interessantes são
encontrados ?
• Completude: encontrar todos os padrões
interessantes:
– O sistema pode encontrar todos os padrões interessantes ?
– Associação x classificação x agrupamento.
• Otimização: busca apenas dos padrões
interessantes:
– O sistema pode encontrar somente padrões interessantes ?
– Abordagens:
• Encontrar todos os padrões e descartar (filtrar) os não
interessantes;
• Gerar apenas padrões interessantes: otimização de
consultas de mineração.
58
DM: um campo multidisciplinar
Database
Technology
Machine
Learning
Information
Science
Statistics
Data Mining
Visualization
Other
Disciplines
59
DM: esquemas de classificação
• Funcionalidade geral:
– DM descritivo;
– DM preditivo.
• Visões diferentes, classificações diferentes:
– Tipos de DB a serem minerados;
– Tipos de conhecimentos a serem descobertos;
– Técnicas a serem utilizadas;
– Tipos de aplicações alvo.
60
Uma visão multidimensional da
classificação de DM
• DB a serem minerados:
– DB relacional, transacional, OO, OR, ativo, espacial, sérietemporal, textual, multimídia, herdado, heterogêneo, Web...
• Conhecimento a ser minerado:
– Caracterização, agrupamento, associação, classificação,
discriminação, tendência, desvios...
– Funções integradas e mineração em níveis múltiplos;
• Técnicas utilizadas:
– Orientada à DB, data warehouse (OLAP), aprendizagem de
máquina (ML), estatística, visualização...
• Aplicações alvo:
– Varejo, telecomunicações, fraudes, DNA mining, Web
mining...
61
OLAP mining: uma integração de data
warehousing e DM
• Acoplamento dos sistemas de DM, DBMS e data warehouse;
– Sem acoplamento, fracamente acoplados, semi-acoplados,
acoplados;
• On-line analytical mining (OLAM):
– Integração das tecnologias de OLAP e DM;
• Mineração interativa e conhecimento multi-níveis:
– Necessidade de minerar conhecimento e padrões em
diferentes níveis de abstração utilizando drilling / rolling , etc.
• Integração de múltiplas funções de mineração:
– Classificação caracterizada, primeiro agrupamento e depois
associação.
62
Uma arquitetura OLAM
Mining query
Mining result
Layer4
User Interface
User GUI API
OLAM
Engine
OLAP
Engine
Layer3
OLAP/OLAM
Data Cube API
Layer2
MDDB
MDDB
Meta Data
Filtering&Integration
Database API
Filtering
Layer1
Data cleaning
Databases
Data
Data integration Warehouse
Data
63
Repository
Pontos centrais em DM
• Metodologia de mineração e interação com o usuário:
– Mineração de diferentes tipos de conhecimento nas DB;
– Mineração interativa em vários níveis de abstração;
– Incorporação de conhecimento de fundo (background
knowledge);
– Linguagens de consulta para DM e DM ad-hoc;
– Visualização e apresentação dos resultados de DM;
– Manuseio de dados incompletos e de ruídos;
– Avaliação dos padrões: o problema do interesse.
• Performance e escalabilidade:
– Eficiência e escalabilidade dos algoritmos de DM;
– Métodos de DM paralelo, distribuído e incremental.
64
Pontos centrais em DM
• Pontos relacionados à diversidade de tipos de dados:
– Manuseio de dados relacionais e complexos;
– Mineração de fluxos de informação de DB heterogêneas e
de sistemas de informação globais (Web).
• Pontos relacionados às aplicações e impactos sociais:
– Aplicações de descoberta de conhecimento:
• Ferramentas de DM para domínios específicos;
• Resposta inteligente a consultas;
• Controle de processos e processo decisório.
– Integração do conhecimento descoberto ao conhecimento
existente: o problema da fusão de conhecimentos;
– Proteção de dados, segurança, integração e privacidade.
65
Sumário
• Data mining: descoberta de padrões interessantes em grandes
quantidades de dados;
• DM é uma evolução natural da tecnologia de DB, com grande
número de possíveis aplicações;
• O processo de KDD inclui a limpeza, integração, seleção e
transformação dos dados, data mining, avaliação dos padrões e
apresentação do conhecimento;
• A mineração pode ser executada em vários repositórios de
informação;
• Funcionalidades do DM: caracterização, discriminação,
associação, classificação, agrupamento, desvios, análise de
tendências, etc.
• Classificação dos sistemas de DM;
• Pontos centrais em DM.
66
Referências
•
J. Han, M. Kamber. Data Mining: Concepts and Techniques. Morgan
Kaufmann, 2000.
•
R. Goldschmidt; E. Passos. Data Mining: um Guia Prático. Editora
Campus, 2005.
•
I.H.Witten, E. Frank. Data Mining: Practical Machine Learning Tools
and Techniques with JAVA Implementations. Morgan Kaufmann, 2000.
•
P. Adriaans, D. Zantinge. Data Mining. Addison-Wesley, 1996.
•
U. M. Fayyad, G. Piatetsky-Shapiro, P. Smyth, and R. Uthurusamy.
Adv.in Knowledge Discovery and Data Mining. AAAI/MIT Press, 1996.
•
A. Berson, S.J. Schimdt. Data Warehousing, Data Mining & OLAP.
McGraw-Hill, 1997.
•
G. Piatetsky-Shapiro and W. J. Frawley. Knowledge Discovery in
Databases. AAAI/MIT Press, 1991.
67