Class OfflineChangePointDetectionAlgorithm

  • All Implemented Interfaces:
    Algorithm

    @Title("Off-line Change Point Detection")
    @Description("Detects multiple change points in a time series")
    @Reference(authors="D. Picard",title="Testing and Estimating Change-Points in Time Series ",booktitle="Advances in Applied Probability Vol. 17",url="https://doi.org/10.2307/1427090",bibkey="doi:10.2307/1427090") @Reference(authors="E. S. Page",title="On Problems in which a Change in a Parameter Occurs at an Unknown Point",booktitle="Biometrika Vol. 44",url="https://doi.org/10.2307/2333258",bibkey="doi:10.2307/2333258") @Reference(authors="M. Basseville, I. V. Nikiforov",title="Section 2.6: Off-line Change Detection",booktitle="Detection of Abrupt Changes - Theory and Application",url="http://people.irisa.fr/Michele.Basseville/kniga/kniga.pdf",bibkey="books/prentice/BassevilleN93/C2")
    public class OfflineChangePointDetectionAlgorithm
    extends java.lang.Object
    implements Algorithm
    Off-line change point detection algorithm detecting a change in mean, based on the cumulative sum (CUSUM), same-variance assumption, and using bootstrap sampling for significance estimation.

    References:

    D. Picard
    Testing and Estimating Change-Points in Time Series
    Advances in Applied Probability Vol. 17

    early results along these lines can be found in:

    E. S. Page
    On Problems in which a Change in a Parameter Occurs at an Unknown Point
    Biometrika Vol. 44

    also discussed in:

    M. Basseville and I. V. Nikiforov
    Section 2.6: Off-line Change Detection
    Detection of Abrupt Changes - Theory and Application

    Since:
    0.7.5
    Author:
    Sebastian Rühl, Erich Schubert
    • Field Detail

      • bootstrapSamples

        int bootstrapSamples
        Number of samples for bootstrap significance.
      • minConfidence

        double minConfidence
        Mininum confidence.
    • Constructor Detail

      • OfflineChangePointDetectionAlgorithm

        public OfflineChangePointDetectionAlgorithm​(double confidence,
                                                    int bootstrapSteps,
                                                    RandomFactory rnd)
        Constructor
        Parameters:
        confidence - Confidence
        bootstrapSteps - Steps for bootstrapping
    • Method Detail

      • getInputTypeRestriction

        public TypeInformation[] getInputTypeRestriction()
        Description copied from interface: Algorithm
        Get the input type restriction used for negotiating the data query.
        Specified by:
        getInputTypeRestriction in interface Algorithm
        Returns:
        Type restriction
      • run

        public ChangePoints run​(Relation<DoubleVector> relation)
        Executes multiple change point detection for given relation
        Parameters:
        relation - the relation to process
        Returns:
        list with all the detected change point for every time series
      • cusum

        public static void cusum​(double[] data,
                                 double[] out,
                                 int begin,
                                 int end)
        Compute the incremental sum of an array, i.e. the sum of all points up to the given index.
        Parameters:
        data - Input data
        out - Output array (must be large enough).
      • bestChangeInMean

        public static DoubleIntPair bestChangeInMean​(double[] sums,
                                                     int begin,
                                                     int end)
        Find the best position to assume a change in mean.
        Parameters:
        sums - Cumulative sums
        begin - Interval begin
        end - Interval end
        Returns:
        Best change position
      • shuffle

        public static void shuffle​(double[] bstrap,
                                   int len,
                                   java.util.Random rnd)
        Fisher-Yates shuffle of a partial array
        Parameters:
        bstrap - Data to shuffle
        len - Length of valid data
        rnd - Random generator