Systems for structural clustering of time sequences
AssigneeInternational Business Machines Corporation
InventorsVittorio Castelli, Michail Vlachos, Philip S. Yu
Life of this patent
Estimating the term…
Abstract
Arrangements are provided for performing structural clustering between different time series. Time series data relating to a plurality of time series is accepted, structural features relating to the time series data are ascertained, and at least one distance between different time series via employing the structural features is determined. The different time series may be partitioned into clusters based on the at least one distance, and/or the k closest matches to a given time series query based on the at least one distance may be returned.
Claims12
An apparatus for performing structural clustering between different time series, said apparatus comprising:
- an arrangement for accepting time series data relating to a plurality of time series;
- an arrangement for ascertaining structural features relating to the time series data;
- an arrangement for determining at least one distance between different time series via employing the structural features;
- and
- an arrangement for partitioning the different time series into clusters containing at least one of the time series based on the at least one distance;
- wherein the clusters are stored in a computer memory;
- wherein said ascertaining arrangement is adapted to:
- compute all structural features;
- and
- automatically select a number of most relevant features;
- and
- wherein said arrangement for automatically selecting a number of most relevant features is adapted to:
- select a threshold;
- and
- retain features having value larger than the threshold;
- and
- said arrangement for selecting a threshold is adapted to select a threshold which serves to discard features having values attributable to statistical variations via:
- computing a resampling estimate of the distribution of feature values attributable to statistical variations;
- selecting a value of probability of type 1 error;
- and
- selecting as a threshold a value that guarantees the selected value of probability of type 1 error for a distribution equal to the resampling estimate of the distribution.
A non-transitory program storage device readable by machine embodying a program of instructions executed by the machine to perform method steps for performing structural clustering between different time series, said method comprising the steps of:
- accepting time series data relating to a plurality of time series;
- ascertaining structural features relating to the time series data;
- determining at least one distance between different time series via employing the structural features;
- and
- partitioning the different time series into clusters containing at least one of the time series based on the at least one distance;
- wherein the clusters are stored in a computer memory;
- wherein said ascertaining step comprises:
- computing all structural features;
- and
- automatically selecting a number of most relevant features;
- and
- wherein said step of automatically selecting a number of most relevant features comprises:
- selecting a threshold;
- and
- retaining features having value larger than the threshold;
- and
- said step of selecting a threshold comprises selecting a threshold which serves to discard features having values attributable to statistical variations via:
- computing a resampling estimate of the distribution of feature values attributable to statistical variations;
- selecting a value of probability of type 1 error;
- and
- selecting as a threshold a value that guarantees the selected value of probability of type 1 error for a distribution equal to the resampling estimate of the distribution.
Dependencies are inferred from the claim text.