一种基于随机交叠策略的多突变点在线检测方法

doi:10.16180/j.cnki.issn1007-7820.2022.12.001

摘要/Abstract

摘要：

传统的突变点检测方法多以离线为主,无法对大规模的时序数据进行在线检测。针对这一问题,文中基于缓冲区模型和滑动窗口随机交叠策略,提出一种多突变点在线检测方法。该方法以TSTKS算法和滑动窗口模型为基础,通过缓冲区模型实时接收在线时序数据流,并将数据转移到数据接收器中;随后,在数据接收器中使用滑动窗口随机交叠策略对数据流进行切分;最后,在子数据流中用TSTKS算法对数据进行多突变点在线检测。仿真数据和癫痫病人的肌电数据等实验结果表明,文中所提方法具有时耗较短、准确率较高等优点,可作为大规模时序数据流的在线分析备选方案。

关键词: 突变点检测, 交叠理论, 缓冲区, 在线算法, 滑动窗口, 时序数据, 大数据分析, 多路搜索树

Abstract:

The traditional detection methods of multiple change points are mainly off-line, and cannot detect large-scale time series data online. To solve this problem, this study proposes an online detection method of multiple change points based on the buffer model and the sliding window random overlapping strategy. This method is based on TSTKS algorithm and sliding window model, receives online time series data stream in real time through buffer model, and transfers the data to the data receiver. Subsequently, the data stream is segmented using a sliding window random overlap strategy in the data sink. Finally, in the sub-data stream, TSTKS algorithm is used to perform online detection of multiple change points on the data. The experimental results of simulation data and EMG data of epilepsy patients show that the proposed method has the advantages of shorter time consumption and higher accuracy, and can be considered as an alternative for online analysis of large-scale time series data streams.

Key words: multiple change points detection, overlapping theory, the buffer, online algorithm, sliding window, time series data, big data analysis, ternary search tree

中图分类号:

TP311

朱俊俊,齐金鹏,钟金美,任晴,曹一彤. 一种基于随机交叠策略的多突变点在线检测方法[J]. 电子科技, 2022, 35(12): 1-9.

ZHU Junjun,QI Jinpeng,ZHONG Jinmei,REN Qing,CAO Yitong. An Online-Method of Multiple Change Points Detection Based on Random and Overlapping Strategy[J]. Electronic Science and Technology, 2022, 35(12): 1-9.

图/表 11

图1

图2

图3

图4

图5

图6

表1

图7

表2

图8

表3

参考文献 20

[1]	邬贺铨. 邬贺铨院士:大数据时代的发展趋势[J]. 广东科技, 2016, 25(17):30-33.
	Wu Hequan. Academician Wu Hequan:The development trend of big data era[J]. Guangdong Science and Technology, 2016, 25(17):30-33.
[2]	严霄凤, 张德馨. 大数据研究[J]. 计算机技术与发展, 2013, 23(4):168-172.
	Yan Xiaofeng, Zhang Dexin. Big data research[J]. Computer Technology and Development, 2013, 23(4):168-172.
[3]	张娜. 大数据时代的挑战、价值与应对策略[J]. 数码世界, 2021(1):62-63.
	Zhang Na. Challenges values and countermeasures in the era of big data[J]. Digital World, 2021(1):62-63.
[4]	姚艳秋. 基于趋势分析的变电站设备异常检测方法[J]. 吉林大学学报(理学版), 2021, 59(3):649-652.
	Yao Yanqiu. Abnormality detection method of substation equipment based on tendency analysis[J]. Journal of Jilin University(Science Edition), 2021, 59(3):649-652.
[5]	范程华, 王群京, 曹欣远, 等. 基于信号突变点校正的太阳能电池片缺陷检测方法[J]. 激光与光电子学进展, 2020, 57(6):238-243.
	Fan Chenghua, Wang Qunjing, Cao Xinyuan, et al. Defect detection method for solar cell based on signal catastrophe-points correction[J]. Laser & Optoelectronics Progress, 2020, 57(6):246-251.
[6]	Atashgar K. Identification of the change point: An overview[J]. The International Journal of Advanced Manufacturing Technology, 2013, 64(9-12):1663-1683. doi: 10.1007/s00170-012-4131-2
[7]	邹俊晨, 齐金鹏, 李娜, 等. 一种快速的突变点在线检测算法设计与实现[J]. 电子科技, 2020, 33(8):10-15.
	Zou Junchen, Qi Jinpeng, Li Na, et al. Design and implementation of a fast online algorithm for mutation point detection[J]. Electronic Science and Technology, 2020, 33(8):10-15.
[8]	李娜, 齐金鹏, 邹俊晨, 等. 一种基于脑电波突变分析的癫痫疾病检测方法[J]. 信息技术, 2019, 43(12):41-46.
	Li Na, Qi Jinpeng, Zou Junchen, et al. Epilepsy disease detection based on drain wave mutation analysis[J]. Information Technology, 2019, 43(12):41-46.
