NONPARAMETRIC METHOD FOR DETERMINATION OF ANOMALOUS EVENT STATES IN COMPLEX SYSTEMS EXHIBITING NON-STATIONARITY

• US 20080270071A1
• Filed: 04/30/2007
• Published: 10/30/2008
• Est. Priority Date: 04/30/2007
• Status: Active Grant

• Current Assignee: Vmware LLC (Broadcom, Inc.)
• Original Assignee: Integrien Corp. (Broadcom, Inc.)
• Inventors: Jeske, Daniel R., Marvasti, Mazda A.
• Granted Patent: US 7,620,523 B2
• Time in Patent Office: Days
• US Class Current: 702/179
• CPC Class Codes: G05B 23/0221 Preprocessing measurements, e.g. data collection rate adjustment; Standardization of measurements; Time series or signal analysis, e.g. frequency analysis or wavelets; Trustworthiness of measurements; Indexes therefor; Measurements using easily measured parameters to estimate parameters difficult to measure; Virtual sensor creation; De-noising; Sensor fusion; Unconventional preprocessing inherently present in specific fault detection methods like PCA-based methods
• CPC Class Codes: G05B 23/024 Quantitative history assessment, e.g. mathematical relationships between available data; Functions therefor; Principal component analysis [PCA]; Partial least square [PLS]; Statistical classifiers, e.g. Bayesian networks, linear regression or correlation analysis; Neural networks
• CPC Class Codes: G06F 11/3438 monitoring of user actions tracking the activity of the user H04L67/535
• CPC Class Codes: G06F 2218/12 Classification; Matching

Abstract

According to a feature of the present disclosure, a method is provided for the determination of anomalous events in complex systems, such as problems, inefficiencies, and failures, and a tool is provided for the detection of these events. Many complex systems are non-stationary or experience periodic fluctuations or spikes in values that are outside of normal ranges, but constitute normal behavior nevertheless. The method accounts for both non-stationarity, as well as fluctuations and spikes. Additional novel features include both a threshold setting initialization method and a regression method for the determination of the start points and end points of events.

Claims

1. A method comprising:

determining at least one threshold based on a set of historical metric data for at least one monitoring period;

performing a cumulative sum analysis on a set of incoming metric data in real time by calculating a cumulative sum value for each metric and comparing the cumulative sum value to the at least one threshold to detect anomalous events; and

initiating an alert state when an anomalous event is detected;

wherein each cumulative sum value is calculated by adding to the previous cumulative sum value the difference between the value of a metric and a value for normal behavior for a current timeslot within the monitoring period; and

wherein if the calculation of the cumulative sum value is negative, it is set to zero.

2. The method of claim 1, wherein the historical metric data is screened to remove abnormal metric data.

3. The method of claim 2, wherein the value for normal behavior is a function of a tunable parameter that determines whether a given metric is outside of a range of normal values for the timeslot in which the given metric is observed.

4. The method of claim 3, wherein at least one cumulative sum value is calculated by the function:

S_n=max{0,S<sub>n−

1</sub>+Y_n−

Q<sub>τ

n</sub>(α

)}

wherein n represents a timeslot, S_n is the cumulative sum value, Y_n is the incoming metric value, Q<sub>τ

n</sub>(α

) is a function defining an extreme value for normal behavior based on historical metric values for the same timeslot in which Y_n is observed and tunable parameter α

, and S_o=0.

5. The method of claim 3, wherein at least two cumulative sum values are calculated by the functions:

S_n⁺=max(0,S<sub>n−

1</sub>⁺+Y_n−

Q<sub>τ

n</sub>(α

))

S_n⁻

=max{0,S<sub>n−

1</sub>⁻

+Q<sub>τ

n</sub>(1−

α

)−

Y_n}

wherein n represents a timeslot;

S_n⁺, S_n⁻

are cumulative sum values;

Y_n is the incoming metric value;

Q<sub>τ

n</sub>(α

) is a function defining a maximum value for normal behavior based on historical metric values for the same timeslot in which Y_n is observed and tunable parameter α

;

Q<sub>τ

n</sub>(1−

α

) is a function defining a minimum lower value for normal behavior based on historical metric values for the same timeslot in which Y_n is observed and tunable parameter α

; and

S_n⁺=0, S_n⁻

=0.

6. The method of claim 4, further comprising performing an initialization procedure comprising:

collecting historical data for a metric for at least one monitoring period, each monitoring period having a plurality of timeslots and each timeslot observing metric data at least once;

screening the historical data to remove anomalous data;

aggregating historical data for each timeslot;

simulating m monitoring periods by;

randomly sampling the aggregated historical data for each timeslot to correspond to a timeslot in the monitoring period to generate a simulated data stream of data points;

calculating a cumulative sum value for each simulated incoming data point sampled;

determining max(S_n)_m, where n is an indicator of sequential position of each data point in the data stream;

determining {max(S_n)₁, max(S_n)₂, . . . , max(S_n)_m};

determining a threshold for a monitoring period, the threshold being computed as ƒ

