时序对齐, 包括基于欧氏距离(euclidean distance, 简称ED)或动态时间扭曲(dynamic time warpping, 简称DTW)的时序对齐策略, 是一种根据时间序列相似性或非相似性度量来连接或匹配时间序列, 提供时序度量的方法.它在时间序列分类、聚类以及分析等领域起着至关重要的作用^[1-4], 被广泛应用于姿势识别^{[3, 5-7]}、手写字符识别^[8]、音乐信息校准^{[9, 10]}、语音识别^{[11, 12]}、基因序列比对^[13]等领域.

基于ED的对齐策略是一种线性映射, 而DTW是非线性映射, 它用于寻找两个序列之间的最优对齐方式, 基于DTW的k近邻分类器(k-nearest neighbor, 简称kNN)也是当前用于时间序列分类的最好算法之一, 它已被成功地应用于分类那些类内具有全局相似性, 并有较大范围时间延迟的时间序列.但是在某些实际应用中, DTW不能有效处理那些类内具有不同全局特性而类间具有相似全局特性的复杂的时间序列, 其原因主要在于以下两个方面:(1)传统DTW是一种按照逐对时间序列来逐步比较的对齐策略(pairwise alignment), 它忽视了同类或异类时间序列间的关联性; (2) DTW赋予对齐序列的每一维度同样的权值, 并且对齐过程未能有效利用其他数据分析方法(如聚类、分类等), 因此削弱了其处理复杂时间序列数据的能力.

例如, 图 1展示了真实电力消费数据的样本, 此数据记录了某个家庭中几乎一年(共349天)的电力消耗情况.其中, 每条时间序列均记录了某一天的电力消耗情况(每10min采样一次, 长度为144).若其在耗电高峰期(如晚6点~8点, 图中范围[108, 120])的耗电量低于年平均消耗水平, 类标记为Low; 相应的类标记为High的时间序列表示其在用电高峰期的耗电量高于年平均水准.从图中可以很明显地观察到:对于Low与High两类复杂时间序列, 同类耗电量序列数据间的全局特性有很大的不同, 两个类别的主要区别在于[108, 120]间的子序列, 而传统DTW无法找到不同类别间的局部辨别性特征.

近年来, 研究者已提出了多种DTW的改进方法, 并将其应用到时间序列分类或聚类问题中.它们大多集中于定义更好的限制策略、全局的或半全局的加权方法等.例如, 第1种改进方式主要依赖于Sakoe-Chiba^[11]或Itakura^[14]来限制DTW的对齐空间, 或者通过预处理时间序列, 比如获取高阶形状特征^[15]、平均化时间序列^[16]、通过多层次方法近似求解DTW最优路径^[17]等, 加快DTW的计算效率.第2种改进方式主要集中于定义全局的加权策略.比如, Jeong等人^[18]提出了一种基于Sakoe-Chiba限制的加权策略, 其根据DTW代价矩阵定义了一种递增函数, 用于赋予离对角线近的点较低的权值、离对角线远的点较高的权值.另一个例子来自姿势识别领域, Reyes等人^[6]提出了一种根据DTW均值来计算类内和类间的方差, 并将所得权值赋予所有姿势类别的加权策略.第3种方式是一种半全局加权策略^{[5, 19]}, 它也是Reyes等人^[6]所提出的算法的扩展, 其主要区别在于为每一个姿势类别的时间序列赋予不同的权值.

上述工作能够产生比较准确的时序对齐方式, 但仍存在缺点, 比如赋予所有类别或时间点(time stamp)相同的权值(全局加权策略); 缺乏对类内以及类间局部不同行为特性的考虑; 辨别性子序列通过标准DTW学得, 而DTW平等地对待每一个特征; 权值并没有随着时间的推进而改变等.在实际复杂时间序列中, 很容易见到时间序列的某一片段明显区别于其他地方的情况, 所以不同的时间点应赋予不同的权值.换言之, 为发现时间序列的局部辨别性特征, 需要定义一种局部加权策略, 赋予每一条时间序列的每一个时间点不同的权值.Frambourg等人^[2]对此具有挑战性的问题进行了初步讨论.它依赖于方差/协方差矩阵来增强或削弱对齐关系, 但由于其需要大量的矩阵运算, 导致其在面对大规模数据时效率大幅下降.

