Text of Algoritmo IPM2 Interaction Pattern Mining AULA 21 DATA MINING
Slide 1
Algoritmo IPM2 Interaction Pattern Mining AULA 21 DATA MINING
Slide 2
Problema de Minerao de Traos de Interao Dados Conjunto de traos de interao Um critrio de qualificao C= (comp-min, minsup, maxerror, minscore) Determinar todos os padres maximais p satisfazendo o critrio de qualificao C |p| comp-min Sup(p) minsup com relao a maxerror Score(p) minscore
Slide 3
Algoritmos IPM (Interaction Pattern Mining) Primeiro algoritmo desenvolvido (Mining System-User Interaction Traces for Use Case Models IWPC 2002) Padres no permitem erros de insero Tcnica Apriori IPM IPM (Recovering Software Requirements from System-user Interaction Traces SEKE 2002) Utiliza busca em largura Permite erros de insero IPM2 IPM2 (From Run-time behavior to Usage Scenarios: An Interaction- Pattern Mining Approach ACM SIGKDD 2002) Utiliza busca em profundidade Evita multiplas varridas no banco de dados, guardando as listas de localizaes (tcnica parecida com a do TreeMiner)
Slide 4
Algoritmo IPM2 Fases principais Pr-processamento Pr-processamento Elimina repeties Descoberta de padres (Minerao) Descoberta de padres (Minerao) Minera os padres sobre o banco de dados pr-processado que verificam o critrio de qualificao especificado pelo usurio Anlise dos padres minerados Anlise dos padres minerados Ajuste no critrio de qualificao para identificar padres de interao que realmente correspondem a requisitos funcionais do sistema legado. Quanto mais longos os traos de execuo e quanto mais estrito o critrio c mais provvel que os padres minerados correspondam a requisitos funcionais do sistema legado real. Um usurio com conhecimento do dominio da aplicao deve decidir quais dos padres minerados correspondem a funcionalidades do sistema legado.
Slide 5
Fase de Pr-processamento Um trao de interao normalmente contm repeties 4 5 6 6 6 6 6 6 6 6 7 Usurio acessou diversas vezes consecutivamente a tela 6 (por exemplo, no software de uma biblioteca, acessou diversas vezes a mesma instncia da tela de consulta do catlogo) Repeties podem impedir que certos padres interessantes sejam detectados 4 5 6 7 no suportado se o MaxError 4 Padro transformado em 4 5 (8) 6 7 Contador do identificador 6 armazenado em separado
Slide 6
Fase de Minerao Gerao do conjunto inicial de padres candidatos de tamanho 2 Padro candidato = satisfaz minsup e maxerror Gerados exaustivamente a partir do banco de dados Listas de localizao so produzidas Gerao de padres candidatos mais longos Junta-se padres de tamanho k com padres de tamanho 2 Gerao feita em profundidade no espao dos padres. Construo de lista de localizao associada a um padro candidato
Gerao do conjunto inicial de padres candidatos de tamanho 2 Input: Um alfabeto A, um critrio C= (c,sp,e,sc), um conjunto de sequncias S Output: Todos os padres candidatos de tamanho 2 (frequentes com relao a (sp, e). 1. Vec = vetor de tamanho |A| (cada posio i vai armazenar lista de padres comeando por i) 2. Para cada trao s em S 3. Para cada i = 1,..., (|s| - e 1) 4. Para j = i + 1,..., i + e + 1 5. Constri padro p = (s[i],s[j]) 6. Se p no est na lista de Vec(s[i]), 7. insere p nesta lista 8. Insere (s,i,j) na lista de localizaes de p 9. Para cada id A 10. Varre os padres de Vec[i] e elimina aqueles com lista de localizaes < sp
Gerao de padres 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 no-maximal} 7. Retorna Results
Slide 11
Gerao de padres candidatos mais longos {1,2}{2,3}{2,5}{3,5} Expand({1,2}) Expand({2,3}) Expand({2,5}) Expand({3,5}) Results1 Results2Results3 Results4 Resultados Elimina no maximais
Slide 12
p k Expand(p={p 1,p 2,...p k }) 1. ExtResults:= p k 2. Para cada padro {p k a} 3. Combina-se p com (p k,a) obtendo novo padro p3 4. Constri-se a lista de localizaes de p3 5. Se p3 frequente 6. TempResults:= Expand(p3) 7. ExtResults:= ExtResults U TempResults % testando se p maximal 8. Se sup(p) > sup(p3) % testando se p maximal 9. Se |p| comp-min e score(p) minscore 10. Insere p em ExtResults 11. Caso contrrio 12. Remove p de ExtResults 13. Se p3 no frequente 14. Se |p| comp-min e score(p) minscore 15. Insere p em ExtResults
Slide 13
Seja erro = k b 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) Ento : (i, startp1, endp2) Loc(P1 x P2) Construo de lista de localizao associada a um padro candidato
Slide 14
Entre as posies startp1 e endp2 no mximo podemos ter posies para os elementos de P1 e para um nmero de casas correspondente ao erro mximo... a1 an P1P2... b startp1 endp1= startp2 endp2 Seja erro = k b P1 = (a1,...,an) P2 = (an, b) P1 x P2 = (a1,...,an, b)
Slide 15
Exemplo s1 = 1 3 7 9 11 2 s2 = 2 1 7 9 8 11 4 2 ERRO = 2 P1 = (1, 1, 5) P2 = (1, 5, 6) 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( ) (2, 2, 6) (2, 6, 8) 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) no pertence a Loc ( )
Ps Minerao Identificao de funcionalidades nos padres minerados Ajuste dos critrios de qualificao novas execues de IPM2 Quanto mais longos forem os traos de interao e mais estrito o critrio de qualificao, maior a possibilidade dos padres minerados corresponderem a funcionalidades do sistema. Compactao: remoo de padres que so subpadres de outros (minerados) Necessidade de um usurio com conhecimento do domnio da aplicao para decidir quais dos padres minerados correspondem efetivamente a cenrios de uso, a funcionalidades da interface. A lista de localizao dos padres dentro dos traos de interao so analisadas a fim de se construir o modelo da funcionalidade correspondente ao padro minerado.
Slide 21
Estudo de caso realizado Sistema legado : LOCIS (Library of Congress Information System http://www.loc.govhttp://www.loc.gov 4 traos de interao com o mesmo usurio |s1| = 454, |s2| = 185, |s3| = 369, |s4| = 410 |A| = 26 (26 identificadores de telas) Critrio de qualificao (6, 9, 1, 7) Comp-min = 6, minsup = 9, maxerror = 1, minscore = 7
Slide 22
Referncias 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.Watch What I do: Programming by Demonstration Kapoor, R. Stroulia, E. : Simultaneous Legacy Interface Migration to Multiple Platforms. Proc. 9th Int. Conf. On Human-Computer Interaction., Vol. 1, 51-55, 2001.Simultaneous Legacy Interface Migration to Multiple Platforms
