Evaluation of KPI Anomaly Detection Methods

doi:10.11871/jfdc.issn.2096-742X.2022.03.004

Abstract

Abstract:

[Objective] As the basis of rapid fault discovery and repair, key performance indicator (KPI, such as page view count, page-view delay, server CPU utilization, router memory utilization, switch throughput, server disk I/O) anomaly detection is becoming more and more critical for the rapid development of cloud computing technology services. [Coverage] We extensively investigated the related works of KPI anomaly detection at home and abroad in recent years. [Methods] We conduct in-depth research and analysis on KPI anomaly detection methods at various development stages and select 13 representative methods for experimental evaluation. [Results] We summarize the general problems, challenges, and frameworks. We evaluate the performance of these methods using the KPI dataset collected from three top-tier Internet companies in terms of accuracy, robustness, and efficiency. [Conclusions] These methods cover statistics-based, supervised, semi-supervised and unsupervised methods with advantages and disadvantages. Our research and analysis provide a basis for future researchers to select the most appropriate KPI anomaly detection method quickly and accurately for their scenarios.

Key words: Key performance indicator, anomaly detection, method evaluation, machine learning

SUN Yongqian,ZHANG Ruru,LIN Zihan,ZHANG Shenglin,TAN Zhiyuan,ZHANG Yuzhi. Evaluation of KPI Anomaly Detection Methods[J]. Frontiers of Data and Computing, 2022, 4(3): 46-65, https://cstr.cn/32002.14.jfdc.CN10-1649/TP.2022.03.004.

Figures/Tables 10

Fig.1

Fig.2

Fig.3

Table 1

Table 2

Fig.4

Table 3

Fig.5

Fig.6

Table 4

Used parameters of key performance indicator anomaly detection methods evaluated"

		Value	Parameter	Value
EWMA	$α$	0.1, 0.3, 0.5, 0.7, 0.9
Wavelet	win	3, 5, 7 (days)	freq	low, mid, high
Holt-winters	$α$ $γ$	0.2, 0.4, 0.6, 0.8 0.2, 0.4, 0.6, 0.8	$β$	0.2, 0.4, 0.6, 0.8
Opprentice	P	0.66	R	0.66
Opprentice	$α$	0.8	tree_count	30
ADS	min_samples	3	max_radius	0.05
ADS	tree_count	30
iForest	n_estimators max_samples	100 auto	contamination max_features	0.1 1
OCSVM	kernel	‘rbf’	nu	0.04
DeepAnT	window kernel_size	50 5	filters activation	32 ‘relu’
FuseAD	window kernel_size p q	50 5 2 2	filters activation d	32 ‘relu’ 1
Donut(Bagel)	window_size mcmc_iteration std_epsilon epoch initial_lr lr_anneal_factor (dropout_rate)	120 10 0.0001 50 0.001 0.75 (0.1)	missing_injection_rate latent_dim coefficient batch_size lr_anneal_epochs grad_clip_norm	0.01 8 0.001 256(128) 10 10.0
PUAD	max_radius	0.05
	$ω$	6	$ϵ$	9
	$π$	0.0015	$θ$	8
	$s$	0.200	$λ$	200

Table 4

References 52

