5.2.2 Análise de Complexidade
Como este algoritmo aplica a estratégia geração–e–teste de candidatos a sua complexidade é imposta pela estratégia de extração: a etapa de geração (considerando o pior caso, sem podas) possui a complexidade de KL, sendo K o número de itemsets frequentes e L o tamanho da maior sequencia extraída. A etapa de verificação vasculha a base de dados para contar as ocorrências de cada sequência candidata; desta forma, se N é o número de registros na base de dados, o MSTS verifica N × KL —pior caso. Assim a complexidade do MSTS é Θ(N × KL)
5.3 Algoritmo Incremental Miner of Stretchy Time Sequence
O algoritmo MSTS apresenta problema com relação ao desempenho em comparação com o GSP. Isso ocorre, pois o MSTS verifica um número maior de sequências de itemsets que o GSP durante o processo de contagem de ocorrências dos padrões. Além disso, bases de dados oriundas de medições em ambiente naturais têm como característica o incrementalismo. Assim sendo, estas bases sofrem periódicos incrementos de dados. Devida a esta característica, a Mineração de Dados Incremental (MDI) apresentou-se como uma boa alternativa para melhorar o desempenho do MSTS.
Entrada: Base de dados bd, minSup, µ, δ , padrões extraídos antes da evolução da base de dados pa, padrões semi-frequentes extraídos antes da evolução da base de dados psa
Saída: Conjunto de padrões C
1 C ← {itemsets ∈ bd} ;
2 C ← MST S(bd,minSup, µ,δ );
3 para cada padrão p ∈ paSpsahacer
4 se númeroDeOcorrências(p)|total de sequencias| ≥ minsup × δ então
5 se númeroDeOcorrencias(p)|total de sequencias| ≥ minsup então
6 C ← C + MST SModi f icado(p, base, minSup, µ, δ ) ;
7 senão
8 adicionaAosSemiFrequentes(p);
9 fim
10 fim
11 fin
Algoritmo 6: O Incremental Miner of Stretchy Time Sequences (IncMSTS). Este algoritmo implementa no MSTS a mineração de dados incremental.
O Algoritmo 6 apresentam o Incremental Miner of Stretchy Time Sequences (IncMSTS). Este algoritmo é o MSTS que aplica a MDI. O algoritmo recebe como entrada o incremento que a base sofreu, bd (ou a base toda se for a primeira vez que está sendo processada), o
5.3 Algoritmo Incremental Miner of Stretchy Time Sequence 59
valor de suporte mínimo minSup, o Valor de Espaçamento Máximo, µ, o valor do parâmetro δ (posteriormente explicado), os antigos padrões extraídos pela mineração anterior, pa, e os padrões semi-frequentes extraídos anteriormente, psa. A saída do algoritmo é o conjunto de padrões frequentes C.
O IncMSTS se baseia na estratégia de armazenamento dos padrões semi–frequentes do IncSpan (CHENG; YAN; HAN, 2004). Assim, o IncMSTS armazena os padrões semi–frequentes.
Um padrão é semi–frequente se seu valor de suporte estiver entre minSup e minSup × δ . Desta maneira, o parâmetro δ é utilizado para configurar o quão próximo de se tornar frequente um padrão deve ser para considerá-lo semi-frequente.
A escolha de um valor de δ pequeno, faz com que mais padrões sejam armazenados como semi–frequente. Isso acarreta uma queda de desempenho do algoritmo e maior uso de memória. Por outro lado, a escolha de um δ grande, faz com que poucos padrões sejam armazenados como semi-frequentes. Isso pode acarretar uma queda de precisão do algoritmo. O valor de δ está entre os valores zero e um (δ ∈ [0;1]).
O incremento que a base de dados recebeu, bd, consiste na continuação sequencial de uma série eventos de um determinado conjuntos de pontos (em dados espaço-temporais). Por exem- plo, no domínio de dados de sensores ambientais, são novas medições extraídas por sensores instalados em uma determinada região. Desta maneira, há uma variação na dimensão temporal dos dados espaço-temporais.
No Algoritmo 6, linha 01, o conjunto de padrões C recebe todos os itemsets frequentes que estão contidos no incremento que a base recebeu, bd. Na linha 02, o conjunto C recebe os resultados da MD aplicada ao incremento bd. A função MSTS é o Algoritmo 4 com uma modi- ficação: para não descartar, imediatamente, os padrões não frequentes gerados, mas verificar se são semi–frequentes (assim como é feito na linha 04 do Algoritmo 6) e, caso sejam, adicionar ao conjunto dos semi–frequentes.
Pela função MSTS, linha 02 do Algoritmo 6, são encontrados, também, os Padrões Corren- tes. Este tipo de padrão é definido como sendo padrões cujos valores de suporte são superiores a minSupse o incremento bd for considerado como a base completa, i.e., são padrões frequentes apenas no incremento bd. Esse padrões são relevantes, pois podem apresentar uma nova ten- dencia da base de dados. Tendencias estas que podem se confirmar com sucessivos incrementos de dados ou serem descartadas por não se provarem promissoras.
Da linha 03 a 11, a atualização das informações antigas (pa e psa) é feita. Se é a primeira vez que o algoritmo está minerando a base, esta informação não existe. Assim, esta parte
5.3 Algoritmo Incremental Miner of Stretchy Time Sequence 60
do algoritmo não é executada. O laço na linha 03 processa para cada padrão, p, contido nos conjuntos de padrões antigos paSpsa.
Na linha 04, verifica-se se o padrão p é semi–frequente (consequentemente, frequente) ou não frequente considerando a base completa (base original mais incrementos). A função n´umeroDeOcorr ˆencias retorna quantas vezes o padrão ocorreu na base de dados completa, uti- lizando a política de janelamento STW.
A verificação de frequencia do padrão p é feita pela função n ´umeroDeOcorr ˆencias, nova- mente, linha 05. Caso o padrão p seja semi-frequente, ele é inserido no conjunto dos semi– frequentes (linha 8). Caso o padrão p seja frequente, ele passará por uma etapa de generali- zação que visa encontrar padrões maiores cujo prefixo seja o padrão p (linha 6). Para isso é utilizada a função MST SModi f icado. Esta função é a parte de generalização do algoritmo MSTS. Na Subseção 5.3.1, um exemplo do funcionamento do algoritmo IncMSTS é apresentado. Na Subseção 5.3.2, é apresentada uma análise da complexidade algorítmica do IncMSTS.
5.3.1 Exemplo da Execução do Incremental Miner of Stretchy Time Sequen-
ces
Considere três estados da base de dados apresentados na Figura 5.3: Estado Inicial, Incre- mento 1 e Incremento 2. Considerando apenas o primeiro estado (Estado Inicial), considere também que o padrão p =< (A B)(D E) > seja frequente para qualquer µ ≥ 1, pois p apresenta um intervalo de tempo (o registro de tempo 2). Estabelecendo µ = 2 unidades de tempo como padrão e suporte mínimo para Estado Inicial é pelo menos uma ocorrência.
A linha Tempo, na Figura 5.3, consiste no momento no qual os eventos (itemsets) foram registrados (linha Tupla). Desta forma, no Tempo 1 foram registrados os eventos A e B; no Tempo 2, o evento C. Os incrementos de dados recebidos, Incremente 1 e 2 consistem em novos dados que foram adicionados a base original (Estado Inicial).
Para encontrar o padrão p′ =< (A B)(D E) F > em Estado Inicial, o algoritmo atua da mesma maneira que o MSTS, pois é a primeira vez que a base é processada. Como p′ ocorre uma vez no tempo {1,3,4}, p′é frequente.
Após o Incremento 1, o suporte mínimo se altera pela adição de novas sequências de item- sets, assim considere que para um padrão ser frequente, ele deve ocorrer ao menos duas vezes na base. Além disso, considere δ = 0.5; desta forma, um padrão é considerado semi-frequente se ocorrer métada das vezes que o mínimo necessária para ser frequente (deve acontecer pelo menos uma vez). O IncMSTS, ao processar o Incremento 1, marca a ocorrência do padrão p
5.3 Algoritmo Incremental Miner of Stretchy Time Sequence 61
Figura 5.3: Exemplo de extração de padrões de forma incremental pelo algoritmo IncMSTS.
nos registros de tempo {5,6}, sem intervalos de tempo. No entanto, o algoritmo não detectará a ocorrência do padrão p′. Desta maneira, o padrão p′ é rebaixado para padrão semi-frequente (pois ocorreu apenas uma vez) e o padrão p se mantem como padrão frequente.
Durante o processamento de Incremento 1, o IncMSTS encontra os padrões correntes pc1=< (A B)(D E) C > e pc2=< (A B)(D E) G >. Este padrões são considerados correntes, pois são frequentes apenas se considerar Incremento 1 como se fosse a base de dados completa. Deste forma, o suporte mínimo para um padrão corrente é a ocorrência de pelo menos uma vez.
Considere o Incremento 2 e que, após a inserções desses registros, o suporte mínimo se manteve o mesmo. Assim, IncMSTS encontra o padrão frequente p nos registros de tempo {9, 11} com um intervalo de tempo (registro 10). O IncMSTS encontra o padrão semi-frequente p′ nos registros de tempo {9,11,13} com dois intervalos de tempo (registros 10 e 12). Desta maneira, p′terá ocorrido duas vezes e é promovido para um padrão frequente. O padrão corrente pc2é encontrado nos registros {9,11,12} com um intervalo de tempo (registro 10). Com isso, pc2 é promovido para padrão frequente, pois ocorreu duas vezes (atingiu o suporte mínimo). O outro padrão corrente, pc1, não é encontrado em Incremento 2; desta forma, pc1 passa a ser considerado um padrão semi-frequente, pois ocorreu a metade do que é necessário para ser considerado frequente.
5.3.2 Análise da Complexidade
O algoritmo IncMSTS aprensenta a mesma complexidade que o MSTS. Porém, devido ao fato da atualização dos padrões já extraídos, o tamanho da base de dados a ser analisada é menor que a base de dados completa. O IncMSTS apresenta também a complexidade algorítmica da atualização dos padrões antigos: Θ(n × l), sendo n o tamanho do incremento de dados e l o tamanho do conjunto de dados antigos. Assim, o ganho em relação ao desempenho se deve ao