Method for anomaly detection in time series data based on spectral partitioning

Patent metadata

Field	Value
Publication number	US-9984334-B2
Application number	US-201414305618-A
Country	US
Kind code	B2
Filing date	Jun 16, 2014
Priority date	Jun 16, 2014
Publication date	May 29, 2018
Grant date	May 29, 2018

Abstract

Anomalies in real time series are detected by first determining a similarity matrix of pairwise similarities between pairs of normal time series data. A spectral clustering procedure is applied to the similarity matrix to partition variables representing dimensions of the time series data into mutually exclusive groups. A model of normal behavior is estimated for each group. Then, for the real time series data, an anomaly score is determined, using the model for each group, and the anomaly score is compared to a predetermined threshold to signal the anomaly.

First claim

We claim:

1. A method for detecting an anomaly in multivariate time series, comprising the steps of:
determining a similarity matrix of nonnegative pairwise similarities between pairs of normal univariate time series data each of which corresponds to a variable representing a dimension of the multivariate time series data;
applying a spectral clustering procedure to the similarity matrix in order to transform the similarity matrix into a block diagonal form, by partitioning the variables representing dimensions of the multivariate time series data into groups, wherein the groups are mutually exclusive;
estimating a probability density model of normal behavior for each group and defining a factored probability distribution model over an entire multivariate time series as a product of the probability densities over each group;
determining, for the multivariate time series data, an anomaly score using the probability density model of normal behavior for each group; and
comparing the anomaly score to a predetermined threshold to signal the anomaly, wherein the steps are performed in a processor.

2. The method of claim 1 , wherein the multivariate time series data are acquired by at least one sensor.

3. The method of claim 1 , wherein the spectral clustering uses an absolute value of a correlation coefficient as a similarity measure.

4. The method of claim 3 , wherein the correlation coefficient is linear, non-linear, an output of a radial-basis function network, or a support vector machine.

5. The method of claim 1 , wherein the spectral clustering maximizes a similarity between variables in the same group, and minimizes the similarity between elements in different groups.

6. The method of claim 1 , wherein the dimensions are of an M-dimensional Euclidean space.

7. The method of claim 1 , wherein the spectral clustering uses a normalized cuts procedure.

8. The method of claim 3 , wherein the similarity measure b ij between pairs of variables i and j is not necessarily symmetric, and the similarity matrix is A with a ij =(b ij +b ji )/2.

9. The method of claim 1 , wherein the model of each group is represented by a probability density function over the variables in the group.

10. The method of claim 9 , wherein the probability density function is a multivariate Gaussian distribution.

11. The method of claim 9 , wherein the probability density function is a non-parametric Parzen kernel density estimate.

12. The method of claim 1 , further comprising:
combining the anomaly scores to form a global anomaly score; and
comparing the global anomaly score to the predetermined threshold to signal the anomaly.

13. The method of claim 12 , wherein combining uses a general logical expression.

14. The method of claim 13 , wherein the logical expression is composed by means of logical operators AND and OR over logical conditions on the scores against group-specific thresholds.

15. The method of claim 1 , wherein the defining the factored probability distribution model over the entire multivariate time series as the product of the probability densities over each group includes representing the factor probability distribution model as

f
⁡

(
x
)

=

∏

p
=
1

p

⁢

⁢

f
p

⁡

(

x

(
p
)

)

,

wherein ƒ(x) is the probability density of the entire multivariate time series, and ƒ p (x (p) ) is the probability density over the group p.

16. The method of claim 1 , wherein the normal univariate time series data is data gathered from a sensor in communication with a machine, such that the data gathered during a time the machine is operating is as the machine's intended operation without anomalies or malfunctions.

17. A system for detecting an anomaly in multivariate time series, comprising:
at least one sensor in communication with a machine;
a memory to store and provide multivariate time series data generated by the at least one sensor in communication with the machine;
a processor in communication with the memory, is configured to:
determine a similarity matrix of nonnegative pairwise similarities between pairs of normal univariate time series data, each of which, corresponds to a variable representing a dimension of the multivariate time series data;
apply a spectral clustering procedure to the similarity matrix in order to transform the similarity matrix into a block diagonal form, by partitioning the variables representing dimensions of the multivariate time series data into groups, wherein the groups are mutually exclusive;
estimate a probability density model of normal behavior for each group and defining a factored probability distribution model over an entire multivariate time series as a product of the probability densities over each group;
determine, for the multivariate time series data, an anomaly score using the probability density model of normal behavior for each group;
compare the anomaly score to a predetermined threshold to signal the anomaly; and

store the signaled anomaly in the memory, wherein the signaled anomaly is a predictive estimate of an impending failure and assists in management of the machine.

18. A method for detecting an anomaly in multivariate time series, comprising the steps of:
determining a similarity matrix of nonnegative pairwise similarities between pairs of normal univariate time series data each of which corresponds to a variable representing a dimension of the multivariate time series data;
applying a spectral clustering procedure to the similarity matrix in order to transform the similarity matrix into a block diagonal form, by partitioning the variables representing dimensions of the multivariate time series data into groups, wherein the groups are mutually exclusive;
estimating a probability density model of normal behavior for each group and defining a factored probability distribution model over an entire multivariate time series as a product of the probability densities over each group;
determining, for the multivariate time series data, an anomaly score using the probability density model of normal behavior for each group;
combining the anomaly scores to form a global anomaly score;
comparing the global anomaly score to the predetermined threshold to signal the anomaly; and
outputting the signaled anomaly via an output interface in communication with the processor, wherein the steps are performed in a processor.

19. A method for detecting an anomaly in multivariate time series, compri

Assignees

• Mitsubishi Electric Res Laboratories Inc

Inventors

• Nikovski Daniel Nikolaev
• Kniazev Andrei
• Jones Michael J

Classifications

• G06N20/00 Primary

  Machine learning · CPC title

• G06F16/35

  Clustering; Classification · CPC title

• G06N99/005 Primary

  Physics · mapped topic

• G06F16/285 Primary

  Clustering or classification · CPC title