PrefixSpan e GSP Correção – Completude – Performance – Escalabilidade

  • View
    103

  • Download
    1

Embed Size (px)

Text of PrefixSpan e GSP Correção – Completude – Performance – Escalabilidade

  • Slide 1
  • PrefixSpan e GSP Correo Completude Performance Escalabilidade
  • Slide 2
  • 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 nmeros primos aparecendo num conjunto input N. 2.Algoritmo Apriori que retorna todos os itemsets frequentes aparecendo num banco de transaes D
  • Slide 3
  • 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 execuo de A que retorna O ?
  • Slide 4
  • Como mostrar que GSP correto ? Seja s = (I1, I2,..., In) um padro sequencial retornado por GSP. S frequente ? Prova : Os padres retornados por GSP so testados na fase do clculo du suporte que garante que o padro retornado frequente.
  • Slide 5
  • Como mostrar que PrefixSpan correto ? Seja s um padro sequencial retornado por PrefixSpan Pergunta: s frequente com relao ao banco de dados de sequncias D original dado como input ? Prova: s retornado por PrefixSpan como sendo frequente em relao a um banco de dados projetado D| s retornado por PrefixSpan como sendo frequente em relao a um banco de dados projetado D| Neste caso prefixo de s Neste caso prefixo de s s suportado por pelo menos N sequncias no banco projetado D| s suportado por pelo menos N sequncias no banco projetado D| Estas N sequncias projetadas so subsequncias de sequncias do banco de dados original D. Estas N sequncias projetadas so subsequncias de sequncias do banco de dados original D. Logo s suportado por pelo menos N sequncias do banco de dados original D. Logo s suportado por pelo menos N sequncias do banco de dados original D. Portanto, s frequente com relao a D. Portanto, s frequente com relao a D.
  • Slide 6
  • Como mostrar que GSP completo ? Seja S um padro sequencial frequente de tamanho k S retornado por GSP ? Prova: por induo sobre k Base da induo k = 1 : se S frequente de tamanho 1 ento S retornado na primeira iterao de GSP. Base da induo k = 1 : se S frequente de tamanho 1 ento S retornado na primeira iterao de GSP. Hiptese de induo : suponhamos que todos os padres frequentes de tamanho inferior a k so retornados por GSP. Hiptese de induo : suponhamos que todos os padres frequentes de tamanho inferior a k so retornados por GSP. Como S = (s1,....,sn) frequente, ento Como S = (s1,....,sn) frequente, ento s = S (primeiro item do primeiro itemset) s = S (ltimo item do ltimo itemset) So padres frequentes de tamanho k-1. Por hiptese de induo, s e s so retornados por GSP. Neste caso, s e s so retornados na iterao k-1 Portanto, S ser gerado na iterao k de GSP, ao se juntar s e s obtidos na iterao precedente. Como S frequente, S ser aprovado na fase do clculo do suporte, e portanto ser retornado por GSP.
  • Slide 7
  • Como mostrar que PrefixSpan completo ? Seja S = (s1,...,sn) um padro sequencial frequente de tamanho k S retornado por PrefixSpan ? Prova: por induo sobre k Base da induo k = 1 : se S frequente de tamanho 1 ento S retornado na primeira iterao de PrefixSpan Base da induo k = 1 : se S frequente de tamanho 1 ento S retornado na primeira iterao de PrefixSpan Hiptese de induo : suponhamos que todos os padres frequentes de tamanho inferior a k so retornados por PrefixSpan Hiptese de induo : suponhamos que todos os padres frequentes de tamanho inferior a k so retornados por PrefixSpan Seja b = ltimo item do ltimo itemset de S S = . b frequente de tamanho k-1 Por hiptese de induo, 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|
  • Slide 8
  • Performance Pontos positivos de PrefixSpan No existe fase de gerao de candidatos No existe fase de gerao de candidatos Padres so estendidos com o acrescimo de um item frequente obtido varrendo-se o banco projetado Padres so estendidos com o acrescimo de um item frequente obtido varrendo-se o banco projetado No caso de GSP, os candidatos so gerados sem levar em conta o banco de dados. Somente aps a gerao, durante o teste do suporte, o banco de dados levado em conta. No caso de GSP, os candidatos so gerados sem levar em conta o banco de dados. Somente aps a gerao, durante o teste do suporte, o banco de dados levado em conta. Os bancos de dados que so varridos so os projetados, que diminuem a cada etapa. Os bancos de dados que so varridos so os projetados, que diminuem a cada etapa. Pontos negativos de PrefixSpan Construo dos bancos projetados Construo dos bancos projetados
  • Slide 9
  • Estudos comparativos GSP e PrefixSpan PC AMD 750MHz, 512 Mb Ram, plataforma Windows 2000, Visual C++ 6.0 Suporte = 1% PrefixSpan : 6,8 seg PrefixSpan : 6,8 seg GSP : 772,82 seg GSP : 772,82 seg SPADE: 20 seg SPADE: 20 seg Suporte entre 0.5 e 0.75% : PrefixSpan 2 a 3 vezes mais perfomante que GSP e Spade.
  • Slide 10
  • Performance DB- C10T8S8I8 10k Clients 8 items per itemset 8 itemsets per client (avg). Average pattern Average pattern: 4 itemsets, 8 items per itemset
  • Slide 11
  • Aplicao: Minerao de padres de navegao na Web (Web Mining) O que faz ? Extrai padres que representam comportamento de navegao na web. Para que ? Melhorar a arquitetura de um site Distribuir material publicitrio no site de forma optimal
  • Slide 12
  • Web Mining Dados: Arquivo de logs de navegao Arquivo de logs de navegao Log = sequncia de pginas visitadas Log = sequncia de pginas visitadas u 1 p 1 t 1 u 2 p 2 t 2 u 3 p 3 t 3 IdUser (IP) Pgina Tempo
  • Slide 13
  • Exemplo um arquivo de logs
  • Slide 14
  • Minerao de Sequncias de Sesses Dados: Web click-streams (sequncias de clicks) sessoPara cada usurio associada uma sesso sessoUma sesso = sequncia de pginas visitadas (tempo inicial tempo final) Dados: conjunto de sesses Sesses sequncia de pginas Pginas items
  • Slide 15
  • Sequncias de Pginas Web Visitadas = Uma sesso BO A C D E G HW UV 1 2 4 3 5 6 7 8 9 10 11 12 13 14 15 < ABCD EB C GWHA G O UOV >
  • Slide 16
  • Transformao de uma Sesso Maximais Conjunto de Sequncias Maximais Arquivo de Logs Sequncias Maximais Uma sesso
  • Slide 17
  • Intelligent Miner Janela Principal
  • Slide 18
  • Minerao
  • Slide 19
  • Resultados da Minerao
  • Slide 20
  • Referncias 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.. /