Mineração de Dados: Introdução - dee.ufrn.bralfredo/dm_ia/cap1_introdu%e7%e3o_a%20DM.pdf · semelhantes que são resposta ... – Objetivo: Reduzir os custos de envio ao focar

© Tan,Steinbach, Kumar Introduction to Data Mining 4/18/2004 1

Mineração de Dados: Introdução

Notas de Aula do Capítulo 1

Introdução à Mineração de Dados

por

Tan, Steinbach, Kumar


� Muitos dados estão sendo

coletados e armazenados

– Dados da web, comércio

Eletrônico

– Compras em lojas de

departamento/supermercados

– Transações bancárias /

transações com cartões de crédito

� Os computadores se tornaram mais baratos e potentes

� A pressão competitiva é forte

– Proporcionar serviços melhores e personalizados para umseguimento (por exemplo na gestão das relações com oconsumidor)

Porque fazer Mineração de Dados? Ponto de Vista Comercial

� Dados coletados e

armazenados a velocidadesenormes (GB/hora)

– sensores remotos em um satélite

– telescópios varrendo o céu– microarrays generating gene

expression data

– simulações científicas gerando

terabytes de dados� As técnicas tradicionais são inviáveis para

tratar dados brutos� A mineração de dados pode ajudar oscientistas

– na classificação e segmentação de dados

– Na formação de hipóteses

Porque fazer Mineração de Dados? Ponto de Vista Científico


Mineração de grandes conjuntos de dados – Motivação

� Muitas vezes existe informação “escondida” nos dados que não é facilmente visível

� Analistas humanos podem levar semanas para descobrir informações úteis

� Grande parte dos dados não é analisada

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”


O que é Mineração de Dados?

�Existem muitas definições– Extração não trivial de informação implícita,

previamente desconhecida e potencialmente útil dos dados

– Exploração e análise por meios automáticos ou semi-automáticos, de grandes quantidades de dados a fim dedescobrir padrões significativos


O que (não) é Mineração de Dados?

�O que é Mineração de Dados?

– Certos nomes prevalecem em determinados locais dos E.U.A. (O'Brien, O'Rurke, O'Reilly ... em

Boston)

– Agrupar documentos semelhantes que são resposta do mecanismo de busca de acordo com seu contexto (por exemplo, floresta amazônica, Amazon.com,)

�O que não é Data Mining?

– Procurar números de telefone numa lista telefônica

– Consultar um mecanismo de busca da Web para obter informações sobre a “Amazônia”


� Se baseia nas idéias de aprendizado de máquina/IA, reconhecimento de padrões, estatística e sistemas de banco de dados

� Técnicas tradicionais podem ser inadequadas devido à

– Tamanho da base dados– Alta dimensionalidade dos dados– Dados cuja natureza de distribuição é heterogênea

Origens da Mineração de Dados

Machine Learning/

Pattern Recognition

Statistics/AI

Data Mining

Database systems


Mineração de Dados: Tarefas

� Métodos de Predição

– Usa algumas variáveis para prever valores desconhecidos ou futuros de outras variáveis.

� Métodos de Descrição

– Encontrar padrões que descrevem os dados e possam ser interpretados pelos humanos.

From [Fayyad, et.al.] Advances in Knowledge Discovery and Data Mining, 1996


Mineração de Dados: Tarefas ...

� Classificação [Preditiva]

� Clustering [Descritiva]

� Descoberta de Regras de Associação [Descritiva]

� Descoberta de Padrões Sequenciais [Descritiva]

� Regressão [Preditiva]

� Detecção de Desvio [Preditiva]


Classificação: Definição

� Dada uma coleção de registros (conjunto de treinamento)

– Cada registro contém um conjunto de atributos, um dos atributos é a classe.

� Encontrar um modelo para o atributo de classe como uma função dos valores de outros atributos.

� Objetivo: registros inéditos devem ser atribuídos a uma classe com a maior precisão possível.

– Um conjunto de teste é utilizado para determinar a precisão do modelo. Normalmente, o conjunto de dados é dividido em conjuntos de treinamento e de teste, com o conjunto de treinamento usado para construir o modelo e o conjunto de teste utilizado para validá-lo.


Exemplo de Classificação

Tid Refund MaritalStatus

TaxableIncome Cheat

1 Yes Single 125K No

2 No Married 100K No

3 No Single 70K No

4 Yes Married 120K No

5 No Divorced 95K Yes

6 No Married 60K No

7 Yes Divorced 220K No

8 No Single 85K Yes

9 No Married 75K No

10 No Single 90K Yes10

Refund MaritalStatus

TaxableIncome Cheat

No Single 75K ?

Yes Married 50K ?

No Married 150K ?

Yes Divorced 90K ?

No Single 40K ?

No Married 80K ?10

TestSet

Training Set

ModelLearn

Classifier


Classificação: Aplicação 1

� Marketing Direto

– Objetivo: Reduzir os custos de envio ao focar um

