文章快速检索 高级检索

Dynamic time warping based on piecewise aggregate approximation and data derivatives
LI Hailin , LIANG Ye
Department of Information Management, Huaqiao University, Quanzhou 362021, China
Abstract: Dynamic time warping (DTW) is often used to measure the similarity of time series data; however, it has efficiency and quality limitations. In this study, a novel DTW method combining piecewise aggregate approximation (PAA) and derivatives is proposed to measure the similarity of time series. The dimensionality of the time series data was effectively reduced by PAA, and the feature sequence was transformed into new sequences by combining the numerical derivatives after the dimensionality reduction. Furthermore, the DTW design corresponded to the similarity measurement method of the feature sequence. The experimental results demonstrate that the proposed method is superior because it has better measurement quality, obtains a better classification effect in time series data mining, and has high efficiency in lower dimensional spaces.
Key words: dynamic time warping     time series     piecewise aggregate approximation     numerical derivative     similarity measure     classification     dimensionality reduction     feature representation

1 相关理论基础 1.1 分段聚合近似(PAA)

 ${q_i} = {1 \over k}\sum\nolimits_{j = k*\left( {i - 1} \right) + 1}^{k*i} {{s_i}} , 1 \le i \le m$ (1)

 图 1 基于PAA的时间序列数据降维和特征表示Fig. 1 Dimensionality reduction and feature representation of time series based on PAA

1.2 动态时间弯曲

 ${\rm{DTW}}\left( {S,Q} \right) = \mathop {\min }\limits_W \left( {\sum\limits_{k = 1}^K {{w_k}} } \right)$ (2)

1)边界性：w1=(1,1)，wk=(n,m);

2)连续性：wk=(a,b)，wK-1=(a′,b′)，则a-a′≤1，b-b′≤1;

3)单调性：wk=(a,b)，wK-1=(a′,b′)，则a-a′≥0，b-b′≥0;

 $\gamma \left( {i,j} \right) = d\left( {i,j} \right) + \min \left\{ \matrix{ \gamma \left( {i - 1,j - 1} \right) \hfill \cr \gamma \left( {i - 1,j} \right) \hfill \cr \gamma \left( {i,j - 1} \right) \hfill \cr} \right.$ (3)

 图 2 动态时间弯曲及其最优路径Fig. 2 Dynamic time warping and the best path

DTW在很多领域的应用中都有着很好的效果，然而较高的时间复杂度成为了该方法的瓶颈问题。目前也有部分学者对其进行了改进，使其具有较好的度量效率。另外，由于DTW有时也存在过度“变态”弯曲的状况，即一条时间序列的一个值对应着另一条序列的较长子序列，进而造成计算结果不精确的问题。针对该问题，Keogh和Pazzani提出了导数动态时间弯曲(DDTW)，有效地克服了DTW对时间轴的过度弯曲时造成的影响。

DDTW与DTW两种方法基本算法相似，DTW中距离矩阵元素(i,j)的距离值为 d(i,j)=(si-qj)2；DDTW距离矩阵元素的距离值为对应导数之间的距离，即d(i,j)=(si′-qj′)2，且数值导数si

 $s{'_i} = {{\left( {{s_i} - {s_{i - 1}}} \right) + \left( {{s_{i + 1}} - {s_{i - 1}}} \right)/2} \over 2}$ (4)

2 近似导数动态时间弯曲方法

 ${D_{{\rm{PADD}}}}\left( {S,Q} \right) = \alpha {\rm{DTW}}\left( {\bar S,\bar Q} \right) + \beta {\rm{DTW}}\left( {S',Q'} \right)$ (5)

 $\left\{ \matrix{ \alpha = {\cos ^2}\theta \hfill \cr \beta = {\sin ^2}\theta \hfill \cr} \right., \theta \subset \left[ {0,{\pi \over 2}} \right]$ (6)

 图 3 参数α、β选取原理Fig. 3 The principle of selecting parametersαandβ

1)分别对时间序列进行平均分段，每个子序列长度分别为ks=n/wskq=m/wq

2)根据PAA思想，对每个子序列进行均值表示，获得PAA序列S=(s1,s2,…,sws)和Q=(q1,q2,…,qwq)，其中两组特征序列的元素分别为${{\bar s}_i} = {1 \over {{k_s}}}\sum\limits_{j = {k_s}\left( {i - 1} \right) + 1}^{i{k_s}} {{s_j}}$和${{\bar q}_i} = {1 \over {{k_q}}}\sum\limits_{j = {k_s}\left( {i - 1} \right) + 1}^{i{k_q}} {{q_j}}$。

3)利用式(4)分别对PAA序列进行数据导数求解，得到基于导数的特征序列S′=(s1,s2,…,sws-2)和Q′=(q1,q2,…,qwq-2)。

