在时间序列分类问题中,我们将任意实值型有次序的数据看作一条时间序列^[1].它与传统分类问题之间的差别在于:传统分类数据的属性次序是不重要的,并且变量之间的相互关系独立于它们的相对位置;而对于时间序列数据而言,在寻找最佳的辨别性特征时,变量的次序起着至关重要的作用.在过去的10多年中,针对时间序列分类问题的研究主要集中在基于不同距离度量方式的最近邻(1-NN)算法上,如基于欧式距离或者动态时间规整(dynamic time wrapping,简称DTW)的1-NN等^{[2, 3, 4]}.近年来,基于时间序列shapelets的分类方法引起了研究者广泛的关注^{[1, 5, 6, 7, 8]}.

时间序列shapelets是时间序列中能够最大限度地表示一个类别的子序列^{[5, 6]}.基于时间序列shapelets的分类方法具有分类准确性高、分类速度快、可解释性强等优点,它的具体概念是由Ye等人^[5]所提出的.图 1所示为解决经典Gun/NoGun问题^{[5, 9]}的最佳shapelet,该shapelet准确地展现了Gun与NoGun序列间的不同.如Esling等人^[10]所述,此方法大大缩小了时间序列和形状分析间的差距.

图 1(Fig.1)

Fig.1 Best shapelet 图 1 Shapelet示例

基于shapelets的时间序列分类算法可分为两类:

· 第1类方法在发现时间序列shapelets的同时构造分类器.在文献[5]中,作者采用信息增益度量每一条时间序列的候选shapelet,并选取当前信息增益最大的shapelet作为决策树的分裂节点.该方法通过不断地递归搜索当前最好的shapelets完成决策树的构建.Mueen等人^[7]针对shapelets在可表示性方面的不足,提出了一种根据shapelets的合取或析取构建决策树的算法,并采用了多种加速技术来加快分类器的构建.Rakthanmanon等人^[8]针对前两种shapelets发现算法在时间效率上的不足,提出了一种基于SAX(symbolic aggregate approximation)表示的快速shapelets发现算法,尽管此算法发现的是近似的而不是精确的shapelets,但它在提升shapelets发现效率的同时,保持了一定的分类准确性.

· 第2类方法将时间序列shapelets的选择过程当作单独的预处理步骤来处理,即:通过shapelets转换,将shapelets的发现和分类器的构造相分离.其主要优点是优化了shapelets的选择过程,并能够灵活应用不同的分类策略.Bagnall等人^[11]指出:解决时间序列分类问题的最简单方式,是将时间序列映射到其他辨别性特征容易被检测到的空间.作者通过在建造分类器之前将时间序列分类问题转换到其他空间,极大地提升了分类的准确性.Lines等人^[1]首次提出了基于shapelets转换的时间序列分类方法,此方法通过在构建分类器之前创建新的分类数据,使得它在保持shapelets的解释力的同时提升了分类的准确性.另外,时间序列shapelets还被应用于其他方面,比如聚类^[12]、早期分类^[13]、姿势识别^[14]、天气预测^[15]等等.

然而,基于shapelets转换的时间序列分类方法存在两个主要问题:

· 一是shapelets转换时,所选取的时间序列shapelets的数量影响着分类结果的好坏,而用于产生最好分类结果的shapelets数量是很难确定的;

· 二是被选择的shapelets之间往往存在着较大的相似性.

例如,对于经典的Gun/NoGun问题,通过文献[1]中所提出的ShapeletFilter算法而得到的前10个shapelets如图 2(a)所示.从图中可以观察到:这10个shapelets聚成了两簇,即,shapelets之间存在着极大的相似性.我们只需要找出这两簇中最具有辨别性的2个shapelets(如图 2(b)所示)就可以涵盖这10个shapelets,从而允许其他有辨别性的shapelets参与到数据转换中,并有利于提高分类准确率.

图 2(Fig.2)

Fig.2 Similar shapelets and discriminative shapelets 图 2 相似shapelets与辨别性shapeletsv

对于数据转换时所需shapelets的数量,我们借鉴属性选择中的序列覆盖思想^[16],提出了shapelet覆盖的概念,并根据shapelets对实例的覆盖情况来选取shapelets.

本文的主要贡献有:

(1) 提出了一种简单有效的shapelet剪枝方法,它能够过滤相似的shapelets,并减少候选shapelets样本的数量;

(2) 提出了一种基于shapelets覆盖的方法来确定用于数据转换的shapelets的数量,保证了shapelets对实例的覆盖;

(3) 将所提出的算法和其他基于shapelets的时间序列分类算法以及基于DTW和欧式距离的1-NN分类器作对比,阐明了我们所提出算法的分类准确性.

本文第1节将阐述时间序列分类问题的相关定义和shapelets转换方法的研究背景.第2节描述本文所提出的shapelet选择和shapelet覆盖等方法.第3节给出实验描述并评估所提出的算法.第4节进行相应的总结以及对进一步工作的展望.

一条时间序列是一组序列数据,它常常是在相等间隔的时间段内,依照给定的采样率,对某潜在的过程进行观察的结果.时间序列分类的目标是:首先,从标定类标的训练集中学习到能够区分不同类别的有鉴别性的特征;然后,当一条未标定的时间序列到来时,它能够自动决定该时间序列的类标.假设一个时间序列数据集有n条时间序列:D={T₁,T₂,···,T_n},每一条时间序列有m个观测值和一个类值c_i,即T_i=át_i1,t_i2,···,t_im,c_iñ.我们的目标是,构造一个将时间序列的观测值映射到类值的函数.为方便起见,假设数据集D中每一条时间序列具有相同数目的观测值.文中涉及的符号见表 1.

