A non-parametric statistical technique for changepoint detection in cyber-physical systems
DOI:
https://doi.org/10.17721/2706-9699.2025.1.09Keywords:
real-time series, changepoint, nonparametric statistics, cyber-physical systems, dimensionality reductionAbstract
Cyber-physical systems generate multidimensional time series describing the state of the system. When the state of the system changes, it is necessary to detect the transition point in the time series. The article describes a new nonparametric method for detecting the transition point in multidimensional time series generated by components of cyber-system components, using the principal component analysis (PCA) as a dimensionality reduction method, and this dimensionality reduction is accompanied by the application of Petunin statistics to one-dimensional data sets. Numerical and quasi-real experiments demonstrate the high accuracy and stability of the proposed algorithm over a wide range of distributions and hypothetical examples of cyber-physical systems. The accuracy is measured by the number of steps after the transition point when it was detected. There is also a comparison with the already known methods — the Wilcoxon test and the KolmogorovSmirnov consistency test. Accuracy up to 20 steps from the transition point was achieved, and in most cases even less — no more than 10 steps. This method provides a clear and human-understandable interpretation of algorithms and their results.
References
Klyushin D.A., Petunin Y.I., Nonparametric population equivalence test based on measure of closeness between samples. Ukrainian Mathematical Journal. 2003. Vol. 55. P. 181–198.
Truong C., Oudre L., Vayatis N. Selective review of offline change point detection methods. Signal Processing. 2020. Vol. 167. doi:10.1016/j.sigpro.2011.2.1072912.
Alippi C., Boracchi G., Carrera D., Roveri M. Change Detection in Multivariate Data streams: Likelihood and Detectability Loss. Twenty-Fifth International Joint Conference on Artificial Intelligence (IJCAI-16), 2016. P. 1368–1374. doi:10.48550/arXiv.1510.04850.
Wang Z., Zwetsloot I.M. A Change-Point Based Control Chart for Detecting Sparse Changes in High-Dimensional Heteroscedastic Data. 2021. arXiv:2101.09424v1. doi:10.48550/arXiv.2101.09424.
Sorba O., Geissler C. Online Bayesian inference for multiple change points and risk assessment. 2021. arXiv preprint arXiv:2106.05834v1. doi:10.48550/arXiv.2106.05834.
Navarro M., Allen G.I., Weylandt M. Network Clustering for Latent State and Change point Detection. 2021. arXiv preprint arXiv:2111.01273v1. doi:10.48550/arXiv.2111.01273.
Tickle S.O., Eckley I.A., Fearneadh P. A computationally efficient, high dimensional multiple change point procedure with application to global terrorism incidence. 2020. arXiv:2011.03599v2. doi:10.1111/rssc.12695.
Fearneadh P., Rigaill G. Change point Detection in the Presence of Outliers. Journal of the American Statistical Association. 2018. Vol. 114. P. 169–183. doi:10.1080/016214512.2017.1385466.
Romano G., Eckley I., Fearneadh P., Rigaill G. Fast Online Change point Detection via Functional Pruning CUSUM statistics. 2021. arXiv:2110.08205v2. doi:10.48550/arXiv.2110.08205.
Wang Z., Lin X., Mishra A., Sriharsha R. Online Change point Detection on a Budget. International Conference on Data Mining Workshops (ICDMW), 2022. P. 414–420. doi:10.1109/ICDMW53433.2021.00057.
Windmann A., Steude H., Niggemann O. Robustness and Generalization Performance of Deep Learning Models on Cyber-Physical Systems: A Comparative Study. 2023. doi:10.48550/arXiv.2306.07737.
Steude H., Windmann A., Niggemann O. Learning Physical Concepts in Cyber Physical Systems: A Case Study. 2021. doi:10.48550/arXiv.2111.14151.
Aminikhanghahi S., Cook D.J. A survey of methods for time series change point detection. Knowledge and Information Systems. 2017. Vol. 51. P. 339–367.
Jaehyeok S., Ramdas A., Rinaldo A. E-detectors: a nonparametric framework for online change point detection. 2022. arXiv:2203.03532v1. doi:10.48550/arXiv.2203.03532.
Wendelberger L., Gray J., Reich B., Wilson A. Monitoring Deforestation Using Multivariate Bayesian Online Change point Detection with Outliers. 2021. arXiv preprint arXiv:2112.12899v2. doi:10.48550/arXiv.2112.12899.
Adams P., Mackay D. Bayesian Online Change point Detection. 2007. arXiv preprint arXiv:0710.3742v1. doi:10.48550/arXiv.0710.3742.
Cooney P., White A. Change-point Detection for Piecewise Exponential Models. 2021. arXiv preprint arXiv:2112.03962v1. doi:10.48550/arXiv.2112.03962.
Hallgren K.L., Heard N.A., Turcotte M.J.M. Change point detection on a graph of time series. 2021. arXiv:2102.04112v1. doi:10.48550/arXiv.2102.04112.
Fotoohinasab A., Hocking T., Afghah F. A Greedy Graph Search Algorithm Based on Change point Analysis for Automatic ORs Complex Detection. Computers in Biology and Medicine. 2021. Vol. 130. P. 104208.
Renz K., Stache N., Fox G., Varol G., Albanie S. Sign Segmentation with Change point-Modulated Pseudo-Labelling. 2021. arXiv:2104.13817v1. doi:10.48550/arXiv.2104.13817.
Gallagher C., Killick R., Lund R., Shi X. Autocovariance Estimation in the Presence of Change points. 2021. arXiv preprint arXiv:2102.10609v2. doi:10.48550/arXiv.2102.10609.
Madreimov I., Petunin Yu.I Characterization of a uniform distribution using order statistics. Teor Ver Mat Statist. 1982. 27. P. 96–102.
Matveichuk S.A., Petunin Yu.I. Generalization of Bernoulli schemes that arise in order statistics, I, Ukrainian. Math. J. 1990. Vol. 42. No. 4. P. 459–466.
Matveichuk S.A., Petunin Yu.I. Generalization of Bernoulli schemes that arise in order statistics. II, Ukrainian Math. J. 1991. Vol. 43. No. 6. P. 728–734.
Hill B.M. Posterior distribution of percentiles: Bayes’ theorem for sampling from a population. J Am Stat Assoc. 1968. Vol. 63. P. 677–691.
van der Waerden B.L. Mathematische Statistik. Springer-Verlag, Berlin, 1957; English transl. of 2nd ed., Springer-Verlag, Berlin and New York, 1969.
Petunin Y.I., Klyushin D.A., Ganina K.P., Borodai N.V., Andrushkiv R.I. Computer diagnosis of breast cancer. Bulletin of Kyiv University, Ser. Cybernetics. 2001. Vol. 2. P. 58–68.
Pearson K. On Lines and Planes of Closest Fit to Systems of Points in Space. Philosophical Magazine, 2(11): 559–572, 1901. https://doi.org/10.1080/14786440109462720.
Jolliffe I.T. Principal Component Analysis. Springer Series in Statistics, Springer Verlag, New York, 2002. https://doi.org/10.1007/b98835.
