Introdução

Prof. Dra. Nádia Félix

[Link]@[Link]

2021
Introdução

! Grande quantidade de informação armazenada em

muitas áreas: comércio, indústria, governo, ciência, etc.
! Exemplos:
– cada compra em um supermercado fica registrada em uma
tabela de transações(com o código de barra)
– todas as chamadas telefônicas (origem, destino, horário,
duração, ...)
– o SUS mantém registro magnético de todos os atendimentos
realizados (hospital, data, médico, diagnóstico, procedimentos
realizados, ...)
– Imagens de satélite, bioinformática, ...
BDs atuais

! BDs atuais são feitos para armazenar e recuperar rápida

e eficientemente dados operacionais
! BDs atuais são úteis para recuperar dados específicos,
mas não são capazes de extrair conhecimento genérico
! Exemplo: um sistema bancário recupera rapidamente as últimas
movimentações ou o saldo de uma conta, mas teria dificuldade em
descrever o perfil do cliente em relação a outros clientes ou
determinar se ele seria um bom pagador em caso de fazer um
empréstimo
BD x DM

! Banco de Dados
– Encontre todos os clientes com sobrenome “Silva”.
– Identifique os clientes que compraram mais de R$1.000,00 no
último mês.
– Encontre todos os clientes que compraram leite.

! Data Mining
– Encontre todos os clientes com baixo risco, em caso de
realizarem um empréstimo.

– Identifique clientes com hábitos de compras similares.

– Encontre todos os itens que são normalmente comprados

junto com leite.
Descoberta de conhecimento em bases de dados

Em Inglês – KDD (Knowlegde Discovery in Database)

Objetivo: extrair conhecimento novo, útil e

interessante, implícito em grandes volumes de
dados, e representá-lo de forma acessível para
o usuário.
Relações da DCBD com outras áreas

! O processo de DCBD utiliza conhecimento de

várias áreas:
– BD
– IA: aprendizagem de máquina, redes neurais,
representação de conhecimento, ...
– Estatística
– ...
DCBD: Exemplo

! Em uma empresa de fornecimento de água encanada

uma das maiores despesas é com energia elétrica

! Objetivo da empresa: reduzir o consumo de energia

elétrica
DCBD: Exemplo

! Dados:
– consumo diário de água
– aspectos do tempo (temperatura, umidade do ar, …)
– dia da semana e do mês, feriado, férias, ...

! Objetivo da DCBD: prever o consumo de água, de

forma a minimizar o bombeamento, e por conseguinte, o
consumo de energia elétrica
Tarefas de DCBD ...

! Classificação [Preditivo]
! Clustering [Descritivo]
! Regras de associação [Descritivo]
! Padrões seqüenciais [Descritivo]
! Outliers [Preditivo]
Exemplos de Tarefas de Classificação

! Predizer se um tumor é benigno ou maligno

! Classificar transações de cartões

de crédito como legítimas ou
fraudulentas

! Classificar estruturas secundárias de

proteínas como alpha-helix,
beta-sheet, or random coil

! Categorizar textos como da área de finanças,

previsão de tempo, esportes, cultura, etc.
Classificação: Aplicação 1

! Marketing direto
– Objetivo: Reduzir o custo de postagem na oferta para
um conjunto alvo de consumidores mais prováveis de
comprar um novo produto.
– Abordagem:
u Usar os dados de um produto similar oferecido anteriormente.
u Sabemos quais consumidores compraram e quais não
compraram. Esta decisão {compra, não compra} forma o
atributo classe.
u Coletarvárias informações demográficas, de estilo de vida e
de interações com a empresa de todos estes clientes.
– Tipo de atividade, local da moradia, rendimentos, estado civil, etc.
u Usar
esta informação como atributos de entrada para gerar
um modelo de classificação. From [Berry & Linoff] Data Mining Techniques, 1997
Classificação: Aplicação 2

! Detecção de fraudes
– Objetivo: identificar casos de fraude em transações
com cartão de crédito.
– Abordagem:
u Usaras 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, etc
u Rotular
as transações passadas como fraude ou não. Isto
forma o atributo classe.
u Gerar um modelo de classificação para as transações.
u Usar
este modelo para detectar fraudes observando as
novas transações .
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:
u 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,
etc.
u Rotularos clientes como fiéis ou infiéis a empresa.
u Gerar um modelo.
From [Berry & Linoff] Data Mining Techniques, 1997
Processo de Classificação

Deriva Modelo
Amostras Calcula Acuracia
(Regras)

Dados

Dados
de teste
Ilustrando a Tarefa de Classificação

Tid Attrib1 Attrib2 Attrib3 Class

Learning
1 Yes Large 125K No
algorithm
2 No Medium 100K No

3 No Small 70K No

4 Yes Medium 120K No

Induction
5 No Large 95K Yes

6 No Medium 60K No

7 Yes Large 220K No Learn

8 No Small 85K Yes Model
9 No Medium 75K No

10 No Small 90K Yes

Model
10

Training Set
Apply
Tid Attrib1 Attrib2 Attrib3 Class Model
11 No Small 55K ?

12 Yes Medium 80K ?

13 Yes Large 110K ? Deduction

14 No Small 95K ?

15 No Large 67K ?
10

Test Set
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.
– Um conjunto de teste é usado para determinar a
acurácia do modelo. Normalmente, o conjunto de
dados é dividido em conjunto de treinamento e
conjunto de teste, com o conjunto de treinamento
usado para a construção do modelo e o conjunto
de teste para validação.
 Exemplo...

Classe: compra produto

