We describe new nonparametric tests for detection change points of the time series, which are the points dividing the time series into segments of random values obeying different distributions. The proposed tests are based on the Dempster-Hill theory and generalizations of the Bernoulli scheme. To recognize the change points, simplified versions of the Klyushin-Petunin homogeneity test are proposed. The significance level of these tests does not exceed 0.05, and the accuracy is comparable to the original version. The tests have high sensitivity and specificity of recognizing the heterogeneity of two random samples with different means and the same variances or equal means but different variances. The described tests can be useful in a wide variety of areas from healthcare (for example, when analyzing time series generated by pulse oximeters) to IoT devices in industry and in everyday life.
The modern epoch is characterized by the intensive development of information networks and IoT technologies. There are more and more information sources that generate large amounts of sequential data that form time series which need to be processed in a short time. The problem has been exacerbated by the COVID-19 outbreak, which has raised questions related to the processing of signals from medical devices, tracking tools, etc. For example, a change in the distribution of random variables representing the level of oxygen in the blood of a patient with COVID-19 may require an immediate response from clinicians, which means that the change point in the time series generated by the pulse oximeter must be found in real time.
A time series is considered homogeneous if all its segments consist of random values that obey the same distribution. A change point is a point before and after which the values of the time series obey different distributions. Consequently, the problem of detecting the change point can be reduced to testing of samples homogeneity in adjacent segments of time series.
Change point detection methods are divided into online and offline. Online methods analyze
fragments of a time series in real time. Offline methods analyze a complete time series from the first
to the last point. A fairly detailed review of methods for finding change points in time series is given
in [
Since the problem of finding a change point can be reduced to the problem of samples
homogeneity, it should be mentioned that such tests are divided into parametric and nonparametric
tests. The former tests are based on the assumption that the time series data obey a specific (e.g.,
Gaussian distribution) or parameterized distribution [
Consider the problem of testing homogeneity of two samples which is equivalent to the problem of change point detection. Usually, to solve this problem the Kolmogorov–Smirnov test and the Mann– Whitney–Wilcoxon test are used. Recently, we proposed to use the Klyushin–Petunin test [25] and demonstrated its high performance [26].
Suppose that samples x = ( x1, x2,..., xn ) and y = ( y1, y2 ,..., ym ) are drawn from the distributions F1 and F2 , respectively. The null hypothesis states that x and y obey the same distribution, i.e. F1 = F2. The alternative hypothesis states that F1 ≠ F2.
Standard non-parametric two-sample homogeneity tests (Kolmogorov–Smirnov, Mann–Whitney– Wilcoxon, etc.) produce only one-sided confidence limits with the given significance level. This means that if the test statistics exceeds a given threshold the samples are considered as homogeneous, otherwise the answer is uncertain. Therefore, it is desirable to construct tests with two-sided confidence limits for a test statistics. Such tests is the Klyushin–Petunin homogeneity test [25] based on the Matveychuk–Petunin model [27–29]. It allow constructing a two-sided confidence interval with a given the significance level for both the true and false null hypothesis and estimating the probability of types I and II errors. 2.1.
Let x = ( x1, x2 ,..., xn ) ∈ F1 , y = ( y1, y2 ,..., yn ) ∈ F2 , and x(0) = −∞, x(1) , x(2) ,..., x(n) , x(n+1) = +∞ be corresponding variance series. The null hypothesis H0 states that F1 = F2 . If the null hypothesis is true, then due to the Dempster–Hill assumption [30] we have n + 1 Corollary 1. Selecting random natural numbers i and j such that i < j N times, for a p(k,n) = P ( yk ∈ ( x(i) , x( j) )) = ij p(k,n) = P ( yk ∈ ( x(i) , x( j) )) ≈ ij j − i j − i n + 1 , i < j. , i < j.
(1) sufficiently large N we have
Corollary 2. Selecting random natural numbers N times (N < n) from (1) we have j −1 p(k,n) = P ( yk ∈ ( x(1) , x( j) )) = ij n + 1 .
If F1 ≠ F2 , then p(k,n) significantly deviates from ij . Therefore, we must estimate a difference between observed relative frequency h(k,n) of the event yk ∈( x(i) , x( j) ) . To do this, we use a ij confidence limits ( pi(j1) , pi(j2) ) for the binomial proportion p(k,n) with given significance level β. Let ij j − i n + 1 Lxy be the number of the intervals ( pi(j1) , pi(j2) ) containing pij , hxy = 2Lxy n ( n −1) be the proportion of the intervals ( pi(j1) , pi(j2) ) containing p(k,n) , hyx = ij
is the proportion of the intervals ( pi(j1) , pi(j2) ) 2Lyx m (m − 1) containing p(k,m) in the scheme where the samples x and y are switched. Then, p-statistics [25] is ij
The original version of the Klyushin–Petunin test use N = ( pi(j1) , pi(j2) ) . Let L be the number of intervals ( pi(j1) , pi(j2) ) containing p(k,n) ij frequency of the random event { pij ∈( pi(j1) , pij
(2) )} with the probability 1 − β . Construct the confidence interval In for the probability of the event { pij ∈( pi(j1) , pij (2) )} with the given significance level (for definiteness, in this paper we use the Wilson confidence interval [31]). The decision rules may be formulated in the following way: 1) Original version. If the confidence interval In covers 0.95 then the null hypothesis is accepted, otherwise it is rejected. 2) First simplified version. Generate N random natural numbers i and j such that j > i, where N ≥ 30. Compute ρ( x, y ) using only intervals ( x(i) , x( j) ) with above mentioned i and j , and the confidence interval In . If In covers 0.95 then the null hypothesis is accepted, (n −1) n 2
confidence intervals and (2) is the relative otherwise it is rejected.
rejected.
3)
Second simplified version. Compute
ρ( x, y ) using only intervals ( x(1) , x( j) ) and the confidence interval In . If In covers 0.95 then the null hypothesis is accepted, otherwise it is
Analyzing the Figures 1-6, we see that the choice of the confidence intervals Iij does not effect to the final result: homogeneity measures are equivalent. Therefore, the family of homogeneity measures based on Dempster–Hills theory has high performance both for small and large samples, and the pstatistics may be considered as independent of the selection of the type of the confidence interval.
In [26] we have shown that in the context of change point detection the sensitivity and specificity of the Klyushin–Petunin test are higher than the sensitivity and specificity of the classical tests (Kolmogorov–Smirnov and Mann–Whitney–Wilcoxon). Now, we consider the simplified versions of the Klyushin–Petunin test and restricted ourselves with randomly selected 100 intervals ( x(i) , x( j) ) following to the recommendations given in [32]. We generated samples containing 40 random numbers obeying distributions which have the same mean and the different variances, the different means and the same variance, and different means and different variances, and averaged results on 10 runs.
Here N(µ, σ) is the Gaussian distribution with the mean µ and the standard deviation σ, U(a, b) is the uniform distribution on an interval (a, b), LN(µ, σ) is the lognormal distribution with the mean µ and the standard deviation σ, Exp(λ) is the exponential distribution with the parameter λ, Γ(α, β) is the gamma distribution with parameters α and β (Fig. 7–9). Consider a time series x1, x2 ,..., xn ,... . A change-point in the time series is a point xm such that a sample ( x1, x2 ,..., xm ) is drawn from a distribution F1 and a sample ( xm+1, xm+2 ,..., xn ) is drawn from a distribution F2 ≠ F1. Let the sample ( x1, x2 ,..., xn ) be fixing. Consider the sliding window ( xi , xi+1,..., xi+n ) , where i = 1,..., n. As i increases the sliding window “contaminated by the elements of the sample ( xn+1, xn+2,..., x2n ) . 1
1 0,6 0,4 0,2 0 1 0,8 0,6 0,4 0,2 0 1 0,8 0,6 0,4 0,2 0 1 0,8 0,6 0,4 0,2 0
0,6 0,4 0,2 0 1 0,8 0,6 0,4 0,2 0 1 0,8 0,6 0,4 0,2 0 1 0,8 0,6 0,4 0,2 0 0,6 0,4 0,2 0 1 0,8 0,6 0,4 0,2 0 1 0,8 0,6 0,4 0,2 0 1 0,8 0,6 0,4 0,2 0 distribution N (0,1) and the second segment ( x1, x2 ,..., x80 ) has the distribution N(3,1), the first sample is considered contaminated when m > 16 according to the original Klyushin–Petunin original test (see Table 1). When the change point is equal to 40 then the corresponding test is considered as failed. As expected, that the Klyushin–Petunin test in general is more robust and sensitive than its simplified versions.
The Table 1 shows that the Klyushin–Petunin test is sensitive both for distributions with different means and the same standard deviation (for example, N(0,1) vs N(1,4), and similar variants) and for distributions with the same means and the different standard deviations (for example, N(0,1) vs N(0,4), and similar variants). It also demonstrates the high performance for distributions with different means and standard deviations (exponential and gamma distributions). The less distributions differ from each other, the earlier change points are detected.
Table 1 demonstrates that the original Klyushin–Petunin test is most robust. The first and second simplified versions of the p-statistics are not monotonic. Due to the high sensitivity and robustness the original Klyushin–Petunin test may be considered as an effective method for testing samples heterogeneity and change-point detecting. The fact that first and second simplified versions are unstable is quite understandable, since they are based on the incomplete information (former) or random choice of intervals (latter). Therefore, despite on the complicated computations, the original version of the Klyushin–Petunin test is a preferred choice.
The accuracy, sensitivity and specificity of the simplified versions of the Klyushin–Petunin test are comparable with the original version of this test. However, the original version, despite of its computational complication, is more robust. All the versions of the Klyushin–Petunin test do not depend on assumptions about parameters of distributions and equally sensitive to difference between means and standard deviations of distributions. Their significance levels are less that 0.05. They do not require large storage for saving data. All the versions of the Klyushin–Petunin test are more effective than the Kolmogorov–Smirnov and Mann–Whitney–Wilcoxon tests for small samples (size less than 40).
[18] C. Zou, Y. Liu, P. Qin, and Z. Wang, “Empirical likelihood ratio test for the change-point problem, Statistics & Probability Letters, 77 (2007) 374–382. doi:10.1016/j.spl.2006.08.003. [19] M. Holmes, I. Kojadinovic, and J. Quessy, “Nonparametric tests for change-point detection a la Gomabay and Hovath, Journal of Multivariate Analysis, 115 (2013) 16–32. doi:10.1016/j.jmva.2012.10.004. [20] P. Fearnhead, Z. Liu, “On line inference for multiple change point problems, Journal of Royal
Statistical Society, Series B, 69 (2007) 203–213, doi:10.1111/j.1467-9868.2007.00601.x. [21] Y. Mei, “Sequential change-point detection when unknown parameters are present in the prechange distribution, The Annals of Statistics, 34 (2006) 92–122. doi:10.1214/009053605000000859. [22] D. Siegmund, Sequential analysis, Springer Series in Statistics. Springer-Verlag, New York, 1985. doi:10.1007/978-1-4757-1862-1. [23] H. Poor, O. Hadjiliadis, Quickest Detection, Cambridge University Press, Cambridge, 2009.
doi:10.1017/CBO9780511754678. [24] A. Tartakovsky, B. Rozovskii, R. Blazek, and H. Kim, A novel approach to detection of intrusions in computer networks via adaptive sequential and batch-sequential change-point detection methods, IEEE Trans. Signal Process, 54 (2006) 3372–3382. doi: 10.1109/TSP.2006.879308. [25] D. Klyushin, Yu. Petunin, “A Nonparametric Test for the Equivalence of Populations Based on a Measure of Proximity of Samples, Ukrainian Mathematical Journal, 55 2003 181–198. doi:10.1023/A:1025495727612. [26] D. Klyushin, I. Martynenko, “Nonparametric Test for Change-Point Detection in Data Stream, 2020 IEEE Third International Conference on Data Stream Mining and Processing (DSMP), 2020, pp. 281–286. doi:10.1109/DSMP47368.2020.9204193. [27] S. Matveichuk, Yu. Petunin, “A generalization of the Bernoulli model occurring in order statistics. I., Ukrainian Mathematical Journal, 42 1990 459–466. doi:10.1007/BF01071335. [28] S. Matveichuk, Yu. Petunin, “A generalization of the Bernoulli model occurring in order statistics. II., Ukrainian Mathematical Journal, 43 (1991) 728–734. doi:10.1007/BF01058940. [29] N. Johnson, S. Kotz, “Some generalizations of Bernoulli and Polya-Eggenberger contagion models, Statistical Papers, 32 (1991) 1–17. doi:10.1007/BF02925473. [30] B. Hill, “Posterior distribution of percentiles: Bayes' theorem for sampling from a population, Journal of the American Statistician Association, 63 1968 677–691. doi:10.1080/01621459.1968.11009286. [31] A. Pires, C. Amado, Interval Estimators for a Binomial Proportion: Comparison of Twenty Methods, REVSTAT-Statistical Journal, 6 (2008) 165–197. doi:10.1080/01621459.1968.11009286. [32] H. Freudenthal, “The ‘empirical law of large numbers’ or ‘The stability of frequencies’, Educ Stud Math, 4 (1972) 484–490. doi:10.1007/BF00567002.