噪声鲁棒的动态时间规整算法

邱莲鹏，宋承云

（重庆理工大学 计算机科学与工程学院，重庆 400054）

0 引言

时间序列数据在生物系统［1］、遥感［2］、多媒体［3］、手写［4］和运动物体轨迹追踪［5］等领域中广泛分布。与静态数据不同，时间序列数据具有完全捕获观察对象的时间演变的优势。数据挖掘研究人员提出了大量的算法适应这种类型的数据，这产生了大量的研究任务，如时间序列分类［6］、聚类［7］和分割［8］。时间序列处理中的一项基本任务是量化两个时间序列之间的相似程度，因此，距离/相似性度量的选择直接影响时间序列数据分类和聚类的效果［9］。

动态时间规整（Dynamic Time Warping，DTW）［10］通过动态规划思想寻找两条时间序列之间的最佳匹配路径，从而度量时间序列相似性。与传统的相似性度量方法欧氏距离（Euclidean Distance，ED）等相比，DTW 能有效应对时间序列的振幅变化、相位偏移等问题，已得到更广泛应用。然而，DTW 会引起弯曲路径过度拉伸和过度压缩，导致“病态路径”，即一个时间序列上的一个点匹配另一个时间序列上的多个点，如图1（a）所示。在这种情况下，无法准确计算两个同类时间序列之间的距离值，影响相似性度量的准确性。为了解决该问题，研究者们提出了一些DTW 改进算法，这些方法主要分为两类：一类以提取形状特征考虑局部信息；另一类以惩罚弯曲路径减少“病态路径”。

图1 病态路径示意图Fig.1 Schematic diagram of pathological path

在提取形状特征信息方面，为了在两个序列之间获得直观正确的“特征到特征”对齐，Keogh 等［11］引入了导数DTW（Derivative DTW，DDTW），它计算时间序列的一阶导数，然后通过DTW 对齐两个导数序列。DDTW 只关注单个时间点的信息，没有考虑到上下文信息，因此王见等［12］提出了一种结合形状特征和上下文信息的多维DTW 算法。该算法首先对多维时间序列计算一阶梯度，然后利用一阶梯度的特征查找最优对齐路径。尽管以上方法通过重新调整DTW 度量，在某些数据集上取得了较好的结果，但他们没有修改原始的DTW 算法。

在惩罚弯曲路径方面，Jeong 等［13］提出加权DTW（Weighted DTW，WDTW），这是一种基于惩罚的DTW，WDTW 在计算两点之间的距离时考虑了两点之间的相位差。Batista 等［14］提出了一种复杂度不变的距离度量，它本质上是通过乘以复杂度校正因子校正现有的距离度量（ED、DTW）。另外，窗口约束是一种更直观的解决方案，它限制了每个点可以对齐的范围，约束弯曲路径的方法主要有全局约束和局部约束两种：全局约束将弯曲路径的演化限制到特定区域，使它尽 可能呈 对角线，Sakoe-Chiba［15］和Itakura-Parallelogram［16］约束是两种常见的全局约束。Morel等［17］提出了局部约束方式，利用时间序列局部结构信息约束弯曲路径的搜索；然而选择合适的弯曲约束需要应用领域先验知识，因此很难确定参数大小。

本文借鉴降噪自动编码器（Denoising AutoEncoder）［18］的算法思想，提出了出一种噪声鲁棒的DTW（Noise robust DTW，NoiseDTW）算法。传统的DTW 和DTW 的变体总是计算两个时间序列数据之间的最小距离之和，不能提供适当的局部匹配；在噪声的影响下，容易出现两个同类型的时间序列的累积距离值大于两个不同类型的时间序列的累积距离值的情况，从而增加分类误差。降噪自动编码器为了在处理相似样本时模型有更好的泛化能力，将训练数据加噪声后再输入模型，从而提取到更鲁棒性的表征。基于此，在时间序列中加入少量噪声后执行DTW 算法，以增强算法的噪声抑制能力。如图1（b）所示，在原始的信号中加噪声后，解决了序列对齐中存在的一个点对齐多个点的问题。针对噪声的随机性问题，NoiseDTW 算法通过多次添加噪声的方式提升了算法的稳定性。

