JP7768036B2 - Anomaly detection device and anomaly detection method - Google Patents

Description

This disclosure relates to an anomaly detection device and an anomaly detection method.

Many of the various phenomena that occur in nature and human society (e.g., communication traffic, stock prices, temperature, etc.) are represented by time series data. For this reason, methods for analyzing time series data have long been researched, one of which is operator-theoretic data analysis. Operator-theoretic data analysis applies a mathematical theory known as operator theory by expressing the temporal evolution of time series data using linear operators. In recent years, methods have been proposed that apply operator-theoretic data analysis to anomaly detection (e.g., Non-Patent Document 1).

Hashimoto, Y., Ishikawa, I., Ikeda, I., Matsuo, Y., and Kawahara, Y. Krylov Subspace Method for Nonlinear Dynamical Systems with Random Noise. Journal of Machine Learning Research, 21(172):1-29, 2020.

However, the method described in Non-Patent Document 1 above has the problem that because it calculates the degree of anomaly for each piece of data at each time, it is not necessarily able to detect anomalies in a time interval with a certain width (in other words, anomalies over a certain period of time). For example, while the method described in Non-Patent Document 1 above can detect anomalies when there is a sudden change in value at a certain time, it cannot necessarily detect anomalies where the value changes gradually.

This disclosure was made in consideration of the above points and provides technology that can detect interval-specific anomalies in time-series data.

An anomaly detection device according to one aspect of the present disclosure includes a linear operator estimator configured to use time series data generated from a predetermined dynamical system to create an approximation of a Perron-Frobenius operator corresponding to the dynamical system; an anomaly degree calculation unit configured to use at least the approximation of the Perron-Frobenius operator to calculate the degree of anomaly in a predetermined time interval of the time series data from which the dynamical system is generated; and an anomaly detection unit configured to use the degree of anomaly to detect the presence or absence of an anomaly in the time interval.

Technology is provided that can detect interval anomalies in time series data.

FIG. 10 is a diagram illustrating an example of a broken line function. FIG. 2 is a diagram illustrating an example of a hardware configuration of the anomaly detection device according to the present embodiment. FIG. 2 is a diagram illustrating an example of a functional configuration of the anomaly detection device according to the present embodiment. 10 is a flowchart illustrating an example of an abnormality detection process according to the present embodiment. FIG. 10 is a diagram illustrating an example of data to which an anomaly has been added. FIG. 10 is a diagram (part 1) showing an example of the abnormality degree. FIG. 10 is a diagram (part 2) showing an example of the abnormality degree.

One embodiment of the present invention is described below.

<Theoretical structure>
The theoretical configuration of this embodiment will be described below.

≪1. Settings≫
Consider a dynamical system as shown in the following equation (1) where X is the state space.

x _t+1 = h(x _t ) (1)
where h is a generally nonlinear mapping from X to X.

Let H be a reproducing kernel Hilbert space (RKHS) consisting of a positive definite kernel k on X: X × X → C (where C is the set of all complex numbers). Note that H is a Hilbert space consisting of complex-valued functions on X. For details on RKHS, see, for example, Chapter 3 of the above-mentioned non-patent document 1.

On H, we define the Perron-Frobenius operator K corresponding to the dynamical system shown in equation (1) as a linear operator that satisfies the following:

Kφ(x)=φ(h(x))
where φ is a feature map for k and is defined as φ(x)=k(·, x).

≪2. Estimation of the Perron-Frobenius operator≫
Assume that data (normal data) x ₀ , ..., x _T up to time T generated by the dynamical system shown in equation (1) are given. In this case, for a given natural number n, an orthonormal system q ₁ , ..., q _n ∈ H that minimizes the following equation (2) is found.

Here, n is given as a natural number equal to or less than T. For example, n is a natural number slightly smaller than T, such as n=[(3/4)T]. Note that <•,•> represents an inner product.

Let P be the projection from H onto the space spanned by q ₁ , . . . , q _n .

In this case, an approximation of the Perron-Frobenius operator K is constructed by PKP. Similarly, for any l=1, 2, ..., q (where q is a predetermined integer of 1 or more), an approximation of K ^l is constructed by PK ^l P.

