Time Series Anomaly Pattern Recognition Based on Adaptive <i>k</i> Nearest Neighbor

Wang Ling; Zhou Nan; Shen Peng

doi:10.7544/issn1000-1239.202111062

Journal of Computer Research and Development > 2023 > 60(1): 125-139. > DOI: 10.7544/issn1000-1239.202111062 CSTR: 32373.14.issn1000-1239.202111062

Wang Ling, Zhou Nan, Shen Peng. Time Series Anomaly Pattern Recognition Based on Adaptive k Nearest Neighbor[J]. Journal of Computer Research and Development, 2023, 60(1): 125-139. DOI: 10.7544/issn1000-1239.202111062

Citation:

PDF (2114 KB)

Time Series Anomaly Pattern Recognition Based on Adaptive k Nearest Neighbor

School of Automation and Electrical Engineering, University of Science and Technology Beijing, Beijing 100083
Key Laboratory of Knowledge Automation for Industrial Processes(University of Science and Technology Beijing), Ministry of Education, Beijing 100083

Funds: This work was supported by the National Natural Science Foundation of China (62076025, 61572073).

More Information

Received Date: October 26, 2021
Revised Date: June 06, 2022
Available Online: February 10, 2023

Graphical Abstract

Abstract

Abstract

As a typical representative of data, time series is widely used in many research fields. The time series anomaly pattern represents the emergence of a special situation, and is of great significance in many fields. Most of the existing time series anomaly pattern recognition algorithms simply detect anomaly subsequences, ignoring the problem of distinguishing the types of anomaly subsequences, and many parameters need to be set manually. In this paper, an anomaly pattern recognition algorithm based on adaptive k nearest neighbor(APAKN) is proposed. Firstly, the adaptive neighbor value k of each subsequence is determined, and an adaptive distance ratio is introduced to calculate the relative density of the subsequence to determine the anomaly score. Then, an adaptive threshold method based on minimum variance is proposed to determine the anomaly threshold and detect all anomaly subsequences. Finally, the anomaly subsequences are clustered, and the obtained cluster centers are anomaly patterns with different changing trends. The whole algorithm process not only solves the density imbalance problem without setting any parameters, but also simplifies the steps of the traditional density-based anomaly subsequence detection algorithm to achieve a good anomaly pattern recognition effect. Experimental results on the 10 data sets of UCR show that the proposed algorithm performs well in detecting anomaly subsequences and clustering anomaly subsequences without setting parameters.
- time series,
- anomaly subsequences,
- anomaly pattern,
- adaptive k nearest neighbor,
- relative density

FullText(HTML)

References (32)

References