Eletrônico

Nome Idade Renda Profissão Classe

Daniel ≤ 30 Média Estudante Sim
João 31..50 Média-Alta Professor Sim
Carlos 31..50 Média-Alta Engenheiro Sim
Maria 31..50 Baixa Vendedora Não
Paulo ≤ 30 Baixa Porteiro Não
Otavio > 60 Média-Alta Aposentado Não

SE. Idade ≤ 30 E Renda = Média ENTÃO Compra-Produto-Eletrônico = SIM.

 Exemplo de Árvore de Decisão

IDADE

≤ 30
31-50
>60
51-60

PROFISSÃO
RENDA
Não Sim
Baixa Médico Engenheiro

Média Vendedor
Alta Professor
Med-Alta
Sim Sim
Não Sim Sim Não
Sim
Sim

Se Idade ≤ 30 e Renda= Baixa então Não compra Eletrônico

Se Idade = 31-50 e Profissão=Médico então compra Eletrônico

Clustering
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.
Clustering: exemplo

! Clustering em espaço 3-D baseado em distância euclidiana.

Distâncias intracluster Distâncias intercluster

são minimizadas são maximizadas
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:
u Obterdiferentes atributos de clientes baseado em
informações geográficas e de estilo de vida dos clientes
u Encontrar grupos (clusters) de clientes similares.
u Medir a qualidade dos clusters observando padrões de
compra entre clientes do mesmo cluster versus entre
clientes de outros clusters
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.
Exemplo de clustering de documentos

! Dados utilizados: 3204 artigos do jornal Los Angeles Times.

! Medida de similaridade: quantas palavras são comuns
nestes documentos (após a filtragem de algumas palavras).
Category Total Correctly
Articles Placed
Financial 555 364

Foreign 341 260

National 273 36

Metro 943 746

Sports 738 573

Entertainment 354 278

Clustering de ações da bolsa

! 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.
! Foram usadas regras de associação para quantificar a medida de
similaridade.
Discovered Clusters Industry Group

1
Applied-Matl-DOW N,Bay-Net work-Down,3-COM-DOWN,
Cabletron-Sys-DOWN,CISCO-DOWN,HP-DOWN,
DSC-Co mm-DOW N,INTEL-DOWN,LSI-Logic-DOWN,
Micron-Tech-DOWN,Texas-Inst-Down,Tellabs-Inc-Down,
Technology1-DOWN
Natl-Semiconduct-DOWN,Oracl-DOWN,SGI-DOW N,
Sun-DOW N

2
Apple-Co mp-DOW N,Autodesk-DOWN,DEC-DOWN,
ADV-M icro-Device-DOWN,Andrew-Corp-DOWN,
Co mputer-Assoc-DOWN,Circuit-City-DOWN,
Technology2-DOWN
Co mpaq-DOWN, EM C-Corp-DOWN, Gen-Inst-DOWN,
Motorola-DOW N,Microsoft-DOWN,Scientific-Atl-DOWN

3
Fannie-Mae-DOWN,Fed-Ho me-Loan-DOW N,
MBNA-Corp -DOWN,Morgan-Stanley-DOWN Financial-DOWN

4
Baker-Hughes-UP,Dresser-Inds-UP,Halliburton-HLD-UP,
Louisiana-Land-UP,Phillips-Petro-UP,Unocal-UP, Oil-UP
Schlu mberger-UP
Regras de Associação
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 Regras descobertas:
2 cerveja, pão {leite} --> {guaraná}
3 cerveja, fralda, guaraná, leite {fralda, leite} --> {cerveja}
4 cerveja, fralda, leite, pão
5 fralda, guaraná, leite
Regras de associação: Aplicação 1

! Marketing e promoção de vendas:

– Considere a seguinte regra descoberta
{Paçoquinha, … } à {Batata Frita}
– Batata Frita como conseqüente: Pode ser usada para
determinar o que deve ser feito para incrementar a
sua venda.
– Paçoquinha no antecedente: Pode ser usado para
ver que produtos podem ser afetados se a loja deixar
de vender Paçoquinha.
– Paçoquinha no antecedente e Batata Frita no
conseqüente: Pode ser usado para ver que produtos
poderiam ser vendidos com Paçoquinha para
promover a venda de Batata Frita!
Regras de associação: Aplicação 2

! 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--
u Se um cliente compra fralda e leite ele tem uma
boa probabilidade de comprar também cerveja.
u Portanto, não fique surpreso de encontrar pacotes
de cerveja próximo das fraldas!
Regras de associação: Aplicação 3

! 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.
 Padrões seqüenciais: 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)
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)
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
Typical network traffic at University level may reach over 100 million connections per day
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
Bibliografia

! TAN,P-N;STEIMBACH, M; KUMAR,V. Introduction to Data Mining. Boston: Addison

Wesley, 2006. 769p.

! HAN,J.; KAMBER, M. Data mining: concepts and techniques. Morgan Kaufmann,

2006 – 2. edição.

! ADRIAANS, Pieter, ZANTINGE, Dolf. Data Mining. Harlow : Addison-Wesley,

1997. 158p.

! FAYYAD, Usama M. et al. Advances in Knowledge Discovery and Data Mining.

American Association for Artificial Intelligence, 1996. 611p.

! BERRY, Michael J. A.; LINOFF, Gordon. Data Mining techniques for marketing,
sales and custumer support. New York: John Wiley, 1997. 454p.

! PYLE, Dorian. Data preparation for data mining. San Diego: Academic Press, 1999.
540p.

! Artigos de congressos e revistas científicas

35