基于DTW 的时间序列相似度量方法的优化*

刘 美 王全民

（北京工业大学信息学部 北京 100020）

1 引言

时间序列数据目前是被分析最多的数据类型之一，KDnuggets的一项民意调查显示，2019年48%的分析师分析过时间序列数据，位居数据分析榜第二位［1］。大部分时间序列数据挖掘算法都将相似度量作为核心子程序，包括分类、聚类和异常检测等［2］。时间序列存在宏观结构和微观形状两方面的相似性［3］：宏观结构能够描述时间序列中整体特征或相似的起伏变化，通常使用平均值、方差等构建特征向量进行比对［4］。ARMA［5］模型是由自回归模型与滑动平均模型组合而成，模型简单易懂，但要求时间序列的平稳性；自回归条件异方差（ARCH）模型［6］针对因变量的方差进行预测，对波动变化预测准确，但也会高估波动率；马尔科夫模型［7］通过建立转移概率矩阵对时序数据进行预测，对过程的状态预测效果良好，但不适用于中长期系统的预测。微观形状在降低数据维度，过滤异常值，克服位移拉伸等方面效果显著［8］。传统的欧氏距离（Euclidean distance，EUC）［9］计算简单，但每个点对其贡献率相同，无法克服异常值及拉伸位移等影响，动态时间规整（Dynamic Time Warping，DTW）［10］能够克服位移问题，但其对异常值同样敏感，又存在计算量大的问题。微观形状的另一类方法通常是将原始序列划分为多个子序列，通过子序列进行比较，进而能在一定程度上克服异常值［11］。分段聚合近似（Piecewise Aggregate Approximation，PAA）［12］允许离散化，通过求取子序列平均值降低噪声影响。符号聚合近似（Symbolic Approximation，SAX）［13］以字符刻画分段信息，精确高效。最长公共子序列（Longest Common Subsequence，LCS）［14］设置相似度阈值，自动过滤离群点，且一定程度上克服尺度位移。编辑距离（Edit Distance on Real Sequence，EDR）［15］原理与LCS 相似，不同在于LCS 值越大越相似，而EDR 中0 即为完全匹配，因此EDR较LCS的精确度更高。

根据上述度量方法的优缺点，就DTW 进行优化，并结合面积度量，克服易受异常值、位移拉伸影响及计算量大的问题，达到提高精度与鲁棒性，减少计算时间的目的。

2 动态时间规整DTW的优化方案

由于时间序列存在的拉伸位移等影响，计算固定对位数据点之间距离的一些方法效果往往不理想，因此需要使用动态时间规整的方法，动态调整对位的点，从而找到一条累计距离最小的路径，提高相似性计算的精度。然而动态时间规整存在计算量大，在比对数据点的过程中易受噪声、异常值等影响的问题。为减少计算时间，提高算法的精度与鲁棒性，在动态时间规整中引入分段聚合与相似度阈值。

2.1 引入分段聚合降低时间复杂度

为降低数据维度，减少计算时间，在数据处理阶段对序列进行分段聚合。分段聚合将时间序列分割成多个子序列，每个子序列是以原始序列的均值来表示。设有长度为n 的时间序列Xu=（xu1，xu2，…，xun），Xl=（xl1，xl2，…，xln），将其分段聚合为长度为m 的时间序列和其中压缩比t=n/m，xik'为子序列均值，公式为

以常规DTW 计算Xu，Xl时间复杂度为O（n2），分段聚合后，时间复杂度为O（m2），由于压缩比t=n/m，所以O（m2）=O（n2/t2），时间复杂度缩小t2倍。

2.2 引入相似度阈值提高鲁棒性

为提高算法的鲁棒性，减少噪声、异常值对计算结果的影响，在构建距离矩阵阶段引入相似度阈值ε≥0 。设距离矩阵Dε（m×m），计算两子序列间的距离，公式为

2.3 通过累积矩阵解决拉伸平移问题

通过累积矩阵，动态调整对位的点，实现了对某些点的重复使用，确保重复使用的点达成的路径是最优的，从而较为高效地解决了数据拉伸与平移的问题。利用距离矩阵Dε（m×m），通过动态规划方法，求解累积矩阵，公式为

为保证DTW 在［0，1］间，用累积距离与分段聚合后长度m 做比，则两条时序数据Xu，Xl的最终距离NDTW为

