Segment-based change detection method in multivariate data stream

• US 8,005,771 B2
• Filed: 09/24/2008
• Issued: 08/23/2011
• Est. Priority Date: 10/04/2007
• Status: Active Grant

• Current Assignee: Siemens Energy Global GmbH & Co. KG (Siemens AG)
• Original Assignee: Siemens Corp. (Siemens AG)
• Inventors: Sheikh, Abdul Saboor, Neubauer, Claus, Yuan, Chao, Chen, Terrence
• Primary Examiner(s): Holmes; Michael B
• Application Number:
  US12/236,587
• Publication Number:
  US 20090091443A1
• Time in Patent Office: 1,063 Days
• Field of Search: 706/12
• US Class Current: 706/12
• CPC Class Codes: G06F 18/2433 Single-class perspective, e.g. one-against-all classification; Novelty detection; Outlier detection
• CPC Class Codes: G06F 2218/12 Classification; Matching

Abstract

A method and framework are described for detecting changes in a multivariate data stream. A training set is formed by sampling time windows in a data stream containing data reflecting normal conditions. A histogram is created to summarize each window of data, and data within the histograms are clustered to form test distribution representatives to minimize the bulk of training data. Test data is then summarized using histograms representing time windows of data and data within the test histograms are clustered. The test histograms are compared to the training histograms using nearest neighbor techniques on the clustered data. Distances from the test histograms to the test distribution representatives are compared to a threshold to identify anomalies.

Claims

1. A method for detecting a change from a normal state in a multivariate data stream, the method comprising the steps of:

(A) receiving a multidimensional training data stream including a plurality of data points representing a normal state;

(B) sampling a plurality of m segment windows in the training data stream, each segment window representing a predefined time interval in the data stream;

(C) for each of said plurality of segment windows, summarizing a distribution of data points in the segment window by constructing a training histogram h;

(D) representing each training histogram h_i by a set of distribution representatives r_i using clustering;

(E) receiving a test data stream including a plurality of multidimensional data points;

(F) sampling data points in a plurality of segment windows in the test data stream, each segment window representing a predefined time interval in the data stream;

(G) for each segment window in the test data, summarizing a distribution of data points in the segment window by constructing a test histogram h′

;

(H) representing each test histogram h′

by a set of distribution representatives r′

using clustering;

(I) comparing test histograms h′

with training histograms h_i using the distribution representatives to find closest matches using a similarity measure S; and

(J) transmitting an indication that the multivariate data stream contains a change from the normal state for those segments having a similarity measure S indicating a similarity lower than a decision threshold σ

.

2. The method of claim 1, wherein each distribution representative r_i includes:

a centroid c_i of a cluster;

a weight w_i representing a number of points in the cluster; and

a vector v_i representing variation within each feature in the cluster.

3. The method of claim 2, wherein clustering is performed using a DBSCAN spatial clustering algorithm.

4. The method of claim 1, wherein the similarity measure S, for each comparison of a test histogram h′

and a training histogram h_i is determined by;

S(h′

,h_i)=min dist(h′

,h_i)∀

h_i.

5. The method of claim 4, wherein the similarity S(h′

, h_i) is calculated by using an earth mover'"'"'s distance metric between a set of bins A representing h′

, and a set of bins B representing h_i, the distance metric formulated as;

6. The method of claim 4, further comprising the steps of:

for each test histogram h′

wherein S indicates a similarity lower than a decision threshold σ

, computing a global average cost per data point; and

transmitting an indication that those data points having a cost exceeding the global average cost per data point are anomalies.

7. The method of claim 6, wherein the global average cost per data point is measured taking into account a centroid of the histogram and a span of the histogram.

8. The method of claim 6, wherein the global average cost per data point is measured by calculating a weighted-mean-variance distance.

9. The method of claim 1, further comprising the step of:

before performing clustering, adding time indices to data points within the segment window.

10. The method of claim 1, wherein the multivariate data stream comprises a data stream from a plurality of sensors monitoring a machine, and the indication that the multivariate data stream contains a change comprises a machine fault alarm.

15. The method of claim 4, wherein the similarity S(h′

, h_i) is calculated by using an earth mover'"'"'s distance metric between a set of bins A representing h′

, and a set of bins B representing h_i, the distance metric formulated as;

11. A computer-usable medium having computer readable instructions stored thereon for execution by a processor to perform a method for detecting a change from a normal state in a multivariate data stream, the method comprising the steps of:

(A) receiving a multidimensional training data stream including a plurality of data points representing a normal state;

(B) sampling a plurality of m segment windows in the training data stream, each segment window representing a predefined time interval in the data stream;

(C) for each of said plurality of segment windows, summarizing a distribution of data points in the segment window by constructing a training histogram h;

(D) representing each training histogram h_i by a set of distribution representatives r_i using clustering;

(E) receiving a test data stream including a plurality of multidimensional data points;

(F) sampling data points in a plurality of segment windows in the test data stream, each segment window representing a predefined time interval in the data stream;

(G) for each segment window in the test data, summarizing a distribution of data points in the segment window by constructing a test histogram h′

;

(H) representing each test histogram h′

by a set of distribution representatives r′

using clustering;

(I) comparing test histograms h′

with training histograms h_i using the distribution representatives to find closest matches using a similarity measure S; and

(J) transmitting an indication that the multivariate data stream contains a change from the normal state for those segments having a similarity measure S indicating a similarity lower than a decision threshold σ

.

12. The computer useable medium of claim 11, wherein each distribution representative r_i includes:

a centroid c_i of a cluster;

a weight w_i representing a number of points in the cluster; and

a vector v_i representing variation within each feature in the cluster.

13. The computer useable medium of claim 12, wherein clustering is performed using a DBSCAN spatial clustering algorithm.

14. The computer useable medium of claim 11, wherein the similarity measure S, for each comparison of a test histogram h′

and a training histogram h_i, is determined by;

S(h′

,h_i)=min dist(h′

,h_i)∀

h_i.

16. The computer useable medium of claim 14, wherein the method further comprises the steps of:

for each test histogram h′

wherein S indicates a similarity lower than a decision threshold σ

, computing a global average cost per data point; and

transmitting an indication that those data points having a cost exceeding the global average cost per data point are anomalies.

17. The computer useable medium of claim 16, wherein the global average cost per data point is measured taking into account a centroid of the histogram and a span of the histogram.

18. The computer useable medium of claim 16, wherein the global average cost per data point is measured by calculating a weighted-mean-variance distance.

19. The computer useable medium of claim 11, wherein the method further comprises the step of:

before performing clustering, adding time indices to data points within the segment window.

20. The computer useable medium of claim 11, wherein the multivariate data stream comprises a data stream from a plurality of sensors monitoring a machine, and the indication that the multivariate data stream contains a change comprises a machine fault alarm.