SYSTEMS AND METHODS FOR STRUCTURAL CLUSTERING OF TIME SEQUENCES

• US 20100057399A1
• Filed: 08/31/2009
• Published: 03/04/2010
• 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,933,740 B2
• Time in Patent Office: Days
• US Class Current: 702/179
• CPC Class Codes: G06F 18/00 Pattern recognition
• CPC Class Codes: G06F 2218/08 Feature extraction

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.

Claims

1. An apparatus comprising:

a processor; and

a program storage device readable by machine, tangibly embodying a program of instructions executable by the processor, the program of instructions comprising;

instructions for using a periodogram for extracting period candidates from time series input to the apparatus;

instructions for verifying the period candidates using an autocorrelation function (ACF);

wherein a period candidate is verified responsive to a determination that the period candidate resides on a hill of the ACF; and

instructions for identify a local maximum of a period candidate determined to reside on a hill.

2. The apparatus according to claim 1, wherein a period candidate is discarded as a false alarm responsive to a determination that the period candidate does not reside on a hill of the ACF.

3. The apparatus according to claim 1, wherein the program of instructions further comprises instructions for computing both the periodogram and the ACF directly through a Fast Fourier Transform of the input time series.

4. The apparatus according to claim 1, wherein instructions for using a periodogram for extracting period candidates from time series input to the apparatus further comprise instructions for determining how much signal energy is attributed to random mechanisms via:

permuting elements of the time series input to produce a sequence x; and

recording a maximum power (p_max) of {tilde over (x)} at any frequency f, wherein the maximum power is given by;

$p_{\max }=\arg <br><br><br><br>\underset{f}{\max }<br><br>{<br><br>\tilde{x}<br><br>\left(f\right)<br><br>}^2$

wherein only periods whose power is more than the maximum power (p_max) of {tilde over (x)} are considered.

5. The apparatus according to claim 1, wherein the program of instructions further comprises instructions for performing an additional period trimming step for discarding periods that are either too large or too small to be considered valid.

6. The apparatus according to claim 2, wherein instructions for verifying the period candidates using an ACF further comprises instructions for approximating the ACF in the proximity of a candidate period to be verified with two linear segments, wherein an upward-downward trend of the two linear segments identifies a hill.

7. The apparatus according to claim 1, wherein instructions for identifying a local maximum of the period candidate determined to reside on a hill further comprises instructions for employing one or more of a hill climbing technique and deriving the local maximum from the two linear segments.

8. The apparatus according to claim 1, wherein:

the time series input to the apparatus comprises distinct and diverse times series input relating to a plurality of time series; and

the program of instructions further comprises;

instructions for using a measure of structural similarity that exploits a power content of one or more most dominant periods in the distinct and diverse time series input relating to a plurality of time series to effectively filter out noise.