2020

An Evaluation of Change Point Detection Algorithms

Burg, Gerrit J. J. van den, Williams, Christopher K. I.

Understand

Change point detection is an important part of time series analysis, as the presence of a change point indicates an abrupt and significant change in the data generating process.

While many algorithms for change point detection have been proposed, comparatively little attention has been paid to evaluating their performance on real-world time series.
Algorithms are typically evaluated on simulated data and a small number of commonly-used series with unreliable ground truth.
Clearly this does not provide sufficient insight into the comparative performance of these algorithms.

Built on

Mengenlehre
Hausdorff, F · 1927
Earlier work this paper cites.
The use of ranks to avoid the assumption of normality implicit in the analysis of variance
Friedman, M · 1937
Earlier work this paper cites.
A comparison of alternative tests of significance for the problem of m m rankings
Friedman, M · 1940
Earlier work this paper cites.
Individual comparisons by ranking methods
Wilcoxon, F · 1945
Earlier work this paper cites.
Continuous inspection schemes
Page, E. S · 1954
Earlier work this paper cites.
Tests of equality between sets of coefficients in two linear regressions
Chow, G. C · 1960
Earlier work this paper cites.
Distribution-free multiple comparisons
Nemenyi, P. B · 1963
Earlier work this paper cites.
Inference about the change-point in a sequence of random variables
Hinkley, D. V · 1970
Earlier work this paper cites.
Procedures for reacting to a change in distribution
Lorden, G · 1971
Earlier work this paper cites.
Multidimensional scaling of measures of distance between partitions
Arabie, P. and Boorman, S. A · 1973
Earlier work this paper cites.
A cluster analysis method for grouping means in the analysis of variance
Scott, A. J. and Knott, M · 1974
Earlier work this paper cites.
A simple sequentially rejective multiple test procedure
Holm, S · 1979
Earlier work this paper cites.
Information Retrieval
Van Rijsbergen, C. J · 1979
Earlier work this paper cites.
Comparing partitions
Hubert, L. and Arabie, P · 1985
Earlier work this paper cites.
Algorithms for the optimal identification of segment neighborhoods
Auger, I. E. and Lawrence, C. E · 1989
Earlier work this paper cites.
Numerical Bayesian Methods Applied to Signal Processing
Ó Ruanaidh, J. J. K. and Fitzgerald, W. J · 1996
Earlier work this paper cites.
A database of human segmented natural images and its application to evaluating segmentation algorithms and measuring ecological statistics
Martin, D. R., Fowlkes, C. C., Tal, D., and Malik, J · 2001
Earlier work this paper cites.
Computation and analysis of multiple structural change models
Bai, J. and Perron, P · 2003
Earlier work this paper cites.

Similar

Learning to detect natural image boundaries using local brightness, color, and texture cues
Martin, D. R., Fowlkes, C. C., and Malik, J · 2004
Cited alongside, same era.
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., Sangtrakulcharoen, P., Tan, L., and Tsai, T. T · 2005
Cited alongside, same era.
Statistical comparisons of classifiers over multiple data sets
Demšar, J · 2006
Cited alongside, same era.
Bayesian online changepoint detection
Original
Adams, R. P. and MacKay, D. J. C · 2007
Cited alongside, same era.
On-line inference for multiple changepoint problems
Fearnhead, P. and Liu, Z · 2007
Cited alongside, same era.
Adaptive detection of multiple change-points in asset price volatility
Lavielle, M. and Teyssiere, G · 2007
Cited alongside, same era.
Learning and inferring motion patterns using parametric segmental switching linear dynamic systems
Oh, S. M., Rehg, J. M., Balch, T., and Dellaert, F · 2008
Cited alongside, same era.
Sequential Bayesian prediction in the presence of changepoints
Garnett, R., Osborne, M. A., and Roberts, S. J · 2009
Cited alongside, same era.
Kernel change-point analysis
Harchaoui, Z., Moulines, E., and Bach, F. R · 2009
Cited alongside, same era.
Adaptive sequential Bayesian change point detection
Turner, R. D., Saatçi, Y., and Rasmussen, C. E · 2009
Cited alongside, same era.
Contour detection and hierarchical image segmentation
Arbelaez, P., Maire, M., Fowlkes, C. C., and Malik, J · 2010
Cited alongside, same era.
The PASCAL Visual Object Classes (VOC) Challenge
Everingham, M., Van Gool, L., Williams, C. K. I., Winn, J., and Zisserman, A · 2010
Cited alongside, same era.