表 1(Table 1)

Table 1 Symbols表 1 符号表 符号 释义 D 时间序列数据集 T, X, Y 时间序列 S, s 时间序列的子序列 |x|, l 时间序列子序列的长度 dist(x,y) 时间序列X与Y之间的规范化距离 subdist(x,y) 子序列距离 x,σx 均值与方差 N, |D| 数据集中时间序列的条数 τ 距离阈值 (s,τ) 一个shapelet E 熵 I 信息增益 G 分裂间隔 L orderline

Table 1 Symbols表 1 符号表

定义1(时间序列及其子序列). 时间序列T是一条实值的序列,可表示为τ₁,τ₂,···,t_m.一条时间序列的子序列S_i,l=t_i,t_i+1,···,t_i+l-1是一条T中从位置i开始长度为l的连续的子序列,这里,1≤i≤m-l+1.注意:数据点τ₁,τ₂,···,t_m是按照时间顺序排列的,两两之间具有相同的时间间隔.时间序列的子序列可以当作是时间序列的局部特征.

定义2(时间序列间的距离). 所有的分类问题都依赖于数据间的相似性度量,时间序列分类问题也不例外.对于给定的具有相同长度m的两条时间序列X和Y,我们可以使用长度规范化的欧式距离来度量他们之间的不同,见公式(1).

注意:为获得两个时间序列之间距离的有效比对并保证缩放和偏移的不变性,在计算真正的距离之前,我们必须使用z-规范化方法(见公式(2))对每个时间序列进行规范化处理

许多时间序列数据挖掘算法只需要对比相等长度的时间序列.而时间序列shapelets需要计算一条较短的时间序列子序列与一条较长的时间序列间的距离.为得到此结果,短的时间序列须在长的序列上滑动,以得到它们之间的最短距离,我们称为子序列距离,并定义为

其中,y_|x|表示时间序列Y中长度为|x|的子序列.需要注意的是,subdist()得到的是两条时间序列间的最小距离.为减少计算规范化距离的时间复杂度和重复利用中间结果,在本文中采用了充分统计量(sufficient statistics)技术来加速此计算过程.相比较于现有的方法,充分统计量技术能够将发现shapelets的时间复杂度降低一个数量级,请读者参照文献[7]中的描述,以进一步了解充分统计量技术.

定义3(shapelets与信息增益). shapelet是由D中某一实例的子序列s和分裂阈值τ所组成的元组(s,τ).τ表示距离的阈值.shapelet会将数据集D分割成两个不相交的子集,其中,

D_left={x:xÎD,subdist(s,x)≤τ},D_right={x:xÎD,subdist(s,x)>τ}.

本文采用信息增益度量shapelets的鉴别能力,令N₁=|D_left|,N₂=|D_right|,一个shapelet的信息增益为

其中,E(D)为数据集D的信息熵,N为数据集D中时间序列的条数.

定义4(分裂间隔). shapelet的分裂间隔为

即为分裂点右侧实例的平均距离减去分裂点左侧实例的平均距离.

定义5(orderline). orderline L是数组的一维表示形式,它按照递增的顺序记录了候选shapelet与数据集D中所有时间序列间的距离.

我们将用图 3所示的例子来阐释shapelet和orderline的概念.左边方框中是一个候选的shapelet,右边的orderline记录了该候选shapelet与数据集D中每个时间序列之间的距离,τ为分裂点的阈值.

图 3(Fig.3)

Fig.3 An example of orderline 图 3 Orderline示例

在图 3中:数据集D为经典的Gun/NoGun数据集,圆形表示NoGun序列与候选shapelet之间的距离,它们与候选shapelet间的距离较小;矩形表示Gun序列与候选shapelet之间的距离,它们与候选shapelet间的距离较大.orderline创建之后,我们就可以计算分裂点、分裂间隔以及候选的shapelet的信息增益等.最终选取最优的一个或多个shapelets进行分类.

为阐述我们的贡献,我们将首先描述文献[1]中提出的基于shapelets转换的时间序列分类方法.此方法的主要动机是:将shapelets的发现与分类器的构建相分离,从而允许转换后的数据应用于传统分类器中.相应的算法实现主要包括3个步骤:首先,通过扫描一次数据集,找到最好的k个shapelets;其次,使用交叉验证方法估计能够得到最好分类结果的shapelets的个数k;然后,将每一条时间序列转换成具有k个属性的实例.即,让每个属性代表一个shapelet,属性值为shapelet与该时间序列之间的距离.这样就创建了一个新的数据集;最后,将转换后的数据集用于朴素贝叶斯、贝叶斯网络、决策树、1-NN等分类器进行分类. 具体的算法描述见算法1.

算法1. ShapeletFilter(T,min,max,k).

输入:时间序列T、最小长度min、最大长度max、shapelet个数k;

输出:k个最好的shapelets kShapelets.

1: kShapelets←Ø;

2: for i←0 to |T| do {T中的每一条时间序列}

3:   shapelets←Ø;

4:   for l←min to max do {T_i中的每一个长度}

5:     for u←0 to |T_i|-l+1 do {每一个起始位置}

6:      S←T_i(u,l);

7:      for m←0 to |T| do {候选shapelet S与每一条时间序列的距离}

8:       D_s←subdist(S,T_m);

9:      orderline←sort(D_s); {创建orderline}

