Time series anomaly detection using multiple statistical models

• US 7,310,590 B1
• Filed: 11/15/2006
• Issued: 12/18/2007
• Est. Priority Date: 11/15/2006
• Status: Active Grant

• Current Assignee: CA, Inc. (d/b/a CA Technologies) (Broadcom, Inc.)
• Original Assignee: Computer Associates Think Inc. (Broadcom, Inc.)
• Inventors: Bansal, Jyoti
• Primary Examiner(s): Raymond; Edward
• Application Number:
  US11/560,312
• Time in Patent Office: 398 Days
• Field of Search: 702/181, 702182-185, 702/188, 714/25, 714/47, 703/1, 703/22
• US Class Current: 702/181
• CPC Class Codes: G06F 11/0715 in a system implementing multitasking multitasking per se G06F9/46
• CPC Class Codes: G06F 11/0751 Error or fault detection not based on redundancy power supply failures G06F1/30; network fault management H04L41/06

Abstract

A time series is analyzed by multiple functions simultaneously to identify an anomaly for a data point in the series. Data point values are predicted by the multiple functions. An anomaly occurs when an actual data point in the series differs significantly from the data point'"'"'s predicted value as generated by the functions. If enough statistical models detect an anomaly has occurred for a data point, an anomaly event is generated. The set of functions can include different types of functions, the same function type configured with different constants, or a combination of these.

Claims

1. A method for detecting an anomaly, comprising:

receiving a first set of data of a time series;

accessing two or more functions fitted to the time series;

determining whether the first set of data differs from a threshold associated with a predicted value for each function;

calculating a first count as the number of thresholds exceeded by the first set of data and

determining whether to generate an anomaly event based on the value of the first count.

2. The method of claim 1, wherein the first set of data is a time series of application performance data.

3. The method of claim 1, wherein the threshold is specific to each function, said step of determining whether the first set of data exceeds a threshold includes:

accessing a threshold associated with a predicted data point value for each of the two or more functions; and

comparing each threshold to a data point in the first set of data.

4. The method of claim 1, wherein the threshold is a percentage of the predicted value.

5. The method of claim 1, wherein the threshold changes as the predicted value of the time series changes.

6. The method of claim 1, wherein said step of determining includes:

determining whether the count is equal or greater than half the total number of two or more functions.

7. The method of claim 1, determining whether the count is at least two.

8. The method of claim 1, wherein said step of determining includes:

weighting a vote associated with at least one of the two or more functions; and

casting a vote for each function for which the first set of data differs by more than the threshold from the predicted value for the function.

9. One or more processor readable storage devices having processor readable code embodied on said processor readable storage devices, said processor readable code for programming one or more processors to perform a method comprising:

receiving a series of data points;

predicting an expected data point for the series of data points using each of two or more functions;

comparing a data point of the series of data points to the two or more expected data points; and

determining whether to generate an event based on the two or more comparisons.

10. The one or more processors of claim 9, wherein the series of data points is a series of application runtime data.

11. The one or more processors of claim 9, wherein said step of predicting an expected value includes:

fitting the two or more functions to a first set of data in the series of data points; and

generating an expected data point value using each of two or more functions for a second set of data in the series of data points.

12. The one or more processors of claim 9, wherein said step of comparing a data point includes:

incrementing a count for each instance that the actual data point exceeds a threshold range associated with each predicted data point.

13. The one or more processors of claim 12, wherein said step of incrementing includes:

weighting an increment value associated with a first function of the two or more functions based on past comparison of prior data points and prior expected data point values generated by the first function.

14. The one or more processors of claim 9, wherein said step of determining whether to generate an event includes:

accessing a count value; and

determining whether the count value is more than half the value of the number of two or more functions.

15. One or more processor readable storage devices having processor readable code embodied on said processor readable storage devices, said processor readable code for programming one or more processors to perform a method comprising:

receiving a series of data points;

predicting an expected data point for the series of data points using each of two or more functions;

comparing a data point of the series of data points to the two or more expected data points; and

determining whether to generate an event based on the two or more comparisons, wherein said step of comparing a data point includes;

incrementing a count for each instance that the actual data point exceeds each predicted data point.

16. An apparatus for processing data, comprising:

a communication interface;

a storage device; and

one or more processors in communication with said storage device and said communication interface, said one or more processors perform a method comprising

receive a first set of data,

fit two or more functions to the first set of data,

receive a second set of data,

compare a point in the second set of data to a predicted point generated from each fitted function,

determine whether a difference for each comparison exceeds a threshold, and

generate an anomaly event based on the number of comparisons that exceed a corresponding threshold.

17. The apparatus of claim 16, wherein the one or more processors receive the first set of data and second set of data from an application.

18. The apparatus of claim 16, wherein the one or more processors determine whether a difference for each comparison exceeds a threshold which is specific to each function.

19. The apparatus of claim 16, wherein each threshold is a percentage of the predicted value.

20. The apparatus of claim 16, wherein the threshold changes as the predicted value of the time series changes.

21. The apparatus of claim 16, wherein one or more processors:

increment a count each comparison between a point in the second data set and a predicted point for which the second data set point exceeds a second threshold associated with the predicted point.

22. The apparatus of claim 21, wherein one or more processors determine whether the count is equal or greater than half the total number of two or more functions.

23. The apparatus of claim 16, wherein one or more processors determine whether the count is at least two.

24. A method for detecting an anomaly, comprising:

receiving a first set of data;

fitting a first portion of the first set of data to two or more functions;

determining whether a selected point in the first set of data differs from a predicted point generated using each of the two or more functions by more than a threshold corresponding to each function;

generating a count which represents differences between the selected point and a threshold corresponding with each predicted point; and

determining whether to generate an event based on the count.

25. The method of claim 24, wherein the data is application performance data.

26. The method of claim 24, wherein said step of fitting includes:

accessing the first portion of the first set of data;

fitting each of the two or more functions to the first portion of data, wherein said step of determining whether a selected point in the first set differs from a predicted point is performed using data from the first set of data which is not included in the first portion of data.

27. The method of claim 24, further comprising:

generating a threshold corresponding to each of the two or more functions in response to said step of fitting a first portion.

28. The method of claim 24, wherein said step of determining whether to generate an event includes:

accessing a count value; and

determining whether the count value is greater than a second threshold value.

29. The method of claim 24, further comprising:

generating an anomaly alert in response to the generated event.

30. A method for detecting an anomaly, comprising:

receiving a first set of data;

fitting a first portion of the first set of data to two or more functions;

determining whether a selected point in the first set of data differs from a predicted point generated using each of the two or more functions by more than a threshold corresponding to each function;

generating a count which represents differences between the selected point and a threshold corresponding with each predicted point; and

determining whether to generate an event based on the count, wherein said step of generating a count includes;

incrementing the count for each time that the selected data point exceeds the threshold for a predicted data point.

31. The method of claim 30, wherein said step of generating a count includes:

weighting the increment associated with a first function of the two or more functions based on the accuracy of prior predicted data points for the first function with respect to the first set of data.