Data Mining

BANCO DE DADOS
DISTRIBUÍDOS e DATAWAREHOUSING
Asterio K. Tanaka
http://www.uniriotec.br/~tanaka/tin0036
[email protected]
Introdução a Data Mining
Asterio K. Tanaka
Introdução a Data Mining
•
•
•
•
Conceitos: DM x OLAP
DM como parte de KDD
Objetivos gerais de KDD/DM
Conhecimentos descobertos com DM
–
–
–
–
–
Regras de associação
Hierarquias de classificação
Padrões sequenciais
Padrões em séries temporais
Categorização e segmentação
• Técnicas de DM
– Técnicas para regras de associação
– Árvores de decisão
– Outras técnicas
• Aplicações
Asterio K. Tanaka
Business Intelligence
Increasing potential
to support
business decisions
End User
Making
Decisions
Business
Analyst
Data Presentation
Visualization Techniques
Data Mining
Information Discovery
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
Asterio K. Tanaka
Ambientes analíticos
Data Mining
OLAP
Ferramentas
de Consulta
Modelagem/ Nenhuma ou poucas hipóteses
Segmentação
Multidimensional
Consultas padrão
Hipóteses moderadas
Hipóteses seguras
Asterio K. Tanaka
Arquitetura Genérica de um
Data Warehouse
Meta Dados
FERRAMENTAS
DE CONSULTA
FONTES DE DADOS
OLAP
BDs Operacionais
Extração
Transformação
Carga
Atualização
Análise
Data Mining
Data Warehouse
Relatórios
Fontes Externas
Data Marts
OLAP
Chaudhri&Dayal, SIGMOD RECORD 1997
Asterio K. Tanaka
Processo de Data Warehousing
Asterio K. Tanaka
KDD – Knowledge Discovery in Databases
Fayyad, Usama; Piatetski-Shapiro, Gregory; Smyth, Padhraic (1996) The
KDD Process for Extracting Useful Knowledge from Volumes of Data.
In: Communications of the ACM, pp.27-34, Nov.1996
Asterio K. Tanaka
Definições de Data Mining
• Descoberta de informações não reveladas
em um banco de dados
• Termos Similares
– Categorização de Dados
– Análise Exploratória de Dados (Exploratory Data
Analisys)
– Descoberta orientada a dados (Data driven discovery)
– Aprendizado dedutivo (Deductive learning)
• É parte de KDD (Knowledge Discovery in
Databases)
Asterio K. Tanaka
Data Mining
Processo de extrair informação válida,
previamente desconhecida e de máxima
abrangência a partir de grandes bases
de dados, usando-as para tomada de
decisões.
Permite aos usuários explorar e inferir
informação útil a partir dos dados,
descobrindo relacionamentos escondidos
no banco de dados
Asterio K. Tanaka
Objetivos de Data Mining
• Explanatório: explicar algum evento ou medida observada
– porque a venda de sorvetes caiu no Rio de Janeiro;
• Confirmatório: confirmar uma hipótese
– Uma companhia de seguros , por exemplo, pode querer examinar
os registros de seus clientes para determinar se famílias de duas
rendas tem mais probalidade de adquirir um plano de saúde do
que famílias de uma renda;
• Exploratório:analisar os dados buscando relacionamentos novos e não
previstos.
– Uma companhia de cartão de crédito pode analisar seus registros
históricos para determinar que fatores estão associados a
pessoas que representam risco para créditos
Asterio K. Tanaka
Objetivos de DM e KDD
•
•
•
•
Prediction—Data mining can show how certain attributes within the data will behave in the
future. Examples of predictive data mining include the analysis of buying transactions to predict
what consumers will buy under certain discounts, how much sales volume a store would
generate in a given period, and whether deleting a product line would yield more profits. In
such applications, business logic is used coupled with data mining. In a scientific context,
certain seismic wave patterns may predict an earthquake with high probability.
Identification—Data patterns can be used to identify the existence of an item, an event, or an
activity. For example, intruders trying to break a system may be identified by the programs
executed, files accessed, and CPU time per session. In biological applications, existence of a
gene may be identified by certain sequences of nucleotide symbols in the DNA sequence. The
area known as authentication is a form of identification. It ascertains whether a user is indeed a
specific user or one from an authorized class; it involves a comparison of parameters or images
or signals against a database.
Classification—Data mining can partition the data so that different classes or categories can
be identified based on combinations of parameters. For example, customers in a supermarket
can be categorized into discount-seeking shoppers, shoppers in a rush, loyal regular shoppers,
and infrequent shoppers. This classification may be used in different analyses of customer
buying transactions as a post-mining activity. Sometimes classification based on common
domain knowledge is used as an input to decompose the mining problem and make it simpler.
For instance, health foods, party foods, or school lunch foods are distinct categories in the
supermarket business. It makes sense to analyze relationships within and across categories as
separate problems. Such categorization may be used to encode the data appropriately before
subjecting it to further data mining.
Optimization—One eventual goal of data mining may be to optimize the use of limited
resources such as time, space, money, or materials and to maximize output variables such as
sales or profits under a given set of constraints. As such, this goal of data mining resembles
the objective function used in operations research problems that deals with optimization under
constraints
Asterio K. Tanaka
Tipos de conhecimento
descoberto com DM
1.
2.
3.
4.
5.
Association rules—These rules correlate the presence of a set of items with another range of
values for another set of variables. Examples: (1) When a female retail shopper buys a handbag, she
is likely to buy shoes. (2) An X-ray image containing characteristics a and b is likely to also exhibit
characteristic c.
Classification hierarchies—The goal is to work from an existing set of events or transactions to
create a hierarchy of classes. Examples: (1) A population may be divided into five ranges of credit
worthiness based on a history of previous credit transactions. (2) A model may be developed for the
factors that determine the desirability of location of a store on a 1–10 scale. (3) Mutual funds may be
classified based on performance data using characteristics such as growth, income, and stability.
Sequential patterns—A sequence of actions or events is sought. Example: If a patient underwent
cardiac bypass surgery for blocked arteries and an aneurysm and later developed high blood urea
within a year of surgery, he or she is likely to suffer from kidney failure within the next 18 months.
Detection of sequential patterns is equivalent to detecting association among events with certain
temporal relationships.
Patterns within time series—Similarities can be detected within positions of the time series. Three
examples follow with the stock market price data as a time series: (1) Stocks of a utility company
ABC Power and a financial company XYZ Securities show the same pattern during 1998 in terms of
closing stock price. (2) Two products show the same selling pattern in summer but a different one in
winter. (3) A pattern in solar magnetic wind may be used to predict changes in earth atmospheric
conditions.
Categorization and segmentation—A given population of events or items can be partitioned
(segmented) into sets of "similar" elements. Examples: (1) An entire population of treatment data on
a disease may be divided into groups based on the similarity of side effects produced. (2) The adult
population in the United States may be categorized into five groups from "most likely to buy" to "least
likely to buy" a new product. (3) The web accesses made by a collection of users against a set of
documents (say, in a digital library) may be analyzed in terms of the keywords of documents to
reveal clusters or categories of users.
Asterio K. Tanaka
Data Mining e KDD
• Knowledge Discovery in Databases (KDD):
processo de encontrar informação útil em dados.
• Data Mining: Uso de algoritmos para extração
desta informação –
isto é, DM é parte do processo de KDD.
Asterio K. Tanaka
Processo de KDD
Modified from [FPSS96C]
•
•
•
•
•
Seleção: Obtenção de dados de várias fontes.
Preprocessamento: Limpeza dos dados.
Transformação: Conversão para formato comum.
Data Mining: Obtenção de informação.
Interpretação/Avaliação: Apresentação de
resultados de forma útil.
Asterio K. Tanaka
KDD Ex: Web Log
• Seleção:
– Selecionar dados de log (datas e locais)
• Preprocessamento:
– Remover erros logados
• Transformação:
– Ordenar e agrupar
• Data Mining:
– Identificar e contar padrões
• Interpretação/Avaliação:
– Identificar e mostrar sequencias de acesso frequentes
• Empregos Potenciais:
– Otimização de Cache
– Personalização
Asterio K. Tanaka
Desenvolvimento em Data Mining
•Modelo Relacional
•SQL
•Data Warehousing/OLAP
•Técnicas de Escalabilidade
•Análise, Projeto e Síntese de
Algoritmos
•Estruturas de Dados
•Medidas de Similaridade
•Queries imprecisas
•Informação não estruturada
•Máquinas de Busca
•Teorema de Bayes
•K-Means Clustering
•Análise de Séries de
Tempo
•Redes Neurais
•Lógica nebulosa
•Algoritmos Genéticos
•Teoria dos Conjuntos
Aproximativos
Asterio K. Tanaka
Conceitos Relacionados
•
•
•
•
•
•
•
Bancos de Dados/OLTP
Fuzzy Sets/Logic
Ciência da Informação (Information Retrieval)
Modelagem Dimensional/DW/OLAP
Métodos Estatísticos
Aprendizado de Máquina (Machine Learning)
Visualização
• Computação de Alto Desempenho
(algoritmos/paralelismo)
• Outras disciplinas:
– Redes neurais, modelagem matemática, reconhecimento de
padrões, etc.
Asterio K. Tanaka
DM versus DW e OLAP
•
•
•
DM provê outro nível de análise mais sofisticada que
a provida por ferramentas OLAP
DM em DWs se beneficia da integração e limpeza já
feita sobre os dados
Mas não necessariamente precisa ser feito sobre
DWs
†
Data warehousing/OLAP: Orientado a verificação
†
Data Mining: Orientado a descobertas nãoantecipadas
Asterio K. Tanaka
Banco de Dados vs. Data Mining
•
Consultas
•
– Fracamente definidas
– Linguagem de consulta não definida
precisamente
– Bem definidas
– SQL
„
Dados
„
– Operacionais
„
Output
– Preciso
– Subconjunto do
banco de dados
Consultas
Dados
– Não operacionais
„
Output
– Fuzzy
– Não é subconjunto do banco
de dados
Asterio K. Tanaka
Exemplos de Consultas
• Banco de Dados
– Encontre todas as aplicações de crédito com último nome Silva.
– Identifique clientes que compraram mais de R$ 10.000,00 no
último mês.
– Liste as vendas diárias de leite no último mês.
• Data Mining
– Encontre todos as aplicações de crédito que representem
risco (classificação).
– Identifique clientes com perfis de consumo similares
(Clustering).
– Encontre items que normalmente são comprados em
conjunto com leite (regras de associação).
Asterio K. Tanaka
Objetivos de Data Mining
Modelos e Tarefas
Asterio K. Tanaka