In many fields, from finance to healthcare to engineering, there is a growing need to monitor and analyze large and complex multivariate time series. These time series often contain critical information that can be used to improve decision-making and optimize system performance. However, these time series can also be noisy and subject to various forms of interference, making it difficult to extract meaningful insights. One important challenge is identifying the moments when the underlying process changes, also known as changepoints. Detecting these changepoints in real-time is crucial for timely intervention and improved outcomes. In this paper, we explore the use of Fisher's linear discriminant and Petunin statistics for detecting changepoints in multivariate time series. We show how this approach can be applied to computer modeling and intelligent systems to improve the accuracy and efficiency of decisionmaking in a wide range of fields. Time series, changepoint, nonparametric statistics, computer modeling, intelligent systems.
generate false changepoints. scenarios, and objects. server overload.
Automatic systems and artificial intelligence can be used to recognize changepoints in multidimensional time series, providing valuable opportunities in various fields such as medicine, engineering, economics, and cybersecurity. This can help optimize the allocation of human resources, allowing them to focus on management and critical issues that affect people's lives. Nuclear power plants serve as an important example of the responsible use of computer modeling and intelligent systems. Safety is crucial in the design, use, economics, and licensing of such energy sources. To prevent and mitigate the consequences of accidents, it is essential to ensure the integrity and operability of vital elements within nuclear power plants. Designers have historically incorporated redundant and diverse safety features into these plants to provide reliability, ensuring that the health and safety of workers and the public can be protected with a high level of confidence even in abnormal and unplanned situations.
To be practical, a method should possess several characteristics, including: 1. High precision to minimize false negative and false positive outcomes. 2. Robustness to withstand individual outlying data points that may skew the entire data series and 3. Insensitivity to underlying distributions to maximize its applicability across different domains, 4. Low computational cost to enable real-time processing without excessive resource utilization or 5. Optimal sensitivity that is neither too high to detect insignificant changes nor too low to miss critical events, such as nuclear reactor meltdowns or medical emergencies.
This paper will introduce a novel method for detecting changepoints in multivariate time series, which is based on a metric developed in a previous study [1]. This new method has been shown to
2023 Copyright for this paper by its authors. outperform the Kolmogorov-Smirnov and Wilcoxon statistics, as demonstrated in a recent study [2]. The paper will also discuss the potential applications of this method in the field of computer modeling and intelligent systems, specifically in the area of medicine. Section 2.1 will describe the algorithm used to calculate the Petunin statistic and its properties, while section 2.2 will discuss the algorithm for constructing the Fisher linear discriminant. Section 2.3 will provide an overview of the current state of research on detecting changepoints in multivariate time series. Section 3.1 will present the results of various numerical experiments involving different distributions.
Through a series of experiments and tests, we demonstrate the strength and effectiveness of our method, showing that it is capable of producing good results. Overall, we believe that our method represents a step forward in scientific research, offering a truly unique and innovative approach to solving some of the most challenging problems of our time. We hope that our work will inspire others to explore new and unconventional methods, leading to even more groundbreaking discoveries in the future.
This chapter provides a comprehensive overview of the existing literature, as well as the statistical tools, namely Petunin’s statistic and Fisher's linear discriminant analysis, that will be used in this study. This paper presents novel theoretical results that combine Fisher's linear discriminant analysis and Petunin’s statistic for data analysis in our topic. This is the first study to use these two statistical tools in combination for analyzing data and our results demonstrate the unique benefits of this approach. 2.1.
Let us consider two general populations and ′ and corresponding distribution functions and ′.
Let there be two samples
= ( 1, 2, … ) ∈ and ′ = ( 1′, 2′, … ′) ∈ ′, and (
( ) = = {
∈ (Δ(1), Δ(2))} , ( ) = 1 −
If we have a sample ′ ∈ ( (′1), (′2), (′3), … , (′ )), we can find the frequency ℎ random event and confidence intervals (Δ(1), Δ
(
ℎ 2 2 2 2 2 + 2 + 2 ( ) + − √ℎ ( ) (1 − ℎ
( )) + ( ) + + √ℎ ( ) (1 − ℎ ( )) + − + 1 2 4 2 4 Assuming ( ) = 1 −
( ( ) where ( ) is the normal distribution density, we can determine
the significance level of the confidence interval
( , ) = (Δ(1), Δ
(
with an approximate significance level of 0.05 [1]. 2.2.
Fisher's linear discriminant and LDA (Linear discriminant analysis) are terms that are often used interchangeably, but Fisher's original paper [3] describes a discriminant that differs slightly from LDA. Fisher's method does not rely on some of the assumptions of LDA, such as classes with normal distributions or equal class covariances. of the variance between the classes to the variance within the classes:
Consider two classes of observations with means ⃗⃗⃗⃗0, ⃗⃗⃗⃗1 and covariances Σ0, Σ1. If we use the linear combination of features ⃗⃗ ⋅ , the means of the resulting distribution will be ⃗⃗ ⋅ ⃗⃗⃗ , and the variances will be ⃗⃗ Σ ⃗⃗ for = 0,1. Fisher defined the separation between these two distributions to be the ratio = 2 2 ℎ = (⃗⃗ ⋅ ⃗⃗⃗ − ⃗⃗ ⋅ ⃗⃗⃗⃗0)2 ⃗⃗ Σ1⃗⃗ + ⃗⃗ Σ0⃗⃗ = (⃗⃗ ⋅ (⃗⃗⃗ − ⃗⃗⃗⃗0)) ⃗⃗ (Σ0 + Σ1)⃗⃗ 2
The measure described here is a way to evaluate the effectiveness of class labelling by comparing the separation between two sets of observations to the variance within each set. The maximum separation is achieved when a certain linear combination of features is used, with the vector representing the normal to the discriminant hyperplane.
⃗⃗ ∝ (Σ0 + Σ1)−1(⃗⃗⃗ − ⃗⃗⃗⃗0)
In a two-dimensional problem, this hyperplane is represented by a line that is perpendicular to this vector. The data points are then projected onto this hyperplane, and a threshold is chosen based on analysis of the one-dimensional distribution of the projections. One possible way to set this threshold is by placing it between the projections of the means of the two sets of observations. 1 2 = ⃗⃗ ⋅ (⃗⃗⃗⃗0 + ⃗⃗⃗⃗1) =
⃗⃗⃗⃗1 Σ1−1⃗⃗⃗⃗1 −
⃗⃗⃗⃗0 Σ0−1⃗⃗⃗⃗0 The value of the parameter c in the threshold condition ⃗⃗ ⋅ > can be explicitly determined in this case. It should be noted that Fisher's original discriminant differs slightly from LDA in terms of the assumptions it makes about the classes being normally distributed or having equal covariances. 1 2 1 2 2.3.
There are numerous approaches to detection of changepoints in multidimensional time series of random values. A changepoint of a time series is such point where values of time series have different distribution that before and after that point. Methods for detection changepoints in multidimensional time series can be classified into online and offline algorithms. Online algorithms work on portion of data in time, but offline algorithms work on completed sets of data. Article [6] provided a comprehensive review of offline methods for changepoint detection. For online algorithms, we aim to consider a method that is independent of initial distributions.
The article [7] proposes a novel approach for discriminant analysis, called Kernel Fisher Discriminant, which shows competitive performance compared to other classification techniques and has potential for further extensions in multi-class discriminants and generalization error bounds.
Increasing of dimension can slow down computations. Article [8] discussed application of divergence measures to detect a changepoint in a time series. Changepoint detection can be performed in different ways, such as detection of a changepoint in time series or localization of its coordinates. Article [9] focused on detecting a changepoint, but their method has not high accuracy in localization. Article [10] proposed a Bayesian method with linear computational complexity, but its accuracy is insufficient. Article [11] developed an effective convex network clustering algorithm, but it is computationally complex. The article [12] proposes a change-point based control chart for monitoring sparse changes in high-dimensional mean vector in HDLSS scenarios, which is robust to correlation, non-normality, and heteroscedasticity and shows efficient detection of large sparse shifts with accurate estimation of the change-point and potential OC variables, as shown by experimentation and a real case study.
To process online data, identify outliers without restricted assumptions about the data distribution, we will examine papers that consider our problem from the same point of view. Articles [13] and [14] developed a Bayesian method for exploring geographical data. Article [15] considered algorithms for exponential models only, while article [16] requires information about type of distribution to increase the accuracy of their method. Article [17] made assumptions on distribution to decrease computational complexity. Article [18] also required prior assumptions about the data. Pre-processing the data can increase the precision of changepoint detection in multivariate time series [19]. Articles [20] and [21] proposed Bayesian methods for segmenting multivariate time series with implicit examination of a dependency structure.
In the study by [22], an algorithm was examined for streaming data, which relied on a massive matrix that was contingent on the size of the original data space. Comparable techniques were explored in a different research paper by Romano and others in [23].
The Petuninʼs statistics is a measure of distance between two distributions, which can be used to detect a changepoint in a time series. The proposed algorithm is based on this statistic and has the following properties:
1. Stability: The algorithm is designed to be stable over time, meaning that it can accurately detect changepoints even when underlying distribution of data changes over time.
2. High accuracy: The Petuninʼs statistics is a robust measure of distance between distributions. It allows accurate detection of changepoints even in the presence of outliers or other noise in data.
3. Speed: The algorithm is designed to be computationally efficient, allowing for real-time processing of streaming data.
4. Independence from basic distributions: The algorithm does not require any assumptions or prior knowledge about the underlying distribution of the data, making it applicable to a wide range of time series data.
In summary, the proposed algorithm based on Petuninʼs statistic offers a stable, accurate, and computationally efficient method for detecting changepoints in time series data, without requiring any specific assumptions about the underlying distribution of data.
In this chapter, we present a method for detecting changepoints in time series data and conduct several numerical experiments to evaluate its performance with different distributions.
Our method is based on a combination of statistical tools, including Petunin’s statistic and Fisher's linear discriminant analysis. By using these tools in combination, we can identify changepoints in time series data with high accuracy.
The purpose of our experiments is to demonstrate the accuracy of the following algorithm for a stationary time series, which should find the first changepoint and test the homogeneity hypothesis.
At the beginning we take ℎ and designate the elements 1, … , ℎ - starting ones, with which we will continue to work using the sliding window method. When we have a sample ( +1, +2, … , + ℎ), we do the following with it: Building a linear Fisher discriminant for samples ( 1, 2, … , ℎ) and ( +1, +2, … , + ℎ) and find the projections on the line. Rotate the resulting straight line so that only one coordinate remains, and make the rest the same. Getting projections ( 1, 2, … , ℎ) and ( +1, +2, … , + ℎ) Calculate the Petunin’s statistics for the resulting sets of projections If ≥ 0.95, then we say that the new sample has the same distribution as the original one, otherwise we say that the other and shift the initial sample to position ( + ℎ+1, … , +2⋅ ℎ). Shifting our window one position to the right and start the algorithm from the beginning. We do this until all the data is gone.
If sample after element become inhomogeneous, then the point +1 regarded as a changepoint.
To demonstrate how the algorithm works, we take a series of length = 400 and divide it into 4 equal intervals with different distributions. Then we run our algorithm 100 times and average the values of Petunin's statistics (P statistics), after which we display the obtained values in two colors: blue is not less than 0.95, that is, for those samples that have the same distribution as the original and red less than 0.95 - having a different distribution.
For each experiment, we calculated five measures of error: mean absolute error (MAE), mean squared error (MSE), mean squared deviation (MSD), root mean squared error (RMSE), and normalized root mean squared error (NRMSE). To demonstrate the effectiveness of the described algorithm, we will rely on the latter value. As is well known, if NRSME > 0.5 the results can be considered as random. If a NRMSE is close to 0, then the results are considered good.
We aim to conduct a numerical experiment that involves analyzing several time series with jumps of varying distributions. In the first scenario, we will analyze a time series consisting of nearly nonoverlapping uniform distributions and test the hypothesis of a shift in this series. In the second scenario, we will analyze a time series with jumps of uniform distributions initially exhibiting significant overlap, followed by mild overlap, and ultimately no overlap, with the purpose of testing the hypothesis of a shift. Additionally, we will examine time series with jumps of normal distributions, where distinct means exhibit minimal overlap, to test the hypothesis of a shift. In the fourth scenario, we will examine time series with jumps that comprise normal distributions with identical means but gradually differing variances, aiming to test the scale hypothesis. Finally, in the fifth scenario, we will analyze a time series with jumps of normal distributions with the same means but differing variances, testing the scale hypothesis on this series.
We will analyze time series with jumps that consists of nearly non-overlapping uniform distributions. The aim is to test the hypothesis of a shift in this series.
We will analyze time series with jumps that consists of uniform distributions initially exhibiting significant overlap, followed by mild overlap, and ultimately no overlap. The purpose is to test the hypothesis of a shift in this series. Measures of error for uniform distributions with distinct means that exhibit significant overlap initially, followed by mild overlap, and ultimately no overlap.
We will analyze time series with jumps composed of normal distributions with distinct means that exhibit minimal overlap. The aim is to test the hypothesis of a shift in this series.
We will examine time series with jumps that comprises normal distributions with identical means, but with gradually differing variances. The objective is to test the scale hypothesis on this series.
Value 47.75 2468.69 19.96 46.73 0.23
Let's consider time series with jumps, which is composed of normal distributions with the same means, but with variances that differ more strongly. On this time series, we will be able to test the scale hypothesis.
Distribution 1 As can be seen from Table 9 and Figure 9, the desired changepoint is 100. In Figure 10, we see that the p-statistic takes values greater than 0.95 only in the first interval and the measures of error we can see in Table 10. Indeed, it is worth noting that hypotheses about scale are generally more challenging to test than those about shift. However, our algorithm is designed to detect changepoints even in scenarios where the scale hypothesis is being tested, allowing for a comprehensive analysis of the time series. By identifying these points, we can gain valuable insights into the behavior of the series and validate or reject our hypotheses.
In conclusion, our study has presented a novel algorithm for detecting changepoints in time series data that combines Fisher's linear discriminant and Petunin's statistics. Our numerical experiments have shown that this algorithm can accurately and quickly detect changes in a wide range of distribution functions.
Additionally, our algorithm has several advantages over existing changepoint detection methods. Firstly, our algorithm does not require any assumptions about the distribution of the data, making it more flexible and applicable to a wider range of scenarios. Secondly, the computational complexity of our algorithm is relatively low, which makes it efficient and scalable to larger datasets. Finally, our algorithm provides interpretable results, which can help researchers and practitioners to better understand the nature of changes in the time series data.
The implications of our results are significant, as our algorithm could have practical applications in monitoring the health status of COVID-19 patients in clinics. By accurately detecting changes in vital signs or symptoms, medical professionals could intervene earlier and improve patient outcomes. Furthermore, we have evaluated the performance of our algorithm using NRMSE, which measures the accuracy of the detected changepoints. Our NRMSE values demonstrate that our algorithm works accurately.
However, we acknowledge that there are limitations to our study, such as using simulated data in our experiments. Therefore, the performance of our algorithm may differ when applied to real-world data. Nevertheless, our algorithm provides a valuable contribution to the field of changepoint detection, and we plan to evaluate its performance on real-world data in future research.
We hope that our combination of Fisher's linear discriminant and Petunin's statistics will inspire further research in this area and contribute to improving the accuracy and efficiency of changepoint detection algorithms. Overall, our study provides a promising foundation for future research in this field.
[3] R. A. Fisher, The Use of Multiple Measurements in Taxonomic Problems. Annals of
Eugenics, volume 7, 2nd. ed., 1936, pp. 179–188. [4] B.L. Van der Waerden, Mathematische Statistic, Springer-Verlag, Berlin, 1957; English. transl. of 2nd. ed. (1965) Springer-Verlag, Berlin and New York, 1969 [5] Y. I. Petunin, D. A. Klyushin, K. P. Ganina, N. V. Borodai, R. I. Andrushkiv, Computer diagnosis of breast cancer, Bulletin of Kyiv University, Ser. cybernetics, volume 2, 2001, pp. 58-68. [6] C. Truong, L. Oudre, N. Vayatis, Selective review of offline changepoint detection methods,
Signal Processing, volume 167, 2020, 107299. doi:10.1016/j.sigpro.2019.107299. [7] S. Mika, Fisher Discriminant Analysis with Kernels, IEEE Conference on Neural Networks for
Signal Processing IX, 1999, pp. 41–48. doi:10.1109/NNSP.1999.788121 [8] C. Alippi, G. Boracchi, D. Carrera M. Roveri, Change Detection in Multivariate Datastreams: Likelihood and Detectability Loss, Twenty-Fifth International Joint Conference on Artificial Intelligence (IJCAI-16), 2016, pp. 1368–1374. doi:10.48550/arXiv.1510.04850. [9] Z. Wang, X. Lin, A. Mishra, R. Sriharsha, Online Changepoint Detection on a Budget, 2021 International Conference on Data Mining Workshops (ICDMW), 2021, pp. 414–420. doi:10.1109/ICDMW53433.2021.00057. [10] S. Jaehyeok, A. Ramdas, and A. Rinaldo, E-detectors: a nonparametric framework for online changepoint detection, arXiv preprint arXiv:2203.03532v1, 2022.
doi:10.48550/arXiv.2203.03532. [11] O. Sorba, C. Geissler, Online Bayesian inference for multiple changepoints and risk assessment.
arXiv preprint arXiv:2106.05834v1, 2021. doi:10.48550/arXiv.2106.05834. [12] M. Navarro, G. I. Allen, M. Weylandt, Network Clustering for Latent State and Changepoint
Detection, 2021. arXiv preprint arXiv:2111.01273v1. doi:10.48550/arXiv.2111.01273. [13] Z. Wang, I. M. Zwetsloot, A Change-Point Based Control Chart for Detecting Sparse Changes in High-Dimensional Heteroscedastic Data, 2021. arXiv preprint arXiv:2101.09424v1. doi:10.48550/arXiv.2101.09424. [14] L. Wendelberger, J. Gray, B. Reich, A. Wilson, Monitoring Deforestation Using Multivariate
Bayesian Online Changepoint Detection with Outliers, 2021. arXiv preprint arXiv:2112.12899v2. [15] P. Adams, D. Mackay, Bayesian Online Changepoint Detection, 2007. arXiv preprint arXiv:0710.3742v1. doi:10.48550/arXiv.0710.3742 [16] P. Cooney, A. White, Change-point Detection for Piecewise Exponential Models, 2021. arXiv preprint arXiv:2112.03962v1. doi:10.48550/arXiv.2112.03962 [17] J. Castillo-Mateo, Distribution-Free Changepoint Detection Tests Based on the Breaking of
Records, 2021. arXiv preprint arXiv:2105.08186v1. doi:10.48550/arXiv.2105.08186. [18] K. L. Hallgren, N. A. Heard, M. J. M. Turcotte, Changepoint detection on a graph of time series, 2021. arXiv preprint arXiv:2102.04112v1. doi:10.48550/arXiv.2102.04112 [19] A. Fotoohinasab, T. Hocking, F. Afghah, A Greedy Graph Search Algorithm Based on Changepoint Analysis for Automatic QRS Complex Detection, Computers in Biology and Medicine, 2021, volume 130, 104208. doi:10.1016/j.compbiomed.2021.104208 [20] P. Fearnhead, G. Rigaill, Changepoint Detection in the Presence of Outliers, Journal of the American Statistical Association, 2018, volume 114, pp. 169–183.
doi:10.1080/01621459.2017.1385466 [21] F. Harlé, F. Chatelain, C. Gouy-Pailler, S. Achard, Rank-based multiple change-point detection in multivariate time series, 22nd European Signal Processing Conference (EUSIPCO), 2014, pp. 1337–1341. doi:10.5281/zenodo.43927. [22] K. Renz, N. C. Stache, N. Fox, G. Varol, S. Albanie, Sign Segmentation with ChangepointModulated Pseudo-Labelling, 2021. arXiv preprint arXiv:2104.13817v1.
doi:10.48550/arXiv.2104.13817 [23] G. Romano, I. Eckley, P. Fearnhead, G. Rigaill, Fast Online Changepoint Detection via Functional Pruning CUSUM statistics, 2021. arXiv preprint arXiv:2110.08205v2. doi:10.48550/arXiv.2110.08205.