Inferindo pontos de mudança em séries temporais com dados não rotulados: um breve estudo usando dados do NDT
Resumo
Utilizamos algoritmos de detecção de pontos de mudança em séries temporais de latência e throughput, coletados por meio da ferramenta NDT, para identificar momentos de mudanças estatísticas nessas séries. Examinamos três métodos clássicos (Shewhart, EWMA e CUSUM) e destacamos que suas implementações simples podem não ser adequadas para detectar tais pontos. Apresentamos então estratégias simples para remediar este problema. Também introduzimos um novo método de detecção de pontos de mudança que oferece flexibilidade e interpretabilidade para facilitar o processo de tomada de decisão. Mostramos uma aplicação simples que pode ser usada para avaliar QoS, mesmo quando os rótulos não estão disponíveis.Referências
Aggarwal, C. C. (2017). Outlier Analysis. Springer, New York, 2 edition.
Aminikhanghahi, S. and Cook, D. J. (2017). A survey of methods for time series change point detection. Knowledge and information systems, 51(2):339–367.
Basseville, M. and Nikiforov, I. V. (1993). Detection of abrupt changes: theory and application. Prentice Hall.
Braei, M. and Wagner, S. (2020). Anomaly detection in univariate time-series: A survey on the state-of-the-art. arXiv preprint arXiv:2004.00433.
Chandola, V., Banerjee, A., and Kumar, V. (2009). Anomaly detection: A survey. ACM computing surveys (CSUR), 41(3):1–58.
Farkas, K. (2015). Cusum anomaly detection. [link]. [Online; accessed 12-January-2024].
Li, J., Fearnhead, P., Fryzlewicz, P., and Wang, T. (2024). Automatic Change-Point Detection in Time Series via Deep Learning. Journal of the Royal Statistical Society Series B: Statistical Methodology.
Liu, Z., Zhang, Z., and Liu, Y. (2021). Power grid security risk assessment method based on weighted voting ensemble machine learning algorithm. In 2021 6th International Conference on Power and Renewable Energy (ICPRE), pages 607–613.
M-Lab (2024). NDT - network diagnostic tool.
Montgomery, D. C. (2013). Introduction to Statistical Quality Control. Wiley, New York, 7 edition.
Moustakides, G. V. (2014). Multiple optimality properties of the shewhart test. Sequential Analysis, 33(3):318–344.
Nordmann, L. and Pham, H. (1999). Weighted voting systems. IEEE Transactions on Reliability, 48(1):42–49.
Page, E. S. (1954). Continuous inspection schemes. Biometrika, 41(1/2):100–115.
Roberts, S. (1959). Control chart tests based on geometric moving averages. Technometrics, 1(3):239–250.
Santos, G., Mendonça, G., Leão, R., and e Silva, E. S. (2022). Detecção de anomalias em redes baseada em medições de qos e rótulos de qoe com ruído. In Anais do XL Simpósio Brasileiro de Redes de Computadores e Sistemas Distribuídos, pages 98–111, Porto Alegre, RS, Brasil. SBC.
Schmidl, S., Wenig, P., and Papenbrock, T. (2022). Anomaly detection in time series: a comprehensive evaluation. Proceedings of the VLDB Endowment, 15(9):1779–1797.
Shewhart, W. A. (1929). Control of quality of manufactured product.
Streit, A., Santos, G. H., Leão, R. M., e Silva, E. d. S., Menasché, D., and Towsley, D. (2021). Network anomaly detection based on tensor decomposition. Computer Networks, 200:108503.
Tartakovsky, A., Nikiforov, I., and Basseville, M. (2015). Sequential analysis: Hypothesis testing and changepoint detection. CRC press.
Tartakovsky, A. G., Polunchenko, A. S., and Sokolov, G. (2013). Efficient computer network anomaly detection by changepoint detection methods. IEEE Journal of Selected Topics in Signal Processing, 7(1):4–11.
Vasantam, T., Towsley, D., and Veeravalli, V. V. (2021). Quickest change detection in the presence of transient adversarial attacks. In 2021 55th Annual Conference on Information Sciences and Systems (CISS), pages 1–6. IEEE.
Xie, L., Moustakides, G. V., and Xie, Y. (2023). Window-limited cusum for sequential change detection. IEEE Transactions on Information Theory.
Ximenes, D., Mendonça, G., Santos, G. H., de Souza, E., Leão, R. M., Menasché, D. S., et al. (2018). O problema de detecção e localização de eventos em séries temporais aplicado a redes de computadores. In Anais do XVII Workshop em Desempenho de Sistemas Computacionais e de Comunicação. SBC.
Aminikhanghahi, S. and Cook, D. J. (2017). A survey of methods for time series change point detection. Knowledge and information systems, 51(2):339–367.
Basseville, M. and Nikiforov, I. V. (1993). Detection of abrupt changes: theory and application. Prentice Hall.
Braei, M. and Wagner, S. (2020). Anomaly detection in univariate time-series: A survey on the state-of-the-art. arXiv preprint arXiv:2004.00433.
Chandola, V., Banerjee, A., and Kumar, V. (2009). Anomaly detection: A survey. ACM computing surveys (CSUR), 41(3):1–58.
Farkas, K. (2015). Cusum anomaly detection. [link]. [Online; accessed 12-January-2024].
Li, J., Fearnhead, P., Fryzlewicz, P., and Wang, T. (2024). Automatic Change-Point Detection in Time Series via Deep Learning. Journal of the Royal Statistical Society Series B: Statistical Methodology.
Liu, Z., Zhang, Z., and Liu, Y. (2021). Power grid security risk assessment method based on weighted voting ensemble machine learning algorithm. In 2021 6th International Conference on Power and Renewable Energy (ICPRE), pages 607–613.
M-Lab (2024). NDT - network diagnostic tool.
Montgomery, D. C. (2013). Introduction to Statistical Quality Control. Wiley, New York, 7 edition.
Moustakides, G. V. (2014). Multiple optimality properties of the shewhart test. Sequential Analysis, 33(3):318–344.
Nordmann, L. and Pham, H. (1999). Weighted voting systems. IEEE Transactions on Reliability, 48(1):42–49.
Page, E. S. (1954). Continuous inspection schemes. Biometrika, 41(1/2):100–115.
Roberts, S. (1959). Control chart tests based on geometric moving averages. Technometrics, 1(3):239–250.
Santos, G., Mendonça, G., Leão, R., and e Silva, E. S. (2022). Detecção de anomalias em redes baseada em medições de qos e rótulos de qoe com ruído. In Anais do XL Simpósio Brasileiro de Redes de Computadores e Sistemas Distribuídos, pages 98–111, Porto Alegre, RS, Brasil. SBC.
Schmidl, S., Wenig, P., and Papenbrock, T. (2022). Anomaly detection in time series: a comprehensive evaluation. Proceedings of the VLDB Endowment, 15(9):1779–1797.
Shewhart, W. A. (1929). Control of quality of manufactured product.
Streit, A., Santos, G. H., Leão, R. M., e Silva, E. d. S., Menasché, D., and Towsley, D. (2021). Network anomaly detection based on tensor decomposition. Computer Networks, 200:108503.
Tartakovsky, A., Nikiforov, I., and Basseville, M. (2015). Sequential analysis: Hypothesis testing and changepoint detection. CRC press.
Tartakovsky, A. G., Polunchenko, A. S., and Sokolov, G. (2013). Efficient computer network anomaly detection by changepoint detection methods. IEEE Journal of Selected Topics in Signal Processing, 7(1):4–11.
Vasantam, T., Towsley, D., and Veeravalli, V. V. (2021). Quickest change detection in the presence of transient adversarial attacks. In 2021 55th Annual Conference on Information Sciences and Systems (CISS), pages 1–6. IEEE.
Xie, L., Moustakides, G. V., and Xie, Y. (2023). Window-limited cusum for sequential change detection. IEEE Transactions on Information Theory.
Ximenes, D., Mendonça, G., Santos, G. H., de Souza, E., Leão, R. M., Menasché, D. S., et al. (2018). O problema de detecção e localização de eventos em séries temporais aplicado a redes de computadores. In Anais do XVII Workshop em Desempenho de Sistemas Computacionais e de Comunicação. SBC.
Publicado
20/05/2024
Como Citar
ALMEIDA, Cleiton M. de; LEÃO, Rosa M. M.; SILVA, Edmundo de Souza e.
Inferindo pontos de mudança em séries temporais com dados não rotulados: um breve estudo usando dados do NDT. In: SIMPÓSIO BRASILEIRO DE REDES DE COMPUTADORES E SISTEMAS DISTRIBUÍDOS (SBRC), 42. , 2024, Niterói/RJ.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2024
.
p. 686-699.
ISSN 2177-9384.
DOI: https://doi.org/10.5753/sbrc.2024.1462.