Сomparative analysis of algorithms for change points detection in regression models of time series





time series, anomalies, change points detection, change detection predictive algorithms, regression models


Changes detection in the behavior of the object is one of the main goals оf any real-world objects’ monitoring. The behavior of an object can change over time due to its reaction to external events, as well as under the influence of the internal development laws of the object. Problems occur in cases when internal changes couldn't be observed directly. In such cases, it is possible to obtain information about the internal changes only through analysis of the time series observed parameters, the measurement of which could be performed technically and/or organizationally. Several changes detection algorithms in time series, which are based on the linear regression models are discussed. It is assumed that if the event of changes occurs, the time series before and the time series after the change point are described by models which cannot be considered identical. Some known algorithms for analyzing the identity of models and algorithms that have not previously been deposited in the literature are considered. In particular, an algorithm for change points detection based on changes in the values of the regression models coefficients; based on analyzing the confidence interval of the predicted values of the series; based on analyzing regression residuals based on the use of Höffding's inequality; Chow algorithms for comparing variances of residuals; an algorithm for comparing the distributions of residuals using the Kolmogorov-Smirnov's two-samples test. The variety of objects in the real world, types of changes in their behavior, which are based on the unpredictability of the reasons that caused them, do not allow choosing a single change points detection method and makes a comparative assessment of various algorithms an urgent engineering problem. The paper proposes an algorithms’ analysis depending on the types of changes that are most typical for parameters time series in various domains. The effectiveness of the algorithms is assessed by the method of the statistical experiment by their ability to detect a change, as well as by comparing the number of false detection errors and skipping real changes. The obtained results can be used for further research of algorithms, in particular, in the case of constructing an ensemble of algorithms for identifying change points of the behavior of monitored objects.

Author Biographies

Viacheslav Riabtsev, Institute of special communication and information protection of National technical university of Ukraine “Igor Sikorsky Kyiv polytechnic institute”, Kyiv

candidate of engineering sciences, associate professor, associate professor at the cybersecurity and application of information systems and technology academic department

Dmytro Sharadkin, Institute of special communication and information protection of National technical university of Ukraine “Igor Sikorsky Kyiv polytechnic institute”, Kyiv

candidate of engineering sciences, associate professor, associate professor at the cybersecurity and application of information systems and technology academic department

Yurii Kliat, Military Academy, Odesa

candidate of technical sciences, deputy chief


D. G. Pascual, Artificial Intelligence Tools: Decision Support Systems in Condition Monitoring and Diagnosis, Boca Raton, Florida, USA: CRC Press, 2015.

E. S. Page, “A test for a change in a parameter occurring at an unknown point”, Biometrika, vol. 42, no. 3/4, pp. 523-527, 1955, doi: https://doi.org/10.2307/2333401.

S. Liu, A. Wright, and M. Hauskrecht, “Change-Point Detection Method for Clinical Decision Support System Rule Monitoring”, Artif Intell Med Conf Artif Intell Med, pp. 126-135, 2017, doi: https://doi.org/10.1007/978-3-319-59758-4_14.

S. J. Taylor, and B. Letham, “Forecasting at Scale”, The American Statistician, Taylor & Francis J., vol. 72 (1), pp. 37-45, 2018, doi: https://doi.org/10.1080/00031305.2017.1380080.

D.-H. Tran, “Change detection in streaming data”, Thesis of dissertation of the Requirements for the degree of Doktor-Ingenieur, Technische Universität Ilmenau, Germany, 2013.

A. G. Tartakovsky, I. Nikiforov, and M. Basseville, Sequential Analysis: Hypothesis Testing and Changepoint Detection, Monographs on Statistics & Applied Probability, vol. 136, Publisher: Chapman & Hall/CRC, Taylor and Francis Group, 2015.

B. Kurt, Ç. Yıldız, T. Y. Ceritli, B. Sankur, and A. T. Cemgil, “A Bayesian change point model for detecting SIP-based DDoS attacks”, Digital Signal Processing, vol. 77, pp. 48-62, 2018, doi: https://doi.org/10.1016/j.dsp.2017.10.009.

V. V. Sokolov, O. M. Shapoval, and D. M. Sharadkin “Ensemble of algorithms for detecting anomalies in time series and its use for problems of monitoring the state of systems in real time”, VITI’s collection of scientific papers, 2020, no. 3, p. 82-93, 2020.

