近年来，时间序列成为了数据挖掘研究领域中的热点，其研究成果已被广泛地应用在工业、金融、气象、航天、生物医学等各种领域^{[1, 2, 3, 4, 5]}。然而，相似性度量方法成为时间序列数据挖掘领域中基础而又极其关键的工作之一，很多挖掘任务的结果易受其相似性度量质量和效率的影响。目前，动态时间弯曲(dynamic time warping,DTW)是一种鲁棒性较强的方法之一，其最早应用于语音识别^[6]，如今已被广泛应用于时间序列相似性的度量^{[7, 8, 9]}。欧氏距离虽能快速度量时间序列之间的相似性，但其限于相同时间点上的数据匹配，而且对异常数据点较为敏感。DTW不仅可以弯曲度量不等长时间序列之间的相似性，其度量质量能较好地反映数据之间的异步关系^[10]。然而，由于DTW需要在代价矩阵中计算最优弯曲路径，使其具有较高的时间复杂度或较好的度量精度^{[11, 12, 13]}。

时间序列降维表示是通过某种方法将原始序列进行转换或者特征提取，以达到将原始时间序列在低维度表示的目的。由于直接使用和计算原始时间序列可能需要付出较大的代价，如消耗较多存储空间，运行效率低等问题，加上原始时间序列包含很多“噪音点”，容易导致相似性度量结果不准确。因此，为简化数据模型和算法的复杂性，提高数据挖掘技术的性能，有必要对原始时间序列进行降维处理，达到效率和准确性的平衡。目前，针对时间序列降维的方法已有很多且较为成熟，如分段聚合近似(piecewise aggregate approximation,PAA)^[14]，该方法通过将时间序列进行平均分段，并以分段均值反映分段信息，最终达到数据降维的目的；分段线性近似(piecewise liner approximation,PLA)^[15]利用线性模型对时间序列进行分割，根据不同的分割策略可以得到不同的时间序列降维效果；基于域变换的离散傅里叶变换(discrete fourier transform,DFT)^[16]和离散小波变换(discrete wavelet transform,DWT)^[17]，利用变换后的系数对时间序列进行特征表示；奇异值分解(singular value decomposition,SVD)^[18]，利用数值计算将高维数据转换到低维空间，不仅应用在时间序列数据降维及索引，而且也被广泛地应用于模式识别、图像压缩等等。由于降维方法对整个研究过程起着十分关键的作用，不仅要求算法能够尽可能简单快速，以降低时间消耗，也要尽量充分反映时间序列的信息。因此研究过程中应选择合适的降维方法来解决问题。

鉴于传统DTW方法在度量时间序列相似性时具有计算时间效率较低和缺少考虑序列的形态(即凹凸性)等问题，并且从使用较为简单的数据降维方法以简化模型的角度出发，本文提出通过利用分段聚合近似(PAA)方法对时间序列进行数据降维，获得保持原始序列主要特征的数据序列，再构造基于数据点的一阶导数的新特征序列，结合动态时间弯曲提出一种新的距离度量方法，即近似导数动态时间弯曲方法。数值实验分类结果和效率分析表明，该方法能从形态视角出发，较好地从数据集中找出相似序列，提高数据挖掘领域中分类算法的质量，具有一定的优越性。

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

分段聚合近似是一种有效的数据降维方法，其在减小数据存储和提高计算效率方面起到了很大的作用。通过对长度为n的序列S=(s₁,s₂,…,s_n)转化为另一条长度为m的序列Q=(q₁,q₂,…,q_m)，实现时间序列的数据降维和特征表示，其中n>m，且令k=n/m。新序列中任意元素q_i满足：

对序列S进行分段后求出每段的均值，每段均值形成序列Q，进而达到序列S数据降维的目的。如图 1，子图(a)显示了长度为60的时间序列S通过PAA被平均分成10段，每段均值代表相应片段的特征；子图(b)显示由10个均值组成的新序列Q。

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

图选项

分段聚合近似方法通过均值来表示序列片段的特征，容易忽略数据的局部形态变化情况。然而，在实际运用中，时间序列的整体形态通常是关注和研究的重点。PAA得到的序列特征不仅能够很好地反映较长时间序列数据形态的整体变化趋势，而且还能对时间序列数据进行数据降维，起到提高相关数据挖掘算法效率的作用。

