Skip to content

Dynamic programming (Dynp)#

Description#

The method is implemented in both Dynp, which is a full native python implementation for which the user can choose any cost functions defined in ruptures.costs

It finds the (exact) minimum of the sum of costs by computing the cost of all subsequences of a given signal. It is called "dynamic programming" because the search over all possible segmentations is ordered using a dynamic programming approach.

In order to work, the user must specify in advance the number of changes to detect. (Consider using penalized methods when this number is unknown.)

The complexity of the dynamic programming approach is of the order \(\mathcal{O}(CKn^2)\), 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 Dynp:

  • 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, 5
signal, bkps = rpt.pw_constant(n, dim, n_bkps, noise_std=sigma)

# change point detection
model = "l1"  # "l2", "rbf"
algo = rpt.Dynp(model=model, min_size=3, jump=5).fit(signal)
my_bkps = algo.predict(n_bkps=3)

# show results
rpt.show.display(signal, bkps, my_bkps, figsize=(10, 6))
plt.show()