On optimal multiple changepoint algorithms for large data
From MaRDI portal
Abstract: There is an increasing need for algorithms that can accurately detect changepoints in long time-series, or equivalent, data. Many common approaches to detecting changepoints, for example based on penalised likelihood or minimum description length, can be formulated in terms of minimising a cost over segmentations. Dynamic programming methods exist to solve this minimisation problem exactly, but these tend to scale at least quadratically in the length of the time-series. Algorithms, such as Binary Segmentation, exist that have a computational cost that is close to linear in the length of the time-series, but these are not guaranteed to find the optimal segmentation. Recently pruning ideas have been suggested that can speed up the dynamic programming algorithms, whilst still being guaranteed to find true minimum of the cost function. Here we extend these pruning methods, and introduce two new algorithms for segmenting data, FPOP and SNIP. Empirical results show that FPOP is substantially faster than existing dynamic programming methods, and unlike the existing methods its computational efficiency is robust to the number of changepoints in the data. We evaluate the method at detecting Copy Number Variations and observe that FPOP has a computational cost that is competitive with that of Binary Segmentation.
Recommendations
- Optimal detection of changepoints with a linear computational cost
- A pruned dynamic programming algorithm to recover the best segmentations with 1 to \(K_{\max}\) change-points
- A pruned recursive solution to the multiple change point problem
- A computationally efficient nonparametric approach for changepoint detection
- Fitting multiple change-point models to data
Cites work
- scientific article; zbMATH DE number 4169866 (Why is no real title available?)
- A Cluster Analysis Method for Grouping Means in the Analysis of Variance
- A Modified Bayes Information Criterion with Applications to the Analysis of Comparative Genomic Hybridization Data
- A computationally efficient nonparametric approach for changepoint detection
- A new look at the statistical model identification
- Algorithms for the optimal identification of segment neighborhoods
- Circular binary segmentation for the analysis of array-based DNA copy number data
- Detecting simultaneous change points in multiple sequences
- Estimating the dimension of a model
- Estimating the number of change points in a sequence of independent normal random variables
- Estimating the number of change-points via Schwarz' criterion
- Multiple changepoint fitting via quasilikelihood, with application to DNA sequence segmentation
- Multiscale change point inference. With discussion and authors' reply
- Optimal detection of changepoints with a linear computational cost
- Statistical methods for DNA sequence segmentation
- Structural Break Estimation for Nonstationary Time Series Models
- Structural breaks in time series
- Using penalized contrasts for the change-point problem
- Wild binary segmentation for multiple change-point detection
Cited in
(53)- Multiple change point detection in functional data with applications to biomechanical fatigue data
- Most Recent Changepoint Detection in Panel Data
- Greedy Segmentation for a Functional Data Sequence
- Optimal change-point detection and localization
- Changepoint analysis of Klementinum temperature series
- Scalable multiple changepoint detection for functional data sequences
- Optimized variable selection via repeated data splitting
- Detecting multiple generalized change-points by isolating single ones
- Epidemic changepoint detection in the presence of nuisance changes
- Two-stage data segmentation permitting multiscale change points, heavy tails and dependence
- Detecting possibly frequent change-points: wild binary segmentation 2 and steepest-drop model selection
- A Total Variation Based Method for Multivariate Time Series Segmentation
- Consistency of a range of penalised cost approaches for detecting multiple changepoints
- Multiscale change-point segmentation: beyond step functions
- A heuristic, iterative algorithm for change-point detection in abrupt change models
- Labeled Optimal Partitioning
- Cross-validation for change-point regression: pitfalls and solutions
- An \(L_0\)-norm regularized method for multivariate time series segmentation
- Constrained dynamic programming and supervised penalty learning algorithms for peak detection in genomic data
- A pruned dynamic programming algorithm to recover the best segmentations with 1 to \(K_{\max}\) change-points
- Bayesian Change Point Detection with Spike-and-Slab Priors
- Tail-greedy bottom-up data decompositions and fast multiple change-point detection
- Robust algorithms for multiphase regression models
- Change-point estimation in the multivariate model taking into account the dependence: application to the vegetative development of oilseed rape
- Is a finite intersection of balls covered by a finite union of balls in Euclidean spaces?
- Autocovariance estimation in the presence of changepoints
- Linear Time Dynamic Programming for Computing Breakpoints in the Regularization Path of Models Selected From a Finite Set
- Multi-threshold proportional hazards model and subgroup identification
- Detecting Abrupt Changes in High-Dimensional Self-Exciting Poisson Processes
- Exact spike train inference via \(\ell_{0}\) optimization
- A computationally efficient nonparametric approach for changepoint detection
- Change-detection-assisted multiple testing for spatiotemporal data
- Relating and comparing methods for detecting changes in mean
- fpop
- A comparison of single and multiple changepoint techniques for time series data
- Identifying multiple changes for a functional data sequence with application to freeway traffic segmentation
- BayesProject: fast computation of a projection direction for multivariate changepoint detection
- On optimal segmentation and parameter tuning for multiple change-point detection and inference
- Detecting Changes in Covariance via Random Matrix Theory
- Changepoint Detection in the Presence of Outliers
- Detecting Changes in Slope With an L0 Penalty
- fpopw
- A shape-based cutting and clustering algorithm for multiple change-point detection
- Most recent changepoint detection in censored panel data
- Multithreshold change plane model: estimation theory and applications in subgroup identification
- A pruned recursive solution to the multiple change point problem
- Mixture of segmentation for heterogeneous functional data
- Detecting Abrupt Changes in the Presence of Local Fluctuations and Autocorrelated Noise
- Multidecision Quickest Change-Point Detection: Previous Achievements and Open Problems
- New efficient algorithms for multiple change-point detection with reproducing kernels
- Univariate mean change point detection: penalization, CUSUM and optimality
- Optimal detection of changepoints with a linear computational cost
- Sequential changepoint detection in neural networks with checkpoints
This page was built for publication: On optimal multiple changepoint algorithms for large data
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q106347)