[1]	O'Leary B, Reiners J J, Xu Xiaohong, et al. Identification and influence of spatio-temporal outliers in urban air quality measurements[J]. Science of The Total Environment, 2016, 573: 55−65
[2]	Qin Yu, Lou Yuansheng. Hydrological time series anomaly pattern detection based on isolation forest[C] //Proc of the 3rd Information Technology, Networking, Electronic and Automation Control Conf (ITNEC). Piscataway, NJ: IEEE, 2019: 1706−1710
[3]	Wang Jibin, Wang Ping, Wang Suping. Automated detection of atrial fibrillation in ECG signals based on wavelet packet transform and correlation function of random process[J]. Biomedical Signal Processing and Control, 2020, 55: 101662
[4]	Liang Haoran, Song Lei, Wang Jianxing, et al. Robust unsupervised anomaly detection via multi-time scale DCGANs with forgetting mechanism for industrial multivariate time series[J]. Neurocomputing, 2021, 423: 444−462
[5]	Wang Xing, Lin J, Patel N, et al. Exact variable-length anomaly detection algorithm for univariate and multivariate time series[J]. Data Mining and Knowledge Discovery, 2018, 32(6): 1806−1844 doi: 10.1007/s10618-018-0569-7
[6]	苏卫星,朱云龙,刘芳,等. 时间序列异常点及突变点的检测算法[J]. 计算机研究与发展,2014,51(4):781−788 Su Weixing, Zhu Yunlong, Liu Fang, et al. A detection algorithm of outlier and mutation points in time series[J]. Journal of Computer Research and Development, 2014, 51(4): 781−788 (in Chinese)
[7]	刘芳,齐建鹏,于彦伟,等. 基于密度的Top-n局部异常点快速检测算法[J]. 自动化学报,2019,45(9):1756−1771 doi: 10.16383/j.aas.c180425 Liu Fang, Qi Jianpeng, Yu Yanwei, et al. A fast algorithm for density-based Top-n local outlier detection[J]. Acta Automatica Sinica, 2019, 45(9): 1756−1771 (in Chinese) doi: 10.16383/j.aas.c180425
[8]	Hyndman R J, Wang E, Laptev N. Large-scale unusual time series detection[C] //Proc of the 15th IEEE Int Conf on Data Mining Workshop (ICDMW). Piscataway, NJ: IEEE, 2015: 1616−1619
[9]	Senin P, Lin J, Wang Xing, et al. Time series anomaly discovery with grammar-based compression[C] //Proc of the 18th Int Conf on Extending Database Technology(EDBT). New York: ACM, 2015: 481−492
[10]	Boniol P, Palpanas T. Series2graph: Graph-based subsequence anomaly detection for time series[J]. Proceedings of the VLDB Endowment, 2020, 13(12): 1821−1834 doi: 10.14778/3407790.3407792
[11]	Cheng Kaiwen, Chen Yietarng, Fang Wenhsien. An efficient subsequence search for video anomaly detection and localization[J]. Multimedia Tools and Applications, 2016, 75: 15101−15122
[12]	Hawkins D. Identification of outliers[M] //Monographs on Applied Probability and Statistics. Berlin: Springer, 1980: 51−73
[13]	Huo Wunjun, Wang Wei, Li Wen. Anomalydetect: An online distance-based anomaly detection algorithm[C] //Proc of the Int Conf on Web Services. Berlin: Springer, 2019: 63−79
[14]	Zhang Pengcheng, Xiao Yan, Zhu Yuelong, et al. A new symbolization and distance measure based anomaly mining approach for hydrological time series[J]. International Journal of Web Services Research, 2016, 13(3): 26−45 doi: 10.4018/IJWSR.2016070102
[15]	Zheng Dequan, Li Fenghuan, Zhao Tiejun. Self-adaptive statistical process control for anomaly detection in time series[J]. Expert Systems with Applications, 2016, 57: 324−336
[16]	Izakian H, Pedrycz W. Anomaly detection in time series data using a fuzzy c-means clustering[C] //Proc of the Joint IFSA World Congress and NAFIPS Annual Meeting (IFSA/NAFIPS). Piscataway, NJ: IEEE, 2013: 1513−1518
[17]	Medico R, Spina D, VandeGinste D, et al. Autoencoding density-based anomaly detection for signal integrity applications[C] //Proc of the 27th IEEE Conf on Electrical Performance of Electronic Packaging and Systems (EPEPS). Piscataway, NJ: IEEE, 2018: 47−49
[18]	Zhang Chunkai, Chen Yingyang, Yin Ao. Anomaly subsequence detection with dynamic local density for time series[G] //LNCS 11707: Proc of the 30th Int Conf on Database and Expert Systems Applications. Berlin: Springer, 2019: 291−305
[19]	Dunn J C. A fuzzy relative of the ISODATA process, and its use in detecting compact well-separated clusters[J]. Journal of Cybernetics, 1973, 3(3): 32−57 doi: 10.1080/01969727308546046
[20]	Pedrycz W, Oliveira V. A development of fuzzy encoding and decoding through fuzzy clustering[J]. IEEE Transactions on Instrumentation & Measurement, 2008, 57(4): 829−837
[21]	Genolini C, Ecochard R, Benghezal M, et al. kmlShape: An efficient method to cluster longitudinal data (time-series) according to their shapes[J]. PLoS ONE, 2016, 11(6): 1−24
[22]	Likas A, Vlassis N, Verbeek J J. The global k-means clustering algorithm[J]. Pattern Recognition, 2003, 36(2): 451−461 doi: 10.1016/S0031-3203(02)00060-2
[23]	Ma Ruizhe, Filali S B, Angryk R. Time series distance density cluster with statistical preprocessing[C] //Proc of the 20th Int Conf on Big Data Analytics and Knowledge Discovery. Berlin: Springer, 2018: 371−381
[24]	Paparrizos J, Gravano L. K-shape: Efficient and accurate clustering of time series[C] //Proc of the 42nd ACM SIGMOD Int Conf on Management of Data. New York: ACM, 2015: 1855−1870
[25]	Breunig M M , Kriegel H P , Ng R T , et al. LOF: Identifying density-based local outliers[C] //Proc of the 28th ACM SIGMOD Int Conf on Management of Data. New York: ACM, 2000: 93−104
[26]	Berndt D J, Clifford J. Using dynamic time warping to find patterns in time series[C] //Proc of the Workshop on Knowledge Discovery in Databases. New York: ACM, 1994: 229−248
[27]	Cover T, Hart P. Nearest neighbor pattern classification[J]. IEEE Transactions on Information Theory, 1967, 13(1): 21−27 doi: 10.1109/TIT.1967.1053964
[28]	Pukelsheim F. The three sigma rule[J]. The American Statistician, 1994, 48(2): 88−91
[29]	Pérez-Ortiz M, Durán-Rosal A M, Gutiérrez P A, et al. On the use of evolutionary time series analysis for segmenting paleoclimate data[J]. Neurocomputing, 2019, 326/327: 3−14
[30]	Dau H A, Bagnall A, Kamgar K, et al. The UCR time series archive[J]. IEEE/CAA Journal of Automatica Sinica, 2019, 6(6): 1293−1305 doi: 10.1109/JAS.2019.1911747
[31]	Qian Pengjiang, Chung Fulai, Wang Shitong, et al. Fast graph-based relaxed clustering for large data sets using minimal enclosing ball[J]. IEEE Transactions on Systems, Man, and Cybernetics, 2012, 42(3): 672−687 doi: 10.1109/TSMCB.2011.2172604
[32]	Wang Yangtao, Chen Lihui. K-MEAP: Multiple exemplars affinity propagation with specified K clusters[J]. IEEE Transactions on Neural Networks and Learning Systems, 2016, 27(12): 2670−2682 doi: 10.1109/TNNLS.2015.2495268