1.2 动态时间弯曲

动态时间弯曲最初被应用于语音识别中，常被运用到比较2条时间序列的相似性。针对2条时间序列S=(s₁,s₂,…,s_n)和Q=(q₁,q₂,…,q_m)，对任意两点之间的距离构建一个n×m的距离矩阵D，其中d(i,j)表示时间序列数据点s_i和q_j之间的距离，即d(i,j)=(s_i-q_j)²。DTW的基本思想就是从距离矩阵中寻找一条使得2条序列之间的累计距离最小的路径，其最小累积距离值为

弯曲路径是一条具有连续K个距离矩阵元素的集合W=(w₁,w₂,…,w_K)，第k个元素为w_k=(i,j)_k且max(n,m)≤K≤n+m-1。与此同时，弯曲路径通常要遵循着3个条件：

1)边界性：w₁=(1,1)，w_k=(n,m);

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

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

最优弯曲路径的求解可以通过动态规划来找出最小累积距离，即

式(3)说明当前元素的累积距离(i,j)是当前元素距离值与邻近3个元素累积距离的最小值之和，且γ(n,m)表示DTW度量时间序列S和Q的最小距离 DTW(S,Q)=γ(n,m)。

如图 2(a)所示，动态时间弯曲方法可以很好地匹配不同时间点但具有相似形态的序列特征，使得时间序列的相似性特征能够较好地得到体现。另外，通过累积矩阵的构建可以获取其最优弯曲路径和最小度量距离，如图 2(b)所示。

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

图选项

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

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

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

若直接使用动态时间弯曲方法对时间序列进行相似性度量，则时间消耗太大，并且也会造成时间过度弯曲等问题，不利于大规模的长度较长的时间序列数据挖掘。为此，在使用动态时间弯曲度量相似性之前，通常先对时间序列数据进行数据降维，不仅可以得到反映时间序列大部分信息的低维特征表示，而且还能近似表示原始时间序列的整体性信息。除此之外，在分类过程中，针对低频时间序列数据缺少具体局部信息的状况，序列被归为哪一类通常可能取决于其整体形状，而不是局限于严格的数值比较。因此，相似性度量的结果不仅需要充分考虑序列的具体数值，也要考虑序列整体形态(凹凸性)。

传统研究方法是对时间序列进行数据降维，然后使用传统距离公式直接进行相似性度量。由于数据降维会损耗时间序列的部分信息，实验效果也就相当于以准确性来换取时间效率。鉴于时间序列具体数据值的重要性、形态的特殊性、度量准确性以及高运行效率的必要性，结合分段聚合近似以及数值导数，提出一种基于分段聚合近似和数值导数的动态时间弯曲方法，称为分段聚合导数距离(piecewise approximation derivative distance,PADD)。该方法主要综合考虑时间序列的具体数值信息和形态特征，以获得更好的度量效果，提高运行效率，减少异常点对度量的影响为目标，同时从时间序列的整体数据匹配和形态的凸凹性出发，更为完善地度量时间序列异步相关性。

时间序列S=(s₁,s₂,…,s_n)和Q=(q₁,q₂,…,q_m)，通过分段聚合近似方法对它们进行数据降维并进行整体数据的特征表示，即S=PAA(S,w_s)和Q=PAA(Q,w_q)，其中w_s和w_q为降维后维度，也是分段数目。另外，为了反映原始时间序列整体形态的特征，利用数据导数来反映PAA对原始时间序列降维后的序列进行整体形态特征描述。利用式(4)对S和Q进行数据导数计算，以反映原始时间序列的整体形态特征，即S′和Q′。最后，利用动态时间弯曲方法分别对(S,Q)和(S′,Q′)进行距离度量，并综合两者的加权平均作为新方法的距离度量函数，即

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

图选项

结合上述思想，本文提出的分段聚合导数距离(PADD)算法步骤如下：

输入 时间序列S=(s₁,s₂,…,s_n)和Q=(q₁,q₂,…,q_m)，分段数目w_s和w_q以及参数θ;

输出 度量距离D_PADD(S,Q)。

1)分别对时间序列进行平均分段，每个子序列长度分别为k_s=n/w_s和k_q=m/w_q。

