开放科学(资源服务)标志码(OSID)：

0 概述

时间序列是指按照采集时间先后顺序排列的观测数据，广泛存在于金融^[1-2]、道路交通^[3]、社交网络^[4-5]、工业电网^[6]等领域。随着信息技术的发展，时间序列数据量与日俱增，利用相应数据挖掘技术从海量时间序列中发现潜在知识和规律已成为当前数据挖掘的研究热点。时间序列相似性度量是衡量两条时间序列相似程度的度量方法，是时间序列聚类和分类分析中不可缺少的步骤^[7]，度量方法性能直接影响时间序列数据挖掘的效果^[8]。

BERNDT等^[9]于1994年提出的动态时间规整(Dynamic Time Warping，DTW)是时间序列相似性度量中的常用方法。与传统相似性度量(如欧氏距离)相比，DTW对时间序列的相位偏移、振幅变化等情况具有更强的鲁棒性。然而，DTW算法存在“病态对齐”的缺陷，即在并不相似的特征之间进行对齐，使一条时间序列上的点匹配另一条时间序列上一大块区域的点^[10]。在这种不合理匹配的情况下，可能出现同类时间序列之间的距离值大于不同类时间序列之间的距离值，进而影响最终的度量效果。

为了抑制病态对齐现象，提高时间序列之间的相似性度量效果，ZHANG等^[11]提出限制对齐路径长度的动态时间规整(LDTW)算法从时间序列之间的对齐路径长度开始，通过给定对齐路径长度上限$ {L}_{\mathrm{U}\mathrm{B}} $来限制时间序列之间的对齐路径长度。相比其他改进算法(如权重DTW^[12-13]、窗口限制Sakoe-Chiba band^[14]、Itakura parallelogram^[15]、learned window^[16]、改进进步模式step pattern^{[15, 17]}等)从局部限制每个数据点所能匹配对应数据点的数量，LDTW算法在全局上限制对齐路径总体长度，保留局部对齐的灵活性，抑制“病态对齐”现象，在UCR公共数据集上的分类效果有更明显提升。但LDTW算法将原DTW算法中的二维累计代价矩阵扩张为三维矩阵，增大了时间复杂度，在多数数据集上进行分类实验的时间开销远大于原DTW算法以及相关衍生算法。

本文对LDTW算法进行改进，提出固定对齐路径长度的动态时间规整(FDTW)算法。通过分析LDTW算法所需要计算的累计代价矩阵元素数量、时间序列长度和对齐路径长度上限之间的关系，调整LDTW算法中控制对齐路径长度的策略，使得对齐路径长度由限制在某个范围内改为固定到某个数值上，从而降低累计代价矩阵元素的计算量，提高计算效率。

1 相关工作 1.1 DTW算法

DTW为了适应时间序列间的相位偏移和振幅变化，将时间序列数据点之间对齐方式由欧氏距离的“一对一”改为“一对多”。设X={x₁，x₂，…，x_R}和Y={y₁，y₂，…，y_C}是两条长度分别为R和C的时间序列。对齐路径$ \pi $用于描述X和Y之间数据点的对齐关系，它被定义为包含K个二元组集合，每个二元组包含两个分别来自时间序列X和Y的数据点下标。$ \pi $的表示如式(1)所示：

$ \pi =\left\{\left({\pi }_{1}^{X}, {\pi }_{1}^{Y}\right), \left({\pi }_{2}^{X}, {\pi }_{2}^{Y}\right), \cdots , \left({\pi }_{k}^{X}, {\pi }_{k}^{Y}\right), \cdots , \left({\pi }_{K}^{X}, {\pi }_{K}^{Y}\right)\right\} $

(1)

$ \pi $需遵循以下3个条件：1)边界性，即$ {\pi }_{1}^{X}={\pi }_{1}^{Y}=1 $，$ {\pi }_{K}^{X}=R $，$ {\pi }_{K}^{Y}=C $；2)单调性，即$ {\pi }_{k}^{X}\le {\pi }_{k+1}^{X} $，$ {\pi }_{k}^{Y}\le {\pi }_{k+1}^{Y} $；3)连续性，即$ {\pi }_{k+1}^{X}-{\pi }_{k}^{X}\le 1 $，$ {\pi }_{k+1}^{Y}-{\pi }_{k}^{Y}\le 1 $。

在以上条件约束下，X和Y之间所有对齐路径的集合记为$ {A}^{XY} $。DTW目标是最小化两条时序数据中所有对应数据点的局部距离值之和，并以之作为全局距离值，其定义如式(2)所示：

$ D\left(X, Y\right)=\underset{\mathrm{\pi }\in {A}^{XY}}{\mathrm{m}\mathrm{i}\mathrm{n}}\sum \limits_{(i, j)\in \mathrm{\pi }}d({x}_{i}, {y}_{j}) $

