Apresentação do PowerPoint - ic.unicamp.brsantanch/teaching/db/2016-2/slides/Data_Mining... · O que é Data Mining? “Data mining is the process of discovering interesting patterns

Data Mining MC536 – Banco de Dados

Profº.: André Santanchè

PED: Lucas Oliveira Batista

Introdução

Dilúvio de dados

Dados de empresa, sociedade, ciência,

engenharia...

Apenas dados são suficientes?

2

Introdução

3

O que é Data Mining?

“Data mining is the process of discovering

interesting patterns and knowledge from

large amounts of data” (Han; Kamber; Pei,

2011)

Fontes de dados: Banco de Dados

relacionais, Banco de Dados em grafos,

Data Warehouse, Web…

4


Lots of raw data in

Some data mining

Facts, rules, patterns out

5

Lots of data

Some rules or facts or patterns

Fonte: Introdução a Data Mining Eamon Keogh


6

Data Mining não é Knowledge Discovery from Data


7

Data Mining não é Data Warehouse


8

Data Mining é um passo da KDD que aplica algoritmos específicos para

extrair padrões a partir de dados

Quais técnicas são utilizadas?

9

Data Warehouse

Reconhecimento

de padrões

Computação de

alta performace Aplicações

Data Mining

Banco de Dados

Estatística

Recuperação de Informação

Algoritmos

Aprendizado de Máquina

Visualização

Porque utilizar Data Mining?

Enorme quantidade de dados são

coletadas diariamente

Dificuldade dos humanos em visualizar e

entender grande conjunto de dados

Permite análise de dados automática

10

Empresa “Um Pouco de Tudo”

A Um Pouco de Tudo é uma grande

empresa de eletrônicos com diversas filiais

espalhadas pelo mundo

Armazena uma grande quantidade de

dados sobre filiais, empregados, clientes,

produtos, transações de vendas...

11

Quais métodos são utilizados

para gerar padrões?

Técnicas de Data Mining são dividas em:

Descrição de Classes/Conceitos

Mineração de padrões frequentes,

associações e correlações

Classificação e Regressão para análise

preditiva

Análise de agrupamento

Análise de outlier

12








preditiva


Análise de outlier

13

Descrição de

Classes/Conceitos

Associa dados a classes ou conceitos

Classes de itens a venda: computadores ou

impressoras

Conceito de clientes: gastaMuito ou

gastaPouco

Derivados usando caracterização de

dados e/ou discriminação de dados

14

Descrição de Classes/Conceitos:

Caracterização

Características gerais de uma classe

Um Pouco de Tudo: características de

clientes que gastam mais de R$ 5000 por

ano

15


Caracterização

Características gerais de uma classe

Um Pouco de Tudo: características de

clientes que gastam mais de R$ 5000 por

ano

Clientes entre 40 e 50 anos, empregados e

com alta taxa de crédito

16


Discriminação

Comparar características entre classes

Um Pouco de Tudo: Clientes que compram

regularmente X Clientes que raramente

compram

17


Discriminação

Um Pouco de Tudo: Clientes que compram

regularmente X Clientes que raramente

compram

18

80%

20%

20 e 40 anos,

ensino superior 60%

40% Jovens ou

idosos e sem

ensino

superior








preditiva


Análise de outlier

19

Padrões frequentes,


Padrões frequentes gera associações e

correlações entre dados

Um Pouco de Tudo: Quais itens são

frequentemente comprados juntos?

20







Compra (Cliente, PC) => Compra (Cliente,

Software) [suporte: 25% confiança: 50%]

21







22

Transação 1 PC, DVD, Software

Transação 2 DVD, Cartão Memória

Transação 3 PC, Cartão Memória

Transação 4 Televisão, Som







23











24












CD) [suporte: 0.3% confiança: 5%]

25








CD) [suporte: 0.3% confiança: 5%]

26

Exercício 1

Cite 2 padrões frequentes que poderiam

ser minerados considerando o banco de

dados abaixo.

27

Transação 1 Pão, leite, queijo, presunto, desodorante, feijão

Transação 2 Achocolatado, pão, leite

Transação 3 Cebola, laranja, salsa, manga

Transação 4 Carne, presunto, ovos, queijo, pão

Transação 5 Chocolate, pipoca, refrigerante, leite

Transação 6 Caneta, bala, fralda, queijo, leite, pão








preditiva


Análise de outlier

28

Classificação e Regressão

para análise preditiva

Classificação: baseada na análise de

dados de classes conhecidas

29

Examples of

class A

3 4

1.5 5

6 8

2.5 5

Examples of

class B

5 2.5

5 2

8 3

4.5 3

Pigeon Problem 1 (extraído de Eamon Keogh)