2)根据PAA思想，对每个子序列进行均值表示，获得PAA序列S=(s₁,s₂,…,s_ws)和Q=(q₁,q₂,…,q_wq)，其中两组特征序列的元素分别为${{\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′=(s′₁,s′₂,…,s′_ws-2)和Q′=(q′₁,q′₂,…,q′_wq-2)。

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

在上述算法中，1)实现了时间序列的分段，使用等划分的方法实现数据划分并获得相应的子序列片段;2)中方法对子序列段的均值特征表示，而且大量研究结果表明^[19]，对于高维时间序列来说，PAA方法可以保留足够的数据信息来反映原序列的波动形态;3)实现均值特征序列的导数表示，以便更好地反映特征序列的形态变化情况。最后，利用式(6)同时从均值特征序列和导数特征序列来反映原始时间序列的数据信息，以确保距离度量函数能够较好地通过特征序列之间的数值关系来反映原始时间序列之间的数值和形态变化关系。

另外，从算法的整个描述过程，容易分析得到新方法的计算时间效率。长度为n的时间序列进行分段聚合近似时，其时间复杂度为O(n)，计算一阶导数的时间复杂度也为O(n)。另外，对PAA特征序列和导数序列进行DTW距离度量所需要的时间复杂度分别为O(w_sw_q)和O((w_s-2)(w_q-2))，故PADD整个算法过程的时间复杂度近似为O(2w_sw_q+4n)。由于分段数目w_s和w_q通常远小于原始时间序列的长度，即w_s$ \ll $n和w_q$ \ll $n，故PADD的时间复杂度O(2w_sw_q+4n)要低于与传统DTW和DDTW的时间复杂度O(n²)。特别地，数值实验的分类结果和时间计算效率分析表明，PADD能够较好地度量时间序列的相似性，反映数据形态之间的变化关系，进而提高时间序列数据挖掘算法的分类结果，还能在低维特征空间下获得较高的时间效率。

3 数值实验

为了更好地理解和检验PADD方法的性能，实验通过对时间序列数据集进行分类实验，与传统DTW和DDTW方法进行比较，验证新方法在不同时间序列数据集中的距离度量质量和时间计算效率。

3.1 分类实验

实验一共进行两个阶段，1)训练模型，使用“留一法”(leave-one-out)求出合适的参数θ构建度量距离;2)测试模型，得到分类效果。由于时间序列取值范围差距较大，度量相似性结果可能会出现很大偏差，因此有必要对所有时间序列数据进行归一化处理，消除量纲。

使用训练集训练模型过程中，给定时间序列分段数目w以及范围为[0,π/2]且步长为0.01的θ，利用分段聚合近似以及一阶求导分别得到新的特征序列。训练阶段结合“枚举法”测试在w情况下每个θ的分类情况，选择错误率最小的θ作为该w情况下的最优参数。一旦求得参数立即构建度量距离公式(5)，进入2)利用最近邻(1-NN)分类方法检测该距离公式分类效果。

图 4给出了数据集ECG在不同w取值下的最佳参数θ。根据式(5)与式(6)易知，θ取值越大，时间序列相似性度量形态匹配所占比重越大；反之，则形态匹配的比重就越小。图 4也说明了时间序列数据集在大部分情况下更倾向于形态匹配而不是具体数值上的比较。

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

图选项

本次实验使用Keogh教授提供的数据集^[20]，并随机抽取20个数据集进行分类实验。如表 1所示，包含了各个数据集的基本详细信息，包括数据集名称、类别个数、训练集个数、测试集个数、时间序列长度。表 2包含了DTW、DDTW、PADD的平均错误率，并且给出了PADD的最小错误率，其中括号表示能够取得PADD的最小分类错误率的w，例如当CBF数据被降维到原始序列长度的70%时，可以取得最小错误率0。

从实验结果来看，PADD的平均分类效果与DTW和DDTW相比有着较大的优势，并且从最小分类错误率的均值及标准差上来看也取得了不错的效果，进而验证了PADD在时间序列数据挖掘中距离度量的有效性。实验结果反映了时间序列分段聚合后的特征序列长度大多数为原始序列长度的50%~100%，即w大多数取值为5~10时，PADD将会取到比较好的效果。这也说明在进行序列转换过程中，将时间序列的整体信息以及具体细节尽量完整保存下来会取得更好的效果。

