The paper is devoted to the construction of the algorithm of piecewise linear approximation of time series, the distinctive feature of which is the preservation of sharp "peaks" and data outliers. As a basis, the iterative algorithm of piecewise linear approximation proposed by E. K. Bely in 1994 was taken. This algorithm was used to describe the experimental medical data on respiratory function of the lungs. The algorithm was modi ed to signi cantly increase the precision and to reduce the number of iterations. The rule of determining the optimal number of time series splitting by the minimum of the adjusted coe cient of determination was obtained. A new criterion for the algorithm stopping was proposed. As a testing data, the two-factor function of WeierstrassMandelbrot was used, which allows to generate data in a wide range of shapes and variability. In numerical experiment, the control parameters of the function were set by random variables with a uniform distribution law. The estimations of probability densities of the output parameters of the algorithm were obtained by the Monte Carlo method. The convergence of the approximation algorithm was studied and the regions of shape and variability parameters, at which the algorithm converges, were revealed.
The main approaches for time series modelling use smoothing methods [
In [
The main drawback of this algorithm is the long convergence (about a
thousand iterations) [
Therefore, in this paper the following modi cation of the algorithm is proposed: 1. The method of least squares is used to evaluate values of parameters of the linear functions. 2. The new split point is determined only if it falls within the interval between the point under consideration with the index i and the point with the index i + 2 ([ti + t; ti+2 t]), where t is set so that each interval ([ti; ti+1] and [ti+1; ti+2]) contains at least one point of the original time series. 3. The new conditions of loop stopping are based on three metrics of quality of the approximation.
The algorithm for determining the number of partition intervals is also proposed. 2
As a testing data, the two-factor function of Weierstrass-Mandelbrot [
The Weierstrass-Mandelbrot (W-M) function is continuous everywhere but di erentiable nowhere:
W (t) = : (1) (2) Approximation of <W (t) till the 2N -th term of the series is:
C(t) =
XN 1 m= N
It can be seen from Fig. 1, how the W-M function changes to di erent values of the b and D parameters. To simulate real time series, the ranges of parameters b and D were determined as b 2 [1:3; 1:9] and D 2 [1:1; 1:8] so that the W-M function simulation algorithm converges. A su cient number of series terms in the simulation of the W-M function equal to 30 (N = 30) is also determined.
As a metrics of quality of the approximation, the adjusted coe cient of determination (Ra2dj ), the mean absolute percentage error (MAPE), root-mean-square error (RMSE), MAPE for centered data, Ra2dj for centered data, Akaike information criterion (AIC), and di erence between the points (DBP) were used. With the exception of DBP, all other metrics are traditional metrics in statistics. The di erence between the points is calculated as follows: DBP = n1 Pin=1 jtik+1 tikj, tik is the partition point in the k-th iteration.
Numerical experiments showed some regularities in the change of metric values, which allowed formulating the conditions for stopping of the algorithm. From Tabl. 1, you can see that the DBP statistics become constant, and the MAPE statistics become cyclical with the length of the cycle 2.
This property is satis ed for di erent values of the shape (b) and the number of intervals of the partition (n) (see Fig. 2).
As a result, to determine the optimal number of iteration the stopping conditions of the algorithm can be formulated (Condition-K): 1. Ra2dj has stabilized or looped; 2. Di erence between the points (DBP) has stabilized or looped; 3. MAPE has stabilized or looped.
And the new algorithm of approximation time series is:
t) then ti+1 = ti+1, otherwise ti+1 = ti+1 3
Problem of optimal number of partition intervals The next problem is to determine optimal number of partition intervals n. To solve the problem the second algorithm is proposed. It uses Monte Carlo method.
Algorithm for estimation of number of partition intervals For every j 2 [1; J ]:
Get a uniformly distributed value of bj on the interval [1:3; 1:9] Get a uniformly distributed value of Dj on the interval [1:1; 1:8] Simulate W-M function with parameters bj and Dj Set the time interval t 2 [ts; tf ] Set n = nmin { initial number of intervals Set Kj = 30 { number of iterations of algorithm Set the initial partition of the interval: ts = t0 < t1 < : : : < tn 1 = tf While Condition-n
For every i 2 [1; n]:
Estimate coe cients of line regressions ai and bi for interval [ti; ti+1] by Ordinary Least Squares method
Calculate ti+1 the point of intersection of lines y = ai + bit and y = ai+1 + bi+1t
If ti+1 2 (ti + t; ti+2 t) then ti+1 = ti+1, otherwise ti+1 = ti+1 n = n + 1
Calculate MAPE and Ra2dj statistics Estimate average value of n, MAPE, Ra2dj
In this algorithm the stopping conditions to determine number of partition intervals (Condition-n) are below (also see Fig. 3): 1. The maximum number of intervals is reached (nmax); 2. sign[Ra2dj (n) Ra2dj (n 1)] sign[Ra2dj (n 1) Ra2dj (n 3. Ra2dj (n) has maximized to critical value;
On the Fig. 4 histograms of the output metrics of the algorithm are presented. The estimations of parameters: n = 25; Ra2dj = 0:968; M AP E = 0:013 show that the convergence of the algorithm is quite acceptable. 4
The presented algorithms make it possible to obtain an approximation of the time series that preserves its "peaks". The rst algorithm is designed to determine the optimal number of iteration. The second algorithm is designed to estimate number of partition intervals. Both algorithms were tested for the Weierstrass-Mandelbrot function. For each algorithm, the stopping conditions were formulated on the basis of time series approximation quality metrics.
As a result of numerical experiments, estimates of the following parameters were obtained.