Computer Science ›› 2022, Vol. 49 ›› Issue (4): 144-151.doi: 10.11896/jsjkx.210600045

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

Three-way Drift Detection for State Transition Pattern on Multivariate Time Series

SHEN Shao-peng, MA Hong-jiang, ZHANG Zhi-heng, ZHOU Xiang-bing, ZHU Chun-man, WEN Zuo-cheng   

  1. School of Software Engineering, Chengdu University of Information Technology, Chengdu 610225, China
  • Received:2021-06-04 Revised:2021-09-24 Published:2022-04-01
  • About author:SHEN Shao-peng,born in 1993,postgraduate,is a member of China Computer Federation.His main research interests include reinforcement learning and anomaly detection.ZHANG Zhi-heng,born in 1990,Ph.D,is a member of China Computer Federation.His main research interests include time-series analysis,three-way decision and cost-sensitive learning.
  • Supported by:
    This work was supported by the National Natural Science Foundation of China(41604114,62006200),Ministry of Education Industry-University-Research Collaborative Education Project(201902298010),Sichuan Science and Technology Department Project(2020YFG0307),Chengdu Key R&D Support Plan(2021-YF05-00933-SN) and Sichuan Tourism University Scientific Research Project(2020SCTU14,19SCTUZY03).

Abstract: Unsupervised drift detection for multivariate time series (MTSs) is an important task in machine learning.However, this issue is challenging because the definitions of sequential patterns and their drifts are very flexible.Inspired by the idea of “Think in Threes”, this paper proposes a three-way drift detection method for state transition pattern with periodic wildcard gaps (3WDD-STAP), which is improved from the incremental mining algorithm of STAP.Without additional parameters, both frequent and drifted STAPs can be obtained simultaneously.Considering the support changes around the increments, we define three types of STAP drift.Type I drift indicates that STAPs change from frequent to infrequent.The incremental dataset needs to be rescanned.Type II drift indicates that STAPs change from infrequent to frequent.The original dataset needs to be rescanned.Type III drift indicates that STAPs retain frequent or infrequent, namely, these STAPs are normal.No dataset needs to be rescanned.Finally, experimental results on 2 real-world datasets show that:1)we obtain less drifted STAPs with less α and β, and vice versa;2)the two types of drifted STAPs obeys different distribution for various datasets;3)the obtained STAPs and their drifts have strong readability.

Key words: Anomaly detection, Incremental learning, Multivariate time series, Sequential pattern discovery, Think in Threes

CLC Number: 

  • TP391
