Boosted linear modeling of non-linear time series

• US 20070233435A1
• Filed: 03/31/2006
• Published: 10/04/2007
• Est. Priority Date: 03/31/2006
• Status: Abandoned Application

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Bradski, Gary
• Application Number:
  US11/394,834
• Publication Number:
  US 20070233435A1
• Time in Patent Office: Days
• US Class Current: 703/2
• 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

Abstract

A method and apparatus for boosted linear modeling of non-linear time series. An embodiment of a method includes receiving a series of data elements, where the series of data elements is a time series and where the time series has a non-linearity. One or more decision trees are generated for the data elements, with the decision tree models dividing the time series into a plurality of data groups. Further, each of the data groups is modeled as a linear function.

Claims

1. A computer implemented method comprising:

receiving a series of data elements, the series of data elements comprising a time series, the time series having a non-linearity;

generating one or more decision trees for the data elements, the one or more decision tree models dividing the time series into a plurality of data groups; and

modeling each of the data groups as a linear function.

2. The method of claim 1, further comprising statistically boosting the one or more decision tree models.

3. The method of claim 2, wherein boosting the one or more decision tree models comprises providing a set of training data to a first decision tree model and determining which data points are incorrectly predicted.

4. The method of claim 3, wherein boosting the one or more decision tree models further comprises generating a weight adjustment factor for the decision tree.

5. The method of claim 4, wherein boosting the one or more decision tree models further comprises using the weight adjustment factor to adjust a weight value allocated to each data element of the training data based on which data points are incorrectly predicted.

6. The method of claim 1, wherein generating the one or more decision tree models includes performing an autoregressive analysis of the time series over a previous n data points.

7. The method of claim 1, wherein generating the one or more decision tree models further includes choosing a feature of the time series data and separating the time series data based on whether each data point meets a requirement of the feature.

8. A time series analyzer comprising:

a first module to divide a non-linear time series into a plurality of data groups;

a second module to model each of the plurality of portions as a linear time series model; and

a third module to statistically boost the plurality of linear time series models.

9. The time series analyzer of claim 8, wherein the division of the time series into a plurality of data groups includes choosing a data feature to maximize homogeneity between data groups.

10. The time series analyzer of claim 9, wherein the first module divides the time series using one or more decision trees.

11. The time series analyzer of claim 10, wherein the one or more decision trees are based on Classification and Regression Trees (CART) technology.

12. The time series analyzer of claim 10, wherein each of the one or more decision trees comprises a stump with a single split.

13. A system comprising:

a communication device to receive time series data for analysis, the time series data being non-linear;

a dynamic access memory to hold the time series data received by the communication device; and

a processor to perform time series analysis, the processor to split the time series data into a plurality of data sets, the processor to model each of the data sets as a linear model.

14. The system of claim 13, wherein the processor is to further statistically boost the linear models.

15. The system of claim 14, wherein the processor boosting the linear models includes modifying a weight value for each data point being processed using the linear model, wherein the modification of the weight values increases the weight given to a data point that is predicted incorrectly and generates a weighted vote for the associated linear model.

16. The system of claim 13, wherein the processor is to split the time series data using one or more decision trees.

17. A machine-readable medium having stored thereon data representing sequences of instructions that, when executed by a machine, cause the machine to perform operations comprising:

receiving data in a time series, the time series being non-linear;

generating a plurality of decision tree models for the data elements, the plurality of decision tree models dividing the time series into a plurality of data groups according to data features, the plurality of decision tree models modeling each of the data groups as a linear function; and

statistically boosting the plurality of decision tree models.

18. The medium of claim 17, wherein boosting the plurality of decision tree models comprises applying a set of training data to a first decision tree model of the plurality of decision tree models and determining which data points of the set of training data are incorrectly predicted by the first decision tree model.

19. The medium of claim 17, wherein boosting the plurality of decision tree models further comprises adjusting the weight given to each data element of the training data based on which data points are determined to be incorrectly predicted.

20. The medium of claim 19, wherein boosting the plurality of decision tree models further comprises applying the training data with adjusted weights to a second decision tree model of the plurality of decision tree models and further generating a weighted vote for the first decision tree model.

21. The medium of claim 17, wherein generating the one or more decision tree models further includes choosing a feature of the time series data for each of the one or more decision tree models and separating the time series data based on whether each data point meets a requirement of the feature.

22. The medium of claim 21, wherein a first feature is used for a first decision tree model of the plurality of decision tree models and for a second decision tree model of the plurality of decision tree models.