[9]	Qi J P, Qi J, Pu F, et al. Multi-channel detection for abrupt change based on the ternary search tree and kolmogorov statistic method[C]. Hangzhou: Proceedings of the Thirty-fourth Chinese Control Conference, 2015.
[10]	宋向忠. “t”检验在新建分析方法评价中的应用[J]. 石化技术, 2021, 28(7):49-50.
	Song Xiangzhong. Application of "t" test in evaluation of new analytical methods[J]. Petrochemical Technology, 2021, 28(7):49-50.
[11]	侯澍旻, 李友荣, 刘光临. 一种基于KS检验的时间序列非线性检验方法[J]. 电子与信息学报, 2007(4):808-810.
	Hou Shumin, Li Yourong, Liu Guangfen. A nonlinear test method for time series based on KS test[J]. Journal of Electronics & Information technology, 2007(4):808-810.
[12]	Liu J L, Qi J P, Zou J C, et al. Multiple change points detection method based on TSTKS and CPI sliding window strategy[C]. Shenzhen: Proceedings of Chinese Intelligent Systems Conference, 2020.
[13]	李建中, 张冬冬. 滑动窗口规模的动态调整算法[J]. 软件学报, 2004(12):1800-1814.
	Li Jianzhong, Zhang Dongdong. Algorithms for dynamically adjusting the sizes of sliding windows[J]. Journal of Software, 2004(12):1800-1814.
[14]	康伟, 李战怀, 张龙波. 基于滑动窗口的数据流连接聚集查询降载策略[J]. 计算机工程, 2009, 35(22):50-52.
	Kang Wei, Li Zhanhuai,Zhang Longbo.Load shedding strategy of join aggregation query over data streams based on sliding window[J]. Computer Engineering, 2009, 35(22):50-52.
[15]	苏卫星, 朱云龙, 刘芳, 等. 时间序列异常点及突变点的检测算法[J]. 计算机研究与发展, 2014, 51(4):781-788.
	Su Weixing, Zhu Yunlong, Liu Fang, et al. Outliers and change-points detection algorithm for time series[J]. Journal of Computer Research and Development, 2014, 51(4):781-788.
[16]	张媛, 李常斌, 王刘明, 等. 几种河川径流序列突变检验方法的对比[J]. 水利水电技术, 2020, 51(2):38-47.
	Zhang Yuan, Li Changbin, Wang Liuming, et al. Application and comparison of several test methods for changepoints diagnosis in stream flow variations[J]. Water Resources and Hydropower Engineering, 2020, 51(2):38-47.
[17]	刘弹, 李晓婉, 梁霖, 等. 采用时间序列突变点检测的滚动轴承性能退化评价方法[J]. 西安交通大学学报, 2019, 53(12):10-16.
	Liu Dan, Li Xiaowan, Liang Lin, et al. A method for evaluating performance degradation of rolling bearings using detection of time series mutation point[J]. Journal of Xi'an Jiaotong University, 2019, 53(12):10-16.
[18]	刘杰, 房俊, 雷峰津. 电能质量异常数据在线检测方法[J]. 计算机工程与应用, 2020, 56(9):240-247. doi: 10.3778/j.issn.1002-8331.1901-0084
	Liu Jie, Fang Jun, Lei Fengjin. On-line detection method for abnormal data of power quality[J]. Computer Engineering and Applications, 2020, 56(9):240-247. doi: 10.3778/j.issn.1002-8331.1901-0084
[19]	王文, 饶元, 李绍稳, 等. 基于预测模型的异常农情数据在线检测方法的研究[J]. 湖南农业大学学报(自然科学版), 2020, 46(4):495-500.
	Wang Wen, Rao Yuan, Li Shaowen, et al. Research on online detection method of abnormal agricultural condition data based on predictive model[J]. Journal of Hunan Agricultural University(Natural Science Edition), 2020, 46(4):495-500.
[20]	丁智国, 莫毓昌, 杨凡. 一种新的在线流数据异常检测方法[J]. 计算机科学, 2016, 43(10):63-65. doi: 10.11896/j.issn.1002-137X.2016.10.011
	Ding Zhiguo, Mo Yuchang, Yang Fan. Novel anomaly detection method of online streaming data[J]. Computer Science, 2016, 43(10):63-65. doi: 10.11896/j.issn.1002-137X.2016.10.011

算法性能	TSTKS	HWKS	KS	T
Tim/s	0.159 0	0.105 0	0.571 0	1.976 0
Hit/%	89.4	85.1	71.6	63.5
MAE	0.31	1.25	1.81	107.70

缓冲区长度	Tim/s	SF	DF
2⁹	1.538 2	0.369 4	85.235 6
2¹⁰	1.631 1	0.392 6	78.993 9
2¹¹	1.715 3	0.378 1	81.430 4
2¹⁴	1.694 1	0.377 9	73.038 0

算法性能	TSTKS	HWKS	KS	T
Tim/s	1.686 0	0.812 0	0.602 0	3.730 0
VF	34.973 5	20.866 5	328.550 9	65.397 2
DF	0.386 8	0.368 1	0.324 3	0.339 4