Systems and methods for clustering time series data based on forecast distributions

• US 9,336,493 B2
• Filed: 06/06/2011
• Issued: 05/10/2016
• Est. Priority Date: 06/06/2011
• Status: Active Grant

• Current Assignee: SAS Institute Incorporated
• Original Assignee: SAS Institute Incorporated
• Inventors: Lee, Taiyeong, Duling, David Rawlins
• Primary Examiner(s): HARPER, ELIYAH STONE
• Application Number:
  US13/153,899
• Publication Number:
  US 20120310939A1
• Time in Patent Office: 1,800 Days
• Field of Search: 707/736, 707/999.102, 707/637, 707/748
• US Class Current: 1/1
• CPC Class Codes: G06F 16/285 Clustering or classification
• CPC Class Codes: G06F 16/335 Filtering based on additional data, e.g. user or group profiles filtering in web context G06F16/9535, G06F16/9536
• CPC Class Codes: G06F 16/907 Retrieval characterised by using metadata, e.g. metadata not derived from the content or metadata generated manually
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06Q 10/04 Forecasting or optimisation specially adapted for administrative or management purposes, e.g. linear programming or "cutting stock problem" market predictions or forecasting for commercial activities G06Q30/0202

Abstract

In accordance with the teachings described herein, systems and methods are provided for clustering time series based on forecast distributions. A method for clustering time series based on forecast distributions may include: receiving time series data relating to one or more aspects of a physical process; applying a forecasting model to the time series data to generate forecasted values and confidence intervals associated with the forecasted values, the confidence intervals being generated based on distribution information relating to the forecasted values; generating a distance matrix that identifies divergence in the forecasted values, the distance matrix being generated based the distribution information relating to the forecasted values; and performing a clustering operation on the plurality of forecasted values based on the distance matrix. The distance matrix may be generated using a symmetric Kullback-Leibler divergence algorithm.

Claims

1. A computer-implemented method, comprising:

accessing a set of variables, wherein accessing is performed at a computing device;

accessing time series data with respect to each of the variables of the set;

with respect to each of the variables of the set, forecasting values and determining a distribution of the forecasted values, wherein forecasting includes using a forecasting model and the time series data accessed with respect to each of the variables;

identifying all possible variable pairs, wherein each of the variable pairs consists of two of the variables of the set;

with respect to each of the variables pairs, calculating a divergence metric using the distributions of the forecasted values for the variables of the respective variable pair; and

defining clusters such that at least one of the clusters includes two or more of the variables of the set, wherein defining the clusters is performed using a hierarchical clustering algorithm and is based on the calculated divergence metrics, wherein each of the divergence metrics is a symmetric Kullback-Leibler divergence metric, wherein, with respect to each of the variable pairs, the calculated symmetric Kullback-Leibler divergence metric is equal to;

2. The method of claim 1, wherein the forecasting model includes at least one of:

an exponential smoothing model;

a moving average model;

an autoregressive model;

or

an autoregressive integrated moving average model.

3. The method of claim 1, wherein the hierarchical clustering algorithm includes at least one of a single-link clustering algorithm, an average-link clustering algorithm, or a complete-link clustering algorithm.

4. The method of claim 1, further comprising:

applying a common pricing policy based on at least one of the defined clusters.

5. The method of claim 1, further comprising:

receiving a clustering parameter specifying a number of clusters, wherein defining the clusters is based on the clustering parameter.

6. The method of claim 1, further comprising:

generating a distance matrix based on the Kullback-Leibler divergence metrics.

17. The method of claim 1, wherein, with respect to each of the variables of the set:

the forecasted values and the distribution of the forecasted values are associated with a future time period;

determining the distribution of the forecasted values includes adding multiple distributions of values, wherein each of the added distributions is associated with a particular time during the future time period and represents one of the forecasted values; and

forecasting the values includes determining the multiple distributions that are added.

7. A computer-implemented system, comprising:

one or more data processors; and