10:     quality←assessCandidate(S,orderline,D_s); {计算shapelets最大信息增益}

11:     shapelets.add(S,quality);

12:   sortByQuality(shapelets); {根据信息增益大小排序}

13:   removeSelfSimilar(shapelets); {移除自相似的shapelets}

14: kShapelets←merge(k,kShapelets,shapelets); {保留当前最好的k个shapelets}

15: return kShapelets;

算法1描述了从数据集中抽取k个最好的shapelets的过程.根据最大最小长度的设置范围,每一条时间序列的每一种可能长度的子序列都被做了相应的评估,并最终得到最好的k个shapelets.得到一个候选的shapelet之后,需要计算该shapelet与每一条时间序列间的距离,构建orderline(第2行~第9行),并计算能得到最大信息增益的分裂点(第9行~第11行).得到所有候选shapelets之后,根据其信息增益大小进行排序(第12行).若两个shapelets来自同一条时间序列并有重叠之处,则认为它们是自相似的,此时需要保留较好的shapelet,并移除自相似的shapelet(第13行).一旦得到一条时间序列中所有非自相似的shapelets,就将它们与现有的最好的k个shapelets相结合,并保留最好的k个(第14行).

得到k个最好的shapelets之后,利用它们将原有的时间序列转换成新的数据集的方法见算法2.数据转换时使用的子序列距离计算方法如算法3所示(第5行).shapelets与时间序列比对时,都进行了规范化处理(算法3第2行、第5行).对于D中的每一条时间序列D_i,它的子序列距离通过与S_j(j=0,···,k-1)计算得出.得到的k个距离用于构建转换后数据集,即:新的数据集中,每一条实例有k个属性,每一个属性值都对应于相应的shapelet到原始时间序列的距离(第6行、第7行).

算法2. TransformData(S,D).

输入:最好的k个shapelets S、数据集D;

输出:转换后的数据集output.

1: output←Ø;

2: for i←0 to |D| do {D中的每一条时间序列}

3:   transformed←Ø;

4:   for j←0 to |S| do {S中的每一个shapelet}

5:     dist←subdist(S_j,D_i); {子序列距离}

6:     transformed.add(dist);

7:   output.add(transformed);

8: return output;

算法3. subdist(x,y).

输入:时间序列x和y,|x|≤|y|;

输出:x与y的规范化距离.

1: bestSum←MAX_VALUE;

2: x←zNorm(x); {规范化}

3: for i←0 to |y|-|x|+1 do {y中的每一个起始位置}

4:   sum←0;

5:   z←zNorm(y_i,|x|); {规范化}

6:   for j←0 to |x| do {计算欧氏距离}

7:     sum←sum+(z_i-x_i)²;

8:   bestSum←min(bestSum,sum); {取最小值}

9: return (bestSum/|x|)^1/2;

本文提出的转换算法通过4个主要步骤处理shapelets:

· 首先,通过扫描一次数据集,找到所有候选的shapelets;

· 其次,通过使用本文提出的shapelet剪枝方法,从候选shapelets中移除相似的shapelets;

· 再次,使用本文新提出的shapelet覆盖方法来确定用于数据转换的shapelets的数目k;

· 最后,将每条时间序列转换成具有k个属性的实例,并将多种不同的分类策略应用到时间序列分类中.

生成所有候选shapelets的过程见算法4.此算法处理数据的过程与文献[1]中的shapelet生成算法相类似.主要区别在于:我们算法的目标是找到所有的候选shapelets而不是最好的k个.原因是:任意时间序列的任意长度的子序列都有可能是辨别性shapelet,所以直接省略了参数k的设置.需要注意的是:当自相似的shapelets从一条时间序列中移除之后(第13行),将它们添加到候选的shapelets中,并按照它们信息增益的降序排列.此过程不断迭代,直至处理完所有的时间序列(第14行).

算法4. CandidateShapelets(T,min,max).

输入:时间序列T、最小长度min、最大长度max;

输出:候选shapelets CandidateShapelets.

1: CandidateShapelets←Ø;

2: for i←0 to |T| do {T中的每一条时间序列}

3:   shapelets←Ø;

4:   for l←min to max do {T_i中的每一个可能长度}

5:     for u←0 to |T_i|-l+1 do {每一个起始位置}

6:      S←T_i(u,l);

7:       for m←0 to |T| do {计算候选shapelet S与每一条时间序列的距离}

8:         D_s←subdist(S,T_m);

9:     orderline←sort(D_s); {创建orderline}

10:     quality←assessCandidate(S,orderline,D_s); {计算shapelets最大信息增益}

11:     shapelets.add(S,quality);

12:   sortByQuality(shapelets); {根据信息增益大小排序}

13:   removeSelfSimilar(shapelets); {移除自相似的shapelets}

14:   CandidateShapelets.add(shapelets); {保留所有候选的shapelets}

15: return CandidateShapelets;

我们提出shapelet剪枝方法的主要目的是:剪去相似的shapelets,从而允许更多有辨别性的shapelets参与到数据转换中.为了更好地描述shapelet剪枝方法,我们将首先描述相似shapelets的概念.

定义6(相似shapelets). 对于两个shapelets,(S₁,τ₁)和(S₂,τ₂),(S₁,τ₁)优于(S₂,τ₂).若它们所在时间序列的类标相同,并且两者间的子序列距离subdist(S₁,S₂)小于(S₁,τ₁)的分裂阈值τ₁,那么两者为相似的shapelets.

