开放科学（资源服务）标志码（OSID）：

0 概述

时间序列是当前非常普遍且与时间相关的高维数据，是目前生活中比较常见的一种数据类型^[1]，同时也是数据挖掘领域中主要的研究对象，它广泛存在于金融股票、航天气象、医疗诊断分析等领域中^[2]。时间序列的相似性度量用来衡量不同时间序列之间的相互关系，从中挖掘有用信息并将其结果用于分类、聚类、模式发现等方面，使其更好地应用于社会生产实践。例如在医疗服务行业中，通过对医疗检测数据所形成的时间序列（如心电图数据）进行分类研究，可以发现具有相同或相似的患者在身体机能方面的“共性”变化趋势，在此基础上研究并制定更加合理的治疗方案，实现智慧医疗。相似性度量是数据挖掘相关领域研究的基础和前提，其度量效果将直接影响后续时间序列聚类、分类等相关研究的精度。因此，针对时间序列数据的相似性度量已经成为时间序列数据挖掘领域相关研究的热点之一^[3]。

时间序列是在一定的时间内记录一个或多个属性伴随时间变化的数据，对具有单个属性采样得到的序列称为一元时间序列（UTS），对具有多个属性采样得到的序列称为多元时间序列（MTS）^[4]。目前对一元时间序列的研究相对较多，已逐渐形成了较为成熟的理论和方法，而多元时间序列的理论和方法尚不完善^[5]。多元时间序列由多个不同的变量维度组成，其结构比单一变量复杂得多，如果只是看成多个变量维度的简单叠加，则容易忽略变量的内在相关性及变量序列的形态特性，导致相似性度量不准确，尤其是对具有强内在相关性的多元时间序列数据。而在现实生活中，多元时间序列更为常见，例如：股票的涨跌变化趋势受多种因素的影响^[6]；医学中患者某个疾病的确诊一般也是通过多个生理指标共同体现出来；某地的天气状况一般要考虑温度、湿度、气压等因素。因此，对多元时间序列的研究更具有重要的理论和现实意义。多元时间序列具有的高维、复杂、动态、高噪声等特性，如果直接对原始数据进行相关研究，将产生挖掘结果不准确、时间效率低下以及研究结论可信度较低等问题^[7]。因此，在进行相似性度量之前，需要对多元时间序列进行特征表示，提取多元时间序列的主要特征，利用转换后的特征代替原始数据进行数据挖掘任务。

相似性度量是时间序列聚类和分类研究中必不可少的关键步骤，其作用是对时间序列的变化、形状和距离进行相似性度量，针对不同领域数据的序列特征将有其相适应的相似性度量函数^[8]。目前针对MTS常见的的相似性度量方法主要有欧式距离（Euclidean Distance，ED）^[9]和动态时间弯曲距离（Dynamic Time Warping，DTW）^[10]距离。欧式距离具有计算简单、时间复杂度低的优点，但只能度量长度相同的时间序列，而且对时间序列形态变化很敏感，不能辨别序列之间的形状相似性，无法反映趋势动态变化幅度的相似性。动态时间弯曲距离是基于动态规划的思想，避免了欧氏距离存在的不足，不仅能够避免欧氏距离一对一匹配的问题，而且通过扭曲序列实现了时间序列之间“一对多”的映射，因此，可以对任意等长或不等长时间序列进行相似性度量，并且DTW对时间序列偏移、幅度变化等情况也有很强的鲁棒性。然而，DTW不仅时间复杂度高，在相似性匹配过程中也容易出现因一味地追求最小距离而对时间序列过渡的拉伸或压缩的现象，从而影响度量精度。

