29
Mineração de Dados Temporais Introdução Data Mining Sandra de Amo 03/07/22 1 Pós-graduação em Ciência da Computação - 2012

Mineração de Dados Temporais Introdução Data Mining Sandra de Amo 18/2/20141 Pós-graduação em Ciência da Computação - 2012

Embed Size (px)

Citation preview

Page 1: Mineração de Dados Temporais Introdução Data Mining Sandra de Amo 18/2/20141 Pós-graduação em Ciência da Computação - 2012

Mineração de Dados TemporaisIntrodução

Data Mining Sandra de Amo

11/04/23 1Pós-graduação em Ciência da Computação - 2012

Page 2: Mineração de Dados Temporais Introdução Data Mining Sandra de Amo 18/2/20141 Pós-graduação em Ciência da Computação - 2012

Apr 11, 2023 Escola de Verão - USP - São Carlos 2010 2

Mineração de Dados Temporais

Fator tempo é importante !

• {Leite, Manteiga} só é frequente nas compras feitas entre 7:00 e 9:00.

• A confiança da regra {Queijo Vinho} é alta nos finais de semana (comportamento cíclico).

• A confiança da regra de associação Escolaridade = Superior Partido = PT vem decaindo nos últimos 10 anos.

• Clientes que compram ipod frequentemente compram base para ipod depois de um mes da compra do ipod.

Page 3: Mineração de Dados Temporais Introdução Data Mining Sandra de Amo 18/2/20141 Pós-graduação em Ciência da Computação - 2012

Apr 11, 2023 Escola de Verão - USP - São Carlos 2010 3

Panorama Geral : Dados Simbólicos versus Séries Temporais

Dados simbólicos: elementos que evoluem no tempo são representados por símbolos.

– Artigos comprados por um cliente ao longo do tempo: ipod, rádio, computador, base de ipod,...

– Sintomas apresentados por um paciente ao longo do tratamento: febre, náusea, tontura,...

– Eventos de uma linha de montagem: troca de turnos de funcionário, falha na execução da tarefa, congestionamento da linha,...

Page 4: Mineração de Dados Temporais Introdução Data Mining Sandra de Amo 18/2/20141 Pós-graduação em Ciência da Computação - 2012

Apr 11, 2023 Escola de Verão - USP - São Carlos 2010 4

Panorama Geral : Dados Simbólicos versus Séries Temporais

Dados numéricos (séries temporais): – Cotações de uma determinada ação ao longo do

ano de 2009.– Temperaturas registradas numa determinada

região no século XX.– Indice pluviométrico de uma determinada região

do planeta na década de 90.– Colheita obtida (em toneladas) de um

determinado cereal, numa determinada região, na década de 2000 a 2009.

Page 5: Mineração de Dados Temporais Introdução Data Mining Sandra de Amo 18/2/20141 Pós-graduação em Ciência da Computação - 2012

Apr 11, 2023 Escola de Verão - USP - São Carlos 2010 5

Dados numéricos x Dados simbólicosS = (1, 4.5, 6, 2, 2.4, 7.1, 4, 2.4, 1, 4.8, 5.8, 1.8, 2.5, 7.2, 2, 2.4)

tempo

dado

1 2 3 4 5 6 87 9 10 11 12 13 14 15 16

Domínio dos valores dos dados é estruturado: totalmente ordenado

Page 6: Mineração de Dados Temporais Introdução Data Mining Sandra de Amo 18/2/20141 Pós-graduação em Ciência da Computação - 2012

Apr 11, 2023 Escola de Verão - USP - São Carlos 2010 6

Série temporal: representação gráfica

Permite utilizar técnicas de análise matemática e estatistica para detecção de formatos (shapes) especificos que se repetem com frequência ao longo do gráfico

Page 7: Mineração de Dados Temporais Introdução Data Mining Sandra de Amo 18/2/20141 Pós-graduação em Ciência da Computação - 2012

Problemas tratados neste curso : Mineração de Padrões Temporais

1. Mineração de Regras de Associação Temporais

2. Mineração de Dados Sequenciais (simbólicos)

3. Mineração de Séries Temporais

11/04/23 Pós-graduação em Ciência da Computação - 2012 7

Page 8: Mineração de Dados Temporais Introdução Data Mining Sandra de Amo 18/2/20141 Pós-graduação em Ciência da Computação - 2012

Um outro problema de Mineração Temporal = Classificação Temporal

Dado: um conjunto de sequências (amostras de treinamento) [ (a1,...,an), classe 1]

[ (b1,...,bn), classe 2]

.... [ (z1,...,zn), classe 1]

Objetivo: produzir um modelo de classificaçãosequência não classificada sequência classificada

Page 9: Mineração de Dados Temporais Introdução Data Mining Sandra de Amo 18/2/20141 Pós-graduação em Ciência da Computação - 2012