4)利用DTW分别对上述两种特征序列进行度量距离，并实现线性组合，即DPADD(S,Q)=αDTW(S,Q)+βDTW(S′,Q′)。

3 数值实验

3.1 分类实验

 图 4 不同w下的最优参数θFig. 4 The best parameter θ for different w

 Datasets NO.C S.tr S.Tst length Beef 5 30 30 470 CBF 4 30 900 128 Coffee 2 28 28 286 D.S.Z. 4 16 306 345 ECG200 2 100 100 96 E.F.D. 2 23 861 136 Face Four 4 24 88 350 Fish 7 175 175 463 Gun Point 2 50 150 150 I.P.D. 2 67 1 029 24 Lighting7 7 70 73 319 M. I. 10 381 760 99 M.S. 2 20 1 252 84 Olive Oil 4 30 30 570 OSU Leaf 6 200 242 427 S.A.R.S. 2 20 601 70 S.A.R.S II 2 27 953 65 Symbols 6 25 995 398 S.C. 6 300 300 60 Trace 4 23 1 139 82 注：表头NO.C、S.Tr、S.Tst、Length分别表示类别个数、训练集个数、测试集个数、序列长度。数据集名D.S.Z.、E.F.D.、I.P.D.、M.I.、M.S.、S.A.R.S.、S.A.R.S II、S.C.分别表示Diatom Size Reduction、ECG Five Days、Italy Power Demand、Medical Images、Mote Strain、Sony AIBO Robot Surface、Sony AIBO Robot Surface II、Synthetic Control.

 % Datasets DTW DDTW PADD(avg) PADD(min) Beef 50.00 30.00 32.33 23.33(2) CBF 0.33 27.11 1.14 0.00(7) Coffee 17.86 14.29 2.86 0.00(3,5,10) D.S.Z. 3.27 6.21 5.49 3.27(5,10) ECG200 23.00 19.00 12.90 9.00(2) E.F.D. 23.23 35.08 26.82 17.65(1) Face Four 17.05 29.55 20.91 15.91(5,6,7) fish 16.57 10.29 12.41 10.86(6) Gun-Point 9.33 1.33 5.40 2.67(5,7) I.P.D. 4.96 8.75 6.81 4.28(6,8) Lighting7 27.40 41.09 28.63 23.29(1) M.I. 26.32 32.24 29.89 26.45(5) M.S. 16.53 28.04 16.53 12.70(8) Olive Oil 13.33 16.67 14.00 13.33(2~9) OSU Leaf 40.91 7.02 27.89 19.42(2,5) S.A.R.S. 27.45 25.46 28.40 20.13(9) S.A.R.S II 16.98 16.37 21.49 16.26(9) Symbols 5.03 2.51 4.31 3.62(2,3) S.C. 0.67 56.33 6.33 0.67(10) Trace 0.00 1.00 2.90 0.00(5,10) MEAN 17.01 20.42 15.37 11.14 SD 13.42 14.74 10.78 8.89

 图 5 分类错误率和时间序列分段聚合长度的关系Fig. 5 The relationship of classification and the length of time series piecewise aggregation

 图 6 实验数据集序列示例Fig. 6 The example of datasets

 图 7 分类错误率的比较Fig. 7 Comparison of classification error rates

3.2 时间效率分析

 图 8 3种方法的时间效率Fig. 8 Time efficiency of the three methods

