用于时间序列数据分类的超快速替代方案

时间序列 05/10/2021

三个要点
✔️提出了一个关于时间序列分类的新观点
✔️基于线性分类的训练时间大幅减少，预测精度高
✔️将时间序列数据转换为符号表示，并以χ-平方极限为标准，终止搜索三角树（分支修剪）。

MrSQM: Fast Time Series Classification with Symbolic Representations
written by Thach Le Nguyen, Georgiana Ifrim
(Submitted on 2 Sep 2021)
Comments: Published on arxiv.
Subjects: Machine Learning (cs.LG)

code：

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

简介

本文是关于时间序列数据的分类。它的特点是使用符号表示法和使用具有卡方限制的模式挖掘。该模型的名称是 "多表征序列挖掘机"，缩写为MrSQM。它以早期的线性分类为基础，但在准确性和学习效率上有所提高。

以前的研究

以前关于时间序列分类（TSC）的研究的基线是1-N最邻近的分类（1NN-DTW）。这个模型很简单，但存在着对噪音缺乏稳健性的问题，此后有三个小组开发了这个模型。

1) 集体分类

HIVE-COTE很受欢迎，它是许多分类器的集合，使用不同的数据表示和特征，每个分类器都根据分类的质量进行加权。

问题是，学习UEA/UCR的基准需要两周以上的时间。

2）深度学习分类

FCN、Resnet等都很高效，并显示出与HIVE-COTE相当的准确性。InceptionTime在准确性和差异性方面有所提高，但它仍然需要数周时间来训练。

3）线性分类

这是一种传统的方法，但最近在时间序列库上的使用取得了良好的效果。这种想法已经成功地被纳入大规模的分类器中，如LIBLINEAR。

在TSC中，WEASEL生成一个大的SFA（见下文）单词特征空间，用χ-squared特征选择进行过滤，并训练一个逻辑回归分类器；MrSEOL使用SAX（见下文）和SFA的大特征空间来进行Greedy梯度下降和逻辑回归。最近的ROCKET生成了大量的随机卷积核，并使用了称为最大集合和ppv的新功能。

与集合学习或深度学习相媲美的精确度可以在几个数量级的时间内实现。UEA/UCR基准可以在几个小时内完成培训。

另一个特点是方法的概念简单，可以分为三个阶段：1）数据转换，2）特征选择和3）线性分类。

方法描述

从以前的研究来看，它是基于线性回归的。输入的时间序列数据被转换为符号表示，如SAX和SFA。符号表示法是为文档挖掘而开发的技术，SAX是符号聚合近似法，SFA是符号傅里叶近似法。整个工作流程如图1所示。

时间序列的符号化表示

SAX和SFA在数据转换方面有以下三个共同步骤

1) 在滑动窗口中提取时间序列的一个片段

2) 用一个通常长度较短的向量来近似每一个片段

3）对近似值进行离散化处理，以获得符号词（如abbacc）。

SAX和SFA的主要区别在于近似和离散化技术，总结于表1。

符号序列的特征选择

监督的方法

χ-平方检验是一种著名的对候选特征进行排序的方法。对于某类特征_ck的测量频率_Ok和预期频率_Ek，Chi2的计算方法如下

在符号表示中出现的每个子词都是一个特征的候选者。如果对它们进行详尽的评估，并使用Chi2对它们进行排名，成本会很高；Chi2统计量有一个上限，这对于顺序数据特别有用。上限表示为

由于顺序数据的反单调性，一个序列被保证只出现其前缀的频率。因此，候选特征的Chi2得分可以通过使用方程（2）检查其前缀而过早地得到约束。为了有效地搜索，并有效地使用上界，子序列使用三角树来存储。trie是一个树形数据结构，其中边对应于符号，节点对应于由根到该节点的所有路径的边连接而成的子序列。

每个节点存储相应子序列的倒置索引（位置列表）。通过这种方式，可以通过迭代位置列表快速生成子节点。为了简单起见，我们假设我们在两类序列数据中寻找一个接壤的子序列，并且^Oj值小于或等于它上面的节点。Oj值低于它上面的节点，所以如果我们在某个点上切开阈值，我们就知道它下面的所有东西都在阈值以下，而不必进行搜索。因此，我们从尝试树上修剪。