D. М. Sharadkin, “Сhange-point detection test based on the analysis of the time series’ autocorrelation and its application for information security”, Information Technology and Security, vol. 5, iss. 1 (8), рр. 42-54, January-June 2017, doi: https://doi.org/10.20535/2411-1031.2017.5.1.120555.

D. V. Hinkley, “Inference about the change-point in a sequence of random variables” Biometrika, vol. 57, no. 1, pp. 1-17, 1970, doi: https://doi.org/10.2307/2334932.

S. Liu, M. Yamada, N. Collier, and M. Sugiyama, “Change-point detection in time-series data by relative density-ratio estimation”, Neural Networks, vol. 43, pр. 72-83, 2013, doi: https://doi.org/10.1016/j.neunet.2013.01.012.

G. Boracchi, C. Cervellera, and D. Macciò, “Uniform histograms for change detection in multivariate data”, International Joint Conference on Neural Networks (IJCNN), Anchorage, pp. 1732-1739, 2017, doi: https://doi.org/10.1109/IJCNN.2017.7966060.

R. Sebastiao, and J. Gama, “A study on change detection methods”, in Proc. 4th Portuguese Conf. on Artificial Intelligence, Aveiro, Portugal, 2009, pp. 353-364.

M. Hushchyn, K. Arzymatov, and D. Derkach, “Online Neural Networks for Change-Point Detection”, arXiv: 2010.01388, 2020. [Online]. Available: https://arxiv.org/abs/2010.01388. Accessed on: August 27, 2021.

T. de Ryck, M. de Vos, and A. Bertrand, “Change Point Detection in Time Series Data Using Autoencoders With a Time-Invariant Representation”, in IEEE Transactions on Signal Processing, vol. 69, pp. 3513-3524, 2021, doi: https://doi.org/10.1109/TSP.2021.3087031.

K. G. Mehrotra, C. K. Mohan, and H. M. Huang, Anomaly Detection. Principles and Algorithms. Springer International Publishing AG 2017, doi: https://doi.org/10.1007/978-3-319-675268.

S. Ratnasingam, “Sequential change-point detection in linear regression and linear quantile regression models under high dimensionality”, A Dissertation Submitted to the Graduate College of Bowling Green State University in partial fulfillment of the requirements for the degree of Doctor of Philosophy, August 2020.

M. V. Zhitlukhin, “Sequential Methods for Testing Statistical Hypotheses and Detecting Disorders”, Dissertation for the degree of candidate of physical and mathematical sciences, V. A. Steklov’s Mathematical Institute., Moscow, 2013.

X. Xu, H. Liu, and M. Yao, Recent Progress of Anomaly Detection. Hindawi Complexity, vol. 2019, Article ID 2686378, 11 p., doi: https://doi.org/10.1155/2019/2686378.

G. J. J. van den Burg, and C. K .I. Williams, “An Evaluation of Change Point Detection Algorithms”, arXiv: 2003.06222v2 [stat.ML] 25 May 2020, 33 p. [Online] Available: https://arxiv.org/abs/2003.06222v2. Accessed on: August 27, 2021.

E.-S. Apostol, C.-O. Truica, F. Pop, and C. Esposito, “Change Point Enhanced Anomaly Detection for IoT Time Series Data”, Water (Special Issue Smart Water Solutions with Big Data), vol. 13, no. 12, 20 p., 2021, doi: https://doi.org/10.3390/w13121633.

S. A. Ayvazyan, V. M. Buchstaber, I. S. Enyukov, and L. D. Meshalkin, Applied Statistics. Classifications and dimensionality reduction, Moskow: Finance and statistics, 1989.

Sh. Shalev-Schwartz, and Sh. Ben-David, Machine Learning Ideas. From theory to algorithms, M: DMK Press, 2019.

L. A. Landman and A. V. Faddeenkov, “Comparative analysis of various methods for assessing the structural stability of objects based on their time series”, Bulletin of the ASTU. Series: Management, Computer Engineering and Informatics, no. 1, pp. 119-128, 2019, doi: https://doi.org/10.24143/2072-9502-2019-1-119-128.



How to Cite

Riabtsev, V., Sharadkin, D., & Kliat, Y. (2021). Сomparative analysis of algorithms for change points detection in regression models of time series. Collection "Information Technology and Security", 9(2), 137–150. https://doi.org/10.20535/2411-1031.2021.9.2.249887