AplicaçõesAs principais aplicações: dados são sequências

numéricas ou sequências de vetores numéricos.• gestos

– sequência de imagens = sequência de vetores numéricos– Objetivo: classificar um gesto em uma determinada classe: gesto

de adeus, gesto de acolhida (“hello !”), gesto de dúvida, etc.• fala

– sequência de fonemas (sinais sonoros) – Objetivo: transcrever sequências de sinais sonoros em sua

representação escrita.• assinatura manual

– sequência de coordenadas de pontos (x,y) no plano desenhadas por usuários num dispositivo (tábua) digital.

– Objetivo: associar a uma dada assinatura manual um nome de usuário.

Page 10: Mineração de Dados Temporais Introdução Data Mining Sandra de Amo 18/2/20141 Pós-graduação em Ciência da Computação - 2012

11/04/23 Pós-graduação em Ciência da Computação - 2012 10

Problema de Mineração de Regras Temporais Cíclicas [Özden et al 1998]

• Base de dados = uma única sequência longa de itemsets D1, D2, …, Dn,…

Di = conjunto das compras realizadas por clientes no instante i (unidade de tempo = hora, dia, semana, mes, …)

– Clientes não são identificados

Page 11: Mineração de Dados Temporais Introdução Data Mining Sandra de Amo 18/2/20141 Pós-graduação em Ciência da Computação - 2012

Problema de Mineração de Regras Temporais Cíclicas

• Padrão Temporal : Regra de Associação Cíclica– Regra X Y, onde X e Y são itemsets– XY tem bom suporte e boa confiança em certos

instantes i que ocorrem periodicamente.

– Exemplo: café pão-com-manteiga • tem boa confiança entre 7 e 9 da manhã. • Padrão se repete a cada 24 horas.

11/04/23 Pós-graduação em Ciência da Computação - 2012 11

Page 12: Mineração de Dados Temporais Introdução Data Mining Sandra de Amo 18/2/20141 Pós-graduação em Ciência da Computação - 2012

11/04/23 Pós-graduação em Ciência da Computação - 2012 12

Exemplo1 2 3 4

{a,b}{a,c,b}{c,b,a,d}{c,a}{b,d}

Suporte mínimo = 40%Confiança minima = 50 %

{a,c,b}{d,c}{b,c,d}{c,b}{d,e}

{a,b}{a,c}{c,b,d}{d,b}{a,d,b}

Regra : a b

Suporte = 3/5Confiança = 3/4

Suporte = 1/5 Confiança = 100%

Suporte = 2/5 Confiança = 2/3

{a,c,e}{a,c}{a,e,c,d}{a,f,b}{b,d}

Suporte = 1/5 Confiança = 1/4

X X

Page 13: Mineração de Dados Temporais Introdução Data Mining Sandra de Amo 18/2/20141 Pós-graduação em Ciência da Computação - 2012

11/04/23 Pós-graduação em Ciência da Computação - 2012 13

Conceitos de Base• Ciclo = (p,m)

– p = período– m = offset = instante a partir do qual o padrão começa a se repetir

periodicamente, 0 ≤ m < p• Regra de Associação Cíclica

– (X Y, ciclo)– Medidas de Interesse : Suporte , Confiança

0 1 2 3 4 5 6 7 8

(3,0)(3,1) (3,2)

Como são os instantes i que fazem parte de um ciclo (p,m) ? i = m + kp, k = 0,1,…

isto é : m = i mod p

Page 14: Mineração de Dados Temporais Introdução Data Mining Sandra de Amo 18/2/20141 Pós-graduação em Ciência da Computação - 2012

11/04/23 Pós-graduação em Ciência da Computação - 2012 14

Formulação do ProblemaMineração de Regras de Associação Cíclicas

• Entrada– Uma sequência D0, ..., Dn-1

onde Di = conjunto de itemsets

– Lmin > 0 , Lmax > 0– α = nível mínimo de suporte – β = nível mínimo de confiança

• Saída: Todas as regras de associação cíclicas (r,(p,m)) tais que : – Lmin ≤ p ≤ Lmax– Para todo i = j.p, e m ≤ i ≤ n-1, tem-se que

• suporte(r) ≥ A e confiança(r) ≥ B em Di

Page 15: Mineração de Dados Temporais Introdução Data Mining Sandra de Amo 18/2/20141 Pós-graduação em Ciência da Computação - 2012

11/04/23 Pós-graduação em Ciência da Computação - 2012 15

Algoritmo Sequencial

• Fase 1: Encontra as regras Para cada instante i, aplica algoritmo Apriori

(ou outro mais eficiente) e encontra todas as regras de associação X Y com suporte e confiança acima dos limites mínimos, com relação ao banco de transações Di

