FAAD：一种无监督快速准确的数据流上多维序列异常检测方法

李彬; 王意洁; 杨东升; 李勇谋; 马行空

doi:10.1631/FITEE.1800038

Your Location：

Home >

Browse articles >

FAAD：一种无监督快速准确的数据流上多维序列异常检测方法

常规文章 | Updated：2022-05-19

- FAAD：一种无监督快速准确的数据流上多维序列异常检测方法
- FAAD: an unsupervised fast and accurate anomaly detection method for a multi-dimensional sequence over data stream
- 信息与电子工程前沿（英文） 2019年20卷第3期页码：388-404
- Affiliations：
  
  Science and Technology on Parallel and Distributed Processing Laboratory, College of Computer, National University of Defense Technology, Changsha 410073, China
  Block Chain Research Institute of LianLian Pay, Hangzhou 310000, China
- Author bio：
  
  [ "Bin LI, E-mail: libin16a@nudt.edu.cn" ]
  Yi-jie WANG, E-mail: wangyijie@nudt.edu.cn
- Funds：
  
  Project supported by the National Key R & D Program of China (No. 2016YFB1000101), the National Natural Science Foundation of China (Nos. 61379052 and 61502513), the Natural Science Foundation for Distinguished Young Scholars of Hunan Province, China (No. 14JJ1026), and the Specialized Research Fund for the Doctoral Program of Higher Education, China (No. 20124307110015)
- DOI：10.1631/FITEE.1800038
  中图分类号： TP391.4
- 收稿：2018-01-15，
  
  修回：2018-;3-14，
  
  纸质出版：2019-03
- Accepted：
Scan QR Code
李彬, 王意洁, 杨东升, 等. FAAD：一种无监督快速准确的数据流上多维序列异常检测方法[J]. 信息与电子工程前沿（英文）, 2019,20(3):388-404.

Bin LI, Yi-jie WANG, Dong-sheng YANG, et al. FAAD: an unsupervised fast and accurate anomaly detection method for a multi-dimensional sequence over data stream[J]. Frontiers of Information Technology & Electronic Engineering, 2019, 20(3): 388-404.
李彬, 王意洁, 杨东升, 等. FAAD：一种无监督快速准确的数据流上多维序列异常检测方法[J]. 信息与电子工程前沿（英文）, 2019,20(3):388-404. DOI： 10.1631/FITEE.1800038.

Bin LI, Yi-jie WANG, Dong-sheng YANG, et al. FAAD: an unsupervised fast and accurate anomaly detection method for a multi-dimensional sequence over data stream[J]. Frontiers of Information Technology & Electronic Engineering, 2019, 20(3): 388-404. DOI： 10.1631/FITEE.1800038.

摘要

最近，序列异常检测被广泛应用于许多领域。这些领域中的序列数据在数据流上通常是多维的。设计同时满足检测精度和速度的数据流上多维序列异常检测方法是一个挑战。因为：（1）序列数据和庞大状态空间的维度冗余导致序列建模能力较差；（2）异常检测无法适应数据流的高速性，尤其是概念漂移会降低检测率。一方面，大多数现有序列异常检测方法集中在单维序列。另一方面，多维序列研究主要集中在静态数据集而非数据流。为提高数据流上多维序列异常检测性能，提出一种新型无监督快速和准确异常检测（fastand accurate anomaly detection，FAAD）方法，该方法包括3种算法。首先，采用一种“信息计算和最小生成树聚类”（information calculation and minimum spanning tree cluster，IMC）方法减少冗余维度。其次，为加速模型构建确保数据流上序列的检测率，提出一种“基于索引概率后缀树的随机抽样和子序列划分”（random sampling and subsequence partitioning based on the index probabilistic suffix tree，RSIPST）方法。最后，“基于模型动态调整的异常缓冲”（anomaly buffer based on model dynamic adjustment，ABMDA）方法显著降低数据流中概念漂移的影响。在流平台Storm上实施FAAD检测多维日志审计数据。与现有异常检测方法相比，FAAD在检测精度和速度方面不受概念漂移影响，具有良好性能。

Abstract

Recently