(2)

其中：$ d({x}_{i}, {y}_{j})=|{x}_{i}-{y}_{j}{|}^{2} $。

DTW算法采用动态规划思想利用递归公式将以上问题转换为对X和Y子序列问题的求解，如式(3)所示：

$ D\left({X}_{R}^{1}, {Y}_{C}^{1}\right)=d({x}_{R}, {y}_{C})+\mathrm{m}\mathrm{i}\mathrm{n}D\left({X}_{R-1}^{1}, {Y}_{C}^{1}\right)\cdot \\ D\left({X}_{R}^{1}, {Y}_{C-1}^{1}\right)D\left({X}_{R-1}^{1}, {Y}_{C-1}^{1}\right) $

(3)

由于子序列问题相互交叠，直接采用递归方式会产生大量的重复计算，因此DTW算法通过建立一个R×C累计代价矩阵M来存放子问题的解以避免重复计算。因此，需计算R×C个矩阵元素，DTW算法的时间复杂度为$ O(R\times C) $。

DTW算法为了使序列间的距离值最小，计算过程中可能出现“病态对齐”现象^[18]。“病态对齐”示意图如图 1所示。时间序列A与时间序列B为不同类别，而与时间序列C为同一类别，但DTW算法通过大规模的“一对多”对齐，在序列A和序列B并不具有相似性的局部数据点之间进行匹配，最终使得AB之间距离值大于AC之间的距离值，违背了同类序列之间度量值应更小的事实。图 1(a)的弯曲路径长度为54，图 1(b)的弯曲路径长度为51。“病态对齐”缺陷限制了DTW算法的度量效果。

1.2 LDTW算法

DTW算法在出现“病态对齐”现象的同时，对齐路径的长度K也会增大。因此，LDTW算法通过对对齐路径总长度K进行限制来抑制“病态对齐”现象。

给定时间序列X和Y，令min S、max S分别表示X和Y之间允许的最小对齐路径长度和最大对齐路径长度，即$ \mathrm{m}\mathrm{i}\mathrm{n}S=\mathrm{m}\mathrm{a}\mathrm{x}\left(R, C\right) $，$ \mathrm{m}\mathrm{a}\mathrm{x}S=R+C-1 $。X和Y之间允许长度相同的对齐路径并不唯一，令$ {A}_{l}^{XY} $为所有长度l的对齐路径集合；L_UB为给定的对齐路径长度上限，则时间序列X和Y之间的$ {L}_{\mathrm{D}} $距离值如式(4)所示：

$ {L}_{\mathrm{D}}(X, Y, {L}_{\mathrm{U}\mathrm{B}})=\underset{l\in [\mathrm{m}\mathrm{i}\mathrm{n}S, {L}_{\mathrm{U}\mathrm{B}}]}{\mathrm{m}\mathrm{i}\mathrm{n}}\underset{\pi \in {A}_{l}^{XY}}{\mathrm{m}\mathrm{i}\mathrm{n}}\sum \limits_{(i, j)\in \mathrm{\pi }}d({x}_{i}, {y}_{j}) $

(4)

LDTW算法采用动态规划方法将问题转换为求解X和Y的子序列问题，并建立R×C×L_UB的三维累计代价矩阵M，依次计算矩阵元素如式(5)所示：

$ \begin{array}{l}M\left[r\right]\left[c\right]\left[l\right]=d({x}_{r}, {y}_{c})+\mathrm{m}\mathrm{i}\mathrm{n}M[r-1][c-1][l-1]\cdot \\ M[r-1]\left[c\right][l-1]M\left[r\right][c-1][l-1]\end{array} $

(5)

其中：M[r][c][l]值为子序列$ {X}_{r}^{1} $和子序列$ {Y}_{c}^{1} $之间对齐路径长度l的最小距离值。由于不同长度的子序列之间可能产生的对齐路径长度范围不同，加上L_UB限制，并非所有矩阵M的元素都需要计算，因此LDTW算法按第三维优先顺序计算矩阵M，且在计算前先确定所有子序列间对齐路径长度的范围来避免不必要计算。

所有需要计算的矩阵元素计算完成后，元素M[R][C][min S]为min S长度的对齐路径对应的最小距离值；M[R][C][minS +1]为min S+1长度的对齐路径对应的最小距离值；M[R][C][L_UB]为L_UB长度的对齐路径所对应的最小距离值。LDTW算法从候选元素中选取最小值作为最终的度量值。该距离值所对应的对齐路径长度一定小于L_UB，达到了从总体上控制长度以减少“病态对齐”现象的目的。

LDTW算法引入对齐路径长度概念，将累计代价矩阵由原DTW算法的二维扩展到三维，算法的时间复杂度也由原DTW算法的O(R×C)增长为O(L_UB×R×C)，使得分类过程的时间开销大于原DTW及其衍生算法。