conjunto de consumidores propensos a comprar um novo produto desenvolvido para celulares.

– Abordagem:

� Usar os dados de um produto similar introduzido previamente.

� Sabemos quais os clientes que decidiram comprar e quais os

que decidiram o contrário. Esta decisão {comprar, não comprar}

constitui o atributo de classe.

� Coletar diversas informações relacionadas à demografia, estilo

de vida, interação da empresa... sobre todos esses clientes.

– Tipo de negócio, onde eles ficam, o quanto eles ganham, etc.

� Usar essas informações como atributos de entrada para

desenvolver um modelo de classificação.From [Berry & Linoff] Data Mining Techniques, 1997



� Detecção de Fraude

– Objetivo: Prever casos fraudulentos nas transações envolvendo cartões de crédito.

– Abordagem:

� Usar as transações com cartão de crédito e as informações sobre titular da conta como atributos.

– Quando é que um cliente compra, o que ele compra, quantas vezes ele paga na hora, etc

� Rotular transações anteriores como fraudulentas ou legítimas. Isto constitui o atributo de classe.

� Encontrar um modelo para a classe das transações.

� Usar este modelo para detectar fraudes, observando as transações de um cartão de crédito em uma conta.



� Análise de mudanças dos consumidores (churn):

– Objetivo: Prever se um cliente é susceptível a ser perdido para um concorrente.

– Abordagem:

�Usar um registro detalhado das transações realizadas com cada um dos clientes atuais e anteriores, para localizar os atributos.

– Quantas vezes o cliente liga, onde ele liga, a que hora do dia ele

liga mais, a sua situação financeira, estado civil, etc.

�Rotular os clientes como leais ou desleais.

�Encontrar um modelo para a fidelidade.

From [Berry & Linoff] Data Mining Techniques, 1997



� Catalogação de Pesquisas estelares

– Objetivo: Prever a classe de objetos estelares (estrela ou galáxia), especialmente aqueles visualmente

esvanecidos, com base nas imagens de pesquisas

telescópicas (do Observatório de Palomar).

– 3000 imagens com 23.040 x 23.040 pixels por imagem.

– Abordagem:

� Segmentar a imagem.

� Medir os atributos da imagem (características) - 40 deles por

objeto.

� Modelar a classe com base nestas características.

� História de sucesso: foi possível encontrar 16 novos high red-

shift quasars, alguns dos objetos mais distantes que são

difíceis de encontrar!From [Fayyad, et.al.] Advances in Knowledge Discovery and Data Mining, 1996


Classificando Galáxias

Early

Intermediate

Late

Tamanho do Banco de Dados: • 72 milhões de estrelas, 20 milhões de galáxias • Catálogo de Objetos: 9 GB

• Banco de dados das imagens: 150 GB

Classes: • Estágios de Formação

Atributos:• Características da imagem,

• Características das ondas de luz recebidas, etc.

Courtesy: http://aps.umn.edu


Definição de Clusters

� Dado um conjunto de pontos de dados, cada um tendo um conjunto de atributos, e uma medida de semelhança entre eles, encontrar clusters de tal forma que

– Os pontos de dados em um cluster são mais semelhantes entre si.

– Os pontos de dados em clusters separados são menos semelhantes entre si.

� Medidas de similaridade:

– Distância Euclidiana se os atributos são contínuos.

– Outras medidas específicas do problema.


Ilustrando a Clusterização

⌧Clusterização baseada na distância euclidiana num espaço 3-D.

As distâncias dentro do cluster

são minimizados

As distâncias dentro do cluster

são minimizados

As distâncias entre os clusters

são maximizadas

As distâncias entre os clusters

são maximizadas


Clustering: Aplicação 1

� Segmentação de Mercado:

– Objetivo: subdividir um mercado em subconjuntos distintos de clientes, em que qualquer subconjunto pode concebivelmente ser selecionado como um mercado-alvo a ser atingido com mix de marketing distinto.

– Abordagem:� Coletar atributos diferentes de clientes com base em suas

informações geográficas e relacionadas ao seu estilo de vida.

� Encontrar clusters contendo clientes semelhantes.

� Medir a qualidade do agrupamento observando os padrões de compra dos clientes no mesmo cluster versus aqueles de clusters diferentes.


Clustering: Aplicação 2

� Clusterização de documentos:

– Objetivo: Encontrar grupos de documentos que

são similares uns aos outros com base nos

termos importantes que neles aparecem.

– Abordagem: Identificar os termos mais frequentes

em cada documento. Formar uma medida de

similaridade baseada nas freqüências de termos

diferentes. Use-a para formar os clusters.

– Ganho: Recuperação de Informação pode utilizar

os clusters para relacionar um novo documento

ou termos de pesquisa aos documentos

presentes nestes clusters.


Ilustrando a Clusterização de Documentos

� Pontos de clusterização: 3204 Artigos do Los Angeles Times.

� Medida de similaridade: Quantas palavras são comuns nestes

documentos (após a filtragem de algumas palavras).