[1]	裴丹, 张圣林, 裴昶华, 阿里巴巴公司. 基于机器学习的智能运维. 中国计算机学会通讯, 2017, 13(12): 68-72.
[2]	Barford P, Kline J, Plonka D, et al. A signal analysis of network traffic anomalies[C]// Proceedings of the 2nd ACM SIGCOMM Workshop on Internet measurement, 2002: 71-82.
[3]	Yan H, Flavel A, Ge Z, et al. Argus: End-to-end service anomaly detection and localization from an isp’s point of view[C]// 2012 Proceedings IEEE INFOCOM, IEEE, 2012: 2756-2760.
[4]	Zhang Yin, Ge Zihui, Greenberg A, et al. Network anom-ography[C]// Proceedings of the 5th ACM SIGCOMM conference on Internet Measurement, 2005: 30-30.
[5]	Krishnamurthy B, Sen S, Zhang Yin, et al. Sketch-based change detection: methods, evaluation, and applications[C]// Proceedings of the 3rd ACM SIGCOMM conference on Internet measurement, 2003: 234-247.
[6]	Choffnes D R, Bustamante F E, Ge Z. Crowdsourcing service-level network event monitoring[C]// Proceedings.of the ACM SIGCOMM 2010 Conference, 2010: 387-398.
[7]	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, 2017: 1067-1075.
[8]	Li J, Di S, Shen Y, et al. FluxEV: a fast and effective unsupervised framework for time-series anomaly detec-tion[C]// Proceedings of the 14th ACM International Con-ference on Web Search and Data Mining, 2021: 824-832.
[9]	Silverman B W. Density estimation for statistics and data analysis[M]. Routledge, 2018.
[10]	Cleveland R B, Cleveland W S, McRae J E, et al. STL: A seasonal-trend decomposition[J]. J. Off. Stat, 1990, 6(1): 3-73.
[11]	Wen Q, Gao J, Song X, et al. RobustSTL: A robust sea-sonal-trend decomposition algorithm for long time series[C]// Proceedings of the AAAI Conference on Artificial Intelligence, 2019, 33(01): 5409-5416.
[12]	Wen Q, Zhang Z, Li Y, et al. Fast RobustSTL: Efficient and robust seasonal-trend decomposition for time series with complex patterns[C]// Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Disco-very & Data Mining, 2020: 2203-2213.
[13]	Wen Q, He K, Sun L, et al. RobustPeriod: Robust Time-Frequency Mining for Multiple Periodicity Detection[C]// Proceedings of the 2021 International Conference on Management of Data, 2021: 2328-2337.
[14]	Chen Yingying, Mahajan R, Sridharan B, et al. A prov-ider-side view of web search response time[J]. ACM SIGCOMM Computer Communication Review, 2013, 43(4): 243-254. doi: 10.1145/2534169.2486035
[15]	Lee S B, Pei Dan, Hajiaghayi M T, et al. Threshold com-pression for 3g scalable monitoring[C]// 2012 Proceedings IEEE INFOCOM, IEEE, 2012: 1350-1358.
[16]	Mahimkar A, Ge Zihui, Wang Jia, et al. Rapid detection of maintenance induced changes in service performance[C]// Proceedings of the Seventh conference on emerging Networking EXperiments and Technologies, 2011: 1-12.
[17]	Liu Dapeng, Zhao Youjian, Xu Haowen, et al. Oppren-tice: Towards practical and automatic anomaly detection through machine learning[C]// Proceedings of the 2015 Internet Measurement Conference, 2015: 211-224.
[18]	Wang J, Jing Y, Qi Q, et al. ALSR: An adaptive label screening and relearning approach for interval-oriented anomaly detection[J]. Expert Systems with Applications, 2019, 136: 94-104. doi: 10.1016/j.eswa.2019.06.028
[19]	Zhang Y, Zhu Y, Li X, et al. Anomaly Detection Based on Mining Six Local Data Features and BP Neural Network[J]. Symmetry, 2019, 11(4): 571. doi: 10.3390/sym11040571
[20]	Bu Jiahao, Liu Ying, Zhang Shenglin, et al. Rapid depl-oyment of anomaly detection models for large number of emerging kpi streams[C]// 2018 IEEE 37th International Performance Computing and Communications Confer-ence (IPCCC), IEEE, 2018: 1-8.
[21]	ZHANG S, ZHAO C, SUI Y, et al. Robust KPI Anomaly Detection for Large-Scale Software Services with Partial Labels[C]// 2021 IEEE 32nd International Symposium on Software Reliability Engineering (ISSRE), Wuhan, China: IEEE, 2021: 103-114.
[22]	Qian J, Liu F, Li D, et al. Large-scale kpi anomaly dete-ction based on ensemble learning and clustering[J]. Journal of Cybersecurity, 2020, 2(4): 157-166.
[23]	Ding Zhiguo, Fei Minrui. An anomaly detection approach based on isolation forest algorithm for streaming data using sliding window[J]. IFAC Proceedings Volumes, 2013, 46(20): 12-17.
[24]	Jiang Jianmin, Yasakethu L. Anomaly detection via one class svm for protection of scada systems[C]// 2013 International Conference on Cyber-Enabled Distributed Computing and Knowledge Discovery, IEEE, 2013: 82-88.
[25]	Amer M, Goldstein M, Abdennadher S. Enhancing one-class support vector machines for unsupervised anomaly detection[C]// Proceedings of the ACM SIGKDD workshop on outlier detection and description, 2013: 8-15.
[26]	Munir M, Siddiqui S A, Dengel A, et al. DeepAnT: A deep learning approach for unsupervised anomaly detection in time series[J]. IEEE Access, 2018, 7: 1991-2005. doi: 10.1109/ACCESS.2018.2886457
[27]	Munir M, Siddiqui S A, Chattha M A, et al. FuseAD: unsupervised anomaly detection in streaming sensors data by fusing statistical and deep learning models[J]. Sensors, 2019, 19(11): 2451. doi: 10.3390/s19112451
[28]	Xu Haowen, Chen Wenxiao, Zhao Nengwen, et al. Unsupervised anomaly detection via variational auto-encoder for seasonal kpis in web applications[C]// Proce-edings of the 2018 World Wide Web Conference, 2018: 187-196.
[29]	Li Zeyan, Chen Wenxiao, Pei Dan. Robust and unsuper-vised kpi anoALSmaly detection based on conditional variational autoencoder[C]// 2018 IEEE 37th International Performance Computing and Commun-ications Confer-ence (IPCCC), IEEE, 2018: 1-9.
[30]	YU G, CAI Z, WANG S, et al. Unsupervised Online Anomaly Detection With Parameter Adaptation for KPI Abrupt Changes[J]. IEEE Transactions on Network and Service Management, 2020, 17(3): 1294-1308. doi: 10.1109/TNSM.2019.2962701
[31]	WANG Y, WANG Z, XIE Z, et al. Practical and White-Box Anomaly Detection through Unsupervised and Act-ive Learning[C]// 2020 29th International Conference on Computer Communications and Networks (ICCCN), Honolulu, HI, USA: IEEE, 2020: 1-9.
[32]	ZHAO Y, ZHANG X, SHANG Z, et al. A Novel Hybrid Method for KPI Anomaly Detection Based on VAE and SVDD[J]. Symmetry, 2021, 13(11): 2104. doi: 10.3390/sym13112104
[33]	NIE L, ZHAO L, LI K. Robust Anomaly Detection Using Reconstructive Adversarial Network[J]. IEEE Transa-ctions on Network and Service Management, 2021, 18 (2): 1899-1912.
[34]	YOKKAMPON U, CHUMKAMON S, MOWSHOWITZ A, et al. Improved Variational Autoencoder Anomaly Detection in Time Series Data[C]// 2020 IEEE Inter-national Conference on Systems, Man, and Cybernetics (SMC), Toronto, ON, Canada: IEEE, 2020: 82-87.
[35]	NIU Z, YU K, WU X. LSTM-Based VAE-GAN for Time-Series Anomaly Detection[J]. Sensors, 2020, 20 (13): 3738. doi: 10.3390/s20133738
[36]	GEIGER A, LIU D, ALNEGHEIMISH S, et al. TadGAN: Time Series Anomaly Detection Using Generative Adver-sarial Networks[C]// 2020 IEEE International Conference on Big Data (Big Data), Atlanta, GA, USA: IEEE, 2020: 33-43.
[37]	YE H, MA X, PAN Q, et al. An Adaptive Approach for Anomaly Detector Selection and Fine-Tuning in Time Series[J]. arXiv:1907.07843 [cs, stat], 2019.
[38]	REN H, XU B, WANG Y, et al. Time-Series Anomaly Detection Service at Microsoft[C]// Proceedings of the 25th ACM SIGKDD International Conference on Know-ledge Discovery & Data Mining, Anchorage AK USA: ACM, 2019: 3009-3017.
[39]	Qiu Juan, Qingfeng Du, Wei Wang, Kanglin Yin, and Liang Chen. Short-term performance metrics forecasting for virtual machine to support anomaly detection using hybrid ARIMA-WNN model[C]. In 2019 IEEE 43rd Ann-ual Computer Software and Applications Conference (CO-MPSAC), IEEE, 2019,vol. 2,pp.330-335.
[40]	LAN Z, XU L, FANG W. FDNN: Feature-based Deep Neural Network Model for Anomaly Detection of KPIs[C]//2019 IEEE 10th International Conference on Software Engineering and Service Science (ICSESS), Beijing, China: IEEE, 2019: 286-289.
[41]	JIANG W, HONG Y, ZHOU B, et al. A GAN-Based Ano-maly Detection Approach for Imbalanced Industrial Time Series[J]. IEEE Access, 2019, 7: 143608-143619. doi: 10.1109/ACCESS.2019.2944689
[42]	Duan X Y, Chen N J, Xie Y S. Intelligent Detection of Large-Scale KPI Streams Anomaly Based on Transfer Learning[C]// CCF Conference on Big Data. Springer, Singapore, 2019: 366-379.
[43]	Chen W, Xu H, Li Z, et al. Unsupervised anomaly dete-ction for intricate kpis via adversarial training of vae[C]// IEEE INFOCOM 2019-IEEE Conference on Computer Communications, IEEE, 2019: 1891-1899.
[44]	Shi J, He G, Liu X. Anomaly detection for key perfor-mance indicators through machine learning[C]// 2018 International Conference on Network Infrastructure and Digital Content (IC-NIDC), IEEE, 2018: 1-5.
[45]	Al Mamun S M, Beyaz M. LSTM recurrent neural net-work (RNN) for anomaly detection in cellular mobile net-works[C]// International Conference on Machine Learning for Networking, Springer, Cham, 2018: 222-237.
[46]	Chandola V, Banerjee A, Kumar V. Anomaly detection: A survey[J]. ACM computing surveys (CSUR), 2009, 41(3): 1-58.
[47]	Shon T, Moon J. A hybrid machine learning approach to network anomaly detection[J]. Information Sciences, 2007, 177(18): 3799-3821. doi: 10.1016/j.ins.2007.03.025
[48]	Zhang J, Wang Z, Yuan J, et al. Positive and unlabeled learning for anomaly detection with multi-features[C]// Proceedings of the 25th ACM international conference on Multimedia, 2017: 854-862.
[49]	Li Zhihan, Zhao Youjian, Liu Rong, et al. Robust and rapid clustering of kpis for large-scale anomaly detection[C]// 2018 IEEE/ACM 26th International Symposium on Quality of Service (IWQoS), IEEE, 2018: 1-10.
[50]	Qiu J, Du Q, Qian C. Kpi-tsad: A time-series anomaly detector for kpi monitoring in cloud applications[J]. Sy-mmetry, 2019, 11(11): 1350.
[51]	Paparrizos J, Gravano L. k-shape: Efficient and accu-rate clustering of time series[C]// Proceedings of the 2015 ACM SIGMOD International Conference on Managem-ent of Data, 2015: 1855-1870.
[52]	Zhang Shenglin, Lin Xiaofei, Sun Yongqian, et al. Rese-arch on Unsupervised KPI Anomaly Detection Based on Deep Learning[J]. Frontiers of Data&Computing, 2020, 2(3): 87-100.

	需要标注	人工调参	方法技术	适用KPI类型	输出	发表年份