2 FDTW算法 2.1 算法原理

在LDTW算法中，当时间序列长度R为5，L_UB为9时计算的矩阵元素如图 2所示。从图 2可以看出，矩阵的第一、第二维度分别表示时间序列数据点下标，第三维度为对齐路径长度。根据式(5)可知，当前层元素值计算只与前一层中左方、上方和左上方的相邻元素值有关，与正下方的元素值无关，即矩阵元素$ M\left[r\right]\left[c\right]\left[l\right] $的计算与$ M\left[r\right]\left[c\right][l-1] $无关。矩阵元素$ M\left[{x}_{5}\right]\left[{y}_{5}\right]\left[9\right] $的计算无需元素$ M\left[{x}_{5}\right]\left[{y}_{5}\right]\left[8\right] $参与，而$ M\left[{x}_{5}\right]\left[{y}_{5}\right]\left[8\right] $的计算无需$ M\left[{x}_{5}\right]\left[{y}_{5}\right]\left[7\right] $参与。若只计算长度等于L_UB对齐路径对应的最佳距离值，相比计算出所有对齐路径长度小于$ {L}_{\mathrm{U}\mathrm{B}} $的最佳距离值所需要计算的累计代价矩阵元素数量更少，且仍保留通过限制长度以抑制“病态对齐”的原理。由于对齐路径长度被限定为阈值$ {L}_{\mathrm{U}\mathrm{B}} $，将这种方法称为固定对齐路径长度的DTW算法。

2.2 算法描述

FDTW算法的目标是从所有长度为给定值的对齐路径中找出使得对应距离值最小的对齐路径，并将该最小值作为距离值。令X和Y表示待度量的两条时间序列，F_L表示给定的对齐路径长度，则X和Y之间的F_D距离值如式(6)所示：

$ {F}_{\mathrm{D}}(X, Y, {F}_{\mathrm{S}})=\underset{\pi \in {A}_{FL}^{XY}}{\mathrm{m}\mathrm{i}\mathrm{n}}\sum\limits _{(i, j)\in \pi }d({x}_{i}, {y}_{j}) $

(6)

其中：$ {A}_{FL}^{XY} $表示序列X和Y之间所有长度为F_L的对齐路径的集合。

利用递归公式将式(6)转化为对子序列间距离值的求解，如式(7)所示：

$ F\left({X}_{R}^{1}, {Y}_{C}^{1}, {F}_{\mathrm{L}}\right)=d({x}_{R}, {y}_{C})+\mathrm{m}\mathrm{i}\mathrm{n}{F}_{\mathrm{D}}\left({X}_{R-1}^{1}, {Y}_{C}^{1}, {F}_{\mathrm{L}}-1\right)\cdot \\ {F}_{\mathrm{D}}\left({X}_{R}^{1}, {Y}_{C-1}^{1}, {F}_{\mathrm{L}}-1\right){F}_{\mathrm{D}}\left({X}_{R-1}^{1}, {Y}_{C-1}^{1}, {F}_{\mathrm{L}}-1\right) $

(7)

其中：$ {X}_{e}^{s} $为序列$ X $的起点为s终点为e的子序列。为方便后续描述，将子序列$ {X}_{R}^{e} $称为$ {X}_{e}^{s} $的互补子序列($ {X}_{e}^{s} $和$ {X}_{R}^{e} $互补组成整序列X)。

为避免对相同子问题进行重复求解，FDTW算法建立三维累计代价矩阵M，采用动态规划方式从最小子序列开始依次对所有子序列间被允许的对齐路径长度下的距离值进行计算。使被计算的子序列在距离数量最小化的前提下求解出最终序列间距离，计算过程应当满足以下条件：1)计算某对子序列间的距离值时，其依赖的子序列距离值已经被计算；2)当前被计算的子序列间距离值一定会被后续的计算所依赖。

当序列长度为5时，不同条件下计算的子问题如图 3所示。当时间序列X、Y长度为5时，所有子序列问题如图 3(a)所示(矩阵行列坐标和矩阵元素值分别对应两条子序列下标以及对齐路径长度)。为满足计算过程的条件1，将图 3(a)中所有子序列问题全部求解，但在LDTW算法中(L_UB取为7)，由于不需要求取序列X、Y之间对齐路径长度为8、9对应的距离值。为满足计算过程条件2，将求解的其余子问题相应缩减为图 3(b)的范围。在FDTW算法中(F_L为7)，只需取序列X、Y之间对齐路径长度为7对应的距离值，将求解的其余子问题进一步缩减为图 3(c)的范围。范围缩减后某些子序列间不需要计算任何对齐路径长度下的距离值，其子序列在图 3中用阴影表示。

为了使计算过程满足以上条件，FDTW算法首先根据参数F_L对所有子序列之间的对齐路径长度范围进行计算；其次在范围内计算各子序列距离值。因此，FDTW算法步骤分为子序列间对齐路径长度范围计算和各子序列距离值计算。