≪3. Calculation of abnormality level≫
Let d be a given natural number. Consider calculating an anomaly in an interval with a time width of d. When capturing an anomaly in a long interval, d is set to a relatively large value such as 100. Conversely, when capturing an anomaly in a short interval, d is set to a relatively small value such as 10. Below, three methods, Methods 1 to 3, will be explained as methods for calculating the degree of anomaly.

・Method 1
Let τ be a given natural number, and normal data x _τ , ..., x _{τ+d from time τ to τ+d} are given. τ may be any natural number, but is set to, for example, τ=0.

The predicted value of x _τ at time τ is represented as x _τ '. First, w ₀ , ..., w _q-1 εC that approximately satisfy the following equation (3) are calculated.

Here, J _l =PK ^l P is an approximation of the Perron-Frobenius operator constructed in "2. Estimation of the Perron-Frobenius operator". Hereinafter, we will set φ(x _τ+d ′) = φ(x _τ+d ). However, φ(x _τ+d ′) may be constructed approximately, similar to the above equation (3).

The w ₀ , ..., w _q-1 ∈ C that approximately satisfies the above formula (3) can be calculated as follows. That is, first, the broken-line functions f and g are constructed as shown in Fig. 1 (note that Fig. 1 shows the case where t = τ + i + 1 as an example). Specifically, for i = 0, ..., d, the broken-line functions f and g shown in the following formula (4) are constructed.

Next, using these broken line functions f and g, the prediction error err(τ, w) from time τ to τ+d is defined as in the following equation (5).

Here, w = (w ₀ , ..., w _q-1 ). Then, w that minimizes this err(τ, w) is found using a gradient method or the like. This gives w that approximately satisfies the above equation (3). Hereinafter, this w will be represented as w ^* .

Next, for each time t (t>T, t>τ), predicted values (more precisely, values obtained by mapping the predicted values to the feature space) for times t to t+d are calculated using w ^* and the approximation ^PKlP of the Perron-Frobenius operator constructed in "2. Estimation of the Perron-Frobenius operator", and the degree of anomaly for an interval having a width of times t to t+d is calculated based on the error between these predicted values and the actual measured values. Specifically, the degree of anomaly for times t to t+d is defined as err(t, w ^* ) using the function defined in equation (5). Note that, for example, the difference between err(τ, w ^* ) and err(t, w ^* ), |err(τ, w ^* ) - err(t, w ^* )|, may be used as the degree of anomaly.

・Method 2
If the function f is constructed by replacing φ(x _τ+i ′) (i=0, ..., d−1) in equation (3) with J _i+1 φ(x _τ−1 ), the prediction error defined in equation (5) does not depend on w. Therefore, after making this replacement, the prediction error defined in equation (5) may be adopted as the degree of anomaly.

・Method 3
In Methods 1 and 2, the degree of abnormality at times later than time T is calculated using approximation ^PKlP of the Perron-Frobenius operator constructed in "2. Estimation of Perron-Frobenius operator". For this reason, when constructing ^PKlP , normal data _x0 , ..., _xT up to time T are required.

However, there may be cases where normal data is not available in advance. In such cases, the degree of anomaly from time t to t+d (t = 0, 1, ...) may be calculated as follows. First, using the data from time t to t+d, an approximate PKP of the Perron-Frobenius operator is constructed using a method similar to that described in "2. Estimating the Perron-Frobenius Operator." Then, the number of eigenvalues of magnitude 1 in this PKP is used as the degree of anomaly from time t to t+d. In this case, for example, when the degree of anomaly from time t to t+d has changed compared to the previous time (in other words, when it has changed compared to the degree of anomaly from time t-1 to t+d-1), it can be detected that an anomaly has occurred in the period from time t to t+d.

<Hardware configuration of the abnormality detection device 10>
An example of the hardware configuration of the anomaly detection device 10 according to this embodiment is shown in Fig. 2. As shown in Fig. 2, the anomaly detection device 10 according to this embodiment includes an input device 101, a display device 102, an external I/F 103, a communication I/F 104, a random access memory (RAM) 105, a read only memory (ROM) 106, an auxiliary storage device 107, and a processor 108. Each of these pieces of hardware is connected to each other via a bus 109 so as to be able to communicate with each other.

