Robust forecasting techniques with reduced sensitivity to anomalous data

• US 8,370,194 B2
• Filed: 03/17/2010
• Issued: 02/05/2013
• 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:
  US12/726,188
• Publication Number:
  US 20100185499A1
• Time in Patent Office: 1,056 Days
• Field of Search: 705/7.37
• US Class Current: 705/7.37
• 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 system for monitoring a monitored computer system, the monitoring system comprising:

a computer data repository that stores a first plurality of seasonality factors for a first time t from prior seasons for the monitored computer system and a second plurality of seasonality factors for a second time t+x from prior seasons for the monitored computer system, where x is a forecast time horizon; and

a processor programmed, via executable program code, to at least;

determine a first seasonal adjustment factor for the first time t based at least in part on the first plurality of seasonality factors;

deseasonalize an observation y(t) of a metric of the monitored computer system at the first time t based at least in part on the first seasonal adjustment factor;

determine a level component based at least in part on the deseasonalized observation of the monitored computer system;

determine a second seasonal adjustment factor for the second time t+x based at least in part on the second plurality of seasonality factors; and

compute a first forecast F₁(t+x) based at least in part on the level component and the second seasonal adjustment factor for the second time t+x, wherein the first forecast F₁(t+x) is considered in determining a computed forecast F(t+x) for the metric of the monitored computer system.

2. The system of claim 1, wherein the first plurality of seasonality factors are from the prior seasons that are closest in time to the first time t.

3. The system of claim 1, wherein the processor is further programmed to determine the first seasonal adjustment factor by calculating an average of at least some of the first plurality of seasonality factors.

4. The system of claim 1, wherein the first plurality of seasonality factors comprises at least three seasonality factors, and the processor is further programmed to:

at least substantially ignore a high value and a low value from among the at least three seasonality factors; and

determine the first seasonal adjustment factor from the remaining seasonality factors.

5. The system of claim 1, wherein the second plurality of seasonality factors are from the prior seasons that are closest in time to the second time t+x.

6. The system of claim 1, wherein the processor is further programmed to determine the second seasonal adjustment factor by calculating an average of at least some of the second plurality of seasonality factors.

7. The system of claim 1, wherein the second plurality of seasonality factors comprises at least three seasonality factors, and the processor is further programmed to:

at least substantially ignore a high value and a low value from among the at least three seasonality factors; and

determine the second seasonal adjustment factor from the remaining seasonality factors.

8. The system of claim 1, wherein the processor is further programmed to:

compute a trend component; and

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

9. The system of claim 1, wherein the processor is further programmed to:

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

determine a value for the forecast F(t+x) based at least in part on one or more of the first forecast F₁(t+x) and the one or more supplemental forecasts.

10. The system of claim 9, wherein to obtain the one or more supplemental forecasts the processor is further programmed to:

determine a second forecast F₂(t+x) based on observations of the metric of the monitored computer system from times earlier than t−

m;

determine a third forecast F₃(t+x) based on observations of the metric of the monitored computer system from times earlier than t−

2m, where m is a time interval.

11. The system of claim 10, wherein the time interval m is selected to be longer than a duration of an expected or typical anomaly of the metric of the monitored computer system.

12. The system of claim 1, wherein the processor is further programmed to:

determine an expected range of observations of the metric of the monitored computer system, the expected range at least partially based on the computed forecast F(t+x); and

compare an observation y(t+x) to the computed forecast F(t+x) or to the expected range of observations to determine whether an anomaly is present in the monitored computer system.

13. The system of claim 12, wherein the processor is further programmed to generate an alert or initiate a corrective action at least partially in response to the determination that an anomaly is present in the monitored computer system.

14. The system of claim 13, wherein the corrective action 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.

15. The system of claim 13, wherein the alert comprises an electronic message.

16. The system of claim 1, wherein the processor is further programmed to acquire a stream of data values from the monitored computer system, the data values representative of the metric of the monitored computer system.

17. The system of claim 16, wherein to acquire the stream of data values, the processor is further programmed to perform one or more of the following:

(1) monitor traffic generated on a computer network by the monitored computer system, (2) make API calls or queries to the monitored computer system, and (3) communicate with a software-based probe configured to run on the monitored computer system.

18. The system of claim 1, wherein the monitored computer system comprises a networked system comprising at least one computer.

19. The system of claim 1, wherein the metric of the monitored computer system comprises one or more of the following:

a server response time, a page latency, a CPU utilization, a system load, and a number of processing operations per unit time.

20. The system of claim 1, wherein the monitored computer system provides functionality for users to purchase items, and the metric of the monitored computer system comprises one or more of the following:

an item order rate, an item price, and an item popularity.

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

a data repository configured to store observation data for a metric of the monitored computer system; and

computer hardware configured to execute an anomaly detection engine, the anomaly detection engine comprising;

a forecasting component configured to determine a forecast for a time t+x from a time t of the metric of the monitored computer system, where x is a forecast time horizon, the forecasting component configured to;

compute, based at least in part on the stored observation data, 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 computer system; and

determine the forecast based at least in part on at least one of the computed seasonal adjustment factors.

22. The system of claim 21, further comprising a data acquisition component configured to receive data values related to the metric of the monitored computer system, the observation data stored by the data repository related to the received data values.

23. The system of claim 21, wherein the anomaly detection engine further comprises an anomaly detection component configured to:

determine an expected range of observations of the metric of the monitored computer system, the expected range at least partially based on the forecast determined by the forecasting component;

compare the observation data to the forecast or to the expected range of observations to determine whether there is an anomaly in the monitored computer system; and

generate an alert or initiate a corrective action at least partially in response to the determination that there is an anomaly in the monitored computer system.

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

a data repository configured to store observation data for a metric of the monitored computer system; and

computer hardware configured to execute an anomaly detection engine, the anomaly detection engine comprising;

a forecasting component configured to determine a forecast for a time t+x from a time t of the metric of the monitored computer system, where x is a forecast time horizon, the forecasting component configured to;

generate a plurality of individual forecasts of the metric of the monitored computer system for the time t+x, where each of the plurality of individual forecasts is based on observation data ending earlier in time than the time t; and

compute the forecast for the time t+x based at least in part on the plurality of individual forecasts; and

an anomaly detection component configured to;

determine the presence of an anomaly in the metric of the monitored computer system based at least in part on one or more of;

(1) the observation data, (2) the forecast for the time t+x, and (3) an expected range of observations of the metric of the monitored computer system, the expected range at least partially based on the computed forecast for the time t+x; and

generate an alert or initiate a corrective action at least partially in response to the determined presence of an anomaly in the monitored computer system.

25. The system of claim 24, wherein to generate at least some of the plurality of individual forecasts, the forecasting component is configured to:

receive from the data repository a number of seasonality factors from prior seasons for the first time t, where a seasonality factor corresponds to a time that is an integer multiple of seasonal periods prior to the first time t;

deseasonalize the observation data at the time t using at least some of the collected seasonality factors;

compute a level component based at least in part on the deseasonalized observation data; and

compute at least one individual forecast based at least in part on the level component and a second seasonal adjustment factor for the time t+x.

26. The system of claim 25, wherein to determine the second seasonal adjustment factor for the time t+x, the forecasting component is configured to:

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

determine the second seasonal adjustment factor using at least some of the second seasonality factors.