基于区间的时间序列分类算法的研究

来源:用户上传      作者:

　　摘   要：时间序列分类是时间序列数据挖掘的一个分支，针对传统时间序列分类模型存在的失真的问题，文章提出了基于区间权值的集成算法EAIW（Ensemble Algorithm of Interval Weights）。首先利用区间权值计算方法，为时间序列的不同区间赋予不同的权值，对计算做了并行化处理，以解决子序列特征不明显的问题。进而确定集成分类器的基分类器，以保证集成分类器的性能。然后，在训练集上训练集成分类器，并行化改进集成分类器训练、分类较为耗时的部分。文章将提出的算法在时间序列分类数据库上进行了实验，结果表明提出的算法比基准算法最优正确率数目高25%，并且算法在并行化之后具备可伸缩性。
　　关键词：时间序列;分类;数据挖掘;CUDA
　　1 引言
　　时间序列是以均匀时间间隔连续测量的多个实值数的序列，一般被认为是一个整体，而不是单独的数值字段[1，2]。时间序列可以反映事物的变化与发展，其广泛存在于各行各业，如生物信息学、金融学、工程学。时间序列数据挖掘可以分为分类、聚类、检索、预测、频繁模式发现[3]。本文主要研究时间序列分类。
　　传统的时间序列分析模型的建立依赖于严密的数学理论与假设，仅在假设合理时传统方法才有效，否则所建立的模型将面临严重失真的问题。与传统的时间序列分析不同的是，时间序列数据挖掘不需要具备严格的数学理论以及平稳、线性且符合正态分布等假设，它可以根据经验，发现数据中存在的新的有价值的模式、信息等。
　　本文主要工作是，为时间序列区间赋予权值，采用集成分类的算法，通过权值对时间序列进行分类。此外，针对分类器训练、预测运行时间较长的问题，基于CUDA[4]，对本文的分类器中较为耗时的部分进行了并行化改进。
　　2 相關工作
　　近年来，提出了许多不同的时间序列分类算法。Kate[3]通过计算测试集中时间序列与训练集中所有时间序列的DTW（Dynamic Time Warping）距离，并将其作为该时间序列的特征，再将该特征输入至分类器中，以达到对时间序列分类的目的。Ye等人[5]提出了基于时间序列shapelets构建决策树的分类算法。Fang Z等人[6]对Ye等人的算法进行了改进。首先从分段聚合近似（Piecewise Aggregate Approximation，PAA）词空间中发现shapelet候选词，然后引入覆盖度的概念来度量候选对象的质量，并设计了一种计算shapelet的最佳数量的方法解释分类决策。Fulcher等人[7]通过从时间序列分析文献中的上千种特征中选择最具判别性的特征集，来解决时间序列分类问题。Hatami等人[8]使用递归图（recurrence plot）把序列转化为纹理图像，再基于特征袋（Bag of Features，BoF）方法对它们进行分类。Ergezer H等人[9]提出了一种利用特征协方差矩阵进行时间序列分类的新方法。Silva等人[10]指出DTW距离计算中存在的问题，为解决该问题，忽略DTW距离计算中首尾的一小部分，通过引入一个参数来描述忽略部分的多少，解决该问题。
　　基于集成学习的分类算法，Sch?fer[11]提出了BOSS（Bag-of-SFA-Symbols）算法，通过对时间序列的子序列应用SFA[12]，其可以获得一种对噪声与冗余数据容忍度较高的时间序列模型，并基于该模型构建多个分类器对时间序列进行分类。
　　本文主要贡献：（1）引入时间序列区间权值，使子序列更有区分度;（2） 使用GPU，对区间权值计算过程与集成分类器训练过程做出并行化改进。对时间序列进行分类时，目前许多研究只采用单一分类器，效率低下。另一些研究虽然采用集成分类器，但时间序列的特征选择不佳，导致算法正确率低下。因此，选用时间序列区间权值作为分类特征，采用集成算法，对时间序列分类，提高了分类正确率。
　　3 区间权值计算
　　3.1 最近邻算法
　　在时间序列研究中，常用的基准算法就是最近邻算法（1 Nearest Neighbor，1NN），下面对其进行简要介绍。
　　给定训练集，其中包含条时间序列，分别属于个类别，定义待分类时间序列到训练集中时间序列的距离为：。若满足公式（1），则最邻近分类器认为待分类时间序列的类别为。
　　（1）最近邻算法常用的距离度量有两种，分别为欧几里得距离（Euclidean Distance，ED）与DTW距离。在本文中使用欧几里得距离进行区间权值计算，使用DTW距离算法作为基分类器的算法。
　　3.2 权值的计算
　　在一些数据集中，当时间索引处于某些区间内时，数据集中各个类别的时间序列的子序列不具有能够显著区分类别的特征。比如在一些区间内，数据受到了较多的噪声的干扰。而在另一些区间内，可能会存在能够较好地区分不同类别的特征。面临这样的数据集时，该分类器的分类准确率会下降。
　　为了解决上述问题，本文为时间序列的不同区间赋予不同的权值，该权值代表了其区分数据集中不同类别时间序列的能力。权值越大，表示该区间区分类别的能力越强，反之则越小。并将时间序列区间的权值作为相应的基分类器的权值。
　　若某一区间内存在较多能够区分不同类别的特征，则分类器在该区间上的分类准确率必然较高，反之分类准确率会较低。因此，使用分类准确率作为区间的权值是合理的。1NN-ED分类器与本文基分类器所采用的1NN-DTW分类器较为接近，因此使用其计算区间的权值，能够近似地反映该区间作为1NN-DTW的训练集使用时的分类能力。此外，欧几里得距离与DTW距离相比，计算时的时间复杂度较低，对于需要计算训练集中全部区间的权值的EAIW算法而言，能够减少训练时间。
　　时间序列区间的示意图如图1所示，[ta，tb]为一个区间，对应了图中时间序列的一条子序列。 　　在给出计算时间序列区间的权值的算法之前，首先给出时间序列区间的定义。
　　定义1 时间序列区间：给定时间序列，其中时间索引，将[ta，tb]称为时间序列区间，其中，且a < b。
　　本文中的时间序列区间的权值是指时间序列数据集的训练集的子集的权值，该子集由训练集中处于该区间内的所有时间序列的子序列所构成，且该子集被用做基分类器的训练集。本文所采用的时间序列数据集中的所有时间序列的长度均相等，因此某一条时间序列的区间也可以对应其他时间序列相同位置的区间，从而构成训练集在该区间上的子集。该权值在分类器训练时得出，用于后续的预测类标号的过程中。下面给出时间序列区间的权值的形式化定义。
　　定义2 时间序列区间的权值：给定时间序列数据集的训练集，其在区间[ta，tb]上的子集为，，该子集所对应的权值为，将该权值称为时间序列区间的权值。
　　为了能够反映某一区间区分不同类别的时间序列的能力大小，同时充分利用训练集，本文采用了留一交叉验证（leave-one-out cross validation）的思想，来计算区间的权值。留一交叉验证的示意图如图2所示。对于区间[ta，tb]，计算其权值如公式（4）所示：
　　3.3 计算并行化
　　本文引入权值矩阵W来记录每个GPU线程的计算结果，线程的计算结果记录在W的元素中。同时该矩阵也能够为GPU线程指示其需要计算的区间。每个GPU线程仅计算一个区间的权值。区间与W的行号、列号的对应关系如公式（5）、公式（6）所示：
　　4.1 基于区间的基分类器
　　本文提出的EAIW算法是一种集成算法，对于时间序列长度为m的数据集，则集成分类器由m-1个构造相似的基分类器所构成。由于时间序列长度m可能很大，造成基分类器数量较多，因此在选择基分类器时要遵循三个基本要求。
　　（1）简单有效。由于集成分类器中可能存在较多基分类器，因而要求基分类器结构要简单，以免造成分类算法运行时间过长的问题。简单的同时，还要保证算法的有效性，基分类器的分类准确率也要高。
　　（2）非参数。在时间序列分类的相关文献中，常用于确定分类器参数的方法为交叉验证，此方法十分耗费时间。对于每个存在参数的基分类器，都需要使用交叉验证来确定其参数，这对于内部存在较多基分类器的集成分类器而言，是不可取的。
　　（3）基于实例。基于实例的分类器无需经过训练就可以直接对时间序列进行分类，能有效地提高集成分类器的效率。
　　根据上述三点要求，因此选择1NN分类器作为基分类器。在1NN分类器的距离度量方面，选择DTW作为其距离度量。与欧几里得距离相比，DTW距离能够更加有效地应对时间序列中特征的形变，从而提高分类准确率。
　　4.2 训练集成分类器
　　本文提出的EAIW算法在对测试集进行分类之前，需要在训练集上进行训练。在训练过程开始之前，首先对训练集中的时间序列进行z-score标准化。z-score标准化是时间序列分类文献中常用的数据预处理方法，该方法将一条时间序列中的数据点的均值化为0，标准差化为1。将序列标准化，以便使时间序列之间的距离能够反映它们之间的相似程度。接下来EAIW算法需要计算训练集上所有区间的权值，其遍历所有区间的方式为，对于任一时间索引 ，将其作为区间的左端点，从最小的区间长度2开始，每次为区间长度增加1，直至区间的右端点等于时间序列的长度m，计算区间的权值weight。这一过程的示意图如图3 所示。
　　该过程与使用不同长度的滑动窗口获取全部区间相比，更有利于后续的并行化。对于时间序列长度为m的数据集，此过程会计算全部m（m-1）/2个区间的权值，如果产生与之相同数量的基分类器，则后续的分类过程将会十分耗时。因此EAIW算法仅使用某一时间索引产生的具有最高权值的区间来构建基分类器，该区间以及其权值记录在训练结果 中。这样可以提高基分类器的质量，提升分类准确率;同时又能够减少基分类器的数量，降低集成分类器对测试集分类时所需的时间。EAIW算法的总体示意图如图4 所示。
　　在对测试集分类之前，与训练时相同，首先对其进行z-score标准化。第i个基分类器在对测试集进行分类时，不对整个测试集中的時间序列进行类标号预测，而是预测其区间[[i][1][1]，  [i][1][2]]所对应的测试集的子集的类标号。基分类器的结合策略为加权投票，对于第i个基分类器，其权值为[i][2]。EAIW算法对测试集进行分类的伪代码如算法4所示。
　　4.3 并行化集成分类器
　　集成分类器的并行化方案为每个GPU线程使用第j个基分类器预测测试集中时间序列的类标号。为此引入矩阵P来记录GPU线程预测的类标号，P的行数为k，与测试集中时间序列的数量相对应，P的列数为m-1，与基分类器数量相对应。P中元素记录预测出的类标号。并行集成分类器的核函数的伪代码如算法5所示。
　　计算DTW距离时需要构建矩阵，该矩阵所需的空间为，现今所有支持CUDA的GPU的线程本地内存（local memory per thread）仅为512KB，该空间开销对于单个GPU线程而言过于庞大。例如，当时间序列的长度为512，时间序列中的数据使用单精度浮点数（占用4字节）存储时，则计算DTW距离需要至少1MB的内存空间，大于GPU线程的本地内存。因此本文使用降低了空间复杂度的DTW距离，使用它可以使本文中所用到的时间序列长度最长的数据集所需的空间小于512KB。
　　矩阵P计算完成后，对其每行由基分类器集合得到的结果进行加权投票，对应的基分类器的权值为。该过程结束后，可得到测试集中每条时间序列的预测类标号。
　　5 性能评价
　　5.1 实验环境
　　本文算法实现环境为Intel（R） Core（TM） i7-8700 CPU @ 3.2GHz，24.00G 内存，GP107 型GPU。算法基于Python实现，以PyCharm为主要开发工具，在Windows 10平台下调试运行。 　　算法实现中所用到的库主要包括：NumPy、SciPy以及Numb等。其中Numba用于将Python代码编译为CUDA核函数以及设备函数。
　　5.2 算法分类准确率评价
　　5.2.1 数据集
　　本文使用UEA&UCR时间序列分类数据库中的数据集，该数据库中共包含85个数据集，这些数据集被近年来的许多时间序列分类文献所采用。本文将这些数据集分为两个部分，一部分用于确定集成算法EAIW中结合策略的参数，称为train;另一部分用于与其他算法进行分类准确率的对比，称为test。
　　train与test的划分原则是，使它们中的数据集的数量尽可能相等，且TSCI的分布近似相同。这样可以避免引入额外的偏差，影响最终结果。
　　5.2.2 分类准确率
　　本节将EAIW与基准算法1NN以及BOP算法进行分类准确率对比，如表1所示。其中1NN-ED与1NN-DTW分别采用的是欧几里得距离与DTW距离。BOP算法基于时间序列的词袋表示。分类准确率为分类正确的时间序列数量与测试集中时间序列总数之比。
　　由表1可知，四者的最优个数分别为15、10、12、7，因此本文提出的算法的最优正确率数目比基准算法高25%以上，43个数据集的平均准确率为0.763、0.743、0.760、0.729，本文提出的算法依然最高，这说明了本文算法的有效性。
　　5.3 算法运行时间评价
　　5.3.1 数据集
　　影响本文提出算法的运行时间的因素主要包括：训练集大小、测试集大小以及时间序列长度，本文从这三个方面来评价并行化改进后算法的运行时间。使用UEA&UCR数据库中的第5个数据集WormsTwoClass，评价时间序列长度对算法运行时间的影响，并将数据集的训练集与测试集大小扩充为前文中提及的85个数据集相应部分的平均值，训练集的平均大小为529，测试集的平均大小为1068。时间序列的长度范围为100至900，记录每个时间序列长度对应的算法的训练时间、分类时间以及总运行时间。使用UEA&UCR数据库中的第13个数据集Ham，评价训练集大小与测试集大小对运行时间的影响。该数据集的时间序列长度为431，接近85个数据集的平均时间序列长度为422。训练集与测试集的大小范围为100至900，记录每个训练集与测试集大小对应的算法的训练时间、分类时间以及总运行时间。在上述两个评价过程中，如果所用的数据集的训练集或测试集的大小不能满足实验要求，则使用其训练集中的第一条时间序列与其对应的类标签将训练集或测试集扩充至指定大小。
　　5.3.2 运行时间评价
　　并行化改进后的EAIW算法的运行时间随时间序列长度的变化如图5所示。由图5可知，随着时间序列长度的增加，训练时间、分类时间以及总时间的增长均较为缓慢。训练时间总体上低于分类时间，这是由于训练时的区间权值计算使用了时间复杂度较低的欧几里得距离，而分类时采用了时间复杂度较高的DTW距离所导致的。图5表明并行化改进后的EAIW算法的运行时间具备对于时间序列长度的可伸缩性。
　　并行化改进后的EAIW算法的运行时间随训练集与测试集大小的变化如图6所示。由图6 可知，随着训练集与测试集大小的增长，并行化改进后的EAIW算法的训练时间的增长幅度较小，说明算法对训练集与测试集大小具有可伸缩性;而分类时间与总运行时间的增长幅度较大。这说明分类耗时对于时间序列长度的增加较不敏感，而对于训练集与测试集大小的增加较为敏感。其原因在于分类时使用的基分类器是基于实例的，且计算DTW距離的时间复杂度较高，因此每个基分类器的分类耗时会随训练集大小而较快地增加，导致总分类时间的增加。同时测试集的增加又进一步增加了分类耗时，这两个因素导致了分类时间对于训练集与测试集大小的增加较为敏感。
　　6 结束语
　　时间序列是一种日常生活中广泛存在的数据形式，在时间序列数据上进行数据挖掘可以发现一些新的知识与模式。本文针对传统分类算法存在的失真问题，提出了基于区间的集成分类算法EAIW，并在时间序列分类文献中常用的数据集上，对本文提出的算法进行了实验，与其他算法进行了对比，实验结果显示算法准确率优于基准算法。针对多分类器训练、预测运行时间较长的问题，对本文的分类器中较为耗时的部分进行了基于CUDA并行化改进，算法具备可伸缩性。
　　基金项目：
　　1.国家自然科学基金资助项目（项目编号：61872073，61572123）;
　　2.辽宁省高校创新团队支持计划资助项目（项目编号：LT2016007）。
　　参考文献
　　[1] Fu T. A review on time series data mining[J]. Engineering Applications of Artificial Intelligence， 2011， 24（1）： 164-181.
　　[2] Ma L.B ， A Novel Many-objective Evolutionary Algorithm Based on Transfer Learning with Kriging model， Information Sciences，2019， DOI： 10.1016/j.ins.2019.01.030.
　　[3] Kate R J. Using dynamic time warping distances as features for improved time series classification[J]. Data Mining & Knowledge Discovery， 2015， 30（2）： 283-312.
　　[4] NVIDIA Developer Zone， CUDA toolkit documentation[EB/OL]. https：//docs.nvidia.com/cuda/cuda-c-programming-guide/， 2018. 　　[5] Ye L， Keogh E. Time series shapelets： a new primitive for data mining[C]//Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM， 2009： 947-956.
　　[6] Fang Z， Wang P， Wang W. Efficient Learning Interpretable Shapelets for Accurate Time Series Classification[C]//2018 IEEE 34th International Conference on Data Engineering （ICDE）. IEEE， 2018： 497-508.
　　[7] Fulcher B D， Jones N S. Highly comparative feature-based time-series classification[J]. IEEE Transactions on Knowledge & Data Engineering， 2014， 26（12）： 3026-3037.
　　[8] Hatami N， Gavet Y， Debayle J. Bag of recurrence patterns representation for time-series classification[J]. Pattern Analysis & Applications， 2018： 1-11.
　　[9] Ergezer H， Leblebicio?lu K. Time series classification with feature covariance matrices[J]. Knowledge and Information Systems， 2018， 55（3）： 695-718.
　　[10] Silva D F， Batista G E A P A， Keogh E. Prefix and suffix invariant dynamic time warping[C]. IEEE International Conference on Data Mining， 2017： 1209-1214.
　　[11] Sch?fer P. The BOSS is concerned with time series classification in the presence of noise[J]. Data Mining and Knowledge Discovery， 2015， 29（6）： 1505-1530.
　　[12] Sch?fer P. SFA： a symbolic fourier approximation and index for similarity search in high dimensional datasets[C]. International Conference on Extending Database Technology， 2012： 516-527.
转载注明来源:https://www.xzbu.com/1/view-15129780.htm