[1] PAWLAK Z.Rough sets[J].International Journal of Computer &Information Sciences,1982,11(5):341-356.
[2] YAO Y Y.Three-way decisions and cognitive computing[J].Cognitive Computation,2016,8(4):543-554.
[3] YAO Y Y.The geometry of three-way decision[J/OL].Applied Intelligence,2021:1-28.
[4] LI J H,HUANG C C,QI J J,et al.Three-way cognitive concept learning via multi-granularity[J].Information Sciences,2017,378:244-263.
[5] MAOH,ZHAO S F,YANG L Z.Relationships between three-way concepts and classical concepts[J].Journal of Intelligent & Fuzzy Systems,2018,35(1):1063-1075.
[6] DENG X F,YAO Y Y.Decision-theoretic three-way approximations of fuzzy sets[J].Information Sciences,2014,279:702-715.
[7] YAO Y Y.Interval sets and three-way concept analysis in incomplete contexts[J].International Journal of Machine Lear-ning and Cybernetics,2017,8(1):3-20.
[8] FANG Y,MIN F.Cost-sensitive approximate attribute reduction with three-way decisions[J].International Journal of Approximate Reasoning,2019,104:148-165.
[9] MIN F,LIU F L,WEN L Y,et al.Tri-partition cost-sensitive active learning through kNN[J].Soft Computing,2019,23(5):1557-1572.
[10] YE X,LIU D.An interpretable sequential three-way recommendation based on collaborative topic regression[J/OL].Expert Systems with Applications,2021,168.
[11] ZHANG H R,MIN F,SHI B.Regression-based three-way re-commendation[J].Information Sciences,2017,378:444-461.
[12] MIN F,ZHANG S M,CIUCCI D,et al.Three-way active lear-ning through clustering selection[J].International Journal of Machine Learning and Cybernetics,2020,11(5):1033-1046.
[13] YUE X D,CHEN Y F,MIAO D Q,et al.Tri-partition neighborhood covering reduction for robust classification[J].Interna-tional Journal of Approximate Reasoning,2017,83:371-384.
[14] YU H,WANG X C,WANG G Y,et al.An active three-wayclustering method via low-rank matrices for multi-view data[J].Information Sciences,2020,507:823-839.
[15] MIN F,ZHANG Z H,ZHAI W J,et al.Frequent pattern disco-very with tri-partition alphabets[J].Information Sciences,2020,507:715-732.
[16] LI H X,ZHANG L B,HUANG B,et al.Sequential three-way decision and granulation for cost-sensitive face recognition[J].Knowledge-Based Systems,2016,91:241-251.
[17] REN R S,WEI L.The attribute reductions of three-way concept lattices[J].Knowledge-based systems,2016,99:92-102.
[18] ZHOU B,YAO Y Y,LUO J G.Cost-sensitive three-way email spam filtering[J].Journal of Intelligent Information Systems,2014,42(1):19-45.
[19] ZHUANG D E H,LI G C L,WONG A K C.Discovery of temporal associations in multivariate time series[J].IEEE Transactions on Knowledge and Data Engineering,2014,26(12):2969-2982.
[20] ZHANG Z H,MIN F.Frequent state transition patterns of multivariate time series[J].IEEE Access,2019,7:142934-142946.
[21] ZENG S C,ZHANG Z H,MIN F,et al.A three-way incremental updating method of state transition pattern[J].Journal of Zhengzhou University (Natural Science Edition),2020,52(1):16-23.
[22] MIN F,WU Y X,WU X D.The Apriori property of sequence pattern mining with wildcard gaps[J].International Journal of Functional Informatics and Personalized Medicine,2012,4(1):15-31.
[23] WU X D,ZHU X Q,HE Y,et al.PMBC:pattern mining from biological sequences with wildcard constraints[J].Computers in Biology and Medicine,2013,43(5):481-492.
[24] WU Y X,TONG Y,ZHU X Q,et al.NOSEP:Nonoverlapping sequence pattern mining with gap constraints[J].IEEE Tran-sactions on Cybernetics,2017,48(10):2809-2822.
[25] QIAN Y K,CHEN M,YE L X,et al.Network-wide anomaly detection method based on multiscale principal component analysis[J].Journal of Software,2012 (2):361-377.
[26] ZHOU D H,WEI M H,SI X S.A survey on anomaly detection,life prediction and maintenance decision for industrial processes[J].Acta Automatica Sinica,2013,39(6):711-722.
[27] MAO J L,JIN C Q,ZHANG Z G,et al.Anomaly detection for trajectory big data:advancements and framework[J].Journal of Software,2017,28(1):17-34.
[28] YOU C C,FENG X P,LIU L J,et al.An abnormal chest X-ray diagnostic report detection method based on topic model[J].Computer Engineering & Science,2020,42(4),741-748.
[29] MEI Y D,CHEN X,SUN Y Z,et al.A method for software system anomaly detection based on log in formation and CNN-text[J].Chinese Journal of Computers,2020,43(2):366-380.
[30] CHU G,HU X G,ZHANG Y H.Semantic-based Concept Drift Detection Algorithm for Text Data Stream[J].Computer Engineering,2018,44(2):24-30.
[31] ZHOU Y J,XU C,LI J G.Unsupervised anomaly detectionmethod based on improved CURE clustering algorithm[J].Journal on Communications,2010,31(7):4-23.
[32] LI N,GUO G D,CHEN L F.Concept drift detection method with limited amount of labeled data[J].Journal of Computer Applications,2012,32(8):2176-2185.
[33] CHENG G,QIAN D X,GUO J W,et al.A classification ap-proach based on divergence for network traffic in presence of concept drift[J].Journal of Computer Research and Development,2020,57(12):2673-2682.
[34] HU M,BAI X,XU W,et al.Review of anomaly detection algorithms for multidimensional time series[J].Journal of Computer Applications,2020,40(6) 1553-1564.
[35] LIAN Y F,DAI Y X,WANG H.Anomaly detection of user behaviors based on profile mining[J].Chinese Journal of Compu-ters,2002,25(3):325-330.
[36] TIAN X G,GAO L Z,SUN C L,et al.Anomaly detection ofprogram behaviors based on system calls and homogeneous markov chain models[J].Journal of Computer Research and Development,2007(9):1538-1544.
[37] XIAO H,HU Y F.Data mining based on segmented time warping distance in time series database[J].Journal of Computer Research and Development,2005,42(1):72-78.
[38] KEOGH E,LONARDI S,CHIU W.Finding Surprising Patterns in a Time Series Database In Linear Time and Space[C]//Proceedings of the 8th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York:ACM Press,2002:550-556.
[39] YU B J,XIA Z G,WANG J L.Anomaly detection algorithm based on gaussian process model[J].Computer Engineering and Design,2016,37(4):914-920.
[1] XU Tian-hui, GUO Qiang, ZHANG Cai-ming. Time Series Data Anomaly Detection Based on Total Variation Ratio Separation Distance [J]. Computer Science, 2022, 49(9): 101-110.
[2] 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.
[3] LIU Dong-mei, XU Yang, WU Ze-bin, LIU Qian, SONG Bin, WEI Zhi-hui. Incremental Object Detection Method Based on Border Distance Measurement [J]. Computer Science, 2022, 49(8): 136-142.
[4] 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.
[5] 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.
[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] QING Lai-yun, ZHANG Jian-gong, MIAO Jun. Temporal Modeling for Online Anomaly Detection [J]. Computer Science, 2021, 48(7): 206-212.
[9] GUO Yi-shan, LIU Man-dan. Anomaly Detection Based on Spatial-temporal Trajectory Data [J]. Computer Science, 2021, 48(6A): 213-219.
[10] XING Hong-jie, HAO ZhongHebei. Novelty Detection Method Based on Global and Local Discriminative Adversarial Autoencoder [J]. Computer Science, 2021, 48(6): 202-209.
[11] ZOU Cheng-ming, CHEN De. Unsupervised Anomaly Detection Method for High-dimensional Big Data Analysis [J]. Computer Science, 2021, 48(2): 121-127.
[12] 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.
[13] YANG Yue-lin, BI Zong-ze. Network Anomaly Detection Based on Deep Learning [J]. Computer Science, 2021, 48(11A): 540-546.
[14] 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.
[15] ZHONG Ying-yu, CHEN Song-can. High-order Multi-view Outlier Detection [J]. Computer Science, 2020, 47(9): 99-104.
Full text



No Suggested Reading articles found!