On the Improvements of Metaheuristic Optimization-Based Strategies for Time Series Structural Break Detection

Burczaniuk, Mateusz; Jastrzębska, Agnieszka

doi:10.15388/24-INFOR572

Informatica

On the Improvements of Metaheuristic Optimization-Based Strategies for Time Series Structural Break Detection

Volume 35, Issue 4 (2024), pp. 687–719

Mateusz Burczaniuk Agnieszka Jastrzębska

https://doi.org/10.15388/24-INFOR572

Pub. online: 1 October 2024 Type: Research Article

Open Access

Received
1 October 2023

Accepted
1 September 2024

Published
1 October 2024

Abstract

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.

References

Abdel-Basset, M., Abdel-Fatah, L., Sangaiah, A.K. (2018). Metaheuristic algorithms: a comprehensive review. In: Computational Intelligence for Multimedia Big Data on the Cloud with Engineering Applications, pp. 185–231.

Altansukh, G., Osborn, D.R. (2022). Using structural break inference for forecasting time series. Empirical Economics, 63, 1–41.

Bai, J., Perron, P. (1998). Estimating and testing linear models with multiple structural changes. Econometrica, 66(1), 47–78.

Bai, J., Perron, P. (2003). Computation and analysis of multiple structural change models. Journal of Applied Econometrics, 18(1), 1–22.

Bai, J., Duan, J., Han, X. (2024). The likelihood ratio test for structural changes in factor models. Journal of Econometrics, 238(2), 105631.

Bardwell, L., Fearnhead, P., Eckley, I.A., Smith, S., Spott, M. (2019). Most recent changepoint detection in panel data. Technometrics, 61(1), 88–98.

Behrendt, S. (2021). Structural breaks in Box-Cox transforms of realized volatility: a model selection perspective. Quantitative Finance, 21(11), 1905–1919.

Borzykh, D.A., Yazykov, A.A. (2020). On the practical applicability of three cusum-methods for structural breaks detection in EGARCH-models. Vestnik of Saint Petersburg University. Applied Mathematics. Computer Science. Control Processes, 16(1), 19–30.

Casini, A., Perron, P. (2024). Change-point analysis of time series with evolutionary spectra. Journal of Econometrics, 242(2), 105811.

Charalampakis, A., Dimou, C. (2010). Identification of Bouc–Wen hysteretic systems using particle swarm optimization. Computers & Structures, 88(21), 1197–1205.

Cheng, Y., Yi, J., Yang, X., Lai, K.K., Seco, L. (2022). A CEEMD-ARIMA-SVM model with structural breaks to forecast the crude oil prices linked with extreme events. Soft Computing, 26, 8537–8551.

Cho, H., Kirch, C. (2022). Two-stage data segmentation permitting multiscale change points, heavy tails and dependence. Annals of the Institute of Statistical Mathematics, 74(4), 653–684.

Cho, H., Korkas, K.K. (2022). High-dimensional garch process segmentation with an application to value-at-risk. Econometrics and Statistics, 23, 187–203.

Cho, H., Kirch, C. (2024). Data segmentation algorithms: univariate mean change and beyond. Econometrics and Statistics, 30, 76–95.

Davis, R.A., Yau, C.Y. (2013). Consistency of minimum description length model selection for piecewise stationary time series models. Electronic Journal of Statistics, 7, 381–411.

Davis, R., Lee, T., Rodriguez-Yam, G. (2005). Structural breaks estimation for non-stationary time series signals. In: IEEE Workshop on Statistical Signal Processing Proceedings, Vol. 2005, pp. 233–238.

Davis, R.A., Lee, T.C.M., Rodriguez-Yam, G.A. (2006). Structural break estimation for nonstationary time series models. Journal of the American Statistical Association, 101(473), 223–239.

Davis, R.A., Lee, T.C.M., Rodriguez-Yam, G.A. (2008). Break detection for a class of nonlinear time series models. Journal of Time Series Analysis, 29(5), 834–867.

Davis, R.A., Hancock, S.A., Yao, Y.-C. (2016). On consistency of minimum description length model selection for piecewise autoregressions. Journal of Econometrics, 194(2), 360–368.

Ditzen, J., Karavias, Y., Westerlund, J. (2021). Testing and Estimating Structural Breaks in Time Series and Panel Data in Stata. Discussion Papers 21-14, Department of Economics, University of Birmingham.

Doerr, B., Fischer, P., Hilbert, A., Witt, C. (2017). Detecting structural breaks in time series via genetic algorithms. Soft Computing, 21, 4707–4720.

Dorigo, M., Stützle, T. (2019). Ant Colony Optimization. MIT Press, Cambridge, MA.

Éltetö, T., Hansen, N., Germain-Renaud, C., Bondon, P. (2012). Scalable structural break detection. Applied Soft Computing, 12(11), 3408–3420.

Ermshaus, A., Schäfer, P., Leser, U. (2023). ClaSP: parameter-free time series segmentation. Data Mining and Knowledge Discovery, 37(3), 1262–1300.

Farsi, N., Mahjouri, N., Ghasemi, H. (2020). Breakpoint detection in non-stationary runoff time series under uncertainty. Journal of Hydrology, 590, 125458.

Fryzlewicz, P. (2014). Wild binary segmentation for multiple change-point detection. The Annals of Statistics, 42(6).

Fryzlewicz, P. (2020). Detecting possibly frequent change-points: wild binary segmentation 2 and steepest-drop model selection. Journal of the Korean Statistical Society, 49(4), 1027–1070.

Hall, A.R., Osborn, D.R., Sakkas, N. (2013). Inference on structural breaks using information criteria. The Manchester School, 81(S3), 54–81.

Huang, S.-H., Shih, W.-Y., Lu, J.-Y., Chang, H.-H., Chu, C.-H., Wang, J.-Z., Huang, J.-L., Dai, T.-S. (2020). Online structural break detection for pairs trading using wavelet transform and hybrid deep learning model. In: 2020 IEEE International Conference on Big Data and Smart Computing (BigComp), pp. 209–216.

Hvass Pedersen, M.E. (2010). Good Parameters for Particle Swarm Optimization. In technical report No. HL1001. Hvass Laboratories.

Inclan, C., Tiao, G.C. (1994). Use of cumulative sums of squares for retrospective detection of changes of variance. Journal of the American Statistical Association, 89(427), 913–923.

Kim, K., Park, J.H., Lee, M., Song, J.W. (2022). Unsupervised change point detection and trend prediction for financial time-series using a new CUSUM-based approach. IEEE Access, 10, 34690–34705.

Kirch, C., Reckruehm, K. (2024). Data segmentation for time series based on a general moving sum approach. Annals of the Institute of Statistical Mathematics, 76, 393–421.

Kovács, S., Bühlmann, P., Li, H., Munk, A. (2023). Seeded binary segmentation: a general methodology for fast and optimal changepoint detection. Biometrika, 110(1), 249–256.

Lan, N., Geyer, M., Chemla, E., Katzir, R. (2022). Minimum description length recurrent neural networks. Transactions of the Association for Computational Linguistics, 10, 785–799.

Lee, T.H., Parsaeian, S., Ullah, A. (2022). Efficient combined estimation under structural breaks. Advances in Econometrics, 43A, 119–142.

Li, Y., Cezeaux, R., Yu, D. (2019a). Automating data monitoring: detecting structural breaks in time series data using Bayesian minimum description length.

Li, Y., Lund, R., Hewaarachchi, A. (2019b). Multiple changepoint detection with partial information on changepoint times. Electronic Journal of Statistics, 13(2), 2462–2520.

Lim, H., Choi, H., Choi, Y., Kim, I.-J. (2020). Memetic algorithm for multivariate time-series segmentation. Pattern Recognition Letters, 138, 60–67.

Lu, Q., Lund, R., Lee, T.C.M. (2010). An MDL approach to the climate segmentation problem. The Annals of Applied Statistics, 4(1), 299–319.

Madrid Padilla, O.H., Yu, Y., Wang, D., Rinaldo, A. (2022). Optimal nonparametric multivariate change point detection and localization. IEEE Transactions on Information Theory, 68(3), 1922–1944.

Meier, A., Kirch, C., Cho, H. (2021). mosum: a package for moving sums in change-point analysis. Journal of Statistical Software, 97(8), 1–42.