为了更为清楚地剖析分类结果在不同参数下的情况，给出了Sony AIBO Robot Surface和ECG这两个数据集的分类情况，如图 5所示。从图 5 中可以看出，分类错误率呈高低波动状态。对于某些数据集如Sony AIBO Robot Surface来说，在不同w情况下并非所有的PADD错误率都是最小的，但是在最小错误率上却能够优于DTW和DDTW的错误率。然而，在有些数据集如ECG，不管w取何值，新方法的分类错误率都是低于另外两者的错误率。

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

图选项

从图 5中发现，不同数据集呈现出来的性能不一样。由于分段聚合近似采用的是均值作为替代值，这并非最佳的降维方法，因此，若数据集中的序列数据波动较多、振幅较大，会对降维效果造成一定的影响。如图 6所示。

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

图选项

图 6分别给出的是训练集Sony AIBO Robot Surface和ECG的3条时间序列，可以观察到子图(a) 的序列在整体波动上比子图(b)的多。因此，影响了序列降维的效果，给后续的相似性度量造成了一定的影响。由于数据集的特性会给本方法造成一定的影响，因此，本方法适合波动较为平缓的数据集，并会取得较好的效果。

图 7描述的是PADD的平均分类错误率以及最小分类错误率与DTW、DDTW的错误率的比较，为了便于直观比较，数值均经过归一化后取值范围为[0,0.5]，数值偏向方表示对应方法的错误率较大。

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

图选项

图 7中子图(a)、(b)分别描述PADD的平均错误率与DTW、DDTW的错误率比较，子图(c)、(d)分别描述PADD最小错误率与DTW、DDTW错误率比较。结果分析表明，不管从平均错误率还是最小错误率角度来比较，PADD错误率所对应的坐标纵轴值相对较小，使其偏向于DTW和DDTW所代表的横轴值较大，大多散点都偏向于DTW和DDTW，故说明PADD具有较小的分类错误率，进行验证了本文新方法在时间序列度量中的有效性和优越性。

3.2 时间效率分析

本实验使用“留一法”(leave-one-out)求解参数，参数确定后立即构建度量距离公式。特征序列长度越长，计算所要消耗的时间越大，且成数量级增长。如图 8所示，描述了数据集Sony AIBO Robot Surface和ECG在不同w条件下PADD时间效率与DTW、DDTW的时间效率比较。

由于DDTW需要利用式(4)预先对时间序列数据进行求导，因此DDTW时间效率略高于DTW时间效率。另外，随着特征序列长度w的增长，PADD消耗的时间也随之增长。当分段数目w增长到一定程度时，PADD的计算时间消耗会大于传统DTW和DDTW方法。理论上结合时间复杂度的分析可知，PADD的时间复杂度近似为O(2w²+4n)，DTW和DDTW的时间复杂度为O(n²)，当且仅当w<$\sqrt {{{{{\left( {n - 2} \right)}^2} - 4} \over 2}} $时，PADD的时间效率要低于DTW和DDTW。因此，在分段比例超过约$\sqrt {{{{{\left( {n - 2} \right)}^2} - 4} \over 2}} /n = \sqrt {{{n - 2} \over 2}} $时，时间效率便开始降低。可以发现，n为任意值，该比例均约为70%，从图中也清楚地看到，DTW、DDTW、PADD三者在分段比例约为70%的地方相交。另外，在PADD过程中会涉及到一些辅助计算，故若大于某一特定降维之后的维度时，PADD将会消耗更多的计算时间。然而，如图 8所示，在数据降维后的低维空间中，PADD可以取得较好的时间效率，具有一定的计算性能优势。

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

图选项

4 结束语

针对动态弯曲方法对时间序列数据相似性度量质量和效率的局限性，以及从简化模型的角度考虑，本文提出一种基于分段聚合近似和数值导数的动态时间弯曲方法，结合分段聚合近似算法以及数值求导将时间序列进行转换，得到符合要求的特征序列，构建新的距离公式对新的特征序列进行相似性度量。数值实验结果表明，与传统的动态时间弯曲度量方法相比，在分类效果和计算性能上具有一定的优势。通过实验发现，针对波动较为平缓的数据进行挖掘，将会取得更好的效果。特别地，在数据压缩量较大的低维空间下，新方法在保证分类质量的前提下，能够获得较好的时间效率。另外，参数选择是一个至关重要的步骤，不同参数对实验结果具有一定的影响，将来需要对参数选择做进一步探讨和研究。