Monthly Archives: September 2019

时间序列

深度学习在时间序列分类中的应用

Leave a comment

本篇博客将会分享几篇文章，其内容主要集中在深度学习算法在时间序列分类中的应用。

无论是图像分类，文本分类，还是推荐系统的物品分类，都是机器学习中的常见问题和应用场景。同样的，时间序列的分类问题也是研究时间序列领域的重要问题之一。近期，神经网络算法被用于物体识别，人脸识别，语音分类等方向中，于是有学者用深度学习来做时间序列的分类。

假设

X=\{x_{1},\cdots,x_{n}\}

是一个长度为 n 的时间序列，高维时间序列

X = \{X^{1},\cdots,X^{M}\}

则是由 M 个不同的单维时间序列而组成的，对于每一个 1\leq i\leq M 而言，时间序列 X^{i} 的长度都是 n. 而时间序列的分类数据通常来说都是这种格式：数据集

D=\{(X_{1},Y_{1}),(X_{2},Y_{2}),\cdots,(X_{N},Y_{N})\}

表示时间序列与之相应的标签，而 Y_{i} 是 one hot 编码，长度为 K（表示有 K 个类别）。

整体来看，时间序列分类的深度学习方案大体是这个样子的：输入的是时间序列，通过某个神经网络算法进行端到端的训练，最后输出相应的分类概率。

ReviewFigure1.png

而做时间序列分类的深度学习算法分成生成式（Generative）和判别式（Discriminative）两种方法。在生成式里面包括 Auto Encoder 和 Echo State Networks 等算法，在判别式里面，包括时间序列的特征工程和各种有监督算法，还有端到端的深度学习方法。在端到端的深度学习方法里面，包括前馈神经网络，卷积神经网络，或者其余混合模型等常见算法。

ReviewFigure5.png

深度学习算法在时间序列分类中的应用：Baseline

这一部分将会介绍用神经网络算法来做时间序列分类的 Baseline，其中包括三种算法，分别是多层感知机（MLP），FCN（Fully Convolutional Network）和 ResNet。其论文的全名是《Time Series Classification from Scratch with Deep Neural Networks: A Strong Baseline》。这篇论文中使用的神经网络框架如下图所示：

DNN_Baseline_结构1.png

多层感知机（MLP）模型使用了全连接层，每个隐藏层大约 500 个神经元，然后使用 ReLU 作为激活函数，同时使用 Dropout 来防止过拟合，最后一层是 Softmax 层。MLP 中一个基础的块包括：

\tilde{x} = f_{dropout, p}(x),

y = W\cdot \tilde{x} + b,

h = ReLU(y).

除了前馈神经网络之外，全卷积网络（FCN）同样可以作为时间序列的特征提取工具，一个卷积块包括：

y = W \otimes x + b,

s = BN(y),

h = ReLU(s),

在这里，\otimes 指的是卷积算子，BN 指的是 Batch Normalization，ReLU 则是激活函数。

Residual Network 是在 FCN 的基础上进行的改造。令 Block_{k} 来表示第 k 个卷积块，而 Residual 块就定义为：

h_{1} = Block_{k_{1}}(x),

h_{2} = Block_{k_{2}}(h_{1}),

h_{3} = Block_{k_{3}}(h_{2}),

y=h_{3} + x,

\hat{h}=ReLU(y).

其中，k_{1} = 64, k_{2} = 128, k_{3} = 128。

ReviewFigure6_ResNet.png

评价指标

Mean Per Class Error (in Multi-class Classification only) is the average of the errors of each class in your multi-class data set. This metric speaks toward misclassification of the data across the classes. The lower this metric, the better.

模型的评价指标使用的是 Mean Per-Class Error，指的是在多分类场景下，每一类（Class）错误率的平均值。换句话说，一个数据集 D=\{d_{k}\}_{1\leq k\leq K} 是由 K 个类的元素构成的，每个类的标签是 C=\{c_{k}\}_{1\leq k\leq K}，通过模型其实可以计算出模型对每一个类的错误率 e_{k}，那么模型的 MPCE 就是：MPCE= \sum_{1\leq k\leq K} e_{k}/K.

其实验结论是：

DNN_Baseline_实验数据1.png

MSCNN

MSCNN 的全称是 Multi-Scale Convolutional Neural Networks，相应的论文是《Multi-Scale Convolutional Neural Networks for Time Series Classification》。

在时间序列的分类算法里面，通常来说，可以分成以下几种：

  1. 基于距离的方法（distance-based methods）：kNN，SVM（相似核），DTW；
  2. 基于特征的方法（feature-based methods）：SVM，逻辑回归等；
  3. 基于神经网络的方法（neural network-based methods）：CNN 等；

正如前文所提到的，一条时间序列通常可以写作 T=\{t_{1},\cdots,t_{n}\}，其中 t_{i} 表示在时间戳 i 下的取值，并且时间序列 T 的长度是 n。在时间序列分类的场景下，每一条时间序列对应着唯一的一个标签（label），也就是说 D=\{(T_{i},y_{i})\}_{i=1}^{N}。其中 D 集合里面包含 N 条时间序列，每条时间序列 T_{i} 对应着一个标签 y_{i}。y_{i} 表示分类值集合 \mathcal{C} = \{1,\cdots,C\} 中的元素，C\in \mathbb{Z}^{+}。

MSCNN 的整体结构：

在 Multi-Scale Convolutional Neural Network（MSCNN）中，包括几个串行的阶段，

  1. 变换阶段（Transformation Stage）：包括恒等变换，下采样，谱变换等变换方式，每一种方式都是一个分支，并且也是卷积神经网络的输入；
  2. 局部卷积（Local Convolution Stage）：使用卷积层来对不同的输入提取特征，不同的输入分支之间是相互独立的，输出的时候都会经过一个最大值池化（max pooling）的过程；
  3. 整体卷积（Full Convolution Stage）：把上一步提取到的特征进行拼接（concatenate），然后使用全连接层并且加上一个 softmax 层来做多分类。

如下图所示，MSCNN 是一个端到端的训练网络结构，所有参数都是通过后向传播算法得到的。

MSCNN结构1.png

首先来看神经网络的第一步，变换阶段（Transformation Stage），也就是神经网络的多尺度的输入。在不同的尺度下，神经网络能够提炼到不同类型的特征。长期的特征（long-term features）反映了时间序列的整体趋势，短期的特征（short-term features）反映了时间序列的局部的微妙变化。要想判断时间序列的形状，不仅要参考整体的特征，也要参考局部的特征，这两者对于判断时间序列的形状都具有一定的辅助作用。

在 Transformation Stage，identity map 指的是恒等变换，也就是说时间序列是原封不动的作为神经网络的输入数据。对于 Smoothing Transformation，指的就是对时间序列进行必要的平滑操作，将新的时间序列作为神经网络的输入数据。在这种情况下，我们可以对时间序列 T=\{t_{1},\cdots,t_{n}\} 进行移动平滑，i.e.

T^{\ell}=(x_{i}+x_{i+1}+\cdots+x_{i+\ell-1})/\ell, 0\leq i\leq n-\ell+1,

其中的 \ell\in \mathbb{Z}^{+} 表示窗口长度。对于不同的窗口长度 \ell，我们可以的到不同的时间序列平滑序列，但是它们的长度都是一样的，都是原始的时间序列长度 n。

而下采样（down sampling）指的则是对时间序列的间隔进行抽样操作。假设时间序列 T=\{t_{1},\cdots,t_{n}\}，下采样的比例是 k，也就是说我们每隔 k 个点保留时间序列的取值，i.e.

T^{k} = \{t_{1+k\cdot i}\}, 0\leq i \leq [(n-1)/k].

用这种方法，我们可以对 k=1,2,3,\cdots 来进行下采样的时间序列提取。在进行了恒等变换，平滑变换，下采样之后，时间序列就可以变成多种形式，作为神经网络的输入。

其次，在神经网络部分，本文使用了一维（1-D）的卷积层和最大值池化的方法来提取特征，并且在局部卷积阶段之后把提炼到的抽象特征进行拼接（concatenate）。拼接完了之后，持续使用卷积层和池化层进行特征的提取，然后使用全连接层（fully connected layers）和 softmax 层来进行时间序列类别的预测。

数据增强

在深度学习里面，由于是端到端的训练网络，因此是需要相对多的样本数据的，于是有的时候需要进行数据增强（data augmentation）。也就是在现有的基础上获得更多的训练数据。对于时间序列 T=\{t_{1},\cdots,t_{n}\}，可以定义一个子序列：

S_{i:j} = \{t_{i}, t_{i+1},\cdots,t_{j}\}, 1\leq i,\leq j\leq n，

