Exact penalised changepoint detection (PELT)

Minimises \(\sum_{l} C(y_{(\tau_{l-1}+1):\tau_l}) + \beta m\) exactly by the pruned dynamic program of Killick, Fearnhead and Eckley (2012), Algorithm 2, which attains the same solution as the full \(O(n^2)\) segment-neighbourhood search at close to linear cost. Pruning uses their Theorem 3.1 with \(K = 0\), valid for a log-likelihood cost.

Usage

morie_pelt(x, cost = "mean", penalty = NULL, min_seglen = 1L)

Arguments

x

Numeric series.

cost

Segment cost, "mean" (default; Normal change in mean, unit variance) or "meanvar" (Normal change in mean and variance). Both routes the paper gives are available.

penalty

Penalty \(\beta\) per changepoint. Default NULL uses the BIC/SIC value p * log(n) with p = 1 for "mean" and p = 2 for "meanvar" (their Sec. 3.1).

min_seglen

Minimum segment length; forced to at least 2 for "meanvar", where singleton segments make the likelihood unbounded.

Value

A list with changepoints (0-based split positions, as on the Python side), n_changepoints, objective, penalty, segment_means, estimate, n and method.

References

Killick, R., Fearnhead, P. and Eckley, I. A. (2012). Optimal detection of changepoints with a linear computational cost. Journal of the American Statistical Association, 107(500), 1590-1598.

Examples

V <- c(1, 2, 3, 4, 5, 6, 7, 8)
morie_pelt(V)
#> $changepoints
#> [1] 2 4 6
#> 
#> $n_changepoints
#> [1] 3
#> 
#> $objective
#> [1] 8.238325
#> 
#> $penalty
#> [1] 2.079442
#> 
#> $segment_means
#> [1] 1.5 3.5 5.5 7.5
#> 
#> $estimate
#> [1] 2 4 6
#> 
#> $n
#> [1] 8
#> 
#> $method
#> [1] "PELT (Killick-Fearnhead-Eckley 2012)"
#>