需要注意的是:定义的相似shapelets主要强调了形状的相似性,作比较的两个shapelets往往来自不同的时间序列;而自相似shapelets存在于同一条时间序列,并具有重叠的部分.由于τ₁是能够获取最大信息增益的距离阈值,当subdist(S₁,S₂)<τ₁时,表示S₁和S₂具有相似的形状,并且S₁能够在大部分情况下替代S₂.例如,从图 2(a)中可以观察到,解决Gun/NoGun问题的前10个shapelets间存在着极大的形状相似性.Shapelet剪枝之后,我们剪去了相似的shapelets,并能够使用2个不相似的shapelets来代表最好的10个(如图 2(b)所示).过滤相似shapelets的过程见算法5.

算法5. ShapeletsPrune(candidateShapelets).

输入:候选shapelets candidateShapelets;

输出:不相似的shapelets NoSimilarShapelets.

1: NoSimilarShapelets←Ø;

2: size←candidateShapelets.size(); {候选shapelets的个数}

3: for i←0 to size do {每一个候选shapelet}

4:   selectShapelet←candidateShapelets.get(i); {获取候选shapelet}

5:   NoSimilarShapelets.add(selectShapelet); {添加到不相似的shapelets中}

6:   Distance←selectShapelet.splitThreshold; {获取距离阈值}

7:   forj←i+1 to size do {每一个候选shapelet}

8:     ToPrune←candidateShapelets.get(j); {获取待剪枝的候选shapelet}

9:     Dist←subdist(selectShapelet,ToPrune); {计算距离}

10:     if (Dist≤Distance) {若两者间的距离小于阈值且类标不同,保留待剪枝的shapelet}

11:       if (selectShapelet.classLabel!=ToPrune.classLabel)

12:        NoSimilarShapelets.add(ToPrune);

13:     else {若两者间的距离大于阈值,保留待剪枝的shapelet}

14:      NoSimilarShapelets.add(ToPrune);

15:   candidateShapelets←NoSimilarShapelets;

16:   size←candidateShapelets.size();{重新获取候选shapelets的个数}

17: return NoSimilarShapelets;

在循环的开始和结束处,我们都需要初始化候选shapelets的数目,因为基本上每一次循环,候选shapelets的数目都将会减少(第2行和第16行).对于候选shapelets中的每一个shapelet,我们都将其与优于它的shapelets作比较,并决定是否剪去它(第3行~第14行).若ToPrune shapelet和selectShapelet shapelet间的子序列距离小于等于selectShapelet的分裂阈值,我们将比较它们的类标:当它们类标相同时,剪去ToPrune;否则,我们保留ToPrune,并将它应用于下一次循环中(第10行~第14行).最后,我们得到用于shapelet覆盖步骤的所有不相似的shapelets.

文献[1]使用5折交叉验证方法来确定用于数据转换的shapelets的数量.显然,这是一项十分耗时的工作,尤其当训练数据量比较大时,它的缺点会更明显.原因是,此方法需要运行多次才能得到拥有较好分类准确率的shapelets的数量.为了有效并简洁地获取用于最终转换的shapelets的数量,我们提出了一个新的概念——shapelet覆盖.

定义7(Shapelet覆盖). 给定shapelet (S₁,τ₁)和与它相对应的orderline L,分裂阈值τ₁将L上的数据点或者说数据集D分割成两部分:左边是与shapelet间子序列距离小于τ₁的时间序列数据集D_l,右边是与shapelet间子序列距离大于τ₁的时间序列数据集D_r.那么我们认为,<i>D_l能够被shapelet成功覆盖,D_r不能够被shapelet覆盖.参照图 3,根据此定义,我们可以认为圆形所代表的时间序列是能够被shapelet覆盖的数据集.

本文提出的shapelet覆盖的概念借鉴了属性选择算法中序列覆盖的思想.这里,我们可以将shapelet当做时间序列的一个特殊的特征来处理.两者间的主要区别在:于shapelet覆盖是一种近似的覆盖方法,它并不意味着某一时间序列包含此shapelet,而是它们的子序列距离小于某一给定的阈值.通过shapelet覆盖来选择shapelets的过程见算法6.

算法6. ShapeletsCoverage(NoSimilarShapelets,δ).

输入:不相似的Shapelets NoSimilarShapelets、覆盖参数δ;

输出:辨别性shapelets Shapelets.

1: Shapelets←Ø;

2: Initialize(InstanceTable); {初始化InstanceTable}

3: size←NoSimilarShapelets.size(); {不相似shapelets的个数}

4: for i←0 to size do {每一个候选shapelet}

5:   Selected←false; {标志位}

6:   InstanceID←NoSimilarShapelets.get(i).InstanceID; {获取被覆盖的实例ID}

7:   for j←0 to InstanceID.size() do {每一个实例ID}

8:     if (InstanceTable.contains(InstanceID_j)) {InstanceTable是否包含此ID}

9:      Selected←true;

10:       if (InstanceID_j.number()<δ) {是否达到覆盖次数δ}

11:        if (InstanceID_j.number()+1≥δ) {达到覆盖次数δ则移除此ID,否则加1}

12:         InstanceTable.remove(InstanceID_j);

13:        else

14:         InstanceID_j.number()++;

15:   if (Selected) {若标志位为真,则加入到辨别性shapelets中}

16:     Shapelets.add(NoSimilarShapelets.get(i));

17: return Shapelets;

