Structural break detection is an important time series analysis task. It can be treated as a multi-objective optimization problem, in which we ought to find a time series segmentation such that time series theoretical models constructed on each segment are well-fitted and the segments are long enough to bear meaningful information. Metaheuristic optimization can help us solve this problem. This paper introduces a suite of new cost functions for the structural break detection task. We demonstrate that the new cost functions allow for achieving quantitatively better precision than the cost functions employed in the literature of this domain. We show particular advantages of each new cost function. Furthermore, the paper promotes the use of Particle Swarm Optimization (PSO) in the domain of structural break detection, which so far has relied on the Genetic Algorithm (GA). Our experiments show that PSO outperforms GA for many analysed time series examples. Last but not least, we introduce a non-trivial generalization of the top-performing state-of-the-art approach to the structural break detection problem based on the Minimum Description Length (MDL) rule with autoregressive (AR) model to MDL ARIMA (autoregressive integrated moving average) model.

Structural break detection is a time series analysis problem aiming to detect change points in a sequence of observations forming the time series. It is of particular value for areas such as economics or incident detection, in which we are interested in analysing time series in segments, and we need an algorithm to partition the data.

The structural break detection problem can be naturally formulated as an optimization task, where we wish to minimize a specific cost function defined for the produced time series segments. The rough idea is that each produced segment should represent a sequence of observations without a change point. This is typically measured using residuals of a theoretical model built on a segment and real time series values, which should be as small as possible. Unfortunately, simplifying the problem into just such an assumption leads to segments composed of single observations. Thus, the problem of structural break detection is typically formulated as a balance between two conflicting criteria: we wish to split the time series into segments without change points and, at the same time, maximize the length of the segments.