Examples of

class A

3 4

1.5 5

6 8

2.5 5

Examples of

class B

5 2.5

5 2

8 3

4.5 3

8 1.5

4.5 7

What class is this object?

What about this one, A or B?

Pigeon Problem 1

Examples of

class A

3 4

1.5 5

6 8

2.5 5

Examples of

class B

5 2.5

5 2

8 3

4.5 3

8 1.5

This is a B!

Pigeon Problem 1

Here is the rule. If the left bar is smaller than the right bar, it is an A, otherwise it is a B.

Examples of

class A

4 4

5 5

6 6

3 3

Examples of

class B

5 2.5

2 5

5 3

2.5 3

8 1.5

7 7

Even I know this one

Pigeon Problem 2 Oh! This ones hard!

Examples of

class A

4 4

5 5

6 6

3 3

Examples of

class B

5 2.5

2 5

5 3

2.5 3

7 7

Pigeon Problem 2

So this one is an A.

The rule is as follows, if the two bars are equal sizes, it is an A. Otherwise it is a B.

Examples of

class A

4 4

1 5

6 3

3 7

Examples of

class B

5 6

7 5

4 8

7 7

6 6

Pigeon Problem 3

This one is really hard! What is this, A or B?

Examples of

class A

4 4

1 5

6 3

3 7

Examples of

class B

5 6

7 5

4 8

7 7

6 6

Pigeon Problem 3 It is a B!

The rule is as follows, if the square of the sum of the two bars is less than or equal to 100, it is an A. Otherwise it is a B.

Person Hair

Length

Weight Age Class

Homer 0” 250 36 M

Marge 10” 150 34 F

Bart 2” 90 10 M

Lisa 6” 78 8 F

Maggie 4” 20 1 F

Abe 1” 170 70 M

Selma 8” 160 41 F

Otto 10” 180 38 M

Krusty 6” 200 45 M

Comic 8” 290 38 ?

Weight <= 160?

yes no

Hair Length <= 2?

yes no

Weight <= 160?

yes no

Hair Length <= 2?

yes no

Male

Male Female

How would

these people

be classified?



Um Pouco de Tudo: Classificar o resultado

de um item em promoção em BOM ou

RUIM

40





RUIM

41

Desconto, marca

20%, DELL

50%, ITAUTEC

30%, DELL

21%, ITAUTEC

10%, DELL

15%, DELL

Desconto, marca

10%, ITAUTEC

15%, ITAUTEC

5%, ITAUTEC

20%, ITAUTEC

19%, ITAUTEC





RUIM

42

Desconto, marca

20%, DELL

50%, ITAUTEC

30%, DELL

21%, ITAUTEC

10%, DELL

15%, DELL

Desconto, marca

10%, ITAUTEC

15%, ITAUTEC

5%, ITAUTEC

20%, ITAUTEC

19%, ITAUTEC

Padrão:

Se desconto>20%

BOM

SenãoSe marca=DELL

BOM

Senão RUIM





RUIM

43

Desconto, marca

20%, DELL

50%, ITAUTEC

30%, DELL

21%, ITAUTEC

10%, DELL

15%, DELL

Desconto, marca

10%, ITAUTEC

15%, ITAUTEC

5%, ITAUTEC

20%, ITAUTEC

19%, ITAUTEC

Padrão:

Se desconto>20%

BOM

SenãoSe marca=DELL

BOM

Senão RUIM



Regressão: prever valores em falta ou não

disponíveis

Um Pouco de Tudo: Prever a receita de um

item com base em anos anteriores

44





45 0

0,5

1

1,5

2

2,5

3

3,5

4

2005 2006 2007 2008 2009 2010 2011 2012 2013

Re

ce

ita

(e

m m

ilh

õe

s)

Ano





46 0

0,5

1

1,5

2

2,5

3

3,5

4

2005 2006 2007 2008 2009 2010 2011 2012 2013

Re

ce

ita

(e

m m

ilh

õe

s)

Ano








preditiva


Análise de outlier

47

Análise de Agrupamento

Analisa o conjunto de dados sem conhecer

as classes que pertencem

Um Pouco de Tudo: Agrupar os clientes de

acordo com seu endereço

48




49




50








preditiva


Análise de outlier

51

Análise de Outlier

Analisa dados com comportamento muito

diferente dos demais dados

Um Pouco de Tudo: Detectar fraudes no

uso do cartão de crédito

52

Análise de Outlier



53 0

2000

4000

6000

8000

10000

12000

set/11 dez/11 abr/12 jul/12 out/12 jan/13 mai/13

Va

lor

da

co

mp

ra (

em

re

ais

)

Mês/Ano

