Systems and/or methods for dynamic anomaly detection in machine sensor data

• US 10,410,135 B2
• Filed: 05/21/2015
• Issued: 09/10/2019
• Est. Priority Date: 05/21/2015
• Status: Active Grant

• Current Assignee: Software AG USA Incorporated (Software AG)
• Original Assignee: Software AG USA Incorporated (Software AG)
• Inventors: Shumpert, James Michael
• Primary Examiner(s): Waldron, Scott A.
• Assistant Examiner(s): Lamardo, Viker A
• Application Number:
  US14/718,277
• Publication Number:
  US 20160342903A1
• Time in Patent Office: 1,573 Days
• Field of Search: 706 12
• CPC Class Codes: G06F 11/008 Reliability or availability analysis
• CPC Class Codes: G06F 11/0721 within a central processing unit [CPU]
• CPC Class Codes: G06F 11/079 Root cause analysis, i.e. error or fault diagnosis in a hardware test environment G06F11/22; in a software test environment G06F11/36
• CPC Class Codes: G06N 20/00 Machine learning

Abstract

Certain example embodiments relate to techniques for detecting anomalies in streaming data. More particularly, certain example embodiments use an approach that combines both unsupervised and supervised machine learning techniques to create a shared anomaly detection model in connection with a modified k-means clustering algorithm and advantageously also enables concept drift to be taken into account. The number of clusters k need not be known in advance, and it may vary over time. Models are continually trainable as a result of the dynamic reception of data over an unknown and potentially indefinite time period, and clusters can be built incrementally and in connection with an updatable distance threshold that indicates when a new cluster is to be created. Distance thresholds also are dynamic and adjustable over time.

Claims

1. A system for detecting anomalies in data dynamically received from a plurality of sensors that are associated with at least one of a plurality of machines, the system comprising:

a knowledgebase;

a model store; and

processing resources including at least one processor and a memory, the processing resources being configured, for each instance of data that is received from the plurality of sensors, to at least;

select a model from the model store based on which machine of the plurality of machines is associated with at least one corresponding sensor that provided the data;

classify, using the selected model, the respective instance of data as being one of a normal instance type and an anomalous instance type, wherein classification of the instance of data as an anomalous instance type indicates a potential operating issue with the machine that corresponds to the selected model;

in response to a classification of the respective instance being a normal instance type, use the data in the respective instance to train the selected model without a supervised designation of the respective instance;

in response to a classification of the respective instance being an anomalous instance type that is not new, determine from the knowledgebase an action to be taken and take the determined action; and

in response to a classification of the respective instance being an anomalous instance type that is new, seek confirmation from an authorized user as to whether the respective instance should be designated as a confirmed new anomalous instance type, and;

responsive to confirmation from the authorized user that the respective instance is a new anomalous instance type, update the knowledgebase with information about the respective instance and/or an action to be taken should the new anomalous instance type be detected again; and

train the selected model by using both the data in the respective instance and the corresponding designation from the authorized user;

wherein each model in the model store is implemented using a k-means cluster algorithm modified to be continually trainable as a result of the dynamic reception of data over a time period, wherein clusters within each model are built incrementally and in connection with an updatable distance threshold that indicates when a new cluster is to be created; and

wherein each said model has a respective total number of clusters that is dynamic and learned over time, wherein

a given data stream X from a given one of the machines includes instances x₁ . . . x_n with a number of variables d;

the modified k-means cluster algorithm uses a cluster initialization window p, a distance threshold t, an instance-weighting window w, a number of clusters k, clusters c₁ . . . c_n, sample covariance matrices S₁ . . . S_k for respective clusters, and μ

₁ . . . μ

_k as centroids of respective clusters; and

the modified k-means algorithm is programmed to;

initialize centroid μ

₁ of cluster c₁ as the mean of instances x₁ . . . x_p, and matrix S₁ as the covariance of instances x₁ . . . x_p, cluster c₁ and instances x₁ . . . x_p being predicted as normal instance types; and

for each instance i from x_p+1 . . . x_∞

in the given data stream X;

temporarily assign instance x_i to the cluster with the nearest centroid μ

₁ . . . μ

_k;

if the distance of x_i to that centroid is greater than the distance threshold t, obtain a cluster assignment for x_i from an or the authorized user; and

if the cluster assignment is for a confirmed new anomalous instance type, (a) create a new cluster c_j+1, and set centroid μ

