IDEAS home Printed from https://ideas.repec.org/a/oup/biomet/v110y2023i1p249-256..html
   My bibliography  Save this article

Seeded binary segmentation: a general methodology for fast and optimal changepoint detection

Author

Listed:
  • S Kovács
  • P Bühlmann
  • H Li
  • A Munk

Abstract

SummaryWe propose seeded binary segmentation for large-scale changepoint detection problems. We construct a deterministic set of background intervals, called seeded intervals, in which single changepoint candidates are searched for. The final selection of changepoints based on these candidates can be done in various ways, adapted to the problem at hand. The method is thus easy to adapt to many changepoint problems, ranging from univariate to high dimensional. Compared to recently popular random background intervals, seeded intervals lead to reproducibility and much faster computations. For the univariate Gaussian change in mean set-up, the methodology is shown to be asymptotically minimax optimal when paired with appropriate selection criteria. We demonstrate near-linear runtimes and competitive finite sample estimation performance. Furthermore, we illustrate the versatility of our method in high-dimensional settings.

Suggested Citation

  • S Kovács & P Bühlmann & H Li & A Munk, 2023. "Seeded binary segmentation: a general methodology for fast and optimal changepoint detection," Biometrika, Biometrika Trust, vol. 110(1), pages 249-256.
    • Handle: RePEc:oup:biomet:v:110:y:2023:i:1:p:249-256.
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1093/biomet/asac052
    Download Restriction: Access to full text is restricted to subscribers.
    ---><---

    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. Fryzlewicz, Piotr, 2020. "Detecting possibly frequent change-points: Wild Binary Segmentation 2 and steepest-drop model selection—rejoinder," LSE Research Online Documents on Economics 106681, London School of Economics and Political Science, LSE Library.
    2. 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.
    3. 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.
    4. 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.
    5. 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.
    6. 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.
    7. Kim, Chang-Jin & Morley, James C. & Nelson, Charles R., 2005. "The Structural Break in the Equity Premium," Journal of Business & Economic Statistics, American Statistical Association, vol. 23, pages 181-191, April.
    8. Camilo Rivera & Guenther Walther, 2013. "Optimal detection of a jump in the intensity of a Poisson process or in a density with likelihood ratio statistics," Scandinavian Journal of Statistics, Danish Society for Theoretical Statistics;Finnish Statistical Society;Norwegian Statistical Association;Swedish Statistical Association, vol. 40(4), pages 752-769, December.
    9. 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.
    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. 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.
    2. Florian Gunsilius & David Van Dijcke, 2023. "Free Discontinuity Regression: With an Application to the Economic Effects of Internet Shutdowns," Papers 2309.14630, arXiv.org, revised Jan 2024.

    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. Cho, Haeran & Kirch, Claudia, 2024. "Data segmentation algorithms: Univariate mean change and beyond," Econometrics and Statistics, Elsevier, vol. 30(C), pages 76-95.
    2. 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).
    3. Andreas Anastasiou & Piotr Fryzlewicz, 2022. "Detecting multiple generalized change-points by isolating single ones," Metrika: International Journal for Theoretical and Applied Statistics, Springer, vol. 85(2), pages 141-174, February.
    4. 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.
    5. 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.
    6. 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.
    7. Lu Shaochuan, 2023. "Scalable Bayesian Multiple Changepoint Detection via Auxiliary Uniformisation," International Statistical Review, International Statistical Institute, vol. 91(1), pages 88-113, April.
    8. 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.
    9. Kang-Ping Lu & Shao-Tung Chang, 2023. "An Advanced Segmentation Approach to Piecewise Regression Models," Mathematics, MDPI, vol. 11(24), pages 1-23, December.
    10. Sean Jewell & Paul Fearnhead & Daniela Witten, 2022. "Testing for a change in mean after changepoint detection," Journal of the Royal Statistical Society Series B, Royal Statistical Society, vol. 84(4), pages 1082-1104, September.
    11. Sang Gil Kang & Woo Dong Lee & Yongku Kim, 2021. "Bayesian Multiple Change-Points Detection in a Normal Model with Heterogeneous Variances," Computational Statistics, Springer, vol. 36(2), pages 1365-1390, June.
    12. 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.
    13. 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.
    14. Bill Russell & Dooruj Rambaccussing, 2019. "Breaks and the statistical process of inflation: the case of estimating the ‘modern’ long-run Phillips curve," Empirical Economics, Springer, vol. 56(5), pages 1455-1475, May.
    15. 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.
    16. Guenther Walther & Andrew Perry, 2022. "Calibrating the scan statistic: Finite sample performance versus asymptotics," Journal of the Royal Statistical Society Series B, Royal Statistical Society, vol. 84(5), pages 1608-1639, November.
    17. 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.
    18. Kang-Ping Lu & Shao-Tung Chang, 2021. "Robust Algorithms for Change-Point Regressions Using the t -Distribution," Mathematics, MDPI, vol. 9(19), pages 1-28, September.
    19. Stefan Albert & Michael Messer & Julia Schiemann & Jochen Roeper & Gaby Schneider, 2017. "Multi-Scale Detection of Variance Changes in Renewal Processes in the Presence of Rate Change Points," Journal of Time Series Analysis, Wiley Blackwell, vol. 38(6), pages 1028-1052, November.
    20. Claudia Kirch & Christina Stoehr, 2022. "Sequential change point tests based on U‐statistics," Scandinavian Journal of Statistics, Danish Society for Theoretical Statistics;Finnish Statistical Society;Norwegian Statistical Association;Swedish Statistical Association, vol. 49(3), pages 1184-1214, September.

    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:oup:biomet:v:110:y:2023:i:1:p:249-256.. 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: Oxford University Press (email available below). General contact details of provider: https://academic.oup.com/biomet .

    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.