有监督时间序列分割与状态识别算法

doi:10.19678/j.issn.1000-3428.0056243

摘要/Abstract

摘要： 时间序列分割与状态识别是一项重要的时间序列挖掘任务，可用于识别被监测对象的运行状态，然而目前多数无监督时间序列分割算法得到的结果无法满足用户的状态识别期望。为实现符合用户意图的时间序列分割，提出一种有监督的时间序列分割算法。构造特征集合并自动训练特征概率模型参数，以此构建特征高斯概率分布模型进行相关序列的特征设计，同时利用匹配损失计算和改进的贪心策略设定特征权重约束，通过增加分割位置约束条件及增量计算2种优化方式提高分割效率。在多个真实数据集上的实验结果表明，与pHMM和AutoPlait算法相比，该算法可以全面表达状态类别，对时间序列进行更精准的分割。

关键词: 数据挖掘, 时间序列分割, 状态识别, 特征模型, 贪心策略

Abstract: Time series segmentation and state recognition is an important time series mining task that can be used to automatically identify the running state of the monitored object,but servel unsupervised time series segmentation algorithms fail to meet the state recognition expectation of users.To address the problem,this paper proposes a supervised time series segmentation algorithm.It constructs a characteristic set and on this basis trains the parameters of the characteristic probability model automatically,so as to build the characteristic Gaussian probability distribution model and design the characteristics of the related sequence.Meanwhile,the matching loss calculation and improved greedy strategy are used to design feature weight constraints,and the segmentation efficiency is increased by using two optimization methods:adding constraints of segmentation positions and incremental calculation.Experimental results on multiple real data sets show that,compared with the pHMM and AutoPlait algorithms,the proposed algorithm can fully express all categories of states and implement more accurate segmentation of time series.

Key words: data mining, time series segmentation, state recognition, feature model, greedy strategy

中图分类号:

TP391

史明阳, 王鹏, 汪卫. 有监督时间序列分割与状态识别算法[J]. 计算机工程, 2020, 46(5): 131-138.

SHI Mingyang, WANG Peng, WANG Wei. Algorithm of Supervised Time Series Segmentation and State Recognition[J]. Computer Engineering, 2020, 46(5): 131-138.

https://www.ecice06.com/CN/Y2020/V46/I5/131

图/表 8

20200513201856

20200513201901

20200513201904

20200513201908

20200513201912

20200513201916

20200513201919

20200513201923

参考文献

[1] LIAO Jun,ZHOU Zhongliang,KOU Yingxin,et al.Method for time series segment based on important point[J].Computer Engineering and Applications,2011,47(24):166-170.(in Chinese)廖俊,周中良,寇英信,等.一种基于重要点的时间序列分割方法[J].计算机工程与应用,2011,47(24):166-170.
[2] JIANG Yixian,ZHANG Qishan.Time series segmentation algorithm based on important point and grey GM(1,1) model[J].Statistics and Decision,2016(24):28-30.(in Chinese)江艺羡,张岐山.基于重要点与灰色GM(1,1)模型的时间序列分段算法[J].统计与决策,2016(24):28-30.
[3] WANG Lizhu,LIU Xiaodong.Time-series segmentation based on fuzzy clustering algorithm and information granules[J].Fuzzy Systems and Mathematics,2015,29(1):175-182.(in Chinese)王立柱,刘晓东.基于信息颗粒和模糊聚类的时间序列分割[J].模糊系统与数学,2015,29(1):175-182.
[4] BAO Jiayong,ZHAO Yuexu.Sea surface temperature time series segmentation based on Floyd algorithm[J].Application of Statistics and Management,2019,38(8):326-333.(in Chinese)鲍家勇,赵月旭.基于Floyd算法的海温时间序列分割[J].数理统计与管理,2019,38(8):326-333.
[5] KEOGH E,CHU S,HART D,et al.An online algorithm for segmenting time series[C]//Proceedings of IEEE International Conference on Data Mining.Washington D.C.,USA:IEEE Press,2001:289-296.
[6] WANG Peng,WANG Haixun,WANG Wei.Finding semantics in time series[C]//Proceedings of ACM SIGMOD International Conference on Management of Data.New York,USA:ACM Press,2011:385-396.
[7] FORNEY G D.The Viterbi algorithm[J].Proceedings of the IEEE,1973,61(3):268-278.
[8] MATSUBARA Y,SAKURAI Y,FALOUTSOS C.AutoPlait:automatic mining of co-evolving time sequences[C]//Proceedings of CVPR'14.New York,USA:ACM Press,2014:193-204.
[9] GHARGHABI S,DING Y,YEH C C M,et al.Matrix profile VIII:domain agnostic online semantic segmentation at superhuman performance levels[C]//Proceedings of IEEE International Conference on Data Mining.Washington D.C.,USA:IEEE Press,2017:117-126.
[10] YEH C C M,ZHU Y,ULANOVA L,et al.Matrix profile I:all pairs similarity joins for time series:a unifying view that includes motifs,discords and shapelets[C]//Proceedings of International Conference on Data Mining.Washington D.C.,USA:IEEE Press,2016:1-5.
[11] DING H,TRAJCEVSKI G,SCHEUERMANN P,et al.Querying and mining of time series data:experimental comparison of representations and distance measures[J].Proceedings of the VLDB Endowment,2008,1(2):1542-1552.
[12] XI X,KEOGH E,SHELTON C,et al.Fast time series classification using numerosity reduction[C]//Proceedings of IEEE International Conference on Machine Learning.Washington D.C.,USA:IEEE Press,2006:1-40.
[13] SAKOE H,CHIBA S.Dynamic programming algorithm optimization for spoken word recognition[J].IEEE Transactions on Acoustics,Speech,and Signal Processing,1978,26(1):43-49.
[14] NGUYEN T,SEVERIN G G I.Time series classification by sequence learning in all-subsequence space[C]//Proceedings of the 33rd International Conference on Data Engineering.Washington D.C.,USA:IEEE Press,2017:1-10.
[15] SENIN P,MALINCHIK S.SAX-VSM:interpretable time series classification using sax and vector space model[C]//Proceedings of International Conference on Data Mining.Washington D.C.,USA:IEEE Press,2013:1-10.
[16] LIN J,KEOGH E,WEI L,et al.Experiencing SAX:a novel symbolic representation of time series[J].Data Mining and Knowledge Discovery,2007,15:107-144.
[17] CHEN Qiuxia,CHEN Lei,LIAN Xiang,et al.Indexable PLA for efficient similarity search[C]//Proceedings of the 33rd International Conference on Very Large Data Bases.New,York,USA:ACM Press,2007:435-446.
[18] REISS A,STRICKER D.Towards global aerobic activity monitoring[C]//Proceedings of PETRA'11.New York,USA:ACM Press,2011:1-8.
[19] REISS A,WEBER M,STRICKER D.Exploring and extending the boundaries of physical activity recognition[C]//Proceedings of IEEE International Conference on Systems.Washington D.C.,USA:IEEE Press,2011:1-10.
[20] MATEI Z,CHOWDHURY M,FRANKLIN M J,et al.Spark:cluster computing with working sets[C]//Proceedings of the 2nd USENIX Conference on Hot Topics in Cloud Computing.Boston,USA:USENIX,2010:10-11.

选择文件类型/文献管理软件名称

选择包含的内容