System and method for outlier detection via estimating clusters

• US 9,336,484 B1
• Filed: 09/13/2012
• Issued: 05/10/2016
• Est. Priority Date: 09/26/2011
• Status: Active Grant

• Current Assignee: USA As Represented By The Administrator Of The NASA
• Original Assignee: United States Of America As Represented By The Administrator Of The National Aeronautics And Space Administration
• Inventors: Iverson, David J.
• Primary Examiner(s): Breene, John
• Assistant Examiner(s): Dinh, Lynda
• Application Number:
  US13/615,202
• Time in Patent Office: 1,335 Days
• Field of Search: 702179-181
• US Class Current: 1/1
• CPC Class Codes: G06F 11/3003 Monitoring arrangements specially adapted to the computing system or computing system component being monitored
• CPC Class Codes: G06F 11/3006 where the computing system is distributed, e.g. networked systems, clusters, multiprocessor systems multiprogramming arrangements G06F9/46; allocation of resources G06F9/50
• CPC Class Codes: G06F 16/2462 Approximate or statistical queries
• CPC Class Codes: G06F 16/2465 Query processing support for facilitating data mining operations in structured databases
• CPC Class Codes: G06F 16/285 Clustering or classification
• CPC Class Codes: G06F 17/18 for evaluating statistical data , e.g. average values, frequency distributions, probability functions, regression analysis forecasting specially adapted for a specific administrative, business or logistic context G06Q10/04
• CPC Class Codes: G06F 18/2323 based on graph theory, e.g. minimum spanning trees [MST] or graph cuts
• CPC Class Codes: G06F 18/2433 Single-class perspective, e.g. one-against-all classification; Novelty detection; Outlier detection
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06N 3/08 Learning methods
• CPC Class Codes: G06N 5/00 Computing arrangements using knowledge-based models
• CPC Class Codes: G06N 5/02 Knowledge representation; Symbolic representation

Abstract

An efficient method and system for real-time or offline analysis of multivariate sensor data for use in anomaly detection, fault detection, and system health monitoring is provided. Models automatically derived from training data, typically nominal system data acquired from sensors in normally operating conditions or from detailed simulations, are used to identify unusual, out of family data samples (outliers) that indicate possible system failure or degradation. Outliers are determined through analyzing a degree of deviation of current system behavior from the models formed from the nominal system data. The deviation of current system behavior is presented as an easy to interpret numerical score along with a measure of the relative contribution of each system parameter to any off-nominal deviation. The techniques described herein may also be used to “clean” the training data.

Claims

1. A method of detecting anomalies in a behavior of a system implemented by a processor coupled to a memory, the memory having stored therein a set of instructions, that when executed by the processor, cause the processor to perform the method comprising:

(a) providing cluster modeling data for a plurality of clusters to an outlier detection module, the cluster modeling data identifying a number of training points in each of the plurality of clusters;

(b) receiving a query point at the outlier detection module, the query point comprising a plurality of parameters, the query point including training data provided by the plurality of sensors in real-time or near real-time, wherein the sensors provide sensor data, wherein the sensor data including at least one of pressure data, flow data, position data, acceleration data, velocity data and temperature data, wherein the sensor data utilized to form the query point;

(c) generating a group of closest clusters that is closest to the query point from the plurality of clusters, using the outlier detection module and determining if the group of the closest cluster is satisfied a threshold value, wherein the threshold value is a user-defined value;

(d) determining a weighted distance value between the query point and each cluster in the group of closest clusters using the outlier detection module, wherein the weighted distance value, WDV, between the query point and each cluster in the group of closest clusters is determined by;

WDV=nd

where n is the number of the training points in a cluster and d is the distance between the cluster and the query point;

(e) generating a summary distance value for the query point by combining the weighted distance values between the query point and each of the clusters using the outlier detection module; and

(f) determining if the query point is an outlier based upon the summary distance value using the outlier detection module.

2. The method of claim 1, further comprising determining a weighted average deviation of each of the plurality of parameters of the query point.

3. The method of claim 1, further comprising acquiring sensor readings from a plurality of sensors and forming values for the query point based upon the sensor readings.

4. The method of claim 3, further comprising forming values for the query point from sensor readings taken over time.

5. The method of claim 1, further comprising removing the query point from training data if the query point is an outlier.

6. The method of claim 1, further comprising normalizing the summary distance value and displaying the normalized summary distance value on a display.

7. The method of claim 1, wherein step (c) further comprises determining the group of closest clusters to the query point from the plurality of clusters such that a sum of a number of training points in the group of closest clusters equals or exceeds a predetermined value.

8. The method of claim 7, further comprising adding a cluster to the group of closest clusters whose distance from the query point is closer than a cluster in the group of closest clusters.

9. The method of claim 8, further comprising removing a cluster from the group of closest clusters whose distance is further from the query point than a cluster added to the group of closest clusters.

10. A system for detecting an anomaly in a behavior of a system, comprising:

a processor;

a memory coupled to the processor;

a plurality of input and output devices coupled to the processor, the plurality of devices including a plurality of sensors, and

a data storage coupled to the processor having cluster modeling data for a plurality of clusters stored therein, the cluster modeling data comprising a number of training points in each of the plurality of clusters;

the memory having stored therein a set of instructions, that when executed by the processor, cause the processor to perform the operations of;

receive a query point comprising a plurality of parameters including training data provided by the plurality of sensors in real-time or near real-time, wherein the sensors provide sensor data, wherein the sensor data including at least one of pressure data, flow data, position data, acceleration data, velocity data and temperature data, wherein the sensor data utilized to form the query point;

generate a group of closest clusters that is closest to the query point from the plurality of clusters,

determine if the group of the closest cluster is satisfied a threshold value;

wherein the threshold value is a user-defined value;

determine a weighted distance value between the query point and each of the clusters in the group of closest clusters,

wherein the weighted distance value, WDV, between the query point and each cluster in the group of closest clusters is determined by;

WDV=nd

where n is the number of the training points in a cluster and d is the distance between the cluster and the query point,

generating a summary distance value for the query point by combining the weighted distance values between the query point and each of the clusters using the outlier detection module, and

determine if the query point is an outlier based upon the summary distance value.

11. The system of claim 10, wherein the parameters of the query point are determined from the sensor data.

12. The system of claim 10, wherein the set of instructions, that when executed by the processor, are further operable to cause the processor to determine a weighted average deviation of each parameter of the query point.

13. The system of claim 10, wherein the set of instructions, that when executed by the processor, are further operable to cause the processor to normalize the summary distance value.

14. The system of claim 10, wherein the set of instructions, that when executed by the processor, are further operable to cause the processor to determine the group of closest clusters to the query point from the plurality of clusters such that a sum of the number of training points in the group of closest clusters equals or exceeds a predetermined value.

15. The system of claim 14, wherein the set of instructions, that when executed by the processor, are further operable to cause the processor to add a cluster to the group of closest clusters whose distance from the query point is closer than a cluster in the group of closest clusters.

16. The system of claim 15, wherein the set of instructions, that when executed by the processor, are further operable to cause the processor to replace a cluster in the group of closest clusters with a cluster whose distance from the query point is closer than the replaced cluster.

17. The system of claim 10, wherein the cluster modeling data for the plurality of clusters further comprises a distance value for each cluster from an indexing reference point.

18. The system of claim 17, wherein the set of instructions, that when executed by the processor, are further operable to cause the processor to determine a distance between the query point and the indexing reference point.