基于动态规划求解时间序列DTW中心

计算机科学 ›› 2015, Vol. 42 ›› Issue (12): 278-282.

基于动态规划求解时间序列DTW中心

孙焘,夏斐,刘洪波

大连理工大学创新实验学院大连116024,大连理工大学创新实验学院大连116024,大连海事大学计算机学院大连116024

出版日期:2018-11-14 发布日期:2018-11-14
基金资助:
本文受国家自然科学基金(61472058)资助

Calculating DTW Center of Time Series Using Dynamic Planning

SUN Tao, XIA Fei and LIU Hong-bo

Online:2018-11-14 Published:2018-11-14

摘要/Abstract

摘要： 中心时间序列表明了一个时间序列集合中的公共特征,是时间序列聚类的重要手段。提出了一个利用动态规划求解两条时间序列DTW中心的方法,即以最小化中心序列到两条样本序列的DTW距离平方和为目标,递归求解最优解。在此基础上,给出了基于中心与样本匹配度的剪枝方法,降低了时间复杂度。并在理论上证明了该方法可以获得最优解。实验结果显示,相比于DBA算法,该算法能够获得更小的DTW距离平方和,并且有更好的鲁棒性。

关键词: 中心时间序列,DTW,动态规划,匹配度剪枝

Abstract: The central time series plays an important role in time series clustering,which indicates the common features of time series.We proposed dynamic planning approach called DPSSD to calculate central time series of two time series.The approach is recursive based on the minimizing sum of squares of DTW (SSD) distance from central series to two sample series.Degree-pruning was also introduced to decrease the algorithm time complexity.The proposed algorithm was proved theoretically.It can achieve the optimal solution.In the experiments,the results illustrate that our approaches have much better performance and robustness than DBA,which is measured by SSD.

Key words: Central time series,DTW,Dynamic planning,Degree-pruning

孙焘,夏斐,刘洪波. 基于动态规划求解时间序列DTW中心[J]. 计算机科学, 2015, 42(12): 278-282. https://doi.org/

SUN Tao, XIA Fei and LIU Hong-bo. Calculating DTW Center of Time Series Using Dynamic Planning[J]. Computer Science, 2015, 42(12): 278-282. https://doi.org/

参考文献

[1] Anami B S,Pagi V B.Acoustic signal-based approach for fault detection in motorcycles using chaincode of the pseudospectrum and dynamic time warping classifier[J].IET Intelligent Transport Systems,2014,8(1):21-27
[2] Trajcevski G,Gunopulos D,Aggarwal C C.Time-seriesdata clustering[M].Aggarwal C C,Reddy C K,eds.Data Clustering:Algorithms and Applications,CRC Press,2013:357-375
[3] Hu B,Rakthanmanon T,Hao Y,et al.Using the minimum description length to discover the intrinsic cardinality and dimensionality of time series[J].Data Mining and Knowledge Disco-very, 2015,29(2):358-399
[4] Hautamaki V,Nykanen P,Franti P.Time-series clustering byapproximate prototypes[C]∥Proceedings of International Conference on Pattern Recognition.IEEE,2008:1-4
[5] Berndt D J,Clifford J.Using dynamic time warping to find patterns in time series[J].KDD Workshop,ser.Seattle,WA,1994,10(16):359-370
[6] 谢福鼎,李迎,孙岩,等.一种基于关键点的时间序列聚类算法[J].计算机科学,2012,39(3):157-159 Xie F D,Li Y,Sun Y,et al.Cluster Algorithm for Time Series Based on Key Points[J].Computer Science,2012,39(3):157-159
[7] 郭崇慧,苏木亚.基于独立成分分析的时间序列谱聚类方法[J].系统工程理论与实践,2011,31(10):1921-1931 Guo Chong-hui,Su Mu-ya.Spectral clustering method based on independent component analysis for time series[J].Systems Engineering Theory & Practice,2011,31(10):1921-1931
[8] Gupta L,Molfese D,Tammana R,et al.Nonlinear alignment and averaging for estimating the evoked potential[J].IEEE Transactions on Biomedical Engineering,1996,43(4):348-356
[9] Salvador S,Chan P.Toward accurate dynamic time warping in linear time and space[J].Intelligent Data Analysis,2007,11(5):561-580
[10] Niennattrakul V,Ratanamahatana C.Shape averaging undertime warping[C]∥Proceedings of International Conference on Electrical Engineering/Electronics,Computer,Telecommunications and Information Technology.IEEE,2009:626-629
[11] Petitjean F,Ketterlin A,Ganarski P.A global averaging me-thod for dynamic time warping,with applications to clustering[J].Pattern Recognition,2011,44(3):678-693
[12] Keogh E,Folias T.The UCR time series data mining archive.http://www.cs.ucr.edu/ eamonn/time series data

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed