Generalização da Técnica
Levelwise para Mineração de
Padrões
Sandra de Amo
Definição dos Conceitos
relacionados à tarefa de mineração
•
Como são os padrões ?
– Itemsets, Sequências, Árvores, Grafos,...
•
Como são os elementos do Banco de Dados onde se vai descobrir padrões ?
– Estrutura compatível com a linguagem de padrões
•
Noções importantes relacionando padrões e elementos do banco de dados.
– Quando um elemento do banco de dados suporta um padrão ?
– Suporte(P) = porcentagem de elementos do banco de dados que suporta P
– Subpadrão: quando P’ é subpadrão de P ?
– Relação de Ordem Parcial no conjunto dos Padrões
P1 < P2 : P2 é mais específico do que P1.
- Padrão P2 imediatamente mais específico que P1
- P2 > P1
- Não existe P’ diferente de P2 e de P1 tal que P2 > P’ > P1
Formalização do Problema de
Mineração de Padrões
• Dados
– Um banco de dados BD
– Um limite minimo de suporte N
• Encontrar todos os padrões P com
suporte(P) >= N.
Técnica de Mineração (Levelwise)
Iteração k
• Fase da Geração
– Constrói Ck = todos os padrões imediatamente mais específicos
do que os padrões Fk
• Fase da Poda
– Remove de Ck padrões que contém um subpadrão
imediatamente menos específico e que não esteja em Fk
• Fase do Cálculo do Suporte
– Para cada elemento t do BD
• varre todos os padrões de Ck
• Incrementa o contador daqueles que são suportados por t.
Problema da Mineração de Episódios –
[Mannila et al 1997]
• Base de dados = uma única sequência longa de eventos (série
temporal simbólica)
– sequência de disparos de um alarme em um sistema de
telecomunicações.
– sequência de ações de um usuário sobre uma interface.
– sequência de crimes ocorridos em uma determinada região.
– sequência de doenças ocorridas em uma determinada região.
• Padrão = Episódio
– Um conjunto parcialmente ordenado de eventos.
Exemplo
DADO DE INPUT : uma única sequência longa de eventos
E
D
F
B
E A
C E
E
A
B
D
C E A
Padrão = episódio
A
C
B
E
Conceitos de Base
•
E = conjunto de tipos de eventos
Ex: {alarme A, alarme B, alarme C}
•
Evento = (A,t), onde A ϵ E, t = instante
•
Sequência de eventos = uma tripla (s, Ti, Tf) onde :
–
s = lista ordenada de eventos =
[(A1, t1), (A2, t2), ..., (A, tn) ] , Ti ≤ t1 < t2 < ... < tn < Tf
–
Ti = tempo inicial, Tf = tempo final
Ex: ( [ (A,1), (B,3), (C,5), (A,7) ], 1, 8 )
•
Episódio: tripla (V, ≤, g), onde
–
–
–
V = conjunto de vértices
≤ = relação de ordem parcial em V
g: V  E
Exemplo
DADO DE INPUT : uma única sequência longa de eventos
30
E
49
D
F
B
E A
C E
E
A
B
D
C E A
E
Representação formal = ([(E,30), (D,31), (F, 32), (B,33), (E,35),...., (E,48)], 30, 49)
A
C
B
Representação formal = ({1,2,3}, ≤, g)
1 ≤ 3, 2 ≤ 3
g(1) = A, g(2) = B, g(C) = 3
Como “medir” o interesse de um
episódio ?
•
Janela de uma sequência de eventos (s,Ti,Tf) = sequência de
eventos (w,ti,tf) onde :
– w = lista de pares (A,tn) de s onde ti ≤ t < tf
– ti < Tf , tf > Ti
•
Largura de uma janela (w,ti,tf) = |tf – ti|
•
Win(s,n) = conjunto de todas as janelas de s com largura n.
•
Número de janelas de Win(s,n) = Tf – Ti – n + 1
Exemplo
DADO DE INPUT : uma única sequência longa de eventos
30
E
49
D
F
B
E A
C E
E
A
B
D
C E A
Janela ([(B,33), (E,35), (A,36), (C,37)], 33, 38)
E
Medida de Interesse =
Suporte
•
Episódio E = (V, ≤, g) ocorre numa janela (w,ti,tf) onde
w = [(A1,t1), (A2,t2), ..., (An,tn)],
se existe uma função injetiva f: V  {1,...,n} tal que:
–
–
•
g(x) = Af(x) para todo x ϵ V
se x < y então tf(x) < tf(y)
Isto é: Os vértices de E são mapeados em eventos de w, de tal
modo que a ordem verificada entre os vértices em E corresponde
à ordem dos eventos mapeados.
Exemplo
DADO DE INPUT : uma única sequência longa de eventos
30
E
49
D
F
B
E A
w1
E
A
B
D
w2
Episódio ocorre em w1
A
C
B
C E
Episódio ocorre em w2
C E A
E
Medida de Interesse =
Suporte
• Dada uma sequência de eventos s
• Parâmetros : largura de janela = n,
suporte mínimo = α
• Episódio E
Suporte(E,s,n) = Tt de janelas onde E ocorre
Total de janelas
E é frequente se Suporte(E,s,n) > α
Exemplo
DADO DE INPUT : uma única sequência longa de eventos
30
E
49
D
F
B
E A
C E
E
w1
w2
B
D
C E A
E
w3
Largura da janela = 5
Suporte mínimo = 5%
A
episódio E
C
B
A
Total de janelas de tamanho 5 =
49 – 30 + 5 – 1 = 23
Suporte(E,s,5) = 3/23 = 0.11
Logo episódio E é frequente
Formulação do Problema:
Mineração de Episódios
Entrada: uma longa sequência de eventos
S,
N > 0, 0 ≤ M ≤ 1
Saída: todos os episódios com suporte ≥
M, com relação a janelas de largura N.