本文的算法通过扫描一次不相似的shapelets来得到最终用于转换的辨别性shapelets(第4行).当一个shapelet被访问之后,被此shapelet覆盖的时间序列将被移除掉.但是在真正的时间序列分类任务中,考虑到分类准确率,我们可能希望用多个shapelets去覆盖一个实例.为实现此想法,引进了一个shapelet覆盖参数δ.若一条时间序列被至少δ个shapelets覆盖,这条时间序列将不会被进一步考虑(第8行~第14行).用一个名为InstanceTale的数组来存储每一条时间序列的计数值.初始时,InstanceTable中的每一个值被初始化为0(第2行).为更加清楚地解释此过程,采用了一个简单的实例进行说明,如图 4和图 5所示.

图 4(Fig.4)

Fig.4 Two orderlines 图 4 两个orderline示例

图 5(Fig.5)

Fig.5 Coverage of time series 图 5 时间序列被覆盖情况示例

在图 4中,orderline L₁和L₂展示了两个不同shapelets区分实例的情况.假设δ=2,第1次循环时,第1个shapelet的orderline为L₁,InstanceTable如图 5(a)所示.时间序列{300,400}与第1个shapelet之间的距离大于τ,所以它们未被此shapelet 覆盖,并且它们的计数值仍为0.由于每个实例的计数值更新之后都没有达到阈值δ=2,所以没有时间序列被移除.在第2次循环时,orderline为L₂,实例{100,600,800}与该shapelet间的距离小于阈值τ,所以它们的计数值都增加1(如图 5(b)所示).按照前述的规定,时间序列{100,600,800}可以从InstanceTable中移除.需要注意的是:当且仅当一个shapelet能覆盖InstanceTable中的任何一个实例时,它才能加入最终的shapelets中(第15行、第16行).

在第2.2节和第2.3节中,首先通过对候选shapelet剪枝,获得不相似的shapelets;然后,根据shapelet覆盖方法,从不相似的shapelets中得到用于数据转换的辨别性shapelets.为更快地获取用于数据转换的shapelets,可考虑将shapelet剪枝与shapelet覆盖方法相结合,即,直接通过对候选shapelets的遍历而得到最终的shapelets.此部分的目的是将shapelet剪枝和shapelet覆盖相整合.该方法相比较于前面分别计算shapelet剪枝和shapelet覆盖的方法至少节省了一个时间复杂度为O(m)的循环,m为不相似shapelets的个数.该整合版本见算法7.

算法7. PruneAndCoverage(candidateShapelets,δ).

输入:候选shapelets candidateShapelets、覆盖参数δ;

输出:辨别性shapelets Shapelets.

1: Shapelets←Ø;

2: size←candidateShapelets.size(); {候选shapelets的个数}

3: Initialize(InstanceTable); {初始化InstanceTable}

4: for i←0 to size do {每一个候选shapelet}

5:   if (InstanceTable.isEmpty()) {若InstanceTable为空,跳出循环}

6:     break;

7:   selectShapelet←candidateShapelets.get(i); {获取候选shapelet}

8:   Shapelets←UpdateCoverage(selectShapelet,δ); {更新InstanceTable}

9:   for j←i+1 to size do {每一个候选shapelet}

10:     ToPrune←candidateShapelets.get(j); {获取待剪枝的shapelet}

11:     PruneShapelets(selectShapelet,ToPrune); {剪枝}

12:   size←UpdateSize();{更新候选shapelets的个数}

13: return Shapelets;

第1行~第3行中,首先初始化了InstanceTable和候选shapelets的数量.然后,对于每一个候选的shapelet,在剪去与它相似的shapelets之前,我们需要检查InstanceTable是否为空:若InstanceTable为空,由于此方法将不会选择任何shapelet,循环就可以直接中断(第5行、第6行).此后,继续更新每一条时间序列的覆盖情况,并剪去相似的shapelets(第7行~第11行),具体方法见第2.2节和第2.3节.当一个候选shapelet访问结束后,因为候选shapelets的数量可能发生了变化,我们得更新size的大小(第12行).最终返回用于数据转换的shapelets.

本节将评估辨别性shapelets在时间序列分类问题上的表现.我们对原有的方法做出了一些改变:

· 首先,将讨论用于数据转换时shapelet覆盖参数δ的最优值;

· 其次,将提出的ShapeletSelection算法与文献[1]中的ShapeletFilter算法、文献[17]中的ClusterShapelet算法以及经典的1-NN分类器相比较,阐明了辨别性shapelets在时间序列分类问题上的优势.所有的算法均是在Weka框架下,使用Java代码实现的.所采用的数据集均包括训练集和测试集,其中,shapelets的发现和分类器的构建都是在训练集上进行的,测试集仅用于测试分类器的分类准确率.我们还需要感谢Lines提供的关于Shape letFilter的源代码.

在时间序列分类任务中,为分类准确率考虑,我们希望用多个shapelets去覆盖某个实例.此部分的目标就是找到一个合适的shapelet覆盖参数δ.为获取最好的δ,我们首先讨论δ和shapelets数量间的关系;然后,试图通过经验估计来设置能够获得最好分类准确率的覆盖参数δ.

图 6展示了δ变化时,17个数据集(见表 2)的shapelets数目的变化.所有的实验都是在这些数据的训练集上进行的.我们可以很明显地观察到:初始时,shapelets的数目会随着δ的增长而增长;当shapelets的数目无法满足δ的需求时会到达shapelets数目的峰值并从图 7中可以发现:当δ=4时,大部分数据集的分类准确率接近或达到了他们的最大值.所以,为保持简洁性和一致性,我们在接下来的实验中将覆盖参数δ设置为4.注意:实验中的所有分类准确率都是通过在训练集上建立分类器,然后在测试集上进行测试所得到的.

