Mineração de Dados Temporais Introdução

  • View
    26

  • Download
    0

Embed Size (px)

DESCRIPTION

Mineração de Dados Temporais Introdução. Data Mining Sandra de Amo. Mineração de Dados Temporais. Fator tempo é importante ! {Leite, Manteiga} só é frequente nas compras feitas entre 7:00 e 9:00 . - PowerPoint PPT Presentation

Text of Mineração de Dados Temporais Introdução

  • Minerao de Dados TemporaisIntroduoData Mining Sandra de Amo **Ps-graduao em Cincia da Computao - 2012

    Ps-graduao em Cincia da Computao - 2012

  • *Escola de Vero - USP - So Carlos 2010*Minerao de Dados Temporais

    Fator tempo importante !

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

    A confiana da regra {Queijo Vinho} alta nos finais de semana (comportamento cclico).

    A confiana da regra de associao 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.

    Escola de Vero - USP - So Carlos 2010

  • *Escola de Vero - USP - So Carlos 2010*Panorama Geral : Dados Simblicos versus Sries TemporaisDados simblicos: elementos que evoluem no tempo so representados por smbolos.

    Artigos comprados por um cliente ao longo do tempo: ipod, rdio, computador, base de ipod,...

    Sintomas apresentados por um paciente ao longo do tratamento: febre, nusea, tontura,...

    Eventos de uma linha de montagem: troca de turnos de funcionrio, falha na execuo da tarefa, congestionamento da linha,...

    Escola de Vero - USP - So Carlos 2010

  • *Escola de Vero - USP - So Carlos 2010*Panorama Geral : Dados Simblicos versus Sries TemporaisDados numricos (sries temporais): Cotaes de uma determinada ao ao longo do ano de 2009.Temperaturas registradas numa determinada regio no sculo XX.Indice pluviomtrico de uma determinada regio do planeta na dcada de 90.Colheita obtida (em toneladas) de um determinado cereal, numa determinada regio, na dcada de 2000 a 2009.

    Escola de Vero - USP - So Carlos 2010

  • *Escola de Vero - USP - So Carlos 2010*Dados numricos x Dados simblicosS = (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) tempodado1234 5687910111213141516Domnio dos valores dos dados estruturado: totalmente ordenado

    Escola de Vero - USP - So Carlos 2010

  • *Escola de Vero - USP - So Carlos 2010*Srie temporal: representao grficaPermite utilizar tcnicas de anlise matemtica e estatistica para deteco de formatos (shapes) especificos que se repetem com frequncia ao longo do grfico

    Escola de Vero - USP - So Carlos 2010

  • Problemas tratados neste curso : Minerao de Padres TemporaisMinerao de Regras de Associao Temporais

    2. Minerao de Dados Sequenciais (simblicos)

    3. Minerao de Sries Temporais*Ps-graduao em Cincia da Computao - 2012*

    Ps-graduao em Cincia da Computao - 2012

  • Um outro problema de Minerao Temporal = Classificao Temporal Dado: um conjunto de sequncias (amostras de treinamento) [ (a1,...,an), classe 1] [ (b1,...,bn), classe 2] .... [ (z1,...,zn), classe 1]

    Objetivo: produzir um modelo de classificaosequncia no classificada sequncia classificada

  • AplicaesAs principais aplicaes: dados so sequncias numricas ou sequncias de vetores numricos.gestos sequncia de imagens = sequncia de vetores numricosObjetivo: classificar um gesto em uma determinada classe: gesto de adeus, gesto de acolhida (hello !), gesto de dvida, etc.falasequncia de fonemas (sinais sonoros) Objetivo: transcrever sequncias de sinais sonoros em sua representao escrita.assinatura manual sequncia de coordenadas de pontos (x,y) no plano desenhadas por usurios num dispositivo (tbua) digital.Objetivo: associar a uma dada assinatura manual um nome de usurio.

  • *Ps-graduao em Cincia da Computao - 2012*Problema de Minerao de Regras Temporais Cclicas [zden et al 1998]Base de dados = uma nica sequncia longa de itemsets D1, D2, , Dn,

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

    Clientes no so identificados

    Ps-graduao em Cincia da Computao - 2012

  • Problema de Minerao de Regras Temporais CclicasPadro Temporal : Regra de Associao CclicaRegra X Y, onde X e Y so itemsetsXY tem bom suporte e boa confiana em certos instantes i que ocorrem periodicamente.

    Exemplo: caf po-com-manteiga tem boa confiana entre 7 e 9 da manh. Padro se repete a cada 24 horas.

    *Ps-graduao em Cincia da Computao - 2012*

    Ps-graduao em Cincia da Computao - 2012

  • *Ps-graduao em Cincia da Computao - 2012*Exemplo1234{a,b}{a,c,b}{c,b,a,d}{c,a}{b,d} Suporte mnimo = 40%Confiana 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/5Confiana = 3/4Suporte = 1/5 Confiana = 100%Suporte = 2/5 Confiana = 2/3{a,c,e}{a,c}{a,e,c,d}{a,f,b}{b,d} Suporte = 1/5 Confiana = 1/4XX

    Ps-graduao em Cincia da Computao - 2012

  • *Ps-graduao em Cincia da Computao - 2012*Conceitos de BaseCiclo = (p,m)p = perodom = offset = instante a partir do qual o padro comea a se repetir periodicamente, 0 m < pRegra de Associao Cclica (X Y, ciclo)Medidas de Interesse : Suporte , Confiana

    012345678(3,0)(3,1)(3,2)Como so os instantes i que fazem parte de um ciclo (p,m) ? i = m + kp, k = 0,1, isto : m = i mod p

    Ps-graduao em Cincia da Computao - 2012

  • *Ps-graduao em Cincia da Computao - 2012*Formulao do ProblemaMinerao de Regras de Associao CclicasEntradaUma sequncia D0, ..., Dn-1 onde Di = conjunto de itemsetsLmin > 0 , Lmax > 0 = nvel mnimo de suporte = nvel mnimo de confiana

    Sada: Todas as regras de associao cclicas (r,(p,m)) tais que : Lmin p LmaxPara todo i = j.p, e m i n-1, tem-se que suporte(r) A e confiana(r) B em Di

    Ps-graduao em Cincia da Computao - 2012

  • *Ps-graduao em Cincia da Computao - 2012*Algoritmo Sequencial Fase 1: Encontra as regras Para cada instante i, aplica algoritmo Apriori (ou outro mais eficiente) e encontra todas as regras de associao X Y com suporte e confiana acima dos limites mnimos, com relao ao banco de transaes Di

    Apriori aplicado m vezes, onde m = comprimento da sequncia D

    Ps-graduao em Cincia da Computao - 2012

  • *Ps-graduao em Cincia da Computao - 2012*Algoritmo Sequencial Armazenamento das regras em formato sequencialPara cada regra de associao r associada uma sequncia de bits de tamanho n (0 0 1 0 1 0 1 0 0 0 1 1 ... 1) 0 na posio i = a regra r no boa em Di 1 na posio i = a regra r boa em Di

    Ps-graduao em Cincia da Computao - 2012

  • *Ps-graduao em Cincia da Computao - 2012*Algoritmo Sequencial Fase 2: Detecta os ciclosPara cada sequncia 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 no vazio: elimina ciclos inteis - - 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

    Ps-graduao em Cincia da Computao - 2012

  • *Ps-graduao em Cincia da Computao - 2012*Exemplo 012345678Seja 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) } 9Etapa 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)}

    Ps-graduao em Cincia da Computao - 2012

  • *Ps-graduao em Cincia da Computao - 2012*Exemplo Sejam Lmin = 1, Lmax = 5Final 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)

    0123456789Ciclo suprfluo

    Ps-graduao em Cincia da Computao - 2012

  • *Ps-graduao em Cincia da Computao - 2012*Consideraes de PerformanceAlgoritmo Sequencial factvel quando o conjunto das sequncias representando as regras cabem na memria principal.

    Um outro algoritmo mais eficiente: Algoritmo InterleavedReduo do tempo da fase do clculo do suporte dos itemset Fase 1: Itemsets frequentes cclicos so encontrados Fase 2: Regras de Associao cclicas so encontradas

    Ps-graduao em Cincia da Computao - 2012

  • Propriedade Importante FASE 2Um ciclo da regra X Y um mltiplo de um ciclo do itemset X U Y

    Permite executar a gerao das regras cclicas a partir da deteco dos itemsets cclicos

    *Ps-graduao em Cincia da Computao - 2012*

    Ps-graduao em Cincia da Computao - 2012

  • *Ps-graduao em Cincia da Computao - 2012*Exemplo1234{a,b}{a,c,b}{c,b,a,d}{c,a}{b,d} Suporte mnimo = 40%Confiana 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/5Suporte = 1/5 Suporte = 2/5 {a,c,e}{a,c}{a,e,c,d}{a,f,b}{b,d} Suporte = 1/5 XX

    Ps-graduao em Cincia da Computao - 2012

  • Propriedades Importantes FASE 1Pulo de ciclos :Reduz o nmero de itemsets candidatos no clculo do suporte em certos instantes.

    Poda de ciclos: Reduz o escopo dos ciclos candidatos para um determinado itemset baseado nos ciclos de seus subitemsets

    Eliminao de ciclos:Reduz o escopo dos ciclos candidatos para um determinado itemset baseado no fato de X no ser frequente em algum instante t

    *Ps-graduao em Cincia da Computao - 2012*

    Ps-graduao em Cincia da Computao - 2012

  • Propriedades Importantes Fase 1Pulo de ciclos : tcnica que evita o clculo do suporte de um itemset candidato X nos instantes que no so parte do ciclo do itemset XSe o instante t no parte de um ciclo do itemset X ento X pode ser podado do conjunto de candidatos durante a fase da poda de Apriori executado no instante t.

    Poda de ciclos : Se um ite