The input device 101 is, for example, a keyboard, mouse, touch panel, physical button, etc. The display device 102 is, for example, a display, display panel, etc. Note that the anomaly detection device 10 does not necessarily have to have at least one of the input device 101 and the display device 102, for example.

The external I/F 103 is an interface with external devices such as a recording medium 103a. The anomaly detection device 10 can read from and write to the recording medium 103a via the external I/F 103. Examples of recording media 103a include flexible disks, CDs (Compact Discs), DVDs (Digital Versatile Disks), SD memory cards (Secure Digital memory cards), and USB (Universal Serial Bus) memory cards.

The communication I/F 104 is an interface for connecting the anomaly detection device 10 to a communication network. The RAM 105 is a volatile semiconductor memory (storage device) that temporarily stores programs and data. The ROM 106 is a non-volatile semiconductor memory (storage device) that can store programs and data even when the power is turned off. The auxiliary storage device 107 is a storage device (storage device) such as an HDD (Hard Disk Drive), SSD (Solid State Drive), or flash memory. The processor 108 is an arithmetic device such as a CPU (Central Processing Unit).

The anomaly detection device 10 according to this embodiment has the hardware configuration shown in FIG. 2, and is therefore capable of performing the anomaly detection process described below. Note that the hardware configuration shown in FIG. 2 is merely an example, and the hardware configuration of the anomaly detection device 10 is not limited to this. For example, the anomaly detection device 10 may have multiple auxiliary storage devices 107 or multiple processors 108, or may have various other hardware components in addition to the hardware shown in the figure.

<Functional configuration of the abnormality detection device 10>
An example of the functional configuration of the anomaly detection device 10 according to this embodiment is shown in Fig. 3. As shown in Fig. 3, the anomaly detection device 10 according to this embodiment includes a linear operator estimator unit 201, an anomaly degree calculation unit 202, and an anomaly detection unit 203. These units are realized, for example, by a process in which one or more programs installed in the anomaly detection device 10 are executed by the processor 108. The anomaly detection device 10 according to this embodiment also includes a storage unit 204. The storage unit 204 is realized, for example, by the auxiliary storage device 107.

The linear operator estimation unit 201 constructs an approximation of the Perron-Frobenius operator using the method described in "2. Estimation of the Perron-Frobenius operator."

The anomaly level calculation unit 202 calculates the anomaly level using one of methods 1 to 3 described in "3. Calculation of anomaly levels."

The anomaly detection unit 203 detects the occurrence of an anomaly using the anomaly degree calculated by the anomaly degree calculation unit 202.

The memory unit 204 stores various data (e.g., given normal data and parameters (d, n, etc.), approximations of the Perron-Frobenius operator, etc.).

<Abnormality detection processing>
The anomaly detection process according to this embodiment will be described below with reference to Fig. 4. As an example, the following describes a case where the degree of anomaly is calculated using Method 1 described in "3. Calculation of the degree of anomaly." In this case, steps S101 to S102 in Fig. 4 are executed in advance, while steps S103 to S105 are repeatedly executed for each time t.

The linear operator estimation unit 201 constructs an approximation PK ^l P of the Perron-Frobenius operator by the method described in "2. Estimation of the Perron-Frobenius operator" (step S101).

Next, the abnormality degree calculation unit 202 calculates w ^* by the method described in "3. Calculation of abnormality degree" (step S102).

The anomaly degree calculation unit 202 calculates predicted values (more precisely, values obtained by mapping the predicted values to the feature space) for times t to t+d using w ^* calculated in step S102 above and the approximation ^PKlP of the Perron-Frobenius operator calculated in step S101 above (step S103). These predicted values can be calculated using equation (3). That is, in equation (3), φ( _x't ), ..., φ(x't _+d ) can be calculated by setting τ=t and w=w ^* .

