The DOI matches its Crossref record; 29 of the 29 references it cites were found in a registry or an index.
Optimal Detection of Changepoints With a Linear Computational Cost
Open accessAbstract
In this article, we consider the problem of detecting multiple changepoints in large datasets. Our focus is on applications where the number of changepoints will increase as we collect more data: for example, in genetics as we analyze larger regions of the genome, or in finance as we observe time series over longer periods. We consider the common approach of detecting changepoints through minimizing a cost function over possible numbers and locations of changepoints. This includes several established procedures for detecting changing points, such as penalized likelihood and minimum description length. We introduce a new method for finding the minimum of such cost functions and hence the optimal number and location of changepoints that has a computational cost, which, under mild conditions, is linear in the number of observations. This compares favorably with existing methods for the same problem whose computational cost can be quadratic or even cubic. In simulation studies, we show that our new method can be orders of magnitude faster than these alternative exact methods. We also compare with the binary segmentation algorithm for identifying changepoints, showing that the exactness of our approach can lead to substantial improvements in the accuracy of the inferred segmentation of the data. This article has supplementary materials available online.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
A new look at the statistical model identification
Akaike, H. (1974) · IEEE Transactions on Automatic Control · doi:10.1109/tac.1974.1100705 · Cited by 51,879
Estimating the Dimension of a Model
Schwarz, G. (1978) · The Annals of Statistics · doi:10.1214/aos/1176344136 · Cited by 47,033
Holland, J. H. (1992) · The MIT Press eBooks · doi:10.7551/mitpress/1090.001.0001 · Cited by 47,002
A Cluster Analysis Method for Grouping Means in the Analysis of Variance
Scott, A. J., & Knott, M. (1974) · Biometrics · doi:10.2307/2529204 · Cited by 2,770
Circular binary segmentation for the analysis of array-based DNA copy number data
Olshen, A. B., Venkatraman, E. S., Lucito, R., & Wigler, M. (2004) · Biostatistics · doi:10.1093/biostatistics/kxh008 · Cited by 2,325
Freimer, M., Bellman, R. E., & Dreyfus, S. E. (1964) · Journal of the American Statistical Association · doi:10.2307/2282884 · Cited by 2,153
Bellman, R. E., & Dreyfus, S. E. (1962) · Princeton University Press eBooks · doi:10.1515/9781400874651 · Cited by 1,971
Use of Cumulative Sums of Squares for Retrospective Detection of Changes of Variance
Inclán, C., & Tiao, G. C. (1994) · Journal of the American Statistical Association · doi:10.1080/01621459.1994.10476824 · Cited by 1,156
Volatility in Emerging Stock Markets
Aggarwal, R., Inclan, C., & Leal, R. (1999) · The Journal of Financial and Quantitative Analysis · doi:10.2307/2676245 · Cited by 734
Parametric Statistical Change Point Analysis: With Applications to Genetics, Medicine, and Finance
Chen, J., & Gupta, A. K. (2012) · Birkhäuser Boston eBooks · doi:10.1007/978-0-8176-4801-5 · Cited by 596
An algorithm for optimal partitioning of data on an interval
Jackson, B., Scargle, J. D., Barnes, D., Arabhi, S., Alt, A., Gioumousis, P., Gwin, E., San, P., Tan, L., & Tsai, T. T. (2005) · IEEE Signal Processing Letters · doi:10.1109/lsp.2001.838216 · Cited by 422
Zhang, N. R., & Siegmund, D. O. (2007) · Biometrics · doi:10.1111/j.1541-0420.2006.00662.x · Cited by 407
Structural Break Estimation for Nonstationary Time Series Models
Davis, R. A., Lee, T. C. M., & Rodriguez-Yam, G. A. (2006) · Journal of the American Statistical Association · doi:10.1198/016214505000000745 · Cited by 407
Use of Cumulative Sums of Squares for Retrospective Detection of Changes of Variance
Inclan, C., & Tiao, G. C. (1994) · Journal of the American Statistical Association · doi:10.2307/2290916 · Cited by 399
On Tests for Detecting Change in Mean
Sen, A., & Srivastava, M. S. (1975) · The Annals of Statistics · doi:10.1214/aos/1176343001 · Cited by 355
A statistical approach for array CGH data analysis
Picard, F., Robin, S., Lavielle, M., Vaisse, C., & Daudin, J.-J. (2005) · BMC Bioinformatics · doi:10.1186/1471-2105-6-27 · Cited by 353
Algorithms for the optimal identification of segment neighborhoods
Auger, I. E., & Lawrence, C. E. (1989) · Bulletin of Mathematical Biology · doi:10.1007/bf02458835 · Cited by 326
Detecting multiple breaks in financial market volatility dynamics
Andreou, E., & Ghysels, E. (2002) · Journal of Applied Econometrics · doi:10.1002/jae.684 · Cited by 324
Multiple Change-Point Estimation With a Total Variation Penalty
Harchaoui, Z., & Lévy-Leduc, C. (2010) · Journal of the American Statistical Association · doi:10.1198/jasa.2010.tm09181 · Cited by 311
Minimal Penalties for Gaussian Model Selection
Birgé, L., & Massart, P. (2007) · Probability Theory and Related Fields · doi:10.1007/s00440-006-0011-8 · Cited by 299
Parametric Statistical Change Point Analysis
Chen, J., & Gupta, A. K. (2000) · Birkhäuser Boston eBooks · doi:10.1007/978-1-4757-3131-6 · Cited by 284
Multiple changepoint fitting via quasilikelihood, with application to DNA sequence segmentation
Braun, J. (2000) · Biometrika · doi:10.1093/biomet/87.2.301 · Cited by 174
Tests for Variance Shift at an Unknown Time Point
Hsu, D. A. (1977) · Journal of the Royal Statistical Society Series C (Applied Statistics) · doi:10.2307/2346968 · Cited by 170
The Maximum Likelihood Method for Testing Changes in the Parameters of Normal Observations
Horvath, L. (1993) · The Annals of Statistics · doi:10.1214/aos/1176349143 · Cited by 159
Joint segmentation, calling, and normalization of multiple CGH profiles
Picard, F., Lebarbier, É., Hoebeke, M., Rigaill, G. J., Thiam, B., & Robin, S. S. (2011) · Biostatistics · doi:10.1093/biostatistics/kxq076 · Cited by 144
Analysis of changepoint models
Eckley, I. A., Fearnhead, P., & Killick, R. (2011) · Cambridge University Press eBooks · doi:10.1017/cbo9780511984679.011 · Cited by 130
Self-citationPruned dynamic programming for optimal multiple change-point detectionPreprint
Rigaill, G. J. (2010) · arXiv (Cornell University) · Cited by 71
On the Underfitting and Overfitting Sets of Models Chosen by Order Selection Criteria
Guyon, X., & Yao, J. (1999) · Journal of Multivariate Analysis · doi:10.1006/jmva.1999.1828 · Cited by 56
Using CART to Detect Multiple Change Points in the Mean for Large Sample
Gey, S., & Lebarbier, E. (2008) · HAL · Cited by 15
Cited by
Selective review of offline change point detection methods
Truong, C., Oudre, L., & Vayatis, N. (2020) · Signal Processing · doi:10.1016/j.sigpro.2019.107299 · Cited by 1,338
changepoint : An R Package for Changepoint Analysis
Killick, R., & Eckley, I. A. (2014) · Journal of Statistical Software · doi:10.18637/jss.v058.i03 · Cited by 1,330
Self-citationCicero predicts cis-regulatory DNA interactions from single-cell chromatin accessibility data
Pliner, H. A., Packer, J. S., McFaline-Figueroa, J. L., Cusanovich, D. A., Daza, R. M., Aghamirzaie, D., Srivatsan, S., Qiu, X., Jackson, D., Minkina, A., et al. (2018) · Molecular Cell · doi:10.1016/j.molcel.2018.06.044 · Cited by 789
Wild binary segmentation for multiple change-point detection
Fryzlewicz, P. (2014) · The Annals of Statistics · doi:10.1214/14-aos1245 · Cited by 566
A Nonparametric Approach for Multiple Change Point Analysis of Multivariate Data
Matteson, D. S., & James, N. A. (2014) · Journal of the American Statistical Association · doi:10.1080/01621459.2013.849605 · Cited by 542
Metadata
- Authors
- Killick, R., Fearnhead, P., & Eckley, I. A.
- Venue
- Journal of the American Statistical Association
- Publisher
- Informa UK Limited
- Published
- 2012-10-17
- Volume
- 107
- Issue
- 500
- Pages
- 1590-1598
- ISSN
- 0162-1459 (ISSN-L)
- 1537-274X
- OpenAlex
- W1975684011
- Cited by
- 2,548
- References
- 29
- FWCI
- 46.70
- Type
- journal article
- Language
- en
- Open access
- green
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.