Category TotalArticles

CorrectlyPlaced

Financial 555 364

Foreign 341 260

National 273 36

Metro 943 746

Sports 738 573

Entertainment 354 278


Clustering of S&P 500 Stock Data

Discovered Clusters Industry Group

1Applied-Matl-DOW N,Bay-Network-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,

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,

Co mpaq-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-UPOil-UP

� Observa os movimentos diários do estoque.� Pontos de clusterização: Stock-{UP/DOWN}� Medida de similaridade: Dois pontos são mais semelhantes se os eventos

descritos por eles acontecem frequentemente juntos no mesmo dia.�Usamos as regras de associação para quantificar uma medida de similaridade.


Descoberta de Regras de Associação: Definição

� Dado um conjunto de registros onde cada um contém um

determinado número de itens de uma dada coleção;

– Produz regras de dependência que irão prever a

ocorrência de um item com base em ocorrências de

outros itens.

TID Items

1 Bread, Coke, Milk

2 Beer, Bread

3 Beer, Coke, Diaper, Milk

4 Beer, Bread, Diaper, Milk

5 Coke, Diaper, Milk

Rules Discovered:

{Milk} --> {Coke}{Diaper, Milk} --> {Beer}

Rules Discovered:

{Milk} --> {Coke}{Diaper, Milk} --> {Beer}


Descoberta de Regras de Associação: Aplicação 1

� Marketing and Sales Promotion:

– Let the rule discovered be

{Bagels, … } --> {Potato Chips}

– Potato Chips as consequent => Pode ser usado para determinar o que deve ser feito para aumentar suas vendas.

– Bagels in the antecedent => Pode ser usado para ver quais os produtos que seriam afetados se a loja pára a venda de bagels.

– Bagels in antecedent and Potato chips in consequent=> Can be used to see what products should be sold with Bagels to promote sale of Potato chips!



� Gestão das prateleiras do supermercado.

– Objetivo: Identificar os itens que são comprados em conjunto por uma quantidade razoável de clientes.

– Abordagem: Processa os dados coletados no ponto-de-venda com scanners de código de barras para localizar as dependências entre os itens.

– Uma regra clássica --

�Se um cliente compra fraldas e leite, então é muito

provável que ele compre cerveja.

�Assim, não se surpreenda se você encontrar pacotes de cerveja empilhados ao lado de fraldas!



� Gestão de estoques:

– Objetivo: uma empresa assistência técnica quer

antecipar a natureza de reparos nos produtos de seus consumidores e manter os veículos de equipados com peças certas para reduzir no número de visitas

aos domicílios dos consumidores.

– Abordagem: processar os dados sobre as ferramentas e as peças necessárias nos reparos anteriores em locais diferentes e descobrir os

padrões de co-ocorrência.


Descoberta de padrões sequenciais: Definição

� Dado um conjunto de objetos, com cada objeto associado com a sua própria linha de tempo dos acontecimentos, encontrar as regras que prevêem fortes dependências seqüenciais entre diferentes eventos.

� As regras são formadas primeiramente pela descoverta de padrões. Ocorrências de eventos nos padrões são regidos por restrições de tempo.

(A B) (C) (D E)

<= ms

<= xg >ng <= ws

(A B) (C) (D E)


Descoberta de padrões sequenciais: Exemplos

� Nos logs dos alarmes de telecomunicações,

– (Inverter_Problem Excessive_Line_Current)

(Rectifier_Alarm) --> (Fire_Alarm)

� Nas sequencias de transação dos pontos de venda,

– Computer Bookstore:

(Intro_To_Visual_C) (C++_Primer) -->

(Perl_for_dummies,Tcl_Tk)

– Athletic Apparel Store:

(Shoes) (Racket, Racketball) --> (Sports_Jacket)


Regressão

� Prever um valor de uma determinada variável contínua

valorizados com base nos valores de outras variáveis, assumindo um modelo linear ou não linear de dependência.

� Muito estudada em estatística, no campo de redes neurais.

� Exemplos:

– Previsão da vendas de novos produtos baseado nas

despesas em propaganda.

– Previsão da velocidade do vento como uma função da

temperatura, umidade, pressão atmosférica, etc.

– Previsão de séries temporais de índices das bolsas de

valores.


Detecção de desvios e anomalias

� Detecta desvios significativos do comportamento normal

� Aplicações:

– Detecção de fraudes

envolvendo cartões de crédito

– Detecção de

intrusão na rede

Typical network traffic at University level may reach over 100 million connections per day


Desafios da Mineração de Dados

� Escalabilidade

� Dimensionalidade

� Dados complexos e heterogêneos

� Qualidade dos dados

� Propriedade e distribuição dos dados

� Preservação da Privacidade

� Streaming Data

Documents

Mineração de Dados: Introdução - dee.ufrn.bralfredo/dm_ia/cap1_introdu%e7%e3o_a%20DM.pdf · semelhantes que são resposta ... – Objetivo: Reduzir os custos de envio ao focar