2.2.1 子序列间对齐路径长度范围计算

长度分别为R和C的序列X和Y之间允许产生最小和最大对齐路径长度，其计算结果为：min S=max(R，C)、max S=R+C-1。为方便描述，将min S和max S组成的对齐路径长度范围[min S，max S]称为原始对齐路径长度范围。子序列$ {X}_{6}^{1} $和$ {Y}_{4}^{1} $之间调整后的对齐路径长度范围如图 4所示，时间序列长度$ R=C=7 $，设F_L为11，阴影元素$ [{x}_{6}, {y}_{4}] $代表当前要计算子序列$ {X}_{6}^{1} $和$ {Y}_{4}^{1} $之间路径长度范围。从图 4可以看出，实线表示$ {X}_{6}^{1} $和$ {Y}_{4}^{1} $之间长度最大的一条对齐路径，其长度$ \mathrm{m}\mathrm{a}\mathrm{x}S=6+4-1=9 $；长虚线表示$ {X}_{6}^{1} $和$ {Y}_{4}^{1} $之间长度最小的一条对齐路径，长度min S=max(6，4)=6，因此子序列$ {X}_{6}^{1} $和$ {Y}_{4}^{1} $之间的原始长度范围为$ \left[\mathrm{6, 9}\right] $。若子序列$ {X}_{6}^{1} $和$ {Y}_{4}^{1} $之间对齐路径长度为6，那么对齐路径总长度为F_L，其互补子序列$ {X}_{7}^{6} $和$ {Y}_{7}^{4} $之间对齐路径长度为F_L+1$ - $6=6(加1是对齐路径元素$ \left({\pi }_{1}\left(k\right), {\pi }_{2}\left(k\right)\right) $被计算了两次)。子序列$ {X}_{7}^{6} $和$ {Y}_{7}^{4} $之间产生的对齐路径长度小于6；同样，若对齐路径在子序列$ {X}_{6}^{1} $和$ {Y}_{4}^{1} $之间长度为9，那么子序列$ {X}_{7}^{6} $和$ {Y}_{7}^{4} $之间对齐路径长度为F_L+1$ - $9=3，但子序列$ {X}_{7}^{6} $和$ {Y}_{7}^{4} $之间的对齐路径长度总是大于3。

因此，根据参数F_L和互补子序列$ {X}_{R}^{r} $和$ {Y}_{C}^{c} $之间的原始对齐路径长度，对子序列$ {X}_{r}^{1} $和$ {Y}_{c}^{1} $间原始的齐路径长度范围的上限和下限进行进一步调整。

1) 调整范围上限

在计算出子序列$ {X}_{r}^{1} $和$ {Y}_{c}^{1} $之间的原始最大对齐路径长度$ \mathrm{m}\mathrm{a}\mathrm{x}S $后，计算其互补子序列$ {X}_{R}^{r} $和$ {Y}_{C}^{c} $之间的最小原始对齐路径长度min S_toEnd = max(R-r+1，C-c+1)。从图 4可以看出，短虚线表示子序列$ {X}_{7}^{6} $和$ {Y}_{7}^{4} $之间长度最小的一条对齐路径，其长度min S_toEnd = max(7-6，7-4)+1 = 4。用给定的固定长度F_L减去该长度得到子序列$ {X}_{r}^{1} $和$ {Y}_{c}^{1} $之间的另一组最大长度max S_1=F_s+1-min S_toEnd。子序列$ {X}_{6}^{1} $和$ {Y}_{4}^{1} $之间的max S_1 = 11+1-4 = 8。最终FDTW算法在两个最大长度$ \mathrm{m}\mathrm{a}\mathrm{x}S $和$ \mathrm{m}\mathrm{a}\mathrm{x}S\_1 $中选取较小者作为子序列$ {X}_{r}^{1} $和$ {Y}_{c}^{1} $之间调整后最大对齐路径长度$ \mathrm{F}\mathrm{i}\mathrm{x}\mathrm{e}\mathrm{d}\_\mathrm{m}\mathrm{a}\mathrm{x}S $。子序列$ {X}_{6}^{1} $和$ {Y}_{4}^{1} $之间调整后最大长度Fixed_max S=min(max S，max S_1)=min(9，8)=8。算法1描述求取子序列$ {X}_{r}^{1} $和$ {Y}_{c}^{1} $之间调整后最大长度的过程。

算法1  计算子序列间对最大对齐路径长度

输入  子序列$ {X}_{r}^{1} $和$ {Y}_{r}^{1} $的长度r、c；固定对齐路径长度F_L；时间序列X和Y的长度R，C

输出  子序列$ {X}_{r}^{1} $和$ {Y}_{r}^{1} $间调整后最大对齐路径长度

