对工夫序列进行分类是利用机器和深度学习模型的常见工作之一。本篇文章将涵盖 8 种类型的工夫序列分类办法。这包含从简略的基于间隔或距离的办法到应用深度神经网络的办法。这篇文章旨在作为所有工夫序列分类算法的参考文章。
工夫序列定义
在涵盖各种类型的工夫序列 (TS) 分类办法之前,咱们先对立工夫序列的概念,TS 能够分为单变量或多变量 TS。
- 单变量 TS 是一组有序的(通常)实数值。
- 多变量 TS 是一组单变量 TS。每个工夫戳都是一个向量或实数值数组。
单或多元 TS 的数据集通常蕴含一个单或多元 TS 的有序集。此外,数据集通常蕴含由一个繁多编码的标签向量示意,其长度示意不同类的标签。
TS 分类的指标是通过在给定数据集上训练任何分类模型来定义的,这样模型就能够学习所提供数据集的概率分布。也就是说当给定 TS 时,模型应该学会正确地调配类标签。
基于间隔的办法
基于间隔或最近邻的 TS 分类办法应用各种基于间隔的度量来对给定数据进行分类。它是一种监督学习技术,其中新 TS 的预测后果取决于与其最类似的已知工夫序列的标签信息。
间隔度量是形容两个或多个工夫序列之间间隔的函数,它是决定性的。典型的间隔度量是:
- p 范数(如曼哈顿间隔、欧几里德间隔等)
- 动静工夫规整 (DTW)
决定度量后,通常利用 k 最近邻 (KNN) 算法,该算法测量新 TS 与训练数据集中所有 TS 之间的间隔。计算完所有间隔后,抉择最近的 k 个。最初新的 TS 被调配到 k 个最近街坊中的大多数所属的类别。
尽管最风行的范数必定是 p 范数,尤其是欧几里德间隔,但它们有两个次要毛病,使它们不太适宜 TS 分类工作。因为范数仅针对雷同长度的两个 TS 定义,实际上并不总是可能失去长度相等的序列。范数仅独立比拟每个工夫点的两个 TS 值,然而大多数 TS 值互相关联。
而 DTW 能够解决 p 范数的两个限度。经典的 DTW 能够最小化工夫戳可能不同的两个工夫序列点之间的间隔。这意味着轻微偏移或扭曲的 TS 依然被认为是类似的。下图可视化了基于 p 范数的度量与 DTW 的工作形式之间的差别。
联合 KNN,将 DTW 作为基准基准算法,用于 TS 分类的各种基准评估。
KNN 也能够有决策树的办法实现。例如,邻近森林算法建模了一个决策树森林,应用间隔度量来划分 TS 数据。
基于区间和频率的办法
基于区间的办法通常将 TS 宰割为多个不同的区间。而后应用每个子序列来训练一个独自的机器学习 (ML) 分类器。会生成一个分类器汇合,每个分类器都作用于本人的区间。在独自分类的子序列中计算最常见的类将返回整个工夫序列的最终标签。
工夫序列森林
基于区间的模型最驰名的代表是工夫序列森林(Time Series Forest)。TSF 是建设在初始 TS 的随机子序列上的决策树的汇合。每棵树负责将一个类调配给一个区间。
这是通过计算汇总特色(通常是均值、标准差和斜率)来为每个距离创立特征向量来实现的。之后依据计算出的特色训练决策树,并通过所有树的少数投票取得预测。投票过程是必须的,因为每棵树只评估初始 TS 的某个子序列。
除了 TSF 之外,还有其余基于区间的模型。TSF 的变体应用附加特色,例如子序列的中值、四分位数间距、最小值和最大值。与经典的 TSF 算法相比,还存在一种相当简单的算法,称为 Random Interval Spectral Ensemble (RISE)算法。
RISE
RISE 算法在两个方面有别于经典的 TS 森林。
- 每棵树应用单个 TS 距离
- 它是通过应用从 TS 中提取的光谱特色来训练的(而不是应用汇总统计数据作为均值、斜率等)
在 RISE 技术中,每个决策树都建设在一组不同的傅里叶、自相干、自回归和局部自相干特色之上。该算法按如下形式工作:
抉择 TS 的第一个随机区间,并在这些区间上计算上述特色。而后通过组合提取的特色创立一个新的训练集。在这些根底上,训练决策树分类器。最初应用不同的配置反复这些步骤以创立集成模型,该模型是单个决策树分类器的随机森林。
基于字典的办法
基于字典的算法是另一类 TS 分类器,它基于字典的构造。它们涵盖了大量不同的分类器,有时能够与上述分类器联合应用。
这里是涵盖的基于字典的办法列表:
- Bag-of-Patterns (BOP)
- Symbolic Fourier Approximation (SFA)
- Individual BOSS
- BOSS Ensemble
- BOSS in Vector Space
- contractable BOSS
- Randomized BOSS
- WEASEL
这类的办法通常首先将 TS 转换为符号序列,通过滑动窗口从中提取“WORDS”。而后通过确定“WORDS”的散布来进行最终分类,这通常是通过对“WORDS”进行计数和排序来实现的。这种办法背地的实践是工夫序列是类似的,这意味着如果它们蕴含类似的“WORDS”则属于同一类。基于字典的分类器次要过程通常是雷同的。
- 在 TS 上运行特定长度的滑动窗口
- 将每个子序列转换为一个“WORDS”(具备特定长度和一组固定字母)
- 创立这些直方图
上面是最风行的基于字典的分类器的列表:
Bag-of-Patterns 算法
模式袋 (Bag-of-Patterns, BOP) 算法的工作原理相似于用于文本数据分类的词袋算法。这个算法计算一个单词呈现的次数。
从数字(此处为原始 TS)创立单词的最常见技术称为符号聚合近似 (SAX)。首先将 TS 划分为不同的块,每个块之后都会标准化,这意味着它的均值为 0,标准差为 1。
通常一个词的长度比子序列中实数值的数量要长。因而,进一步对每个块利用分箱。而后计算每个分箱的均匀理论值,而后将其映射到一个字母。例如,对于所有低于 -1 的平均值,调配字母“a”,所有大于 -1 和小于 1 的值“b”,所有高于 1 的值“c”。下图形象化了这个过程。
这里每个段蕴含 30 个值,这些值被分成 6 个一组,每个组被调配三个可能的字母,形成一个五个字母的单词。最初汇总每个词的呈现次数,并通过将它们插入最近邻算法来用于分类。
Symbolic Fourier Approximation
与上述 BOP 算法的思维相同,在 BOP 算法中,原始 TS 被离散化为字母而后是单词,能够对 TS 的傅里叶系数利用相似的办法。
最驰名的算法是 Symbolic Fourier Approximation (SFA),它又能够分为两局部。
计算 TS 的离散傅立叶变换,同时保留计算系数的子集。
- 监督:单变量特征选择用于依据统计数据(如 F 统计量或 χ2 统计量)抉择排名较高的系数
- 无监督:通常取第一个系数的子集,代表 TS 的趋势
后果矩阵的每一列都被独立离散化,将 TS 的 TS 子序列转换为单个单词。
- 监督:计算分箱边缘,使得实例熵的杂质规范最小化。
- 无监督:计算分箱边缘,使其基于傅立叶系数的极值(分箱是对立的)或基于这些的分位数(每个分箱中的系数数量雷同)
基于下面的预处理,能够应用各种不同算法,进一步解决信息以取得 TS 的预测。
BOSS
Bag-of-SFA-Symbols (BOSS) 算法的工作原理如下:
- 通过滑动窗口机制提取 TS 的子序列
- 在每个片段上利用 SFA 转换,返回一组有序的单词
- 计算每个单词的频率,这会产生 TS 单词的直方图
- 通过利用 KNN 等算法联合自定义 BOSS 度量(欧氏间隔的渺小变动)进行分类。
BOSS 算法的变体蕴含很多变体:
BOSS Ensemble
BOSS Ensemble 算法常常用于构建多个单个 BOSS 模型,每个模型在参数方面各不相同:字长、字母表大小和窗口大小。通过这些配置捕获各种不同长度的图案。通过对参数进行网格搜寻并仅保留最佳分类器来取得大量模型。
BOSS in Vector Space
BOSS in Vector Space (BOSSVS) 算法是应用向量空间模型的个体 BOSS 办法的变体,该办法为每个类计算一个直方图,并计算词频 - 逆文档频率 (TF-IDF) 矩阵。而后通过找到每个类的 TF-IDF 向量与 TS 自身的直方图之间余弦类似度最高的类,失去分类。
Contractable BOSS
Contractable BOSS(cBOSS) 算法比经典的 BOSS 办法在计算上快得多。
通过不对整个参数空间进行网格搜寻而是对从中随机抉择的样本进行网格搜寻来实现减速的。cBOSS 为每个根本分类器应用数据的子样本。cBOSS 通过仅思考固定数量的最佳基分类器而不是高于特定性能阈值的所有分类器来进步内存效率。
Randomized BOSS
BOSS 算法的下一个变体是 Randomized BOSS (RBOSS)。该办法在滑动窗口长度的抉择中增加了一个随机过程,并奇妙地聚合各个 BOSS 分类器的预测。这相似于 cBOSS 变体,缩小了计算工夫,同时仍放弃基准性能。
WEASE
通过在 SFA 转换中应用不同长度的滑动窗口,TS 分类词提取 (WEASEL) 算法能够进步规范 BOSS 办法的性能。与其余 BOSS 变体相似,它应用各种长度的窗口大小将 TS 转换为特征向量,而后由 KNN 分类器对其进行评估。
WEASEL 应用特定的特色推导办法,通过仅应用利用 χ2 测验的每个滑动窗口的非重叠子序列进行,过滤掉最相干的特色。
将 WEASEL 与 Multivariate Unsupervised Symbols(WEASEL+MUSE)相结合,通过将上下文信息编码到每个特色中从 TS 中提取和过滤多元特色。
基于 Shapelet 的办法
基于 shapelets 的办法应用初始工夫序列的子序列 (即 shapelets) 的思维。抉择 shapelets 是为了将它们用作类的代表,这意味着 shapelets 蕴含类的次要特色,这些特色可用于辨别不同的类。在最优的状况下,它们能够检测到同一类内 TS 之间的部分相似性。
下图给出了一个 shapelet 的示例。它只是整个 TS 的子序列。
应用基于 shapelets 的算法须要确定应用哪个 shapelets 的问题。能够通过手工制作一组 shapelets 来抉择,但这可能十分艰难。也能够应用各种算法主动抉择 shapelets。
基于 Shapelet 提取的算法
Shapelet Transform 是由 Lines 等人提出的一种基于 Shapelet 提取的算法,是目前最罕用的算法之一。给定 n 个实值观测值的 TS, shapelet 由长度为 l 的 TS 的子集定义。
shapelet 和整个 TS 之间的最小间隔能够应用欧几里德间隔 - 或任何其余间隔度量 - shapelet 自身和从 TS 开始的所有长度为 l 的 shapelets 之间的间隔。
而后算法选出 k 个长度属于肯定范畴的最佳 shapelets。这一步能够被视为某种单变量特征提取,每个特色都由给定数据集中 shapelet 与所有 TS 之间的间隔定义。而后依据一些统计数据对 shapelets 进行排名。这些通常是 f 统计量或 χ²统计量,依据它们区分类的能力对 shapelets 进行排序。
实现上述步骤后,能够利用任何类型的 ML 算法对新数据集进行分类。例如基于 knn 的分类器、反对向量机或随机森林等等。
寻找现实的 shapelets 的另一个问题是可怕的工夫复杂性,它会随着训练样本的数量成倍增加。
基于 Shapelet 学习 的算法
基于 Shapelet 学习的算法试图解决基于 Shapelet 提取的算法的局限性。这个想法是学习一组可能区分类的 shapelet,而不是间接从给定的数据集中提取它们。
这样做有两个次要长处:
- 它能够取得不蕴含在训练集中但对类别具备强烈辨别力的 shapelet。
- 不须要在整个数据集上运行算法,这能够显着缩小训练工夫
然而这种办法也有一些应用可微分最小化函数和抉择的分类器引起的毛病。
要想代替欧几里德间隔,咱们必须依赖可微分函数,这样能够通过梯度降落或反向流传算法来学习 shapelet。最常见的依赖于 LogSumExp 函数,该函数通过取其参数的指数之和的对数来平滑地迫近最大值。因为 LogSumExp 函数不是严格凸函数,因而优化算法可能无奈正确收敛,这意味着它可能导致蹩脚的部分最小值。
并且因为优化过程自身是算法的次要组成部分,所以还须要增加多个超参数进行调优。
然而该办法在实践中十分有用,能够对数据产生一些新的见解。
基于核的办法
基于 shapelet 的算法的一个轻微变动是基于核的算法。学习和应用随机卷积核(最常见的计算机视觉算法),它从给定的 TS 中提取特色。
随机卷积核变换 (ROCKET) 算法是专门为此目标而设计的。。它应用了大量的内核,这些内核在长度、权重、偏置、收缩和填充方面都不同,并且是从固定的散布中随机创立的。
在抉择内核后,还须要一个可能抉择最相干的特色来区分类的分类器。原始论文中应用岭回归(线性回归的 L2 正则化变体)来执行预测。应用它有两个益处,首先是它的计算效率,即便对于多类分类问题也是如此,其次是应用穿插验证微调惟一的正则化超参数的十分的简略。
应用基于核的算法或 ROCKET 算法的外围劣势之一是应用它们的计算成本相当低。
基于特色的办法
基于特色的办法个别能够涵盖大多数算法,这些算法对给定的工夫序列应用某种特征提取,而后由分类算法执行预测。
对于特色,从简略的统计特色到更简单的基于傅里叶的特色。在 hctsa(https://github.com/benfulcher…)中能够找到大量这样的个性,然而尝试和比拟每个个性可能是一项无奈实现的工作,特地是对于较大的数据集。所以提出了典型工夫序列特色 (catch22) 算法被提出了。
catch22 算法
该办法旨在推断一个小的 TS 特色集,不仅须要弱小的分类性能,而且还能够进一步最小化冗余。catch22 从 hctsa 库中总共抉择了 22 个个性(该库提供了 4000 多个个性)。
该办法的开发人员通过在 93 个不同的数据集上训练不同的模型来取得 22 个特色,并评估其上体现最好的 TS 特色,失去了一个依然放弃杰出性能的小子集。其上的分类器能够自由选择,这使得它成为另一个超参数来进行调优。
Matrix Profile Classifier
另一种基于特色的办法是 Matrix Profile (MP) 分类器,它是一种基于 MP 的可解释 TS 分类器,能够在放弃基准性能的同时提供可解释的后果。
设计人员从基于 shapelet 的分类器中提取了名为 Matrix Profile 模型的。该模型表示 TS 的子序列与其最近街坊之间的所有间隔。这样,MP 就可能无效地提取 TS 的特色,例如 motif 和 discord,motif 是 TS 的彼此十分类似的子序列,而 discords 形容彼此不同的序列。
作为实践上的分类模型,任何模型都能够应用。这种办法的开发者抉择了决策树分类器。
除了这两种提到的办法之外,sktime 还提供了一些更基于特色的 TS 分类器。
模型集成
模型集成自身不是一种独立的算法,而是一种组合各种 TS 分类器以创立更好组合预测的技术。模型集成通过组合多个独自的模型来缩小方差,相似于应用大量决策树的随机森林。并且应用各种类型的不同学习算法会导致更宽泛和更多样化的学习特色集,这反过来会取得更好的类别辨别力。
最受欢迎的模型集成是 Hierarchical Vote Collective of Transformation-based Ensembles (HIVE-COTE)。它存在许多不同品种的类似版本,但它们的共同点是通过对每个分类器应用加权平均值来组合不同分类器的信息,即预测。
Sktime 应用两种不同的 HIVE-COTE 算法,其中第一种联合了每个预计器的概率,其中包含一个 shapelet 变换分类器 (STC)、一个 TS 森林、一个 RISE 和一个 cBOSS。第二个由 STC、Diverse Canonical Interval Forest Classifier(DrCIF,TS 森林的变体)、Arsenal(ROCKET 模型的汇合)和 TDE(BOSS 算法的变体)的组合定义。
最终的预测是由 CAWPE 算法取得的,该算法为每个分类器调配权重,这些权重是通过在训练数据集上找到的分类器的绝对预计品质取得的。
下图是用于可视化 HIVE-COTE 算法工作构造的罕用图示:
基于深度学习的办法
对于基于深度学习的算法,能够本人写一篇很长的文章来解释无关每种架构的所有细节。然而本文只提供一些罕用的 TS 分类基准模型和技术。
尽管基于深度学习的算法在计算机视觉和 NLP 等畛域十分风行并失去宽泛钻研,但它们在 TS 分类畛域却并不常见。Fawaz 等人。在他们对于 TS 分类的深度学习的论文中对以后现有办法的详尽钻研:总结钻研了具备六种架构的 60 多个神经网络 (NN) 模型:
- Multi-Layer Perceptron
- Fully Convolutional NN (CNN)
- Echo-State Networks (based on Recurrent NNs)
- Encoder
- Multi-Scale Deep CNN
- Time CNN
上述大多数模型最后是为不同的用例开发的。所以须要依据不同的用例进行测试。
在 2020 年还公布了 InceptionTime 网络。InceptionTime 是五个深度学习模型进行的集成,其中每个模型都是由 Szegedy 等人首先提出的 InceptionTime 创立的。这些初始模块同时将多个不同长度的过滤器利用于 TS,同时从 TS 的较短和较长子序列中提取相干特色和信息。下图显示了 InceptionTime 模块。
它由多个以前馈形式重叠的初始模块组成,并与残差连贯。最初是全局均匀池化和全连贯神经网络生成预测后果。
下图显示了单个初始模块的工作状况。
总结
本文总结的大量的算法、模型和技术列表不仅能帮忙了解工夫序列分类办法的广大畛域,心愿对你有所帮忙
援用
[1] Johann Faouzi. Time Series Classification: A review of Algorithms and Implementations. Ketan Kotecha . Machine Learning (Emerging Trends and Applications), Proud Pen, In press, 978–1–8381524- 1–3. ffhal-03558165
[2] Fawaz, Hassan Ismail, et al.“Deep learning for time series classification: a review”
[3] Dinger, Timothy R., et al.“What is time series classification?”
[4] Edin, Frederik, Time series classification — an overview
[5] Anion, Alexandra, A brief introduction to time series classification algorithms
https://avoid.overfit.cn/post/3183d68076724a3db2654ecd22bd20c4
作者:Jan Marcel Kezmann