对于正整数 s\in \mathbb{Z}^{+}，可以生成 n-s+1 个子序列如下所示：

Slicing(T,s) = \{S_{1:s},S_{2:s+1},\cdots,S_{n-s+1:n}\},

这些子序列的标签与原始的时间序列 T 是一样的。

本文用到的数据集情况如下表所示：

MSCNN数据集1.png

实验数据如下图所示：

MSCNN实验1MSCNN数据集2

结论

本文使用了 MCNN 来对变换之后的时间序列进行特征提取，并且进行了端到端的模型训练。并且也讨论了卷积神经网络使用在 shapelet learning 上的一些逻辑和方法，然后解释了 MSCNN 在时间序列分类上能够有不错表现的原因。但是所有的 TSC 数据集都不算特别大，对端到端的训练模式有一定的限制。

GASF 和 GADF 方法

这篇文章《Imaging Time Series to Improve Classification and Imputation》介绍了如何把时间序列转换成图像，包括 GASF 方法和 GADF 方法。

假设时间序列是 X = \{x_{1},\cdots, x_{n}\}，长度是 n，我们可以使用归一化方法把时间序列压缩到 [0,1] 或者 [-1,1]：

\tilde{x}_{0}^{i} = (x_{i} - \min(X))/(\max(X) -\min(X)),

\tilde{x}_{-1}^{i} = ((x_{i} - \max(X)) + (x_{i}-\min(X)))/(\max(X) - \min(X)),

此时的 \tilde{x}_{0}^{i}\in[0,1], \forall 1\leq i\leq n，\tilde{x}_{-1}^{i} \in [-1,1],\forall 1\leq i\leq n。于是可以使用三角函数来代替归一化之后的值。下面通用 \tilde{x}_{i} 来表示归一化之后的时间序列，令 \phi_{i} = \arccos(\tilde{x}_{i})，\tilde{x}_{i} \in [-1,1]，1\leq i\leq n。因此，\phi_{i}\in[0,\pi]，于是，\sin(\phi_{i}) \geq 0。

定义矩阵 GASF（Gramian Angular Summation Field） 为

GASF = [\cos(\phi_{i}+\phi_{j})]_{1\leq i,j\leq n}

于是，

GASF = [\cos(\phi_{i})\cdot \cos(\phi_{j}) - \sin(\phi_{i})\cdot \sin(\phi_{j})]_{n\times n}

令 \tilde{X}=(\cos(\phi_{1}),\cdots,\cos(\phi_{n}))^{T}，可以得到

GASF = \tilde{X} \cdot \tilde{X}^{T} - \sqrt{I - \tilde{X}^{2}} \cdot \sqrt{I - \tilde{X^{T}}^{2}}

以上的都是 element 乘法和加法，I 表示单位矩阵。它的对角矩阵是

diag(GASF) = \{\cos(2\phi_{1}),\cdots, \cos(2\phi_{n})\}

= \{2\cos^{2}(\phi_{1})-1,\cdots,2\cos^{2}(\phi_{n})-1)\} = \{GASF_{ii}\}_{1\leq i\leq n}.

如果是使用 min-max normalization 的话，是可以从 diag(GASF) 反推出 \tilde{x}_{i} 的。因为，2 \tilde{x}_{i}^{2} - 1 = 2\cos^{2}(\phi_{i}) - 1 = GASF_{ii}，可以得到 y_{i} = \sqrt{(GASF_{ii}+1)/2}。

定义 GADF（Gramian Angular Difference Field）如下：

GADF = [\sin(\phi_{i}-\phi_{j})]_{1\leq i,j\leq n}

= [\sin(\phi_{i})\cdot cos(\phi_{j}) - \cos(\phi_{i})\cdot\sin(\phi_{j})]_{1\leq i,j\leq n}

= \sqrt{1-X^{2}}\cdot X^{T} - X \cdot \sqrt{1-(X^{T})^{2}}.

GASFGADF1.png

Markov Transition Field（MTF）

除了 GSAF 和 GSDF 之外，《Imaging Time Series to Improve Classification and Imputation》，《Encoding Time Series as Images for Visual Inspection and Classification Using Tiled Convolutional Neural Networks》，《Encoding Temporal Markov Dynamics in Graph for Time Series Visualization》也提到了把时间序列转换成矩阵 Image 的算法 MTF。在 pyts 开源工具库里面，也提到了 MTF 算法的源码。

