卷积小形变换提高重复模式的准确性

时间序列 26/11/2021

三个要点
✔️ Shapelets被发现具有很强的解释力，但在建模精度上较差。
✔️ 卷积等内核方法被认为是更准确的，但解释力较差。
✔️ 将扩张与小形状结合起来，同时满足

Convolutional Shapelet Transform: A new approach for time series shapelets
written by Antoine Guillaume, Christel Vrain, Elloumi Wael
(Submitted on 28 Sep 2021)
Comments: Published on arxiv.
Subjects: Computer Vision and Pattern Recognition (cs.CV); Machine Learning (cs.LG)

code：

本文所使用的图片要么来自论文、介绍性幻灯片，要么是参考这些图片制作的。

简介

通常情况下，会重复一系列的特征动作，例如在驱动机器人手臂时。有一个shaplet的概念，可以把一连串的动作当作一个单元，但在建模的准确性方面还有待改进。在本文中，我们对这样的领域提出了一个建议。

时间序列数据被用于许多不同的领域，为了在该领域安全地使用算法，有时有效地解决问题与理解决策背后的原因同样重要。最近在时间序列分类方面的研究产生了具有高准确性的算法，但代价是时间效率差。卷积核方法具有类似的性能，但具有极高的可扩展性，是朝着这个方向迈出的一步。然而，这些方法，特别是内核方法，都不容易解释。另一方面，基于shapelets的方法，虽然没有这些方法好，但可以产生对领域专家来说容易理解的结果。

在本文中，我们介绍了卷积小形变换（CST），它是对时间序列小形的一种改编，将扩张的概念（用于卷积核）引入小形。我们还提出了一种从卷积核中提取判别性的卷积小图的算法。这种算法使我们能够产生小的非连续的判别性子序列，与时间序列的长度无关。我们表明，这种方法是一种新的基于shaplet的算法，不仅与最先进的shaplet方法有竞争力，而且可以被看作是解释卷积核方法的工具。本文的贡献可以概括为以下几点

- 启用了扩展时间序列shapelets的使用。

- 一种提取卷积shapelets的方法，它依赖于卷积核的输出和其识别数据的能力。

- 与最重要的shaplet和卷积核方法进行比较研究。

- 提供卷积核的可解释性的方法

为了让大家对本文有一个直观的了解，我们举了一个例子。这是一个使用经典的 "GunPoint "数据集[17]的直观例子（见图1）。这个数据集是基于一个记录演员的一只手的运动的传感器。0类代表演员拿出枪，对准枪，然后把枪放回枪套，而1类代表演员在不拿出枪的情况下做同样的动作。

背景介绍

作为背景，我们将重点介绍两种方法，它们是我们提出的方法的核心。

形状

shaplet被定义为代表一个类别成员的时间序列子序列。在大多数情况下，基于shaplet的算法由三个步骤区分：候选shaplet的生成、过滤和评估。在最初的方法中，shaplet被用来构建一个 "shaplet树"。候选人是通过列举树的节点的时间序列中存在的所有长度为l的子序列来提取的。然后计算和评估与输入的距离，并通过信息增益选择分割当前节点的最佳候选人：S = {v1,.,vl}是一个长度为l的shaplet，其值为z归一化（即μS=0，σS=1），X={x1，...}。,xn}是一个时间序列，shaplet距离是S与X的所有长度为l的z归一化子序列之间的最小距离。

shaplet变换算法避免了在树的每一步对shaplet进行评估，而是从N个输入时间序列中提取M个候选shaplet，然后只进行一次评估，产生一个N×M距离矩阵作为分类器的输入数据。这个矩阵被称为 "shaplet变换"。图2显示了一个有两个shaplet的例子。许多算法都是在小形状的基础上设计的，其中一些算法使用离散化或随机选择来过滤掉候选小形状，还有一些算法从数据中构建小形状的位置索引，并生成有限的候选小形状。最近一些进化方法和神经网络的工作包括将小形状的位置作为一个特征，而其他的，如我们的方法，从输入数据的不同表示中提取小形状。

随机卷积核变换

RandOm卷积神经传递系统（ROCKET）随机初始化了大量的卷积核（默认为10.000）。这样的内核是K={l，_{w1，...。,_wl},b,d,p}，其中l是内核的长度，w是权重，b是偏置，d是扩张，p是填充。使用这个内核，我们可以从时间序列的卷积中创建特征，并将其反馈给分类器（图3）。给定一个时间序列X_={x1,...._,xn}和一个内核K，卷积产生一个大小为n-((l-1)×d)+2p的向量C，其中向量的位置i定义如下

