# Linearly penalized segmentation (`Pelt`

)#

# Description#

The method is implemented in `Pelt`

.

Because the enumeration of all possible partitions impossible, the algorithm relies on a pruning rule.
Many indexes are discarded, greatly reducing the computational cost while retaining the
ability to find the optimal segmentation.
The implementation follows [Killick2012].
In addition, under certain conditions on the change point repartition, the avarage computational complexity is of the order of \(\mathcal{O}(CKn)\), where \(K\) is the number of change points to detect, \(n\) the number of samples and \(C\) the complexity of calling the considered cost function on one sub-signal.
Consequently, piecewise constant models (`model=l2`

) are significantly faster than linear or autoregressive models.

To reduce the computational cost, you can consider only a subsample of possible change point indexes, by changing the `min_size`

and `jump`

arguments when instantiating Pelt:

`min_size`

controls the minimum distance between change points; for instance, if`min_size=10`

, all change points will be at least 10 samples apart.`jump`

controls the grid of possible change points; for instance, if`jump=k`

, only changes at`k, 2*k, 3*k,...`

are considered.

## Usage#

```
import numpy as np
import matplotlib.pylab as plt
import ruptures as rpt
# creation of data
n, dim = 500, 3
n_bkps, sigma = 3, 1
signal, b = rpt.pw_constant(n, dim, n_bkps, noise_std=sigma)
# change point detection
model = "l1" # "l2", "rbf"
algo = rpt.Pelt(model=model, min_size=3, jump=5).fit(signal)
my_bkps = algo.predict(pen=3)
# show results
fig, (ax,) = rpt.display(signal, bkps, my_bkps, figsize=(10, 6))
plt.show()
```

## References#

[Killick2012] Killick, R., Fearnhead, P., & Eckley, I. (2012). Optimal detection of changepoints with a linear computational cost. Journal of the American Statistical Association, 107(500), 1590–1598.