一种快速的突变点在线检测算法设计与实现

doi:10.16180/j.cnki.issn1007-7820.2020.08.002

摘要/Abstract

摘要：

传统TSTKS算法是一种离线突变点检测算法,该算法在待检测数据存在多个突变点时准确度较低。针对这一问题,文中结合TSTKS算法与滑动窗口理论,提出了一种快速时序数据突变点在线检测方法。该方法利用滑动窗口的思想将待检测数据切分为若干子段,并根据窗口顺序对每个子段采用TSTKS算法进行突变点检测,进而实现时序数据多突变点快速检测。实验结果表明,相比于常见的几种突变点检测算法,采用文中提出算法对存在多突变点的时序数据进行检测时耗时较少,相对误差率较低且命中率较高。

关键词: TSTKS算法, 突变点检测, 三叉搜索树, 滑动窗口理论, 时序数据, 在线检测

Abstract:

The traditional TSTKS algorithm is an offline mutation point detection algorithm, which has low accuracy when there are multiple mutation points in the time series data. To solve this problem, TSTKS algorithm and sliding window theory were combined to propose an online detection method for fast time series data mutation points. The method used sliding window to divide the data into several sub-segments, and took TSTKS algorithm to detect the mutation point for each sub-segment according to the order of window, so as to realize the rapid multi-mutation points detection of time series data. The results showed that compared with the common algorithms, the proposed algorithm took less time, had lower relative error rate and higher hit rate in multiple mutation points detection

Key words: TSTKS algorithm, mutation point detection, trigeminal search tree, sliding window theory, time series data, online detection

中图分类号:

TP311

邹俊晨,齐金鹏,李娜,刘佳伦,朱厚杰. 一种快速的突变点在线检测算法设计与实现[J]. 电子科技, 2020, 33(8): 10-16.

ZOU Junchen,QI Jinpeng,LI Na,LIU Jialun,ZHU Houjie. Design and Implementation of a Fast Online Algorithm for Mutation Point Detection[J]. Electronic Science and Technology, 2020, 33(8): 10-16.

图/表 12

图1

图2

图3

图4

图5

图6

图7

表1

图8

表2

图9

表3

参考文献 22

[1]	Aminikhanghahi S, Cook D J. A survey of methods for time series change point detection[J]. Knowledge and Information Systems, 2017,51(2):339-367. doi: 10.1007/s10115-016-0987-z pmid: 28603327
[2]	宋巧红. 一种数据流突变点快速探测算法的研究与实现[D]. 上海:东华大学, 2018.
	Song Qiaohong. Research and implementation of a fast detection algorithm for abrupt-point change of data stream[D]. Shanghai:Donghua University, 2018.