3 结合面积度量提升精度

3.1 宏观结构特征-面积度量

面积度量利用了原数据中的所有信息，能充分反应时间序列的整体特性。面积度量要求时间序列长度相等。设有时序数据组X，其中任一数据Xi=（xi1，xi2，…，xij，…，xin），i=1，2，…，q，序列长度为n，且元素不全为0，xij为该序列的第j个数据。选取Xu、Xl，其中u≠l，则定义Xu、Xl的面积距离为

面积距离至少具有如下性质：

1）非负性：AREA（Xu，Xl）≥0；

2）有界性：AREA（Xu，Xl）≤1；

3）对称性：AREA（Xu，Xl）=AREA（Xl，Xu）。

根据性质1）与2），可知AREA（Xu，Xl）在［0，1］范围内，即当两序列完全相同时为1（自相似性），当两序列对应元素相加为0 时为0，AREA 越大序列越相似，对相似性有明确描述。性质3）表明序列Xu与Xl的贡献率在此公式中时一致的。

3.2 面积度量与DTW的有机结合

面积度量利用了元数据中所有信息，能充分反应整体特征，同时也就无法避免噪声产生的影响，也无法解决位移拉伸等问题；DTW 有割裂时间序列整体性的缺陷，但引入分段聚合与相似度阈值后，能降低计算量，过滤噪声与异常值，并且能够通过动态规划解决位移拉伸问题。基于以上二者优缺点，提出面积距离与优化DTW 结合的方法（Area and New Dynamic Time Warping，ANDTW），既可以利用面积距离描述宏观结构，又可以将微观形状具有的优势融入其中，进一步提升算法精度与鲁棒性。

对 于 时 间 序 列Xu=（xu1，xu2，…，xun），Xl=（xl1，xl2，…，xln）首先通过分段聚合PAA 将原始序列等分为m 个子序列，并计算每个子序列的均值；其次根据相似度阈值ε构建距离矩阵Dε（m×m）并计算累积矩阵δm×m；第三根据式（5）计算面积距离AREA（Xu，Xl）；最后将归一化处后的DTW 距离NDTWu，l与面积距离AREA（Xu，Xl）相结合。最终距离公式为

由于NDTWu，l计算结果为相异距离，AREA（Xu，Xl）计算相似度，且取值都在［0，1］之间，则用NDTWu，l与AREA（Xu，Xl）相减，得到Xu，Xl间的最终距离，取值在［-1，1］间，值越小越相似。

3.3 基于面积度量与DTW算法实现

算法1 ANDTW算法

输入：待度量时间序列，相似度阈值ε，压缩比t。

输出：相似度距离。

1）时间序列规范化，得到标准时间序列Xu，Xl。

3）根据阈值ε，利用式（2）、（3）、（4），计算NDTW 距离NDTW（u，l）=δu，l（m，m）/m。

4）根据式（5）计算Xu，Xl的面积距离AREA（Xu，Xl）。

5）根据式（6），将二者结合，得到最终ANDTW距离。

4 实验

为验证ANDTW 方法具有高精确度与鲁棒性，采用ECU、DTW、PAA、SAX、EDR 等进行分类对比实验。

4.1 实验数据及环境

“UCR Time Series Classification Archive”即UCR数据集，是目前时间序列挖掘领域重要的开源数据集资源，涵盖人工数据、现实数据和图形数据，由此可以通过不同类型的数据发现不同方法度量效果的差异。不同数据集所包含时间序列个数不同，但同一数据集中序列长度相等。每个数据集不均等的分为训练集和测试集，且都带有分类标签。为测试不同方法性能，从UCR 中选取30 个数据集进行实验［16］，数据类别范围为2～10，时间序列长度从24～900不等。

实验环境为Windows 10 64 位系统Intel-i7 CPU、16 GB 内存的高配置计算机，开发环境使用python3.7语言的jupyter notebook开发工具。

4.2 精确度验证实验及时间效率比较

实验过程中，量纲会对收敛速度和计算结果造成一定的影响，因此实验之前要进行数据的归一化处理。使用Z-score 标准化，使经过处理的数据符合标准正态分布，即均值为0，标准差为1。