1 相关工作

DTW 是一种利用动态规划在两个时间序列之间搜索最佳匹配路径的算法。为了应对信号的相位偏移和振幅变化，DTW 将序列进行非线性弯曲，以测量不同长度序列之间的相似性，DTW 算法的概述如下。

假设单变量时间序列P的长度为M，Q的长度为N，其中P=(p1，p2，…，pM)，Q=(q1，q2，…，qN)。图2（a）和图2（b）分别表示时间序列P和Q，为了DTW 能够计算P和Q之间的相似度，构建一个大小为M×N的距离矩阵D（如图2（c）所示），其中的元素d(pi，qj)表示pi与qj之间的距离，通过式（1）计算：

图2 DTW距离矩阵Fig.2 Distance matrix of DTW

为了保证弯曲路径匹配的有效性，w通常需要满足3 个约束条件，即边界条件、连续性条件和单调性。边界条件代表路径必须从w1开始到wk结束，连续性条件表示必须一步一步地寻找最优路径，单调性约束弯曲路径向前移动。DTW 的目标是在所有满足上述约束条件的w中，通过动态规划思想确定距离最短的一条路径w。假设DTW(P，Q)表示d(pi，qj)的累积距离，为了确定P和Q之间的最佳对齐路径，通过式（2）计算最短的一条路径的累积距离DTW(P，Q)，根据这条路径对齐两条时间序列，可视化结果如图1 所示。

其中：M≥i＞1 并且N≥j＞1，D(M，N)为DTW 度量下序列P和Q的最小距离，可知DTW(P，Q)=D(M，N)。当i，j=1时，DTW(P，Q)=D(1，1)=d(p1，q1)。

2 NoiseDTW 算法

2.1 算法原理

针对DTW 在噪声的影响下容易出现“病态路径”的问题，本文提出了对噪声鲁棒的NoiseDTW 算法。算法原理示意图如图3 所示。

图3 NoiseDTW 算法的原理示意图Fig.3 Schematic diagram of principle of NoiseDTW algorithm

对于给定的两个时间序列P和Q（如图3（a）所示），加入均值为0、方差为α的高斯噪声，得到时间序列nP=(np1，np2，…，npi，…，npM) 和nQ=(nq1，nq2，…，nqj，…，nqN)（如图3（b）所示）。设D1是nP和nQ的距离矩阵，大小为M×N，D1的计算如式（3）所示：

在式（3）计算加入噪声之后的两个时间序列的距离矩阵D1中调用递归式（2）搜索累积距离DTW(nP，nQ)最小的弯曲路径W1。重复添加随机噪声、计算距离矩阵和搜索弯曲路径，在第e次迭代后，得到e个距离矩阵(D1，D2，…，De)，搜索相应的距离矩阵得到e条弯曲路径(W1，W2，…，We)，每条弯曲路径代表每次迭代产生的距离矩阵中累积距离最短的路径（如图3（c）所示）。

明显地，越多的弯曲路径通过位置(i，j)，表明pi和qj具有很强的相似性，应该给予较大的匹配可能性。因此，NoiseDTW 统计每个点(i，j)的弯曲路径通过的次数，以构建新的距离矩阵D'（如图3（d）所示），大小为M×N，计算公式如式（4）。

进一步，调用递归式（2）找到最优的弯曲路径。根据上一步得到的最优路径，对齐时间序列P和Q（如图3（e）所示）。具体的NoiseDTW 算法伪代码如算法1 所示。

算法1 NoiseDTW 算法。

