Computer Science ›› 2022, Vol. 49 ›› Issue (9): 101-110.doi: 10.11896/jsjkx.210600174

• Database & Big Data & Data Science • Previous Articles     Next Articles

Time Series Data Anomaly Detection Based on Total Variation Ratio Separation Distance

XU Tian-hui1, GUO Qiang1, ZHANG Cai-ming2   

  1. 1 School of Computer Science and Technology,Shandong University of Finance and Economics,Jinan 250014,China
    2 School of Software,Shandong University,Jinan 250014,China
  • Received:2021-06-22 Revised:2021-10-15 Online:2022-09-15 Published:2022-09-09
  • About author:XU Tian-hui,born in 1998,postgra-duate.Her main research interests include data analysis and anomaly detection.
    GUO Qiang,born in 1979,Ph.D,professor,is a member of China Computer Federation.His main research interests include computer vision and data mi-ning.
  • Supported by:
    National Natural Science Foundation of China(61873145,61802229),Natural Science Foundation of Shandong Province for Excellent Young Scholars(ZR2017JL029) and Science and Technology Innovation Program for Distinguished Young Scholars of Shandong Province Higher Education Institutions(2019KJN045).

Abstract: Anomaly detection for time series data is one of the important research problems in data analysis.Its main challenge is to detect if there are any anomalies and locate anomalies with low delay according to context.Most of existing anomaly detection methods capture anomalies using the probability density ratio to measure similarity between sequences.These methods need to use the cross-validation method to estimate the parameters of probability density ratio.However,cross-validation can increase the computational complexity,resulting in low computational efficiency and a high time delay.To address these issues,this paper proposes a detection method based on total variation ratio separation distance,in which total variation is adopted to extract sequence fluctuation features.Due to the fact that the total variation ratio is better than probability density ratio,the proposed method achieves higher computational efficiency and lower time delay.To reduce noise interference and further improve the detection accuracy,the proposed method is combined with the relative total variation.Experimental results show that the proposed method performs well in terms of detection accuracy,low delay and computational efficiency.

Key words: Anomaly detection, Probability density ratio, Time delay, Total variation, Relative total variation

CLC Number: 

  • TP391