_j+1=x_i and covariance matrix S_j+1 as the mean of existing covariance matrices S₁ . . . S_j, and (b) predict the class of c_j+1 for x_i; and

otherwise;

update the centroid μ

_j as the w window-weighted mean of the instances x_i that have been assigned to the cluster;

if the number of instances x_i that have been assigned to the cluster is greater than the cluster initialization window p, update the matrix S_j as the w window-weighted covariance of the instances x_i that have been assigned to the cluster; and

predict the class of c_j for x_i.

2. The system of claim 1, wherein the distance threshold is updatable based on the variability and distribution of the received data.

3. The system of claim 1, wherein the each said model has a respective total number of clusters that is not preset by an authorized user or programmer of the system.

4. The system of claim 1, wherein instances are assigned to clusters exactly one time.

5. The system of claim 1, wherein centroid calculations for clusters in each said model use a weighted mean of the assigned cluster instances that are received over time, at least after an initial training period.

6. The system of claim 5, wherein centroid distance calculations implement Mahalanobis distance measurement.

7. The system of claim 1, wherein the model store is configured to store one model for each machine from which data is receivable.

8. The system of claim 1, wherein the data from the sensors is received as events via a messaging buss.

9. The system of claim 8, further comprising a complex event processing (CEP) engine, the processing resources being further configured to at least receive and normalize the data that received by using the CEP engine.

10. The system of claim 1, wherein the model store is implemented in an in-memory data grid.

11. The system of claim 1, wherein classification of the respective instance being an anomalous instance type that is new is based on determination that the data of the instance is located more than a predetermined distance from the nearest cluster within the selected model.

12. The system of claim 11, further comprising a complex event processing (CEP) engine, the processing resources being further configured to at least perform the classification using the CEP engine.

13. The system of claim 1, wherein the modified k-means algorithm is further programmed to return clusters c₁ . . . c_k and centroids μ

₁ . . . μ

_k upon request.

14. The system of claim 1, wherein the modified k-means algorithm is further programmed such that:

while n≤

w, perform calculations such that;

15. The system of claim 1, wherein the instance-weighting window w is equal to the mean time between failures divided by the product of a constant and the sampling interval T.

16. A system for detecting anomalies in data dynamically received from a plurality of sensors, each said sensor being associated with one or more machines, the system comprising:

a model store, each said machine having an associated model stored therein; and

processing resources including at least one processor and a memory, the processing resources being configured to train each said model using a modified k-means cluster algorithm in which there are defined a cluster initialization window p, a distance threshold t, an instance-weighting window w, a number of clusters k, clusters c₁ . . . c_n, sample covariance matrices S₁ . . . S_k for respective clusters, and μ

₁ . . . μ

_k as centroids of respective clusters;

wherein each said cluster has an associated class, the class being one of an anomalous type class and a non-anomalous type class;

wherein, for each given data stream X from a given one of the machines that includes data instances x₁ . . . x_n with a number of variables d, the modified k-means algorithm is programmed to;

initialize centroid μ

₁ of cluster c₁ as the mean of instances x₁ . . . x_p, and matrix S₁ as the covariance of instances x₁ . . . x_p, cluster c₁ and instances x₁ . . . x_p being predicted as normal instance types; and

for each instance i from x_p+1 . . . x_∞

in the given data stream X;

temporarily assign instance x_i to the cluster with the nearest centroid μ

₁ . . . μ

_k;

if the distance of x_i to that centroid is greater than the distance threshold t, obtain a cluster assignment for x_i from an authorized user; and

if the cluster assignment is for a confirmed new anomalous instance type, (a) create a new cluster c_j+1, and set centroid μ

_j+1=x_i and covariance matrix S_j+1 as the mean of existing covariance matrices S₁ . . . S_j, and (b) predict the class of c_j+1 for x_i; and

otherwise;

update the centroid μ

_j as the w window-weighted mean of the instances x_i that have been assigned to the cluster;

if the number of instances x_i that have been assigned to the cluster is greater than the cluster initialization window p, update the matrix S_j as the w window-weighted covariance of the instances x_i that have been assigned to the cluster; and

predict the class of c_j for x_i.

17. The system of claim 16, wherein the modified k-means algorithm is further programmed to return clusters c₁ . . . c_k and centroids μ

₁ . . . μ

_k upon request.

18. The system of claim 16, wherein the modified k-means algorithm is further programmed such that:

while n≤

w, perform calculations such that;

19. The system of claim 16, wherein the instance-weighting window w is equal to the mean time between failures divided by the product of a constant and the sampling interval T.