这是第一次将这种方法应用于时间序列数据。我们已经获得了一种高效的符号表示时间序列分类算法。

另一种选择有用特征的方法是信息增益（IG），它表示预测对目标变量的数据的分割程度。然而，它的分区性能与Chi2相当，而且不能适用于多类，所以我们采用Chi2。

无监督的方法

子序列对序列数据的依赖性很高：如果其中一个子序列被Chi2分数划定，其他子序列也会被划定，并一起被选中。Chi2检验或任何对类似特征进行独立排序的监督方法往往对这种勾稽关系问题很弱。换句话说，排名靠前的特征彼此之间高度相关，所选的特征集存在冗余现象。随机特征选择增加了多样性。

对于一个时间序列的符号表示，符号的子字（子串）是一个候选特征。随机特征选择器只是对时间序列的索引、它在时间序列中的位置和子字的长度进行采样。

混合方法

由于每种方法都有其优点和缺点，监督和非监督方法被结合起来，在MrSQM中有两种结合方式：1）监督特征选择和非监督过滤；2）非监督特征选择和监督过滤。

MrSQM分类器的变体

基于上述概念，我们选择了四种类型。

1) MrSQM-R：通过对特征值的随机抽样进行无监督的特征选择

2）MrSQM-RS：混合方法，通过MrSQM-R选择候选人，并通过监督下的Chi2测试来完善。

3) MrSQM-S：在监督下选择Chi2上界的所有子序列特征来修剪分支，并通过Chi2测试来选择最佳的上界k子序列集

4）MrSQM-SR：混合方法。候选特征由有监督的MrSQM-S生成，并通过随机抽样进行过滤。

评级

设置

该数据集包括来自UEA/UCR TSC档案的112个固定长度的单变量时间序列；MrSQM可以扩展到可变长度。准确度的提高是通过Holm校正的Wilcoxon签名等级测试来衡量的，并通过使用R库scmamp计算的临界差异（CD）图来显示。CD显示了几种数据集的方法在平均准确率方面的排名。CD显示了几种数据集的平均准确度排名，在统计学上没有显著差异的方法用一条横线（表示CD）连接起来，以便于观察是否有显著差异。

敏感度分析

枝条切割效果分析

由于分支修剪（Chi2限制），子序列的数量已经大大减少。

SAX、SFA的比较

在选择SAX或SFA特征的模型之间没有统计学上的显著差异。在MrSQM-R-SS之间发现了一个明显的差异，其中两个特征都被选中。

特征选择方法的比较

MrSQM-RS、MrSQM-R之间以及MrSQM-R、MrSQM-SR和MrSQM-S之间没有显著差异。MRSQM-RS、MrSQM-R和MrSQM-SR、MrSQM-S之间有显著差异。学习和推理的时间是70分钟。

同时使用SAX和SFA功能需要的运行时间大约是使用其中一个的两倍。

MrSQM vs. SOTA象征性TSC

MrSQM和传统的符号化TSC（WEASEL、MrSEQL、BOSS、cBOSS、S-BOSS）在准确性上没有明显的区别。然而，传统的SOTA需要10-12小时以上的培训。

MrSQM与其他SOTA TSC的对比

到目前为止，最准确的时间序列分类器是HIVE-COTE 1.0、TS-CHIEL、ROCKET和Inception Time，除了ROCKET，它需要更多的计算机资源和几天或几周的训练。图7显示了这些方法与MrSQM-RS的准确性比较。

MrSQM-RS的准确性并不逊色，学习速度更快。只有ROCKET的训练和推理时间为1.5小时，与MrSQM-RS相差不大，但ROCKET对某些数据集的准确性有所下降。然而，ROCKET在某些数据集上会降低准确性，而MrSQM-RS则不会；HIVE-COTE等需要密集的超参数调整，而MrSQM则对所有数据集使用默认参数。用过的。