DOCSEARCHbyAlgolia
Submit Docs

ruptures: Offline Change Point Detection

repository·master·Indexed 24 days ago

https://github.com/deepcharles/ruptures

A Python library for offline change point detection in non-stationary signals. It provides a consistent interface for parametric and non-parametric models, including algorithms like Pelt, Binseg, BottomUp, Dynp, L1Potts, and KernelCPD. The library includes various cost functions (e.g., CostL1, CostL2, CostRbf, CostLinear), synthetic dataset generators (pw_constant, pw_linear, pw_normal, pw_wavy), and evaluation metrics such as the Hausdorff metric, Rand index, and precision-recall.

Tokens
23.4K
Snippets
60
Records
136
Agent score
84%

What's inside ruptures

  1. Overview of the ruptures package structure

    master

    The ruptures package is organized into modules based on the type of procedure they perform. Understanding these modules helps in locating specific functionality for change point detection:

    • ruptures.base: Contains the base classes used for extending the library.
    • ruptures.detection: Contains the core search methods for detecting change points.
    • ruptures.costs: Contains cost functions used by detection algorithms.
    • ruptures.datasets: Provides utilities for generating synthetic data sets.
    • ruptures.metrics: Provides metrics for evaluating the performance of detection methods.
    • ruptures.show: Contains functions for displaying and visualizing results.

  2. Use CostCLinear for continuous linear change detection

    master

    The CostCLinear cost function is used to measure the error when approximating a signal with a continuous linear spline. A linear spline is affine on each interval between knots (change points) and is continuous across those knots. This is particularly useful for detecting signals that exhibit piecewise linear trends rather than abrupt jumps in value.

    To use CostCLinear in a change point detection algorithm (like rpt.Dynp), you can either pass an instance of the class to the custom_cost argument or use the string identifier model="clinear".

    import ruptures as rpt

# Option 1: Pass a CostCLinear instance
c = rpt.costs.CostCLinear()
algo = rpt.Dynp(custom_cost=c)

# Option 2: Use the model string
algo = rpt.Dynp(model="clinear")

  3. Use L1Potts for robust change point detection

    master

    The L1Potts method performs piecewise constant 1D signal segmentation by minimizing the L1 Potts functional. Unlike L2-based detectors (like Pelt(model="l2")), L1Potts is robust to heavy-tailed noise and outliers because it uses an L1 fit.

    Key characteristics:

    • Input: Accepts only 1D signals.
    • Complexity: Solves the problem exactly in $\mathcal{O}(KN)$ time (where $N$ is the number of samples and $K$ is the number of distinct values).
    • Performance: Significantly faster than Pelt(model="l1") (typically 20–30× speedup).
    • Prediction Mode: Only supports penalty-only mode (predict(pen=...)). Parameters like n_bkps and epsilon are not supported.
    import numpy as np
import matplotlib.pylab as plt
import ruptures as rpt

# creation of data with heavy-tailed (Laplace) noise
n, sigma = 500, 1.0
n_bkps = 3
signal, bkps = rpt.pw_constant(n, 1, n_bkps, noise_std=sigma)
signal = signal.ravel() + np.random.default_rng(0).laplace(scale=sigma, size=n)

# change point detection
algo = rpt.L1Potts().fit(signal)
my_bkps = algo.predict(pen=3.0)

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

  4. Use the CostL1 cost function for median shift detection

    master

    The CostL1 (Least Absolute Deviation) cost function is a robust estimator used to detect changes in the median of a signal. It is particularly useful for identifying shifts in the central point (mean, median, or mode) of a distribution.

    To use it, you can either pass an instance of rpt.costs.CostL1() to a detection algorithm via the custom_cost argument, or simply specify model="l1" in algorithms that support it.

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

# Create a signal
n, dim = 500, 3
n_bkps, sigma = 3, 5
signal, bkps = rpt.pw_constant(n, dim, n_bkps, noise_std=sigma)

