Skip to content

Bottom-up segmentation (BottomUp)#

Description#

Bottom-up change point detection is used to perform fast signal segmentation and is implemented in BottomUp in a sequential manner. Contrary to binary segmentation, which is a greedy procedure, bottom-up segmentation is generous: it starts with many change points and successively deletes the less significant ones. First, the signal is divided in many sub-signals along a regular grid. Then contiguous segments are successively merged according to a measure of how similar they are. See for instance [Keogh2001] or [Fryzlewicz2007] for an algorithmic analysis of BottomUp. The benefits of bottom-up segmentation includes low complexity (of the order of \(\mathcal{O}(n\log n)\), where \(n\) is the number of samples), the fact that it can extend any single change point detection method to detect multiple changes points and that it can work whether the number of regimes is known beforehand or not.

Schematic view of the bottom-up segmentation algorithm

Usage#

Start with the usual imports and create a signal.

import numpy as np
import matplotlib.pylab as plt
import ruptures as rpt

# creation of data
n, dim = 500, 3  # number of samples, dimension
n_bkps, sigma = 3, 5  # number of change points, noise standart deviation
signal, bkps = rpt.pw_constant(n, dim, n_bkps, noise_std=sigma)

To perform a bottom-up segmentation of a signal, initialize a BottomUp instance.

# change point detection
model = "l2"  # "l1", "rbf", "linear", "normal", "ar"
algo = rpt.BottomUp(model=model).fit(signal)
my_bkps = algo.predict(n_bkps=3)

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

In the situation in which the number of change points is unknown, one can specify a penalty using the pen parameter or a threshold on the residual norm using epsilon.

my_bkps = algo.predict(pen=np.log(n) * dim * sigma**2)
# or
my_bkps = algo.predict(epsilon=3 * n * sigma**2)

For faster predictions, one can modify the jump parameter during initialization. The higher it is, the faster the prediction is achieved (at the expense of precision).

algo = rpt.BottomUp(model=model, jump=10).fit(signal)

References#

[Keogh2001] Keogh, E., Chu, S., Hart, D., & Pazzani, M. (2001). An online algorithm for segmenting time series. Proceedings of the IEEE International Conference on Data Mining (ICDM), 289–296.

[Fryzlewicz2007] Fryzlewicz, P. (2007). Unbalanced Haar technique for nonparametric function estimation. Journal of the American Statistical Association, 102(480), 1318–1327.