在这种情况下，一个点_xi∈X在计算C时可以被多次使用。(例如，_xi可以用来计算任何c∈（c0,...,ci），取决于扩展和长度）。,ci）可以用来计算C）。如果使用填充，在x的开头和结尾添加零，以便内核在所有点上都是中心。每个核产生两个特征，最大值（max）和卷积产生的向量中正值的百分比（ppv）。如果产生N个核，转换将输出2N个特征。ROCKET的版本。用{-1,2}选择权重，只提取ppv特征。

在下文中，给定一个双数序列X和一个内核K，产生卷积C的函数被称为_CK(X)，所有X∈$/chi $的卷积空间被称为_CK(X)的集合。

卷积小形变换

这是因为，给定一个内核K，如果从K产生的卷积空间中提取的ppv统计量可以将数据划分为更纯粹的（在信息增益的意义上）子集，这意味着这是由输入空间的每个子集特有的模式引起的卷积空间的差异的结果。此外，由于ppv是基于在卷积中具有正值的点的比例，给定由K生成的卷积空间，如果索引i的一个点在数据的一个子集中对ppv有正贡献，而在另一个子集中有负贡献，那么用于计算这个i的值的卷积这意味着输入空间中的点形成一个模式，有助于识别子集。在本文中，我们利用在卷积空间中发现的差异，从输入空间中提取这种判别模式，并构建一个卷积小体，根据提取的模式对时间序列进行比较。我们将卷积shaplet定义为S = {d,l, {v1,., vl}}，其中d是一个扩展参数，l是长度，{v1,.,vl}是Z的归一化值。时间序列X的shaplet距离是通过考虑X的所有大小为l的子序列以及元素之间的扩展d来定义的。卷积小分队S和时间序列X之间的距离函数D写为：。

利用这组距离函数和卷积小图，我们可以构建小图变换，然后将其用于分类算法。算法1假设X ={X1,....,Xn}作为一组偶数长度的输入时间序列，Y_={y1,...}。_,yn}作为各自的类，并概述了该方法。

内核和数据分割生成

第一步是生成一组核，从中提取ppv统计量和一个矩阵L，计算X的每个点在_CK(χ)的卷积运算中出现的次数，该运算对每个样本X∈χ和每个核K∈Κ产生正值。内核的生成依靠的是与Mini-ROCKET相同的方法。

一旦输入被生成，下一步就是分离出可用于将数据分割成更纯粹的子集的鉴别性核。为了反映这个想法，ExtractNodes函数生成了一个由n_trees决策树组成的森林，以所有内核的ppv统计数据为特征。然后，它提取森林中的每个节点，并存储该节点的输入数据、该节点输出的两个分区，以及用于划分该节点输入数据的特征（即内核）。这使我们能够探索节点的集合，其中内核被用来创建输入数据的一个更纯粹的子集。请注意，通过使用决策树的集合，潜在的抽样被考虑到了，重复的节点也被删除。

形状-let的提取

从上一步我们得到一个矩阵L和一组树状节点。每个节点由一个内核_Ki表示，它产生用于分割数据的ppv特征，X是该节点使用的输入时间序列，Y是在该节点进行的分割。给定树节点的内核_Ki，我们确定卷积空间中产生ppv差异的点，并提取该差异在Y的类之间最大的shapelets。为了计算这个差异，我们首先需要为X的每个样本找到卷积空间中每个点的分数，然后为每个类别构建一个分数，为其计算差异。该类分数旨在衡量卷积空间中的一个点对该类样本导致正值的可能性。为了计算X的每个样本的分数，用矩阵L表示，将卷积空间中每个卷积操作中使用的所有点的贡献相加。的所有点在卷积空间中的每一次卷积操作中使用。这就产生了一个形式为(|X|,|X| - (l - 1) × d)的矩阵L，其中L[j,c]是样本j与内核_Ki的卷积的第c点的得分。从这个矩阵中，将一个类的每个样本的L相加，就可以得到每个类的分数LC。鉴于这两个新矩阵，为了提取分区Y中两个班级中每个班级的候选小形状，我们计算一个班级的LC和另一个班级的LC之间的差异，得出每个班级的向量D。如前所述，这种操作背后的直觉是，D中某一点的值越高，在这一点上，Ki卷积就越有可能对一类样本输出正值，对另一类样本输出负值。然后，我们通过查看D中高于百分位数P的部分，就知道在哪里提取候选人，如图4所示。提取本身采取了在P处预选的每个区域，并注意到m为该区域最大值的索引，搜索当前类的哪个样本j使L[j,m]最大化。如果找到了，就用_Ki的第m次卷积操作中使用的这个样本的值创建一个候选。

