Time series decomposition

Patent metadata

Field	Value
Publication number	US-11146445-B2
Application number	US-201916700931-A
Country	US
Kind code	B2
Filing date	Dec 2, 2019
Priority date	Dec 2, 2019
Publication date	Oct 12, 2021
Grant date	Oct 12, 2021

Abstract

Time series decomposition method and system are provided. Time series data including at least a seasonality component is received. A noise removal filter may be applied to the time series data. Furthermore, a trend component and the seasonality component are extracted from the time series data. A residual component may subsequently be extracted from the time series data based on the trend component and the seasonality component. Anomaly detection may then be performed on the trend component or the residual component to determine whether an anomaly exists in the time series data.

First claim

What is claimed is:

1. A method implemented by one or more computing devices, the method comprising:
receiving time series data comprising at least a seasonality component;
applying a noise removal filter to the time series data;
extracting a trend component from the time series data, wherein extracting the trend component from the time series data comprises:
modeling the trend component in terms of at least a circulant matrix; and
computing the modeled trend component using a predefined algorithm with a fast Fourier transform;

extracting the seasonality component from the time series data;
obtaining a residual component from the time series data based on the trend component and the seasonality component; and
performing an anomaly detection on the trend component or the residual component to determine whether an anomaly exists in the time series data.

2. The method of claim 1 , wherein the noise removal filter comprises a bilateral filter.

3. The method of claim 1 , wherein extracting the seasonality component from the time series data comprises extracting the seasonality component from the time series data through non-local seasonal filtering.

4. The method of claim 3 , wherein the non-local seasonal filtering comprises considering a predetermined number of previous seasonal neighborhoods with each neighborhood comprising a predetermined number of data points.

5. The method of claim 1 , wherein performing the anomaly detection on the trend component comprises applying one or more statistical tests on the trend component to determine whether an anomaly type exists in the trend component of the time series data, the anomaly type comprising a monotonic trend or a change of mean, and the one or more statistical tests comprising at least a t-test or a MK-test.

6. The method of claim 1 , wherein performing the anomaly detection on the residual component comprises applying one or more statistical tests on the residual component to determine whether an anomaly type exists in the residual component of the time series data, the anomaly type comprising at least a change of variance or a type of spikes and dips, and the one or more statistical tests comprising at least a F-test or an Extreme Studentized Deviate (ESD) test.

7. The method of claim 1 , wherein the seasonality component comprises a seasonality component having a pattern that repeats regularly with a particular time period, or a seasonality component having a pattern that shifts from one time period to another time period.

8. One or more computer readable media storing executable instructions that, when executed by one or more processors, cause the one or more processors to perform acts comprising:
receiving time series data comprising at least a seasonality component;
applying a noise removal filter to the time series data;
extracting a trend component from the time series data, wherein extracting the trend component from the time series data comprises:
modeling the trend component in terms of at least a circulant matrix; and
computing the modeled trend component using a predefined algorithm with a fast Fourier transform;

extracting the seasonality component from the time series data;
obtaining a residual component from the time series data based on the trend component and the seasonality component; and
performing an anomaly detection on the trend component or the residual component to determine whether an anomaly exists in the time series data.

9. The one or more computer readable media of claim 8 , wherein the noise removal filter comprises a bilateral filter.

10. The one or more computer readable media of claim 8 , wherein extracting the seasonality component from the time series data comprises extracting the seasonality component from the time series data through non-local seasonal filtering.

11. The one or more computer readable media of claim 10 , wherein the non-local seasonal filtering comprises considering a predetermined number of previous seasonal neighborhoods with each neighborhood comprising a predetermined number of data points.

12. The one or more computer readable media of claim 8 , wherein performing the anomaly detection on the trend component comprises applying one or more statistical tests on the trend component to determine whether an anomaly type exists in the trend component of the time series data, the anomaly type comprising a monotonic trend or a change of mean, and the one or more statistical tests comprising at least a t-test or a MK-test.

13. The one or more computer readable media of claim 8 , wherein performing the anomaly detection on the residual component comprises applying one or more statistical tests on the residual component to determine whether an anomaly type exists in the residual component of the time series data, the anomaly type comprising at least a change of variance or a type of spikes and dips, and the one or more statistical tests comprising at least a F-test or an Extreme Studentized Deviate (ESD) test.

14. The one or more computer readable media of claim 8 , wherein the seasonality component comprises a seasonality component having a pattern that repeats regularly with a particular time period, or a seasonality component having a pattern that shifts from one time period to another time period.

15. A system comprising:
one or more processors; and
memory storing executable instructions that, when executed by one or more processors, cause the one or more processors to perform acts comprising:
receiving time series data comprising at least a seasonality component;
applying a noise removal filter to the time series data;

extracting a trend component from the time series data, wherein extracting the trend component from the time series data comprises:
modeling the trend component in terms of at least a circulant matrix; and
computing the modeled trend component using a predefined algorithm with a fast Fourier transform;
extracting the seasonality component from the time series data;
obtaining a residual component from the time series data based on the trend component and the seasonality component; and
performing an anomaly detection on the trend component or the residual component to determine whether an anomaly exists in the time series data.

16. The system of claim 15 , wherein extracting the seasonality component from the time series data comprises extracting the seasonality component from the time series data through non-local seasonal filtering, wherein the non-local seasonal filtering comprises considering a predetermined number of previous seasonal neighborhoods with each neighborhood comprising a predetermined number of data points.

17. The system of claim 15 , wherein:
performing the anomaly detection on the trend component comprises applying one or more statistical tests on the trend component to determine whether an anomaly type exists in the trend component of the time series data, the anomaly type existing in the trend component comprising a monotonic trend or a change of mean, and the one or more statistical tests on the trend component comprising at least a t-test or a MK-test; and
performing the anomaly detection on the residual component comprises applying one or more statistical tests on the residual component to determine whether an anomaly type exists in the residual component of the time series data, the anomaly type existing in the residual component comprising at least a change of variance or a type of spikes and dips, and the one or more statistical tests on the residual component comprising at least a F-test or an Extreme St

Assignees

• Alibaba Group Holding Ltd

Inventors

• Qingsong Wen
• Gao Jingkun
• Song Xiaomin
• Sun Liang
• Xu Huan
• Yin Wotao
• Yao Tao

Classifications

• H04L41/147

  for predicting network behaviour · CPC title

• H04L41/064 Primary

  involving time analysis · CPC title

• H04L41/0604 Primary

  using filtering, e.g. reduction of information by using priority, element types, position or time · CPC title

• H04L41/0677

  Localisation of faults · CPC title

• G06F17/16 Primary

  Matrix or vector computation {, e.g. matrix-matrix or matrix-vector multiplication, matrix factorization (matrix transposition G06F7/78)} · CPC title