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
- A Cluster Analysis Method for Grouping Means in the Analysis of Variance
- A computationally efficient nonparametric approach for changepoint detection
- A Modified Bayes Information Criterion with Applications to the Analysis of Comparative Genomic Hybridization Data
- 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
- scientific article; zbMATH DE number 4169866 (Why is no real title available?)
- 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
(70)- fpopw
- A pruned dynamic programming algorithm to recover the best segmentations with 1 to \(K_{\max}\) change-points
- Labeled Optimal Partitioning
- Exact spike train inference via \(\ell_{0}\) optimization
- Change-point estimation in the multivariate model taking into account the dependence: application to the vegetative development of oilseed rape
- A heuristic, iterative algorithm for change-point detection in abrupt change models
- A pruned recursive solution to the multiple change point problem
- New efficient algorithms for multiple change-point detection with reproducing kernels
- Robust algorithms for multiphase regression models
- Tail-greedy bottom-up data decompositions and fast multiple change-point detection
- Most recent changepoint detection in censored panel data
- Is a finite intersection of balls covered by a finite union of balls in Euclidean spaces?
- Detecting multiple generalized change-points by isolating single ones
- Consistency of a range of penalised cost approaches for detecting multiple changepoints
- Autocovariance estimation in the presence of changepoints
- Sequential changepoint detection in neural networks with checkpoints
- A comparison of single and multiple changepoint techniques for time series data
- Detecting possibly frequent change-points: wild binary segmentation 2 and steepest-drop model selection
- Univariate mean change point detection: penalization, CUSUM and optimality
- BayesProject: fast computation of a projection direction for multivariate changepoint detection
- Identifying multiple changes for a functional data sequence with application to freeway traffic segmentation
- A shape-based cutting and clustering algorithm for multiple change-point detection
- Multiscale change-point segmentation: beyond step functions
- A computationally efficient nonparametric approach for changepoint detection
- Detecting Changes in Slope With an L0 Penalty
- Multidecision Quickest Change-Point Detection: Previous Achievements and Open Problems
- Optimal detection of changepoints with a linear computational cost
- Constrained dynamic programming and supervised penalty learning algorithms for peak detection in genomic data
- An L₀-norm regularized method for multivariate time series segmentation
- Linear Time Dynamic Programming for Computing Breakpoints in the Regularization Path of Models Selected From a Finite Set
- Changepoint Detection in the Presence of Outliers
- fpop
- A Total Variation Based Method for Multivariate Time Series Segmentation
- On optimal segmentation and parameter tuning for multiple change-point detection and inference
- Epidemic changepoint detection in the presence of nuisance changes
- Detecting Abrupt Changes in the Presence of Local Fluctuations and Autocorrelated Noise
- Change-detection-assisted multiple testing for spatiotemporal data
- Bayesian Change Point Detection with Spike-and-Slab Priors
- Greedy Segmentation for a Functional Data Sequence
- Optimal change-point detection and localization
- Relating and comparing methods for detecting changes in mean
- 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
- Multithreshold change plane model: estimation theory and applications in subgroup identification
- Multi-threshold proportional hazards model and subgroup identification
- Detecting Changes in Covariance via Random Matrix Theory
- Cross-validation for change-point regression: pitfalls and solutions
- Mixture of segmentation for heterogeneous functional data
- Multiple change point detection in functional data with applications to biomechanical fatigue data
- Online multivariate changepoint detection: leveraging links with computational geometry
- A changepoint approach to modelling nonstationary soil moisture dynamics
- A latent variable model with change-points and its application to time pressure effects in educational assessment
- Transfer learning for piecewise-constant mean estimation: optimality, _1 and _0 penalization
- Drift versus Shift: Decoupling Trends and Changepoint Analysis
- Penalty learning for optimal partitioning using multilayer perceptron
- On the modified information-based approach to the change point detection (CPD) problem under the non-central skew t distribution
- Data-adaptive structural change-point detection via isolation
- An efficient algorithm for exact segmentation of large compositional and categorical time series
- Ms.FPOP: A Fast Exact Segmentation Algorithm with a Multiscale Penalty
- Functional Labeled Optimal Partitioning
- Efficient Multiple Change Point Detection and Localization For High-Dimensional Quantile Regression with Heteroscedasticity
- A semiparametric approach to the detection of change-points in volatility dynamics of financial data
- Improving power by conditioning on less in post-selection inference for changepoints
- An inexact projected regularized Newton method for fused zero-norms regularization problems
- Post-selection inference for quantifying uncertainty in changes in variance
- Change-point detection in regression models via the max-EM algorithm
- Two-stage data segmentation permitting multiscale change points, heavy tails and dependence
- Detecting Abrupt Changes in High-Dimensional Self-Exciting Poisson Processes
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)