1. function FIXED_MAX_STEP(r，c，FL，R，C)

//计算子序列间原始最大对齐路径长度

2. maxS = r+c-1

//计算互补子序列间的原始最小对齐路径长度

3. minS_toEnd = max(R-r，C-c)+1

4. maxS_1 = F_L-minS_toEnd+1

//从两个最大对齐路径长度中选取较小者作为返回值

5..fixed_maxS = min(maxS，maxS_1)

6. return fixed_maxS

7. end function

2) 调整范围下限

在计算出子序列$ {X}_{r}^{1} $和$ {Y}_{c}^{1} $之间的原始最小对齐路径长度min S后，计算相应互补子序列$ {X}_{R}^{r} $和$ {Y}_{C}^{c} $之间的最大原始对齐路径长度max S_toEnd = (R-r+1)+(C-c+1)-1。长短虚线表示子序列$ {X}_{7}^{6} $和$ {Y}_{7}^{4} $之间长度最长的一条对齐路径，其长度max S_toEnd=7-6+7-4+1=5。用给定的固定长度F_L减去该长度，得到子序列$ {X}_{r}^{1} $和$ {Y}_{c}^{1} $之间的另一组最小长度min S_1=F_S+1-max S_toEnd。例如子序列$ {X}_{6}^{1} $和$ {Y}_{4}^{1} $之间的min S_1=11+1-5=7。最终FDTW算法在两个最小长度$ \mathrm{m}\mathrm{i}\mathrm{n}~~S $和$ \mathrm{m}\mathrm{i}\mathrm{n}~~S\_1 $中选取较大值作为调整后最小对齐路径长度$ \mathrm{F}\mathrm{i}\mathrm{x}\mathrm{e}\mathrm{d}\_\mathrm{m}\mathrm{i}\mathrm{n}~~S $。子序列$ {X}_{6}^{1} $和$ {Y}_{4}^{1} $之间的调整后最小长度Fixed_min S=max(min S，min S_1)=max(6，7)=7。算法2描述求取子序列$ {X}_{r}^{1} $和$ {Y}_{c}^{1} $之间调整后最小长度的过程。

算法2  计算子序列间对最小齐路径长度

输入  子序列$ {X}_{r}^{1} $和$ {Y}_{r}^{1} $的长度r、c；固定对齐路径长度F_L；时间序列X和Y的长度R，C

输出  子序列$ {X}_{r}^{1} $和$ {Y}_{r}^{1} $间的调整后最小对齐路径长度

1. function FIXED_MIN_STEP(r，c，F_L，R，C)

//计算子序列间原始最小对齐路径长度

2. minS = max(r，c)

//计算互补子序列间的原始最大对齐路径长度

3. maxS_toEnd = R-r + C-c+1

4. minS_1 = F_L-maxS_toEnd+1

....//从两个最大对齐路径长度中选取较大者作为返回值

5. fixed_minS = max(minS，minS_1)

6. return fixed_minS

7. end function

经过以上调整，子序列$ {X}_{6}^{1} $和$ {Y}_{4}^{1} $之间的对齐路径长度范围由原始范围[6,9]变为[7,8]，达到了排除无需计算子序列问题的目的。实际FDTW算法和LDTW算法在流程上的区别体现在以上确定子序列间对齐路径长度范围的过程。LDTW算法计算出子序列$ {X}_{r}^{1} $和$ {Y}_{c}^{1} $之间的原始对齐路径长度范围[min S，max S]后，并不会对长度范围的下限进行进一步缩小，序列X和Y之间的路径长度范围为[min S，L_UB]，而FDTW算法会对下限进行进一步调整，使得该范围只有一个值，即F_L。

2.2.2 子序列之间距离值计算

确定子序列间对齐路径长度范围后，FDTW算法根据式(5)计算每个矩阵元素，该过程和LDTW算法相同，具体步骤可以用算法3进行描述。算法3第3、第4行建立累计代价矩阵并初始化；第6~14行对累计代价矩阵进行计算，其中第8、第9行调用算法1和算法2对子序列之间的对齐路径长度范围进行计算。

算法3   FDTW算法

输入  时间序列X、Y；固定对齐路径长度F_L；时间序列长度R、C

输出  时间序列X、Y之间的F_D距离值

1. function F_D(X，Y，FL，R，C)

2. //创建三维累计代价矩阵并初始化

3. let M be a (R+1)×(C+1)×(F_L+1) matrix with maximum float value

4. M[0][0][0] = 0

5. //依次计算所有子序列间的距离值

6. for r = 1 to R+1 do

7. for c = 1 to C+1 do

//调用算法1计算子序列间的对齐路径长度下限

8. fixedMinS =FIXED_MIN_STEP(r，c，F_L，R，C)

//调用算法2计算子序列间的对齐路径长度上限