4 结束语

 [1] 韩敏, 许美玲, 王新迎. 多元时间序列的子空间回声状态网络预测模型[J]. 计算机学报, 2014, 37(11): 2268-2275. HAN Min, XU Meiling, WANG Xinying. A multivariate time series prediction model based on subspace echo state network[J]. Chinese journal of computers, 2014, 37(11): 2268-2275. [2] MARSZA EK A, BURCZY SKI T. Modeling and forecasting financial time series with ordered fuzzy candlesticks[J]. Information sciences, 2014, 273: 144-155. [3] ZAMORA M, LAMBERT A, MONTERO G. Effect of some meteorological phenomena on the wind potential of Baja California[J]. Energy procedia, 2014, 57: 1327-1336. [4] GRAVIO G D, MANCINI M, PATRIARCA R, et al. Overall safety performance of air traffic management system: forecasting and monitoring[J]. Safety science, 2015, 72: 351-362. [5] 李海林, 郭韧 万校基. 基于特征矩阵的多元时间序列最小距离度量方法[J]. 智能系统学报, 2015, 10(3): 442-447. LI Hailin, GUO Ren, WAN Xiaoji. A minimum distance measurement method for multivariate time series based on the feature matrix[J]. CAAI transactions on intelligent systems, 2015, 10(3): 442-447. [6] 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. [7] IZAKIAN H, PEDRYCZ W, JAMAL I. Fuzzy clustering of time series data using dynamic time warping distance[J]. Engineering applications of artificial intelligence, 2015, 39: 235-244. [8] ZHANG Zheng, TANG Ping, DUAN Rubing. Dynamic time warping under pointwise shape context[J]. Information sciences, 2015, 315: 88-101. [9] 李正欣, 张凤鸣, 李克武. 基于DTW的多元时间序列模式匹配方法[J]. 模式识别与人工智能, 2011, 24(3): 425-430. LI Zhengxin, ZHANG Fengming, LI Kewu. DTW based pattern matching method for multivariate time series[J]. Pattern recognition and artificial intelligence, 2011, 24(3): 425-430. [10] LI Hailin. Asynchronism-based principal component analysis for time series data mining[J]. Expert systems with applications, 2014, 41(6): 2842-2850. [11] KEOGH E, PAZZANI M J. Derivative dynamic time warping[C]//Proceedings of the 1st SIAM International Conference on Data Mining. Chicago, IL, USA, 2001: 1-11. [12] JEONG Y S, JAYARAMAN R. Support vector-based algorithms with weighted dynamic time warping kernel function for time series classification[J]. Knowledge-based systems, 2015, 75: 184-191. [13] GÓRECKI T, ŁUCZAK M. Using derivatives in time series classification[J]. Data mining and knowledge discovery, 2013, 26(2): 310-331. [14] 李海林, 杨丽彬. 时间序列数据降维和特征表示方法[J]. 控制与决策, 2013, 28(11): 1718-1722. LI Hailin, YANG Libin. Method of dimensionality reduction and feature representation for time series[J]. Control and decision, 2013, 28(11): 1718-1722. [15] BANKÓ Z, ABONYI J. Mixed dissimilarity measure for piecewise linear approximation based time series applications[J]. Expert systems with applications, 2015, 42(21): 7664-7675. [16] AGRAWAL R, FALOUTSOS C, SWAMI A. Efficient similarity search in sequence databases[C]//Proceedings of the 4th International Conference on Foundations of Data Organization and Algorithms. Berlin Heidelberg: Springer, 1993, 730: 69-84. [17] WANG Hongfa. Clustering of hydrological time series based on discrete wavelet transform[J]. Physics procedia, 2012, 25: 1966-1972. [18] WENG Xiaoqing, SHEN Junyi. Classification of multivariate time series using two-dimensional singular value decomposition[J]. Knowledge-based systems, 2008, 21(7): 535-539. [19] LIN J, KEOGH E, WEI Li, et al. Experiencing SAX: a novel symbolic representation of time series[J]. Data mining and knowledge discovery, 2008, 15(2): 107-144. [20] KEOGH E, XI X, WEI L, et al. The UCR time series classification/clustering homepage[EB/OL]. 2007. http://www.cs.ucr.edu/-eamonn/time_series_data/.
DOI: 10.11992/tis.201507064

0

#### 文章信息

LI Hailin, LIANG Ye

Dynamic time warping based on piecewise aggregate approximation and data derivatives

CAAI Transactions on Intelligent Systems, 2016, 11(02): 249-256.
DOI: 10.11992/tis.201507064