英语原文共 33 页，剩余内容已隐藏，支付完成后下载完整资料
广义shapelet随机森林
Isak Karlsson, Panagiotis Papapetrou, Henrik Bostrom
(Stockholm University, Stockholm, Sweden)
摘要：shapelet是时间序列中最具有辨别性的子序列，通常嵌入在基于shapelet的决策树中。然而时间序列shapelet枚举计算昂贵，除了决策树学习算法难以有效地处理高维数据外，严重限制了基于shapelet的决策树学习在大型（多元）时间序列数据库中的适用性。本文提出了一种基于树的广义随机shapelet森林算法，利用shapelets实现单变量和多变量时间序列分类。该算法生成一组基于shapelet的决策树，其中用于构建树的实例选择和shapelet的选择都是随机的。对于单变量时间序列，通过大量的实证研究表明，该算法的预测性能可与目前最先进的算法相媲美，并显著优于其他几种算法，同时至少提高了一个数量级。对于多变量时间序列，结果表明该算法的计算开销比目前的算法要小得多，且精度更高。
关键字：多变量时间序列；时间序列分类；时间序列shapelet；决策树；集成方法
1.引言
在许多领域，重复的测量被收集，以获得对象的特征或随时间演变的情况。这些领域的例子包括形状轮廓识别，例如，对历史文档或投射点进行分类,心电图分类（ECGs），和流数据中异常检测（Rebbapragada等，2009）。这些测量数据通常以固定的速率收集，这种集合通常称为数据序列。对于随时间变化的测量，这样的序列称为时间序列，它们可以是单变量（单个变量随时间变化），也可以是多变量（有d个随时间变化的变量）。
本文研究的重点是时间序列分类。换句话说，给定一个时间序列集合，我们希望根据描述一个实例的观测时间序列，推断出一个可以预测分类输出变量值的模型。
举例 让我们考虑一个医学领域的例子。具体来说，给定一名患者的心电图（ECG），我们希望通过利用从不同患者身上采集的、标有分类结果变量的心电图过去观测数据中的信息来推断该患者的心血管疾病状况。因此，在这种情况下，结果变量对应于患者的心脏状况。心电图的一个例子如图1所示。我们可以观察到，在这种情况下，ECG可以建模为一个多变量时间序列，由15个同时进化的变量组成，每个变量对应于一个心脏信号随时间变化的电压。
时间
图1 一个有15个变量的心电图的例子，每一个变量都是一个心脏信号，由一个单独的电压表测量，并随时间变化。心电图可以看作是一个15维的时间序列。
实现快速准确的时间序列分类在过去十年中引起了数据挖掘界的极大兴趣。其中一个研究方向是将时间序列表示为普通的特征向量。这种表示法允许直接应用标准监督学习算法，如决策树、支持向量机（SVMs）、神经网络和最近邻分类器。对于单变量时间序列（UTS）分类，实验证据已被反复证明基于相似性的弹性措施方法，如动态时间扭曲（DTW）提供了最先进的预测性能。然而，多元时间序列（MTS）的特征不仅是个体属性之间的相似性，更是不同属性之间的关系。后者没有被传统的单变量方法所捕获，这导致了对基于特征的方法的关注，如学习模式相似性。
时间序列分类的一个新方法是识别和提取时间序列子序列，称为shapelets，它可以作为分类的判别特征，它们的主要特点是具有类区分性、相位无关性，即位置不变性，较长时间序列的子序列。基于shapelet的单变量时间序列分类方法已经被提出，例如基于shapelet的决策树和使用shapelet转换的预处理方法，对于多元时间序列也提出了类似的方法。有一种方法是为每个维度构建基于shapelet的决策树，然后将单个分类器组合起来使用多数投票结果，而另一种方法是使用加权投票执行shapelet转换。虽然基于shapelet的决策树可以为从业者提供可解释的规则，从而提供内部规律，这已被证实，但它们的分类准确性和培训成本往往令人望而却步，这限制了它们在处理大型和多变量时间序列时的适用性。因此，对基于shapelet的决策树的一个扩展是构成由这些树构成的森林，其中每个单独的树都是通过仅考虑所有可用shapelets的一个子集来构建的。后者可以导致显著的加速，特别是对于较大的多变量时间序列，可以更快地生成整个森林，并获得比单棵树（通过枚举所有shapelets生成）更高的预测性能，类似于随机森林在单个决策树上所做的改进。
本文的主要贡献如下：
求新 我们提出了一种高效、有效的时间序列分类方法。我们的方法的关键新颖之处在于它扩展了随机shapelet森林算法来支持的单变量和多变量时间序列分类。
效率和有效性 通过对单变量和多变量时间序列数据集的广泛实验评估，我们证明了所提出的算法与最先进的方法相比可以获得有竞争力的预测性能，同时平均降低了一个数量级的训练成本。此外，我们使用不同的参数设置来评估该方法的可靠性，同时提供对于不同的情况下如何优化它们的方法，通过分解均方误差的由森林里的单个树分配的类概率偏差和方差来探索评估措施的影响。
适用性 我们证明了该新方法在跨越不同应用领域的大而多样数据集上的适用性，包括56个单变量和14个多变量时间序列数据集。最后，本文提出的算法实现简单、准确、快速、并行，即适用于广泛的任务。
论文的其余部分组织如下：在下一节，我们将讨论时间序列分类的相关工作，重点讨论基于shapelet的分类器和多元时间序列；在第三节中，定义了符号和问题设置；在第四节中，我们提出了生成随机shapelet树森林的算法，并讨论了各种实现选择；第五章给出了实验设置和实验结果；最后在第六部分我们总结了主要发现，并指出了今后的工作方向。
2.相关工作
单变量时间序列分类的大多数方法通常依赖于基于实例的分类算法，例如k-近邻，使用不同的相似性（或距离）度量，其中最常见和最简单的方法是欧几里德范数。为了提高精度，人们提出了一些弹性距离度量方法，如动态时间规整（DTW）或最长公共子序列和变体，如cDTW、EDR、ERP等，这些方法对错位和时间扭曲具有很强的健壮性。这些距离测量允许局部失真，例如，DTW通过允许非线性距离计算来寻找两个序列之间的最佳匹配。通过使用正则化，例如，k近邻的搜索性能和泛化行为可以得到很大的改善。对于基于实例的单变量时间序列分类器的更完整的概述，读者可以参考Ding等人（2008）的论述。虽然DTW算法在多变量情况下的扩展是非平凡的，但是多变量时间序列分类已经提出了几种替代方法，其中最简单、最常用的是所有单变量距离的累积距离。Bankoacute;（2012）提出了另一种选择，提出了基于相关性的DTW（CBDTW），将DTW与主成分分析相结合，保持时间序列之间的相关结构。
为了补充基于实例的分类器并提高生成模型的可解释性，引入了shapelets概念。Shapelets通常被描述为子序列，其与其他时间序列的距离提供了用于分类和解释的区别性特征。对于基于shapelet的分类器，其思想是以分而治之的方式递归地考虑训练数据的所有子序列，同时使用评分函数评估shapelets的质量以评估其鉴别能力，构造一个可解释的shapelet树分类器。
最常见的评分函数是信息增益,这也是构建传统决策树时常用的方法。Ye和Keogh（2009）为了尽早剔除不提供信息的shapelet候选者，从而加速穷举搜索，他们采用了信息增益获取到早抛弃和低边界的方法。然而，由于组合爆炸，当类的数量增加时，信息增益的下界没有变化从而导致不可行。为了克服这个限制，我们考虑了其他基于方差分析的测量方法，其基本原理是这些测量方法的计算成本更低。Hills等（2014）研究表明，虽然使用信息增益和基于方差的方法在预测性能上没有显著差异，但计算成本显著降低。除了这些加速对shapelet的穷举搜索的技术外，文献中还提出了其他一些方法。例如，在寻找最佳匹配的同时，还探索了处理内存消耗的时间复杂度的方法。
决策树是可解释的，这在很多领域都很有用。然而，在预测性能方面，它们几乎在所有情况下都比其他分类器做得更好，比如支持向量机，深度神经网络和随机森林。为了克服这个限制，Hillsetal.（2014）提出了一种单扫描算法来寻找时间序列集合中最好的k个shapelets。随后，使用生成的k个shapelets集合生成一个新的变换后的k-feature数据集，每个属性是第i个shapelet到第j个原始时间序列的最小距离。通过将shapelet搜索和模型生成分开，时间序列分类被简化为一个特征选择（或生成）问题，从而能够使用广泛的高效学习算法。
Shapelet变换是一个更普遍的特征生成概念的实例，它被深入研究以用于时间序列分类。例如，生成特性包括基于间隔的特性，统计特征以及其他可解释的特征，如相关结构、分布或熵。通常，这些转换产生的特性可以分为三个主要类别：基于相关的、基于自相关的和基于形状的，每个类别分别表示时间、变化和形状上的相似性。例如，Deng等人（2013）提出了基于均值、标准差、坡度等区间特征的时间序列森林，Baydogan等人（2013）提出了时间序列词袋的变换。由于穷举shapelet研究需要对训练数据中的每个子序列进行枚举，因此对于大的、多变量的时间序列数据集是不可行的。为了提高搜索速度，通常只考虑特定长度的子序列，例如在预定义范围内的子序列，从而减少搜索空间。最佳shapelet长度通常是未知的，需要使用交叉验证在多个分类器上进行强力搜索。由于计算限制，这通常是不可行的。为了提高性能，Hills等（2014）提出了一种基于启发式算法的shapelet长度估计方法。
对于单变量时间序列分类，Grabocka等人(2014)通过shapelet学习(LTS)的概念，提出了一种在所有shapelets中进行穷举枚举和搜索的方法。在单变量时间序列分类领域，这可以被认为是目前在分类精度方面的最新进展。在该框架中，shapelets从训练数据中学习，同时使用logistics回归损失函数最小化训练误差，使用软最小值来最小化距离。与其他主要基于穷举搜索shaplet的分类器相比，学习shapelets能够显著提高预测性能。除了计算成本高之外，LTS的主要缺点是需要调优的超参数数量多，并且很难选择初始shapelet原型，这通常会对结果的精度产生很大影响。
关于多变量时间序列分类，文献中主要介绍了两种使用shapelets的方法。Patri等（2014）提出了一种shapelet森林，用于对异构的多变量传感器数据进行分类。该算法使用快速shapelet方法从每个维度中提取信息量最大的shapelets。利用这些shapelets计算出一个距离矩阵，并使用不同的特征选择方法为每个shapelet学习权值。另一个新的多变量时间序列的分类是通过对每个维度构建的各个shapelet树的投票进行加权，并将所使用的shapelets的学习权值相加来完成的。Cetin等人（2015）提出了类似的方法，即从每个时间序列维度构建一个shapelet树。针对后者，提出了几种提高搜索速度的技术，使树的构建变得易于处理。通过使用多长度索引和动态步进，这些技术显著提高了生成树的性能。对不同的投票方法进行了评估，结果显示，在每个维度上构建一个shapelet树要优于在多个维度上定义的shapelets。然而，这些方法的主要缺点是，通过为每个维度构建一个独立的树时，这些树没有考虑维度之间的潜在依赖关系。此外，用于确定最终类别的加权投票技术没有考虑不同维度的重要性不同。与shapelet变换相似，Wistuba等人（2015）提出了一种多变量时间序列的方法，超快shapelets（UFS），该方法使用随机shapelets作为特征。作者证明了这种转换既快速又准确。特别是，该方法在多变量时间序列分类方面表现优于相关算法（Wistuba等，2015）。UFS最突出的优点是能够以较低的计算成本建模不同维度之间的关系，这与本文中提出的方法非常相似。然而，与本研究中提出的方法相反，UFS的一个缺点是全局地考虑预先选择的shapelets池中的shapelets，而本研究中提出的方法在每棵树的每个节点上局部地考虑一组shapelets，从而提高了多样性，并将搜索引向更重要的区域。最后，多元时间序列分类的另一个研究方向包括基于特征的方法，如学习模式相似度（LPS）、多元时间序列的符号表示（SMTS）和时间序列词袋的多元扩展。
3.问题设置
本文研究的问题是单变量和多变量时间序列分类，即，当前的任务是，给定一个或多个集值变量，每个变量的值按时间排序，并按固定的时间间隔采样，我们想要推断出一个能够根据观察到的变量准确预测不可见示例的类标签的模型。接下来，我们将提供一些背景定义和问题公式化来研究该问题。
定义1（d维时间序列）一个d维时间序列T={T1，hellip;，hellip;，Td}是d个变量的序列，Tkisin;Rm，forall;kisin;{1，hellip;,hellip;,d},Tk ={Tk,1,...,Tk,m},当中Tk,jisin;R,forall;jisin;{1，hellip;,hellip;,m}。当d=1时，T定义了一个单变量时间序列，简单表示为T={T1，hellip;,Tm}，由m个有序元素Tjisin;R组成该序列。若dgt;1，T定义了多变量时间序列。
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[236361]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