We may divide the existing structural break detection approaches into two groups. One uses predominantly statistical procedures. A prominent representative of this group is Bai and Perron (

In this paper, we present novel contributions to the domain of structural break detection using metaheuristic optimization. In particular:

We present a suite of new cost functions to be used for structural break detection.

We present a new methodology for cost function construction that assumes that the cost function value should contain a proportional weight for the variance of residual errors and take into account the relation between segment order and its length.

We present a generalization of Davis’s approach to the MDL with the ARIMA model. This generalization at the first sight may seem trivial compared to the initial Davis’s model based on AR. However, when broken down into parts, it required introducing model-specific optimizations to manage the computational complexity. The generalized model allowed for increasing accuracy of break detection in comparison to the AR-based approach.

To the best of our knowledge, this is also the first paper demonstrating the application of Ant Colony Optimization and Particle Swarm Optimization algorithms in conjunction with the Minimum Description Length rule to detect structural breaks in time series. In particular, we show that Particle Swarm Optimization typically slightly outperforms Genetic Algorithm. In addition, we show that PSO is easier to tune for the structural break detection problem than GA since the tunable hyperparameters are real numbers. We have also enriched PSO with an additional hyperparameter internally limiting the maximal number of detected intervals.

The essential contribution addressed in this paper is the new cost functions. We may summarize them as follows:

A new function, termed Elastic Minimum Description Length (EMDL), which is an extension of the classical Minimum Description Length (MDL) cost function. It allows the user to incorporate expert knowledge into the cost function. No other cost function provides such a possibility.

Two new cost functions based on the penalty cost function. Our extensions allow to produce better results for real-world time series by including a penalty for the structural break count, a penalty for the number of fitted model parameters, and emphasize the importance of model residuals.

An extension applicable to all the cost functions that adds a weight controlling the minimal allowed segment length. The literature of the domain reports that the techniques available so far employ strict rules concerning the minimal segment length. We propose to relax this approach. In the paper, we demonstrate that, in consequence, we gain flexibility because we eliminate the non-intuitive additional parameter that has to be set by a user.

An extension applicable to all the cost functions that punishes deviations from a linear trend which helps to detect shifts in data with the trend. Experiments have proven that this method works well also for data with a nonlinear trend. We show that including this extension allows detecting the exact point of trend shift (of inflection), even if the underlying theoretical time series model is not sensitive to it.

Proposed framework for structural break detection was tested using a suite of synthetic and real-world time series. In the paper, we address the properties of the proposed approach and compare it with the existing methods.

The remainder of the paper is structured as follows. Section

The problem of detecting structural breaks in time series is well-recognized in the literature. There are two base variants: online and offline, the use of which is determined by the practical setting in which we need to execute this task. There were many works devoted to the online variant such as these by Tartakovsky (

Offline structural break detection has its own subvariants. The most classical division of available methods is into two groups. The first group aims at finding at most one changepoint (AMOC) detection, where the aim is to state if a time series contains one structural break and, subsequently, where it is located. The popular methods include cumulative sums (CUSUM) (Yang and Zhang,

We can also divide the existing structural break detection methods according to how the structural break is defined and found. The most straightforward approach is a canonical segmentation problem, where the only parameter analysed during breakpoint detection is time series mean. Numerous works have been dedicated to this approach, and they have been thoroughly discussed by Cho and Kirch (

This article is devoted to multiple structural break detection in an offline manner, so let us describe analogous leading and popular methods used for the task. As Shi

A distinct category can be assigned to the methods which sequentially analyse time series and are able to increasingly add new structural breaks, such as the method proposed by Bai and Perron (

The first mentioned family of approaches (recursive one) generally uses AMOC methods to detect one structural breaks and later run the same AMOC method for chunked data. The base method in the area is binary segmentation (BS) (Scott and Knott,

Many different approaches were proposed that can be described as general methods that jointly analyse entire time series. Some are using Bayesian learning or other probability-theory-based techniques for changepoint detection. In this line of research, the algorithms typically employ recursion to partition the data into segments. We envision that the changepoints of interest separate these segments. Bayesian approaches use different methods to solve the problem. Another technique was delivered by Li

Another notable way to solve the problem of locating multiple structural breaks in a time series is Cumulative Sums of Squares (CUSUM), studied by Inclan and Tiao (

Other approach to the problem was moving sum (MOSUM) procedure. Their method is essential in canonical segmentation problem. It was recently used, for instance, by Cho and Kirch (

It is vital to notice that many of known approaches use constraint on the minimum distance between two consecutive structural changes. The approach is very popular and was used, for example, by Davis

As a side note, we have observed a growing number of papers elaborating on the benefits of including a structural break detection step in time series forecasting procedures. Among researchers focusing on this aspect, we find Smith (

The last group of methods for solving the task we want to discuss are evolutionary algorithms. In particular, it is worth mentioning the works of Davis

The genetic algorithm was also considered in the works of Doerr

Éltetö

Many of the methods used for structural break detection require an objective function that allows comparing particular structural change positions. Choosing an appropriate objective function is not easy because of the need to simultaneously fit the data model and minimize the number of model parameters, as state (Shi

Penalty function methods have been analysed as well. For example, Hall

For more complex approaches, a fairly obvious choice was to check known information criterion models. Akaike Information Criterion (AIC), Bayesian Information Criterion (BIC), or modified Bayesian Information Criterion (mBIC) can be employed (Zhang and Siegmund,

In recent years, the principle of Minimum Description Length (MDL) formulated by Rissanen (

In this section, we provide basic information related to the background knowledge behind the proposed approach.

Time series can be simply described as a sequence of values observed in time. There are many different ways to model time series. One of the very popular is the use of models from the AutoRegressive Integrated Moving Average (ARIMA) family. The simplest model belonging to this family is the autoregressive model (AR), which can be written as

The model can be briefly expressed as

A time series structural break is a place in the time series where data changes its characteristics. It can be a change in the time series mean, variance, or a point where a trend has emerged or disappeared. The most often-mentioned definition says that it is a place in the time series where the time series model or one of its parameters changes (for example, Cheng

In this work, we use metaheuristic optimization-based algorithms to solve the problem of time series structural break detection. We selected Ant Colony Optimization (ACO), Particle Swarm Optimization (PSO), and Genetic Algorithm (GA). The algorithms mentioned are all metaheuristics, which means that they do not guarantee that an optimal solution will be found. However, they can find a good-enough solution in a relatively short time. This property makes them indispensable in many engineering applications, see Abdel-Basset

ACO, PSO, and GA are based on an analogous idea that the algorithm operates on a collection of candidate solutions called population. The procedure is iterative. In each iteration, the population undergoes specific modifications, and in this manner, candidate solutions are constructed or modified. An essential part of these algorithms is a cost function that evaluates how good a particular candidate solution is. Since these are heuristic optimization approaches, termination criteria concern either a count of performed iterations or a count of iterations without any improvement.

ACO is a method proposed and developed by Dorigo and Stützle (

Ants construct solutions in a probabilistic, step-wise manner. If we have an iteration

The general scheme of ACO is presented in Algorithm

General schema of ACO

PSO is patterned on the behaviour of birds’ flocks or schools of fish. In contrast to ACO, the algorithm operates in a continuous space. The population is interpreted as a collection of particles. Each particle has its own location, memory, and velocity. The location of a particle

The location of a particle is updated according to:

The general flow of the PSO is presented in Algorithm

General schema of PSO

GA is a long-known evolutionary algorithm that uses a population of solutions. Each solution is represented by a chromosome, which consists of genes. The population is modified by three fundamental operations: selection, crossover, and mutation, which are performed during each iteration. These operations are defined very generally. Thus, so many variants of the GA have arisen. The first operation is selection, which aims to pick the best individuals from the population. The two most common selection mechanisms are proportional selection and tournament selection. A mutation usually makes a minor change to the solution. For example, in the popular bit flip mutation for binary encoded chromosomes, one or more bits are randomly selected and inverted. There are other types of mutations, such as swap mutation, truncation mutation, or inversion mutation. Crossover initially results in several parent solutions that combine to form one or more offspring. Popular crossover methods are uniform crossover, one-point crossover, or multi-point crossover. In many situations, applying standard mutation or crossover methods is impossible, and the need to modify them or create custom, problem-specific crossover or mutation operators arises.

The general scheme of the GA is presented in Algorithm

Pseudocode of GA

The island model is one of the approaches to perform multi-population optimization. In the model, there are several populations located on several islands. After every

The island model is a simple, yet effective method to get good results fast. It is often used with the genetic algorithm but can also be applied to other evolutionary algorithms.

Selecting a cost function to measure the quality of solutions is a critical problem in metaheuristic optimization. Constructing a suitable cost function for the structural break detection problem is difficult because we need to minimize the model errors and the number of structural breaks and balance the two.

The literature offers various solutions to this problem; more information is available from Farsi

Davis

Let us recall the key contributions of this paper:

a generalization of Davis’s approach to the MDL with the ARIMA model,

new cost functions: Elastic MDL – a variant of MDL giving more flexibility to the user and new functions based on penalty cost suitable to process real-world time series,

including a weight for punishing (controlling) minimal allowed interval length,

an extension of the cost function that takes into account deviations from a linear trend observed on time series segments,

new cost functions using relations between segment’s order and length,

in this study, PSO and ACO algorithms, in conjunction with the Minimum Description Length rule, are used for the first time in the task of structural break detection in time series.

In the following subsections, we present them in detail.

Let us define the MDL function for the ARIMA model based on Eqs. (

The defined function in Eq. (

In this subsection, we address new cost functions. Each of them was defined in two variants – for the AR and ARIMA model.

This extension relies on penalties for structural breaks count, model parameter count, and variation of model fitting error. The version for the AR model is defined as:

We defined the second cost function to give residual errors higher importance. The variant delivered for the AR model looks as follows:

The rationale was to partition the time series such that the segments are as long as possible, but short enough to fit the theoretical model well. The shorter the segment, the easier it is to fit a theoretical model. At the same time, for practical reasons, too many segments may not be helpful.

These conflicting goals (long segments with good theoretical models) were coded differently by means of different objective functions.

The third idea was to use the MDL function to give users more flexibility and allow them to tune it to their preferences. The version for the AR model is defined as:

The following cost function is based on the assumption that structural break selection is satisfactory when the variance of residual errors is small, and the orders of assigned models are small compared to the adjusted segment’s length. The version for AR was defined as

The final cost function is a combination of penalty and division cost functions. We defined it for the AR model as

Comparing this cost function with the plain MDL (see Eq. (

We proposed two extensions to the cost functions that can increase their capabilities.

The first extension is a weight for enforcing minimal allowed interval length. A common pitfall of structural break detection algorithms is that they find too short, insignificant time series segments. So far, the problem has mostly been solved by inserting a strict ban on generating time series segments shorter than a certain threshold. Such a tough, binary solution is not clear and justified. Thus, we propose a new attempt to solve this problem. We suggest adding to cost functions a penalty term defined as follows:

The second extension was dedicated to the methods that do not account for trends. We propose to solve this deficiency by adding a weight to a cost function to estimate the deviation from a linear trend. We can define it as

Both extensions can be applied with the use of additional parameters, giving them suitable impact.

To implement the ACO algorithm for the structural break detection problem, we have modified the rule of ranking possible edges from that presented in Eq. (

The method allows estimating the count of structural breaks after the

Since PSO is an algorithm operating in a continuous space, its application to the structural break detection problem requires adaptations. We have solved this problem by creating an upper limit on the produced structural breaks (

We used the traditional genetic algorithm formulation with tournament selection, with two-point crossover. We used mutation similar to bit flip mutation, where each bit described if an

While designing the new solutions, we paid a lot of attention to the issue of computational complexity. It was critical since the problem at hand involved intensive computations. The algorithms we used needed information about cost function value linked with time series segments. The information could be calculated dynamically during the computation of a structural break or eager (earlier) before the computation. The second strategy seems more straightforward as we divide our task into two sub-tasks: computation of a cost function for all possible segments and finding structural breaks. It is viable only for short time series because executing it for long time series would induce many redundant calculations.

Let us address in more detail the computational complexity of finding structural breaks. We will mark population size as

In each iteration, GA performs selection, mutation, crossover, and evaluation. The time complexity of two-point crossover and mutation is

ACO performs three operations: construction of a new solution, evaluation, and updating pheromone trace in each iteration. During solution construction, an ant calculates probabilities and needs knowledge of cost function at analysed time series segments, which is done in

Sorting solutions calculated by ants in time

Pheromoneevaporation in

Putting new pheromone int time

In this section, we present the experiments’ outcomes to validate the quality of the proposed novel methods. The scope of the study covered both artificial and real-world time series representing different situations. Most of the analysed time series were relatively short, since conventional structural break detection tasks are executed for such cases. We analysed eight synthesized time series, which included instances with different numbers of structural breaks, appearing and disappearing trends, and changing time series mean and variance. There was also an example of a white noise time series with added variation, in which the algorithms should not detect any structural breaks. We have defined “test cases” of synthetic time series. We assumed some underlying time series properties for each test case and then generated each test case multiple times, maintaining the same underlying properties but with some random noise. This entailed that the experiments were repeated multiple times for each test case. Specific differences between particular time series instances within a single “case” arise only because we draw values, but the parameters of distributions we use stay the same.

On top of ten synthetic series, we used two real-world time series representing the power demand of a fridge freezer in a kitchen. They come from the Electrical Load Measurement dataset by Murray

The dataset is available at

Let us list and briefly discuss synthetic test cases:

Time series composed of two segments with the same segment variance but different segment mean (an example is given in Fig.

Time series composed of two segments with the same mean and different segment variance (an example is given in Fig.

Time series composed of two segments generated with the use of different AR models (

Test case without structural breaks. It is a white noise series with a small random distortion (example is in Fig.

Example time series coming from artificial test cases analysed in the paper.

Two real-world time series describing fridge freezer power demand.

Test case where time series start with a long and low-variance segment, but at the end there is a short, but intense, rise of values (example is in Fig.

Time series composed of three segments, where the first and the third segments are identical and have a fixed mean and variance. The segment in the middle has a larger variance than the other two segments (see Fig.

Test case, which follows a parabolic pattern with low variance of data points. An example is given in Fig.

Time series generated using the AR model based on the equation:

To eliminate the possible bias arising due to the randomness of the empirical methodology of this study, we have been performing multiple repetitions of the experiments. For each synthesized test case, we generated 10 time series instances with different random number generator seeds. Experiments were executed for each generated time series. As a result, we performed 10 repetitions of each experiment for each test case. Our motivation was to ensure a reasonable variability of the data by maintaining the same data generation process that relies on drawing from distributions. To keep the same level of objectivity in result evaluation, in the case of the real-world time series, we were also repeating the experiments 10 times.

The outcomes of the experiments that were conducted involving different algorithms were compared with each other and with the outcomes obtained by other researchers. We assume three state-of-the-art methods, which we use for such comparisons. The first is the method proposed by Bai and Perron (

We propose two metrics for the evaluation of the outcomes of structural break detection procedures:

break point difference (BPD) – absolute value of the difference between the found and correct count of structural breaks,

score value (SC):

At first, we compared results obtained with the MDL, SPF1, SPF2, EMDL, DCF, and PDCF cost functions. We used both the AR and ARIMA models and both versions of the cost function: with and without a weight for deviation from a linear trend. The experiments concerned seven synthetic time series and two real-world time series. The only omitted case is Fig.

Experiments were performed using PSO with parameters

A detailed discussion on optimization algorithms hyperparameters and their fitting is provided in Section

Our results were evaluated with the use of BPD and SC metrics and conclusions attained with use of both were very similar. The best results (assessed with the use of BPD and SC metrics) were obtained consecutively for configurations: EMDL

BPD score for the best-performing cost functions.

Cost function | Test case | ||||||||||

MSE | Mean | ||||||||||

EMDL |
– | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 1.0 | 1.1 | 0.3 | 0.27 |

EMDL |
– | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.1 | 1.0 | 1.2 | 0.3 | 0.29 |

MDL |
– | 0.1 | 0.0 | 0.0 | 0.0 | 0.0 | 0.1 | 1.0 | 1.3 | 0.2 | 0.30 |

MDL |
– | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 2.5 | 1.2 | 0.5 | 0.47 |

DCF |
– | 0.0 | 0.0 | 0.0 | 0.9 | 0.0 | 0.0 | 0.8 | 2.0 | 1.0 | 0.52 |

PDCF |
– | 0.0 | 0.0 | 0.0 | 1.0 | 0.0 | 0.0 | 0.7 | 2.0 | 1.0 | 0.52 |

SPF |
– | 0.8 | 1.0 | 0.3 | 0.0 | 1.0 | 2.0 | 0.4 | 0.5 | 0.1 | 0.68 |

SPF2 |
– | 0.0 | 1.0 | 0.2 | 0.0 | 0.5 | 2.0 | 2.8 | 0.3 | 0.0 | 0.76 |

SPF |
+ | 0.2 | 0.7 | 0.8 | 0.1 | 1.4 | 0.4 | 3.7 | 0.0 | 0.0 | 0.81 |

SPF2 |
+ | 0.1 | 0.9 | 0.8 | 0.1 | 1.0 | 0.8 | 3.9 | 0.0 | 0.1 | 0.86 |

SC score for the best-performing cost functions.

Cost function | Test case | ||||||||||

Type | MSE | Mean | |||||||||

EMDL |
– | 0.019 | 0.001 | 0.007 | 0.000 | 0.013 | 0.004 | 2.062 | 2.265 | 1.203 | 0.619 |

EMDL |
– | 0.006 | 0.001 | 0.009 | 0.000 | 0.011 | 0.224 | 2.036 | 2.465 | 1.181 | 0.659 |

MDL |
– | 0.225 | 0.001 | 0.007 | 0.000 | 0.028 | 0.218 | 2.062 | 2.673 | 1.051 | 0.659 |

MDL |
– | 0.019 | 0.001 | 0.009 | 0.000 | 0.006 | 0.013 | 5.023 | 2.465 | 1.432 | 0.996 |

DCF |
– | 0.050 | 0.008 | 0.009 | 1.800 | 0.060 | 0.010 | 1.679 | 4.062 | 2.062 | 1.082 |

PDCF |
– | 0.050 | 0.008 | 0.008 | 2.000 | 0.081 | 0.018 | 1.473 | 4.062 | 2.062 | 1.085 |

SPF |
– | 1.652 | 2.062 | 0.624 | 0.000 | 2.062 | 4.062 | 1.087 | 1.042 | 0.293 | 1.431 |

SPF2 |
– | 0.006 | 2.062 | 0.505 | 0.000 | 1.045 | 4.062 | 5.659 | 0.630 | 0.000 | 1.552 |

SPF |
+ | 0.421 | 1.517 | 1.639 | 0.200 | 2.866 | 0.891 | 7.418 | 0.010 | 0.000 | 1.662 |

SPF2 |
+ | 0.215 | 1.902 | 1.640 | 0.200 | 2.015 | 1.699 | 7.844 | 0.009 | 0.217 | 1.749 |

Let us discuss the behaviour of various cost functions in more detail. For the simplest cases, analysed functions perform very well. For test case

Most of analysed methods correctly find the place where the variance changes (test case

Most of presented cost functions detect change between two different AR models very well (case

Most of presented cost functions correctly solved the task of processing white noise time series (case

Test case

Result obtained for the test cases composed of three segments of the same length (case

The next test case concentrated on a rather theoretical example, where time series was the shape of a parabola (see Fig.

The last two examples were the real-world time series describing fridge freezer power demand. We analysed two examples. First, where the freezer was turned on and turned off after some time (case

We have observed that the proposed cost functions enhance time series processing capabilities for structural break detection algorithms. Noteworthy, for all of the proposed cost functions, we can find a set of parameters that works very well for various test cases. Furthermore, we will demonstrate in Section

The empirical experiments have shown that the cost functions using the ARIMA model are very good, and in many cases, they are better than the ones using the AR model. Their weak point is computational complexity, which is higher, and this difference grows as the time series length increases. For example, it took only 0.3s for the AR model to calculate MDL cost function partial values for all possible time series segments for the test case with 50 data points and 190.0s for ARIMA. In contrast, for a case with 100 data points, it took 1.4s and 937.7s, respectively. This shows that cost functions using the ARIMA model are helpful for short time series. In practice, it is not a severe limitation for many real-world domains applying break detection methods (such as economics), in which relatively short time series are of interest.

The proposed objective functions punish for deviations from theoretical models constructed on developed segments. Therefore, if these models cannot reflect the underlying data well, there is no reasonable justification to apply this model. If the data contains a clearly visible and changing trend, the recommended choice is an objective function that punishes deviations from theoretical models. The component that punishes for short intervals should we weighted as less important. Punishing for deviations from a theoretical model is a lousy strategy for high-variance time series or if variance is the crucial distinction for subsequent segments. In this case, punishing for short segments and diminishing the punishment for deviations from theoretical models is much better.

In this section, we present a study on the impact of hyperparameters on the heuristic algorithms. We performed these experiments with the use of classical AR MDL cost function without the MSE modification due to its good reputation and long presence in literature. The objective of these experiments was to demonstrate technical validity of parameter selection for the optimizers. Such a study is necessary in methods utilizing heuristic approaches. While it does not deliver new results concerning the algorithmic level, it shows the behaviour of the procedure and allows to verify its stability and robustness.

We performed tests for 3 configurations of PSO:

All the experiments were performed with maximal limit of 10 detected structural breaks. Tables

BPD score for different PSO configurations.

Config. | Test case | |||||||||

Mean | ||||||||||

0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 2.5 | 1.2 | 0.5 | 0.467 | |

0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 2.6 | 1.7 | 0.9 | 0.578 | |

0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 2.6 | 1.9 | 1.0 | 0.611 |

SC score for different PSO configurations.

Config. | Test case | |||||||||

Mean | ||||||||||

0.019 | 0.001 | 0.009 | 0.000 | 0.006 | 0.013 | 5.023 | 2.465 | 1.432 | 0.996 | |

0.019 | 0.001 | 0.009 | 0.000 | 0.006 | 0.018 | 5.224 | 3.463 | 1.936 | 1.186 | |

0.019 | 0.001 | 0.009 | 0.000 | 0.006 | 0.014 | 5.222 | 3.862 | 2.062 | 1.244 |

According to the two presented metrics, the best results achieved using PSO were for the parameter configuration

The most interesting observations were made for the real-world time series. All named configurations did not locate structural breaks in the correct locations and found none or one structural break close to the end of the time series. The detection of such structural breaks (near or precisely at the end of a sequence) is a side effect of the algorithm’s operations. During the optimization procedure, each structural break location is treated as a variable, and it can change its position in time series. A variable at the end of the time series is treated as if the structural break did not exist. This, however, may result in the observed adverse effect. If a time series is challenging, we may end up with incorrectly identified structural breaks near the end. The described behaviour did not occur for configuration

BPD score for different GA configurations.

Config. | Test case | |||||||||

Mean | ||||||||||

0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 1.5 | 2.0 | 1.0 | 0.500 | |

0.1 | 0.0 | 0.0 | 0.0 | 0.1 | 0.0 | 1.5 | 2.0 | 1.0 | 0.522 | |

0.1 | 0.0 | 0.2 | 0.0 | 0.0 | 0.0 | 1.4 | 2.0 | 1.0 | 0.522 | |

0.1 | 0.0 | 0.1 | 0.0 | 0.0 | 0.0 | 1.6 | 2.0 | 1.0 | 0.533 |

SC score for different GA configurations.

Config. | Test case | |||||||||

Mean | ||||||||||

0.029 | 0.030 | 0.012 | 0.000 | 0.049 | 0.067 | 3.027 | 4.062 | 2.062 | 1.038 | |

0.235 | 0.018 | 0.021 | 0.000 | 0.249 | 0.053 | 3.028 | 4.062 | 2.062 | 1.081 | |

0.245 | 0.041 | 0.417 | 0.000 | 0.065 | 0.081 | 2.827 | 4.062 | 2.062 | 1.089 | |

0.244 | 0.028 | 0.211 | 0.000 | 0.039 | 0.054 | 3.230 | 4.062 | 2.062 | 1.103 |

For the GA we ran the experiments on a grid of parameters. We have tested mutation probabilities from the set

Both metrics indicated the same best-performing parameter configurations listed below:

The results calculated for listed configurations are in Tables

The analysis showed that it was generally better not to use the direction modification. The average value of the SC metrics of the results concerning the direction modification was 1.467, while the average for the results without it was 1.187. For various values of mutation probability, crossover probability, and tournament size, mean SC metrics fluctuations were very little, especially compared to concerning mutation modification influence.

Qualitative analysis of the experiments’ results showed that the outcomes were quite similar for all tested GA parameters. There were minor differences in the count of detected structural breaks in a few cases.

SC score for different ACO configurations.

Config. | Test case | |||||||||

Mean | ||||||||||

0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 1.8 | 2.0 | 1.0 | 0.53 | |

0.0 | 0.0 | 0.1 | 0.0 | 0.0 | 0.0 | 1.8 | 2.0 | 1.0 | 0.54 | |

0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 1.9 | 2.0 | 1.0 | 0.54 |

SC score for different ACO configurations.

Config. | Test case | |||||||||

Mean | ||||||||||

0.029 | 0.001 | 0.011 | 0.000 | 0.006 | 0.014 | 3.625 | 4.062 | 2.062 | 1.090 | |

0.013 | 0.001 | 0.211 | 0.000 | 0.006 | 0.024 | 3.629 | 4.062 | 2.062 | 1.112 | |

0.029 | 0.003 | 0.009 | 0.000 | 0.006 | 0.031 | 3.823 | 4.062 | 2.062 | 1.114 |

The experiments with ACO were conducted for a grid of parameters. We tested different combinations of parameters assuming the following sets of values of interest: the evaporation parameter

Subsequently, we looked into each parameter and analysed its role in the achieved outcomes. As BPD and SC metrics usually give similar conclusions, but the SC metric provides more information, the discussion below refers to the average value of the SC. The results showed that:

a more favourable value for the evaporation coefficient is 0.9 (SC 1.289) than 0.5 (SC 1.383),

a slightly better value of importance of the pheromone parameter is 1.0 (SC 1.335) than 1.5 (SC 1.337),

2 is a slightly better value than 5 for the weight of fragment rank (achieving the average SC of 1.321, in comparison to 1.350),

for the importance of estimated break count parameter value 2 (SC 1.292) is a better choice than 1 (SC 1.379),

increasing the count of elitist ants had a little contribution towards the improvement of the score (SC 1.345 for value 2 and 1.327 for 4),

a better value of scale of the pheromone update parameter was 0.05 (SC 1.324) than 0.2 (SC 1.348),

better results were obtained with the use of a limit of 10 maximum detected structural changes (SC 1.319) than with the use of a limit of 4 (SC 1.353).

The most significant conclusion refers to the structural break count limit. This limit allows for accelerating calculations and achieving better results for test cases where the desirable structural break count is less than this limit. The experiments showed that more favourable results were obtained with a bigger limit, which indicates that the algorithm can very well generalize and detect fewer breaks than this limit, which is an essential feature for many possible real-world applications of structural break detection methods.

The proposed approaches were compared with two selected state-of-the-art methods: Bai and Perron (

We performed experiments using the Bai-Perron method with the same test cases as in previous tests. Mean BPD and SC for these examples and general mean are presented in Table

BPD and SC results for the Bai-Perron method.

Test case | ||||||||||

Mean | ||||||||||

BPD | 0.1 | 0 | 0.7 | 0.2 | 0 | 0.4 | 4.1 | 1.0 | 4.0 | 1.167 |

SC | 0.335 | 0.081 | 1.492 | 0.400 | 0.066 | 0.864 | 8.214 | 2.020 | 8.058 | 2.392 |

We can see that the Bai-Perron method was substantially worse than the presented methods. Qualitative analysis showed that the Bai-Perron method achieved moderately satisfying results for cases

We compared our work also to the state-of-the-art ClaSP algorithm by Ermshaus

The results covered in Table

BPD and SC results for the ClaSP method.

Metric | Mean | |||||||||

BPD | 1.0 | 1.0 | 0.1 | 0.0 | 1.0 | 2.0 | 1.0 | 2.0 | 1.0 | 1.011 |

SC | 2.062 | 2.062 | 0.235 | 0.000 | 2.062 | 4.062 | 2.062 | 4.062 | 2.062 | 2.074 |

Contrary to previous experiments, to process the real-world dataset published by Davis

Table

Davis

Subsequently, we compared our results against those calculated using Bai-Perron’s and ClaSP methods. They are also given in Table

It is essential to state that the means and standard deviations presented in Table

Still, to provide a deeper analysis, Table

Comparison with the state-of-the-art methods for case

Algo. | Config. | Cost Function | Mean 1 | Std 1 | Mean 2 | Std 2 |

Davis |
– | MDL |
0.50000 | 0.00200 | 0.74200 | 0.00700 |

Bai-Perron | – | – | 0.49898 | 0.07827 | 0.73511 | 0.03329 |

ClaSP | – | – | 0.62666 | 0.16288 | 0.73706 | 0.00674 |

PSO | EMDL |
0.50020 | 0.00373 | 0.75039 | 0.00050 | |

PSO | ARIMA MDL | 0.50127 | 0.00291 | 0.75000 | 0.00159 | |

GA | EMDL |
0.50068 | 0.00252 | 0.75000 | 0.00260 | |

PSO | PDCF |
0.50068 | 0.00412 | 0.74932 | 0.00393 |

First and foremost, Table

Our approach is very good in comparison with state-of-the-art methods. In our opinion, it is also more versatile and customizable. We have delivered not a single method but a suite of methods. Finally, we may emphasize that our results are much better than those obtained with Bai-Perron’s and ClaSP methods. These two algorithms struggle to find two structural breaks. Even if they find two structural breaks, they locate them inaccurately.

The discussed experiments have proven the key statements from the introductory section of this paper. In our studies, we have delivered a suite of new cost functions to be used for structural break detection with the help of metaheuristic optimization.

The experimental procedure was designed to ensure that a satisfying number of repetitions of a model construction process was performed. We have paid attention to the three aspects in which properties influence the processing outcome. To eliminate chances of drawing unfounded conclusions, we applied the following schema:

We have drawn 10 (different) time series for each synthetic time series case. The generative process stayed the same within one case, but time series-specific values were different.

For real-world time series, each experiment was repeated 10 times.

We have fixed the metaheuristic methods’ hyperparameters to a selected configuration and run the same configuration for different specifications of the break detection algorithm to test one aspect.

We have fixed the structural break detection algorithm specification for a few configurations and tested the impact of metaheuristic algorithm hyperparameters.

The introduced changes allowed us to improve the qualitative and quantitative outcomes of the structural break detection task. In particular, concerning the state-of-the-art algorithms, we managed to:

improve numerical accuracy of the results, especially when analysing time series containing trend,

show that ACO and PSO methods are not worse at solving the task than GA,

give more flexibility to the experts (potential users of our method) by allowing, optionally, to set parameters that control the count of detected structural breaks.

Each new cost function or modification presented in this paper targeted a different new property. The Elastic MDL method guarantees results similar to the state-of-the-art techniques but introduces the possibility of adapting the model’s shape to the user’s preferences. Methods using a penalty for deviation from a linear trend work well for real-world time series. DCF and PDCF cost functions capture the new understanding of cost functions designed for structural break detection problems. Let us recall that these two take into account the variance of residuals.

The experiments have shown that using ARIMA often helps to achieve better results than AR. Thanks to the use of metaheuristic approaches, in such cases, the optimization procedure adjusts the model’s shape and allows us to obtain more accurate results.

Our studies in this area can be continued. The most interesting future research area is extending this approach to time series with multiple variables.

There is a straightforward solution to this task because the proposed formulas are additive, cf. equations (

An alternative path worthy of further inspection when working with multivariate time series could be to reduce time series dimensionality (perhaps even to one dimension) and proceed with the approach presented in this paper. The potential problem that may arise when working with such a solution is that the procedure may become intangible. We would have to employ an external algorithm whose properties will heavily influence the processing outcome. Analysing the performance of such a data processing pipeline will be more complex, as we need to cover this additional algorithm.

Finally, the most advanced solution would be to replace ARIMA/AR, predominantly for univariate time series, with a model suitable for dealing with multiple variables. VAR (Vector Autoregression) can be fused to the proposed framework in such a case.