A new distributional treatment for time series anomaly detection

被引:0
作者
Kai Ming Ting
Zongyou Liu
Lei Gong
Hang Zhang
Ye Zhu
机构
[1] Nanjing University,National Key Laboratory for Novel Software Technology, School of Artificial Intelligence
[2] Deakin University,Centre for Cyber Resilience and Trust
来源
The VLDB Journal | 2024年 / 33卷
关键词
Time series; Anomaly detection; Isolation kernel; Distributional kernel;
D O I
暂无
中图分类号
学科分类号
摘要
Time series is traditionally treated with two main approaches, i.e., the time domain approach and the frequency domain approach. These approaches must rely on a sliding window so that time-shift versions of a sequence can be measured to be similar. Coupled with the use of a root point-to-point measure, existing methods often have quadratic time complexity. We offer the third R\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathbb {R}$$\end{document} domain approach. It begins with an insight that sequences in a stationary time series can be treated as sets of independent and identically distributed (iid) points generated from an unknown distribution in R\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathbb {R}$$\end{document}. This R\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathbb {R}$$\end{document} domain treatment enables two new possibilities: (a) The similarity between two sequences can be computed using a distributional measure such as Wasserstein distance (WD), kernel mean embedding or isolation distributional kernel (KI\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {K}_I$$\end{document}), and (b) these distributional measures become non-sliding-window-based. Together, they offer an alternative that has more effective similarity measurements and runs significantly faster than the point-to-point and sliding-window-based measures. Our empirical evaluation shows that KI\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {K}_I$$\end{document} is an effective and efficient distributional measure for time series; and KI\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {K}_I$$\end{document}-based detectors have better detection accuracy than existing detectors in two tasks: (i) anomalous sequence detection in a stationary time series and (ii) anomalous time series detection in a dataset of non-stationary time series. The insight makes underutilized “old things new again” which gives existing distributional measures and anomaly detectors a new life in time series anomaly detection that would otherwise be impossible.
引用
收藏
页码:753 / 780
页数:27
相关论文
共 90 条
  • [1] Bandaragoda TR(2018)Isolation-based anomaly detection using nearest-neighbor ensembles Comput. Intell. 34 968-998
  • [2] Ting KM(2019)Time series anomaly detection based on shapelet learning Comput. Stat. 34 945-976
  • [3] Albrecht D(2018)Unsupervised outlier detection for time series by entropy and dynamic time warping Knowl. Inf. Syst. 54 463-486
  • [4] Liu FT(2021)Unsupervised and scalable subsequence anomaly detection in large data series VLDB J. 30 909-931
  • [5] Zhu Y(2020)The Wasserstein–Fourier distance for stationary time series IEEE Trans. Signal Process. 69 709-721
  • [6] Wells JR(2003)Haar wavelets for efficient similarity search of time-series: with and without time warping IEEE Trans. Knowl. Data Eng. 15 686-705
  • [7] Beggel L(2006)Statistical comparisons of classifiers over multiple datasets J. Mach. Learn. Res. 7 1-30
  • [8] Kausler BX(1979)Distribution of the estimators for autoregressive time series with a unit root J. Am. Stat. Assoc. 74 427-431
  • [9] Schiegg M(1996)Efficient tests for an autoregressive unit root Econometrica 64 813-836
  • [10] Pfeiffer M(1994)Fast subsequence matching in time-series databases ACM SIGMOD Rec. 23 419-429