sequence anomaly detection has been widely used in many fields. Sequence data in these fields are usually multi-dimensional over the data stream. It is a challenge to design an anomaly detection method for a multi-dimensional sequence over the data stream to satisfy the requirements of accuracy and high speed. It is because: (1) Redundant dimensions in sequence data and large state space lead to a poor ability for sequence modeling; (2) Anomaly detection cannot adapt to the high-speed nature of the data stream

especially when concept drift occurs

and it will reduce the detection rate. On one hand

most existing methods of sequence anomaly detection focus on the single-dimension sequence. On the other hand

some studies concerning multi-dimensional sequence concentrate mainly on the static database rather than the data stream. To improve the performance of anomaly detection for a multi-dimensional sequence over the data stream

we propose a novel unsupervised fast and accurate anomaly detection (FAAD) method which includes three algorithms. First

a method called "information calculation and minimum spanning tree cluster" is adopted to reduce redundant dimensions. Second

to speed up model construction and ensure the detection rate for the sequence over the data stream

we propose a method called "random sampling and subsequence partitioning based on the index probabilistic suffix tree." Last

the method called "anomaly buffer based on model dynamic adjustment" dramatically reduces the effects of concept drift in the data stream. FAAD is implemented on the streaming platform Storm to detect multi-dimensional log audit data. Compared with the existing anomaly detection methods

FAAD has a good performance in detection rate and speed without being affected by concept drift.

关键词

Keywords

references

H Bao , , , YJ Wang . . A C-SVM based anomaly detection method for multi-dimensional sequence over data stream . . Proc IEEE 22 nd Int Conf on Parallel and Distributed Systems , , 2016 . . p.948 - - 955 . . DOI: 10.1109/ICPADS.2016.0127 http://doi.org/10.1109/ICPADS.2016.0127 . .

GE Box , , , GM Jenkins , , , GC Reinsel , , , 等 . . Time Series Analysis: Forecasting and Control . . John Wiley & Sons, Hoboken, USA , , 2015 . . .

S Budalakoti , , , AN Srivastava , , , R Akella , , , 等 . . Anomaly Detection in Large Sets of High-Dimensional Symbol Sequences . . TM-2006-214553, NASA Ames Research Center, USA , , 2006 . . .

S Budalakoti , , , AN Srivastava , , , ME Otey . . Anomaly detection and diagnosis algorithms for discrete symbol sequences with applications to airline safety . . IEEE Trans Syst Man Cybern C , , 2009 . . 39 ( ( 1 ): ): 101 - - 113 . . DOI: 10.1109/TSMCC.2008.2007248 http://doi.org/10.1109/TSMCC.2008.2007248 . .

BP Carlin , , , TA Louis . . Bayes and Empirical Bayes Methods for Data Analysis (2 nd Ed.) . . Chapman & Hall/ CRC Press, Boca Raton, FL, USA , , 2000 . . .

V Chandola , , , V Mithal , , , V Kumar . . Comparative evaluation of anomaly detection techniques for sequence data . . Proc 8 th IEEE Int Conf on Data Mining , , 2008 . . p.743 - - 748 . . DOI: 10.1109/ICDM.2008.151 http://doi.org/10.1109/ICDM.2008.151 . .

V Chandola , , , A Banerjee , , , V Kumar . . Anomaly detection: a survey . . ACM Comput Surv , , 2009 . . 41 ( ( 3 ): ): Article 15 DOI: 10.1145/1541880.1541882 http://doi.org/10.1145/1541880.1541882 Article 15 . .

V Chandola , , , A Banerjee , , , V Kumar . . Anomaly detection for discrete sequences: a survey . . IEEE Trans Knowl Data Eng , , 2012 . . 24 ( ( 5 ): ): 823 - - 839 . . DOI: 10.1109/TKDE.2010.235 http://doi.org/10.1109/TKDE.2010.235 DOI: 10.1109/TKDE.2010.235 http://doi.org/10.1109/TKDE.2010.235 . .

MC Dani , , , C Freixo , , , FX Jollois , , , 等 . . Unsupervised anomaly detection for aircraft condition monitoring system . . Proc IEEE Aerospace Conf , , 2015 . . p.1 - - 7 . . DOI: 10.1109/AERO.2015.7119138 http://doi.org/10.1109/AERO.2015.7119138 . .

