Video

# Changepoint Detection – Part 2

If you haven’t already, I would strongly recommend glancing over the part 1 of this post before continuing. In it we talked about a method for detecting a single changepoint through techniques such as maximum log-likelihood estimation. The question now is the more difficult one of how can we search for multiple changepoints?

The simplest thing to do would be to initially apply our Single Changepoint Detection (SCD) method to the series we want to analyse. If there is no changepoint found we are done, but if there is a changepoint found we end up with two distinct segments.

The key idea is that we can then apply the same SCD method to each of those segments individually to see if either of them contain a changepoint. See the pattern yet? Essentially we can repeat this process to every new segment we make as a result of finding a changepoint,  until we don’t detect any additional changepoints.

This is what’s known as an iterative method since we repeat the same steps over and over again. The beauty of it lies in its simplicity and the fact that the single changepoint problem can be directly extended to the multiple changepoint problem! In the literature this method is often referred to as ‘Binary Segmentation’.

Procedure for Binary Segmentation

1. Apply the Single Changepoint Detection Method to test for a single changepoint.
2. If there is no changepoint, stop.
3. If there is a changepoint, split the data into two segments: before and after the changepoint.
4. Apply the Single Changepoint Detection Method to both of the segments.
5. Repeat iteratively – until no more changepoints detected.

This slideshow requires JavaScript.

The binary segmentation method is a well-known and widely used method because of its simplicity and speed. In mathematical terms it is of order $O(n\log{}n)$, where n is the number of changepoints. It does however have a key disadvantage: it is only approximate.

If you think about it you will realise that the location of each changepoint detected by binary segmentation depends on the location of the previous changepoint. This means that the result produced for the location of all the changepoints will not necessarily be the overall best result. In particular binary segmentation struggles when there is a small period of change within a larger structure period.

Strength and Limitations

• Simple
• Fast
• Only Approximate

Lots of other algorithms have been produced in recent times that try to build upon and improve on binary segmentation. In fact the problem of detecting multiple changepoints is an active area of research at STOR-i, where many people have made contributions to the area. In particular some people based here have even developed new and exact methods for detecting multiple changepoints such as PELT and CROPS.

Advertisements