Posts about ED-PELT
Implementation of efficient algorithm for changepoint detection: ED-PELT
Changepoint detection is an important task that has a lot of applications. For example, I use it to detect changes in the Rider performance test suite. It's very important to detect not only performance degradations, but any kinds of performance changes (e.g., the variance may increase, or a unimodal distribution may be split to several modes). You can see examples of such changes on the following picture (we change the color when a changepoint is detected):
Unfortunately, it's pretty hard to write a reliable and fast algorithm for changepoint detection.
Recently, I found a cool paper (Haynes, K., Fearnhead, P. & Eckley, I.A. "A computationally efficient nonparametric approach for changepoint detection," Stat Comput (2017) 27: 1293) that describes the ED-PELT algorithm.
It has O(N*log(N)) complexity and pretty good detection accuracy.
The reference implementation can be used via the changepoint.np R package.
However, I can't use R on our build server, so I decided to write my own C# implementation.