F Esposito , , , N di Mauro , , , TMA Basile , , , 等 . . Multidimensional relational sequence mining . . Fundam Inform , , 2008 . . 89 ( ( 1 ): ): 23 - - 43 . . . .

MA Hall . . Correlation-based feature selection for discrete and numeric class machine learning . . Proc 17 th Int Conf on Machine Learning , , 2000 . . p.359 - - 366 . . . .

Y Jin , , , WL Zuo . . Multi-dimensional concept lattice and incremental discovery of multi-dimensional sequential patterns . . J Comput Res Dev , , 2007 . . 44 ( ( 11 ): ): 1816 - - 1824 . . DOI: 10.1360/crad20071102 http://doi.org/10.1360/crad20071102 . .

L Kaufman , , , PJ Rousseeuw . . Finding Groups in Data: an Introduction to Cluster Analysis . . John Wiley & Sons, New York, USA , , 2009 . . .

E Keogh , , , K Chakrabarti , , , M Pazzani , , , 等 . . Dimensionality reduction for fast similarity search in large time series databases . . Knowl Inform Syst , , 2001 . . 3 ( ( 3 ): ): 263 - - 286 . . DOI: 10.1007/PL00011669 http://doi.org/10.1007/PL00011669 . .

JJ Kponyo , , , YJ Kuang , , , EZ Zhang , , , 等 . . VANET cluster-on-demand minimum spanning tree (MST) prim clustering algorithm . . Proc Int Conf on Computational Problem-Solving , , 2013 . . p.101 - - 104 . . DOI: 10.1109/ICCPS.2013.6893585 http://doi.org/10.1109/ICCPS.2013.6893585 . .

T Lane . . Machine Learning Techniques for the Domain of Anomaly Detection for Computer Security . . Purdue University, Indiana, USA , , 1998 . . .

CH Lee . . A multi-phase approach for classifying multidimensional sequence data . . Intell Data Anal , , 2015 . . 19 ( ( 3 ): ): 547 - - 561 . . DOI: 10.3233/IDA-150731 http://doi.org/10.3233/IDA-150731 . .

C Li , , , XG Tian , , , X Xiao , , , 等 . . Anomaly detection of user behavior based on shell commands and cooccurrence matrix . . J Comput Res Dev , , 2012 . . 49 ( ( 9 ): ): 1982 - - 1990 . . . .

XY Li , , , YJ Wang , , , XL Li , , , 等 . . Parallelizing skyline queries over uncertain data streams with sliding window partitioning and grid index . . Knowl Inform Syst , , 2014 . . 41 ( ( 2 ): ): 277 - - 309 . . DOI: 10.1007/s10115-013-0725-8 http://doi.org/10.1007/s10115-013-0725-8 . .

P Parveen , , , N Mcdaniel , , , Z Weger , , , 等 . . Evolving insider threat detection stream mining perspective . . Int J Artif Intell Tools , , 2013 . . 22 ( ( 5 ): ): 1360013 DOI: 10.1142/S0218213013600130 http://doi.org/10.1142/S0218213013600130 . .

Q Qian , , , JL Wu , , , W Zhu , , , 等 . . Improved edit distance method for system call anomaly detection . . Proc IEEE 12 th Int Conf on Computer and Information Technology , , 2012 . . p.1097 - - 1102 . . DOI: 10.1109/CIT.2012.223 http://doi.org/10.1109/CIT.2012.223 . .

DN Ron , , , Y Singer , , , N Tishby . . Learning probabilistic automata with variable memory length . . Proc 7 th Annual Conf on Computational Learning Theory , , 1994 . . p.35 - - 46 . . DOI: 10.1145/180139.181006 http://doi.org/10.1145/180139.181006 . .

E Sarhrouni , , , A Hammouch , , , D Aboutajdine . . Application of symmetric uncertainty and mutual information to dimensionality reduction and classification of hyperspectral images . . Int J Eng Technol , , 2012 . . 4 ( ( 5 ): ): 268 - - 276 . . DOI: 10.1145/180139.181006 http://doi.org/10.1145/180139.181006 . .