9. fixedMaxS =FIXED_MAX_STEP(r，c，F_L，R，C)

//根据式(5)计算子序列间在对齐路径长度范围内的距离值

10. for s = fixedMinS to fixedMaxS do

11. M[r][c][s]=dis(x_r-1，y_c-1)+min$ \left\{\begin{array}{l}\mathrm{M}[\mathrm{r}-1][\mathrm{c}-1][\mathrm{s}-1]\\ \mathrm{M}[\mathrm{r}-1]\left[\mathrm{c}\right][\mathrm{s}-1]\\ \mathrm{M}\left[\mathrm{r}\right][\mathrm{c}-1][\mathrm{s}-1]\end{array}\right. $

12. end for

13. end for

14. end for

15. return M[R][C][FL]

16. end function

2.3 算法时间复杂度

FDTW算法的时间复杂度与累计代价矩阵中需要计算的累计代价矩阵元素数量相关，本文对LDTW算法的累计代价矩阵元素数量N的分析过程中得出FDTW算法的计算量。

LDTW算法的N值与时间序列长度R、C以及对齐路径长度上限L_UB相关(当时间序列长度不变时，N值随L_UB变化)。为了找出N值与R、C和L_UB之间的关系，LDTW算法中累计代价矩阵拆分如图 5所示，用相同的边缘线条类型来体现拆分后各分量矩阵在原矩阵的坐标位置。将第一个包含坐标为[R，C]元素的分量矩阵及其之前的分量矩阵标记为a类分量矩阵，将其余分量矩阵标记为b类分量矩阵。从图 5可以看出，根据先后顺序依次计算分量矩阵将满足以下规律：当前计算元素所依赖的元素都已在此之前计算完毕。从图 5(a)可以看出，箭头在计算元素M[x₄][y₄][5]时，依赖的三个元素M[x₃][y₃][4]、M[x₃][y₄][4]和M[x₄][y₃][4]都已经完成计算。当所有a类分量矩阵计算完成时，长度等于L_UB的对齐路径所对应的最小距离值则计算完成，该值是FDTW算法在参数F_L=L_UB时的目标值。因此，a类分量矩阵元素数量是FDTW算法的累计代价矩阵元素的计算量，而b类分量矩阵元素数量是FDTW算法与LDTW算法之间矩阵元素计算量的差值。

根据确定序列间对齐路径长度范围的规则可知，a类分量矩阵个数为max S-L_UB+1，每个a类分量矩阵包含的元素数量为[R-(max S-L_UB)][C-(max S-L_UB)]，则所有a类分量矩阵元素总数量如式(8)所示：

$ {M}_{a}=\left(R-m\right)\left(C-m\right)\left(m+1\right) $

(8)

其中：m = max S-L_UB。

b类分量矩阵个数为L_UB-min S，所有b类分量矩阵所包含的元素数量构成首项为|R-C|+1，二级首项为|R-C|+3，二级公差为2的二阶等差数列，可推导出所有b类分量矩阵元素的总数量如式(9)所示：

$ {M}_{b}=\frac{n\left(n+1\right)\left(2n+3p+1\right)}{6} $

(9)

其中：n=L_UB-min S；p=|R-C|。

当两条时间序列长度相等，即R=C时，所有a类分量矩阵元素总数量简化如式(10)所示：

$ {M}_{a}={\left({L}_{\mathrm{U}\mathrm{B}}-R+2\right)}^{2}\left(2R-1-{L}_{\mathrm{U}\mathrm{B}}\right) $

(10)

其中：M_a为关于对齐路径长度上限L_UB的三次函数，当L_UB为(5R-4)/3时M_a的取值范围如式(11)所示：

$ {M}_{a}\in \left[R\text{，}\frac{4{(R+1)}^{3}}{81}\right] $

(11)

当两条时间序列长度相等，所有b类分量矩阵元素的总数量简化如式(12)所示：

$ {M}_{b}=\frac{n(n+1)(2n+1)}{6} $

(12)

N值为a类分量矩阵元素数量和b类矩阵元素数量之和，N = M_a + M_b。推算出N为关于对齐路径长度上限L_UB的单调递增函数，N的取值范围如式(13)所示：

$ N\in \left[R, \frac{R\left(R+1\right)\left(2R+1\right)}{6}\right] $

(13)

在以上推导过程中，N值代表LDTW算法中需要计算累计代价矩阵元素的数量，M_a值代表FDTW算法中需要计算的累计代价矩阵元素数量，M_b值为LDTW算法计算量和FDTW算法之间的差值。由于对累计代价矩阵元素的计算是LDTW算法和FDTW算法的基本操作，累计代价矩阵元素数量即为算法基本操作的执行频度。从式(12)和式(13)可以看出，LDTW算法和FDTW算法累计代价矩阵元素数量都与时间序列长度呈三次方关系。因此这两种算法的时间复杂度都为O(n³)。当R=C=50时，N、M_a、M_b随L_UB变化对比如图 6所示。从图 6可以看出，L_UB取值越大，差值M_b越大。当两种算法的参数相同时，FDTW算法计算量比LDTW算法更低。

3 实验

为了与DTW算法及其变体算法的相关工作保持一致，本文采用1-NN分类方法，将FDTW算法作为距离度量，在UCR公共数据集上进行分类实验，以验证FDTW算法的性能。

3.1 数据集

近年来，UCR时间序列数据文档^[19]被研究者广泛引用，本文从该数据文档中选取序列长度分布在60~637的37个数据集进行实验。所选取的数据集如表 1所示。

3.2 FDTW-1NN分类结果

最近邻分类方法因无需设置参数，分类结果仅依赖于度量方式而被广泛采用，本文采用该方法进行分类实验。ED距离、DTW算法、Sakoe-Chiba窗口DTW算法、LDTW算法以及FDTW算法在相同数据集上的分类准确率如表 2所示。其中，w是Sakoe-Chiba窗口DTW算法的参数，即窗口宽度占序列长度的百分比。Sakoe-Chiba窗口DTW算法、LDTW算法以及FDTW算法设置的参数值标注在准确率右侧，该参数都由交叉验证法在训练集上学习得到。从表 2可以看出，LDTW算法和FDTW算法在绝大多数数据集上取得最佳分类准确率。与LDTW算法相比，在WordSynonyms数据集上，FDTW算法的分类准确率最多提高了7个百分点，在Lightning7数据集上，最多降低了4个百分点。

FDTW算法与其他算法的分类准确率对比如图 7所示。从图 7可以看出，黑点代表各数据集，对角线代表中线，若黑点位于该线上则代表两种算法准确率相等。从图 7(a)、图 7(b)、图 7(c)可以看出，相比ED距离、DTW算法、Sakoe-Chiba窗口DTW算法，FDTW算法在绝大多数数据集上表现更优(相比ED距离有29个，相比DTW算法有28个，相比Sakoe-Chiba窗口DTW算法有27个)，在部分数据集上持平(相比ED距离有5个，相比DTW算法有4个，相比Sakoe-Chiba窗口DTW算法有5个)，部分数据集上呈略微劣势(相比ED距离有3个，相比DTW算法有5个，相比Sakoe-Chiba窗口DTW算法有5个)。从图 7(d)可以看出，相比LDTW算法，FDTW算法的分类正确率在22个数据集上持平，在8个数据集上胜出，7个数据集上呈劣势。

与高准确率相比，算法提前在哪些数据集上能取得高的准确率更能体现算法的可靠性^[20]。本文采用文献[20]提出的增益混淆矩阵对FDTW算法的可靠性进行评估。通过式(14)分别计算FDTW算法与对比算法(competitor algorithm)之间的预期准确率增益和实际准确率增益：

$ g=\frac{{a}_{\mathrm{F}\mathrm{D}\mathrm{T}\mathrm{W}}}{{a}_{\mathrm{c}\mathrm{o}\mathrm{m}\mathrm{p}\mathrm{e}\mathrm{t}\mathrm{i}\mathrm{t}\mathrm{o}\mathrm{r}~~\mathrm{ }\mathrm{a}\mathrm{l}\mathrm{g}\mathrm{o}\mathrm{r}\mathrm{i}\mathrm{t}\mathrm{h}\mathrm{m}}} $

(14)

计算预期增益时，将交叉验证过程中在训练集上取得的最高准确率作为预期准确率，而计算实际增益时，在测试集上进行分类实验的结果作为实际准确率。FDTW算法与其他4种算法间预期准确率增益和实际准确率增益对比如图 8所示。其中每个点代表一个数据集，每个点会出现在4个区域中的一个区域(包括边缘)，这4个区域分别是：1)真阳性(TP)，数据点出现在此区域是预计在该数据集上提高准确率，而实际上确实提高了，出现在该区域的数据点越多，证明算法可靠性越强；2)真阴性(TN)，数据点出现在此区域是预计在该数据集上准确率降低，而实际上确实降低了，如果出现在该区域的数据点过多，应避免在此数据集上使用被提出的算法；3)假阴性(FN)，数据点出现在此区域中是预计在该数据集上准确率降低，实际上准确率有所提高；4)假阳性(FP)，数据点出现在此区域中是预计在该数据集上准确率会提高，但实际上准确率却下降了，出现在该区域的数据点越多，说明算法的可靠性越差。

