Change-point Detection in Time Series: A Study of Online Methods Applied to Computer Network Measurements
Autores
|
7457 |
768,754,3235
|
|
|
7458 |
768,754,3235
|
|
|
7459 |
768,754,3235
|
Informações:
Publicações do PESC
Nesta dissertação, estudamos métodos clássicos e do estado da arte para a identificação de pontos de mudanças, de modo online, em séries temporais de latência e vazão de rede. Examinamos os modelos clássicos Shewhart, EWMA e CUSUM e mostramos que implementações básicas podem não ser adequadas para detectar tais pontos. Propomos, então, estratégias simples para contornar este problema. Estudamos também os métodos BOCD e RRCF (este originalmente proposto para detecção de anomalias) e, de forma análoga aos métodos clássicos, propomos modificações simples que aumentaram o desempenho nos conjuntos de dados analisados. Avaliamos ainda um novo método para detecção de mudanças, o VWCD, que oferece flexibilidade, interpretabilidade e permitiu a detecção de pontos de mudança com maior precisão.
Aplicamos os métodos estudados a um conjunto de dados não rotulados de latência e vazão de rede, construído por nós usando a ferramenta M-Lab NDT, e apresentamos uma aplicação simples que pode ser usada para o monitoramento da qualidade de serviço de rede. Além disso, avaliamos o desempenho dos métodos utilizando um conjunto de medições de latência com pontos de mudanças rotulados. Os algoritmos propostos, incluindo o VWCD, apresentaram desempenho competitivo com um algoritmo offline do estado da arte, o Pelt não-paramétrico.
In this work, we study classical and state-of-the-art methods to identify change points in time series of network latency and throughput, in an online setting. First, we study the classic methods of Shewhart, EWMA and CUSUM, concluding that their straightforward implementations may not be suitable for detecting such points. We then present simple strategies to mitigate this problem. We also study the methods BOCD, RRCF (this was initially proposed for anomaly detection) and, similarly to the classical methods, we propose simple strategies that improve their performance in the studied datasets. We also introduce a novel change-point detection method, the VWCD, that offers flexibility and interpretability and increases the precision of the change-point detection.
We applied the methods to a non-labeled dataset of latency and throughput, built by us using the M-Lab NDT tool, and showed a simple application that can be used to access the network quality of service. Furthermore, we assessed the methods' performance using a latency dataset with labeled change points. The proposed algorithms, including the VWCD, showed competitive performance with a state-of-the-art offline algorithm, the non-parametric Pelt.