Mineração de Traços
de Execução
AULA 20
DATA MINING
Motivação

Evolução de um software




Como ?


Requisitos funcionais originais
Como ?


Correção de erros
Adaptações de seu funcionamento
Melhoria de suas funcionalidades
Documentação
Problemas



Inexistente
Confusa, ambigua
Desatualizada
Problema central


Entender as funcionalidades de um
software existente, cuja documentação é
inutilizável.
Exemplo

Adaptação das funcionalidades de um software
existente para operar em novas plataformas (ex.
Web)
Exemplo

Projeto CelLEST (University of Alberta – Canada)

Objetivo:


Desenvolver um método semi-automático para migrar para a
Web interfaces desenvolvidas originalmente para serem operadas
em plataformas tradicionais. Documentação das interfaces
originais não são utilizáveis.
Metodologia: as funcionalidades de uma interface podem
ser “descobertas” a partir do comportamento em tempo
real de seus usuários.
Arquitetura de CelLEST
S1 = i1 i2 i3 i4 ...
S2 = a1 a2 a3 a4 i1 i3 ...
S3 = b1 a2 a3 a4 i1 i3 ..
1a Fase: LeNDI
Modelo
especificando
uma
funcionalidade
Interface Legada
LeNDI: Legacy Navigation Domain Interface
Sequências de identificadores
de telas
P1 = i1 i3
P2 = a1 a2
..
2a Fase: Mineração de padrões
de interação com o usuário
Traços da Interação com o Usuário



Cada sequência = lista de identificadores de telas da
interface.
S = i1 i2 ... in
Transição entre duas telas =




Resulta de uma sequência de movimentos do cursor
Resulta de um conjunto de teclas “apertadas”
Padrão sequencial representa múltiplas execuções de
uma mesma tarefa.
Padrão sequencial corresponde a uma funcionalidade
da interface.
Tecnologia utilizada após a mineração

Transformando padrões de interação com o usuário em um
modelo de especificação de uma funcionalidade da interface

Enfoque “Programação por demonstração”


Transformando as especificações de funcionalidades numa
especificação declarativa da interface


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.
Nova interface = front-end da interface legada, para ser
utilizada em um ambiente multi-plataforma.
Mineração de Sequências: para
diferentes problemas, diferentes soluções


Mineração de Padrões Sequenciais em banco
de dados de sequências de transações: GSP,
Spade, PrefixSpan, Clospan.
Mineração de Episódios (Mannila-ToivonenVerkamo) em uma única sequência longa:
Winepi, Minepi, Seq-ready&Go
Mineração de Sequências: para
diferentes problemas, diferentes soluções

Mineração de Padrões em Bioinformáticacada padrão é uma expressão regular
(representando um conjunto de strings).

Exemplo de padrão




A.CG.
Representa o conjunto de strings
AACGA;AACGC;AACGT;AACGG;ACCGA;ACCGC;…
Ocorre duas vezes na sequência AACGCCTACCGT
Algoritmo de Mineração: Teiresias
Mineração de Sequências: para
diferentes problemas, diferentes soluções

Mineração de Traços de Interação em banco
de dados de sequências de identificadores de
telas


Exemplo de padrão 1 4 5
ocorre na sequência 3 5 1 3 4 8 9 5 6
com erro inferior a 3
Mineração de Traços de Interação com o
usuário: Conceitos principais


A = alfabeto de identificadores de telas da interface do
sistema legado.
Sequência



s = sequência de elementos de A = {a1, ..., an}.
Representa um traço de interação entre a interface do sistema legado e
um de seus usuários.
Episódio


e = subsequência (contigua) de uma sequência do banco de dados de
traços = pedaço de uma sequência
Exemplo :

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
Mineração de Traços de Interação com o
usuário: Conceitos principais


Padrão: sequência de identificadores
Um episódio e suporta um padrão p com erro máximo α




se p ocorre em e com no máximo α inserções erradas
p[1] = e[1] e p[n] = e[m], onde n= tamanho de p, m = tamanho de e
Os elementos de p aparecem em e na mesma ordem em que aparecem em p.
Exemplo
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
p = 23 56 32 ocorre no episódio 23 34 56 32 com no máximo 1 inserção errada.
p = 23 56 32 ocorre no episódio 23 35 56 49 32 com no máximo 2 inserções erradas.
Mineração de Traços de Interação com o
usuário: Conceitos principais

Suporte de um padrão p com relação a um limite α de erros

= número de episódios em um conjunto de sequências que
suportam p com um número máximo α de erros de inserção.
Exemplo
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


Suporte (4 5 6) = 5 para α = 1
Suporte (4 5 6) = 6 para α = 3
Mineração de Traços de Interação com o
usuário: Conceitos principais

Lista de localizações de um padrão p num
conjunto de sequências – com relação a um
limite α de inserções erradas.

Lista de triplas (seqnum, startLoc, endloc)



Seqnum = identificador da sequência onde p aparece
startLoc = início do episódio suportando p (α)
endLoc = fim do episódio suportando p (α)
Exemplo
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
P=456
α=3
Loclist(p) =
(s1, 2, 4), (s1, 7, 10), (s1, 24, 27), (s2, 8, 11), (s2, 15, 20), (s2, 25, 27)
Mineração de Traços de Interação com o
usuário: Conceitos principais

Densidade de um padrão p suportado por um conjunto de
episódios E = razão entre o tamanho de p e o tamanho médio
dos episódios de E.

Densidade(p) = |p| * suporte(p)
Σ
eɛE
|e|
Exemplo
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
P=456
1) α = 3
Suporte(p) = 6
|p| = 3
Tamanho médio dos episódios suportando p = 4
Densidade(p) = 3/4 = 0,75
2) α = 1
Tamanho médio dos episódios suportando p = 3,6
Densidade(p) = 3/3,6 = 0,83
Mineração de Traços de Interação com o
usuário: Conceitos principais

Padrão Maximal
P é maximal se todo padrão que o contiver tem suporte estritamente menor
do que P.
Exemplo
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
P = 5 6 é maximal
Repare que 4 5 6 contém P, mas seu suporte é menor.

P’ = 35 56 não é maximal
Suporte(35 56) = 2, mas Suporte(35 56 49) = 2

Mineração de Traços de Interação com o
usuário: Conceitos principais

Critérios de qualificação de um padrão p
(comp-minimo, MinSup, MaxError, MinScore)
 comp-minimo = comprimento minimo
 MinSup = suporte mínimo
 MaxError = número máximo de erros de inserção
 MinScore = score mínimo
score(p) = log |p| * log sup(p) * densidade(p)
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
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.