System and method for extracting symbols from numeric time series for forecasting extreme events

• US 6,594,622 B2
• Filed: 11/29/2000
• Issued: 07/15/2003
• Est. Priority Date: 11/29/2000
• Status: Expired due to Term

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: International Business Machines Corporation
• Inventors: Srivastava, Ashok N.
• Primary Examiner(s): WACHSMAN, HAL D
• Application Number:
  US09/726,698
• Publication Number:
  US 20030004692A1
• Time in Patent Office: 958 Days
• Field of Search: 702/189, 702/124, 702/126, 702/176, 702/179-181, 702/196, 702/191, 702/193-195, 702/177, 702/178, 702/FOR.103, 702/FOR.104, 702/FOR.134, 702/FOR.139, 702/FOR.154, 702/FOR.166, 702/FOR.167, 702/FOR.170, 705/10, 705/7, 703/2, 708/134, 708/514, 700/73, 700/74, 706/21, 706/925, 706/932
• US Class Current: 702/189
• CPC Class Codes: G06F 17/16 Matrix or vector computation , e.g. matrix-matrix or matrix-vector multiplication, matrix factorization matrix transposition G06F7/78
• CPC Class Codes: G06F 17/18 for evaluating statistical data , e.g. average values, frequency distributions, probability functions, regression analysis forecasting specially adapted for a specific administrative, business or logistic context G06Q10/04
• CPC Class Codes: G06F 2218/08 Feature extraction
• CPC Class Codes: G06Q 10/06375 Prediction of business process outcome or impact based on a proposed change
• CPC Class Codes: G06Q 40/06 Asset management; Financial planning or analysis

Abstract

A method for predicting extreme changes in numeric time series data includes converting a numeric time series into a sequence of symbols. A prediction method, such as a neural network or nearest neighbor algorithm is used to make the forecast. A numeric time series data is identified with extreme changes in them, and a window of length W that precedes the extreme change is extracted. Those extracts of a time series are built into a matrix (characteristic matrix) for singular value decomposition. The built matrix undergoes singular value decomposition, which reveals the characteristic vectors (symbols) that are indicative of time series that have characteristics that precede an extreme event. To perform forecasting, a window of length W in a new time series is generated and the dot product of the windows is taken against a predetermined number of columns of characteristic matrix, and, forecasting is performed on the new series.

Claims

1. A method for predicting extreme changes in numeric time series data comprising the steps of:

a) receiving a finite time series of data elements from said numeric time series data, said finite time series of data elements characterized as having one or more sharp changes in values;

b) for each sharp change in said finite time series of data elements, extracting a window of elements from said finite time series of data elements that precedes each sharp change;

c) building a matrix from said finite time series window extracts;

d) performing singular value decomposition on said built matrix to obtain characteristic vectors; and

,

e) obtaining a set of symbols from resulting characteristic vectors determined from said step d),

wherein said resulting set of symbols are used by a forecasting algorithm to predict a future sharp change in subsequent finite numeric time series data received.

2. The method as claimed in claim 1, wherein each extracted window comprises a time series vector of data elements, said step c) of building a matrix includes placing each time series vector of data elements in row-major order.

3. The method as claimed in claim 2, wherein said finite time series comprises T data elements having values denoted as y(t), said T data elements further characterized as having N extreme changes at time steps {k(1), k(2), . . . , k(N)}, said step c) of building said matrix comprising the steps of:

i) initialize index j=1;

ii) calculate x(j)={y(k(1)−

W), y(k(2)−

W), . . . , y(W)}, x(j) being elements of said built matrix;

iii) calculate said built matrix X={X;

x(j)};

iv) repeat steps i)-iii) until j=N.

4. The method as claimed in claim 3, wherein said step d) of performing singular value decomposition (svd) on said built matrix comprises computing:

X=USV^T where matrices U, S and V are characteristic matrices, said set of symbols to be used for predicting a future sharp change in subsequent finite numeric time series data are held in the characteristic matrix V.

5. The method as claimed in claim 4, further including the step of implementing a forecasting algorithm on a new received time series of data elements to determine whether a sharp change is expected in said new numeric time series data, wherein prior to implementing a forecasting algorithm, the steps of:

generating time series vector windows of length W in the new time series of data elements; and

, computing a dot product of said time series vector windows against a predetermined number of columns of said characteristic matrix V.

6. A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for predicting extreme changes in numeric time series data, the method steps comprising:

a) receiving a finite time series of data elements from said numeric time series data, said finite time series of data elements characterized as having one or more sharp changes in values;

b) for each sharp change in said finite time series of data elements, extracting a window of elements from said finite time series of data elements that precedes each sharp change;

c) building a matrix from said finite time series window extracts;

d) performing singular value decomposition on said built matrix to obtain characteristic vectors; and

,

e) obtaining a set of symbols from resulting characteristic vectors determined from said step d),

wherein said resulting set of symbols are used to predict a future sharp change in subsequent finite numeric time series data received.

7. The program storage device readable by a machine as claimed in claim 6, wherein each extracted window comprises a time series vector of data elements, said step c) of building a matrix includes placing each time series vector of data elements in row-major order.

8. The program storage device readable by a machine as claimed in claim 7, wherein said time series comprises T data elements having values denoted as y(t), said T data elements further characterized as having N extreme changes at time steps {k(1), k(2), . . . , k(N)}, said step c) of building said matrix comprising the steps of:

i) initialize index j=1;

ii) calculate x(j)={y(k(1)−

W), y(k(2)−

W), . . . , y(W)}, x(j) being elements of said built matrix;

iii) calculate said built matrix X={X;

x(j)};

iv) repeat steps i)-iii) until j=N.

9. The program storage device readable by a machine as claimed in claim 8, wherein said step d) of performing singular value decomposition (svd) on said built matrix comprises computing:

X=USV^T where matrices U, S and V are characteristic matrices, said set of symbols to be used for predicting a future sharp change in subsequent finite numeric time series data are held in the characteristic matrix V.

10. The program storage device readable by a machine as claimed in claim 9, wherein said method steps further includes the step of implementing a forecasting algorithm on a new received time series of data elements to determine whether a sharp change is expected in said new numeric time series data, wherein prior to implementing a forecasting algorithm, the steps of:

generating time series vector windows of length W in the new numeric time series data; and

,

computing a dot product of said time series vector windows against a predetermined number of columns of said characteristic matrix V.