最后，RemoveSimilar(Candidates,n_bins)函数用均匀间隔的n_bins离散了所有共享相同扩展的候选值。一旦所有的候选值都被离散化，它就会删除重复的候选值，并将其他候选值保留为小形状，用于小形状变换。我们强调以下两点

- 卷积shaplet的长度不取决于输入时间序列的长度，而只取决于内核的长度。此外，使用扩张的方法可以消除shaplet是一个连续子序列的要求。

- 具体化减少了候选人的数量，产生了不一定存在于输入空间的小形状，并限制了过度训练。

实验

在下文中，我们使用卷积小形变换与山脊分类器作为分类器，并将其表示为CST。我们提供了一个使用社区标准的Python包，以在任何数据集上运行该方法，以及我们实验中使用的脚本和数据。在比较研究中，我们使用了UCR档案中的108个单变量数据集，其中一个子集用于敏感性分析，两个大数据集用于可扩展性分析。结果显示了使用临界差异图和使用Wilcoxon-Holm事后分析计算出的添加小溪（横条中的连接）对象的平均等级。峭壁表明对象之间的差异没有统计学意义。在下文中，我们将CST与Shapelet Forest分类器（SFC）、MrSEQL、Shapelet Transform分类器（STC）和Mini-ROCKET（MiniRKT）进行比较。

参数的敏感度分析

对于仓位，在所做的比较中没有显著差异；对于P，在80以上出现了显著差异。就树木的数量而言，在250个异常点之后没有任何改善。

可扩展性

图6显示了每种方法的平均总执行时间，包括shaplet提取、距离计算、分类和预测，当并行线程数限制在20个并进行10次重采样时。SFC和CST之间执行时间的差异部分是由于在当前版本中，树节点提取和shapletSFC和CST之间的差异也是由于在目前的版本中，树节点的提取和shaplet距离的计算是在一个线程中进行的；只比较一个线程时，差异要小得多，部分原因是MrSEQL在其算法中使用了SAX等近似技术，对于长时间序列来说比CST更有效率，但这这一优势并不适用于样本的数量。

比较评价

图7显示，平均而言，CST比其他基于shapelet的算法略好，但差异不大。表1显示，CST在心电图和EPG记录数据上比其他算法更有效，但在模拟数据上效果较差。表1显示，CST在心电图和EPG数据上比其他算法更有效，但在模拟数据上效果较差。应该注意的是，CST的一些结果可以通过使用非线性模型（如随机森林）来改进，如Adiac数据集（Adiac的准确率约为10%）。在这些数据集上，CST很可能会产生大量与线性模型无法有效使用的类没有直接联系的shapelets；MiniRKT平均来说还是比CST好。

可解释性

图8举例说明了解释过程的各个阶段可能是什么样子。对于小形状，显示了每类小形状距离的倒数，与要分析的样本的距离用红线表示。视觉化。在boxplot之后，会显示带有Z轴归一化值的shaplet，以及表明其延伸的X轴标签。最后，显示测试样本和小形体之间最佳匹配的位置。Shaplet的比例是通过反转Z-normalization来实现的，因此它的比例与它所处的子序列相同。我们可以将内核中的所有小形状可视化，以了解它们的行为。这样的图可以用来显示决策树中样本决策路径中的每一个shaplet，或者用来选择线性模型中每个类的最高系数的shaplet。提供了一个接口来测试在线存储库中任何数据集的方法。

摘要

卷积小形变换是一种处理时间序列小形的新方法，通过使用扩展，可以将非常小的非连续子序列作为小形，有效地覆盖数据中的利益区域。实验表明，与其他基于shaplet的算法相比，这种新方法在合理的计算成本下改进了最先进的shaplet算法。这里我们只举了一个基本的例子，说明如何使用该方法来解释卷积核的结果，但在未来我们将更深入地探索该方法提供的可能性，以便为使用卷积核的方法建立一个可靠的解释工具。我们还在进行其他一些项目。我们还想加强该方法，使其能够使用更多从卷积中提取的统计数据，就像我们最近的论文一样。这可能会使卷积小图识别出更多的模式。此外，他们正在考虑将该算法扩展到多变量分析，并使用其他模型来提取 shapelets。再加上进一步的优化，可能会大大改善该方法的时间性能。