假设时间序列是 X = \{x_{1},\cdots,x_{n}\}，我们把它们的值域分成 Q 个桶，那么每一个 x_{i} 都可以被映射到一个相应的 q_{j} 上。于是我们可以建立一个 Q\times Q 的矩阵 W，w_{ij} 表示在桶 j 中的元素被在桶 i 中的元素跟随的概率，也就是说 w_{ij} = P(x_{t}\in q_{i}|x_{t-1}\in q_{j})，同时，它也满足 \sum_{j=1}^{Q}w_{ij} =1。于是，得到矩阵 W = (w_{ij})_{1\leq i,j\leq Q}。

MTF1.png

除此之外，我们也能够计算一个迁移概率矩阵 M。其中 $m_{ij}$ 表示桶 i 中的元素迁移至桶 j 中的概率 P(q_{i}\rightarrow q_{j})，同样有 \sum_{1\leq j\leq Q} m_{ij} =1。因此，我们同样可以构造出一个 Q\times Q 的矩阵将时间序列可视化。

时间序列的降维方法有两种：

  1. 分段聚合（PAA）：使用局部平均等方法，把时间序列进行降维；
  2. 核变换（Kernel）：使用 Bivariate Gaussian 核或者均值核来把时间序列进行降维。

在把时间序列进行可视化之后，对于时间序列分类的场景，就可以使用 CNN 的技术方案来做了。如下图所示：

tildeCNN.png

其实验数据效果如下：

tildeCNN实验数据1.png

Time Le-Net

在本篇文章《Data Augmentation for Time Series Classification using Convolutional Neural Networks》中，主要用到了卷积神经网络来做时间序列的分类。

time_lenet_1.png

除此之外，也使用了不少数据增强（Data Augmentation）的技术。包括前面提到的 Window Slicing（WS）方法。也考虑了 Warping 的变换技巧，例如 Warping Ratio = 1/2 或者 2。这种时间扭曲指标比率可以通过交叉验证来选择。该方法叫做 Window Warping（WW）技术。

另外也有其余论文使用卷积神经网络做时间序列分类，例如《Convolutional neural networks for time series classification》，如下图所示：

CNN_figure1.png

Multi-Channels Deep Convolutional Neural Networks

在高维时间序列的分类中，有人提出用多通道的卷积神经网络来进行建模。

multichannelcnn_figure3.png

整体来看，分成四个部分。前三个部分作为特征提取工具，最后一层作为分类工具。

  1. Filter Layer：
  2. Activation Layer：
  3. Pooling Layer：
  4. Fully-Connected Layer：

实验对比数据如下：

multichannelcnn_table1.png

结论：

在本篇博客中，列举了一些深度学习算法在时间序列分类中的应用，也介绍了部分数据增强的方法和时间序列数据变换的方法。从以上各篇文章的介绍来看，深度学习在时间序列分类领域上应该是大有可为的。

参考资料：

  1. Wang Z, Yan W, Oates T. Time series classification from scratch with deep neural networks: A strong baseline[C]//2017 international joint conference on neural networks (IJCNN). IEEE, 2017: 1578-1585.
  2. Cui Z, Chen W, Chen Y. Multi-scale convolutional neural networks for time series classification[J]. arXiv preprint arXiv:1603.06995, 2016.
  3. Wang Z, Oates T. Imaging time-series to improve classification and imputation[C]//Twenty-Fourth International Joint Conference on Artificial Intelligence. 2015.
  4. Wang Z, Oates T. Encoding time series as images for visual inspection and classification using tiled convolutional neural networks[C]//Workshops at the Twenty-Ninth AAAI Conference on Artificial Intelligence. 2015.
  5. Liu L. Encoding Temporal Markov Dynamics in Graph for Time Series Visualization, Arxiv, 2016.
  6. Fawaz H I, Forestier G, Weber J, et al. Deep learning for time series classification: a review[J]. Data Mining and Knowledge Discovery, 2019, 33(4): 917-963.
  7. Zhao B, Lu H, Chen S, et al. Convolutional neural networks for time series classification[J]. Journal of Systems Engineering and Electronics, 2017, 28(1): 162-169.
  8. Le Guennec A, Malinowski S, Tavenard R. Data augmentation for time series classification using convolutional neural networks[C]. 2016.