Opprentice	√	否	随机森林	通用	离散值	2015
ADS	√	否	聚类和随机森林	通用	离散值	2018
PUAD	√	否	聚类和PU学习^[48]	通用	离散值	2021
iForest	×	部分	孤立森林	通用	离散值	2013
OCSVM	×	部分	支持向量机	通用	离散值	2013
Donut	×	否	深度生成模型	周期	连续值	2018
Bagel	×	否	深度生成模型	周期	连续值	2018
DeepAnT	×	否	卷积神经网络	周期	连续值	2018
FuseAD	×	否	统计和卷积神经网络	周期	连续值	2019
ARIMA	×	是	统计	通用	离散值	2005
EWMA	×	是	统计	通用	离散值	2003
Wavelet	×	是	统计	通用	离散值	2002
Holt-Winters	×	是	统计	通用	离散值	2012

数据集	时间间隔（分钟）	KPI曲线数量	数据点数量	异常点数量	异常点占比（%）
A	1	12	3145250	58436	1.86
B	1	7	1679741	51082	3.04
C	5	97	838064	2799	0.33

		A			B			C
	Precision	Recall	F1-score	Precision	Recall	F1-score	Precision	Recall	F1-score
ARIMA	0.91	0.55	0.68	0.57	0.55	0.56	0.70	0.81	0.75
EWMA	0.91	0.55	0.69	0.40	0.55	0.46	0.70	0.82	0.75
Wavelet	0.69	0.40	0.51	0.47	0.42	0.44	0.43	0.77	0.55
Holt-winters	0.60	0.51	0.55	0.25	0.34	0.29	0.62	0.77	0.69
Opprentice	0.72	0.69	0.70	0.98	0.85	0.91	0.76	0.83	0.79
ADS	0.55	0.74	0.63	0.60	0.73	0.66	0.81	0.96	0.88*
PUAD	0.88	0.77	0.82*	0.91	0.96	0.93*	0.78	0.95	0.86
iForest	0.54	1	0.70	0.46	1	0.63	0.30	0.89	0.45
OCSVM	0.40	0.99	0.57	0.31	0.98	0.47	0.28	1	0.44
DeepAnT	0.79	0.77	0.78	0.90	0.97	0.93*	0.69	0.90	0.78
FuseAD	0.72	0.69	0.71	0.81	0.84	0.83	0.69	0.94	0.79
Bagel	0.74	0.82	0.78	0.62	0.82	0.71	0.83	0.87	0.85
Donut	0.82	0.79	0.80	0.80	0.80	0.80	0.84	0.90	0.87