目前关于相似性度量方法的改进大多是基于动态时间弯曲展开的，一般包括对计算效率的改进、算法度量精度的提升以及与其他方法融合的改进等。文献[11]提出趋势距离（TD）方法，首先通过对全部变量进行提取特征，然后进行分段和特征拟合，提取分段区间的斜率、长度作为特征，最后使用DTW距离度量特征矩阵之间的距离，在多个数据集上都取得了较好的度量结果，但当数据规模较小、序列趋势变化不明显时，效果不佳。之后，文献[12]又提出分段线性拟合的动态时间弯曲相似性度量（PLR-DTW），使用DTW对多维分段拟合后的时间序列进行度量，在数据规模大、连续性变量的序列上具有较好的效果，但实验结果受参数的选择影响较大。此外，由于只选取了分段的均值作为原始序列的特征表示，并不能体现出序列的趋势特征，因此应用范围有限。DTW在计算多元时间序列最佳弯曲路径时，虽能较好地反映时间序列形态变化问题，但在寻求最小弯曲路径的过程中容易出现不合理的匹配使得序列过渡压缩和拉伸，从而影响度量精度。

针对DTW计算复杂度高及在匹配的过程中出现过度拉伸和压缩的问题，本文提出一种基于分段特征及自适应加权的DTW相似性度量方法。首先对原始时间序列在各个变量维度上进行整体分段，选取分段区间的斜率、最大值、最小值以及时间跨度作为每一段的特征表示，分段特征表示不仅可以实现对原时间序列的大幅降维，还可以较为准确地体现序列的值域和形态特征。然后使用分段后的时间序列特征矩阵进行相似性度量，以大幅降低计算复杂度，提高计算效率。在DTW计算最佳弯曲路径的过程中为每个点设置代价权重来限制序列中点列的重复使用次数，改善序列一对多的情形。

1 多元时间序列分段和特征表示

一种高效的时间序列特征表示方法能大幅提高时间序列数据挖掘的效率^[13]。由于时间序列一般具有时序变化、数值差异及形态多样性的特性，因此可以用$ X=\left\{{x}_{i}\left(t\right)\right\}，i=\mathrm{1, 2}, \cdots , m, t=\mathrm{1, 2}, \cdots , n $表示。当m=1时表示UTS，当m≥2时表示MTS。由于一般原始时间序列数据具有海量性和复杂性^[14]，因此需要对多元时间序列进行分段特征表示，提取序列的特征信息，对数据进行降维以降低存储成本和计算成本。一个简单的做法是：将1个MTS分解成多个UTS，再对每个一元时间序列进行分段特征表示。但这种方法忽略了MTS中各变量之间的相关性，因为事物状态的刻画往往需要多个变量共同确定，并且变量之间通常存在一定的相关性，多元时间序列不能看作是多个单变量时间序列的简单叠加^[15]。因此，在对多元时间序列分段时，需要同时在所有变量维度上进行分段操作，这样可以避免将各个变量割裂开来，保持了分段后变量之间的相关性。本文将采用基于误差的自底向上分段方法^[16]对多元时间序列进行多维分段拟合，首先将长度为n的序列分成n/2段，接着递归地计算2个相邻分段合并后的拟合误差，然后继续合并拟合误差最小的相邻分段，当全部的拟合误差都大于给定的阈值时停止合并。

设多元时间序列有M个变量维度，P_m表示第m维变量在包含I个数据点分段上的拟合线段，则第m维变量在当前分段的拟合标准差定义为：

$ \cos_{}{t}_{m}=\sqrt{\sum\limits_{i=1}^{I}{\left|{x}_{i}-{p}_{m}\right|}^{2}}, m=\mathrm{1, 2}, \cdots , M $

(1)

评估M维的拟合误差，对所有变量的拟合标准误差进行加权求和，即可得到当前分段的拟合标准误差：

$ \cos t= \sum\limits_{m=1}^{M}{\omega }_{m} {\cos t}_{m} $

(2)

由于不同变量的量纲和特征存在差异，在模式匹配中的重要性也不完全相同，因此式（2）在计算拟合段的总误差时，加入了变量维度的权重系数。$ {\omega }_{m} $表示第m个变量的误差权重值，且满足$ \sum\limits_{m=1}^{M}{\omega }_{m}=1 $。这里计算的分段拟合标准误差是在全部变量上的总误差，以达到多维分段的目的。

