Robust forecasting techniques with reduced sensitivity to anomalous data

• US 7,610,214 B1
• Filed: 03/24/2005
• Issued: 10/27/2009
• 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
• Assistant Examiner(s): Singh; Gurkanwaljit
• Application Number:
  US11/089,452
• Time in Patent Office: 1,678 Days
• Field of Search: 705/7, 705/8, 705/10, 379/10, 379/13
• US Class Current: 705/7.31
• CPC Class Codes: G06F 11/008 Reliability or availability analysis
• 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) of a metric of a monitored computer system for a forecast time t+x, the method comprising:

generating a first forecast F₁(t+x) of the metric of the monitored computer system for the forecast time t+x at least partially based on an observation y(t) of the monitored computer system from a first time t earlier in time to the forecast time t+x;

obtaining one or more supplemental forecasts of the metric of the monitored computer system also for the forecast time t+x, where each of the one or more supplemental forecasts are based on data ending earlier in time than the first time t;

determining by execution of software by one or more processors, a value for the forecast F(t+x) from the first forecast F₁(t+x) and the one or more supplemental forecasts; and

performing at least one of the following actions based at least in part on the determined value of the forecast F(t+x);

(1) detecting an abnormality associated with the monitored computer system, (2) generating an alert or a report, and (3) automatically initiating a corrective procedure.

2. The method as defined in claim 1, wherein:

obtaining further comprises obtaining a first supplemental forecast F₂(t+x)|<sub>t−

m</sub> and a second supplemental forecast F₃(t+x)|<sub>t−

2m</sub>, where the first supplemental forecast F₂(t+x)|<sub>t−

m</sub> is at least partially based on an observation y(t−

m) from a first earlier time t−

m earlier in time than the first time t, where the second supplemental forecast F₃(t+x)|<sub>t−

2m</sub> is at least partially based on an observation y(t−

2m) from a second earlier time t−

2m earlier in time than the first earlier time t−

m; and

determining further comprises selecting a median value as the value for the forecast F(t+x), where the median value is selected from the first forecast F₁(t+x), the first supplemental forecast F₂(t+x)|<sub>t−

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

2m</sub>.

3. The method as defined in claim 1, further comprising selecting a minimum value for interval m to be larger than a duration of a typical anomaly.

4. The method as defined in claim 1 wherein determining further comprises selecting a median value from the first forecast F₁(t+x) and the one or more supplemental forecasts, and using the median value as the value for the seasonally adjusted forecast F(t+x).

5. The method as defined in claim 1 wherein determining further comprises computing an unequally weighted average of the first forecast F₁(t+x) and the one or more supplemental forecasts.

6. The method as defined in claim 5 where one or more weights for the unequally weighted average includes zero.

7. The method as defined in claim 1, further comprising obtaining at least two supplemental forecasts, and wherein determining further comprises discarding at least a high value and a low value of the first forecast F₁(t+x) and the at least two supplemental forecasts, and using one or more remaining forecasts after discarding to determine the forecast F(t+x).

8. The method as defined in claim 1, wherein the forecast F(t+x) corresponds to the metric corresponding to performance of a networked system with at least one computer, the method further comprising:

determining an expected range at least partially based on the forecast F(t+x); and

programmatically generating an alert at least partially in response to determining that an observation for forecast time t+x falls outside the expected range.

9. A computer-readable medium having stored thereon a set of program modules that, when executed by a computer, cause the computer to perform the method of claim 1.

10. The method as defined in claim 1, wherein the method comprises detecting an abnormality associated with the monitored computer system based at least in part on the determined value of the forecast F(t+x).

11. The method as defined in claim 10, wherein detecting the abnormality comprises programmatically comparing an observation of the monitored computer system with the forecast F(t+x) or a range at least partially based on the forecast F(t+x).

12. The method as defined in claim 1, wherein the method comprises generating an alert or a report based at least in part on the determined value of the forecast F(t+x).

13. The method as defined in claim 12, wherein the method comprises generating an alert based at least in part on the determined value of the forecast F(t+x), the alert comprising an electronic message.

14. The method as defined in claim 12, wherein the method comprises generating a report, the report comprising information based at least in part on observations of the monitored computer system and the forecast F(t+x).

15. The method as defined in claim 1, wherein the method comprises automatically initiating a corrective procedure at least partially in response to the determined value of the forecast F(t+x).

16. The method as defined in claim 15, wherein automatically initiating the corrective procedure comprises one or more of the following:

(1) executing a load balancing program, (2) rebooting or reconfiguring a server, and (3) correcting erroneous data on a web site.

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

18. A computer-implemented method of computing a forecast F(t+x) of a metric associated with a monitored computer system for a forecast time t+x, the method comprising:

obtaining a plurality of forecasts of the metric associated with the monitored computer system for the forecast time t+x, where the plurality includes forecasts based on observations of the monitored computer system ending at different times;

comparing at least a portion of the obtained forecasts to each other;

