Unsupervised anomaly detection for arbitrary time series

Patent metadata

Field	Value
Publication number	US-9652354-B2
Application number	US-201414218119-A
Country	US
Kind code	B2
Filing date	Mar 18, 2014
Priority date	Mar 18, 2014
Publication date	May 16, 2017
Grant date	May 16, 2017

Abstract

Examining time series sequences representing performance counters from executing programs can provide significant clues about potential malfunctions, busy periods in terms of traffic on networks, intensive processing cycles and so on. An unsupervised anomaly detector can detect anomalies for any time series. A combination of known techniques from statistics, signal processing and machine learning can be used to identify outliers on unsupervised data, and to capture anomalies like edge detection, spike detection, and pattern error anomalies. Boolean and probabilistic results concerning whether an anomaly was detected can be provided.

First claim

What is claimed:

1. A system comprising:
at least one processor:
a memory connected to the at least one process; and
at least one module comprising an anomaly detector that causes the at least one processor to identify anomalies comprising unexpected values in a time series of performance counters generated by a component by:
during execution of the component:
continuously monitoring data points from the performance counters;
determining a distribution of data points within the time series, wherein the time series changes dynamically during execution of the components;
performing pre-processing of the time series
detecting anomalies within the time series; and
reacting to a problem associated with the detected anomalies.

2. The system of claim 1 , further compromising providing information associated with the detected anomalies.

3. The system of claim 1 , wherein the data provided to the anomaly detector for training is only unlabeled data.

4. The system of claim 1 , wherein an anomaly detected by the anomaly detector is one of:
an out of range anomaly, a spike anomaly, an edge anomaly or a pattern error anomaly.

5. The system of claim 1 , further comprising:
a module that causes the at least one processor to:
detect an anomaly using a combination of techniques comprising a Z-test and a Gaussian distribution technique.

6. The system of claim 1 , further comprising:
a module that causes the at least one processor to:
dynamically adjust processing of the performance counters.

7. The system of claim 1 , further comprising:
a module that causes the at least one processor to:
detect anomalies within a time series hiving an evolving distribution.

8. A method comprising:
continuously monitoring, by a processor of a computing device, data points from performance counters generated by a component;
determining a distribution of the data points within a time series, wherein the time series changes dynamically during execution of the component;
providing the data points to a plurality of processing paths in parallel;
identifying anomalies within the time series in the absence of labeled data defining anomalous data and in the absence of labeled data defining normal data;
providing at least one of Boolean or probabilistic results concerning anomaly detection; and
reacting to a problem associated with the detected anomaly.

9. The method of claim 8 , wherein an anomaly of the identified anomalies is an edge anomaly.

10. The method of claim 8 , wherein an anomaly of the identified anomalies is an out of range anomaly.

11. The method of claim 8 , wherein an anomaly of the identified anomalies is a pattern error anomaly.

12. The method of claim 8 , wherein an anomaly of the identified anomalies is a spike anomaly.

13. The method of claim 8 , further comprising:
adapting to a time series having an evolving distribution.

14. A device, comprising:
at least one processor and a memory;
the at least one processor configured to identify anomalies comprising unexpected values in a time series of performance counters generated by a component, by performing actions during execution of the component that:
continuously monitor data points from the performance counters;
determine a distribution of data points within a time series sequence of performance counters, wherein the time series changes dynamically during execution of the component;
perform pre-processing comprising classification of the time series based on a statistic test of the time series;
detect anomalies within the time series; and
perform post-processing of the detected anomalies in order to react to a problem associated with at least one detected anomaly.

15. The device of claim 14 , wherein the at least one processor is further configured to:
detect an out of range anomaly by determining if an absolute value of a difference between a value of the current data point and an average of the time series of a corresponding performance counter is larger than a threshold value calculated during a training phase of anomaly detection.

16. The device of claim 14 , wherein the at least one processor is further configured to:
detect an edge anomaly by determining if an absolute value of a drop or rise is larger than a standard deviation of the time series multiplied by a threshold value calculated during a training phase of anomaly detection.

17. The device of claim 14 , wherein the at least one processor is further configured to:
detect a spike anomaly by determining if a second order derivative of an average value exceeds a threshold value calculated during a training phase of anomaly detection.

18. The device of claim 14 , wherein the at least one processor is further configured to:
detect a pattern error anomaly by modeling a sequence as an auto-regressive process with Gaussian noise during a warm up phase of anomaly detection;
predict an expected value for each upcoming data point in the time series; and
in response to determining that an absolute value of a difference between the expected value and an actual value is larger than a threshold defined during the warm up phase.

19. The device of claim 14 , wherein the at least one processor is further configured to:
control frequency of scoring based on buffering of time windows of variable range.

20. The device of claim 19 , wherein the at least one processor is further configured to:
score anomalies in the absence of labeled training data.

Assignees

• Microsoft Technology Licensing Llc

Inventors

• Filimonov Vitaly
• Periorellis Panagiotis
• Starostin Dmitry
• De Baynast Alexandre
• Akchurin Eldar
• Klimov Aleksandr
• Minka Thomas
• Spengler Alexander

Classifications

• G06N7/01

  Probabilistic graphical models, e.g. probabilistic networks · CPC title

• G06F11/3409 Primary

  for performance assessment · CPC title

• G06N20/00

  Machine learning · CPC title

• G06F11/3452 Primary

  Performance evaluation by statistical analysis · CPC title

• G06Q10/06

  Resources, workflows, human or project management; Enterprise or organisation planning; Enterprise or organisation modelling · CPC title