MINERAÇÃO DE SEQUÊNCIAS RESTRITAS NO ESPAÇO E NO TEMPO

Abstract

Spatio-temporal patterns bring knowledge about time and position where they are present. Finding them is an important task for different domains. However, not all patterns are frequent over an entire dataset, they can occur constrained in space and time. Mining these patterns have as objective to discover the time range, and the set of spatial positions in which event sequences are frequent. This work proposes Generalized Spatial-Time Sequence Miner (G-STSM) algorithm as a solution for the discovery of frequent sequences that are constrained in space and time, bringing the formalization of the problem, definitions, proofs and algorithms As far as is known, after searching the related literature, G-STSM is the first approach able to find such sequences working with one dimension of time and three dimensions of space. G-STSM has been compared with an intuitive approach that searches for sequences of frequent events with very low support and groups its occurrences to find patterns constrained in space and time using known algorithms. A set of real world space-time seismic dataset was chosen to compare both approaches using classification metrics and resource usage records. As a result, G-STSM presented better computational performance with similar quality and it proved to be an efficient data mining tool for finding tight space-time sequences.

Os padrões espaço-temporais trazem conhecimento sobre o tempo e a posição onde eles estão presentes. Encontrá-los é uma tarefa importante para diferentes domínios. No entanto, nem todos os padrões são frequentes por todo um conjunto de dados, eles podem ocorrer restritos no espaço e no tempo. A mineração desses padrões tem como objetivo descobrir a faixa de tempo e o conjunto de posições espaciais em que as sequências de eventos são frequentes. Este trabalho propõe o algoritmo Generalized Spatial-Time Sequence Miner (G-STSM) como uma solução para a descoberta de sequências frequentes que são restritas no espaço e no tempo, trazendo a formalização do problema, definições, provas e algoritmos. Até onde se sabe, após busca na literatura relacionada, o G-STSM é a primeira abordagem capaz de encontrar tais sequências trabalhando com uma dimensão de tempo e três dimensões de espaço. O G-STSM foi comparado com uma abordagem intuitiva que busca sequências de eventos frequentes com suporte muito baixo e agrupa suas ocorrências para encontrar padrões restritos no espaço e no tempo usando algoritmos conhecidos. Foi escolhido um conjunto de dados sísmicos espaço-temporal do mundo real para comparar ambas as abordagens usando métricas de classificação e registro de uso de recursos. Como resultado, o G-STSM apresentou melhor desempenho computacional com qualidade semelhante mostrando-se uma ferramenta de mineração de dados eficiente para encontrar sequências restritas no espaço e no tempo.