[1]LIU S,YAMADA M,COLLIER N,et al.Change-point detection in time-series data by relative density-ratio estimation[J].Neural Networks,2013,43(1):72-83.
[2]SIFFER A,FOUQUE P A,TERMIER A,et al.Anomaly detection in streams with extreme value theory[C]//Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.USA:ACM,2017:1067-1075.
[3]ZHANG Q,HU Y P,JI C,et al.Edge computing application:real-time anomaly detection algorithm for sensing data[J].Journal of Computer Research and Development,2018,55(3):524-536.
[4]GUO Y S,LIU M D.Anomaly detection based on spatial-temporal trajectory data[J].Computer Science,2021,48(6A):213-219.
[5]CAI R C,XIE W H,HAO Z F,et al.Abnormal crowd detection based on multi-scale recurrent neural network[J].Journal of Software,2015,26(11):2884-2896.
[6]CHANDOLA V,BANERJEE A,KUMAR V.Anomaly detec-tion:a survey[J].ACM Computing Surveys,2009,41(3):1-58.
[7]HODGE V,AUSTIN J.A survey of outlier detection methodo-logies[J].Artificial Intelligence Review,2004,22(2):85-126.
[8]SU W X,ZHU Y L,LIU F,et al.Outliers and change-points detection algorithm for time series[J].Journal of Computer Research and Development,2014,51(4):781-788.
[9]STEINWART I,HUSH D,SCOVEL C.A classification framework for anomaly detection[J].Journal of Machine Learning Research,2005,6(1):211-232.
[10]ESKIN E,ARNOLD A,PRERAU M,et al.A geometric framework for unsupervised anomaly detection:Detecting intrusions in unlabeled data[M]//Applications of Data Mining in Compu-ter Security.Boston:Kluwer Academic Publishers,2002:78-99.
[11]HAN D M,GUO F Z,PAN J C,et al.Visual analysis for anomaly detection in time-Series:a survey[J].Journal of Computer Research and Development,2018,55(9):1843-1852.
[12]MOSKVINA V,ZHIGLJAVSKY A.An algorithm based on singular spectrum analysis for change-point detection[J].Communications in Statistics-Simulation and Computation,2003,32(2):319-352.
[13]CHEN J,OUYANG J Y,FENG A Q,et al.DoS anomaly detection based on isolation forest algorithm under edge computing framework[J].Computer Science,2020,47(2):287-293.
[14]KEOGH E,CHU S,HART D,et al.An online algorithm for segmenting time series [C]//Proceedings 2001 IEEE International Conference on Data Mining.USA:IEEE,2001:289-296.
[15]DING X O,YU S J,WANG M X,et al.Anomaly detection on industrial time series based on correlation analysis[J].Journal of Software,2020,31(3):726-747.
[16]FENG A R,WANG X R,WANG Q Y,et al.Database anomaly access detection based on principal component analysis and random tree[J].Computer Science,2020,47(9):94-98.
[17]BORGWARDT K M,GRETTON A,RASCH M J,et al.Integrating structured biological data by kernel maximum mean discrepancy[J].Bioinformatics,2006,22(14):e49-e57.
[18]SUGIYAMA M,SUZUKI T,NAKAJIMA S,et al.Directimportance estimation for covariate shift adaptation[J].Annals of the Institute of Statistical Mathematics,2008,60(4):699-746.
[19]JIANG H,ZHANG H F,LUO Y D,at al.Adaptive threshold network traffic anomaly detection based on KL distance[J].Computer Engineering,2019,45(4):108-113.
[20]KANAMORI T,HIDO S,SUGIYAMA M.A least-squares approach to direct importance estimation[J].The Journal of Machine Learning Research,2009,10(1):1391-1445.
[21]AMINIKHANGHAHI S,WANG T,COOK D J.Real-timechange point detection with application to smart home time series data[J].IEEE Transactions on Knowledge and Data Engineering,2018,31(5):1010-1023.
[22]GIBBS A L,SU F E.On choosing and bounding probability me-trics[J].International Statistical Review,2002,70(3):419-435.
[23]LI S,XIE Y,DAI H,et al.M-statistic for kernel change-point detection[C]//Proceedings of the 28th International Conference on Neural Information Processing Systems.USA:MIT Press,2015:3366-3374.
[24]KANAMORI T,SUZUKI T,SUGIYAMA M.Computationalcomplexity of kernel-based density-ratio estimation:A condition number analysis[J].Machine Learning,2013,90(3):431-460.
[25]XU L,YAN Q,XIA Y,et al.Structure extraction from texture via relative total variation[J].ACM Transactions on Graphics,2012,31(6):1-10.
[26]DING Z P,ZHANG S W,CHEN J Z,et al.Structure-preserving image smoothing with L0 gradient minimization couplinggra-dient fidelity term[J].Scientia Sinica Informationis,2014, 44(11):1370-1384.
[27]WANG Y Y,CHEN S C.A survey of evaluation and design for AUC based classifier[J].Pattern Recognition and Artificial Intelligence,2011,24(1):64-71.
[1] WANG Xin-tong, WANG Xuan, SUN Zhi-xin. Network Traffic Anomaly Detection Method Based on Multi-scale Memory Residual Network [J]. Computer Science, 2022, 49(8): 314-322.
[2] DU Hang-yuan, LI Duo, WANG Wen-jian. Method for Abnormal Users Detection Oriented to E-commerce Network [J]. Computer Science, 2022, 49(7): 170-178.
[3] SHEN Shao-peng, MA Hong-jiang, ZHANG Zhi-heng, ZHOU Xiang-bing, ZHU Chun-man, WEN Zuo-cheng. Three-way Drift Detection for State Transition Pattern on Multivariate Time Series [J]. Computer Science, 2022, 49(4): 144-151.
[4] WU Yu-kun, LI Wei, NI Min-ya, XU Zhi-cheng. Anomaly Detection Model Based on One-class Support Vector Machine Fused Deep Auto-encoder [J]. Computer Science, 2022, 49(3): 144-151.
[5] MA Li-wen, ZHOU Ying. BBR Unilateral Adaptation Algorithm for Improving Empty Window Phenomenon in STARTUP Phase [J]. Computer Science, 2022, 49(2): 321-328.
[6] LENG Jia-xu, TAN Ming-pi, HU Bo, GAO Xin-bo. Video Anomaly Detection Based on Implicit View Transformation [J]. Computer Science, 2022, 49(2): 142-148.
[7] ZHANG Ye, LI Zhi-hua, WANG Chang-jie. Kernel Density Estimation-based Lightweight IoT Anomaly Traffic Detection Method [J]. Computer Science, 2021, 48(9): 337-344.
[8] TAO Xing-peng, XU Hong-hui, ZHENG Jian-wei, CHEN Wan-jun. Hyperspectral Image Denoising Based on Nonconvex Low Rank Matrix Approximation and TotalVariation Regularization [J]. Computer Science, 2021, 48(8): 125-133.
[9] QING Lai-yun, ZHANG Jian-gong, MIAO Jun. Temporal Modeling for Online Anomaly Detection [J]. Computer Science, 2021, 48(7): 206-212.
[10] GUO Yi-shan, LIU Man-dan. Anomaly Detection Based on Spatial-temporal Trajectory Data [J]. Computer Science, 2021, 48(6A): 213-219.
[11] XING Hong-jie, HAO ZhongHebei. Novelty Detection Method Based on Global and Local Discriminative Adversarial Autoencoder [J]. Computer Science, 2021, 48(6): 202-209.
[12] ZOU Cheng-ming, CHEN De. Unsupervised Anomaly Detection Method for High-dimensional Big Data Analysis [J]. Computer Science, 2021, 48(2): 121-127.
[13] SHI Lin-shan, MA Chuang, YANG Yun, JIN Min. Anomaly Detection Algorithm Based on SSC-BP Neural Network [J]. Computer Science, 2021, 48(12): 357-363.
[14] YANG Yue-lin, BI Zong-ze. Network Anomaly Detection Based on Deep Learning [J]. Computer Science, 2021, 48(11A): 540-546.
[15] FENG An-ran, WANG Xu-ren, WANG Qiu-yun, XIONG Meng-bo. Database Anomaly Access Detection Based on Principal Component Analysis and Random Tree [J]. Computer Science, 2020, 47(9): 94-98.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!