从图 8(a)~图 8(c)可以看出，绝大多数数据点都落入TP区域，说明相比ED距离、DTW、Sakoe-Chiba窗口DTW3种算法，FDTW算法的分类准确率得到提高是可靠的。从图 8(d)可以看出，虽然落入TP区域的数据点有所减少，但减少的这些数据点并没有落入其他区域，而是处于横轴边缘，说明在测试集上的分类准确率没有降低。相比其他区域，落在TP区域的数据点更明显，因为在部分数据集上有较高的预期准确率增益和实际准确率增益(如BirdChicken和WordsSynonyms数据集)，说明FDTW算法与LDTW算法相比，在分类准确率上有着持平的结果是可靠的。

3.3 时间开销对比

由2.3节可知FDTW和LDTW算法的时间复杂度都为$ O\left({n}^{3}\right) $，但在参数相同时，FDTW算法需要计算的累计代价矩阵元素数量比LDTW算法更少。为进一步对比FDTW和LDTW算法的计算量，选取两种算法所需参数相同的8个数据集，分别记录两种算法在分类过程中所花费的时间以及两者之间的差值。两种算法在这8个数据集上的分类准确率是持平的。参数相同的数据集下FDTW和LDTW算法的时间开销如表 3所示。为了体现两组时间数据差异，FDTW和LDTW算法分类时间开销对比如图 9所示。从图 9可以看出，FDTW算法在所有数据集上的分类时间开销都小于LDTW算法，时间开销最多减少了10%(Ham数据集)。