The anomaly degree calculation unit 202 calculates the anomaly degree err(t, w*) using the above formulas (4) and (5) with the actual measurement values (more precisely, values obtained by mapping the actual measurement values to the feature space) at times t to t+d as φ(x _t ), ..., φ(x _t+d ⁾ (step S104). Note that |err(τ, w ^* ) - err(t, w ^* )| may also be calculated as the anomaly degree.

Then, the anomaly detection unit 203 detects the occurrence of an anomaly using the degree of anomaly calculated in step S104 above (step S105). For example, the anomaly detection unit 203 may detect an anomaly if the degree of anomaly is greater than a predetermined threshold, and may not detect an anomaly if the degree of anomaly is not greater than a predetermined threshold.

When calculating the degree of abnormality using Method 2 described in "3. Calculation of the degree of abnormality," in step S102, φ(x _τ+i ′) (i=0, ..., d−1) in equation (4) is replaced with J _i+1 φ(x _τ−1 ) to construct the function f, and then w ^* is calculated.

When calculating the degree of anomaly using Method 3 described in "3. Calculation of the degree of anomaly," steps S101 and S102 are not executed, and steps S104 and S105 are simply executed repeatedly for each time t. However, in step S104, the linear operator estimation unit 201 first constructs an approximated PKP of the Perron-Frobenius operator using data from times t to t+d, and then the anomaly calculation unit 202 calculates the number of eigenvalues of magnitude 1 in the approximated PKP as the degree of anomaly. In step S105, the anomaly detection unit 203 detects that an anomaly has occurred in the interval from time t to t+d when the degree of anomaly has changed compared to the previous time.

<Evaluation>
The following describes the evaluation of the anomaly detection device 10 according to this embodiment.

As an example, we artificially added a time-variable anomaly to data on communication traffic volume published by the TOTEM Project (http://totem.run.montefiore.ulg.ac.be/datatools.html), and then calculated the anomaly level using Method 2 described in "3. Calculating the Anomaly Level." The time interval in which the anomaly was added was from 1500 to 1600. Figure 5 shows the data with the anomaly added.

Let _yt be the data at time t. A 100-dimensional vector [ _yt , ..., _yt+99 ] is used as _xt in equation (1). This allows the relationship between _yt , ..., _yt+99 and _yt+1 , ..., _yt+100 to be expressed by equation (1).

At this time, an approximation PK ^l P of the Perron-Frobenius operator was constructed using data from time 0 to 1300 by the method explained in "2. Estimation of the Perron-Frobenius operator." Then, the degree of anomaly was calculated by Method 2 explained in "3. Calculation of the degree of anomaly" for two cases, when d = 13 and when d = 103.

Figure 6 shows the calculation results for the degree of anomaly when d = 13, and Figure 7 shows the calculation results for the degree of anomaly when d = 103. As shown in Figures 6 and 7, it can be seen that the degree of anomaly is high in both the sections where an artificial anomaly was added (times 1500 to 1600).

In both Figures 6 and 7, the degree of anomaly is also high around time 2000. This is because the value of the original data increases suddenly around time 2000, resulting in a localized anomaly.

When d = 103, the degree of anomaly around time 2000 is smaller than the degree of anomaly between times 1500 and 1600. This is because the larger the value of d, the smaller the impact of local anomalies and the more importance is placed on global anomalies.

As described above, the anomaly detection device 10 according to this embodiment can detect interval anomalies in time-series data (i.e., non-local, global anomalies) with high accuracy. The anomaly detection device 10 according to this embodiment can be applied to various devices or systems that use time-series data to detect spatial anomalies over a time span. One example of such a device or system is a device or system that detects communication anomalies from communication traffic.

The present invention is not limited to the specifically disclosed embodiments above, and various modifications, alterations, and combinations with known technologies are possible without departing from the scope of the claims.

10 Abnormality detection device 101 Input device 102 Display device 103 External I/F
103a Recording medium 104 Communication I/F
105 RAM
106 ROM
107 Auxiliary storage device 108 Processor 109 Bus 201 Linear operator estimation unit 202 Anomaly degree calculation unit 203 Anomaly detection unit 204 Storage unit

Claims (6)

a linear operator estimator configured to generate an approximation of a Perron-Frobenius operator corresponding to a predetermined dynamical system using time series data generated from the dynamical system;
an anomaly degree calculation unit configured to calculate an anomaly degree in a predetermined time interval of time-series data from which the dynamical system is generated by using at least an approximation of the Perron-Frobenius operator;
an anomaly detection unit configured to detect whether an anomaly has occurred in the time interval using the anomaly degree;
and
When X is a state space, the dynamical system is expressed as x _t+1 =h(x _t ) by a mapping h:X →X,
The linear operator estimation unit
Using normal data x ₀ , ..., x _T up to time T generated from the dynamical system , a natural number n less than T, and a feature map φ(x) defined as φ(x) = k(·, x) where k is a positive definite kernel on X: X × X → C, an orthonormal system q 1 , ..., q n ∈ H (where H is a reproducing kernel Hilbert space configured by the _positive definite kernel k) that minimizes the sum of ||φ(x i ) - (q 1 〈φ(x i ), q 1 〉 ₊ ... + q n 〈φ(x i ₎ , _q n _〉 ) _{|| 2 from} i ₌ 1 ^to T is obtained,
a projection P from the reproducing kernel Hilbert space H onto a space spanned by the orthonormal systems q ₁ , ..., q _n to generate an approximation PK ^l P (where l=1, 2, ..., q (where q is a predetermined integer of 1 or more)) of the Perron-Frobenius operator K;
The abnormality degree calculation unit
Using normal data x _τ , ..., x _τ+d from time τ to τ+d generated from the dynamical system , calculate w = (w 0 , ..., w q-1 ) that approximately satisfies φ(x' _τ+i ) = w ₀ J ₁ (φ(x _τ+i )) + ... + w _{q-1 J q} ( _φ (x _τ+i-q )) (where x' _τ+i is the predicted value of x _τ+i , and J _l = PK ^l P) for i = ₀ , ..., d;
The anomaly detection device is configured to calculate the degree of anomaly for the time interval represented by time t to t+d (where t>T, t>τ) using the w and an approximation PK l P of the Perron ^- Frobenius operator K. a linear operator estimator configured to generate an approximation of a Perron-Frobenius operator corresponding to a predetermined dynamical system using time series data generated from the dynamical system;
an anomaly degree calculation unit configured to calculate an anomaly degree in a predetermined time interval of time-series data from which the dynamical system is generated by using at least an approximation of the Perron-Frobenius operator;
an anomaly detection unit configured to detect whether an anomaly has occurred in the time interval using the anomaly degree;
and
When X is the state space, the dynamical system is such that x _t+1 = h(x _t ) and
The linear operator estimation unit
The actual value x of the time series data in the time interval represented by time t to t+d ₀ , ..., x _T and a feature map φ(x) defined as φ(x) = k(·, x) where k is a positive definite kernel on X: X × X → C, ||φ(x _i )-(q ₁ 〈φ(x _i ), q ₁ 〉＋・・・＋q _n 〈φ(x _i ), q _n 〉) || ² The orthonormal system q that minimizes the sum from i = 1 to T ₁ , ..., q _n ∈H (where H is a reproducing kernel Hilbert space constructed by the positive definite kernel k),
From the reproducing kernel Hilbert space H to the orthonormal system q ₁ , ..., q _n is configured to generate an approximation PKP of the Perron-Frobenius operator K using a projection P onto the space spanned by
The abnormality degree calculation unit
The anomaly detection device is configured to calculate the number of eigenvalues of magnitude 1 of the PKP as the degree of anomaly in the time interval represented by time t to t+d. The abnormality degree calculation unit
calculating w by minimizing err _{(τ, w):=(||f(t)-g} (t)|| 2 with respect to t from t= _τ- 1 to t=τ+d) using functions f and g defined as f|[τ+i- _{1 ,τ+i]} (t)=(t-(τ+i-1))φ( _x'τ+i )+((τ+i)-t)φ( _x'τ+i-1 ) and g|[τ+i-1,τ+i](t)=(t-(τ+i-1))φ(xτ+i)+ ⁽ (τ+i)-t)φ(xτ+i-1), for i=0,...,d;
Using the w and the approximation PK ^l P of the Perron-Frobenius operator K, calculate φ(x′ _t+i )=w ₀ J ₁ (φ(x _t+i ))+...+w _q−1 J _q (φ(x _t+i−q )) for i=0,...,d;
2. The anomaly detection device according to claim 1, wherein the device is configured to calculate, as the degree of _anomaly , err(t, _w ) = (a value obtained by integrating ||f( _t ) - g( _t )|| ² from t - 1 to _{t + d} ) or |err(τ, w) - err(t, w)| using φ(x't), ..., _φ(x't+d ) and φ(xt), ..., φ(xt+d) relating to actual values xt, ..., xt+ d of the time series data in the time interval. The abnormality degree calculation unit
2. The anomaly detection device according to _{claim 1, wherein the device is configured to calculate, as the degree of anomaly} , err(τ):=(a value obtained by integrating ∥f(t)−g(t)∥ ₂ with respect to t from t= _{τ −1} to t=τ+d) using functions _f and g defined as f| _{[τ+i−1,τ+i]} (t)=(t−( _τ+i −1))Ji+1φ(xτ−1)+((τ+i)−t)Jiφ(xτ−1) and ^g |[τ _+i−1 ,τ+i](t)=(t−(τ+i−1))φ(xτ+i)+((τ+i)−t)φ(xτ+i− 1) . a linear operator estimation procedure for creating an approximation of a Perron-Frobenius operator corresponding to a given dynamical system using time series data generated from the dynamical system;
an anomaly calculation procedure for calculating an anomaly degree in a predetermined time interval of time series data from which the dynamical system is generated, using at least an approximation of the Perron-Frobenius operator;
an anomaly detection step of detecting whether or not an anomaly has occurred in the time interval using the anomaly degree;
The computer executes
When X is a state space, the dynamical system is expressed as x _t+1 =h(x _t ) by a mapping h:X →X,
The linear operator estimation procedure is
Using normal data x ₀ , ..., x _T up to time T generated from the dynamical system , a natural number n less than T, and a feature map φ(x) defined as φ(x) = k(·, x) where k is a positive definite kernel on X: X × X → C, an orthonormal system q 1 , ..., q n ∈ H (where H is a reproducing kernel Hilbert space configured by the _positive definite kernel k) that minimizes the sum of ||φ(x i ) - (q 1 〈φ(x i ), q 1 〉 ₊ ... + q n 〈φ(x i ₎ , _q n _〉 ) _{|| 2 from} i ₌ 1 ^to T is obtained,
, qn ₎ is used to generate an approximation PK ^l P (where l=1, 2, ..., q (where q is a predetermined integer of 1 or more)) of _the Perron-Frobenius operator K,
The abnormality degree calculation procedure includes:
Using normal data x _τ , ..., x _τ+d from time τ to τ+d generated from the dynamical system , calculate w = (w 0 , ..., w q-1 ) that approximately satisfies φ(x' _τ+i ) = w ₀ J ₁ (φ(x _τ+i )) + ... + w _{q-1 J q} ( _φ (x _τ+i-q )) (where x' _τ+i is the predicted value of x _τ+i , and J _l = PK ^l P) for i = ₀ , ..., d;
An anomaly detection method for calculating an anomaly degree for the time interval represented by time t to t+d (where t>T, t>τ) using the w and an approximation PK ^l P of the Perron-Frobenius operator K. a linear operator estimation procedure for creating an approximation of a Perron-Frobenius operator corresponding to a given dynamical system using time series data generated from the dynamical system;
an anomaly calculation procedure for calculating an anomaly degree in a predetermined time interval of time series data from which the dynamical system is generated, using at least an approximation of the Perron-Frobenius operator;
an anomaly detection step of detecting whether or not an anomaly has occurred in the time interval using the anomaly degree;
The computer executes
When X is the state space, the dynamical system is such that x _t+1 = h(x _t ) and
The linear operator estimation procedure is
The actual value x of the time series data in the time interval represented by time t to t+d ₀ , ..., x _T and a feature map φ(x) defined as φ(x) = k(·, x) where k is a positive definite kernel on X: X × X → C, ||φ(x _i )-(q ₁ 〈φ(x _i ), q ₁ 〉＋・・・＋q _n 〈φ(x _i ), q _n 〉) || ² The orthonormal system q that minimizes the sum from i = 1 to T ₁ , ..., q _n ∈H (where H is a reproducing kernel Hilbert space constructed by the positive definite kernel k),
From the reproducing kernel Hilbert space H to the orthonormal system q ₁ , ..., q _n Using the projection P onto the space spanned by, we create an approximation PKP of the Perron-Frobenius operator K,
The abnormality degree calculation procedure includes:
An anomaly detection method that calculates the number of eigenvalues of magnitude 1 of the PKP as the degree of anomaly in the time interval represented by time t to t+d.