SEQUENCE MINING IN SPATIAL-TIME SERIES

Abstract

The problem of discovering sequential patterns in large datasets affects a wide range of scientific and industrial applications. In a growing number of applications, data are collected as spatio-temporal sequences that associate to each item in the sequence a time and a spatial position. This leads to an appealing new challenge for this domain: find, with the same process: i) frequent sequences constrained in space and time that may not be frequent in the entire dataset and ii) the time interval and space range where these sequences are frequent. The discovery of such patterns along with their constraints may lead to extract important knowledge that can remain hidden using traditional methods since their support is extremely low over the entire dataset. We introduce a new Spatio-Temporal Sequence Miner (STSM) algorithm for such purpose. STSM is based on our novel sequential pattern mining principle in order to detect spatial ranges where sequences are frequent. Next, it composes all detected sequences inside each range to discover the ones constrained in space and time where these sequences are frequent. Even though our solution is generic, we evaluate STSM on a seismic use case and illustrate its ability to detect frequent sequences constrained in space and time. We managed to identify 1,500 constrained sequences under high support threshold, which would not have been found using current techniques. Moreover, the identified sequences from STSM correspond to candidate areas for seismic horizons and bright spots that are of high value for domain experts. To the best of our knowledge, this is the first solution to tackle the problem of identifying frequent sequences constrained in space and time.

O problema da descoberta de padr˜oes sequenciais em grandes conjuntos de dados envolve uma ampla gama de aplicac¸ ˜oes cient´ıficas e industriais. Em um n´umero crescente de aplicac¸ ˜oes, os dados s˜ao coletados como sequˆencias espac¸o-temporais onde cada item na sequˆencia ´e associado a um tempo e a uma posic¸ ˜ao espacial. Isso leva a um novo e fascinante desafio para este dom´ınio: encontrar, com o mesmo processo: i) sequˆencias frequentes restritas no espac¸o e no tempo que podem n˜ao ser frequentes em todo o conjunto de dados e ii) o intervalo de tempo e espac¸o onde essas sequˆencias s˜ao frequentes. A descoberta de tais padr˜oes junto com suas restric¸ ˜oes pode levar a extrair conhecimento importante que pode permanecer escondido usando os m´etodos tradicionais, pois seu suporte ´e extremamente baixo no inteiro conjunto de dados. Apresentamos o novo algoritmo Spatio-Temporal Sequence Miner (STSM) para esse fim. O STSM ´e baseado em nosso novo princ´ıpio de minerac¸ ˜ao de padr˜oes sequenciais a fim de detectar intervalos espaciais onde as sequˆencias s˜ao frequentes. Em seguida, ele comp˜oe todas as sequˆencias detectadas dentro de cada intervalo para descobrir aqueles restritos no espac¸o e no tempo em que essas sequˆencias s˜ao frequentes. Apesar de nossa soluc¸ ˜ao ser gen´ erica, avaliamos o STSM em um caso de uso s´ısmico e ilustramos sua capacidade de detectar sequˆencias frequentes restritas no espac¸o e no tempo. Conseguimos identificar 1.500 sequˆencias restritas com alto limite de suporte, as quais n˜ao teriam sido encontradas usando as t ´ecnicas atuais. Al ´em disso, as sequˆencias identificadas pelo STSM correspondem na sismica a ´areas candidatas a horizons e a bright-spots que s˜ao de grande interesse para os especialistas nesse dom´ınio. Tanto quanto ´e do nosso conhecimento, esta ´e a primeira soluc¸ ˜ao para enfrentar o problema da identificac¸ ˜ao de sequˆencias frequentes restritas no espac¸o e no tempo.