图 6(Fig.6)

Fig.6 Relationship between τ 图 6 覆盖参数τ不断增长时shapelet数量的变化

表 2(Table 2)

Table 2 Testing accuracy of ShapeletSelection on different classifiers when δ=4表 2 δ=4时,ShapeletSelection算法在多个数据集上的分类准确率 Data NO. NaïveBayes C4.5 RandomForest 1NN RotationForest BayesNet Average ShapeletFilter CBF 9 99.78% 97.89% 98% 99.67% 99.33% 98.11% 98.80% 92.91% Coffee 7 92.86% 89.29% 92.86% 92.86% 96.43% 92.86% 92.86% 91.67% ECG200 18 21% 21% 18% 12% 14% 19% 17.50% 18.67% ECGFiveDays 10 98.95% 98.95% 99.07% 99.65% 99.30% 99.65% 99.26% 99.19% Cricket 6 70.31% 50% 56.25% 59.38% 51.56% 71.88% 59.90% 59.64% Cricket_new 6 98.98% 66.33% 97.96% 97.96% 89.80% 98.98% 91.67% 92.52% DiatomSizeReduction 8 85.62% 62.09% 91.50% 85.29% 83.99% 82.35% 81.81% 78.87% FaceFour 6 81.82% 75% 93.18% 97.73% 87.5% 96.59% 88.64% 84.47% Gun_Point 15 96.67% 91.33% 99.33% 98.67% 98.67% 100% 97.44% 96.00% ItalyPowerDemand 10 95.92% 94.17% 95.53% 94.85% 96.02% 91.74% 94.70% 93.42% Motes 9 84.74% 81.79% 82.59% 85.94% 86.34% 85.22% 84.44% 82.95% OliveOil 12 93.33% 70% 80% 80% 80% 90% 82.22% 72.22% SonyAIBORobotSurfaceII 10 91.08% 79.54% 87.30% 86.78% 88.35% 88.56% 86.94% 88.53% SonyAIBORobotSurface 7 96.01% 84.86% 88.69% 94.68% 94.34% 95.01% 92.26% 86.99% Symbols 8 76.28% 62.21% 78.09% 82.31% 74.17% 82.21% 75.88% 68.96% synthetic_control 30 98% 92.33% 96.67% 99% 97.67% 97.67% 96.89% 95.17% TwoLeadECG 8 98.77% 86.39% 96.0% 98.95% 96.22% 94.82% 95.20% 92.55%

Table 2 Testing accuracy of ShapeletSelection on different classifiers when δ=4表 2 δ=4时,ShapeletSelection算法在多个数据集上的分类准确率

图 7(Fig.7)

Fig.7 Classification accuracy of 17 datasets the number of shapelet when τ varies 图 7 τ不断增长时17个数据集上准确率的变化

另外发现,候选shapelets时的两个长度参数min和max的设置也是一个难题.由于它们定义了候选shapelets的长度范围,参数设置不对时可能发现不了最具有辨别性的shapelet,从而对分类器的准确率造成影响.为包含尽可能长的长度,我们统一将最小长度设置为n/11,最大长度设置为n/2,n为时间序列中属性的个数.

为说明所提出的shapelet剪枝和shapelet覆盖算法能够提高分类准确率.我们将对比ShapeletSelection算法和ShapeletFilter算法在多个时间序列数据集上的分类准确率.所有的分类器都是在基于shapelets剪枝和覆盖或经典shapelets转换后的数据上训练和测试的.由于本文采用了多个分类模型和数据集来评估所提出的算法,为有效地阐述所提出的ShapeletSelection算法的优点,除分类准确率之外,本文同时采用同一分类模型在相同数据集上的相对准确率和不同分类模型在同一数据集上的平均准确率来进行比对.表 2展示了覆盖参数δ=4时,我们在17个数据集上的测试结果.表中的第1列为所采用的数据的名称;第2列是与δ相对应的shapelets的个数.Average记录了我们所采用的6个分类器的分类准确率平均值.

为方便与ShapeletFilter算法做对比,我们用ShapeletFilter算法做了相同的实验,并在表 2的最后一列列出了ShapeletFilter算法的分类准确率平均值.用于ShapeletFilter算法中的shapelets数量与我们的ShapeletSelection算法相同.结果表明:我们的方法在17个数据集中的14个上优于ShapeletFilter算法,其中在OliveOil数据集上获得了10%的准确率提升.

表 3展示了ShapeletSelection算法对比于经典shapelets的相对准确率.结果表明,ShapeletSelection算法能够提升所有6个分类器的分类准确率.针对所有的情况,我们的方法在近3/4的数据集上具有较好的结果,其中,Naïve Bayes分类器的平均准确性提升了3.64%,单项分类准确率最高提升了23.33%.

表 3(Table 3)

