Systems and methods for structural clustering of time sequences

Abstract

Arrangements and methods 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.

1 . A method of performing structural clustering between different time series, said method comprising the steps of:
 accepting distinct and diverse 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 time-invariant 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.   
   
   
       2 . The method according to  claim 1 , further comprising the step of determining common periodicities corresponding to each of the clusters. 
   
   
       3 . The method according to  claim 1 , further comprising the step of predetermining a number of structural features to compute. 
   
   
       4 . The method according to  claim 1 , wherein:
 said ascertaining step comprises ascertaining frequency content relating to the time series data; and   said ascertaining step further comprises implementing a Discrete Fourier Transform.   
   
   
       5 . The method according to  claim 1 , wherein:
 said ascertaining step comprises determining an orthogonal transformation relating to the time series data;   the orthogonal transformation of the data comprising a Discrete Wavelet Transform.   
   
   
       6 . The method according to  claim 1 , further comprising the steps of:
 selecting at least one of said structural features; and   said determining is performed via employing the at least one structural feature selected.   
   
   
       7 . The method according to  claim 6 , wherein said selecting step is performed by a user. 
   
   
       8 . The method according to  claim 6 , wherein:
 said selecting step is performed automatically; and   said selecting step comprises:
 identifying candidate structural features; and 
 verifying the candidate structural features. 
   
   
   
       9 . The method according to  claim 8 , wherein:
 said identifying step comprises:
 computing a periodogram of the different time series; and 
 identifying peaks of the periodogram; and 
   said verifying step comprises:
 computing an autocorrelation; and 
 selecting identified peaks of the periodogram that lie on hills of the autocorrelation. 
   
   
   
       10 . The method according to  claim 1  wherein said ascertaining step comprises:
 computing all structural features; and   automatically selecting a number of most relevant features.   
   
   
       11 . The method according to  claim 10 , wherein said step of automatically selecting a number of most relevant features comprises:
 selecting a parameter k corresponding to a number of structural features to keep; and   retaining the k features that contain the highest amount of periodic content.   
   
   
       12 . The method according to  claim 10 , 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. 
   
   
   
       13 . An apparatus for performing structural clustering between different time series, said apparatus comprising:
 an arrangement for accepting distinct and diverse 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 time-invariant clusters containing at least one of the time series based on the at least one distances;   wherein the clusters are stored in a computer memory.   
   
   
       14 . The apparatus according to  claim 13 , further comprising an arrangement for determining common periodicities corresponding to each of the clusters. 
   
   
       15 . The apparatus according to  claim 13 , further comprising an arrangement for predetermining a number of structural features to compute. 
   
   
       16 . The apparatus according to  claim 13 , wherein:
 said ascertaining arrangement is adapted to ascertain frequency content relating to the time series data; and   said ascertaining arrangement is further adapted to implement a Discrete Fourier Transform.   
   
   
       17 . The apparatus according to  claim 13 , wherein:
 said ascertaining arrangement is adapted to determine an orthogonal transformation relating to the time series data;   the orthogonal transformation of the data comprising a Discrete Wavelet Transform.   
   
   
       18 . The apparatus according to  claim 13 , further comprising:
 an arrangement for selecting at least one of said structural features; and   said determining arrangement is adapted to employ the at least one structural feature selected.   
   
   
       19 . The apparatus according to  claim 18 , wherein said selecting arrangement is operable by a user. 
   
   
       20 . The apparatus according to  claim 18 , wherein:
 said selecting arrangement is operable automatically; and   said selecting arrangement is adapted to:
 identify candidate structural features; and 
 verify the candidate structural features. 
   
   
   
       21 . The apparatus according to  claim 20 , wherein:
 said identifying arrangement is adapted to:
 compute a periodogram of the different time series; and 
 identify peaks of the periodogram; and 
   said verifying arrangement is adapted to:
 compute an autocorrelation; and 
 select identified peaks of the periodogram that lie on hills of the autocorrelation. 
   
   
   
       22 . The apparatus according to  claim 13  wherein said ascertaining arrangement is adapted to:
 compute all structural features; and   automatically select a number of most relevant features.   
   
   
       23 . The apparatus according to  claim 22 , wherein said arrangement for automatically selecting a number of most relevant features is adapted to:
 select a parameter k corresponding to a number of structural features to keep; and   retain the k features that contain the highest amount of periodic content.   
   
   
       24 . The apparatus according to  claim 22 , 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. 
   
   
   
       25 . A program storage device readable by machine, tangibly 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 distinct and diverse 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 time-invariant 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.   
   
   
       26 . A method of quantifying the structural similarity between different time series, said method comprising the steps of:
 accepting distinct and diverse 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   returning the k closest matches to a given time series query based on the at least one distance;   wherein the k closet matches are stored in a computer memory.   
   
   
       27 . The method according to  claim 26 , wherein the structural features are based on at least one of:
 periodic features extracted from the time-series; and   burst features extracted from the time-series.   
   
   
       28 . An apparatus for quantifying the structural similarity between different time series, said apparatus comprising:
 an arrangement for accepting distinct and diverse 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 returning the k closest matches to a given time series query based on the at least one distance;   wherein the k closest matches are stored in a computer memory.   
   
   
       29 . The apparatus according to  claim 28 , wherein the structural features are based on at least one of:
 periodic features extracted from the time-series; and   burst features extracted from the time-series.