[3]	Fatih C. Change point detection in time series data using support vectors[J]. International Journal of Pattern Recognition and Artificial Intelligence, 2010,24(1):73-95. doi: 10.1142/S0218001410007865
[4]	Yoshinobu K, Masashi S. Sequential change point detection based on directdensity-ratio estimation[J]. Statistical Analysis and Data Mining, 2012,5(2):114-127. doi: 10.1002/sam.v5.2
[5]	Song L, Makoto Y, Nigel C, et al. Change-point detection in time-series data by relative density-ratio estimation[J]. Neural Networks, 2013,43(1):72-83. doi: 10.1016/j.neunet.2013.01.012
[6]	Katherine B E. Time series analysis and its applications[J]. Journal of the American Statistical Association, 2002,97(458):656-657. doi: 10.1198/jasa.2002.s477
[7]	Richard L. Time series analysis and its applications[J]. International Journal of Forecasting, 2001,17(2):299-301. doi: 10.1016/S0169-2070(01)00083-8
[8]	Naoki I, Jurgen K. Change-point detection of climate time series by nonparametric method[J]. Lecture Notes in Engineering and Computer Science, 2010,2186(1):445.
[9]	苏卫星, 朱云龙, 刘芳, 等. 时间序列异常点及突变点的检测算法[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.
[10]	吕凤毛. 面向数据有效学习的机器学习技术研究[D]. 成都:电子科技大学, 2018.
	Lü Fengmao. Research of machine learning techniques for data-efficient learning[D]. Chengdu:University of Electronic Science and Technology of China, 2018.
[11]	顾健. 相关向量机分类方法的应用研究[J]. 电子科技, 2016,29(6):37-40.
	Gu Jian. Application research on classification method of relevance vector machine[J]. Electronic Science and Technology, 2016,29(6):37-40.
[12]	韩敏, 李宇, 韩冰. 基于改进结构保持数据降维方法的故障诊断研究[J]. 自动化学报, 2019(1):1-11.
	Han Min, Li Yu, Han Bing. Research on fault diagnosis of data dimension reduction based on improved structure preserving algorithm[J]. Acta Automatica Sinica, 2019(1):1-11.
[13]	黄铉. 特征降维技术的研究与进展[J]. 计算机科学, 2018,45(1):16-21.
	Huang Xuan. Research and development of feature dimensionality reduction[J]. Computer Science, 2018,45(1):16-21.
[14]	王强. 决策树过拟合问题研究[D]. 合肥:合肥工业大学, 2008.
	Wang Qiang. Overfitting problem researching on decision tree[D]. Hefei:Hefei University of Technology, 2008.
[15]	陈大伟, 闫昭, 刘昊岩. SVD系列算法在评分预测中的过拟合现象[J]. 山东大学学报(工学版), 2014,44(3):15-21.
	Chen Dawei, Yan Zhao, Liu Haoyan. Overfitting phenomenon of the series of single value decomposition algorithms in rating prediction[J]. Journal of Shandong University(Engineering Science Edition), 2014,44(3):15-21.
[16]	吕子昂, 罗四维, 杨坚, 等. 模型的固有复杂度和泛化能力与几何曲率的关系[J]. 计算机学报, 2007(7):1094-1103
	Lü Ziang, Luo Siwei, Yang Jian, et al. The research between intrinsic complexity and generalization of a model and the geometric curvature[J]. Chinese Journal of Computers, 2007(7):1094-1103.
[17]	王伟平, 李建中, 张冬冬, 等. 数据流上周期更新滑动窗口的连接算法[J]. 哈尔滨工业大学学报, 2005(6):756-759.
	Wang Weiping, Li Jianzhong, Zhang Dongdong, et al. Periodically updating sliding window join algorithms over data streams[J]. Journal of Harbin Institute of Technology, 2005(6):756-759.
[18]	李建中, 张冬冬. 滑动窗口规模的动态调整算法[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.
[19]	康伟, 李战怀, 张龙波. 基于滑动窗口的数据流连接聚集查询降载策略[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.
[20]	Qi J P, Zhang Q, Qi J, et al. Multi-channel detection for abrupt change based on the ternary search tree and kolmogorov statistic method[C]. Hangzhou:34^th Chinese Control Conference (CCC), 2015.
[21]	Qi J P, Zhang Q, Zhu Y, et al. Anovel method for fast change-point detection on simulated time series and electrocardiogram data[J]. PLoS ONE, 2014,9(4):1-15.
[22]	宋巧红, 齐金鹏, 张煜. 基于多级Haar小波变换与KS统计的突变点快速探测方法[J]. 计算机工程, 2018,44(5):14-18. doi: 10.19678/j.issn.1000-3428.0046777
	Song Qiaohong, Qi Jinpeng, Zhang Yu. Fast abrupt point detection method based on multistage Haar wavelet transform and KS statistic[J]. Computer Engineering, 2018,44(5):14-18. doi: 10.19678/j.issn.1000-3428.0046777

窗口宽度 W	时耗 Tim/s	相对误差率 CoE/%	命中率 Hit/%
27	0.839 7	37.770 0	67.480 0
29	0.262 5	17.720 0	88.860 0
210	0.146 3	11.530 0	93.040 0
211	0.084 6	12.480 0	92.220 0
213	0.039 1	40.560 0	76.060 0

参数	TSTKS	HWKS	KS	T
时耗Tim / s	0.108 5	0.036 4	0.608 7	1.481 7
相对误差率CoE / %	10.410 0	16.160 0	4.510 0	439.190 0
命中率Hit / %	92.760 0	87.200 0	93.340 0	28.360 0

窗口宽度W	参数	TSTKS	HWKS	KS	T
32	细节波动DS	1.462 3	1.515 8	0.673 4	0.679 8
	统计波动VS	87.490 4	89.226 2	50.380 6	105.988 8
	时耗Tim/s	0.203 0	0.133 0	0.321 0	0.375 0
64	细节波动DS	1.253 9	1.797 6	0.725 9	0.489 6
	统计波动VS	83.182 0	81.983 4	64.811 0	66.215 2
	时耗Tim/s	0.047 0	0.033 0	0.117 0	0.171 0
128	细节波动DS	2.567 6	2.232 2	1.576 5	0.886 9
	统计波动VS	143.976 4	141.814 5	144.720 2	102.982 4
	时耗Tim/s	0.018 0	0.014 0	0.052 0	0.141 0
256	细节波动DS	7.082 7	3.986 4	1.922 6	1.008 5
	统计波动VS	251.787 2	189.326 4	146.791 9	83.966 3
	时耗Tim/s	0.005 0	0.002 0	0.011 0	0.213 0