Then

changepoint
Killick, R. and Eckley, I. A · 2014
Later among the works it cites.
A nonparametric approach for multiple change point analysis of multivariate data
Matteson, D. S. and James, N. A · 2014
Later among the works it cites.
Twenty Questions and Answers About the Ozone Layer: 2014 Update, Scientific Assessment of Ozone Depletion: 2014
Hegglin, M. I., Fahey, D. W., McFarland, M., Montzka, S. A., and Nash, E. R · 2015
Later among the works it cites.
A pruned dynamic programming algorithm to recover the best segmentations with 1 to K m a x {K}_{max} change-points
Rigaill, G · 2015
Later among the works it cites.
Should we really use post-hoc tests based on mean-ranks?
Benavoli, A., Corani, G., and Mangili, F · 2016
Later among the works it cites.
Accurate occupancy detection of an office room from light, temperature, humidity and CO 2 \text{CO}_{2} measurements using statistical learning models
Candanedo, L. M. and Feldheim, V · 2016
Later among the works it cites.
A survey of methods for time series change point detection
Aminikhanghahi, S. and Cook, D. J · 2017
Later among the works it cites.
A computationally efficient nonparametric approach for changepoint detection
Haynes, K., Fearnhead, P., and Eckley, I. A · 2017
Later among the works it cites.
On optimal multiple changepoint algorithms for large data
Maidstone, R., Hocking, T. D., Rigaill, G., and Fearnhead, P · 2017
Later among the works it cites.
Historical greenhouse gas concentrations for climate modelling (CMIP6)
Meinshausen, M., Vogel, E., Nauels, A., Lorbacher, K., Meinshausen, N., Etheridge, D. M., Fraser, P. J., Montzka, S. A., Rayner, P. J., Trudinger, C. M., Krummel, P. B., Beyerle, U., Canadell, J. G., Daniel, J. S., Enting, I. G., Law, R. M., Lunder, C. R., O’Doherty, S., Prinn, R. G., Reimann, S., Rubino, M., Velders, G. J. M., Vollmer, M. K., Wang, R. H. J., and Weiss, R · 2017
Later among the works it cites.
Penalty learning for changepoint detection
Truong, C., Oudre, L., and Vayatis, N · 2017
Later among the works it cites.
QuantTree: Histograms for change detection in multivariate data streams
Boracchi, G., Carrera, D., Cervellera, C., and Macciò, D · 2018
Later among the works it cites.
Spatio-temporal Bayesian on-line changepoint detection with model selection
Knoblauch, J. and Damoulas, T · 2018
Later among the works it cites.
Doubly robust Bayesian inference for non-stationary streaming data with β \beta -divergences
Knoblauch, J., Jewson, J. E., and Damoulas, T · 2018
Later among the works it cites.
A Bayesian change point model for detecting SIP-based DDoS attacks
Kurt, B., Yıldız, Ç., Ceritli, T. Y., Sankur, B., and Cemgil, A. T · 2018
Later among the works it cites.
Forecasting at scale
Taylor, S. J. and Letham, B · 2018
Later among the works it cites.
Changepoint detection in the presence of outliers
Fearnhead, P. and Rigaill, G · 2019
Later among the works it cites.
Selective review of offline change point detection methods
Truong, C., Oudre, L., and Vayatis, N · 2020
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…