({max(S_n)₁, max(S_n)₂, . . . , max(S_n)_m}).

7. The method of claim 6, further comprising reinitializing after the completion of each monitoring period.

8. The method of claim 7, further comprising:

storing an initialization data set after each initialization;

during the reinitialization process, removing the oldest monitoring period of initialization data from the initialization data set and adding the immediately previous monitoring period'"'"'s data to the initialization data set to form an updated initialization data set;

wherein the reinitialization process sues the updated initialization data set.

10. The method of claim 1, further comprising:

determining the end point of each anomalous event.

12. The method of claim 1, further comprising:

determining the start point of each anomalous event.

13. The method of claim 12, wherein the determination of the start point of each anomalous event is designated as the most recent cumulative sum value in the set of ν

cumulative sum values {S_n, S<sub>n−

1</sub>, . . . , S<sub>n−

ν

+1</sub>} having the first negative or flat regression slope;

wherein S_n is initially the first cumulative sum value in an anomalous event to exceed the threshold and regressions over ν

points are calculated until a negative or flat slope results, each calculation taking the regression for the next n−

1 set of cusum values.

9. The method of claim 54, further comprising performing an initialization procedure comprising:

collecting historical data for a metric for at least one monitoring period, each monitoring period having a plurality of timeslots and each timeslot observing metric data at least once;

screening the historical data to remove anomalous data;

aggregating historical data for each timeslot;

simulating m monitoring periods by;

randomly sampling the aggregated historical data for each timeslot to correspond to a timeslot in the monitoring period to generate a simulated data stream of data points;

calculating a cumulative sum value for each simulated incoming data point sampled;

determining max(S_n)_m, where n is an indicator of sequential position of each data point in the data stream;

determining {max(S_n)₁, max(S_n)₂, . . . , max(S_n)_m};

determining a threshold for a monitoring period, the threshold being computed as ƒ

({max(S_n)₁, max(S_n)₂, . . . , max(S_n)_m}).

11. The method of claim 11, wherein the determination of the end point of each anomalous event is designated as the largest cusum value in the set of ν

historical cusum values having negative or flat regression slope;

wherein regressions over ν

cusum values begins at the first cusum statistic to exceed the threshold and progresses for each cusum statistic thereafter until a negative or flat slope is calculated.

14. A method comprising:

collecting historical data for a metric for at least one monitoring period, each monitoring period having a plurality of timeslots and each timeslot observing metric data at least once;

screening the historical data to remove anomalous data;

aggregating historical data for each timeslot;

simulating m monitoring periods by;

randomly sampling the aggregated historical data for each timeslot to correspond to a timeslot in the monitoring period to generate a simulated data stream of data points;

calculating a cumulative sum value for each simulated incoming data point sampled;

determining max(S_n)_m, n is an indicator of sequential position of each data point in the data stream;

determining {(max(S_n)₁, max(S_n)₂, . . . , max(S_n)_m)};

determining a threshold for a monitoring period, the threshold being computed as ƒ

(max(S_n)₁, max(S_n)₂, . . . , max(S_n)_m).

15. The method of claim 14, wherein the aggregate monitoring period data for each timeslot is weighted.

16. The method of claim 15, wherein the more recently observed historical data is given greater weight than less recently observed historical data.

17. The method of claim 14, wherein the function is 0.99max(S_n)₁, max(S_n)₂, . . . , max(S_n)_m).

18. A machine-readable medium having program instructions stored thereon executable by a processing unit for performing the steps of:

determining at least one threshold based on a set of historical metric data for at least one monitoring period;

performing a cumulative sum analysis on a set of incoming metric data in real time by calculating a cumulative sum value for each metric and comparing the cumulative sum value to the at least one threshold to detect anomalous events; and

initiating an alert state when an anomalous event is detected;

wherein each cumulative sum value is calculated by adding to the previous cumulative sum value the difference between the value of a metric and a value for normal behavior for a current timeslot within the monitoring period; and

wherein if the calculation of the cumulative sum value is negative, it is set to zero.

19. The machine-readable medium of claim 18, wherein the historical metric data is screened to remove abnormal metric data.

20. The machine-readable medium of claim 18, wherein the value for normal behavior is a function of a tunable parameter that determines whether a given metric is outside of a range of normal values for the timeslot in which the given metric is observed.

21. The machine-readable medium of claim 20, wherein at least one cumulative sum value is calculated by the function:

S_n=max{0,S<sub>n−

1</sub>+Y_n−

Q<sub>τ

n</sub>(α

)}

wherein n represents a timeslot, S_n is the cumulative sum value, Y_n is the incoming metric value, Q<sub>τ

n</sub>(α

) is a function defining an extreme value for normal behavior based on historical metric values for the same timeslot in which Y_n is observed and tunable parameter α

, and S₀=0.

22. The machine-readable medium of claim 20, wherein at least two cumulative sum values are calculated by the functions:

S_n⁺=max(0,S<sub>n−

1</sub>⁺+Y_n−

Q<sub>τ

n</sub>(α

))

