Сomparative analysis of algorithms for change points detection in regression models of time series
DOI:
https://doi.org/10.20535/2411-1031.2021.9.2.249887Keywords:
time series, anomalies, change points detection, change detection predictive algorithms, regression modelsAbstract
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.
References
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.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2021 Information Technology and Security
This work is licensed under a Creative Commons Attribution 4.0 International License.
The authors that are published in this collection, agree to the following terms:
- The authors reserve the right to authorship of their work and pass the collection right of first publication this work is licensed under the Creative Commons Attribution License, which allows others to freely distribute the published work with the obligatory reference to the authors of the original work and the first publication of the work in this collection.
- The authors have the right to conclude an agreement on exclusive distribution of the work in the form in which it was published this anthology (for example, to place the work in a digital repository institution or to publish in the structure of the monograph), provided that references to the first publication of the work in this collection.
- Policy of the journal allows and encourages the placement of authors on the Internet (for example, in storage facilities or on personal web sites) the manuscript of the work, prior to the submission of the manuscript to the editor, and during its editorial processing, as it contributes to productive scientific discussion and positive effect on the efficiency and dynamics of citations of published work (see The Effect of Open Access).