one or more non transitory computer-readable storage media containing instructions operable to cause the one or more processors to perform operations including;

accessing a set of variables;

accessing time series data with respect to each of the variables of the set;

with respect to each of the variables of the set forecasting values and determining a distribution of the forecasted values, wherein forecasting includes using a forecasting model and the time series data accessed with respect to each of the variables;

identifying all possible variable pairs, wherein each of the variable pairs consists of two of the variables of the set;

with respect to each of the variables pairs, calculating a divergence metric using the distributions of the forecasted values for the variables of the respective variable pair; and

defining clusters such that at least one of the clusters includes two or more of the variables of the set, wherein defining the clusters is performed using a hierarchical clustering algorithm and is based on the calculated divergence metrics, wherein each of the divergence metrics is a symmetric Kullback-Leibler divergence metric, wherein, with respect to each of the variable pairs, the calculated symmetric Kullback-Leibler divergence metric is equal to;

8. The system of claim 7, wherein the forecasting model includes at least one of:

an exponential smoothing model;

a moving average model;

an autoregressive model;

or

an autoregressive integrated moving average model.

9. The system of claim 7, wherein the hierarchical clustering algorithm includes at least one of a single-link clustering algorithm, an average-link clustering algorithm or a complete-link clustering algorithm.

10. The system of claim 7, wherein the operations further include applying a common pricing policy based on at least one of the defined clusters.

11. The system of claim 7, wherein the operations further include:

receiving a clustering parameter specifying a number of clusters,

and wherein defining the clusters is performed based on the clustering parameter.

18. The system of claim 7, wherein, with respect to each of the variables of the set:

the forecasted values and the distribution of the forecasted values are associated with a future time period;

determining the distribution of the forecasted values includes adding multiple distributions of values, wherein each of the added distributions is associated with a particular time during the future time period and represents one of the forecasted values; and

forecasting the values includes determining the multiple distributions that are added.

12. A computer-program product tangibly embodied in a non-transitory machine-readable storage medium, the computer-program product including instructions operable to cause a data processing apparatus to perform operations including:

accessing a set of variables;

accessing time series data with respect to each of the variables of the set;

with respect to each of the variables of the set, forecasting values and determining a distribution of the forecasted values, wherein forecasting includes using a forecasting model and the time series data accessed with respect to each of the variables;

identifying all possible variable pairs, wherein each of the variable pairs consists of two of the variables of the set;

with respect to each of the variables pairs, calculating a divergence metric using the distributions of the forecasted values for the variables of the respective variable pair; and

defining clusters such that at least one of the clusters includes two or more of the variables of the set, wherein defining the clusters is performed using a hierarchical clustering algorithm and is based on the calculated divergence metrics, wherein each of the divergence metrics is a symmetric Kullback-Leibler divergence metric, wherein, with respect to each of the variable pairs, the calculated symmetric Kullback-Leibler divergence metric is equal to;

13. The computer-program product of claim 12, wherein a forecasting model includes at least one of:

an exponential smoothing model;

a moving average model;

an autoregressive model;

or

an autoregressive integrated moving average model.

14. The computer-program product of claim 12, wherein the hierarchical clustering algorithm includes at least one of a single-link clustering algorithm, an average-link clustering algorithm or a complete-link clustering algorithm.

15. The computer-program product of claim 12, wherein the operations further include:

applying a common pricing policy based on at least one of the defined clusters.

16. The computer-program product of claim 12, wherein the operations further include:

receiving a clustering parameter specifying a number of clusters,

wherein defining the clusters is based on the clustering parameter.

19. The computer-program product of claim 12, wherein, with respect to each of the variables of the set:

the forecasted values and the distribution of the forecasted values are associated with a future time period;

determining the distribution of the forecasted values includes adding multiple distributions of values, wherein each of the added distributions is associated with a particular time during the future time period and represents one of the forecasted values; and

forecasting the values includes determining the multiple distributions that are added.