Robust forecasting techniques with reduced sensitivity to anomalous data

• US 7,739,143 B1
• Filed: 03/24/2005
• Issued: 06/15/2010
• Est. Priority Date: 03/24/2005
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Dwarakanath, Samvid H., VanderBilt, Monty, Zook, John M.
• Primary Examiner(s): Jeanty; Romain
• Application Number:
  US11/089,537
• Time in Patent Office: 1,909 Days
• Field of Search: 705/10
• US Class Current: 705/7.31
• 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
• CPC Class Codes: G06Q 30/0202 Market predictions or forecasting for commercial activities

Abstract

Robust forecasting techniques are relatively immune from anomalies or outliers in observed data, such as a stream of data values reflective of the operation or use of a computer system. One robust technique provides a relatively accurate forecast of seasonal behavior even in the presence of an anomaly in corresponding historical data. Another robust forecasting technique provides a relatively accurate forecast even in the presence of an anomaly that spans multiple recent observations. In one embodiment, both techniques are used in combination to automatically detect anomalies in the operation and/or use of a multi-user computer system.

Claims

1. A computer-implemented method of computing a forecast F(t+x) for a second time t+x from at least an observation y(t) at a first time t earlier in time than the second time t+x, where x is a forecast time horizon, the method comprising:

obtaining from a computer memory a first plurality of seasonality factors from prior seasons for the first time t;

determining a first seasonal adjustment factor I_d(t) from the first plurality of seasonality factors;

computing a level component L(t) using at least the first seasonal adjustment factor I_d(t) and the observation y(t);

obtaining a second plurality of seasonality factors from prior seasons for the second time t+x;

determining a second seasonal adjustment factor I_d(t+x) from the second plurality of seasonality factors; and

computing, by execution of software by one or more processors, at least a first forecast F₁(t+x) at least partially based on the level component L(t) and the second seasonal adjustment factor I_d(t+x), wherein the first forecast F₁(t+x) is considered in determining the computed forecast F(t+x).

2. The method as defined in claim 1, wherein the observation y(t) is a metric associated with a monitored computer system.

3. The method as defined in claim 1, further comprising obtaining at least 3 seasonality factors for the first plurality of seasonality factors, where the at least 3 seasonality factors are from prior seasons that are most recent in time to the first time t.

4. The method as defined in claim 3, further comprising obtaining 5 seasonality factors for the first plurality of seasonality factors, where the 5 seasonality factors are from prior seasons that are most recent in time to the first time t, and wherein determining the first seasonal adjustment factor I_d(t) further comprises:

at least substantially ignoring a high value and a low value from among the 5 seasonality factors as components for the first seasonal adjustment factor I_d(t) such that there are 3 remaining seasonality factors; and

combining the 3 remaining seasonality factors to substantially determine the first seasonal adjustment factor I_d(t).

5. The method as defined in claim 4 wherein combining further comprises calculating an unequally weighted average.

6. The method as defined in claim 4 wherein weights for the unequally weighted average correspond to 50% for a median value of the 3 seasonality factors and to 25% for the other 2 seasonality factors.

7. The method as defined in claim 1 wherein determining the first seasonal adjustment factor I_d(t) further comprises computing an unequally weighted average of the seasonality factors.

8. The method as defined in claim 7 where the unequally weighted average weighs the seasonality factors that are near to or at a median value of the seasonality factors more heavily than seasonality factors that are near to or at the extreme values of the seasonality factors.

9. The method as defined in claim 7 where one or more weights for the unequally weighted average corresponds to zero.

10. The method as defined in claim 1 further comprising obtaining 3 or more seasonality factors, where the 3 or more seasonality factors are from prior seasons that are closest in time to the first time t, and wherein determining the first seasonal adjustment factor I_d(t) further comprises selecting a median value of the 3 or more seasonality factors.

11. The method as defined in claim 1 wherein determining the first seasonal adjustment factor I_d(t) further comprises dropping a high value and a low value of the first plurality of seasonality factors and combining the remaining seasonality values.

12. The method as defined in claim 1 wherein determining the first seasonal adjustment factor I_d(t) further comprises computing a geometric mean of at least a portion of the first plurality of seasonality factors.

13. The method as defined in claim 1 wherein computing the level component L(t) comprises computing:

14. The method as defined in claim 13 wherein computing the first forecast F₁(t+x) further comprises computing:

F₁(t+x)=L(t)I_d(t+x).