Murray, D., Liao, J., Stankovic, L., Stankovic, V., Hauxwell-Baldwin, R., Wilson, C., Coleman, M., Kane, T., Firth, S. (2015). A data management platform for personalised real-time energy feedback. In: Proceedings of the 8th International Conference on Energy Efficiency in Domestic Appliances and Lighting.

Rissanen, J. (1978). Modeling by shortest data description. Automatica, 14(5), 465–471.

Romano, G., Rigaill, G., Runge, V., Fearnhead, P. (2022). Detecting abrupt changes in the presence of local fluctuations and autocorrelated noise. Journal of the American Statistical Association, 117(540), 2147–2162.

Safikhani, A., Bai, Y., Michailidis, G. (2022). Fast and scalable algorithm for detection of structural breaks in big VAR models. Journal of Computational and Graphical Statistics, 31(1), 176–189.

Scott, A.J., Knott, M. (1974). A cluster analysis method for grouping means in the analysis of variance. Biometrics, 30(3), 507–512.

Shaochuan, L. (2020). Bayesian multiple changepoints detection for Markov jump processes. Computational Statistics, 35(3), 1501–1523.

Shi, X., Beaulieu, C., Killick, R., Lund, R. (2022a). Changepoint detection: an analysis of the Central England temperature series. Journal of Climate, 35(19), 2729–2742.

Shi, X., Gallagher, C., Lund, R., Killick, R. (2022b). A comparison of single and multiple changepoint techniques for time series data. Computational Statistics & Data Analysis, 170, 107433.

Smith, S.C. (2023). Structural breaks in grouped heterogeneity. Journal of Business & Economic Statistics, 41, 752–764.

Suárez-Sierra, B.M., Coen, A., Taimal, C.A. (2023). Genetic algorithm with a Bayesian approach for the detection of multiple points of change of time series of counting exceedances of specific thresholds. Journal of the Korean Statistical Society, 52, 982–1024.

Tartakovsky, A. (2019). Sequential Change Detection and Hypothesis Testing. Chapman and Hall/CRC.

Woody, J., Xu, Y., Dyer, J., Lund, R., Hewaarachchi, A.P. (2021). A statistical analysis of daily snow depth trends in North America. Atmosphere, 17(7) 820.

Yan, Q., Liu, Y., Liu, S., Ma, T. (2021). Change-point detection based on adjusted shape context cost method. Information Sciences, 545, 363–380.

Yang, Q., Zhang, Y. (2022). Change-point detection for the link function in a single-index model. Statistics & Probability Letters, 186, 109468.

Zhang, N.R., Siegmund, D.O. (2007). A modified Bayes Information Criterion with applications to the analysis of comparative genomic hybridization data. Biometrics, 63(1), 22–32.

Biographies

Burczaniuk Mateusz

Mat.Burczaniuk@gmail.com

M. Burczaniuk received the BSc degree in computer science and the MSc degree in computer science and information systems from the Warsaw University of Technology, Warsaw, Poland, in 2020 and 2021, respectively. His research interests include machine learning, evolutionary computation and swarm intelligence.

Jastrzębska Agnieszka

https://orcid.org/0000-0001-5361-5787

A.Jastrzebska@mini.pw.edu.pl

A. Jastrzębska received the BSc degree in information technology from the University of Derby, Derby, UK, in 2009, the MScEng degree in computer engineering from the Rzeszow University of Technology, Rzeszow, Poland, in 2010, the MA degree in economics from the University of Rzeszow, Rzeszow, in 2011, and the PhD and DSc degrees from the Warsaw University of Technology, Warsaw, Poland, in 2016 and 2021, respectively. She is associate professor with the Faculty of Mathematics and Information Science, Warsaw University of Technology. Her research interests include machine learning and fuzzy modeling. She serves as an associate editor of Applied Soft Computing journal.

Full article Related articles

Open access article under the CC BY license.

Keywords

time series structural break ARIMA Genetic Algorithm Particle Swarm Optimization Ant Colony Optimization Minimum Description Length

Funding

This research was supported by the Warsaw University of Technology within the Excellence Initiative: Research University (IDUB) programme.

Metrics

since January 2020

452

Article info
views

285

Full article
views

205

PDF
downloads

XML
downloads

RSS

Authors

Abstract

References

Biographies

Export citation

Copy and paste formatted citation

Download citation in file