Análise de Outlier



54 0

2000

4000

6000

8000

10000

12000

set/11 dez/11 abr/12 jul/12 out/12 jan/13 mai/13

Va

lor

da

co

mp

ra (

em

re

ais

)

Mês/Ano

outlier

Todos os padrões são

interessantes?

Não!

Milhões de padrões podem ser gerados e pequena fração de padrões interessam ao usuário

Padrão interessante: Facilmente compreendido por humanos

Válido com um determinado grau de certeza

Potencialmente útil

Novo

ou

Valida a hipótese do usuário

55

Exercício 2

Dentre os conceitos de Data Mining

apresentados, quais conceitos você

utilizaria no banco de dados da sua rede

social? Justifique.

56

57

Database vs. Data Mining

• Query – Well defined

– SQL

• Query – Poorly defined

– No precise query language

Output

– Subset of database

Output –Not a subset of database

• Field – Mature

• Field – Maturing

Query Examples

Database • Find all customers that live in Boa Vista

• Find all customers that use Mastercard

• Find all customers that missed one payment

Data mining • Find all customers that are likely to miss one payment (Classification)

• Group all customers with simpler buying habits (Clustering)

• List all items that are frequently purchased with bicycles (Association rules)

• Find any “unusual” customers (Outlier detection, anomaly discovery)

Why is Data Mining Hard?

Scalability

Heterogeneous and Complex Data

Data Ownership and Distribution

Non-traditional Analysis

Privacy issues

60 Fonte: Introdução a Data Mining Eamon Keogh

Data Mining x Sociedade

Qual o impacto do data mining na sociedade?

Violação de privacidade, direitos autorais

Data mining ajuda em pesquisas científicas, gerenciamento empresarial

Divulgação imprópria de dados, violação de privacidade

Data mining invisível

61

Aplicações

62

http://www.google.com.br/url?sa=i&source=images&cd=&cad=rja&docid=2ufoYS9-gZadbM&tbnid=akt3qzzXKpQKoM:&ved=0CAgQjRwwAA&url=http://ensinobiblicoinfantilnani.blogspot.com/2010/12/bichos-da-biblia-gafanhoto-nao-tem.html&ei=oU9mUfaWEqyt0AGgrYC4Ag&psig=AFQjCNFfDlPpW4YF1TTtJ1JEhHob_lpMww&ust=1365745953328509

Em empresas

Diversas empresas utilizam data mining

para marketing, investimento, detecção de

fraude...

Google, Facebook, Walmart, Visa,

Mastercard...

63

Caso Target

Segunda maior rede varejista dos Estados

Unidos

“Aumentou alguns bilhões de dólares no seu

faturamento anual, apenas criando estratégias

de venda com base nas informações extraídas

da mineração de dados.”

A Target sabia que uma adolescente estava

grávida antes mesmo dos pais dela

64

Caso Target

“Conforme o computador analisava os dados,

ele foi capaz de identificar cerca de 25

produtos que, quando analisados em conjunto,

lhe permitiram atribuir a cada cliente uma

pontuação de “previsão de gravidez”. Mais

importante, ele também poderia estimar a

data do parto para dentro de um pequeno

intervalo de tempo, assim a Target poderia

enviar cupons programados para estágios

muito específicos de sua gravidez.”

65

Fonte: http://tecnoblog.net/151635/potencial-whatsapp-mineracao-de-dados/

Em pesquisas

Eamon Keogh

Mineração de séries temporais

Classificação de insetos, folhas....

http://www.cs.ucr.edu/~eamonn/

66

67

email

spam The Classification Problem

Given a collection of annotated

data…

Spam or email?

Polish

Spanish The Classification Problem


data…

Spanish or Polish?

False Nettle

Stinging

Nettle

The Classification Problem


data…

Stinging Nettle or False Nettle?

Irish

Greek The Classification Problem


data…

Greek or Irish?

Gunopulos

Papadopoulos

Kollios

Dardanos

Keogh

Gough

Greenhaugh

Hadleigh Tsotras

Grasshoppers

Katydids The Classification Problem (informal definition)


data. In this case 5 instances

Katydids of and five of

Grasshoppers, decide what

type of insect the unlabeled

example is.

Katydid or Grasshopper?

http://buzz.ifas.ufl.edu/258dj.jpg

http://buzz.ifas.ufl.edu/091dmj.jpg

Thorax

Length

Abdomen

Length Antennae

Length

Mandible

Size

Spiracle

Diameter Leg Length

For any domain of interest, we can measure features

Color {Green, Brown, Gray, Other} Has Wings?

An

ten

na

Le

ng

th

10

1 2 3 4 5 6 7 8 9 10