S_n⁻

=max{0,S<sub>n−

1</sub>⁻

+Q<sub>τ

n</sub>(1−

α

)−

Y_n}

wherein n represents a timeslot;

S_n⁺, S_n⁻

are cumulative sum values;

Y_n is the incoming metric value;

Q<sub>τ

n</sub>(α

) is a function defining a maximum value for normal behavior based on historical metric values for the same timeslot in which Y_n is observed and tunable parameter α

;

Q<sub>τ

n</sub>(1−

α

) is a function defining a minimum value for normal behavior based on historical metric values for the same timeslot in which Y_n is observed and tunable parameter α

; and

S₀⁺=0, S₀⁻

=0.

23. The machine-readable medium of claim 21, further comprising performing an initialization procedure comprising:

collecting historical data for a metric for at least one monitoring period, each monitoring period having a plurality of timeslots and each timeslot observing metric data at least once;

screening the historical data to remove anomalous data;

aggregating historical data for each timeslot;

simulating m monitoring periods by;

randomly sampling the aggregated historical data for each timeslot to correspond to a timeslot in the monitoring period to generate a simulated data stream of data points;

calculating a cumulative sum value for each simulated incoming data point sampled;

determining max(S_n)_m, where n is an indicator of sequential position of each data point in the data stream;

determining {max(S_n)₁, max(S_n)₂, . . . , max(S_n)_m};

determining a threshold for a monitoring period, the threshold being computed as ƒ

({max(S_n)₁, max(S_n)₂, . . . , max(S_n)_m}).

24. The machine-readable medium of claim 23, further comprising reinitializing after the completion of each monitoring period.

25. The method of claim 24, further comprising:

storing an initialization data set after each initialization;

during the reinitialization process, removing the oldest monitoring period of initialization data from the initialization data set and adding the immediately previous monitoring period'"'"'s data to the initialization data set to form an updated initialization data set;

wherein the reinitialization process uses the updated initialization data set.

26. The machine-readable medium of claim 22, further comprising performing an initialization procedure comprising:

collecting historical data for a metric for at least one monitoring period, each monitoring period having a plurality of timeslots and each timeslot observing metric data at least once;

screening the historical data to remove anomalous data;

aggregating historical data for each timeslot;

simulating m monitoring periods by;

randomly sampling the aggregated historical data for each timeslot to correspond to a timeslot in the monitoring period to generate a simulated data stream of data points;

calculating a cumulative sum value for each simulated incoming data point sampled;

determining max(S_n)_m, where n is an indicator of sequential position of each data point in the data stream;

determining {max(S_n)₁, max(S_n)₂, . . . , max(S_n)_m};

determining a threshold for a monitoring period, the threshold being computed as ƒ

({max(S_n)₁, max(S_n)₂, . . . , max(S_n)_m}).

27. The method of claim 26, further comprising:

determining the end point of each anomalous event.

28. The machine-readable medium of claim 27, wherein the determination of the end point of each anomalous event is designated as the largest cusum value in the set of ν

historical cusum values having negative or flat regression slope;

wherein regressions over ν

cusum values begins at the first cusum statistic to exceed the threshold and progresses for each cusum statistic thereafter until a negative or flat slope is calculated.

29. The machine-readable medium of claim 18, further comprising:

determining the start point of each anomalous event.

30. The machine-readable medium of claim 29, wherein the determination of the start point of each anomalous event is designated as the most recent cumulative sum value in the set of ν

cumulative sum values {S_n, S<sub>n−

1</sub>, . . . , S<sub>n−

ν

+1</sub>} having the first negative or flat regression slope;

wherein S_n is initially the first cumulative sum value in an anomalous event to exceed the threshold and regressions over ν

points are calculated until a negative or flat slope results, each calculation taking the regression for the next n−

1 set of cusum values.

31. The machine-readable medium having program instructions stored thereon executable by a processing unit for performing the steps of:

collecting historical data for a metric for at least one monitoring period, each monitoring period having a plurality of timeslots and each timeslot observing metric data at least once;

screening the historical data to remove anomalous data;

aggregating historical data for each timeslot;

simulating m monitoring periods by;

randomly sampling the aggregated historical data for each timeslot to correspond to a timeslot in the monitoring period to generate a simulated data stream of data points;

calculating a cumulative sum value for each simulated incoming data point sampled;

determining max(S_n)_m, n is an indicator of sequential position of each data point in the data stream;

determining {max(S_n)₁, max(S_n)₂, . . . , max(S_n)_m};

determining a threshold for a monitoring period, the threshold being computed as ƒ

({max(S_n)₁, max(S_n)₂, . . . , max(S_n)_m}).

32. The machine-readable medium of claim 31, wherein the aggregate monitoring period data for each timeslot is weighted.

33. The machine-readable medium of claim 32, wherein the more recently observed historical data is given greater weight than less recently observed historical data.

34. The machine-readable medium of claim 31, wherein the function is 0.99max(S_n)₁, max(S_n)₂, . . . , max(S_n)_m).