15. The method as defined in claim 1 wherein computing the level component L(t) comprises computing:

16. The method as defined in claim 1, further comprising:

computing a trend component T(t); and

computing the first forecast F₁(t+x) at least partially based on the level component L(t), the second seasonal adjustment factor I_d(t+x) the forecast time horizon x, and the trend component T(t).

17. The method as defined in claim 16 wherein computing the trend component T(t) comprises computing:

T(t)=γ

{L(t)−

L(t−

1)}+(1−

γ

)T(t−

1),

where γ

corresponds to a smoothing value between 0 and 1, where L(t−

1) denotes a value of the level component from a prior forecast at time t−

1, and where T(t−

1) corresponds to a value of the trend component from the prior forecast at time t−

1.

18. The method as defined in claim 17 wherein computing the first forecast F₁(t+x) comprises computing:

F₁(t+x)={L(t)+xT(t)}I_d(t+x).

19. The method as defined in claim 1, further comprising:

obtaining one or more supplemental forecasts also for the forecast time t+x, where the one or more supplemental forecasts are based only on data from earlier in time than the time t; and

determining a value for the forecast F(t+x) using the first forecast F₁(t+x) and the one or more supplemental forecasts.

20. The method as defined in claim 1, further comprising:

obtaining a second forecast F₂(t+x)|<sub>t−

m</sub> corresponding to a forecast for the second time t+x made using data ending with an observation from a first earlier time t−

m;

obtaining a third forecast F₃(t+x)|<sub>t−

2m</sub> corresponding to a forecast for the second time t+x made using data ending with an observation from a second earlier time t−

2m; and

selecting a median of the first forecast F₁(t+x), the second forecast F₂(t+x)|<sub>t−

m</sub>, and the third forecast F₃(t+x)|<sub>t−

2m</sub> as the computed forecast F(t+x) corresponding to the second time t+x.

21. The method as defined in claim 1 wherein obtaining further comprises retrieving a pre-calculated value.

22. The method as defined in claim 1 wherein obtaining further comprises calculating from one or more observations.

23. The method as defined in claim 1, further comprising:

receiving raw data corresponding to the observation y(t); and

processing the raw data to generate the observation y(t).

24. The method as defined in claim 23 wherein processing comprises smoothing the raw data with a low-pass filter.

25. The method as defined in claim 23 wherein processing comprises:

converting a portion of a time series including the observation y(t) to frequency domain;

low-pass filtering in frequency domain; and

converting the low-pass filtered frequency domain series back to time domain.

26. The method as defined in claim 23 wherein processing comprises computing a square root of the raw data.

27. The method as defined in claim 1, further comprising:

obtaining observations at a higher rate than computing forecasts; and

interpolating between forecasts to generate an estimate for a forecast for a corresponding observation.

28. The method as defined in claim 1, further comprising:

determining an expected range for the observation y(t) at least partially based on one or more corresponding forecasts, wherein the observation y(t) is a metric associated with a monitored computer system; and

comparing the observation y(t) to the one or more forecasts or to the expected range to determine whether an abnormality exists in the monitored computer system.

29. The method as defined in claim 28, further comprising automatically generating an alert at least partially in response to determining that the observation y(t) falls outside the expected range.

30. The method as defined in claim 28, further comprising automatically determining that corrective action is needed in a system associated with the observation y(t) when the observation y(t) falls outside the expected range.

31. The method as defined in claim 1, wherein the observation y(t) corresponds to a metric corresponding to a performance of a networked system with at least one computer, the method further comprising:

determining an expected range for the observation y(t) at least partially based on one or more corresponding forecasts;

comparing the observation y(t) to the one or more prior forecasts or to the expected range to determine whether an abnormality exists in the networked system; and

programmatically generating an alert at least partially in response to determining that the observation y(t) falls outside the expected range.

32. The method as defined in claim 1 where a seasonal period used for obtaining seasonality factors corresponds to a day, a week, a month, a quarter, a year, or a multiple thereof.

33. The method as defined in claim 1, further comprising using a calendar period as the seasonal period and accounting for daylight savings time in obtaining the plurality of seasonality factors.

34. The method as defined in claim 1, wherein the method in its entirety is performed by execution of software by one or more processors.

35. A computer-readable medium having stored thereon a set of program modules that, when executed by a computer, cause the computer to perform a method of computing a forecast F(t+x) for a second time t+x from at least an observation y(t) at a first time t earlier in time than the second time t+x, where x is a forecast time horizon, the method comprising:

obtaining from a computer memory a first plurality of seasonality factors from prior seasons for the first time t;

determining a first seasonal adjustment factor I_d(t) from the first plurality of seasonality factors;

computing a level component L(t) using at least the first seasonal adjustment factor I_d(t) and the observation y(t);

obtaining a second plurality of seasonality factors from prior seasons for the second time t+x

determining a second seasonal adjustment factor I_d(t+x) from the second plurality of seasonality factors; and

computing at least a first forecast F₁(t+x) at least partially based on the level component L(t) and the second seasonal adjustment factor I_d(t+x), wherein the first forecast F₁(t+x) is considered in determining the computed forecast F(t+x).

36. A computer-implemented method of computing a forecast F(t+x) for a second time t+x from at least an observation y(t) at a first time t earlier in time than the second time t+x, where x is a forecast time horizon, the method comprising:

collecting a predetermined number of seasonality factors from prior seasons from a computer memory for the first time t, where a seasonality factor corresponds to a time that is an integer multiple of seasonal periods from the first time t;

deseasonalizing the observation y(t) at the first time t using fewer than all of the collected seasonality factors;

computing a level component using the observation y(t) as deseasonalized; and

computing, by execution of software by one or more processors, at least a first forecast F₁(t+x) at least partially based on the level component and a second seasonal adjustment factor for the second time t+x.

37. The method as defined in claim 36, further comprising:

collecting a predetermined number of second seasonality factors from prior seasons from a computer memory for the second time t+x, where a second seasonality factor corresponds to a time that is an integer multiple of seasonal periods from the second time t+x; and

using fewer than all of the collected second seasonality factors to generate the second seasonal adjustment factor.

38. The method as defined in claim 36, wherein the predetermined number is a fixed number.

39. The method as defined in claim 36, wherein the observation y(t) is of a metric associated with a monitored computer system.

40. The method as defined in claim 36, further comprising:

computing a trend component; and

computing the first forecast F₁(t+x) at least partially based on the level component, the seasonal adjustment factor, the forecast time horizon x, and the trend component.

41. The method as defined in claim 36, further comprising:

obtaining one or more supplemental forecasts also for the forecast time t+x, where the one or more supplemental forecasts are at least partially based on data ending with an observation from earlier in time than the observation y(t); and

determining a value for the forecast F(t+x) using the first forecast F₁(t+x) and the one or more supplemental forecasts.

42. The method as defined in claim 36, wherein the observation y(t) corresponds to a metric corresponding to a performance of a networked system with at least one computer, the method further comprising:

determining an expected range for the observation y(t) at least partially based on one or more corresponding forecasts;

comparing the observation y(t) to the one or more prior forecasts or to the expected range to determine whether an abnormality exists in the networked system; and

programmatically generating an alert at least partially in response to determining that the observation y(t) falls outside the expected range.

43. The method as defined in claim 36, wherein the method in its entirety is performed by execution of software by one or more processors.

44. A computer-readable medium having stored thereon a set of program modules that, when executed by a computer, cause the computer to perform a method of computing a forecast F(t+x) for a second time t+x from at least an observation y(t) at a first time t earlier in time than the second time t+x, where x is a forecast time horizon, the method comprising:

collecting a predetermined number of seasonality factors from prior seasons from a computer memory for the first time t, where a seasonality factor corresponds to a time that is an integer multiple of seasonal periods from the first time t;

deseasonalizing the observation y(t) at the first time t using fewer than all of the collected seasonality factors;

computing a level component using the observation y(t) as deseasonalized; and

computing at least a first forecast F₁(t+x) at least partially based on the level component and a second seasonal adjustment factor for the second time t+x.

45. A computer-implemented method of computing a forecast for a time t+x from a time t for a monitored system, the method comprising:

computing a seasonal adjustment factor for the time t+x and a seasonal adjustment factor for the time t, wherein at least one of the computed seasonal adjustment factors is computed from a plurality of seasonality factors such that the at least one computed seasonal adjustment factor is representative of a normal operating condition of the monitored system; and

using the computed seasonal adjustment factors to compute the forecast by execution of software by one or more processors.

46. The method as defined in claim 45, wherein computing further comprises at least one of retrieving a plurality of seasonality factors and selecting the most representative seasonality factors, computing an unequally weighted average based on relative values among the seasonality factors, selecting a median value, or any combination thereof.

47. The method as defined in claim 45, wherein the method in its entirety is performed by execution of software by one or more processors.