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)- Multithreshold change plane model: estimation theory and applications in subgroup identification
- Epidemic changepoint detection in the presence of nuisance changes
- Detecting multiple generalized change-points by isolating single ones
- Robust algorithms for multiphase regression models
- Most recent changepoint detection in censored panel data
- Constrained dynamic programming and supervised penalty learning algorithms for peak detection in genomic data
- On optimal segmentation and parameter tuning for multiple change-point detection and inference
- New efficient algorithms for multiple change-point detection with reproducing kernels
- Optimal detection of changepoints with a linear computational cost
- BayesProject: fast computation of a projection direction for multivariate changepoint detection
- Autocovariance estimation in the presence of changepoints
- A comparison of single and multiple changepoint techniques for time series data
- Optimal change-point detection and localization
- Bayesian Change Point Detection with Spike-and-Slab Priors
- Univariate mean change point detection: penalization, CUSUM and optimality
- Change-point estimation in the multivariate model taking into account the dependence: application to the vegetative development of oilseed rape
- Multiscale change-point segmentation: beyond step functions
- A computationally efficient nonparametric approach for changepoint detection
- Detecting Changes in Covariance via Random Matrix Theory
- Sequential changepoint detection in neural networks with checkpoints
- A Total Variation Based Method for Multivariate Time Series Segmentation
- Greedy Segmentation for a Functional Data Sequence
- Is a finite intersection of balls covered by a finite union of balls in Euclidean spaces?
- Identifying multiple changes for a functional data sequence with application to freeway traffic segmentation
- Cross-validation for change-point regression: pitfalls and solutions
- A pruned recursive solution to the multiple change point problem
- Detecting Changes in Slope With an L0 Penalty
- fpop
- Multi-threshold proportional hazards model and subgroup identification
- fpopw
- Most Recent Changepoint Detection in Panel Data
- Changepoint analysis of Klementinum temperature series
- Scalable multiple changepoint detection for functional data sequences
- Optimized variable selection via repeated data splitting
- An \(L_0\)-norm regularized method for multivariate time series segmentation
- Exact spike train inference via \(\ell_{0}\) optimization
- Mixture of segmentation for heterogeneous functional data
- Two-stage data segmentation permitting multiscale change points, heavy tails and dependence
- Detecting Abrupt Changes in the Presence of Local Fluctuations and Autocorrelated Noise
- Multidecision Quickest Change-Point Detection: Previous Achievements and Open Problems
- Change-detection-assisted multiple testing for spatiotemporal data
- Detecting Abrupt Changes in High-Dimensional Self-Exciting Poisson Processes
- A shape-based cutting and clustering algorithm for multiple change-point detection
- Changepoint Detection in the Presence of Outliers
- A pruned dynamic programming algorithm to recover the best segmentations with 1 to \(K_{\max}\) change-points
- Detecting possibly frequent change-points: wild binary segmentation 2 and steepest-drop model selection
- Multiple change point detection in functional data with applications to biomechanical fatigue data
- Labeled Optimal Partitioning
- Consistency of a range of penalised cost approaches for detecting multiple changepoints
- Relating and comparing methods for detecting changes in mean
- Linear Time Dynamic Programming for Computing Breakpoints in the Regularization Path of Models Selected From a Finite Set
- A heuristic, iterative algorithm for change-point detection in abrupt change models
- Tail-greedy bottom-up data decompositions and fast multiple change-point detection
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)
