Please use this identifier to cite or link to this item:
http://hdl.handle.net/1843/67719
Type: | Dissertação |
Title: | SAXJS: SAX based online change point detection |
Authors: | Giovanna Ávila Riqueti |
First Advisor: | Heitor Soares Ramos Filho |
First Co-advisor: | Felipe Domingos da Cunha |
First Referee: | João Batista Borges Neto |
Second Referee: | Marcelo Azevedo Costa |
Third Referee: | Frederico Gadelha Guimarães |
Abstract: | Time series are chronologically organized representations over time used to describe the dynamics of a given system. The behavior of this system can manifest variations over time, and the points in time where these variations occur are called change points. Detecting these change points is an important task with several relevant applications for the current world, such as monitoring climate change, investigating medical issues, understanding brainwaves, sleep patterns, and enhancing image classification as a pre-processing step. Despite being an area explored in the literature for decades, the change point detection field still has some challenges. Notably, there are demands for online algorithms capable of operating without the entirety of time series information, and algorithms that demonstrate adaptability across diverse systems. In this work, we propose a novel framework to solve these challenges. This framework is based on Symbolic Aggregate ApproXimation (SAX) transformation, Bag-of-Patterns (BOP) symbology, the probability of transition between symbols, and the Jensen-Shannon distance. We evaluate our framework with synthetic data and real-world cases in comparison to state-of-the-art change point detection algorithms and we have the best values in approximately 71% of the experiments. |
Abstract: | Séries temporais são representações organizadas cronologicamente ao longo do tempo, usadas para descrever a dinâmica de um determinado sistema. O comportamento deste sistema pode apresentar variações ao longo do tempo, e os pontos no tempo onde essas variações ocorrem são chamados de pontos de mudança. Detectar esses pontos de mudança é uma tarefa importante com diversas aplicações relevantes para o mundo atual, como no monitoramento de mudanças climáticas, investigação de problemas médicos, compreensão de ondas cerebrais, padrões de sono e aprimoramento da classificação de imagens como uma etapa de pré-processamento. Apesar da detecção de ponto de mudança ser uma área explorada na literatura por décadas, ainda existem alguns desafios. Notavelmente, existe a demanda por algoritmos que operem de forma \textit{online} sem que seja preciso a informação da série temporal por completo, e por algoritmos que demonstrem adaptabilidade a diversos sistemas. Neste trabalho, nós propomos um novo método capaz de resolver esses desafios. Nossa abordagem é baseada em transformações de séries temporais do tipo \textit{Symbolic Aggregate ApproXimation} (SAX), simbologia de \textit{Bag-of-Patterns} (BOP), probabilidade de transição entre símbolos e distância Jensen-Shannon. Avaliamos nosso algoritmo proposto utilizando casos sintéticos e dados do mundo real, comparando-o com métodos de detecção de pontos de mudança do estado da arte e obtivemos os melhores resultados em aproximadamente 71% dos experimentos. |
Subject: | Computação – Teses Algoritmos de computador – Teses Análise de séries temporais - Teses Detecção de ponto de mudança - Teses |
language: | eng |
metadata.dc.publisher.country: | Brasil |
Publisher: | Universidade Federal de Minas Gerais |
Publisher Initials: | UFMG |
metadata.dc.publisher.department: | ICX - DEPARTAMENTO DE CIÊNCIA DA COMPUTAÇÃO |
metadata.dc.publisher.program: | Programa de Pós-Graduação em Ciência da Computação |
Rights: | Acesso Aberto |
metadata.dc.rights.uri: | http://creativecommons.org/licenses/by-nc-nd/3.0/pt/ |
URI: | http://hdl.handle.net/1843/67719 |
Issue Date: | 5-Feb-2024 |
Appears in Collections: | Dissertações de Mestrado |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
GiovannaRiqueti_dissertacao_mestrado_versao_final.pdf | 2.21 MB | Adobe PDF | View/Open |
This item is licensed under a Creative Commons License