在对多元时间序列进行多维分段线性拟合后，拟合线段的斜率和时间跨度反映了原始序列的形态特征，分段上所有数据点的最大值最小值反映了原始序列的值域特征，因此，选择拟合线段的斜率k、分段区间内的最大值E、最小值e以及分段时间跨度d作为某一变量维度上一个分段的特征。当一个含有M个变量的序列被分成N段时，该序列可用如下特征矩阵表示：

$ \begin{array}{l}\boldsymbol{X}=\left\{\right({k}_{i1}, {E}_{i1}, {e}_{i1}, {d}_{i1}), ({k}_{i2}, {E}_{i2}, {e}_{i2}, {d}_{i2}), \cdots , \\ ({k}_{iN}, {E}_{iN}, {e}_{iN}, {d}_{iN}) \} , i=\mathrm{1, 2}, \cdots , M\end{array} $

(3)

在度量2条多元时间序列相似性时，为了消除不同特征之间的量纲差异对度量结果带来的影响，需要对特征矩阵进行标准化处理，对斜率k、最大值$ E $、最小值$ e $和时间跨度d的标准化方法分别如式（4）~式（7）所示：

$ \begin{array}{l}{\alpha }_{ij}=\arctan k_{ij}, {\alpha }_{ij}\in (-\mathrm{\pi }/2, \mathrm{\pi }/2), \\ i=\mathrm{1, 2}, \cdots , M, j=\mathrm{1, 2}, \cdots , N\end{array} $

(4)

$ {A}_{ij}=\frac{{E}_{ij}-\min(E, e)}{\max(E, e)-\min(E, e)} $

(5)

$ {a}_{ij}=\frac{{e}_{ij}-\min(E, e)}{\max(E, e)-\min(E, e)} $

(6)

$ {s}_{i}=\frac{{d}_{i}}{\sum\limits_{j=1}^{N}{d}_{i}}, {s}_{i}\in \left(\mathrm{0, 1}\right] $

(7)

其中：式（4）将斜率转化为角度；式（5）和式（6）将值域特征归一化；式（7）将时间跨度转化为时间跨度与时间长度的比值。在标准化处理后，得到转换后的特征矩阵如式（8）所示：

