Padrões Sequenciais
Aula 5
Sandra de Amo
11/5/2015
Mestrado em Ciência da Computação
2008
1
Padrões Estruturados: Porque ?
• Dados científicos não podem ser vistos
•
como simples itemsets
Dados científicos apresentam
estruturas mais complexas
– Hierarquias
– Propriedades geométricas
• Exemplos
– Moléculas – Estruturas das proteínas
– Controle de tráfico, workflow
– Documentos XML, Logs de navegação
na Web, Redes sociais.
11/5/2015
Mestrado em Ciência da Computação
2008
2
Padrões Estruturados : Sequências
• Base de dados = conjunto de sequências
– sequência de artigos comprados um cliente durante um
periodo de tempo.
– sequência de sintomas de um paciente durante um periodo de
tempo.
– sequência de ações para evacuar uma cidade em caso de
radiação atômica.
– sequência de páginas web visitadas por um internauta
– sequência de nucleotídeos (DNA)
• Padrão Sequencial
– Lista de items ou itemsets (artigos, sintomas) que
aparecem em diversas sequências de dados.
11/5/2015
Mestrado em Ciência da Computação
2008
3
Exemplo
1
2
{TV ,player} ,
{DVD}
{Computador}
3
{TV} , {player, DVD}
4
{player} , {Computador}
5
Padrão Sequencial
{Computador} ,
{Impressora}
< {TV}, {DVD} >
Sequência de itemsets
Padrão Sequencial =
Conjunto de items +
estrutura de ordem total (linear)
11/5/2015
4
Conceitos de Base
• Padrão Sequencial = < s1,… sn >
•
•
•
si = itemset = {a1,…,ak}
Seja S = < s1,… sm > uma sequência de
dados
P = padrão sequencial = < p1,… pn >
S contém P se :
S1 , … Si, … Sj, … , Su, … , Sm
p1,…, pl, …, pn
11/5/2015
5
Suporte de um padrão sequencial
• D : Base de Dados de Sequências,
• P = Padrão Sequencial
Suporte (P) =
Nb de sequências S em D tais que S contem P
Total de sequências em D
Tamanho de um padrão sequencial = nb de items do padrão
< {a,b}, {c,d}, {a,c} > tem 6 items = 6-padrão
11/5/2015
6
Exemplo
Base de Dados D
1
2
{TV Player} ,{DVD}
3
{Scanner} , {TV} , {Player, DVD}
{Computador}
4
5
{Player} , {Computador}
{Computador} , {Impressora}
Padrão P
Suporte(P) = 2/5 = 40%
< {TV} , {DVD} >
11/5/2015
7
Problema:
Mineração de Padrões Sequenciais
• Dados:
1. Uma base de dados de sequências
2. Um nível mínimo de suporte ,
1≥  > 0
• Encontrar todos os padrões
sequenciais frequentes em D com
respeito a .
11/5/2015
Mestrado em Ciência da Computação
2008
8
Algoritmos de Mineração de
Sequências
• Técnica Apriori – Busca em Largura
– Apriori-All [Agrawal - Srikant 1995]
– GSP [Agrawal – Srikant 1996]
• Classes d’Equivalência – Busca em
Profundidade
– SPADE [M. Zaki, 2001]
• Sem geração de candidatos
– PrefixSpan [Han+, 2001]
11/5/2015
Mestrado em Ciência da Computação
2008
9
Algoritmo GSP
Propriedade Importante: Antimonotonia
a
b
c
d
e
f
g
h
i
j
k
l
m
Frequente
Frequentes
11/5/2015
Mestrado em Ciência da Computação
2008
10
Propriedade da
Antimonotonia
• Se S = <s1, …, sn> é frequente
k = tamanho de S, então :
– S’ = S – primeiro item de s1 e
– S’’= S – último item de sn
S’ e S’’ são padrões frequentes de tamanho k-1.
11/5/2015
Mestrado em Ciência da Computação
2008
11
Como combinar dois padrões
sequenciais ?
a
b
c
d
e
f
g
h
i
b
c
d
e
f
g
h
i
j
Padrão Resultante
11/5/2015
Mestrado em Ciência da Computação
2008
12
GSP – Geração dos
candidatos
F3
< {1,2}, {3} >
< {1,2}, {4} >
< {1,3}, {5} >
< {2}, {3,4} >
< {1}, {3,4} >
< {2}, {3}, {5} >
< {1,2}, {3,4} >
< {1,2}, {3}, {5} >
11/5/2015
C4
Mestrado em Ciência da Computação
2008
13
GSP – Poda
F3
C4
11/5/2015
< {1,2}, {3} >
< {1,2}, {4} >
< {1,3}, {5} >
< {2}, {3,4} >
< {1}, {3,4} >
< {2}, {3}, {5} >
< {1,2}, {3,4} >
< {1,2}, {3}, {5} >
C4 =
Mestrado em Ciência da Computação
2008
< {1,2}, {3,4} >
14
GSP – Cálculo do Suporte
Suporte Mínimo: 50%
Candidatos
Cálculo do Suporte
Base de Dados
1 < {3,1,5,2}, {5}, {3,5,4} >
< {1,2}, {3,4} >
2 < {2}, {3,4} >
3 < {4,5}, {1,3,2}, {3,5,4,7} >
4 < {3}, {2,5} >
F4 =
11/5/2015
< {1,2}, {3,4} >
Mestrado em Ciência da Computação
2008
15
Algoritmo GSP [EDBT 1996]
Entrada : BD de sequências, 1 ≥ N ≥ 0
Saida : Todos os padrões frequentes na BD
C1 = Padrões sequenciais de tamanho 1
F1 = Padrões sequenciais frequentes de C1
k:=1
While Fk não vazio
Ck+1 := Combina(Fk, Fk)
Ck+1 := Poda(Ck, Fk)
Fk+1 : = Calcula-suporte(BD,Ck+1, N)
k : = k+1
11/5/2015
Mestrado em Ciência da Computação
2008
16
Exemplo completo simples
• Base de dados
suporte = 2/3
<{a,b}, {f}>
<{a}, {b}, {c}>
<{d}, {a,e}, {b} ,{e,c} >
C1 = <a> <b> <c> <d> <e> <f>
F1 = <a>, <b>, <c>
C2 = <{a},{a}> <{a,b}> <{a},{b}> {<{b},{a}>
<{b},{b}> <{a},{c}> <{c},{a}> <{a,c}> <{b,c}>
<{b},{c}>, <{c},{c}> , <{c},{b}>
F2 = <{a},{b}> <{a},{c}> <{b},{c}>
C3 = <{a},{b},{c}> F3 = <{a},{b},{c}>
C4 = vazio
11/5/2015
17
Referências
• Artigos:
Agrawal, R., Srikant, R. : Mining Sequential Patterns :
Generalizations and Performance Improvements. Proc. 5th EDBT, 317, 1996.
Agrawal, R., Srikant, R. : Mining Sequential Patterns. Proc. ICDE
1995, pages 1-14.
• Implementações:
Christian Borgelt's Webpages
http://www.borgelt.net//software.html
• Referências
PáginaSrikant http://www.rsrikant.com/publications.html#conf
Página Agrawal http://rakesh.agrawal-family.com/pubs.html/
11/5/2015
Mestrado em Ciência da Computação
2008
18