Apriori é aplicado m vezes, onde m = comprimento da sequência D

Page 16: Mineração de Dados Temporais Introdução Data Mining Sandra de Amo 18/2/20141 Pós-graduação em Ciência da Computação - 2012

11/04/23 Pós-graduação em Ciência da Computação - 2012 16

Algoritmo Sequencial

• Armazenamento das regras em formato sequencialPara cada regra de associação r é associada uma sequência de bits de tamanho n

(0 0 1 0 1 0 1 0 0 0 1 1 ... 1) 0 na posição i = a regra r não é boa em Di 1 na posição i = a regra r é boa em Di

Page 17: Mineração de Dados Temporais Introdução Data Mining Sandra de Amo 18/2/20141 Pós-graduação em Ciência da Computação - 2012

11/04/23 Pós-graduação em Ciência da Computação - 2012 17

Algoritmo Sequencial • Fase 2: Detecta os ciclos

Para cada sequência de bits S = (s1,s2, ... , sn) – C := conjunto de todos os ciclos, ciclo = (p,m), Lmin ≤ p ≤ Lmax, 0 ≤ m < p

– Etapa 2.1 Para cada i = 0,...,nSe si = 0 : elimina de C todos os ciclos (p,m) Lmin ≤ p ≤ Lmax e m = i mod p

– Etapa 2.2 Se C é não vazio: elimina ciclos inúteis - - Para Lmin ≤ p ≤ Lmax

- Para k = 0, ..., p-1 Se (p,k) ∈ C : elimina de C todos os ciclos (p.j, m) tais que k = m mod p

Page 18: Mineração de Dados Temporais Introdução Data Mining Sandra de Amo 18/2/20141 Pós-graduação em Ciência da Computação - 2012

11/04/23 Pós-graduação em Ciência da Computação - 2012 18

Exemplo

0 1 2 3 4 5 6 7 8

Seja S = (1 1 0 1 1 1 0 1 1 0) Lmin = 1 , Lmax = 3

C = { (1,0), (2,0), (2,1), (3,0), (3,1), (3,2) }

9

Etapa 2.1 : Ciclos eliminados i = 2 : (1,0), (2,0),(3,2) i = 6 : (1,0), (2,0),(3,0) i = 9 : (1,0), (2,1), (3,0) No final da Etapa 2.1: C = {(3,1)}

Page 19: Mineração de Dados Temporais Introdução Data Mining Sandra de Amo 18/2/20141 Pós-graduação em Ciência da Computação - 2012

11/04/23 Pós-graduação em Ciência da Computação - 2012 19

Exemplo Sejam Lmin = 1, Lmax = 5• Final da Etapa 2.1 C = {(2,0), (2,1), (3,2), (4,3) }• Etapa 2.2:

Ciclo (2,0) : ciclos eliminados (2n,i) tal que n > 0 i ≡ 0 mod 2 Nada é eliminadoCiclo (2,1) : ciclos eliminados (2n,i) tal que n > 0, i ≡ 1 mod 2 É eliminado o ciclo (4,3)

0 1 2 3 4 5 6 7 8 9

Ciclo supérfluo

Page 20: Mineração de Dados Temporais Introdução Data Mining Sandra de Amo 18/2/20141 Pós-graduação em Ciência da Computação - 2012

11/04/23 Pós-graduação em Ciência da Computação - 2012 20

Considerações de Performance• Algoritmo Sequencial é factível quando o conjunto

das sequências representando as regras cabem na memória principal.

• Um outro algoritmo mais eficiente: Algoritmo Interleaved

Redução do tempo da fase do cálculo do suporte dos itemset Fase 1: Itemsets frequentes cíclicos são encontrados

Fase 2: Regras de Associação cíclicas são encontradas

Page 21: Mineração de Dados Temporais Introdução Data Mining Sandra de Amo 18/2/20141 Pós-graduação em Ciência da Computação - 2012

Propriedade Importante – FASE 2

Um ciclo da regra X Y é um múltiplo de um ciclo do itemset X U Y

Permite executar a geração das regras cíclicas a partir da detecção dos itemsets cíclicos

11/04/23 Pós-graduação em Ciência da Computação - 2012 21

Page 22: Mineração de Dados Temporais Introdução Data Mining Sandra de Amo 18/2/20141 Pós-graduação em Ciência da Computação - 2012

11/04/23 Pós-graduação em Ciência da Computação - 2012 22

Exemplo1 2 3 4

{a,b}{a,c,b}{c,b,a,d}{c,a}{b,d}

Suporte mínimo = 40%Confiança minima = 50 %

{a,c,b}{d,c}{b,c,d}{c,b}{d,e}

{a,b}{a,c}{c,b,d}{d,b}{a,d,b}

Regra : a b

Suporte = 3/5 Suporte = 1/5 Suporte = 2/5

