Modern companies contain a huge number of processes. The larger and more complex the business that one person or company is engaged in, the more impossible it becomes to keep track of all the processes in manual mode. Each element is at risk of failure, and in order to prevent or quickly respond to various breakdowns, you need to be able to recognize errors automatically so that in case of critical situations, seek help from a specialist who can fix everything. For modern systems, which can be important every second and which constantly process huge flows of information, a method is needed that will allow you to quickly recognize changes in state, for example, a deterioration in the patient's condition or server failure. To solve these and similar problems, a new method based on the use of Fisher's linear discriminant and Petunin statistics is proposed. To simulate the process, after turning on the sensors to capture data and a continuous flow of information, a multidimensional time series will be generated, after which the method will recognize changepoints that indicate that the object has changed state or something has happened to it. A clear probabilistic interpretation of the method underlying this classification greatly expands its capabilities within the framework of risk-informed systems.
The use of automatic systems and artificial intelligence to recognize changepoints in multidimensional time series provides great opportunities for risk-informed systems. For example, in the fields of medicine, engineering, economics, cybersecurity, which may be narrowly focused or if the region lacks qualified employees. This will help to optimize the use of human resources, which can be directed to the management or solving critical issues, for example, those related to people's lives.
Nuclear power plants provide another important example of the responsible use of riskinformed systems. In the design, use, economics, and licensing of such energy sources, safety plays a key role. Since such facilities have been used for several decades, it is necessary to ensure the integrity and operability of vital elements of nuclear power plants in order to prevent, and otherwise reduce or mitigate the consequences of accidents that have occurred. Historically, plant designers have redesigned nuclear power plant systems to provide reliability in the form of redundant and varied safety features and to ensure that even in the event of abnormal and unplanned situations, the health and safety of workers and the public can be protected with a high degree of confidence.
For a method to be useful, it must have the following properties, namely: 1. High accuracy to minimize the possibility of false positive and false negative results 2. Stability so that single outliers or anomalies cannot severely corrupt the data series and create a false changepoint. 3. Independence from the main distributions, so that the method is as versatile as possible and can be applied in different areas and for different situations, processes, objects.
4. Low cost of computing to be able to work online without using a lot of computing power and without overloading the server.
5. Balanced sensitivity, that is, not too high so as not to react if the patient simply turned over on
the other side, but not too low so as not to miss the explosion of a reactor at a nuclear power plant.
This article will talk about a new non-parametric method for detecting changepoints in multivariate
time series based on the metric developed in
In section 2.1, we describe the state of the art in the field of detection of changepoints in multivariate time series. In section 2.2 we will consider the algorithm for calculating the Petunin statistic and its properties. In section 2.3 we will consider the algorithm for constructing the Fisher linear discriminant. In section 3.1 we present the results of numerous numerical experiments with a wide range of distributions. Section 3.2 considers possible applications of the proposed algorithm. For example, we can investigate the presence of various diseases in a virtual patient by measuring its parameters, such as heart rate, blood oxygen saturation and body temperature, which need to be monitored.
When considering a task of searching and recognizing change points of random
multidimensional time series there are many ideas for applying the results obtained. A change point of
time series is a point that separates two pieces of a series into ones that have different distributions.
The developed methods for solving the problem of finding a point of change in multidimensional time
series are usually separated into algorithms for streaming (for data coming one by one) and already
fully known (when the whole series is already given completely) data. Streaming data goes constantly
in time, and already known ones are given in their entirety. A detailed review of the change point
detection method in the already given time series was done in
The method discussed in (Navarro, Allen, and Weylandt, 2021) showed excellent performance of
the convex network clustering method, which unfortunately requires large computational costs. One
of the main methods for finding change points, discussed in
The proposed method is needed to process a continuous stream of data, can track outliers and
does not rely on any specific assumptions and known facts about the distribution of data. Below we
consider articles whose authors approached the problem from the same angle. In
In (Wang et al, 2019), the authors consider an algorithm that is used to stream data using a huge
matrix dependent on the dimension of the source data space. Similar methods discussed in
Analysis of papers on this topic shows that the most desirable qualities by searching for points of change in our problem are 1) stability, 2) high accuracy of calculations, 3) speed of work and 4) independence from basic distributions. Below, we describe such an algorithm based on so-called Petuninʼs statistics. 2.2.
The Petunin’s statistic (-statistic) is a measure of proximity between samples proposed by the Ukrainian mathematician Yuriy Petunin. It is used to test the hypothesis that the distribution functions of two samples are equal.
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) ≤ (3) … ≤ () and (′1) ≤ (′2) ≤ (′3) … ≤ ( ) - corresponding ordinal statistics and it is ′ necessary to determine whether they belong to the same distributions. Suppose that ( ) = ′() , then ( ( )) = ( ′ ∈ ( ( ), ( ))) = ( ) = − + 1
If we have a sample ′ ∈ ( (′1), (′2), (′3), … , (′ )), we can find the frequency ℎ random event
and confidence intervals (Δ(1), Δ(2)) for probability at a given level of significance , i.e
= { ∈ (Δ(1), Δ(2))} , ( ) = 1 −
According to
2 2 ℎ( ) + 2 − √ℎ( ) (1 − ℎ( )) + 4 ( ( ) – the density of the normal distribution).
determines the level of significance of the confidence interval
According to rule 3
we will call -statistics and it will be a measure of closeness (, ′) between samples and ′ . Let's substitute the obtained value ℎ in the formula for calculating confidence intervals, we will get a confidence interval = (Δ(1), Δ(2)) to test the hypothesis
with a level of significance approximately equal to 0.05
Fisher’s linear discriminant
2
2
1
2
The terms Fisher's linear discriminant and LDA are often used interchangeably, although Fisher's
original article
Suppose two classes of observations have means ⃗⃗ 0⃗, ⃗⃗ 1⃗ and covariances Σ0, Σ1. Then the linear combination of features⃗ ⃗ ⋅ will have means⃗ ⃗ ⋅⃗⃗ and variances⃗ ⃗ Σ⃗ ⃗ for = 0,1. Fisher defined the separation between these two distributions to be the ratio of the variance between the classes to the variance within the classes: = 2 2 ℎ = (⃗⃗ ⋅ ⃗⃗⃗ − ⃗⃗ ⋅ ⃗⃗⃗⃗0)2 ⃗⃗ Σ1⃗⃗ + ⃗⃗ Σ0⃗⃗ = (⃗⃗ ⋅ (⃗⃗⃗ − ⃗⃗⃗⃗0)) ⃗⃗ (Σ0 + Σ1)⃗⃗ 2
This measure is, in some sense, a measure of the signal-to-noise ratio for the class labelling. It can be shown that the maximum separation occurs when
⃗⃗ ∝ (Σ0 + Σ1)−1(⃗⃗⃗ − ⃗⃗⃗⃗0) When the assumptions of LDA are satisfied, the above equation is equivalent to LDA.
Be sure to note that the vector ⃗⃗ is the normal to the discriminant hyperplane. As an example, in a two dimensional problem, the line that best divides the two groups is perpendicular to ⃗⃗ .
Generally, the data points to be discriminated are projected onto ⃗⃗ ; then the threshold that best separates the data is chosen from analysis of the one-dimensional distribution. There is no general rule for the threshold. However, if projections of points from both classes exhibit approximately the same and ⃗⃗ ⋅ ⃗⃗⃗⃗1. In this case the parameter in threshold condition ⃗⃗ ⋅ > can be found explicitly: distributions, a good choice would be the hyperplane between projections of the two means, ⃗⃗ ⋅ ⃗⃗⃗⃗0 1 2 = ⃗⃗ ⋅
(⃗⃗⃗⃗0 + ⃗⃗⃗⃗1) = ⃗⃗⃗⃗1 Σ1−1⃗⃗⃗⃗1 −
⃗⃗⃗⃗0 Σ0−1⃗⃗⃗⃗0 1 2
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, witwhhich we will continue to work using the sliding window method. When we have a sample ( +1 , +2 , … , +ℎ ( +1, +2, … , +
ℎ) and find the projections on the line. a linear
Fisher discriminant for samples ( 1, 2, … , ℎ ) and 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. Shifting the sample ( +1, +2, … , + ℎ) 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), root mean squared error (RMSE), and 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 NRSMR > 0.5 the results can be considered as random. If a NRMSE is close to 0, then the results are considered good.
Let's consider a saltatory time series, which is composed of uniform distributions that practically do not overlap. On this time series, we will be able to test the shift hypothesis.
Table 1
0-99 100-199 200-299 300-399
U(65;75) U(100;110) U(65;75) U(70,90)
U(96.5;97.5) U(97.0;99.0) U(96.5, 97.5) U(97.5;99.0)
U(36.4;36.7) U(38.0;39.0) U(36.4;36.7) U(37.0;37.5)
21.13 583.21 16.95 21.13 0.21 As can be seen from Table 1 and Figure 1, the desired change point is 100. In Figure 2, we see that the p-statistic takes values greater than 0.95 only near intervals that have a distribution similar to the first one and the measures of error we can see in Table 2.
Let's consider a saltatory time series, which is composed of uniform distributions that are initially strongly overlap, then slightly overlap, and finally no overlap. On this time series, we will be able to test the shift hypothesis.
Table 3
0-99 U(60;70) U(96.0;97.0) U(36.4;36.7) 100-199 U(63;73) U(96.3;97.3) U(36.5;36.8) 200-299 U(70;80) U(97.0, 98.0) U(36.7;37.0) 300-399 U(85,95) U(99.0;99.9) U(37.5;37.8) As can be seen from Table 3 and Figure 3, the desired change point is 100. In Figure 4, 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 4.
Let's consider a saltatory time series, which is composed of normal distributions with different means that almost do not overlap. On this time series, we will be able to test the shift hypothesis. Table 5
0-99 N(70;2) N(96.0;0.15) N(36.5;0.05) 100-199 N(105;2) N(96.3;0.33) N(38.5;0.15) 200-299 N(70;2) N(97.0, 0.15) N(36.5;0.05) 300-399 N(80,4) N(99.0;0.25) N(37.3;0.98)
Let's consider a saltatory time series, 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.
Table 9
0-99 N(70;1) N(97.0;0.10) N(36.55;0.05) 100-199 N(70;5) N(97.0;0.50) N(36.55;0.25) 200-299 N(70;7) N(97.0,1.00) N(36.55;0.5) 300-399 N(70;10) N(97.0,1.50) N(36.55;0.75) As can be seen from Table 9 and Figure 9, the desired change point 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.
In this chapter, an algorithm for finding changepoints using Fisher's linear discriminant and Petunin's statistics was described. Experiments demonstrate fairly fast and accurate recognition when changing the distribution function for a wide range of distributions. This gives a clear presentation of the results, which means that this algorithm can be applied to risk-informed systems, in particular, to work in clinics, to monitor the condition of patients with coronavirus. [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, 130, 2021, 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, 114, 2018, 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] C. Gallagher, R. Killick, R. Lund, X. Shi, Autocovariance Estimation in the Presence of
Changepoints, 2021. arXiv preprint arXiv:2102.10669v2. DOI:10.48550/arXiv.2102.10669 [24] 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. [25] S. O. Tickle, I. A. Eckley, P. Fearnhead, A computationally efficient, high-dimensional multiple changepoint procedure with application to global terrorismincidence, 2020. arXiv preprint arXiv:2011.03599v2. DOI:10.1111/rssa.12695