DISCOVERING MOTIFS RESTRICTED IN SPACE-TIME

Abstract

Many phenomena can be observed and organized as a sequence of observations on a timeline that can be modeled as a time series. A relevant area that is being explored in time series analysis is pattern discovery. Patterns are subsequences of time series related to some special properties or behaviors. A particular pattern that occurs a significant number of times in time series is called motif. Several important phenomena of a time series present different behaviors when observed at points in space (for example, series collected by sensors and IoT) and are best modeled as space-time series. Each time series is associated with a position in space. A space-time pattern is a sequence of events that are limited in space and time. Finding patterns that are frequent and restricted in space and time can allow us to understand how a phenomenon occurs. Several works have been developed to identify motifs in time series. However, studies that address spatiotemporal data techniques have not been identified. In this thesis, we compare different approaches to identifying motifs in time series with their main differences. We propose two methods for automatically identifying space-time restricted motifs in space-time series, the CSA and CSTMP. We experimentally compare the proposed methods with two other alternative methods: the Matrix Profile technique and the ensemble of the Matrix Profile and DBScan techniques. Our results show that CSA and CSTMP are innovative and obtain results that outperform the state-of-the-art techniques for time series and their adaptations for space-time series, being evaluated in two datasets.

Muitos fenômenos podem ser observados e organizados como uma sequência de observações em uma linha do tempo que pode ser modelada como uma série temporal. Uma área relevante que está sendo explorada na análise de séries temporais é a de descoberta de padrões. Padrões são subsequências de séries temporais relacionadas a algumas propriedades ou comportamentos especiais. Um padrão particular que ocorre um número significativo de vezes em séries temporais é denominado motif. Vários fenômenos importantes de uma série temporal apresentam comportamentos diferentes quando observados em pontos do espaço (por exemplo, séries coletadas por sensores e IoT) e são melhor modelados como séries espaço-temporais, em que cada série temporal é associada a uma posição no espaço. Um padrão espaço-temporal é uma sequência de eventos que são limitados no espaço e no tempo. Encontrar padrões que são frequentes e restritos em um espaço e tempo pode nos permitir compreender como um fenômeno ocorre. Diversos trabalhos foram desenvolvidos com o objetivo de identificar motifs em séries temporais, entretanto não foram identificados trabalhos que abordassem técnicas para dados espaço-temporais. Nesta tese comparamos diferentes abordagens de identificação de motifs em séries temporais com suas principais diferenças. Propomos dois métodos para a identificação automática de motifs restritos no espaço-tempo em séries espaço-temporais, o CSA e o CSTMP. Comparamos experimentalmente os métodos propostos com dois outros métodos alternativos: a técnica Matrix Profile e a combinação da técnica Matrix Profile e DBScan. Nossos resultados mostram que CSA e o CSTMP são inovadores e obtém resultados superiores as técnicas estado da arte para séries temporais e suas adaptações para séries espaço-temporais, sendo avaliados em dois datasets.