selecting at least a portion of the obtained forecasts for computation of the forecast F(t+x) at least partially in response to the comparison the computation of the forecast F(t+x) performed by execution of software by one or more processors; and

using the computed forecast F(t+x) at least in part for detecting an anomaly associated with the monitored computer system.

19. The method as defined in claim 18, wherein the selected forecasts are computed using data ending at times spaced at least a minimum value apart, where the minimum value is at least as large as an estimated downtime of the monitored computer system.

20. The method as defined in claim 18, further comprising selecting a median value of the obtained forecasts as the forecast F(t+x).

21. The method as defined in claim 18, further comprising dropping a high value and a low value from the obtained forecasts for the computation of the forecast F(t+x).

22. The method as defined in claim 18, further comprising selectively weighting the forecasts in an unequally weighted average for the computation of the forecast F(t+x), where forecasts near to or at a median value of the forecasts are more heavily weighted than forecasts that are near to or at extreme values.

23. The method as defined in claim 18, wherein the forecast F(t+x) corresponds to the metric corresponding to performance of a networked system with at least one computer, the method further comprising:

determining an expected range at least partially based on the forecast F(t+x); and

programmatically generating an alert at least partially in response to determining that an observation corresponding to the forecast F(t+x) falls outside the expected range.

24. A computer-readable medium having stored thereon a set of program modules that, when executed by a computer, cause the computer to perform the method of claim 18.

25. The method as defined in claim 18, wherein using the computed forecast at least in part for detecting an anomaly associated with the monitored computer system comprises determining whether an observation of the monitored computer system is out of an expected range based at least in part on the computed forecast.

26. The method as defined in claim 25, wherein the expected range is based on a selected amount of variability away from the computed forecast.

27. The method as defined in claim 18, the method further comprising generating an alert regarding the detected anomaly.

28. The method as defined in claim 27, further comprising using the alert at least in part for (1) disabling a process or machinery, (2) initiating a data logging process, or both (1) and (2).

29. The method as defined in claim 18, further comprising automatically initiating a corrective procedure in response to detecting the anomaly.

30. The method as defined in claim 29, wherein automatically initiating the corrective procedure comprises one or more of the following:

(1) executing a load balancing program, (2) rebooting or reconfiguring a server, and (3) correcting erroneous data on a web site.

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

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

generating multiple independent forecasts of the monitored computer system for the time t+x, wherein the multiple forecasts are generated using data up to multiple different times spaced apart by at least an interval m, where m is selected to be at least as long as the length of time that an abnormality in the monitored system is expected to last; and

determining by execution of software by one or more processors, the forecast of the monitored computer system based at least in part on the multiple independent forecasts, such that the forecast is representative of the normal operational state of the monitored computer system.

33. The method as defined in claim 32, wherein the forecast is generated by at least one of unequally weighted averaging based on relative values among the independent multiple forecasts, capping of data values, the selection of a median value, or any combination thereof.

34. The method as defined in claim 32, further comprising performing at least one of the following actions based at least in part on the stored forecast:

(1) detecting an abnormality associated with the monitored computer system, (2) generating an alert or a report, and (3) automatically initiating a corrective procedure.

35. The method as defined in claim 34, wherein the method comprises detecting an abnormality associated with the monitored computer system, the abnormality detected at least in part by programmatically comparing an observation of the monitored computer system with the stored forecast or a range at least partially based on the stored forecast.

36. The method as defined in claim 34, wherein the method comprises generating an alert based at least in part on the stored forecast, the alert comprising an electronic message.

37. The method as defined in claim 34, wherein the method comprises generating an alert based at least in part on the stored forecast, the method further comprising using the alert at least in part for (1) disabling a process or machinery, (2) initiating a data logging process, or both (1) and (2).

38. The method as defined in claim 34, the method comprising automatically initiating a corrective procedure, the corrective procedure comprising one or more of the following:

(1) executing a load balancing program, (2) rebooting or reconfiguring a server, and (3) correcting erroneous data on a web site.

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

40. The method as defined in claim 32, further comprising automatically storing the forecast in a computer storage medium.

41. A system for monitoring a monitored computer system, the monitoring system comprising:

a computer memory configured to store one or more program modules for computing a forecast F(t+x) of a metric of the monitored computer system for a forecast time t+x;

a processor configured to communicate with the computer memory, the processor configured to execute the one or more program modules stored on the computer memory, the program modules configured to;

generate a first forecast F₁(t+x) of the metric of the monitored computer system for the forecast time t+x at least partially based on an observation y(t) of the monitored computer system from a first time t earlier in time to the forecast time t+x;

obtain one or more supplemental forecasts of the metric of the monitored computer system also for the forecast time t+x, where each of the one or more supplemental forecasts are based on data ending earlier in time than the first time t; and

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

42. The monitoring system as defined in claim 41, wherein the monitoring system is further configured to perform at least one of the following based at least in part on the determined value of the forecast F(t+x):

(1) detect an abnormality of the monitored computer system, (2) generate an alert or a report, and (3) automatically initiate a corrective procedure.