算法1 的第7）行和第12）行中的函数dp代表动态规划过程，DTW 算法在动态规划过程中有5 种步进模式可供选择［19］。如图4 所示，DTW 步进模式主要包括 “symmetric1”“symmetric2”“asymmetric”“rabinerJuang”和“symmetric5”。步进模式定义了匹配点对之间的转换和相应权重，填充的圆代表点对匹配的当前位置，连接线表示从当前位置到下一个空心圆的权重，连接线上的数字表示权重值。“symmetric1”是被广泛使用的按对称性和边界分类的步进模式。“symmetric2”是基于局部连续性约束、坡度权重和平滑度这3 个特征的步进模式，相较于“symmetric1”，“symmetric2”模式赋予对角线方向更多的权重。“asymmetric”“rabinerJuang”和“symmetric5”模式可以跳过特定的元素（实心圆未与空心圆匹配）。本文采用默认的步进模式（图4（a）中的模式），它的递归公式如式（2）所示。

图4 5种步进模式Fig.4 Five stepping patterns

2.2 KNN-NoiseDTW 时间序列分类

Geler 等［20］提出的一种K-近 邻（K-Nearest Neighbors，KNN）结合约束DTW 的非常有效的分类器，可以根据已有标签的时间序列数据预测未知的时间序列数据的类别。NoiseDTW 是距离度量算法，需要结合分类器分类时间序列数据，因此本文结合KNN 分类器提出了KNN-NoiseDTW 算法。假设有N对有标签数据{(x1，y1)，(x2，y2)，…，(xN，yN)}，其中yi∈{1，2，…，M}代表时间序列数据不同的类别。KNNNoiseDTW 算法的目标是对每一个没有标签的数据xi′分配一个对应的标签yi′，KNN-NoiseDTW 的流程如算法2 所示。

算法2KNN-NoiseDTW 算法。

3 实验与结果分析

3.1 数据集

本文使用广泛用作评估时间序列数据挖掘算法基准的公共UCR 时间序列文档［21］。这些数据集来源于各个领域，包括医学、气象学、计算机视觉等。数据集在时间序列长度方面各不相同，每个数据集由训练集和测试集两部分组成。本文在 BeetleFly、BirdChicken、DistalPhalanxTW、Fish、Gun-Point、Symbols、ToeSegmentation1 和ToeSegmentation2 这8个噪声影响比较明显数据集上进行实验，其中时间序列长度分布于80～512。数据集信息如表1 所示。

表1 数据集信息Tab.1 Information of datasets

3.2 参数分析

NoiseDTW 算法中所涉及的超参数有高斯噪声的方差α和迭代次数e。对于噪声方差α，本文选择α=0.100、α=0.010、α=0.001 这3 种情况下对8 个时间序列数据集分类。从图5 可以看出，总体上，在α=0.010 时分类准确较高于其他两种情况。对于迭代次数e，本文选择5、10、15、20 来实验，如图6 中所示，e在4 种情况在8 个数据集上进行实验，从图6 可以看出，总体地，算法在e=10 的时候分类准确率最高。因此，在下文的实验中，本文选择α=0.010，e=10。

图6 不同e下的分类准确率Fig.6 Classification accuracy under different e

3.3 模拟对齐实验

在Gun-Point 数据训练集中标签为1 的时间序列中随机选择一条时间序列，通过缩放、拉伸得到变形之后的时间序列匹配。如图7（a）所示，第一条曲线表示原始时间序列，第二条曲线为经过缩放、伸缩之后的时间序列，中间竖线条为匹配路径，方框中为对比的主要区域。传统的欧氏距离是点对点匹配，得到的匹配路径如图7（b）中方框区域所示，可以看出这种一对一的匹配不适用于不等长的时间序列。DTW结果如图7（c）所示，出现明显的一条时间序列的其中一个点对应另一条时间序列的多个点，即“病态路径”。图7（d）表示WDTW 的实验结果，本文在此处将权重因子设置为0.2。图7（e）和图7（f）分别是NoiseDTW 在α=0.01 下，e=5 和e=10 的实验结果，可以看出，在e=10 下更接近真实匹配路径。

图7 四种方法对齐效果与真实匹配路径的对比Fig.7 Comparison of alignment results between four methods and ground truth

3.4 时间序列分类实验