XK Shu , , , DF Yao , , , BG Ryder . . A formal framework for program anomaly detection . . Proc 18 th Int Symp Research in Attacks, Intrusions, and Defenses , , 2015 . . p.270 - - 292 . . DOI: 10.1007/978-3-319-26362-5_13 http://doi.org/10.1007/978-3-319-26362-5_13 . .

G Tandon , , , P Chan . . Learning rules from system call arguments and sequences for anomaly detection . . Proc ICDM Workshop on Data Mining for Computer Security , , 2003 . . p.20 - - 29 . . . .

Y Wang , , , X Ma . . A general scalable and elastic contentbased publish/subscribe service . . IEEE Trans Parall Distr Syst , , 2015 . . 26 ( ( 8 ): ): 2100 - - 2113 . . DOI: 10.1109/TPDS.2014.2346759 http://doi.org/10.1109/TPDS.2014.2346759 . .

YJ Wang , , , S Li . . Research and performance evaluation of data replication technology in distributed storage systems . . Comput Math Appl , , 2006 . . 51 ( ( 11 ): ): 1625 - - 1632 . . DOI: 10.1016/j.camwa.2006.05.002 http://doi.org/10.1016/j.camwa.2006.05.002 DOI: 10.1016/j.camwa.2006.05.002 http://doi.org/10.1016/j.camwa.2006.05.002 . .

YJ Wang , , , XY Li , , , XL Li , , , 等 . . A survey of queries over uncertain data . . Knowl Inform Syst , , 2013 . . 37 ( ( 3 ): ): 485 - - 530 . . DOI: 10.1007/s10115-013-0638-6 http://doi.org/10.1007/s10115-013-0638-6 . .

YJ Wang , , , X Pei , , , X Ma , , , 等 . . TA-update: an adaptive update scheme with tree-structured transmission in erasure-coded storage systems . . IEEE Trans Parall Distr Syst , , 2018 . . 29 ( ( 8 ): ): 1893 - - 1906 . . DOI: 10.1109/TPDS.2017.2717981 http://doi.org/10.1109/TPDS.2017.2717981 . .

JC Xianyu , , , S Rasouli , , , H Timmermans . . Analysis of variability in multi-day GPS imputed activitytravel diaries using multi-dimensional sequence alignment and panel effects regression models . . Transportation , , 2017 . . 44 ( ( 3 ): ): 533 - - 553 . . DOI: 10.1007/s11116-015-9666-2 http://doi.org/10.1007/s11116-015-9666-2 . .

TK Xiong , , , SR Wang , , , QS Jiang , , , 等 . . A new Markov model for clustering categorical sequences . . Proc IEEE 11 th Int Conf on Data Mining , , 2011 . . p.854 - - 863 . . DOI: 10.1109/ICDM.2011.13 http://doi.org/10.1109/ICDM.2011.13 . .

K Yamanishi , , , Y Maruyama . . Dynamic syslog mining for network failure monitoring . . Proc 11 th ACM SIGKDD Int Conf on Knowledge Discovery in Data Mining , , 2005 . . p.499 - - 508 . . DOI: 10.1145/1081870.1081927 http://doi.org/10.1145/1081870.1081927 . .

J Yang , , , W Wang . . CLUSEQ: efficient and effective sequence clustering . . Proc 19 th Int Conf on Data Engineering , , 2003 . . p.101 - - 112 . . DOI: 10.1109/ICDE.2003.1260785 http://doi.org/10.1109/ICDE.2003.1260785 . .

L Yu , , , H Liu . . Feature selection for high-dimensional data: a fast correlation-based filter solution . . Proc 20 th Int Conf on Machine Learning , , 2003 . . p.856 - - 863 . . . .

浏览量

Downloads

CSCD

文章被引用时，请邮件提醒。

Submit

工具集

关联资源

An ensemble method for data stream classification in the presence of concept drift

Deep anomaly detection of temporal heterogeneous data in AIOps: a survey

An efficient online histogram publication method for data streams with local differential privacy

Feature selection techniques for microarray datasets: a comprehensive review, taxonomy, and future directions

A software defect prediction method with metric compensation based on feature selection and transfer learning