1

2

3

4

5

6

7

8

9

Grasshoppers

Katydids

Abdomen Length

An

ten

na

Le

ng

th

10

1 2 3 4 5 6 7 8 9 10

1

2

3

4

5

6

7

8

9

Abdomen Length

Katydids

Grasshoppers

Simple Linear Classifier

If previously unseen instance above the line

then

class is Katydid

else

class is Grasshopper

Katydids

Grasshoppers

R.A. Fisher

1890-1962

10

1 2 3 4 5 6 7 8 9 10

1

2

3

4

5

6

7

8

9

Problemas

77

100

10 20 30 40 50 60 70 80 90 100

10

20

30

40

50

60

70

80

90

10

1 2 3 4 5 6 7 8 9 10

1 2 3 4 5 6 7 8 9

Nearest Neighbor Classifier

If the nearest instance to the

previously unseen instance is a

Katydid

class is Katydid

else

class is Grasshopper

Katydids

Grasshoppers

Joe Hodges

1922-2000

Evelyn Fix

1904-1965

An

ten

na

Le

ng

th

10

1 2 3 4 5 6 7 8 9 10

1

2

3

4

5

6

7

8

9

Abdomen Length

The nearest neighbor algorithm is sensitive to outliers…

The solution is to…

We can generalize the nearest neighbor

algorithm to the K- nearest neighbor (KNN)

algorithm. We measure the distance to the nearest K instances,

and let them vote. K is typically chosen to be an odd

number.

K = 1 K = 3

1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10

1

2

3

4

5

6

7

8

9

10

1 2 3 4 5 6 7 8 9 10 Suppose the following is true,

if an insects antenna is longer

than 5.5 it is a Katydid,

otherwise it is a Grasshopper.

Using just the antenna length

we get perfect classification!

The nearest neighbor algorithm is sensitive to irrelevant

features… Training data

1 2 3 4 5 6 7 8 9 10

1 2 3 4 5 6 7 8 9 10

6

5

Suppose however, we add

in an irrelevant feature, for

example the insects mass.

Using both the antenna

length and the insects mass

with the 1-NN algorithm we

get the wrong classification!

Algumas ferramentas

82

“Weka is a collection of machine learning

algorithms for data mining tasks”

http://www.cs.waikato.ac.nz/ml/weka/

“The Apache Mahout™ project's goal is to build a

scalable machine learning library. […]

Currently Mahout supports mainly three use cases:

[…]Recommendation, Classification and Clustering”

https://mahout.apache.org/

Data Mining software to bussiness

http://www.pentaho.com/

Referências Fayyad, Ussama; Piatetsky-Shapiro, Gregory; SMYTH,

Padhraic. From Data Mining to knowledge Discovery in Databases. AI Magazine, vol 17, nº3. AAAI, 1996.

Fayyad, Ussama. Data Mining and Knowledge Discovery in Databases: Implications for Scientific Databases. SSDM, 1997.

HAO, Yuan; CAMPANA, Bilson; KEOGH, Eamonn. Monitoring and Mining Insect Sounds in Visual Space. SDM 2012.

HAN, Jiawei; KAMBER, Micheline; PEI, Jian. Data Mining: Concepts and Techniques. 3ª ed. Elsevier, 2011.

KEOGH, Eamonn. Introduction to Data Mining. Apresentação. Data Mining Winter 2011.

KEOGH, Eamonn. A Gentle Introduction to Machine Learning and Data Mining for the Database Community

83

Obrigado!

84

Exercício 1- Resposta

Cite 2 padrões frequentes considerando o

banco de dados abaixo.

85

Transação 1 Pão, leite, queijo, presunto, desodorante, feijão

Transação 2 Achocolatado, pão, leite

Transação 3 Cebola, laranja, salsa, manga

Transação 4 Carne, presunto, ovos, queijo, pão

Transação 5 Chocolate, pipoca, refrigerante, leite

Transação 6 Caneta, bala, fralda, queijo, leite, pão

Exercício 1- Resposta

Compra (Cliente, Pão) => Compra (Cliente,

Leite) [suporte: 50% confiança: 75%]

Compra (Cliente, Queijo) => Compra

(Cliente, Presunto) [suporte: 33% confiança:

66%]

86

Exercício 2 - Respota

Possíveis respostas:

Agrupar usuários de acordo com o gênero

musical escolhido. Sugestões de bandas

similares podem ser feitas para o grupo.

Classificar as bandas de acordo com a

popularidade.

87

Documents

Apresentação do PowerPoint - ic.unicamp.brsantanch/teaching/db/2016-2/slides/Data_Mining... · O que é Data Mining? “Data mining is the process of discovering interesting patterns