尽管基于时序对齐的kNN是时间序列分类领域最成功以及最广泛使用的分类器, 但kNN对噪音敏感, k值的变化很容易引起已预测类标的变化, 特别是当异类的数据间具有相同的全局特征时, 此情况更易发生.另外, 由于kNN是一个懒惰式的分类器, 它不像贝叶斯网络或者决策树那样具有明显的可解释性.

为了解决上述问题, 本文提出一种具有辨别性的基于局部加权DTW的时间对齐方式, 并将其应用于kNN中.所提出的加权方法通过迭代学习最近的同类和异类序列的多步对齐(multiple alignments)来获取辨别性特征.它能够在增大类间方差的同时降低类内方差, 并提高分类准确率.主要工作可总结为以下几点.

(1) 提出一种有效的时间序列局部加权模型, 为每一条时间序列的时间点提供权值, 并通过属性局部权重发现辨别性子序列;

(2) 通过将所提出的算法和其他基于非相似性度量的kNN分类器以及基于Shapelets的决策树相比较, 展示了其可解释性;

(3) 将所提出的模型扩展至多变量时间序列分类问题, 并讨论了其特殊情况, 即加权ED的有效性;

(4) 通过在多个复杂时间序列上与多个方法的对比, 展现所提出模型在时间序列分类问题上的准确性.

本文第1节介绍序列对齐的背景知识.基于DTW的时间序列局部加权模型及其学习算法将在第2节和第3节详细介绍.第4节通过实验评价所提出模型在多个数据集(包括单变量和多变量时间序列)上的分类效果.第5节通过在多个人工数据集和真实数据集上的实例解析, 阐释所提出模型的可解释性.最后进行本文工作总结.

1 背景知识

定义 1(时序对齐).对于一个包含有N个单变量离散时间序列的数据集X={x₁, x₂, …, x_N}, 每一条时间序列x={x₁, x₂, …, x_T}的长度为T.两个时间序列x_i与x_j之间的一个对齐排列π的长度为|π|=m(T≤m≤2T-1), 它是由x_i与x_j的对齐点所组成的, 即π=((π₁(1), π₂(1)), (π₁(2), π₂(2)), …, (π₁(m), π₂(m))), 其中, 定义在1到m的成对π₁和π₂遵循以下限制边界和单调性条件.

(1) 1=π₁(1)≤π₁(2)≤…≤π₁(m)=T;

(2) 1=π₂(1)≤π₂(2)≤…≤π₂(m)=T;

(3) ∀l∈{1, …, m-1}, π₁(l+1)≤π₁(l)+1, π₂(l+1)≤π₂(l)+1, (π₁(l+1)-π₁(l))+(π₂(l+1)-π₂(l))≥1.

如图 2所示, 基于ED的时序对齐是一对一映射, 两条时间序列间x_i与x_j的ED时序对齐如矩阵的对角线所示.而基于DTW的时序对齐可以是一种一对多的非线性映射, 比如x_i的第13个采样点可以与x_j的第14个~第17个这4个点相关联, 其映射的起点与终点固定, 分别为(1, 1)和(T, T).

另外, 定义$ \mathcal{A} $为两个序列间所有对齐排列的组合, y为时间序列x的类标.本文中所涉及的符号见表 1.

2 时间序列局部加权模型

本文介绍的局部加权模型综合了Frambourg等人介绍的方差/协方差对齐模型和Weinberger等人提出的最大化边际度量学习算法的优点^[20].为了计算每一条时间序列每一个采样点的权值, 对每一个x, 计算其两个集合cNN⁺和cNN^-(分别称为正例集和负例集), 它们分别由x的c个距离最近的同类别时间序列和不同类别时间序列组成.如图 3所示, cNN⁺和cNN^-都是从训练集中得到的.

注意:本文中定义的正例集和负例集不同于Weinberger等人提出的目标集(targets)和入侵集(impostors), 其中, 入侵集指的是侵入到目标集范围内的不同类别的实例, 而正例集和负例集之间不存在此限制.相应地, 对时间序列x_i的每一个采样点t, 其对应于两个集合x_it⁺和x_it^-, 定义为

