Algoritmo IPM2
Interaction Pattern Mining
AULA 21
DATA MINING
Problema de Mineração de Traços de
Interação

Dados


Conjunto de traços de interação
Um critério de qualificação
C= (comp-min, minsup, maxerror, minscore)

Determinar todos os padrões maximais p
satisfazendo o critério de qualificação C



|p| ≥ comp-min
Sup(p) ≥ minsup com relação a maxerror
Score(p) ≥ minscore
Algoritmos IPM
(Interaction Pattern Mining)


Primeiro algoritmo desenvolvido (Mining System-User Interaction
Traces for Use Case Models – IWPC 2002)

Padrões não permitem erros de inserção

Técnica Apriori
IPM (Recovering Software Requirements from System-user Interaction
Traces – SEKE 2002)



Utiliza busca em largura
Permite erros de inserção
IPM2 (From Run-time behavior to Usage Scenarios: An InteractionPattern Mining Approach – ACM SIGKDD 2002)


Utiliza busca em profundidade
Evita multiplas varridas no banco de dados, guardando as listas de
localizações (técnica parecida com a do TreeMiner)
Algoritmo IPM2 – Fases principais



Pré-processamento

Elimina repetições
Descoberta de padrões (Mineração)

Minera os padrões sobre o banco de dados pré-processado que
verificam o critério de qualificação especificado pelo usuário
Análise dos padrões minerados

Ajuste no critério de qualificação para identificar padrões de interação
que realmente correspondem a requisitos funcionais do sistema
legado.

Quanto mais longos os traços de execução e quanto mais estrito o
critério c mais provável que os padrões minerados correspondam a
requisitos funcionais do sistema legado real.

Um usuário com conhecimento do dominio da aplicação deve decidir
quais dos padrões minerados correspondem a funcionalidades do
sistema legado.
Fase de Pré-processamento

Um traço de interação normalmente contém repetições
 45666666667


Repetições podem impedir que certos padrões
interessantes sejam detectados


Usuário acessou diversas vezes consecutivamente a tela 6 (por
exemplo, no software de uma biblioteca, acessou diversas vezes
a mesma instância da tela de consulta do catálogo)
4 5 6 7 não é suportado se o MaxError ≤ 4
Padrão é transformado em 4 5 (8) 6 7
Contador do identificador 6 – armazenado
em separado
Fase de Mineração

Geração do conjunto inicial de padrões candidatos
de tamanho 2




Geração de padrões candidatos mais longos