由于ED、DTW、Sakoe-Chiba 窗口DTW［20］、WDTW 和NoiseDTW 都是度量距离的算法，需要结合分类器进行分类实验。为了方便，本文在KNN-NoiseDTW 中采用1-NN 分类器，优点是没有参数，分类误差仅取决于相似性度量算法。本文将以上5 种算法在8 个时间序列数据集上对比分类准确率，如表2 所示。先前的研究人员已经发布了UCR 数据集上欧氏距离、DTW 和Sakoe-Chiba 窗口DTW 的1NN 分类准确率报告［21］，因此，本文在此基础上增加了WDTW 和NoiseDTW的分类准确率。NoiseDTW 较好的对齐路径可以提高两个时间序列数据相似性度量的准确性，进一步降低分类误差。从表2 可以看出，分类准确率在8 个时间序列数据集上分别比次优算法提高了1～15 个百分点。

表2 8个时间序列数据集上的分类正确率Tab.2 Classification accuracy on 8 time series datasets

更直观地，本文用折线图来展示5 种算法在不同数据集上的错误率（如图9 所示）。分类错误率计算方式为：

从图8 可以看出，首先，本文算法在整体上有较高的分类准确率。其次，尤其对于BirdChicken、ToeSegmentation1 这两个数据集上分类误差降低明显。在Fish、Gun-Point、Symbols 这3 个数据集上有小幅提升。为了分析原因，本文给出了 BirdChicken、DistalPhalanxTW、Fish、Gun-Point、Symbols 和ToeSegmentation1 数据集中训练集时序数据的时滞对比（如图9 所示）。从图9 可以看出，图9（b）～（d）时间序列数据之间在水平方向位移和扭曲不明显，所以NoiseDTW提升不显著。然而，在图9（a）时间序列数据和图9（f）时间序列数据之间水平方向存在明显的扭曲和位移，这说明NoiseDTW 在这类数据集上具有更好的性能。

图8 分类错误率Fig.8 Classification error rate

图9 多个数据集上的时滞对比Fig.9 Time lag comparison on multiple datasets

3.5 算法复杂度分析

本文将NoiseDTW 与DTW、Sakoe-Chiba 窗 口DTW 和WDTW 进行时间复杂度的对比分析，NoiseDTW 的时间复杂度是O(deMN)，DTW 和WDTW的复杂度分别是O(dMN)、O(dMN2)，其中d为训练集样本数，e为迭代次数（常数），M和N为样本的长度。Sakoe-Chiba 窗口DTW 只是缩小距离矩阵的搜索范围，在时间序列分类过程中，复杂度的量级和DTW一样，因此不再赘述。

进一步，测试算法的实际运行时间。本实验在Windows 10 专业版64 位操作系统环境下运行，处理器为Intel Core i5-9400 CPU @2.90 GHz（双 核），软件为Matlab R2021a 64 位。实验设置NoiseDTW 的迭代次数e=10，在8 个数据集上，3 种算法的运行时间以及时间差值如表3 所示。DTW 时间开销最小，由于加权的影响，WDTW时间消耗更大一些，数据集长度越长，测试集数越大，时间差越明显。本文算法是多次加噪声，虽然比DTW 稍慢一点，但是它的运行时间是随着加噪声的次数变化的，如果只加1 次噪声，NoiseDTW 的时间消耗就近似于DTW。

表3 3种算法的时间开销对比 单位：sTab.3 Comparison of time overhead of three algorithms unit：s

4 结语

针对DTW 容易出现“病态对齐”问题，本文提出对噪声鲁棒的NoiseDTW 算法。通过添加高斯噪声，在两个时间序列的多条可能对齐路径中，采用动态规划思想，找到最优的一条对齐路径。在UCR 时间序列数据集的实验结果表明，与ED 距离、DTW、弯曲窗口的DTW 和WDTW 时间序列距离度量算法相比，本文算法在大多数数据集上具有更高的准确率和时间效率。同时，NoiseDTW 算法的改善空间也很大，比如超参数的设置，将来我们将会继续研究对不同数据采用自适应高斯噪声参数，以提高时间序列的相似性度量效果。