$ \begin{array}{l} \mathit{\boldsymbol{x}}_{it}^ + = \{ t'/(t,t') \in {\pi _{ii'}},{\mathit{\boldsymbol{x}}_{i'}} \in {\rm{cNN}}_i^ + \} ,\\ \mathit{\boldsymbol{x}}_{it}^ - = \{ t'/(t,t') \in {\pi _{ii'}},{\mathit{\boldsymbol{x}}_{i'}} \in {\rm{cNN}}_i^ - \} , \end{array} $

其中, π_ii'是x_i和x_i'之间的标准DTW对齐排列, cNN_i⁺和cNN_i^-是x_i的正例集和负例集.根据图 2所示的DTW时序对齐可知:若x_i与x_j的类标相同, 则对于时间点x₁₃, 其x_it⁺={14, 15, 16, 17};若两条时间序列类标不同, 则x_it^-={14, 15, 16, 17}.

对于每一个x_i, 赋予其一个权值向量w_i=(w_i1, w_i2, …, w_iT), 此向量根据x_i中每个采样点对拉近正例集和远离负例集的贡献而确定.所以, 此处定义w_it为

$ {w_{it}} = \frac{{{A_{it}}}}{{\sum\nolimits_{t' = 1}^T {{A_{it'}}} }}, {\rm{ }}{w_{it}} > 0, {\rm{ }}\sum\nolimits_{t = 1}^T {{w_{it}} = 1} $

(1)

其中,

$ {A_{it}} = \frac{{\sum\nolimits_{{x_{i'}} \in {\rm{cNN}}_i^ - } {\frac{1}{{|{\pi _{ii'}}|}}\left( {\sum\nolimits_{(t, t' \in {\pi _{ii'}})} {{{({x_{it}} - {x_{i't'}})}^2}} } \right)} }}{{\sum\nolimits_{{x_{i'}} \in {\rm{cNN}}_i^ + } {\frac{1}{{|{\pi _{ii'}}|}}\left( {\sum\nolimits_{(t, t' \in {\pi _{ii'}})} {{{({x_{it}} - {x_{i't'}})}^2}} } \right)} }} $

(2)

|π_ii'|是x_it对齐点的个数, 除以|π_ii'|意味着获取正例集和负例集对齐点的均值.对于公式(2)而言, 分母可认为是x_it的类内方差, 而分子是类间方差.由于此模型的目标是在最大化类间方差的同时缩小类内方差, A_it或者w_it越大, x_it的辨别性就越高.

尽管每一个x_it都至少拥有1对正例集或负例集的对齐点(当正例集存在时), 当所有的x_i't'都与x_it相等时, 公式(2)的分母将变为0, 从而公式(2)变得无意义.为了避免这种情况的发生, 公式(2)被修改为

$ {A_{it}} = \frac{{\sum\nolimits_{{x_{i'}} \in {\rm{cNN}}_i^ - } {\frac{1}{{|{\pi _{ii'}}|}}\left( {\sum\nolimits_{(t, t' \in {\pi _{ii'}})} {{{({x_{it}} - {x_{i't'}})}^2}} } \right)} }}{{\sum\nolimits_{{x_{i'}} \in {\rm{cNN}}_i^ + } {\frac{1}{{|{\pi _{ii'}}|}}\left( {\sum\nolimits_{(t, t' \in {\pi _{ii'}})} {{{({x_{it}} - {x_{i't'}})}^2}} } \right) + \varepsilon } }} $

(3)

其中, ε是一个非常小的数, 比如10^-6.

2.1 局部加权DTW

DTW是最为广泛使用的时间序列度量方法之一.它最简单的定义形式如下:

$ DTW({\mathit{\boldsymbol{x}}_i}, {\mathit{\boldsymbol{x}}_{i'}}): = \mathop {\min }\limits_{\pi \in \mathcal{A}} \left( {\sum\limits_{(t, t' \in {\pi _{ii'}})} {||{x_{it}}-{x_{i't'}}|{|^2}} } \right) $

(4)

其中, x_i的每一个点都有相同的权重1/T.

本文介绍的局部加权DTW(locally weighted dynamic time warping, 简称LDTW)非相似性度量方法计算加权序列(x_i, w_i)与x_i之间的距离:

$ LDTW(({\mathit{\boldsymbol{x}}_i}, {\mathit{\boldsymbol{w}}_i}), {\mathit{\boldsymbol{x}}_{i'}}): = \mathop {\min }\limits_{\pi \in \mathcal{A}} \left( {\sum\limits_{(t, t' \in {\pi _{ii'}})} {f({w_{it}})||{x_{it}} - {x_{i't'}}|{|^2}} } \right) $

(5)

其中, ||x_it-x_i't'||²为两者间的欧式距离.尽管存在一些高级的函数来估计w_it的贡献, 为不失一般性和简洁性, 此处将f(w_it)定义为如下所示的指数函数或者幂函数:

$ f\left( w \right) = {{\rm{e}}^{ - \alpha w}} $

(6)

$ f\left( w \right) = {w^{ - \alpha }} $

(7)

对于公式(6)和公式(7), a∈R⁺控制加权机制的影响, 并且α=0对应于标准的、未加权的、均匀的DTW.之所以用负号, 是为了保证优先选择最重要的时间点, 而且LDTW是为了最小化所有时间序列时间点的值之间的非相似性.因此, LDTW是DTW的一种更一般化的表示, 其对齐排序符合定义1中关于时序对齐的限制边界和单调性条件的描述, 并且与图 2中基于DTW的时序对齐类似.

2.2 多变量时间序列

对于多变量时间序列, 每一条时间序列x_i={x_i1, x_i2, …, x_iT}包含T个q维的数值变量, 其中, x_it∈R^q并且x_it= $ {\{ x_{it}^1, ..., x_{it}^q\} ^T}. $尽管每条时间序列的长度T可能不同, 但基于DTW的度量方式能够应对.为了将本文提出的LDTW

方法应用于多变量时间序列, 需要为每一条时间序列的每一个时间点的每一个数值变量计算权值, 针对多变量时间序列的DTW被定义为

$ DTW({\mathit{\boldsymbol{x}}_i}, {\mathit{\boldsymbol{x}}_{i'}}): = \mathop {\min }\limits_{\pi \in \mathcal{A}} \left( {\sum\limits_{k = 1}^q {\sum\limits_{({t^k}, {{t'}^k} \in \pi _{ii'}^k)} {||x_{it}^k - x_{i't'}^k|{|^2}} } } \right) $

(8)

因此, 局部加权后的公式(8)可被表示为

$ LDTW(({\mathit{\boldsymbol{x}}_i}, {\mathit{\boldsymbol{w}}_i}), {\mathit{\boldsymbol{x}}_{i'}}): = \mathop {\min }\limits_{\pi \in \mathcal{A}} \left( {\sum\limits_{k = 1}^q {\sum\limits_{({t^k}, {{t'}^k} \in \pi _{ii'}^k)} {f(w_{it}^k)||x_{it}^k - x_{i't'}^k|{|^2}} } } \right) $

(9)

其中, w_i从1×T维向量(单变量时间序列)转变为q×T维矩阵(多变量时间序列), 相似的变化也发生在π_ii'上.

2.3 局部加权ED

对于基于ED的kNN分类器, 两个时间序列x_i和x_j之间存在一对一的关系.所以, 长度为T的对齐排列π被定义为T对x_i和x_j之间的对齐元素:π=((π₁(1), π₂(1)), (π₁(2), π₂(2)), …, (π₁(T), π₂(T))).与DTW的定义相比, 很容易发现基于ED的度量是DTW的一个特例.实际上, DTW代价矩阵的对角线就代表了ED度量(如图 2所示), 因此很容易将LDTW的思想应用到局部加权的ED中(locally weighted euclidean distance, 简称LED).

$ LED(({\mathit{\boldsymbol{x}}_i}, {\mathit{\boldsymbol{w}}_i}), {\mathit{\boldsymbol{x}}_{i'}}): = \sum\limits_{t = 1}^T {f({w_{it}})||{x_{it}} - {x_{i't'}}|{|^2}} $

(10)

w_it的定义与公式(1)相同, 而A_it被修正为

$ {A_{it}} = \frac{{\sum\nolimits_{{x_{i'}} \in {\rm{cNN}}_i^ - } {{{({x_{it}} - {x_{i't'}})}^2}} }}{{\sum\nolimits_{{x_{i'}} \in {\rm{cNN}}_i^ + } {{{({x_{it}} - {x_{i't'}})}^2} + \varepsilon } }}, \varepsilon > 0 $

(11)

3 基于LDTW的kNN算法

为方便起见, 本文只介绍在单变量时间序列中学习局部加权LDTW和相应的kNN分类器.对于基于LDTW的kNN分类器, 需要找到每一条测试实例x_j(1≤j≤N_test)的k个根据公式(5)所得的距离最近的时间序列.在算法1中, 同类/异类时间序列的个数c将会在下一节进行讨论(第1行).LDTW算法和标准DTW算法之间的主要不同在于:前者需要根据算法2计算每一个x_i的权值w_i(第2行~第4行); 后者直接寻找最近邻, 不考虑权重的不同.

算法1. LDTW(X_train, X_test).

输入:训练集X_train, 测试集X_test.

输出:错误率errorRate.

1:  初始化:读取训练集X_train, 测试集X_test; i=1(1≤i≤N_train), j=1(1≤j≤N_test);

      最近同类或不同类序列的个数c以及最近邻的个数k.

2:  for x_i, 1≤i≤N_train

3:    根据算法2更新x_i的权重w_i

4:  end for

5:  for x_j, 1≤j≤N_test

6:    根据公式(5)寻找x_j的k近邻

7:    预测的x_j类标

8:  end for

9:  根据真实类标计算错误率errorRate

10:  return errorRate

算法2用于学习每一条训练序列的辨别性权重w, 初始时w⁰=(1/T, …, 1/T)意味着每一个特征或者时间点的权重相同, 所以∏^*(0)是根据标准DTW获得的最优对齐排列(第1行~第3行).随着w^p的不断更新(第9行), 权重变得不均匀, 并且∏^*(p)变为根据LDTW获得的最优对齐排列(第7行).需要注意的是, 为得到最优排列∏^*(p), 每一次迭代都需要根据w^p和c找到x的cNN⁺和cNN^-以及相应的对齐点集合.该算法不断迭代, 直到w^p保持不变或者w^p和w^p-1非常接近为止(具体停止标准将在第4.2节进行讨论).

算法2. WeightLearn(c, x, X_train).

输入:c, 正、负例集中序列个数; x, 一条训练实例; X_train, 训练集.

输出:局部权重w^p.

1:  根据公式(4)计算x与X_train中实例间的标准DTW距离, 获取每对时间序列间的DTW对齐方式∏^*(0)

2:  根据标准DTW距离和∏^*(0)寻找cNN⁺, cNN^-以及相应的对齐点集合

3:  根据公式(1)计算w⁰

4:  p=0

5: repeat

6:    p=p+1

7:    根据公式(5)和w^p-1计算实例间的LDTW距离, 获取每对时间序列间的LDTW对齐方式∏^*(p)

8:  根据LDTW距离和∏^*(p)寻找cNN⁺, cNN^-以及相应的对齐点集合

9:  根据公式(1)更新w^p

10:until w^p≈w^p-1

根据动态规划思想, 计算DTW最优对齐方式的时间复杂度为O(T²).由于本文所提出的算法LDTW是经典算法的加权扩展, 其时间复杂度依然为O(T²).但其需要根据DTW/LDTW迭代地寻找每一个训练实例的正例集和负例集并更新权重, 此举需要花费较多的计算量.因此, 在N条长度为T的时间序列上, 计算每一对序列间LDTW距离的时间复杂度为O(N²T²×(p+1)), p+1为算法的迭代次数.在多数情况下, 权重向量w仅需要迭代2次就趋于稳定(详见第4.2节), 因此, 其时间复杂度O(N²T²×(p+1))≈O(2N²T²)≈O(N²T²).同时, LDTW也可以通过使用对齐排列在对角线附近的子集来加速^{[11, 14]}.

4 实验与评价

本节将首先描述所使用的实验数据集(UMD, BME和Conseason从http://ama.liglab.fr/~douzal/tools.html获取, Trajectories从https://archive.ics.uci.edu/ml/datasets/Character+Trajectories获取, 其他数据从http://www.cs.ucr.edu/~eamonn/time_series_data/获取), 然后介绍参数的设置方法, 最后对比不同算法(包括ED、DTW、基于指数函数的LDTW/LED、基于幂函数的LDTW/LED、基于shapelet的决策树等)的实验结果.

4.1 实验数据集

对比实验在40个公共数据集上完成, 见表 2.数据集Trajectories是长度不一的多变量时间序列.数据集Conseason的错误率通过10次有放回抽样获取, 而其他数据在获取时已被区分为训练集与测试集, 所有错误率都在测试集上计算.另外, 由于正例集与负例集均是从训练集中获取的, 表 2的最后一行min表示训练实例中不同类别实例的最小个数.比如, 人工数据集CBF由3个不同的类别组成, 分别为Cylinder, Bell和Funnel, 每一个类别在训练集中的个数分别为10, 12和8, 所以, CBF的min被设置为8.

4.2 参数设置

在本文所有实验中, 近邻个数k的取值范围为{1, 3, 5, 7, 9}.另外, 正例集或负例集的个数c是很难确定的, 因为c值的设定关系到辨别性特征的发现, 设置不正确时将会很难发现辨别性的特征, 进而影响分类准确率.为覆盖尽量多的实例并不失一般性, c被设置为c∈{1, 2, 3, 5, 10}并且c < min.若c≥min, 则有可能发现不了足够的正例集.例如, CBF的min被设置为8, 那么c只能从{1, 2, 3, 5}中取, 当c=10时, 类别Cylinder和Funnel将不能得到足够的正例集, 此时设置其权重为初始权重1/T.具体的参数设置总结于表 3.

对于公式(6)和公式(7), 当w从0到1不断变化时(0 < w < 1), 指数函数的取值范围为1~0(0 < f(w) < 1), 而幂函数的变化范围是+∞~1(1 < f(w) < +∞).随着α的增长, 较大w之间的差别在逐渐减小, 而较小w之间的差别在不断增大.图 4展示了α变化时分类错误率的变化(对于指数函数, α变化范围为0~10, 而幂函数中的α变化范围是0~1, 此实验中, k=1, c=3), 分别在两个不同的数据集ItalyPowerDemand和Beef上进行了测试, 其中, 实线表示指数函数的实验结果, 虚线表示幂函数的实验结果.α=0, 对应于标准的DTW算法.当α从0增长到10(或者相应地从0增长到1)时, 尽管分类错误率曲线有些许起伏, 但整体上都经历了先下降后上升(或震荡平稳)的过程, 并且都在α=1或0.1附近取得最小值.为简洁起见, 本文在训练kNN分类器时, 将指数函数的α设置为1, 幂函数的α设置为0.1.

在算法2中, 本文所提出的模型必须保证每一条时间序列x_i的权重w_i收敛.如图 5所示(此实验中, c=3, α_exp=1, α_pow=0.1保持不变), 仅通过2次迭代, 大多数的规范化欧式距离$ ||\mathit{\boldsymbol{w}}_i^p - \mathit{\boldsymbol{w}}_i^{p - 1}|{|^2} $就接近收敛于0.为进一步保证收敛性, 迭代次数被设置为4.注意:若$ ||\mathit{\boldsymbol{w}}_i^p - \mathit{\boldsymbol{w}}_i^{p - 1}|{|^2} \le 0.1*||\mathit{\boldsymbol{w}}_i^0|{|^2} $为真, 则迭代停止.因为初始时w_i⁰=(1/T, …, 1/T), 0.1倍的‖w_i⁰‖²满足条件$ \mathit{\boldsymbol{w}}_i^p \approx \mathit{\boldsymbol{w}}_i^{p - 1}. $

4.3 与基准分类器对比

这一节将我们所提出的基于LED/LDTW的kNN分类器与经典的基于ED/DTW的kNN相比较.表 4展示了所有对比算法在40个公共数据集上的分类错误率, 其中, 加粗的数值表示所对比方法中最优的结果.如果一个分类错误率与最优结果相比具有显著性差异^[21](显著性水平设置为0.01), 则用“*”来标注.表中所有参数均通过10折交叉验证获得.

对比与标准的度量算法, 表 4中的分类错误率展现了我们所提出的局部加权度量方法LED和LDTW在区分复杂时间序列时的有效性.尽管标准度量方式在两个数据集MoteStrain和WordsSynonyms上具有较好的分类错误率, 但它与我们所提出的方法之间并没有显著性差异, 也就是说, 它们在预测下一个测试实例的类标时会得到相同的结果.我们所提出的算法在40个数据集中的38个上表现较好(包括平局情况, 另外需要注意:因为序列长度不相等, ED/LED不能处理多变量数据集Trajectories).对于没有时间延迟或具有较少延迟的序列, LED算法能够提高其分类准确率, 原因在于这些序列不需要或只有少量的时间扭曲, 而LDTW能够很好地处理具有大量时间延迟或时间扭曲的序列.从表中也可以看到, 基于1NN的度量算法在多于80%的数据集上优于其他k近邻算法, 这也和Wang等人^[22]以及Petitjean等人^[16]的描述相符.对于最近邻个数k与正例集或负例集个数c之间的关系, k大于c的情况只在158次测试中出现了24次, 所以为分类准确率考虑, c应该大于k.

另外, 通过使用多维尺度分析(multidimensional scaling, 简称MDS)^[23], 能够可视化数据集在不同度量下的潜在结构.图 6在二维空间中展示了Coffee和BME数据集在ED/DTW/LDTW度量下的潜在结构(不同颜色的圆圈表示训练集的不同类别, 不同颜色的十字表示测试集的不同类别, 相同的颜色表示相同的类别), 当括号中的参数stress小于20%时, 所获取的图像为数据集潜在结构的精确表示(stress的大小用于度量MDS算法的契合度, stress值越小, 该表示图像就越契合原数据的潜在结构).从图 6中可以观察到, LDTW展现了较强的区分能力.换句话说, LDTW在增大类间方差的同时降低了类内方差(如BME数据集).对于数据集Coffee, 从基于LDTW的MDS表示中可以发现, 不同类别序列之间存在一条较为明显的分割线.

4.4 与基于shapelet的决策树对比

时间序列shapelet是时间序列中能够最大限度地表示一个类别的子序列^{[24, 25]}, 基于时间序列shapelet的决策树具有分类精确率高、可解释性强等优点.为了进一步验证本文所提出算法的有效性, 我们将其与快速shapelet决策树算法^[26](FS)和近似最优化shapelet决策树算法^[27](LTS)做对比.

发现最好shapelet的时间复杂度为O(N²T⁴), 即使经过优化, LTS算法发现shapelet的时间复杂度仍为O(N²T²×maxIter×S), 远超LDTW算法的时间复杂度, 其中, maxIter为LTS的最大迭代次数, S为shapelet的取值范围.因此, FS算法和LTS算法只在部分较小数据集上完成了实验.

为简洁起见, 我们直接选用基于幂函数的LED_pow和LDTW_pow以及基于ED和DTW的基准分类器与LTS和FS做对比实验, 其中LTS和FS的参数设置参照了Bagnall等人^[28]的设置方法.具体分类错误率和分类器排名见表 5.我们在23个数据集上完成了实验, 表现最好的两个分类器为LTS和LDTW_pow, 其中, LTS在13个数据集上的表现最佳, LDTW_pow也在10个数据集上取得了最低的分类错误率.

为了验证多个分类器在多个数据集上的表现, 本文采用Demšar所提出的方法^[29]对表 5中的分类器进行显著性检验.如图 7中给出的Critical Diffierence图所示, 尽管LTS的分类结果更好, 但LTS, LDTW_pow与DTW之间不存在显著性差异, 而且LTS和LDTW_pow明显优于FS算法, 这也重新验证了基于DTW的kNN分类器是难以击败的^[28]这个已被多个学者验证的观点.另外, 由于时间复杂度或分类效果的限制, LTS和FS算法较难应用于大规模的数据集中, 而本文所提出的LDTW算法在具有较低时间复杂度的同时, 保持了较好的分类效果.

5 实例解析

本节将通过实例解析, 展示我们所提出的模型在人工数据集以及实际应用中的有效性与可解释性.

5.1 人工数据集

为展示我们所提出的算法的有效性, 首先考虑两个人工数据集BME和UMD, 这两个数据集均由类间相似而类内不同的时间序列组成^[2].BME数据集的长度为128, 分别由3个类别Begin, Middle和End组成.图 8展示了BME中不同类别的时间序列, 其中, 黑色曲线为代表性序列, 灰色曲线为该类别中其他不同形状的序列.在Begin类别中, 所有时间序列的共同点在于开始阶段会出现一个小钟型子序列; 而对于End类别, 钟型子序列会出现在序列快结束时.但是在Beign或End序列中, 大钟型子序列有可能朝上或者朝下出现, 其与类别的相关性不大.另外, 具有朝上方向大钟型子序列的Beign或End序列在整体上是与Middle序列相似的.

图 9展示了数据集UMD不同类别的轮廓, 它长度为150, 由3个相似的类别Up, Middle和Down组成.其相对于BME数据集更加复杂, 主要区别在于小钟型子序列的方向是朝上还是朝下的, 与其出现位置或时间点并没有直接联系.从图 8中可以观察到, 当小钟型子序列方向朝上时, 无论其出现在序列开头还是末尾, 均定义为Up类别; 当小钟型子序列方向朝下时, 无论其出现在序列开头还是末尾, 均定义为Down类别; 当Up/Down中的大钟型子序列方向朝上时, 它们与Middle序列具有全局相似性.如图 8或图 9的方框区域所示, 最具辨别性的权重刚好对应于小钟型子序列出现的地方.

5.2 真实数据集

Gun/NoGun数据集是一组根据动作捕捉产生的时间序列, 它也是时间序列中最为广泛应用的经典数据集之一.此数据集包含200条实例, 其中50条作为训练集, 另外150条作为测试集, 数据集中的每一条实例的长度均为150(不包含类属性).图 10上半部分展示了该数据集中Gun与NoGun类别的代表性序列, 其中, Gun序列记录了表演者举起手枪并放回原位的动作序列; NoGun序列记录了表演者做同样动作, 但手中并没有手枪时的序列.两种类别具有明显的全局相似性, 其主要区别在于:若表演者手中没有枪, 记录序列中就会出现如图 10所示的方框中类似于波谷的子序列.图 10下半部分给出了两种不同类别序列的局部权重, 黑色权重曲线分别对应于上方Gun与NoGun加粗标注序列的权重.很明显, 通过将学习到的权重映射到原始时间序列, LDTW算法能够准确地发现该经典数据集的辨别性子序列(即方框中所示的片段), 所发现子序列也与时间序列shapelets^{[24, 25]}以及可解释性的序列规则^[30]相符.

5.3 多变量时间序列数据

Trajectories数据集是一个多变量的、长度不等的手写字符集, 它记录了某人在书写20个不同字母(分别为a, b, c, d, e, g, h, l, m, n, o, p, q, r, s, u, v, w, y, z)时笔尖的行走轨迹.该数据集包含2 858个不同长度的手写字母, 每一个字母由3条长短不一的时间序列组成.通过将此多变量时间序列映射到二维空间, 即可得到图 11所示的手写字符.

虽然所有实例均来自于同一个书写者, 不同字母间却具有明显的全局相似性.基于DTW的kNN分类器在该数据集上的分类错误率为0.159, 而LDTW所获取的分类错误率为0.068, 两者之间具有显著性差异.从图中可以观察到, 对于待分类字母“e”, 基于DTW的度量容易将字母“e”与字母“d”“u”“z”混淆, 而LDTW能够很好地找到它们的最近邻.

6 总结与展望

本文介绍了一种用于处理复杂时间序列数据的局部加权DTW模型.它根据训练实例采样点的正例集和负例集来发现辨别性子序列.通过在多个数据集上的测试实验, 表明其无论在单变量时间序列还是多变量时间序列上都具有较强的分类能力.另外, 通过实例解析阐明了基于LDTW的kNN分类器具有可解释性.但由于该模型需要迭代地学习权值, 因此需要消耗大量的时间.未来的研究方向包括使用优化学习方法加速权重的学习过程, 以及将该模型扩展到基于核函数的kNN或支持向量机分类模型等.