[1]	Peng Yingtao, Meng Xiaofeng, Du Zhijuan. Survey on Diversified Recommendation[J]. Journal of Computer Research and Development, 2025, 62(2): 285-313. DOI: 10.7544/issn1000-1239.202330600
[2]	MB-HGCN: A Hierarchical Graph Convolutional Network for Multi-behavior Recommendation“CCIR 2024推荐”[J]. Journal of Computer Research and Development. DOI: 10.7544/issn1000-1239.202440770
[3]	Zeng Weixin, Zhao Xiang, Tang Jiuyang, Tan Zhen, Wang Wei. Iterative Entity Alignment via Re-Ranking[J]. Journal of Computer Research and Development, 2020, 57(7): 1460-1471. DOI: 10.7544/issn1000-1239.2020.20190643
[4]	Dai Chenchao, Wang Hongyuan, Ni Tongguang, Chen Shoubing. Person Re-Identification Based on Deep Convolutional Generative Adversarial Network and Expanded Neighbor Reranking[J]. Journal of Computer Research and Development, 2019, 56(8): 1632-1641. DOI: 10.7544/issn1000-1239.2019.20190195
[5]	Gu Liang, Yang Peng, Dong Yongqiang. A Diversified Recommendation Method for UCL in Broadcast-Storage Network[J]. Journal of Computer Research and Development, 2017, 54(8): 1631-1643. DOI: 10.7544/issn1000-1239.2017.20170128
[6]	Meng Xiangfu, Bi Chongchun, Zhang Xiaoyan, Tang Xiaoliang, Tang Yanhuan. Web Database top-k Diverse Keyword Query Suggestion Approach[J]. Journal of Computer Research and Development, 2017, 54(7): 1577-1591. DOI: 10.7544/issn1000-1239.2017.20160005
[7]	Yu Wenzhe, Sha Chaofeng, He Xiaofeng, Zhang Rong. Review Selection Considering Opinion Diversity[J]. Journal of Computer Research and Development, 2015, 52(5): 1050-1060. DOI: 10.7544/issn1000-1239.2015.20131932
[8]	Wang Xianghai, Cong Zhihuan, Fang Lingling, Song Chuanming. HMM Training Model Using Blending Population Diversity Based Aaptive Genetic Algorithm Title[J]. Journal of Computer Research and Development, 2014, 51(8): 1833-1844. DOI: 10.7544/issn1000-1239.2014.20121211
[9]	Zhang Weiguo, Yin Xia, and Wu Jianping. A Computation Method of Path Diversity Based on AS Relationships[J]. Journal of Computer Research and Development, 2012, 49(1): 167-173.
[10]	Han Jianmin, Yu Juan, Yu Huiqun, Jia Jiong. A Multi-Level l-Diversity Model for Numerical Sensitive Attributes[J]. Journal of Computer Research and Development, 2011, 48(1): 147-158.

Cited By

Cited by

Periodical cited type(7)

1.	罗宇哲，李玲，侯朋朋，于佳耕，程丽敏，张常有，武延军，赵琛. 面向AIoT的协同智能综述. 计算机研究与发展. 2025(01): 179-206 . 本站查看
2.	王蕴，林霄，楼芝兰，李军，孙卫强. 面向边缘光算力网络的上行链路资源协同调度算法. 光通信技术. 2024(03): 45-51 .
3.	王铭源，王正国，李济顺，薛玉君. 层级式机械装备健康指数模型及管理系统构建. 金属矿山. 2024(09): 198-206 .
4.	王睿，王岩，尹朴，齐建鹏，孙叶桃，李倩，张易达，张梅奎. 面向边缘智能的协同训练研究进展. 工程科学学报. 2023(08): 1400-1416 .
5.	薛建强，史彦军，李波. 面向无人集群的边缘计算技术综述. 兵工学报. 2023(09): 2546-2555 .
6.	阴彦磊，王立华，廖伟智，张万达. 融合GRU-Attention与鲸鱼算法的流程制造工艺参数云边联动优化. 计算机集成制造系统. 2023(09): 2991-3005 .
7.	许浩，朱晓娟. SDN中基于模型划分的云边协同推理算法. 兰州工业学院学报. 2023(06): 31-37 .