$ \begin{array}{l}\boldsymbol{X}\text{'}=\left\{\right({\alpha }_{i1}, {A}_{i1}, {a}_{i1}, {s}_{i1}), ({\alpha }_{i2}, {A}_{i2}, {a}_{i2}, {s}_{i2}), \cdots , \\ ({\alpha }_{iN}, {A}_{iN}, {a}_{iN}, {s}_{iN}) \} , i=\mathrm{1, 2}, \cdots , M\end{array} $

(8)

多维分段特征表示不仅保留了特征间的关联性，而且达到了降维的目的。

2 基于自适应的动态时间弯曲距离

在时间序列数据分段线性特征表示完成后，特征矩阵即可看作原始多元时间序列在多维分段之后的特征序列，将以前针对点和点的相似性度量方法用于子段和子段之间，该处理方法大幅降低了计算复杂度，减少了计算时间。经过特征提取和转换后，多元时间序列特征矩阵的行数是相同的，即它们的变量维度是一一对应的关系；由于分段数量可能不同，矩阵的列数不同即序列的长短不一。DTW能通过对时间轴的弯曲解决2个不等长序列之间相似性度量的问题，因此可以用于特征矩阵之间的比较。本文以每段的特征值作为输入值，利用动态时间弯曲来度量2条序列的相似度。

DTW在计算多元时间序列最佳弯曲路径时，虽能通过动态弯曲体现序列形态特征，但是为了获得最小的累积距离，DTW距离可能会将一个时间序列上的多个点映射到另一个时间序列上的一个点，出现不合理的匹配。这使得时间序列过度拉伸和压缩，导致重要的特征信息丢失，因此为了追求最小距离使时间序列过渡扭曲，将无法精准得测量2条时间序列的距离，从而影响度量的精度，如图 1所示。

本文提出基于分段特征及自适应加权的多元时间序列相似性度量（ASW-DTW）方法。该方法为每个序列点赋予代价权值，并且该权值是在计算过程中自行确定的，无需增加额外的计算成本。在动态规划求解最佳弯曲路径的过程中，自适应地调整每个点的权值，使得特征点使用次数愈多，权重系数值愈大。在后文计算匹配路径的过程中将有选择地使用这些点，从而有效减少重复点的使用次数。

对于经过特征提取和标准化处理之后的特征矩阵，可以使用$ \boldsymbol{X}=[{x}_{1}, {x}_{2}, \cdots , {x}_{N}] $来表示，其中，x_i表示多维分段后第i个拟合段上M个变量的特征信息，其可以看作DTW距离中的一个序列点。2个多元时间序列特征矩阵X和Y中的2个拟合段$ {x}_{i}\mathrm{、}{y}_{j} $第m维变量之间的距离为：

$ {d}_{m}=\beta \left|{\alpha }_{mi}-{\alpha }_{mj}^{\mathrm{\text{'}}}\right|+\lambda \left\{\frac{1}{2}\left|{A}_{mi}-{A}_{mj}^{\mathrm{\text{'}}}\right|+\left|{a}_{mi}-{a}_{mj}^{\mathrm{\text{'}}}\right|\right\}+\gamma \left|{s}_{i}-{s}_{j}^{\mathrm{\text{'}}}\right| $

(9)

由于在度量2个拟合段之间的距离时，不同特征的权重不同，因此要为每个特征赋予权重以突出不同特征的重要性，且权重参数满足：

$ \beta +\lambda +\gamma =1 $

(10)

则2个拟合段上DTW中的基础距离定义为：

$ {d}_{\mathrm{b}\mathrm{a}\mathrm{s}\mathrm{e}}=\sum\limits_{m=1}^{M}{\omega }_{m}{d}_{m} $

(11)

多元时间序列不同变量维度代表的意义不同，重要性也有所差异，因此在比较时对不同变量分配不同的权重。其中$ {\omega }_{m} $表示第m个变量的权重值，且所有变量的权重和为1，即$ {\omega }_{m} $的值满足：

$ \sum\limits_{m}^{M}{\omega }_{m}=1 $

(12)

在ASW-DTW距离中，第i个拟合段的自适应代价权重定义如下：

$ {c}_{i}\left(t\right)=k\cdot r\cdot {\mathrm{e}}^{t} $

(13)

其中：k是一个正参数，用来调整代价函数$ {c}_{i}\left(t\right) $的效果，k值越大，$ {c}_{i}\left(t\right) $的效果越强，k值越小，$ {c}_{i}\left(t\right) $的效果越弱；t表示每个点在时间序列中使用的次数，因此代价函数与t成正比，即当t较大时，代价函数也较大。同时，考虑到当2条序列长度不同，特别是长度差异明显时，多对1的情况将会更普遍，此时对畸形匹配的容忍度应该较大，因此引入序列的长度比值r，其定义如下：

$ r=\frac{\min(N, N\text{'})}{\max(N, N\text{'})} \left\{\begin{array}{c}=1, N=N\text{'}\\ < 1, N\ne N\text{'}\end{array}\right. $

(14)

其中：N和$ N\text{'} $分别表示2条序列的长度。当2条序列的长度差异越大时，即r越小，代价权重$ {c}_{i}\left(t\right) $的衰减速率也就越小。

引入代价权值信息之后，采用动态规划计算2条多元时间序列之间的ASW-DTW距离，计算公式如下：

$ \begin{array}{l}{A}_{\mathrm{A}\mathrm{S}\mathrm{W}\mathrm{⁃}\mathrm{D}\mathrm{T}\mathrm{W}(i, j)}=\\ \min\left\{\begin{array}{l}\mathrm{①}{c}_{i}\left(t\right)\cdot {b}_{\mathrm{b}\mathrm{a}\mathrm{s}\mathrm{e}}({x}_{i}, {y}_{j})+{A}_{\mathrm{A}\mathrm{S}\mathrm{W}\mathrm{⁃}\mathrm{D}\mathrm{T}\mathrm{W}(i, j-1)}\\ \mathrm{②}{b}_{\mathrm{b}\mathrm{a}\mathrm{s}\mathrm{e}}({x}_{i}, {y}_{j})+{A}_{\mathrm{A}\mathrm{S}\mathrm{W}\mathrm{⁃}\mathrm{D}\mathrm{T}\mathrm{W}(i-1, j-1)}\\ \mathrm{③}{c}_{j}\left(t\right)\cdot {b}_{\mathrm{b}\mathrm{a}\mathrm{s}\mathrm{e}}({x}_{i}, {y}_{j})+{A}_{\mathrm{A}\mathrm{S}\mathrm{W}\mathrm{⁃}\mathrm{D}\mathrm{T}\mathrm{W}(i-1, j)}\end{array}\right.\end{array} $

(15)

ASW-DTW算法是在原DTW算法的基础上增加了自适应的动态权值。该算法用于寻找2条序列上每个点之间的最优对齐匹配关系，对于长度分别为m、n的2条时间序列X、Y之间的匹配关系可以用弯曲路径$ S=\{{s}_{1}, {s}_{2}, \cdots , {s}_{\mathrm{K}}\} $表示，一般情况下存在着多条弯曲路径，有效的弯曲路径必须满足以下3个条件：

1）边界性：$ {s}_{1}=\left(\mathrm{1, 1}\right) $，$ {s}_{K}=(m, n) $。

2）单调性：给定$ {s}_{k}=(i, j) $和$ {s}_{k+1}=(i\text{'}, j\text{'}) $，有$ i\text{'}\ge i, $$ j\text{'}\ge $。

3）连续性：给定$ {s}_{k}=(i, j) $和$ {s}_{k+1}=(i\text{'}, j\text{'}) $，有$ i\text{'}\le i+1, j\text{'}\le j+1 $。

选取弯曲路径中连续元素的基础距离之和，可得到该路径的累积距离。在式（15）中，ASW-DTW（i，j）表示第i个拟合段和第j个拟合段之间的ASW-DTW累计距离，且ASW-DTW（1，1）=d_base（x₁，y₁）；c_i（t）表示了第i个拟合段当前的权重，即当某点被重复使用时，赋给基础距离一个与该点使用次数有关的权重。通过上式不断迭代以判断下一步的走向，使得累计距离最小，以便得到最优弯曲路径。

当ASW-DTW取值为①时，表示引入代价权重的动态时间弯曲下的最优路径选择经过$ ({x}_{i}, {y}_{j-1})\to $ $ ({x}_{i}, {y}_{j}) $，即点$ {x}_{i} $被重复使用，则对$ {x}_{i} $增加权重，增大该路径的距离。

当ASW-DTW取值为②时，表示引入代价权重的动态时间弯曲下的最优路径选择经过$ ({x}_{i-1}, {y}_{j-1})\to $ $ ({x}_{i}, {y}_{j}) $，即没有点被重复使用。

当ASW-DTW取值为③时，引入代价权重的动态时间弯曲下的最优路径选择经过$ ({x}_{i-1}, {y}_{j})\to $ $ ({x}_{i}, {y}_{j}) $，即$ {y}_{j} $被重复使用，则对$ {y}_{j} $增加权重，增大该路径的距离。

综上所述，采用ASW-DTW算法计算2条多元时间序列之间的最优弯曲距离步骤如下：

1）对多元时间序列进行多维分段特征表示，标准化处理后，得到如式（8）的特征矩阵。

2）以特征矩阵作为ASW-DTW算法的输入，计算特征矩阵之间的动态弯曲距离。详细算法如下：

算法1  ASW-DTW距离度量算法

输入  时间序列$ \boldsymbol{X}=[{x}_{1}, {x}_{2}, \cdots , {x}_{N}], \boldsymbol{Y}=[{y}_{1}, {y}_{2}, \cdots , $ $ {y}_{N\text{'}}], $特征矩阵每个变量权重$ {\omega }_{n} $，趋势、值域特征、时间跨度差异权重β、λ、γ，拟合段权重衰减速率k

初始化  根据式（3）~式（8）将原始多元时间序列X和Y进行多维分段和特征表示处理；定义拟合段初始权值矩阵$ {\boldsymbol{C}}_{\boldsymbol{X}}=[{c}_{1}^{}, {c}_{2}^{}, \cdots , {c}_{N}^{}], {\boldsymbol{C}}_{\boldsymbol{Y}}=[{c}_{1}^{\mathrm{\text{'}}}, {c}_{2}^{\mathrm{\text{'}}}, \cdots , {c}_{N\text{'}}^{\mathrm{\text{'}}}] $各项权值初始值为1；定义累计距离矩阵ASW-DTW，ASWDTW（1，1）=D_base（1，1）

输出  多元时间序列X和Y之间的ASW-DTW距离

1.利用式（14）计算序列长度比值r；

2.利用式（11）计算基础距离矩阵D_base；

3.for i =1：N

4. for j =1：$ \mathrm{N}\mathrm{\text{'}} $

5. $ {\mathrm{d}}_{1}={\mathrm{D}}_{\mathrm{b}\mathrm{a}\mathrm{s}\mathrm{e}}(\mathrm{i}, \mathrm{j})\times {\mathrm{c}}_{\mathrm{i}}+\mathrm{A}\mathrm{S}\mathrm{W}\mathrm{D}\mathrm{T}\mathrm{W}(\mathrm{i}, \mathrm{j}‒1); $

6. $ {\mathrm{d}}_{2}={\mathrm{D}}_{\mathrm{b}\mathrm{a}\mathrm{s}\mathrm{e}}(\mathrm{i}, \mathrm{j})+\mathrm{A}\mathrm{S}\mathrm{W}\mathrm{D}\mathrm{T}\mathrm{W}(\mathrm{i}‒1, \mathrm{j}‒1); $

7. $ {\mathrm{d}}_{3}={\mathrm{D}}_{\mathrm{b}\mathrm{a}\mathrm{s}\mathrm{e}}(\mathrm{i}, \mathrm{j})\times {\mathrm{c}}_{\mathrm{j}}+\mathrm{A}\mathrm{S}\mathrm{W}\mathrm{D}\mathrm{T}\mathrm{W}(\mathrm{i}‒1, \mathrm{j}); $

8. $ \mathrm{A}\mathrm{S}\mathrm{W}\mathrm{D}\mathrm{T}\mathrm{W}=\min({\mathrm{d}}_{1}, {\mathrm{d}}_{2}, {\mathrm{d}}_{3}); $

9. if d₁ == ASWDTW（i，j）do

10. $ {\mathrm{c}}_{\mathrm{i}}={\mathrm{c}}_{\mathrm{i}}\times \mathrm{e} $

11. else if d₂ == ASWDTW（i，j）do

12. $ {\mathrm{c}}_{\mathrm{i}}={\mathrm{c}}_{\mathrm{i}} , {\mathrm{c}}_{\mathrm{j}}={\mathrm{c}}_{\mathrm{j}} $

13. else

14. $ {\mathrm{c}}_{\mathrm{j}}\mathrm{\text{'}}={\mathrm{c}}_{\mathrm{j}}\mathrm{\text{'}}\times \mathrm{e} $

15. end if

16. end for

17.end for

18.return $ \mathrm{A}\mathrm{S}\mathrm{W}\mathrm{D}\mathrm{T}\mathrm{W}(\mathrm{N}, \mathrm{N}\mathrm{\text{'}}) $

3 实验 3.1 实验环境

编译工具Python3.6.0，操作系统Windows8，CPU/Intel^® Core^TM i5-3337U双核处理器，主频1.8 GHz，内存8 GB，硬盘容量1T。

3.2 实验数据与实验方法

为了便于比较时间序列通过相似性度量的聚类性能，本文选取UCI数据集中已知分类结果的多元时间序列作为研究对象，采用k-近邻的方法进行聚类实验。选用Australian Sign Language（ASL）^[17]、EEG^[18]、Robot Execution Failure（REF）^[19]和Japanese Vowels（JV）^[20]4组数据集进行实验，其中：ASL是包含22个特征的手语信号数据集，选择前8种语意对应的216个序列作为实验数据集；EEG是采集了2类人群（alcoholic和control）的脑电图数据，选取前2位测试者的前11次测试作为实验数据；REF是对机器进行故障采集的数据集，采样周期为21 ms，包含6个离散型变量，该数据集包含5个子数据集，实验选取第1个子数据集LP1进行实验，已知LP1数据集分为4类，共有88个样本，样本属于6×15的矩阵，属于时间跨度较小、体现某些状态点的多元时间序列；JV用12个变量刻画了日文元音的发音过程，包含9个测试者的发音数据，每个测试者发音30次，共270个样本。序列长度范围为7~29，属于小规模的多元时间序列。数据集基本信息如表 1所示。

实验采用留一交叉验证结合k-近邻法。首先对具有n个序列的数据集进行特征提取，从中选取1个序列x作为输入序列。然后采用某种相似性度量方法找出与x最相似的k个序列（k分别取1、5和10）。在找出的k个序列中，计算与x同类的序列个数n₀，计算分类准确率为：

$ {\delta }_{i}=\frac{{n}_{0}}{k} $

(16)

对于数据集中其他多元时间序列，依次作为输入序列，可以得到n个相似性度量的准确率。计算平均准确率为：

$ \delta =\frac{1}{n}\sum\limits_{i=1}^{n}{\delta }_{i} $

(17)

并将其作为度量有效性的比较依据。

在ASW-DTW距离度量中，度量结果是由数据点之间的基础距离累计的结果，并且由式（9）可知，参数β、λ、γ的选择也将直接影响到多元时间序列基础距离的度量。因此，为了确定最佳参数组合，本文以ASL数据集为例，选择不同的β、λ、γ，使用KNN分类讨论不同的参数选择对算法准确度的影响，最终找到最佳参数组合，提高度量精度。这里，k取值为5，即使用基于ASW-DTW距离度量的KNN方法从测试集中找出5个与输入序列距离最近的序列，计算评均准确率。为了不失一般性，先假设各个变量的重要性相同，即各个变量维度上的权重$ {\omega }_{m} $相等，在变量维度上不存在差异。在分段拟合标准误差cost取0.03时，权重衰减速率k取值0.05。分别在分段特征参数β、λ、γ取不同值的情况下，计算平均查准率。由于在2个参数确定的情况下满足式（10）的条件，第3个参数将是确定的，因此γ值并未直接给出，例如当β=0.0、λ=0.0时，则有γ =1.0。不同参数下的平均查准率如图 2所示。

从图 2可知，当$ \beta =0.6\mathrm{、}\lambda =0.3\mathrm{、}\gamma =0.1 $时，平均查准率最高，达到0.94。可以看出，在β取值较低时，查准率随着λ的增大而增大，说明在不注重序列趋势差异时，序列的值域差异对距离度量的影响占主导地位，同时，图 2中最前侧一列（λ=0）的查准率均比其他列低，也说明了序列之间值域差异在度量序列距离时的重要性。实验结果表明，将值域特征加入到多元时间序列特征的必要性。

为了验证ASW-DTW算法在多元时间序列相似性度量时的准确性，本文分别在4个数据集上进行实验对比，分别基于ASW-DTW、DTW、PD、TD和SVD的KNN算法在进行相似性查找时的平均准确率。针对每个数据集，均选择最优的参数组合，参数确定方法同实验1，参数选择结果如表 2所示。

每种方法分别取k =1，5，10，将数据集中每个数据依次作为测试数据输入，并计算平均准确率，实验结果如表 3~表 6所示（粗体表示最优值）。

3.3 实验结果分析

由表 3~表 6在4种数据集上分别用5种度量方法的平均准确率可以看出，不同k值下的ASW-DTW方法在4个数据集上均能取得不错的平均准确率，特别是在ASL和EEG数据集上明显优于PD方法和SVD方法。并且可以看出ASW-DTW相比于DTW，平均准确率有一定幅度的提升，说明在这2个数据集上，DTW的畸形匹配问题影响了距离度量结果，而自适应代价权重DTW有效地避免了该问题。在REF-LP1和JV这样的小规模数据集上，ASW-DTW依然能取得不错的结果。在这2个数据集上，ASW-DTW算法相对于DTW的结果提升不大，原因在于：ASW-DTW算法在改善2条时间序列多对一的过渡匹配时，与数据集本身的特点密切相关，说明在这2个数据集上序列没有出现过渡的拉伸或压缩。同时注意到，由于JV数据集序列长度较小，趋势变化不明显，TD算法的度量结果较差，TD算法已经丧失了其有效性，但通过表 6可知，ASW-DTW仍能通过减小趋势差异权重，增加值域特征差异权重的方式取得较好的度量结果。

3.4 计算复杂度比较

对于序列长度分别为m和n的2条时间序列X和Y，由于DTW距离需要在m×n的矩阵上寻找最优弯曲路径，因此计算复杂度为O（m×n）。假设对X、Y时间序列进行多维分段和特征表示后，长度分别为m'和n'，则分段后的时间序列进行相似性度量的计算复杂度为O（m'×n'）。由此可知，计算复杂度主要取决于时间序列特征的长度，可用式（18）比较算法的计算复杂度：

$ \eta =\frac{m\text{'}n\text{'}}{m n} $

(18)

对于给定的数据集，本文使用特征序列的平均压缩率（CR）的平方来近似表示式（18）中的η，近似比较DTW与ASW-DTW方法的计算复杂度，结果如表 7所示。

此外，为了更精准地比较计算复杂度，分别记录ASW-DTW和DTW的计算时间，并利用它们的时间比来比较计算复杂度，如图 3所示。

实验数据对比结果表明，特征序列压缩率的平方CR²可近似比较算法的计算复杂度。由于时间序列在进行分段特征表示后，特征序列长度小于原时间序列，并且结合表 7和图 3可以看出，基于分段特征的时间序列进行相似性度量能较大幅度地降低计算复杂度。

4 结束语

针对DTW寻找路径过程中时间复杂度高且容易出现一对多情形，本文提出一种基于分段加权特征的多元时间序列相似性度量方法。对原始时间序列在各个变量维度上统一进行分段，选取分段后拟合线段的斜率、分段区间的最大值和最小值以及时间跨度作为多元时间在序列的特征表示，比较准确地刻画出多元时间序列不同时刻的趋势和值域信息，实现对原时间序列的大幅降维。针对DTW算法在相似性度量过程中追求最小距离容易出现一对多的情形，本文对每个点赋予代价权重，在匹配过程中通过赋给基础距离自适应代价权重来限制序列中点列的使用来减少不合理匹配情况，以此改善DTW中时间点过度拉伸或压缩以达到较好的匹配效果。实验结果表明，预处理后的时间序列明显减小了算法的计算复杂度，提高了计算效率。因此，基于分段特征的ASW-DTW不仅降低了计算复杂度，而且在多个数据集上能取得较高的查准率，并且该方法可以通过调整拟合特征值的权重来适应不同的数据集。下一步将研究根据变量的重要性对变量的权重进行选择，通过优化模型参数选择方法，将ASW-DTW方法以最优的参数组合应用在各个领域的多元时间序列数据挖掘任务中。