SYSTEMS FOR STRUCTURAL CLUSTERING OF TIME SEQUENCES

• US 20090327185A1
• Filed: 05/05/2008
• Published: 12/31/2009
• Est. Priority Date: 03/31/2005
• Status: Active Grant

• Current Assignee: GlobalFoundries, Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Yu, Philip S., Castelli, Vittorio, Vlachos, Michail
• Granted Patent: US 7,890,294 B2
• Time in Patent Office: Days
• US Class Current: 706/46
• CPC Class Codes: G06F 18/00 Pattern recognition
• CPC Class Codes: G06F 2218/08 Feature extraction

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.

Claims

1. 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.

2. The apparatus according to claim 1, further comprising an arrangement for determining common periodicities corresponding to each of the clusters.

3. The apparatus according to claim 1, further comprising an arrangement for predetermining a number of structural features to compute.

4. The apparatus according to claim 1, 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.

5. The apparatus according to claim 1, 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.

6. The apparatus according to claim 1, 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.

7. The apparatus according to claim 6, wherein said selecting arrangement is operable by a user.

8. The apparatus according to claim 6, wherein:

said selecting arrangement is operable automatically; and

said selecting arrangement is adapted to;

identify candidate structural features; and

verify the candidate structural features.

9. The apparatus according to claim 8, 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.

10. The apparatus according to claim 1, wherein said ascertaining arrangement is adapted to:

compute all structural features; and

automatically select a number of most relevant features.

11. The apparatus according to claim 10, 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.

12. 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 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.