2. 中国矿业大学 安全工程学院, 江苏 徐州 221006
2. School of Safety Engineering, China University of Mining and Technology, Xuzhou Jiangsu 221006, China
Shapelets 是描述时间序列局部特征的子序列，是时间序列中一种微小的局部模式，具有高度的辨识性[1]。基于shapelets的时间序列分类方法，能够发现时间序列之间具有微小区别的局部特征，不仅分类精度高，对分类的结果也有很好的解释能力，已经成为时间序列领域一个重要的研究主题，受到了越来越多的关注[2-5]，并被广泛应用到聚类[6]、姿势识别[7]、早期分类[8]等领域。
原始基于shapelets的分类方法将shapelets的求解与时间序列的分类过程通过一个决策树算法完成，用于产生shapelets候选集的时间复杂度均为O(n2m4)，n为数据集中时间序列的条数，m为时间序列的长度，计算出所有shapelets的集合需要耗费的时间非常惊人。因此，提高shapelets候选集的计算效率成为一个重要的研究方向。文献[1]采用提前停止距离计算和熵剪枝的加速方法；其他的加速技术依赖于计算的重用和对搜索空间的精简[3]，或者在使用符号聚集近似(Symbolic Aggregate approXimation，SAX)表示的基础上对候选的shapelets进行剪枝[4]，以及使用非频繁shapelets[9]和一定数量的随机shapelets[10]；此外，文献[11]中采用并行化的方法提高搜索速度。
另一方面，基于shapelets转换的时间序列分类方法[5]将shapelets的发现过程和分类算法分离开来，从候选集中选取最优的k个shapelets特征，是此类方法的关键。为了确定需要选取的shapelets的数量，文献[5]中使用的5折交叉验证的方法会耗费大量时间，并且不能解决被选择的shapelets之间存在较大相似性的问题。为了解决这个问题，ClusterShapelet算法[12]使用聚类的方法对候选集进行筛选，ShapeletsSelection方法[13]提出了shapelets覆盖的概念来确定shapelets候选集中最优shapelets的个数。但是，运用shapelets覆盖所选取的shapelets，彼此之间仍会有相互重叠的部分，而且会受到评判顺序的影响。这两种方法用于产生shapelets候选集的时间复杂度均为O(n2m4)，时间复杂度较高。
针对目前求解最优shapelets集合不能有效去除冗余，无法高效选取最具代表性的k个shapelets，影响了分类准确率及效率的问题，本文引入数据检索领域的多样化top-k查询方法，对候选的shapelets进行处理，从中选出最具有辨别能力且彼此不相似的shapelets，提高了shapelets特征选择的准确性；同时，借鉴文献[4]中的方法，提高最优shapelets候选集的计算速度，从而从整体上提高基于shapelest转换的分类方法的效率。
1 符号与定义围绕本文的相关工作，以下先给出一些关于shapelets[1]及多样化top-k查询[14]的基本概念。
定义1 分裂点。一个分裂点由一个子序列S和一个距离阈值d组成，可表示为一个元组〈S,d〉。它可以将一个数据集分成两个更小的数据集DL和DR，其中时间序列的个数分别为nL和nR。对于DL中的每个时间序列Ti,L，都有SubsequenceDist(S,Ti,L)＜d；对于DR中的每个时间序列Ti,R，都有SubsequenceDist(S,Ti,R)≥d。其中 SubsequenceDist(S,T)表示子序列S与序列T之间的最小距离。
定义2 信息增益。一个分裂点〈S,d〉的信息增益为:
| $IG(＜S,d>)=E(D)-\frac{{{n}_{L}}}{n}E({{D}_{L}})-\frac{{{n}_{R}}}{n}E({{D}_{R}})$ |
定义3 shapelet。数据集D的shapelet是一个最优分裂点，它能将数据集D分成两部分，使最终的信息增益的值最大。可表示如下:
| $IG\left( \left\langle shapelet(D),{{d}_{osp}} \right\rangle \right)\ge IG(S,d)$ |
定义4 多样化top-k查询。给定一个集合I={v1,v2,…,vn}，对于每一个vi∈I，v的分值为score(vi)。对于vi,vj∈I，有一个用户定义相似度函数sim(vi,vj)和阈值τ，如果sim(vi,vj)>τ，则vi和vj相似，表示为vi≈vj。
给定一个整数k(1≤k＜n)，I的多样化的top-k结果记作Q(I)，是满足下面三个条件的一组结果:
1) Q(I)⊆I,|Q(I)|≤k；
2) 对于任意两个元素vi,vj∈I，vi≠vj，如果vi≈vj，则{vi,vj}⊄Q(I)；
3) $\sum\limits_{{{v}_{i}}\in Q(I)}{score}({{v}_{i}})$是最大的。
直观上看，Q(I)就是至多k个结果的集合，其中没有任意两个元素是彼此相似的，同时这些元素所对应的总分值最大。
定义5 多样化图。给定一个集合，I={v1,v2,…,vn}，I的多样化图表示为G(I)=(V,E)。其中：G是一个无向图；V是I中所有变量组成的顶点集合；若vi≈vj成立，则vi与vj之间有一条边E。不失一般性，假定G(I)中顶点的编号是按照顶点分值的非递增顺序排列，即：
score(vi)≥score(vj); 1≤i＜j≤|V(G(I))|
在定义1~5的基础上，本文提出相似shapelets及多样化top-k shapelets的概念，用来求解最优shapelets集合。
定义6 相似shapelets。对于两个时间序列的shapelets Si和Sj(1≤i＜j≤n,i≠j)，n是shapelets候选集中元素的个数，最优分裂点〈Si,d〉和〈Sj,d〉对应的距离阈值分别为di和dj，如果Si和Sj满足dist(Si,Sj)≤min(di,dj)，那么Si和Sj是相似的，记作Si≈Sj。
定义7 多样化top-k shapelets。在候选的shapelets集合I={S1,S2,…,Sn}中，满足下列条件的k个shapeletes集合称为多样化top-k shapelets，表示为DivTopk(I)：
1) DivTopk(I)⊆I,|DivTopk(I)|≤k；
2) 对于任意两个shapelets，Si,Sj∈I，Si≠Sj，如果Si≈Sj，则{Si,Sj}⊄DivTopk(I)；
3) $\sum\limits_{{{S}_{i}}\in I}{score({{S}_{i}})}$是最大的。
与传统多样化top-k查询的概念相比，多样化top-k shapelets查询所使用的分值为shapelets的信息增益值，相似度函数满足相似shapelets的条件。
2 本文方法基于多样化top-k shapelets转换的分类方法包括三部分：1) 计算shapelets候选集；2) 计算多样化top-k shapelets集；3) 对数据集进行转换，并将转换后的数据应用于时间序列分类过程。
原始计算shapelets候选集的方法，时间复杂度为O(n2m4)，对大多数场景都是不可取的。本文借鉴文献[4]中的方法，将原始的实值和高维数据进行SAX转换；接着使用多样化top-k查询方法对候选的shapelets进行筛选。筛选方法:构造多样化图，求解分类效果最优且不相似的k个shapelets。最后，将k个最优的shapelets作为特征属性，对待测数据进行转换，将每个序列转换为一个包含k个属性的特征向量，使其能够适用于任何典型的时间序列分类算法。
2.1 产生shapelets候选集产生shapelets候选集的过程，是得到最优shapelets的基础，原始算法复杂度过高，本文参考文献[4]中的方法，对原始数据进行SAX转换，从而大幅降低产生shapelets候选集所需的时间。
2.2 多样化top-k shapelets集计算 2.2.1 构造多样化图在候选shapelets集合的基础上，应用定义5~6，构造多样化图，具体过程见算法1。
算法1 conShapeletGraph(allShapelets)。
输入 shapelets候选集allShapelets；
输出 所有shapelets构成的多样化图Graph。
1) Graph=∅
2) sort(allShapelets)
3) for i=1 to |allShapelets|
4) Graph.add(allShapelets [i])
5) end for
6) for j=1 to |allShapelets|
7) for k=1 to |allShapelets|
8) if(allShapelets[j]≈allShapelets[k])
9) Graph[j].add(Graph[k])
10) Graph[k].add(Graph[j])
11) end for
12) end for
13) return Graph
算法1首先初始化多样化图Graph(第1) 行)，并对shapelets候选集中的所有shapelets按信息增益的非递增顺序排序(第2) 行)。然后，将所有的shapelets均设为多样化图的顶点(第3) ~5) 行)。对于图中所有的顶点，按照定义6相似shapelets的计算方法，判断所有的顶点两两之间是否相似(第8) 行)。如果相似，那么这两个顶点之间就会存在一条边，可以将顶点加入到对方的邻接节点中(第9) ~10) 行)。
图 1给出了ChlorineConcentration数据集上候选shapelets集合构造的多样化图，其中图(a)为10个候选shapelets集合，图(b)为该shapelets集合的多样化图，图中节点的编号按照shapelet增益值的非递增顺序排列，即编号越小，其代表的shapelet增益值越大。运用多样化top-k查询算法，最终可以得到图 1(a)中三条加粗的序列，直观上看，这三条序列的形态各不相同，且具有一定的代表性，应该具有最好的分类效果。
|
图 1 候选shapelets构成的多样化图举例 Figure 1 Examples of diversified graph consisted of candidate shapelets |
传统的top-k查询中，返回的结果仅仅基于对象的分值，而多样化top-k查询能够既考虑结果的分值，又兼顾对象之间的相关性，移除结果中的冗余项。这种方法恰好能够解决求解最优shapelets集合的问题，具体过程见算法2。
算法2 DivTopKShapelet(Graph,k)
输入 多样化图Graph，k值输出 top-k shapelets。
1) kShapelets=∅,n=|V(Graph)|
2) kShapelets.add(v1)
3) while(|kShapelets|＜k)
4) for i=2 to n
5) if(Graph[i]∩kShapelets=∅)
6) kShapelets.add(vi)
7) end if
8) end for
9) return kShapelets
该算法首先将信息增益最大的shapelet(v1)放到kShapelets集合中(第2) 行)。如果k=1，此时算法将会结束，并返回该shapelet；否则，对于多样化图中的其他节点，如果该节点的邻接节点都不在kShapelets中，就可以将该节点加入到kShapelets中(第3) ~8) 行)。最后返回k个多样化shapelets(第9) 行)。
2.3 基于多样化shapelets的数据集转换进行多样化shapelets转换的目的是为了将传统的分类算法应用于转换后的时间序列数据集上。在找到k个多样化shapelets后，利用这k个shapelets将原始的时间序列数据集进行转换，每条时间序列都可以表示为拥有k个属性的实例，每个属性的值为时间序列与shapelets之间的距离。这样就把时间序列分类问题看作是一般的分类问题，其具体过程此处不再赘述。
2.4 算法时间复杂度分析本文首先通过SAX转换，将计算shapelets候选集的时间复杂度由O(n2m4)降为O(nm2)；构造多样化图所需的时间复杂度为O(p2)，p为候选shapelets的个数；计算多样化top-k shapelets集的时间复杂度为O(k2p2)。从后面的实验部分得知，当k>4时，分类的准确率就会在一个很小的范围内波动，k可以看作常数。因此，算法的总体复杂度为O(nm2)+O(p2)。而ClusterShapelet方法和ShapeletsSelection方法的时间复杂度分别为O(n2m4)+O(p3)和O(n2m4)+O(p2)。
3 实验结果和分析为了评估多样化shapelets的有效性，本文采用来自UCR[15]的时间序列数据集进行测试，所采用的数据集均包括训练集和测试集。shapelets的产生和构建分类器的过程都在训练集上进行，测试集只用于测试分类器的分类准确率。本文的算法和实验都在Weka框架下使用Java代码实现的。
为方便对比，本文将DivTopKShapelet算法与其他分类器的结合使用，统一都命名为DivTopKShapelet算法。首先运用DivTopKShapelet算法对训练集求取最优shapelets集合，之后对训练集进行转换，结合其他分类算法构建分类器。
3.1 shapelets长度和k值的确定与文献[4]中shapelets的提取方法类似，算法1中有两个参数需要设置：min和max。这两个参数用来决定所要产生候选shapelets的长度范围，如果设置不合理，算法可能无法找到最具辨识力的shapelets，进而对最终的分类结果造成影响。为了保持一致性和简洁性，本文采取与文献[13]相同的做法，统一将最小长度设置为m/11，最大长度设置为m/2，m为时间序列的长度。
图 2展示了随着k的变化，15个数据集在6种分类器上平均准确率的变化。随着k值的增加，数据集的准确率逐渐趋于一个稳定值，在进行分类准确率对比时将k值统一设置为9。
|
图 2 15个数据集准确率随k的变化曲线 Figure 2 Accuracy rate curve of 15 data sets changing with k |
为了更加直观地说明本文工作，本节将DivTopKShapelet与和本文工作最相似的ShapeletSelction算法的最优shapelets集合进行比较，选取TwoLeadECG数据集，结果如图 3所示。shapelets最优集指算法在取得最好分类效果时的shapelets集合。对于TwoLeadECG数据集，当DivTopKShapelet算法的分类效果最好时，shapelets的个数为2，因此k取2。从图中可以看出，在获得最优分类准确率时，DivTopKShapelet算法可以有效筛选出形态上最具有代表性的2个shapelets，而shapeletSelection方法只能筛选出14个最优shapelets，其中仍然存在一定的冗余；同时，DivTopKShapelet算法拥有更高的分类准确率。
|
图 3 最优shapelets集合对比 Figure 3 Comparison between the optimal shapelets sets |
为了说明本文出的DivTopKShapelet算法能够提高时间序列的分类准确率，将该算法与传统分类方法、ClusterShapelet算法和ShapeletSelction算法在15个UCR数据集上的分类 准确率进行对比，从平均准确率和相对准确率两个方面验证本文的DivTopKShapelet算法在时间序列分类问题上的有效性。每种算法在相同数据集上运行10遍，获取平均值作为最终的准确率，所选取的shapelet的个数设为k=9。
3.3.1 DivTopKShapelet与传统分类方法比较本节选取C4.5、1-最近邻(1-Nearest Neighbor,1NN)、朴素贝叶斯(Naive Bayes，NB)、贝叶斯网络(Bayesian Network，BN)、随机森林(Random Forest，RanF)和旋转森林(Rotation Forest，RoF)共6种分类方法，直接对15个数据集进行分类，准确率结果位于表 1中C4.5、1NN、NB、BN、RanF和RoF中“单独”所在的列；同时，将DivTopKShapelet方法分别与这6种分类方法进行结合也对15个数据集进行分类，准确率结果位于相应的“结合”所在列。而且为了表示方便，将15个数据集分别编号为1~15。
|
表 1 DivTopKShapelet与传统时间序列分类方法准确率比较 % Table 1 Accuracy comparison between DivTopKShapelet and traditional time series classification algorithms % |
进一步，为了说明DivTopKShapelet方法与每种分类器结合后的表现，图 4给出了DivTopKShapelet与传统时间序列分类方法之间的相对准确率曲线。相对准确率的值由DivTopKShapelet算法在数据集上结合6个分类器得到的准确率减去相对应传统时间序列分类算法的准确率得到。相对准确率大于0表示DivTopKShapelet方法优于传统分类方法。
|
图 4 DivTopKShapelet与传统时间序列分类方法间的相对准确率 Figure 4 Relative accuracy between DivTopKShapelet and traditional time series classification algorithms |
从图 4可以看出，NB在13个数据集上的相对准确率大于0，C4.5、1NN和BN在10个数据集上的相对准确率大于0，RanF和RoF分别在9个和8个数据集上的相对准确率大于0。这表明相比传统分类方法，DivTopKShapelet算法可以提高大多数数据集的分类准确率。
所有6个分类器在ECGFiveDays、Gun_Point、SonyAIBORobotSurface、SyntheticControl、Trace和TwoLeadECG这6个数据集上的相对准确率得均大于0。C4.5在Coffee数据集上的准确率提升效果最好，为35.72%，1NN和RoF在SonyAIBORobotSurface数据集上的准确率分别提高了27.79%和22.63%，NB在TwoLeadECG数据集上的准确率提高了29.85%，BN和RanF在Coffee数据集上的准确率分别提高了32.14%和28.57%。
3.3.2 DivTopKShapelet和ClusterShapelet本节对DivTopKShapelet算法和ClusterShapelet算法在6种分类器上的相对准确率进行比较，图 5为DivTopKShapelet与ClusterShapelet算法之间的相对准确率曲线。
|
图 5 DivTopKShapelet与ClusterShapelet方法间的相对准确率 Figure 5 Relative accuracy between DivTopKShapelet and ClusterShapelet |
在图 5中，C4.5和RandomForest在13个数据集上的相对准确率大于0，1NN和BN在12个数据集上的相对准确率大于0，NB和RoF分别在11个和10个数据集上的相对准确率大于0。与ClusterShapelet算法相比，DivTopKShapelet算法至少可以提高10个数据集的分类准确率。
在图 5中，6个分类器在15个数据集中的8个上的相对准确率均大于0。C4.5在ECGFiveDays数据集上的准确率提升效果最好，为48.43%，1NN和BN在SonyAIBORobotSurface数据集上的准确率分别提高了37.44%和30.12%，NB在MoteStrain数据集上的准确率提高了31.79%，RanF和RoF在ECGFiveDays数据集上的准确率分别提高了29.85%和29.15%。
3.3.3 DivTopKShapelet和ShapeletSelection本节对DivTopKShapelet算法和ShapeletSelection算法在6种分类器上的相对准确率进行比较，结果如图 6所示。
|
图 6 DivTopKShapelet与ShapeletSelection方法间的相对准确率 Figure 6 Relative accuracy between DivTopKShapelet and ShapeletSelection |
从图 6可知，1NN在11个数据集上的相对准确率大于0，C4.5和RoF在10个数据集上的相对准确率大于0，NB在8个数据集上的相对准确率大于0，BN和RanF在7个数据集上的相对准确率大于0。这表明DivTopKShapelet算法在大多数的数据集上要优于ShapeletSelection算法。
图 6中的6个分类器在AdiacSonyAIBORobotSurface数据集上的相对准确率均大于0。1NN在SonyAIBORobotSurface数据集上的准确率提升效果最好，为32.61%，C4.5在SonyAIBORobotSurface数据集上的准确率提高了16.97%，NB、BN、RanF和RoF在Adiac数据集上的准确率分别提高了17.14%、16.37%、26.09%和23.02%。
3.4 时间对比表 2给出了本文提出的DivTopKShapelet算法与ClusterShapelet算法和ShapeletSelection算法在6个分类器上的平均运行时间对比，其中“加速倍数”为DivTopKShapelet算法对ClusterShapelet算法和ShapeletSelection算法的加速倍数，计算方法为分别用ClusterShapelet算法和ShapeletSelection算法的运行时间除以DivTopKShapelet算法的运行时间。其中“—”代表时间相对过长，不再进行比较。
|
|
表 2 DivTopKShapelet与ClusterShapelet和ShapeletSelction的平均运行时间对比 Table 2 Average running time comparison between DivTopKShapelet,ClusterShapelet and ShapeletSelction |
从表 2中可以看出，由于DivTopKShapelet算法相当于对数据集进行了降维，从n*m长度的时间序列数据，转换为n*k的矩阵，k＜＜m，因此，DivTopKShapelet算法在所有的数据集上都有时间效率的提升。其中，在MedicalImage数据集上的加速效果最好，加速倍数达到了287.8。
由表 2可知，与ShapeletSelection算法相比，DivTopKShapelet算法提升的时间效率更为明显。由于ShapeletSelection算法在求取Shapelets候选集时采用未进行优化的求解算法，因此时间复杂度较高。
4 结语本文提出了一种基于多样化top-k shapelets转换的时间序列分类方法，解决了候选shapelets之间存在冗余和shapelets计算效率低的问题。通过对候选shapelets集合进行多样化top-k查询筛选出其中最具有代表性且互不相似的shapelets，实现对原始数据集的转换和后续分类。实验结果表明，多样化top-k shapelets转换技术可以提高15个时间序列数据集中大部分数据集分类的准确率，并明显提升分类速度。
| [1] | YE L, KEOGH E. Time series shapelets:a new primitive for data mining[C]//KDD'09:Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York:ACM, 2009:947-956. |
| [2] | YE L, KEOGH E. Time series shapelets:a novel technique that allows accurate, interpretable and fast classification[J]. Data Mining and Knowledge Discovery, 2011, 22 (1) : 149-182. |
| [3] | MUEEN A, KEOGH E, YOUNG N. Logical-shapelets:an expressive primitive for time series classification[C]//KDD'11:Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York:ACM, 2011:1154-1162. |
| [4] | RAKTHANMANON T, KEOGH E. Fast shapelets:a scalable algorithm for discovering time series shapelets[C]//SDM 2013:Proceedings of the Thirteenth SIAM Conference on Data Mining. Philadelphia, PA:Society for Industrial and Applied Mathematics (SIAM), 2013:668-676. |
| [5] | LINES J, DAVIS L M, HILLS J, et al. A shapelet transform for time series classification[C]//KDD'12:Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York:ACM, 2012:289-297. |
| [6] | ZAKARIA J, MUEEN A, KEOGH E. Clustering time series using unsupervised-shapelets[C]//ICDM 2012:Proceedings of the IEEE 12th International Conference on Data Mining. Washington, DC:IEEE Computer Society, 2012:785-794. |
| [7] | HARTMANN B, LINK N. Gesture recognition with inertial sensors and optimized DTW prototypes[C]//SMC 2010:Proceedings of the IEEE International Conference on Systems, Man and Cybernetics. Piscataway, NJ:IEEE, 2010:2102-2109. |
| [8] | XING Z, PEI J, YU P S, et al. Extracting interpretable features for early classification on time series[C]//SDM 2011:Proceedings of the 2011 SIAM International Conference on Data Mining. Philadelphia, PA:Society for Industrial and Applied Mathematics (SIAM), 2011:247-258. |
| [9] | HE Q, DONG Z, ZHUANG F, et al. Fast time series classification based on infrequent shapelets[C]//ICMLA 2012:Proceedings of the 201211th International Conference on Machine Learning and Applications. Washington, DC:IEEE Computer Society, 2012, 1:215-219. |
| [10] | WISTUBA M, GRABOCKA J, SCHMIDT-THIEME L. Ultra-fast shapelets for time series classification[J]. Journal of Data & Knowledge Engineering, 2015 . |
| [11] | CHANG K-W, DEKA B, HWU W-M W, et al. Efficient pattern-based time series classification on GPU[C]//ICDM 2012:Proceedings of the IEEE 12th International Conference on Data Mining. Washington, DC:IEEE Computer Society, 2012:131-140. |
| [12] | HILLS J, LINES J, BARANAUSKAS E, et al. Classification of time series by shapelet transformation[J]. Data Mining and Knowledge Discovery, 2014, 28 (4) : 851-881. doi: 10.1007/s10618-013-0322-1 |
| [13] | 原继东, 王志海, 韩萌. 基于Shapelet剪枝和覆盖的时间序列分类算法[J]. 软件学报, 2015, 26 (9) : 2311-2325. ( YUAN J D, WANG Z H, HAN M. Shapelet pruning and shapelet coverage for time series classification[J]. Journal of Software, 2015, 26 (9) : 2311-2325. ) |
| [14] | QIN L, YU J X, CHANG L. Diversifying top-k results[J]. Proceedings of the VLDB Endowment, 2012, 5 (11) : 1124-1135. doi: 10.14778/2350229 |
| [15] | CHEN Y, KEOGH E, HU B, et al. The UCR time series classification archive[DB/OL].[2015-07-01]. http://www.cs.ucr.edu/~eamonn/time_series_data/. |