20. The system of claim 19, wherein the constant is 600 and the cluster initialization window p is 30.

21. The system of claim 16, wherein the distance threshold t is updatable based on the variability and distribution of the received data.

22. The system of claim 21, wherein the distance threshold t is determined using a chi-square cumulative distribution commensurate with a defined false error rate and with a number of degrees of freedom equal to the number of variables in the given data stream X.

23. The system of claim 16, wherein the number of clusters k is adjustable over time.

24. The system of claim 16, wherein vector μ

and covariance matrix S are incrementally updated via Mahalanobis distance calculations.

25. The system of claim 16, wherein the processing resources are further configured to cooperate with a workflow management system to at least issue alerts in response to anomalous class types being predicted.

26. The system of claim 16, wherein plural normal instance type and plural anomalous instance types are definable.

27. A method of detecting anomalies in data dynamically received from a plurality of sensors that are associated with at least one of a plurality of machines, the method comprising:

receiving data from the plurality of sensors; and

for each instance of data received, using processing resources including at least one processor and a memory, to at least;

selecting a model from the model store based on which machine of the plurality of machines is associated with at least one corresponding sensor that provided the data;

classifying, using the selected model, the respective instance of data as being one of a normal instance type and an anomalous instance type, wherein classification of the instance of data as an anomalous instance type indicates a potential operating issue with the machine that corresponds to the selected model;

in response to a classification of the respective instance being a normal instance type, training the selected model by using unsupervised learning with the data;

in response to a classification of the respective instance being an anomalous instance type that is not new, determining an action to be taken and take the determined action; and

in response to a classification of the respective instance being an anomalous instance type that is new, seeking confirmation from an authorized user as to whether the respective instance should be designated as a confirmed new anomalous instance type, and;

responsive to confirmation from the authorized user that the respective instance is a new anomalous instance type, updating a knowledgebase with information about the respective instance and/or an action to be taken should the new anomalous instance type be detected again; and

training the selected model by using supervised learning with both the data in the respective instance and the corresponding designation from the authorized user;

wherein each model in the model store is implemented using a k-means cluster algorithm modified to be continually trainable as a result of the dynamic reception of data over a time period, wherein clusters within each model are built incrementally and in connection with an updatable distance threshold that indicates when a new cluster is to be created; and

wherein each said model has a respective total number of clusters that is dynamic and learned over time, wherein

a given data stream X from a given one of the machines includes instances x₁ . . . x_n with a number of variables d;

the modified k-means cluster algorithm uses a cluster initialization window p, a distance threshold t, an instance-weighting window w, a number of clusters k, clusters c₁ . . . c_n, sample covariance matrices S₁ . . . S_k for respective clusters, and μ

₁ . . . μ

_k as centroids of respective clusters; and

the modified k-means algorithm is programmed to;

initialize centroid μ

₁ of cluster c₁ as the mean of instances x₁ . . . x_p, and matrix S₁ as the covariance of instances x₁ . . . x_p, cluster c₁ and instances x₁ . . . x_p being predicted as normal instance types; and

for each instance i from x_p+1 . . . x_∞

in the given data stream X;

temporarily assign instance x_i to the cluster with the nearest centroid μ

₁ . . . μ

_k;

if the distance of x_i to that centroid is greater than the distance threshold t, obtain a cluster assignment for x_i from an authorized user; and

if the cluster assignment is for a confirmed new anomalous instance type, (a) create a new cluster c_j+1, and set centroid μ

_j+1=x_i and covariance matrix S_j+1 as the mean of existing covariance matrices S₁ . . . S_j, and (b) predict the class of c_j+1 for x_i; and

otherwise;

update the centroid μ

_j as the w window-weighted mean of the instances x_i that have been assigned to the cluster;

if the number of instances x_i that have been assigned to the cluster is greater than the cluster initialization window p, update the matrix S_j as the w window-weighted covariance of the instances x_i that have been assigned to the cluster; and

predict the class of c_j for x_i . . . .

28. The method of claim 27, further comprising updating the distance threshold based on the variability and distribution of the received data.

29. A method of detecting anomalies in data dynamically received from a plurality of sensors, each said sensor being associated with one or more machines, the method comprising:

maintaining a model store, each said machine having an associated model stored therein;

receiving data from the plurality of sensors; and

using processing resources including at least one processor and a memory to train each said model using a modified k-means cluster algorithm in which there are defined a cluster initialization window p, a distance threshold t, an instance-weighting window w, a number of clusters k, clusters c₁ . . . c_n, sample covariance matrices S₁ . . . S_k for respective clusters, and μ