# Use CostL1 in a detection algorithm
c = rpt.costs.CostL1()
algo = rpt.Dynp(custom_cost=c)
# OR
algo = rpt.Dynp(model="l1")

  5. Use Window-based change point detection

    master

    Window-based change point detection (Window) is used for fast signal segmentation. It works by sliding two windows along a data stream and comparing their statistical properties using a discrepancy measure. A change point is detected when the discrepancy between the windows is significantly high.

    Key Advantages

    • Low Complexity: $\mathcal{O}(n w)$, where $n$ is the number of samples and $w$ is the window width.
    • Versatility: Can extend single change point detection methods to detect multiple change points.
    • Flexibility: Works whether the number of regimes is known beforehand or not.

    Configuration Parameters

    • width: The window length in number of samples. It is recommended that the window length is smaller than the smallest regime length.
    • model: The cost function used for comparison. Supported models include "l1", "l2", "rbf", "linear", "normal", and "ar".
    • jump: Controls prediction speed. A higher jump value increases speed but decreases precision.

    Predicting Change Points

    When the number of change points is unknown, you can use one of the following instead of n_bkps:

    • pen: A penalty value.
    • epsilon: A threshold on the residual norm.

  6. Integrate `CostRank` into change point detection algorithms

    master

    You can use the CostRank cost function within change point detection algorithms (those inheriting from BaseEstimator, such as rpt.Dynp). There are two ways to specify the rank-based model:

    1. Pass a custom cost instance: Create an instance of rpt.costs.CostRank() and pass it to the custom_cost argument of the algorithm.
    2. Use the model string: Set the model argument to "rank".

    Both methods are equivalent.

    c = rpt.costs.CostRank()
algo = rpt.Dynp(custom_cost=c)
# is equivalent to
algo = rpt.Dynp(model="rank")

  7. Use Kernelized mean change (`CostRbf`) for change point detection

    master

    The CostRbf cost function detects changes in the distribution of an iid sequence of random variables by using a Radial Basis Function (RBF) kernel. It is a non-parametric method that detects changes in the mean of the signal embedded in a Hilbert space.

    To use CostRbf in a change point detection algorithm (like rpt.Dynp), you can either pass an instance of CostRbf to the custom_cost argument or simply set the model parameter to "rbf".

  9. Create a custom cost function

    master

    To define a custom cost function in ruptures, create a new class that inherits from ruptures.base.BaseCost. You must implement the following two methods:

    1. .fit(signal): This method accepts a signal as input and is used to set the internal parameters of the cost function. It must return 'self'.
    2. .error(start, end): This method accepts two integer indices, start and end, and must return the calculated cost for the segment spanning from start to end.

  10. Perform offline change point detection with ruptures

    master

    The ruptures library is used for offline change point detection, providing methods to analyze and segment non-stationary signals. It supports various parametric and non-parametric models using both exact and approximate detection algorithms.

    To perform detection, you typically follow a three-step workflow:

    1. Generate or load a signal: Use rpt.pw_constant for synthetic piecewise constant signals or load your own data.
    2. Detection: Initialize an algorithm (e.g., rpt.Pelt), call .fit(signal) to train it on the data, and then call .predict(pen=...) to find the change points.
    3. Display: Use rpt.display(signal, bkps, result) to visualize the signal, the true breakpoints (bkps), and the detected change points (result).
    import matplotlib.pyplot as plt
import ruptures as rpt

# generate signal
n_samples, dim, sigma = 1000, 3, 4
n_bkps = 4  # number of breakpoints
signal, bkps = rpt.pw_constant(n_samples, dim, n_bkps, noise_std=sigma)

# detection
algo = rpt.Pelt(model="rbf").fit(signal)
result = algo.predict(pen=10)

# display
rpt.display(signal, bkps, result)
plt.show()

  12. Use the CostMl metric for Mahalanobis-type change detection

    master

    The CostMl cost function detects changes in the mean of an embedded signal using a pseudo-metric defined by a positive semi-definite matrix $M$. It calculates the cost of a sub-signal as the sum of the squared Mahalanobis distances between each point and the empirical mean of that sub-signal.

    To use CostMl, you must provide a metric matrix $M$ (e.g., an identity matrix or the inverse of an empirical covariance matrix) during initialization. You can then use the resulting instance to calculate the error of specific segments or the total sum of costs for a set of change points.

    import numpy as np
import ruptures as rpt

n, dim = 500, 3
signal, bkps = rpt.pw_constant(n, dim, n_bkps=3, noise_std=5)

# Initialize CostMl with a metric matrix M
M = np.eye(dim)
c = rpt.costs.CostMl(metric=M).fit(signal)

# Calculate error for a specific segment [start, end)
print(c.error(50, 150))

# Calculate sum of costs for a list of change points
print(c.sum_of_costs(bkps))
print(c.sum_of_costs([10, 100, 200, 250, n]))