{a,c,e}{a,c}{a,e,c,d}{a,f,b}{b,d}

Suporte = 1/5

X X

Page 23: Mineração de Dados Temporais Introdução Data Mining Sandra de Amo 18/2/20141 Pós-graduação em Ciência da Computação - 2012

Propriedades Importantes – FASE 1– “Pulo” de ciclos :

• Reduz o número de itemsets candidatos no cálculo do suporte em certos instantes.

– “Poda” de ciclos: • Reduz o escopo dos ciclos candidatos para um determinado

itemset baseado nos ciclos de seus subitemsets

– Eliminação de ciclos:• Reduz o escopo dos ciclos candidatos para um determinado

itemset baseado no fato de X não ser frequente em algum instante t

11/04/23 Pós-graduação em Ciência da Computação - 2012 23

Page 24: Mineração de Dados Temporais Introdução Data Mining Sandra de Amo 18/2/20141 Pós-graduação em Ciência da Computação - 2012

Propriedades Importantes – Fase 1

1. “Pulo” de ciclos : técnica que evita o cálculo do suporte de um itemset candidato X nos instantes que não são parte do ciclo do itemset X

Se o instante t não é parte de um ciclo do itemset X então X pode ser podado do conjunto de candidatos durante a fase da poda de Apriori executado no instante t.

2. Poda de ciclos : Se um itemset X tem um ciclo (p,m) então todos os seus subitemsets tem o ciclo (p,m).

Os ciclos de um itemset X são múltiplos de ciclos de seus subitemsets

11/04/23 Pós-graduação em Ciência da Computação - 2012 24

Page 25: Mineração de Dados Temporais Introdução Data Mining Sandra de Amo 18/2/20141 Pós-graduação em Ciência da Computação - 2012

Exemplo

1. Se (2,1) é o único ciclo de {A} Se (2,1) é o único ciclo de {B} Então os ciclos de {A,B} são (2,1) e seus múltiplos2. Se (2,1) é o único ciclo de {A} e (2,0) é o único ciclo de {B} então {A,B} não tem ciclo nenhum (propriedade da poda de ciclos) Logo, não há necessidade de calcular o suporte de {A,B} em

nenhum instante. (propriedade do pulo de ciclos)

11/04/23 Pós-graduação em Ciência da Computação - 2012 25

Page 26: Mineração de Dados Temporais Introdução Data Mining Sandra de Amo 18/2/20141 Pós-graduação em Ciência da Computação - 2012

Propriedades Importantes – Fase 1

3. Eliminação de Ciclos:Se num instante i , sup(X) < minsup então X não pode ter

nenhum ciclo (p,m), onde m = i mod p , Lmin ≤ p ≤ Lmax, 0 ≤ m < p

Exemplo: Suponha que Lmax = 3 e suponha que o itemset X não é frequente nos instances 0, 1, 2 e 3. Então X não tem nenhum ciclo. Assim, não há necessidade de calcular o suporte de X para t > 3.

11/04/23 Pós-graduação em Ciência da Computação - 2012 26

Page 27: Mineração de Dados Temporais Introdução Data Mining Sandra de Amo 18/2/20141 Pós-graduação em Ciência da Computação - 2012

Algoritmo Interleaved (Fase 1)K = 1 : todos os itemsets de tamanho 1 são gerados e seus ciclos detectados.K > 1 :

1. Gera candidatos (Apriori) juntamente com a lista de seus possíveis ciclos candidatos .(“poda ciclos”)

Ck = { (X,Ciclos(X)) | X k-itemset , Ciclos(X) = ciclos candidatos de X

2. Para cada instante t = 0, …, n-1 2.1 Poda candidatos : se o instante t não faz parte de Ciclo(X)

então candidato X é podado.(“pula ciclos”) 2.2 Poda candidatos (Apriori) 2.3 Cálculo do Suporte (Apriori) 2.4 Elimina ciclos: se sup(X) < minsup, elimina ciclos de Ciclos(X)

11/04/23 Pós-graduação em Ciência da Computação - 2012 27

Page 28: Mineração de Dados Temporais Introdução Data Mining Sandra de Amo 18/2/20141 Pós-graduação em Ciência da Computação - 2012

11/04/23 Pós-graduação em Ciência da Computação - 2012 28

Resultados Experimentais

Page 29: Mineração de Dados Temporais Introdução Data Mining Sandra de Amo 18/2/20141 Pós-graduação em Ciência da Computação - 2012

ReferênciaBanu Ozden Sridhar Ramaswamy Avi SilberschatzCyclic Association Rules. Proceeding ICDE '98 Proceedings of the

Fourteenth International Conference on Data Engineering

http://www.cse.ust.hk/~leichen/courses/comp630p/collection/reference-2-10.pdf