PrefixSpan e GSP
Correção – Completude –
Performance – Escalabilidade
Propriedades de um algoritmo
Seja A um algoritmo que tem como objetivo
calcular um conjunto de objetos F
F = conjunto de todos os objetos satisfazendo um
determinada propriedade P.
Exemplos
1. Algoritmo que retorna todos os números
primos aparecendo num conjunto input N.
2. Algoritmo Apriori que retorna todos os itemsets
frequentes aparecendo num banco de
transações D
Propriedades de um algoritmo
Corretude : Todo output de A satisfaz a
propriedade P que caracteriza os
elementos de F ?
Completude: Para todo objeto O de F
existe uma execução de A que retorna O ?
Como mostrar que GSP é correto ?
Seja s = (I1, I2, ..., In) um padrão
sequencial retornado por GSP.
S é frequente ?
Prova : Os padrões retornados por GSP são
testados na fase do cálculo du suporte
que garante que o padrão retornado é
frequente.
Como mostrar que PrefixSpan é
correto ?
Seja s um padrão sequencial retornado por PrefixSpan
Pergunta: s é frequente com relação ao banco de dados de
sequências D original dado como input ?
Prova:






s é retornado por PrefixSpan como sendo frequente em relação a um
banco de dados projetado D|σ
Neste caso σ é prefixo de s
s é suportado por pelo menos N sequências no banco projetado D|σ
Estas N sequências projetadas são subsequências de sequências do
banco de dados original D.
Logo s é suportado por pelo menos N sequências do banco de dados
original D.
Portanto, s é frequente com relação a D.
Como mostrar que GSP é completo
?
Seja S um padrão sequencial frequente de tamanho k
S é retornado por GSP ?
Prova: por indução sobre k


Base da indução k = 1 : se S é frequente de tamanho 1 então S é
retornado na primeira iteração de GSP.
Hipótese de indução : suponhamos que todos os padrões frequentes de
tamanho inferior a k são retornados por GSP.
Como S = (s1,....,sn) é frequente, então
s’ = S – (primeiro item do primeiro itemset)
s’’ = S – (último item do último itemset)
São padrões frequentes de tamanho k-1.
Por hipótese de indução, s’ e s’’ são retornados por GSP. Neste caso, s’ e s’’
são retornados na iteração k-1
Portanto, S será gerado na iteração k de GSP, ao se juntar s’ e s’’ obtidos na
iteração precedente.
Como S é frequente, S será “aprovado” na fase do cálculo do suporte, e
portanto será retornado por GSP.
Como mostrar que PrefixSpan é
completo ?
Seja S = (s1,...,sn) um padrão sequencial frequente de tamanho k
S é retornado por PrefixSpan ?
Prova: por indução sobre k

Base da indução k = 1 : se S é frequente de tamanho 1 então S é
retornado na primeira iteração de PrefixSpan

Hipótese de indução : suponhamos que todos os padrões frequentes de
tamanho inferior a k são retornados por PrefixSpan
Seja b = último item do último itemset de S
S=α.b
α’ é frequente de tamanho k-1
Por hipótese de indução, α é retornado por PrefixSpan.
O banco projetado D| α será considerado em seguida.
S é frequente em D, logo é frequente em D| α
Portanto b é frequente em D| α
Portanto S será obtido expandido-se α com o b e será retornado ao final da
etapa D| α
Performance
Pontos positivos de PrefixSpan




Não existe fase de geração de candidatos
Padrões são estendidos com o acrescimo de um item
frequente obtido varrendo-se o banco projetado
No caso de GSP, os candidatos são gerados sem
levar em conta o banco de dados. Somente após a
geração, durante o teste do suporte, o banco de
dados é levado em conta.
Os bancos de dados que são varridos são os
projetados, que diminuem a cada etapa.
Pontos negativos de PrefixSpan

Construção dos bancos projetados
Estudos comparativos – GSP e
PrefixSpan
PC AMD 750MHz, 512 Mb Ram,
plataforma Windows 2000, Visual C++ 6.0
Suporte = 1%
PrefixSpan : 6,8 seg
GSP : 772,82 seg
SPADE: 20 seg
Suporte entre 0.5 e 0.75% : PrefixSpan é
2 a 3 vezes mais perfomante que GSP e
Spade.
Performance DB- C10T8S8I8
10k Clients – 8 items per itemset – 8 itemsets per client (avg).
Average pattern: 4 itemsets, 8 items per itemset
Aplicação: Mineração de
padrões de navegação na Web
(Web Mining)
O que faz ?
Extrai padrões que representam comportamento de
navegação na web.
Para que ?
Melhorar a arquitetura de um site
Distribuir material publicitário no site de forma optimal
Web Mining
Dados:


Arquivo de logs de navegação
Log = sequência de páginas visitadas
u1
u2
u3
IdUser (IP)
p1
p2
p3
t1
t2
t3
Página
< p1, p2, p3, ... >
Tempo
Exemplo – um arquivo de logs
Mineração de Sequências de
Sessões
• Dados: Web click-streams
(sequências de clicks)
• Para cada usuário é associada uma sessão
• Uma sessão = sequência de páginas visitadas
(tempo inicial – tempo final)
Dados: conjunto de sessões
Sessões  sequência de páginas
Páginas  items
Sequências de Páginas Web
Visitadas = Uma sessão
A
1
B
2
3
D
12
O
6
5
C
13
E
U
15
V
11
7
4
14
G
8
10
9
H
W
< A B C D C B E G HG W A O U O V >
Transformação de uma Sessão
Uma sessão
Conjunto de Sequências Maximais
<ABCD> <AB EGH> <ABEGW> <AOU > <AOV >
Arquivo de Logs
Sequências Maximais
Intelligent Miner – Janela
Principal
Mineração
Resultados da Mineração
Referências
Artigos:
J. Han, J. Pei, B. Mortazavi-Asl, H. Pinto, U. Dayal: Mining Sequential
Patterns by Pattern-Grouwth: The Prefix-Span Approach. IEEE
Transactions on Knowledge and Data Engineering, Vol. 16, n. 11,
2004.
M.S. Chen, J. S. Park, P.S. Yu : Efficient Data Mining for Path
Traversal Patterns. IEEE Transactions on Knowledge Discovery and
Data Engineering 10(2), 209-221, Mars 1998.
/