Inferring change points in time series with unlabeled data: a brief study using NDT data

• Cleiton M. de Almeida UFRJ
• Rosa M. M. Leão UFRJ
• Edmundo de Souza e Silva UFRJ

DOI: https://doi.org/10.5753/sbrc.2024.1462

Abstract

We use change-point detection algorithms in latency and throughput time series, collected using the NDT tool, to identify moments of statistical changes in these series. We examine three classical methods (Shewhart, EWMA, and CUSUM) and highlight that their straightforward implementations may not be suitable for detecting such points. We then present simple strategies to remedy this problem. We also introduce a novel change-point detection method that offers flexibility and interpretability to facilitate the decision-making process. We show a simple application that can be used to assess QoS, even when labels are not available.

References

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.