CPOP: Continuous-piecewise-linear Pruned Optimal Partitioning

Implementation of a changepoint detection method. Project done during my master’s degree.

This project implements in python the CPOP (Continuous-piecewise-linear Pruned Optimal Partitioning) algorithm proposed in the paper below to detect changepoints in a univariate time series using a continuous piecewise linear model and an L0 penalty.

Fearnhead, P., Maidstone, R., & Letchford, A. (2018). Detecting Changes in Slope With an L0 Penalty. Journal of Computational and Graphical Statistics, 28(2), 265–275. https://doi.org/10.1080/10618600.2018.1512868

The main interest of this method is that the values of the approximating piecewise linear function at the changepoints are not constrained to be equal to the values of the time series at these points. This comes at the cost of a more complex optimization problem, which is sped up by the use of a pruned dynamic programming algorithm.

• The (challenging) implementation is done in python and is available on github.
• The project report is also available on github.