IDEAS home Printed from https://ideas.repec.org/a/eee/ecosta/v30y2024icp76-95.html
   My bibliography  Save this article

Data segmentation algorithms: Univariate mean change and beyond

Author

Listed:
  • Cho, Haeran
  • Kirch, Claudia

Abstract

Data segmentation a.k.a. multiple change point analysis has received considerable attention due to its importance in time series analysis and signal processing, with applications in a variety of fields including natural and social sciences, medicine, engineering and finance. The first part reviews the existing literature on the canonical data segmentation problem which aims at detecting and localising multiple change points in the mean of univariate time series. An overview of popular methodologies is provided on their computational complexity and theoretical properties. In particular, the theoretical discussion focuses on the separation rate relating to which change points are detectable by a given procedure, and the localisation rate quantifying the precision of corresponding change point estimators, and a distinction is made whether a homogeneous or multiscale viewpoint has been adopted in their derivation. It is further highlighted that the latter viewpoint provides the most general setting for investigating the optimality of data segmentation algorithms.

Suggested Citation

  • Cho, Haeran & Kirch, Claudia, 2024. "Data segmentation algorithms: Univariate mean change and beyond," Econometrics and Statistics, Elsevier, vol. 30(C), pages 76-95.
    • Handle: RePEc:eee:ecosta:v:30:y:2024:i:c:p:76-95
    DOI: 10.1016/j.ecosta.2021.10.008
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S2452306221001234
    Download Restriction: Full text for ScienceDirect subscribers only. Contains open access articles
    File URL: https://libkey.io/10.1016/j.ecosta.2021.10.008?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Robert Tibshirani & Michael Saunders & Saharon Rosset & Ji Zhu & Keith Knight, 2005. "Sparsity and smoothness via the fused lasso," Journal of the Royal Statistical Society Series B, Royal Statistical Society, vol. 67(1), pages 91-108, February.
    2. Heunis, Andrew J., 2003. "Strong invariance principle for singular diffusions," Stochastic Processes and their Applications, Elsevier, vol. 104(1), pages 57-80, March.
    3. Celisse, A. & Marot, G. & Pierre-Jean, M. & Rigaill, G.J., 2018. "New efficient algorithms for multiple change-point detection with reproducing kernels," Computational Statistics & Data Analysis, Elsevier, vol. 128(C), pages 200-220.
    4. Jushan Bai & Pierre Perron, 1998. "Estimating and Testing Linear Models with Multiple Structural Changes," Econometrica, Econometric Society, vol. 66(1), pages 47-78, January.
    5. Lajos Horváth & Gregory Rice, 2014. "Extensions of some classical methods in change point analysis," TEST: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 23(2), pages 219-255, June.
    6. Inder Tecuapetla-Gómez & Axel Munk, 2017. "Autocovariance Estimation in Regression with a Discontinuous Signal and m-Dependent Errors: A Difference-Based Approach," Scandinavian Journal of Statistics, Danish Society for Theoretical Statistics;Finnish Statistical Society;Norwegian Statistical Association;Swedish Statistical Association, vol. 44(2), pages 346-368, June.
    7. Ninomiya, Yoshiyuki, 2005. "Information criterion for Gaussian change-point model," Statistics & Probability Letters, Elsevier, vol. 72(3), pages 237-247, May.
    8. Annika Betken, 2016. "Testing for Change-Points in Long-Range Dependent Time Series by Means of a Self-Normalized Wilcoxon Test," Journal of Time Series Analysis, Wiley Blackwell, vol. 37(6), pages 785-809, November.
    9. Klaus Frick & Axel Munk & Hannes Sieling, 2014. "Multiscale change point inference," Journal of the Royal Statistical Society Series B, Royal Statistical Society, vol. 76(3), pages 495-580, June.
    10. István Berkes & Robertas Gabrys & Lajos Horváth & Piotr Kokoszka, 2009. "Detecting changes in the mean of functional observations," Journal of the Royal Statistical Society Series B, Royal Statistical Society, vol. 71(5), pages 927-946, November.
    11. Behrendt, Simon & Schweikert, Karsten, 2021. "A Note on Adaptive Group Lasso for Structural Break Time Series," Econometrics and Statistics, Elsevier, vol. 17(C), pages 156-172.
    12. Philip Preuss & Ruprecht Puchstein & Holger Dette, 2015. "Detection of Multiple Structural Breaks in Multivariate Time Series," Journal of the American Statistical Association, Taylor & Francis Journals, vol. 110(510), pages 654-668, June.
    13. Steinebach, Josef & Eastwood, Vera R., 1996. "Extreme Value Asymptotics for Multivariate Renewal Processes," Journal of Multivariate Analysis, Elsevier, vol. 56(2), pages 284-302, February.
    14. Harchaoui, Z. & Lévy-Leduc, C., 2010. "Multiple Change-Point Estimation With a Total Variation Penalty," Journal of the American Statistical Association, American Statistical Association, vol. 105(492), pages 1480-1493.
    15. Chun Yip Yau & Zifeng Zhao, 2016. "Inference for multiple change points in time series via likelihood ratio scan statistics," Journal of the Royal Statistical Society Series B, Royal Statistical Society, vol. 78(4), pages 895-916, September.
    16. Holger Dette & Theresa Eckle & Mathias Vetter, 2020. "Multiscale change point detection for dependent data," Scandinavian Journal of Statistics, Danish Society for Theoretical Statistics;Finnish Statistical Society;Norwegian Statistical Association;Swedish Statistical Association, vol. 47(4), pages 1243-1274, December.
    17. Alexander Aue & Lajos Horváth, 2013. "Structural breaks in time series," Journal of Time Series Analysis, Wiley Blackwell, vol. 34(1), pages 1-16, January.
    18. Herold Dehling & Aeneas Rooch & Murad S. Taqqu, 2013. "Non-Parametric Change-Point Tests for Long-Range Dependent Data," Scandinavian Journal of Statistics, Danish Society for Theoretical Statistics;Finnish Statistical Society;Norwegian Statistical Association;Swedish Statistical Association, vol. 40(1), pages 153-173, March.
    19. H Dehling & R Fried & M Wendler, 2020. "A robust method for shift detection in time series," Biometrika, Biometrika Trust, vol. 107(3), pages 647-660.
    20. Gombay, Edit, 2001. "U-Statistics for Change under Alternatives," Journal of Multivariate Analysis, Elsevier, vol. 78(1), pages 139-158, July.
    21. Alexander Aue & Rex C. Y. Cheung & Thomas C. M. Lee & Ming Zhong, 2014. "Segmented Model Selection in Quantile Regression Using the Minimum Description Length Principle," Journal of the American Statistical Association, Taylor & Francis Journals, vol. 109(507), pages 1241-1256, September.
    22. Yao, Yi-Ching, 1988. "Estimating the number of change-points via Schwarz' criterion," Statistics & Probability Letters, Elsevier, vol. 6(3), pages 181-189, February.
    23. Michael Messer & Stefan Albert & Gaby Schneider, 2018. "The multiple filter test for change point detection in time series," Metrika: International Journal for Theoretical and Applied Statistics, Springer, vol. 81(6), pages 589-607, August.
    24. Fryzlewicz, Piotr, 2020. "Detecting possibly frequent change-points: Wild Binary Segmentation 2 and steepest-drop model selection," LSE Research Online Documents on Economics 103430, London School of Economics and Political Science, LSE Library.
    25. Yao, Yi-Ching, 1990. "On the asymptotic behavior of a class of nonparametric tests for a change-point problem," Statistics & Probability Letters, Elsevier, vol. 9(2), pages 173-177, February.
    26. Haeran Cho & Piotr Fryzlewicz, 2015. "Multiple-change-point detection for high dimensional time series via sparsified binary segmentation," Journal of the Royal Statistical Society Series B, Royal Statistical Society, vol. 77(2), pages 475-507, March.
    27. Michalis K. Titsias & Christopher C. Holmes & Christopher Yau, 2016. "Statistical Inference in Hidden Markov Models Using k -Segment Constraints," Journal of the American Statistical Association, Taylor & Francis Journals, vol. 111(513), pages 200-215, March.
    28. Marie Hušková & Claudia Kirch, 2008. "Bootstrapping confidence intervals for the change‐point of time series," Journal of Time Series Analysis, Wiley Blackwell, vol. 29(6), pages 947-972, November.
    29. Pan, Jianmin & Chen, Jiahua, 2006. "Application of modified information criterion to multiple change point problems," Journal of Multivariate Analysis, Elsevier, vol. 97(10), pages 2221-2241, November.
    30. Antoch, Jaromír & Husková, Marie, 2001. "Permutation tests in change point analysis," Statistics & Probability Letters, Elsevier, vol. 53(1), pages 37-46, May.
    31. Cho, Haeran & Fryzlewicz, Piotr, 2015. "Multiple-change-point detection for high dimensional time series via sparsified binary segmentation," LSE Research Online Documents on Economics 57147, London School of Economics and Political Science, LSE Library.
    32. Florian Pein & Hannes Sieling & Axel Munk, 2017. "Heterogeneous change point inference," Journal of the Royal Statistical Society Series B, Royal Statistical Society, vol. 79(4), pages 1207-1227, September.
    33. Ngai Hang Chan & Chun Yip Yau & Rong-Mao Zhang, 2014. "Group LASSO for Structural Break Time Series," Journal of the American Statistical Association, Taylor & Francis Journals, vol. 109(506), pages 590-599, June.
    34. Rafal Baranowski & Yining Chen & Piotr Fryzlewicz, 2019. "Narrowest‐over‐threshold detection of multiple change points and change‐point‐like features," Journal of the Royal Statistical Society Series B, Royal Statistical Society, vol. 81(3), pages 649-672, July.
    35. Tengyao Wang & Richard J. Samworth, 2018. "High dimensional change point estimation via sparse projection," Journal of the Royal Statistical Society Series B, Royal Statistical Society, vol. 80(1), pages 57-83, January.
    36. Venkata Jandhyala & Stergios Fotopoulos & Ian MacNeill & Pengyu Liu, 2013. "Inference for single and multiple change-points in time series," Journal of Time Series Analysis, Wiley Blackwell, vol. 34(4), pages 423-446, July.
    37. Lee, Chung-Bow, 1995. "Estimating the number of change points in a sequence of independent normal random variables," Statistics & Probability Letters, Elsevier, vol. 25(3), pages 241-248, November.
    38. Steland, Ansgar, 2020. "Testing and estimating change-points in the covariance matrix of a high-dimensional time series," Journal of Multivariate Analysis, Elsevier, vol. 177(C).
    39. Davis, Richard A. & Lee, Thomas C.M. & Rodriguez-Yam, Gabriel A., 2006. "Structural Break Estimation for Nonstationary Time Series Models," Journal of the American Statistical Association, American Statistical Association, vol. 101, pages 223-239, March.
    40. Barigozzi, Matteo & Cho, Haeran & Fryzlewicz, Piotr, 2018. "Simultaneous multiple change-point and factor analysis for high-dimensional time series," Journal of Econometrics, Elsevier, vol. 206(1), pages 187-225.
    41. Nancy R. Zhang & David O. Siegmund, 2007. "A Modified Bayes Information Criterion with Applications to the Analysis of Comparative Genomic Hybridization Data," Biometrics, The International Biometric Society, vol. 63(1), pages 22-32, March.
    42. Chao Du & Chu-Lan Michael Kao & S. C. Kou, 2016. "Stepwise Signal Extraction via Marginal Likelihood," Journal of the American Statistical Association, Taylor & Francis Journals, vol. 111(513), pages 314-330, March.
    43. Richard A. Davis & Thomas C. M. Lee & Gabriel A. Rodriguez‐Yam, 2008. "Break Detection for a Class of Nonlinear Time Series Models," Journal of Time Series Analysis, Wiley Blackwell, vol. 29(5), pages 834-867, September.
    44. Fryzlewicz, Piotr, 2014. "Wild binary segmentation for multiple change-point detection," LSE Research Online Documents on Economics 57146, London School of Economics and Political Science, LSE Library.
    45. P. Fryzlewicz & S. Subba Rao, 2014. "Multiple-change-point detection for auto-regressive conditional heteroscedastic processes," Journal of the Royal Statistical Society Series B, Royal Statistical Society, vol. 76(5), pages 903-924, November.
    46. Dietmar Ferger, 1994. "On the power of nonparametric changepoint-tests," Metrika: International Journal for Theoretical and Applied Statistics, Springer, vol. 41(1), pages 277-292, December.
    47. Lajos Horváth & Gregory Rice, 2014. "Rejoinder on: Extensions of some classical methods in change point analysis," TEST: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 23(2), pages 287-290, June.
    48. Alexander Aue & Gregory Rice & Ozan Sönmez, 2018. "Detecting and dating structural breaks in functional data without dimension reduction," Journal of the Royal Statistical Society Series B, Royal Statistical Society, vol. 80(3), pages 509-529, June.
    49. David S. Matteson & Nicholas A. James, 2014. "A Nonparametric Approach for Multiple Change Point Analysis of Multivariate Data," Journal of the American Statistical Association, Taylor & Francis Journals, vol. 109(505), pages 334-345, March.
    50. Marie Hušková & Claudia Kirch, 2010. "A note on studentized confidence intervals for the change-point," Computational Statistics, Springer, vol. 25(2), pages 269-289, June.
    51. Paul Fearnhead & Guillem Rigaill, 2019. "Changepoint Detection in the Presence of Outliers," Journal of the American Statistical Association, Taylor & Francis Journals, vol. 114(525), pages 169-183, January.
    52. Axel Bücher & Jean‐David Fermanian & Ivan Kojadinovic, 2019. "Combining Cumulative Sum Change‐Point Detection Tests for Assessing the Stationarity of Univariate Time Series," Journal of Time Series Analysis, Wiley Blackwell, vol. 40(1), pages 124-150, January.
    53. Claudia Kirch & Birte Muhsal & Hernando Ombao, 2015. "Detection of Changes in Multivariate Time Series With Application to EEG Data," Journal of the American Statistical Association, Taylor & Francis Journals, vol. 110(511), pages 1197-1216, September.
    54. Claudia Kirch & Joseph Tadjuidje Kamgaing, 2012. "Testing for parameter stability in nonlinear autoregressive models," Journal of Time Series Analysis, Wiley Blackwell, vol. 33(3), pages 365-385, May.
    55. Ieva Axt & Roland Fried, 2020. "On variance estimation under shifts in the mean," AStA Advances in Statistical Analysis, Springer;German Statistical Society, vol. 104(3), pages 417-457, September.
    56. Sangwon Hyun & Kevin Z. Lin & Max G'Sell & Ryan J. Tibshirani, 2021. "Post‐selection inference for changepoint detection algorithms with application to copy number variation data," Biometrics, The International Biometric Society, vol. 77(3), pages 1037-1049, September.
    57. Aston, John A.D. & Kirch, Claudia, 2012. "Detecting and estimating changes in dependent functional data," Journal of Multivariate Analysis, Elsevier, vol. 109(C), pages 204-220.
    58. Górecki, Tomasz & Horváth, Lajos & Kokoszka, Piotr, 2018. "Change point detection in heteroscedastic time series," Econometrics and Statistics, Elsevier, vol. 7(C), pages 63-88.
    59. Marie Hušková & Simos Meintanis, 2006. "Change Point Analysis based on Empirical Characteristic Functions," Metrika: International Journal for Theoretical and Applied Statistics, Springer, vol. 63(2), pages 145-168, April.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Tariku Tesfaye Haile & Fenglin Tian & Ghada AlNemer & Boping Tian, 2024. "Multiscale Change Point Detection for Univariate Time Series Data with Missing Value," Mathematics, MDPI, vol. 12(20), pages 1-22, October.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Fryzlewicz, Piotr, 2020. "Detecting possibly frequent change-points: Wild Binary Segmentation 2 and steepest-drop model selection," LSE Research Online Documents on Economics 103430, London School of Economics and Political Science, LSE Library.
    2. Holger Dette & Theresa Eckle & Mathias Vetter, 2020. "Multiscale change point detection for dependent data," Scandinavian Journal of Statistics, Danish Society for Theoretical Statistics;Finnish Statistical Society;Norwegian Statistical Association;Swedish Statistical Association, vol. 47(4), pages 1243-1274, December.
    3. Haeran Cho & Claudia Kirch, 2022. "Two-stage data segmentation permitting multiscale change points, heavy tails and dependence," Annals of the Institute of Statistical Mathematics, Springer;The Institute of Statistical Mathematics, vol. 74(4), pages 653-684, August.
    4. Marie Hušková & Zuzana Prášková, 2014. "Comments on: Extensions of some classical methods in change point analysis," TEST: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 23(2), pages 265-269, June.
    5. Liu, Bin & Zhang, Xinsheng & Liu, Yufeng, 2022. "High dimensional change point inference: Recent developments and extensions," Journal of Multivariate Analysis, Elsevier, vol. 188(C).
    6. Shi, Xuesheng & Gallagher, Colin & Lund, Robert & Killick, Rebecca, 2022. "A comparison of single and multiple changepoint techniques for time series data," Computational Statistics & Data Analysis, Elsevier, vol. 170(C).
    7. Hajra Siddiqa & Sajid Ali & Ismail Shah, 2021. "Most recent changepoint detection in censored panel data," Computational Statistics, Springer, vol. 36(1), pages 515-540, March.
    8. Cho, Haeran & Kirch, Claudia, 2022. "Bootstrap confidence intervals for multiple change points based on moving sum procedures," Computational Statistics & Data Analysis, Elsevier, vol. 175(C).
    9. Cho, Haeran & Fryzlewicz, Piotr, 2023. "Multiple change point detection under serial dependence: wild contrast maximisation and gappy Schwarz algorithm," LSE Research Online Documents on Economics 120085, London School of Economics and Political Science, LSE Library.
    10. McGonigle, Euan T. & Cho, Haeran, 2023. "Robust multiscale estimation of time-average variance for time series segmentation," Computational Statistics & Data Analysis, Elsevier, vol. 179(C).
    11. Zifeng Zhao & Feiyu Jiang & Xiaofeng Shao, 2022. "Segmenting time series via self‐normalisation," Journal of the Royal Statistical Society Series B, Royal Statistical Society, vol. 84(5), pages 1699-1725, November.
    12. Mengjia Yu & Xiaohui Chen, 2021. "Finite sample change point inference and identification for high‐dimensional mean vectors," Journal of the Royal Statistical Society Series B, Royal Statistical Society, vol. 83(2), pages 247-270, April.
    13. Horváth, Lajos & Rice, Gregory & Zhao, Yuqian, 2023. "Testing for changes in linear models using weighted residuals," Journal of Multivariate Analysis, Elsevier, vol. 198(C).
    14. Michael Messer, 2022. "Bivariate change point detection: Joint detection of changes in expectation and variance," Scandinavian Journal of Statistics, Danish Society for Theoretical Statistics;Finnish Statistical Society;Norwegian Statistical Association;Swedish Statistical Association, vol. 49(2), pages 886-916, June.
    15. Wu Wang & Xuming He & Zhongyi Zhu, 2020. "Statistical inference for multiple change‐point models," Scandinavian Journal of Statistics, Danish Society for Theoretical Statistics;Finnish Statistical Society;Norwegian Statistical Association;Swedish Statistical Association, vol. 47(4), pages 1149-1170, December.
    16. Davis, Richard A. & Hancock, Stacey A. & Yao, Yi-Ching, 2016. "On consistency of minimum description length model selection for piecewise autoregressions," Journal of Econometrics, Elsevier, vol. 194(2), pages 360-368.
    17. Venkata Jandhyala & Stergios Fotopoulos & Ian MacNeill & Pengyu Liu, 2013. "Inference for single and multiple change-points in time series," Journal of Time Series Analysis, Wiley Blackwell, vol. 34(4), pages 423-446, July.
    18. Florian Pein & Hannes Sieling & Axel Munk, 2017. "Heterogeneous change point inference," Journal of the Royal Statistical Society Series B, Royal Statistical Society, vol. 79(4), pages 1207-1227, September.
    19. Cui, Junfeng & Wang, Guanghui & Zou, Changliang & Wang, Zhaojun, 2023. "Change-point testing for parallel data sets with FDR control," Computational Statistics & Data Analysis, Elsevier, vol. 182(C).
    20. Cho, Haeran & Korkas, Karolos K., 2022. "High-dimensional GARCH process segmentation with an application to Value-at-Risk," Econometrics and Statistics, Elsevier, vol. 23(C), pages 187-203.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:ecosta:v:30:y:2024:i:c:p:76-95. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: https://www.journals.elsevier.com/econometrics-and-statistics .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.