1
$\begingroup$

I've been reading up on changepoint algorithms (dynamic programming, Bayesian Online Changepoint detection, Hidden Markov Models, etc.) and am looking to implement an algorithm that has a certain set of attributes, ideally in Python. I don't have a formal stats/math background, so it can be a bit tedious to read through the material and many of the algorithms have limitations, which are sometimes discovered halfway through a paper or blog post.

What I'm looking for:

  1. Fast/online. If an algorithm is sufficiently fast, it's probably less important that it's online. My understanding is that some offline algorithms can be adapted to be online by refining the last "known" changepoint until another is found.
  2. Allows for multiple changepoints, where the total number of changepoints is unknown before running the algorithm
  3. Does not require specifying an exact number of classes for the segments resulting from the changepoints
  4. Allows for multivariate data where the variables are evaluated jointly. Perhaps an alternative would be to perform multiple single variate analyses and attempt to merge changepoints that occur in different variables but near in time. Just a thought since I haven't specifically come across this, but a true multivariate solution would be ideal.
  5. Accounts for changes in standard deviation and not just mean. This could perhaps be replicated by calculating the absolute distance from the latest mean in real time and passing that in as an additional variable. In my specific case, I expect the individual time steps and segment means to be +/- from 0, so simply using absolute value might make it easier and avoid the need for additional recursion.

And obviously something that's as exact as possible would be ideal.

Any suggestions?

$\endgroup$
1
$\begingroup$

The R package bcp seem to fulfill all of these (associated paper here). It returns the probability of change point at each index in your data, so you have to set a threshold yourself. This is a nice feature compared to many other packages.

For multivariate change point detection, it requires that the data is in a matrix format, i.e., that all outcome variables are observed simultaneously (or close enough that it's OK to pretend).

It does not model autocorrelation which is often an important feature of time series.

I have tried to make an overview of change point packages in R. Few match your problem but take a look at the list of not-yet-reviewed packages at the top of the page.

$\endgroup$
3
  • $\begingroup$ Excellent overview of the packages. I should have specified that I'm working in Python, but it looks like there are ways to run R packages in Python. The bcp package does look like a good option but I've also come across a number of Git repositories based on Bayesian Online Changepoint Detection for Python. Do you have any thoughts on PELT? That was another that has stood out so far, but I haven't gotten deep enough into it to see if it handles all of the requirements I mentioned. Not sure if it's part of one of the packages you listed. $\endgroup$ Jan 28 at 15:52
  • $\begingroup$ Jonas maybe you could add changepoint.geo to your list of not-yet-reviewed? $\endgroup$
    – adunaic
    Jan 28 at 16:18
  • $\begingroup$ @adunaic Will do, thanks for the hint. $\endgroup$ Jan 28 at 20:30
1
$\begingroup$

Another R package that meets these options (and can be implemented online) is changepoint.geo. It reduces the multivariate time series down to a bi-variate (angle and distance) series. These are designed to identify changes in mean and variance. Currently, all other projection-based (for dimension reduction and time efficiencies) approaches only consider changes in the mean behaviour. In contrast to BCP, geomcp uses PELT as the optimizer for the bivariate series and so it is an exact solution to the optimization problem.

As with BCP it doesn't model auto- or cross- correlations though.

Most changepoint algorithms are in R at the moment but you can easily use rpy2 to interface to them from Python. Although if you enjoy coding, the transformation is simple to translate to Python and the code for PELT is already available in Python in the ruptures package. I'd be happy to guide on which lines need changing.

$\endgroup$
4
  • $\begingroup$ I'm looking more at DP/PELT algorithms. The one thing that throws me off is the penalty term, which to me is less intuitive than trying to compare multiple groupings of time steps (I understand why it's used and it's probably necessary for minimizing complexity - just less intuitive to me). I'm also looking at a graph-based approach (arxiv.org/pdf/1209.1625.pdf), which seems straightforward but I can't find much for multiple changepoints. Are you aware of anything in Python or R? Side note: it's crazy how diverse but frequently limited the solutions are for this topic. $\endgroup$ Feb 4 at 4:23
  • $\begingroup$ Also, the graph-based approach brings to mind a kind of center of mass approach where mass is accumulated as the total weight of observations (i.e., mean * n). Then, as the center of mass moves with new points being added to the segment, if a threshold of mass*distance is broken from any prior center of mass in the current segment, a new segment is established. This probably ends up being somewhat similar to BCP but might be simpler to implement (I still need to get into the weeds in terms of BCP implementation). $\endgroup$ Feb 4 at 4:39
  • $\begingroup$ The paper you reference has an R package, gSeg. The authors have been communicative so you could reach out to them. cran.r-project.org/web/packages/gSeg/index.html $\endgroup$
    – adunaic
    Feb 5 at 8:24
  • $\begingroup$ The penalty controls the difference in test statistic that is required for a change. This is the same as the thinking as is required for all hypothesis testing and is directly linked to this in the single changepoint scenario. The intuition is that large values require more evidence to say a change exists and small values requires less evidence (so you get more changepoints). If small deviations in penalty drastically change the segmentation then that is not good. The CROPS algorithm allows you to efficiently find all changes in a penalty range if you prefer the "how many changes?" view. $\endgroup$
    – adunaic
    Feb 5 at 8:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.