₁ . . . μ

_k as centroids of respective clusters;

wherein each said cluster has an associated class, the class being one of an anomalous type class and a non-anomalous type class;

wherein, for each given data stream X from a given one of the machines that includes data instances x₁ . . . x_n with a number of variables d, the modified k-means algorithm is programmed to;

initialize centroid μ

₁ of cluster c₁ as the mean of instances x₁ . . . x_p, and matrix S₁ as the covariance of instances x₁ . . . x_p, cluster c₁ and instances x₁ . . . x_p being predicted as normal instance types; and

for each instance i from x_p+1 . . . x_∞

in the given data stream X;

temporarily assign instance x_i to the cluster with the nearest centroid μ

₁ . . . μ

_k;

if the distance of x_i to that centroid is greater than the distance threshold t, obtain a cluster assignment for x_i from an authorized user; and

if the cluster assignment is for a confirmed new anomalous instance type, (a) create a new cluster c_j+1, and set centroid μ

_j+1=x_i and covariance matrix S_j+1 as the mean of existing covariance matrices S₁ . . . S_j, and (b) predict the class of c_j+1 for x_i; and

otherwise;

update the centroid μ

_j as the w window-weighted mean of the instances x_i that have been assigned to the cluster;

if the number of instances x_i that have been assigned to the cluster is greater than the cluster initialization window p, update the matrix S_j as the w window-weighted covariance of the instances x_i that have been assigned to the cluster; and

predict the class of c_j for x_i.

30. The method of claim 29, wherein the modified k-means algorithm is further programmed to return clusters c₁ . . . c_k and centroids μ

₁ . . . μ

_k upon request.

31. The method of claim 29, wherein the modified k-means algorithm is further programmed such that:

while n≤

w, perform calculations such that;

32. The method of claim 29, wherein the instance-weighting window w is equal to the mean time between failures divided by the product of a constant and the sampling interval T.

33. The method of claim 29, wherein the distance threshold t is determined using a chi-square cumulative distribution commensurate with a defined false error rate and with a number of degrees of freedom equal to the number of variables in the given data stream X.

34. The method of claim 29, wherein the number of clusters k is adjustable over time.

35. The method of claim 29, wherein the processing resources are further configured to cooperate with a workflow management system to at least issue alerts in response to anomalous class types being predicted.

36. A non-transitory computer readable storage medium comprising instructions that, when executed in connection with processing resources including at least one processor and a memory, aid in detecting anomalies in data dynamically received from a plurality of sensors, each said sensor being associated with one or more machines, by at least:

maintaining a model store, each said machine having an associated model stored therein;

receiving data from the plurality of sensors; and

training each said model using a modified k-means cluster algorithm in which there are defined a cluster initialization window p, a distance threshold t, an instance-weighting window w, a number of clusters k, clusters c₁ . . . c_n, sample covariance matrices S₁ . . . S_k for respective clusters, and μ

₁ . . . μ

_k as centroids of respective clusters;

wherein each said cluster has an associated class, the class being one of an anomalous type class and a non-anomalous type class;

wherein, for each given data stream X from a given one of the machines that includes data instances x₁ . . . x_n with a number of variables d, the modified k-means algorithm is programmed to;

initialize centroid μ

₁ of cluster c₁ as the mean of instances x₁ . . . x_p, and matrix S₁ as the covariance of instances x₁ . . . x_p, cluster c₁ and instances x₁ . . . x_p being predicted as normal instance types; and

for each instance i from x_p+1 . . . x_∞

in the given data stream X;

temporarily assign instance x_i to the cluster with the nearest centroid μ

₁ . . . μ

_k;

if the distance of x_i to that centroid is greater than the distance threshold t, obtain a cluster assignment for x_i from an authorized user; and

if the cluster assignment is for a confirmed new anomalous instance type, (a) create a new cluster c_j+1, and set centroid μ

_j+1=x_i and covariance matrix S_j+1 as the mean of existing covariance matrices S₁ . . . S_j, and (b) predict the class of c_j+1 for x_i; and

otherwise;

update the centroid μ

_j as the w window-weighted mean of the instances x_i that have been assigned to the cluster;

if the number of instances x_i that have been assigned to the cluster is greater than the cluster initialization window p, update the matrix S_j as the w window-weighted covariance of the instances x_i that have been assigned to the cluster; and

predict the class of c_j for x_i.