Table 3 Relative accuracies of the classifiers when trained with ShapeletSelection and ShapeletFilter表 3 ShapeletSelection与ShapeletFilter间的相对准确率 Data Na?veBayes C4.5 RandomForest 1NN RotationForest BayesNet Average CBF 1.11% 18.33% 7.11% 0.78% 7.55% 0.44% 5.89% Coffee 0.00% 0.00% 3.57% 0.00% 3.57% 0.00% 1.19% ECG200 -1.00% 4.00% -2.00% -3.00% -4.00% -1.00% -1.17% ECGFiveDays 0.00% 0.00% -0.35% 0.23% 0.35% 0.23% 0.07% Cricket 0.00% 0.00% 0.00% 3.13% -1.57% 0.00% 0.26% Cricket_new 0.00% 0.00% 0.00% 2.04% -7.14% 0.00% -0.85% DiatomSizeReduction 0.00% 0.00% 7.19% -6.54% 16.34% 0.65% 2.94% FaceFour 5.68% 0.00% -2.27% 2.28% 15.91% 3.41% 4.17% Gun_Point 2.67% 0.00% 5.33% -1.33% 0.00% 2.00% 1.44% ItalyPowerDemand 2.04% 5.73% 0.29% -0.87% 2.63% -2.14% 1.28% Motes 0.00% 3.60% 0.16% 0.56% 2.79% 1.83% 1.49% OliveOil 23.33% 10.00% 10.00% 6.67% -3.33% 13.33% 10.00% SonyAIBORobotSurfaceII -1.26% 0.00% -0.63% -4.20% -0.95% -2.52% -1.59% SonyAIBORobotSurface 10.15% 0.00% 0.50% 4.66% 7.98% 8.32% 5.27% Symbols 8.54% -3.22% 11.66% 8.94% 2.81% 12.76% 6.92% synthetic_control 2.67% -1.00% 1.67% 2.00% 1.00% 4.00% 1.72% TwoLeadECG 7.99% 0.00% 3.95% 2.99% 1.40% -0.44% 2.65% Average improved 3.64% 2.20% 2.72% 1.08% 2.67% 2.41% 2.45% Data sets improved 9 5 11 11 11 10 14

Table 3 Relative accuracies of the classifiers when trained with ShapeletSelection and ShapeletFilter表 3 ShapeletSelection与ShapeletFilter间的相对准确率

为缓解最好的k个shapelets中存在相似shapelets的问题,在发现最好的k个shapelets之后,Hill等人^[17]采用层次聚类来获取不相似的shapelets.如Rakthanmanon等人^[8]以及Mueen等人^[7]所述,发现shapelets的时间复杂度为O(n²m⁴),其中,n为数据集中时间序列的条数,m为时间序列的长度.由于shapelets聚类和shapel et剪枝操作都是在产生shapelets后进行的,一般情况下,他们将会比ShapeletFilter花费较多的时间.然而,层次聚类在最坏情况下的时间复杂度为O(p³),即使经过优化,层次聚类的复杂度仍有O(p²logp);而本文所提出的shapelets剪枝和覆盖方法的时间复杂度为O(p²),其中,p为候选shapelets的个数.

为方便对比,本文将文献[17]中ClusterShapelet算法的类簇个数设置为辨别性shapelets的个数(表 4第2列),并做了相应的对比实验.表 4展示了ClusterShapelet算法在不同数据集上的分类准确率.

表 4(Table 4)

Table 4 Testing accuracy of ClusterShapelet on different classifiers表 4 ClusterShapelet算法在多个数据集上的分类准确率 Data NO. Na?veBayes C4.5 RandomForest 1NN RotationForest BayesNet Average CBF 9 84.22% 78.11% 77.33% 86.22% 83.00% 81.89% 81.80% Coffee 7 92.86% 89.29% 89.29% 96.43% 92.86% 92.86% 92.26% ECG200 18 16.00% 18.00% 17.00% 17.00% 15.00% 21.00% 17.33% ECGFiveDays 10 86.53% 85.60% 88.50% 86.06% 92.45% 89.66% 88.13% Cricket_new 6 53.13% 51.56% 54.69% 56.25% 65.63% 81.25% 60.42% Cricket 6 74.49% 67.35% 72.45% 83.67% 85.71% 83.67% 77.89% DiatomSizeReduction 8 77.45% 59.15% 83.99% 91.83% 87.58% 88.56% 81.43% FaceFour 6 77.27% 55.68% 65.91% 77.27% 75.00% 81.82% 72.16% Gun_Point 15 90.00% 90.00% 98.67% 97.33% 97.33% 99.33% 95.44% ItalyPowerDemand 10 95.72% 95.43% 94.85% 94.95% 94.66% 96.31% 95.32% Motes 9 89.46% 69.25% 78.99% 83.31% 89.30% 85.46% 82.63% OliveOil 12 80.00% 63.33% 83.33% 83.33% 80.00% 76.67% 77.78% SonyAIBORobotSurfaceII 10 91.29% 87.62% 78.28% 90.24% 88.88% 90.56% 87.81% SonyAIBORobotSurface 7 75.87% 66.89% 76.71% 72.21% 78.70% 83.69% 75.68% Symbols 8 84.42% 64.82% 69.95% 86.63% 87.74% 76.08% 78.27% synthetic_control 30 90.67% 90.67% 93.67% 92.67% 95.67% 89.00% 92.06% TwoLeadECG 8 95.70% 76.03% 93.77% 94.82% 95.52% 96.75% 92.10%

Table 4 Testing accuracy of ClusterShapelet on different classifiers表 4 ClusterShapelet算法在多个数据集上的分类准确率

表 5展示了ShapeletSelection算法对比于shapelets聚类算法的相对准确率.结果同样表明,基于shapelets剪枝和覆盖的转换方法能够提升所有6个分类器的分类准确率.针对所有的情况,我们的方法在近4/5的数据集上具有较好的结果,RandomForest分类器的平均准确性提升了7.87%,Naïve Bayes分类器在Cricket数据集上的准确率升了24.49%.