为了更直观体现FDTW算法和LDTW算法计算量的差异，选取了长度最短的数据集SyntheticControl，将两种算法在该数据集上的三维累计代价矩阵元素对比如图 10所示。在参数相同的情况下，与LDTW算法相比，FDTW算法的累计代价矩阵减少了部分右上角的元素，从而相应减少了时间开销。

3.4 参数对齐路径长度(FL)的选取

参数F_L是FDTW算法所需的唯一参数，该参数的选取将影响数据集的分类准确率。为了选取更合适的F_L参数，本文采用10折交叉验证法从各数据集包含的训练集上对该参数进行学习。将训练集划分为10份，每次将其中一份作为训练集，其余作为测试集，依次计算出参数F_L在所有可能取值下的准确率(即F_L的步长为1)。该过程在不同测试集上重复10次，取均值作为该F_L参数下的最终准确率，然后选取最高准确率所对应的F_L参数值作为最终的参数值。计算两条时间序列在不同F_L值下的FDTW距离值，会出现累计代价矩阵元素被重复计算的现象，例如，对于任何两条时间序列，F_L无论如何取值，累计代价矩阵的第一个元素M[1][1][1]都将被计算，说明在交叉验证过程中，F_L有多种取值可能，元素M[1][1][1]就会被计算多次。本文在进行交叉验证过程中，采用LDTW算法，将参数L_UB设定为$ \mathrm{m}\mathrm{a}\mathrm{x}S $，从而在一次累计代价矩阵的计算过程中得出两条时间序列之间所有对齐路径长度下的弯曲距离值，以此来避免重复计算数据集。

在不同数据集上交叉验证性F_L值对比如图 11所示，从图 11可以看出，部分数据集的最佳准确率所对应的F_L值并不唯一，本文选取更小的F_L值，因这些F_L值通常小于(5R-4)/3，根据2.3节当F_L小于(5R-4)/3时，F_L值越小，算法的计算量越小。

从数据集ArrowHead和ECG200中可以看出，它们最佳分类准确率对应F_L值靠近或等于$ \mathrm{m}\mathrm{i}\mathrm{n}S $，说明对齐路径长度与时间序列长度相等，此时的F_D距离值与ED值等价。同时从表 1可以看出，这些数据集在ED距离下的分类准确率和F_D距离及F_D距离对应的准确率相似。因为这类时间序列存在较小的时滞(相位偏移)，在ArrowHead和BirdChicken数据集上时滞对比如图 12所示。从图 12(a)可以看出，数据集ArrowHead中的序列只在垂直方向上存在一定噪声(振幅差)，横向上几乎不存在相位偏移，在这样的时间序列之间，欧氏距离更适合作为度量方式。从图 12(b)可以看出，BirdChicken数据集中序列之间相位偏移和振幅差同时存在，此时欧氏距离不再有较好的度量效果。经过交叉验证后选取的参数F_L，能够反应序列之间在横向上相位偏移的大小，即时滞的严重程度，使得后续分类更为准确。

4 结束语

针对LDTW算法计算量较大的问题，本文提出FDTW算法。通过调整LDTW算法中对齐路径长度的控制策略，以减少累计代价矩阵中需要计算的元素数量。在UCR时间序列数据集的实验结果表明，与其他时间序列距离度量(ED欧氏距离、DTW动态弯曲距离和DTW_SC窗口动态弯曲距离)相比，FDTW算法在大多数数据集上具有更高的准确率，其与FDTW算法的分类准确率呈持平状态，且时间开销更小。后续将研究如何在保留限制对齐路径长度的同时降低时间复杂度，进一步提高FDTW算法的计算效率。