由于分类结果精确度的高低由分类算法和距离度量两方面决定，本实验主要验证ANDTW 与其他方法相比具有的高精度与鲁棒性，因此分类算法选取最邻近（1NN）分类方法，评价指标也同样使用错误率来进行比较，错误率越低，分类结果越理想。

实验中需要进行两个参数训练：相似度阈值ε和压缩比t，压缩比t用分段数m 表示。由于归一化处理，ε取值设在［0.02，0.2］，步长为0.02。分段数m 范围为［2，n/2］，步长为1 到m，n 为时间序列长度。

图1 显示了数据集BeetleFly 的分段数m 和相似度阈值ε不同取值时的分类错误率。BeetleFly数据集共有2 类、40 个时序数据序列，每个序列长度均为512，且训练集与测试集比例为1：1。图1（a）分段数m 取值为2～256 的错误率情况。容易发现，随着分段数取值的不断增长，错误率急速下降后趋于平稳，而ANDTW 在前期收敛速度更快。图1（b）为固定分段数m 为8 时，ε取值从0.02～0.2 时错误率的分布情况，呈现中部凹陷趋势：相似度阈值ε选择太小，区分度太细，对噪声敏感，ε取值过大，不能充分利用数据，导致分类模糊。

图1 分段数、相似度阈值对错误率影响

表1展示了在30个不同的时序数据集中，不同度量的分类结果错误率比较，底部是对均值、变异系数和偏度进行统计比较。均值是集中趋势的体现；变异系数是原始数据标准差与均值的比，可以在比较两组数据离散程度大小的时候，有效消除测量尺度和量纲的影响。偏度是描述分布偏离对称性程度的一个特征数，当偏度系数大于0 时，即重尾在右侧时，该分布为右偏。可以看出ANDTW 分类错误率均值最低，而偏度最大，说明分类效果更好，且错误率更加集中。变异系数小说明波动幅度较小。通过将表1 转化为图2，可以更为直观地呈现现有方法与ANDTW的分类结果差异性比较。

表1 分类错误率表

图2 分类错误率箱图

图3 百分比堆积条形图时间比较

图4 原数据与处理后数据对比

为验证ANDTW与DTW相比具有更高的效率，记录每个数据集在ANDTW 与DTW 方法下的分类时间，结果如表2所示。

表2 ANDTW与DTW时间比较

从百分比堆积条形图（图中数据为所占总体时间百分比）可以看出ANDTW 所用时间均小于DTW所用时间（所占比小于50%），并且压缩比t越大，所需时间在相应比重中越小，与式（1）所计算的时间复杂度相符合，验证了ANDTW 能够有效降低时间复杂度，提高效率。

4.3 鲁棒性实验

异常值是指一组测定值中与平均值的偏差超过两倍标准差的测定值，与平均值的偏差超过三倍标准差的测定值，称为高度异常的异常值。由于PAA、DTW 与ANDTW 在ECG200 数据集上分类效果相差较小，为验证ANDTW 较PAA，DTW 具有更高的鲁棒性，向ECG200测试集中添加10组均值为0，标准差为0.2的高斯噪声与3%的异常值，得到十组带有噪声与异常值的测试集。原数据与处理后的数据如图所示。

在训练好的模型上对处理后的十组测试集进行分类，分类结果见表3。

表3 十组测试集分类错误率表

三个方法错误率都分布在［0.15，0.25］间，较之前平均错误率0.11有所下降。图5为PAA，DTW 与ANDTW 在10 组测试集中分类错误率比较。散点图中散点分布较多的一方，是分类结果较差的一方。可以看出，在PAA、DTW 与ANDTW 比较时，大部分的点都分布在原理ANDTW 的一方，进一步证明ANDTW有更好的鲁棒性。

图5 效果对比散点图

5 结语

本文针对相似度量方法中存在的易受噪声影响、计算量大、位移拉伸的问题，提出在DTW 中引入分段聚合与相似度阈值，降低计算量的同时提高算法鲁棒性；提出面积距离度量，从宏观结构角度度量序列相似性。二者结合，进一步提高算法精度，与现有方法对比，ANDTW 平均错误率降低了23.3%，在ECG200 数据集上与PAA、DTW 比较，展现出了更高的鲁棒性。但面积度量存在序列长度必须相等的局限，DTW 在动态规划方法中耗时问题未从算法层面得到解决，这两点是下一步任务中研究的重点。