Padrão candidato = satisfaz minsup e maxerror
Gerados exaustivamente a partir do banco de dados
Listas de localização são produzidas
Junta-se padrões de tamanho k com padrões de tamanho 2
Geração é feita em profundidade no espaço dos padrões.
Construção de lista de localização associada a um
padrão candidato
Geração do conjunto inicial de padrões
candidatos de tamanho 2
1
1 4 ; (s1,1,2)
1 5 ; (s1,1,3)
1 6 ; (s1,1,4)
2
3
4
4 5 ; (s1,2,3)
4 6 ; (s1,2,4)
4 3 ; (s1,2,5)
53
56
S1 = 1 4 5 6 3 3 4 5 6 8 1 9 11 23 34 56 32 32 23 35 56 49 32 4 5 3 6
S2 = 2 3 5 6 2 3 3 4 5 8 6 1 9 11 4 34 5 7 8 6 35 56 49 32 4 5 3 6
α=2
Geração do conjunto inicial de padrões
candidatos de tamanho 2
Input: Um alfabeto A, um critério C= (c,sp,e,sc), um conjunto de sequências S
Output: Todos os padrões candidatos de tamanho 2 (frequentes com relação a (sp, e).
1.
Vec = vetor de tamanho |A| (cada posição i vai armazenar lista de padrões
começando por i)
2.
Para cada traço s em S
3.
Para cada i = 1, ..., (|s| - e – 1)
4.
Para j = i + 1, ... , i + e + 1
5.
Constrói padrão p = (s[i],s[j])
6.
Se p não está na lista de Vec(s[i]),
7.
insere p nesta lista
8.
Insere (s,i,j) na lista de localizações de p
9.
Para cada id ε A
10.
Varre os padrões de Vec[i] e elimina aqueles com lista de localizações < sp
Exemplo



A = {1, 2, 3, 4}
S1 = 2 4 3 2 4, S2 = 1 2 4 2 3, S3 = 3 2 4 2 4
α = 2 , sp = 2
1
2
1 2 ; (2,1,2) (2,1,4) 2 4 ; (1,1,2)(1,4,5)
(2,2,3)
1 4 ; (2,1,3)
2 3 ; (1,1,3)(2,2,5)
2 2 ; (1,1,4) (2,2,4)
3
3 2 ; (1,3,4)
3 4 ; (1,3,5)
4
4 3 ; (1,2,3)
4 2 ; (1,2,4)
4 4 ; (1,2,5)
Geração de padrões candidatos mais
longos
Esquema geral
1. Results:= ɸ
2. Para cada id ɛ A
3.
Para cada p ɛ Vec(id)
4.
TempResults = Expand(p)
5.
Results:= Results U TempResults
6. Results:= Results – {p | p não-maximal}
7. Retorna Results
Geração de padrões candidatos mais
longos
{1,2}
Expand({1,2})
Results1
{2,3}
{2,5}
Expand({2,5})
Expand({2,3})
Results2
Results3
Elimina não maximais
Resultados
{3,5}
Expand({3,5})
Results4
Expand(p={p1,p2,...pk})
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
ExtResults:= ɸ
Para cada padrão {pk a}
Combina-se p com (pk,a) obtendo novo padrão p3
Constrói-se a lista de localizações de p3
Se p3 é frequente
TempResults:= Expand(p3)
ExtResults:= ExtResults U TempResults
Se sup(p) > sup(p3)
% testando se p é maximal
Se |p| ≥ comp-min e score(p) ≥ minscore
Insere p em ExtResults
Caso contrário
Remove p de ExtResults
Se p3 não é frequente
Se |p| ≥ comp-min e score(p) ≥ minscore
Insere p em ExtResults
Construção de lista de localização
associada a um padrão candidato
Seja erro = k
P1 = (a1,...,an) P2 = (an, b)
P1 x P2 = (a1,...,an, b)
(i, startp1, endp1) ɛ Loc(P1)
(j, startp2, endp2) ɛ Loc(P2)



i=j
endp1 = startp2
endp2 ≤ startp1 + erro + tamanho(P1)
Então : (i, startp1, endp2) ɛ Loc(P1 x P2)
Construção de lista de localização
associada a um padrão candidato
Seja erro = k
P1 = (a1,...,an) P2 = (an, b)
P1 x P2 = (a1,...,an, b)
P1
a1
startp1
...
P2
an ...
b
endp1= startp2
endp2
Entre as posições startp1 e endp2 no máximo
podemos ter posições para os elementos de P1 e
para um número de casas correspondente ao erro máximo
Exemplo
s1 = 1 3 7 9 11 2
s2 = 2 1 7 9 8 11 4 2
ERRO = 2
P1 = <1, 7, 11 > (1, 1, 5) (2, 2, 6)
P2 = < 11, 2 > (1, 5, 6) (2, 6, 8)
Testando se (1,1,5) pode ser
combinado com (1,5,6) para
produzir (1,1,6)
startp1+ |P1| + erro =
1 + 3 + 2 = 6 = endp2
Logo (1, 1, 6) pertence a
Loc(<1,7,11,2>)
Testando se (2,2,6) pode ser
combinado com (2,6,8) para
produzir (2,2,8)
startp1+ |P1| + erro = 2 + 3 + erro = 2 + 3
+ 2 = 7 < 8 = endp2
Logo (2, 2, 8) não pertence a
Loc (<1, 7, 11, 2> )
Exemplo
A = {1,2,3,4}, S = {s1,s2}. S1 = <1,3,2,3,4,3>, s2 = <2,3,2,4,1,3>, compmin= 3, minsup=2,
maxError = 1, minscore = 0
1
<1,2> (1,1,3)
<1,3> (1,1,2)
(2,4,6)
<1,3>
<3,4>
<3,2>,
<3,3>
<1,3,2> <1,3,3> <1,3,4>
(1,1,3) (1,1,4)
2
<2,1> (2,3,5)
<2,2> (2,1,3)
<2,3> (1,3,4) (2,1,2)
<2,4> (1,3,5) (2,3,4)
<2,3>
4
3
<3,2> (1,2,3) (2,2,3)
<4,3> (1,5,6)(2,4,6)
<3,3> (1,2,4) (1,4,6)
<4,1> (2,4,5)
<3,4> (1,4,5) (2,2,4)
<2,4>
<3,2>
Exemplo (Continuação)
<2,3>
<3,2>
<2,3,2>
(2,1,3)
<3,3>
(1,3,4) (2,1,2)
<3,4>
s1 = <1,3,2,3,4,3>
<2,3,3> <2,3,4>
(1,3,6) (1,3,5)
(2,1,4)
<4,3>
<2,3,4,3>
(1,3,6)
Densidade (<2,3,4>) = 0,86 score(<2,3,4>) = 1,36
s2 = <2,3,2,4,1,3>
Exemplo (Continuação)
<2,4>
(1,3,5) (2,3,4)
<4,3>
s1 = <1,3,2,3,4,3>
s2 = <2,3,2,4,1,3>
<2,4,3>
(1,3,6)
(2,3,6)
<3,2>
<3,3>
<2,4,3,2>
<2,4,3,3>
<3,4>
<2,4,3,4>
Exemplo (Continuação)
<3,2>
<2,3>
<3,2,3>
(1,2,4)
(1,2,3) (2,2,3)
<2,4>
s1 = <1,3,2,3,4,3>
<3,2,4>
(1,2,5)
(2,2,4)
<4,3>
s2 = <2,3,2,4,1,3>
<3,2,4,3>
(1,2,6)(2,2,6)
<3,2>
<3,2,4,3,2>
<3,3>
<3,2,4,3,3>
<3,4>
<3,2,4,3,4>
Densidade(<3,2,4,3>) = 0,80, score(<3,2,4,3>) = 1,60
Pós Mineração
Identificação de funcionalidades nos padrões minerados

Ajuste dos critérios de qualificação – novas execuções de IPM2
Quanto mais longos forem os traços de interação e mais estrito o critério de
qualificação, maior a possibilidade dos padrões minerados corresponderem a
funcionalidades do sistema.



Compactação: remoção de padrões que são subpadrões de outros (minerados)
Necessidade de um usuário com conhecimento do domínio da aplicação para
decidir quais dos padrões minerados correspondem efetivamente a cenários
de uso, a funcionalidades da interface.
A lista de localização dos padrões dentro dos traços de interação são
analisadas a fim de se construir o modelo da funcionalidade correspondente
ao padrão minerado.
Estudo de caso realizado
Sistema legado : LOCIS (Library of Congress
Information System http://www.loc.gov
 4 traços de interação com o mesmo usuário



|s1| = 454, |s2| = 185, |s3| = 369, |s4| = 410
|A| = 26
(26 identificadores de telas)
Critério de qualificação (6, 9, 1, 7)


Comp-min = 6, minsup = 9 ,
maxerror = 1, minscore = 7
Referências

M. El-Ramly, E. Stroulia, P. Sorenson:
From Run-time behavior to Usage Scenarios: An
Interaction-Pattern Mining Approach
ACM SIGKDD 2002.


Cypher, A. : Watch What I do: Programming by
Demonstration, MIT Press, Cambridge, MA, 1993.
Kapoor, R. Stroulia, E. : Simultaneous Legacy Interface
Migration to Multiple Platforms. Proc. 9th Int. Conf. On
Human-Computer Interaction., Vol. 1, 51-55, 2001.