表 5(Table 5)

Table 5 Relative accuracies when trained with ShapeletSelection and ClusterShapelet表 5 ShapeletSelection与ClusterShapelet间的相对准确率 Data Na?veBayes C4.5 RandomForest 1NN RotationForest BayesNet Average CBF 15.56% 19.78% 20.67% 13.45% 16.33% 16.22% 17.00% Coffee 0.00% 0.00% 3.57% -3.57% 3.57% 0.00% 0.60% ECG200 5.00% 3.00% 1.00% -5.00% -1.00% -2.00% 0.17% ECGFiveDays 12.42% 13.35% 10.57% 13.59% 6.85% 9.99% 11.13% Cricket_new 17.19% -1.56% 1.56% 3.13% -14.07% -9.37% -0.52% Cricket 24.49% -1.02% 25.51% 14.29% 4.09% 15.31% 13.78% DiatomSizeReduction 8.17% 2.94% 7.51% -6.54% -3.59% -6.21% 0.38% FaceFour 4.55% 19.32% 27.27% 20.46% 12.50% 14.77% 16.48% Gun_Point 6.67% 1.33% 0.66% 1.34% 1.34% 0.67% 2.00% ItalyPowerDemand 0.20% -1.26% 0.68% -0.10% 1.37% -4.57% -0.62% Motes -4.72% 12.54% 3.60% 2.63% -2.96% -0.24% 1.81% OliveOil 13.33% 6.67% -3.33% -3.33% 0.00% 13.33% 4.44% SonyAIBORobotSurfaceII -0.21% -8.08% 9.02% -3.46% -0.53% -2.00% -0.87% SonyAIBORobotSurface 20.14% 17.97% 11.98% 22.47% 15.64% 11.32% 16.58% Symbols -8.14% -2.61% 8.14% -4.32% -13.57% 6.13% -2.39% synthetic_control 7.33% 1.66% 3.00% 6.33% 2.00% 8.67% 4.83% TwoLeadECG 3.07% 10.36% 2.28% 4.13% 0.70% -1.93% 3.10% Average improved 7.36% 5.55% 7.87% 4.44% 1.69% 4.12% 5.17% Data sets improved 13 11 16 10 10 9 13

Table 5 Relative accuracies when trained with ShapeletSelection and ClusterShapelet表 5 ShapeletSelection与ClusterShapelet间的相对准确率

采用欧式距离或者DTW的1-NN分类器,是目前解决时间序列分类问题的最好方法之一.在此部分,我们将采用欧式距离或者DTW的1-NN分类器与在辨别性shapelets转换后的数据上训练和测试的1-NN分类器做对比实验.实验结果见表 6.

表 6(Table 6)

Table 6 Accuracy of DTW and Euclidean distance with 1-NN on raw dataset and the 1-NN classifier built on the shapelets pruning and coverage transformed dataset (%)表 6 基于欧氏距离和DTW的1-NN分类器在原始数据上的分类准确率和在经过 shapelet剪枝和shapelet覆盖后的数据集上建立的1-NN分类器的分类器准确率比对(%) Data 1NN_ED 1NN_DTW 1NN_ED* 1NN_DTW* CBF 85.00 99.67 99.67 98.89 Coffee 75.00 100.00 92.86 96.43 ECG200 11.00 23.00 12.00 21.00 ECGFiveDays 80.60 76.77 99.65 98.72 Cricket_new 43.75 87.50 59.38 64.06 Cricket 87.76 98.98 97.96 100.00 DiatomSizeReduction 93.46 96.73 85.29 96.08 FaceFour 87.50 82.95 97.73 98.86 Gun_Point 92.00 90.67 98.67 99.33 ItalyPowerDemand 95.72 95.04 94.85 95.82 Motes 85.78 83.47 85.94 83.47 OliveOil 76.67 83.33 80.00 73.33 SonyAIBORobotSurfaceII 86.36 83.11 86.78 87.51 SonyAIBORobotSurface 67.72 72.55 94.68 88.19 Symbols 90.35 94.97 82.31 77.29 synthetic_control 88.00 99.33 99.00 92.67 TwoLeadECG 72.52 90.43 98.95 97.54

Table 6 Accuracy of DTW and Euclidean distance with 1-NN on raw dataset and the 1-NN classifier built on the shapelets pruning and coverage transformed dataset (%)表 6 基于欧氏距离和DTW的1-NN分类器在原始数据上的分类准确率和在经过 shapelet剪枝和shapelet覆盖后的数据集上建立的1-NN分类器的分类器准确率比对(%)

在基于欧式距离度量方面,采用ShapeletSelection算法后的1-NN分类器(1NN_ED*)明显优于初始的1-NN分类器.我们同时对比了基于DTW的1-NN(1NN_DTW)和在转换后数据集上训练和测试的1NN-DTW*.没有任何证据表明,基于shapelets剪枝和shapelet覆盖的方法使得分类准确率变低.

在本文中,我们介绍了shapelet剪枝和覆盖技术,提出了一种用于解决时间序列分类问题的辨别性shapelets转换方法,并通过实验阐述了辨别性shapelets在时间序列分类方面的准确性与可解释性.尽管辨别性shapelets能够去除相似的shapelets,辨别性shapelets间仍具有相互重叠的部分.今后,我们将继续研究在保持分类准确率的同时移除掉相互重叠的辨别性shapelets的方法,并将辨别性shapelets应用到多元时间序列分类和其他更多的实际应用问题中.