Category Archives: 时间序列

时间序列异常检测—节假日效应的应对之道

在时间序列异常检测中,通常有一个较为常见的场景就是“节假日效应”。所谓节假日效应,指的就是在节假日的时候,其时间序列的走势跟日常有着明显的差异性,但是又属于正常的情况。从国内 2020 年的节假日安排可以看出,一年中有好几个关键的假日:

  1. 元旦:1 天;
  2. 春节:7 天;
  3. 清明节:3 天;
  4. 五一劳动节:5 天;
  5. 端午节:3 天;
  6. 国庆节:8 天。

在这些节假日的时候,为了调休,自然也会带来工作日上的调整。例如:在 2020 年 1 月 19 日,2020 年 2 月 1 日是需要上班的(虽然今年受疫情影响最终也没上班)。因此,在这些节假日进行调整和变化的时候,各种各样的业务指标(时间序列)通常也会发生变化,变得跟以往的走势不太一致。因此,如何解决节假日效应的时间序列异常检测就是业务上所面临的问题之一。

£¨Í¼±í£©[Éç»á]2020Äê½Ú¼ÙÈշżٰ²ÅŹ«²¼
2020 年的放假安排
清华大学的 Netman 实验室在 2019 年发表了一篇论文,专门用于解决时间序列异常检测中的节假日效应问题,论文的标题是《Automatic and Generic Periodic Adaptation for KPI Anomaly Detection》。在本文中,所用的时间序列是关于各种各样的业务指标的,包括搜索引擎,网上的应用商店,社交网络数据等等。作者们针对 KPI(Key Performance Indicator)做了时间序列异常检测,并且发明了一种方法来避免节假日效应的问题。论文针对时间序列的工作日(work days),休息日(off days),节假日(festival)做了必要的区分,然后将时间序列的不同时间段进行合理地拆分和组装,再进行时间序列异常检测,从而在一定的程度上解决节假日效应问题。

节假日效应_Fig1
实际案例(1)

在实际的案例中,我们可以看到,同一条时间序列的走势在工作日(work day),休息日(off day),春节(Spring Festival)明显是不一样的。因此,根据工作日的时间序列走势来预测春节的走势明显是不太合理的;同理,根据春节的走势来预测休息日的走势也会带来一定的偏差的。那么如何解决节假日效应的问题就成为了本篇论文的关键之一。

节假日效应_Fig3
实际案例(2)

在上图中,我们可以看到论文中使用的数据都具有某种周期性(Periodicity)。KPI A,B,C 都是具有明显具有工作日和周末特点的,在工作日和周末分别有着不同的形状;KPI D 则是关于网上应用商店周五促销的,因此在周五周六的时候,其实时间序列会出现一个尖峰(peak);KPI E 的话则是每隔 7 天,会有两个尖刺,然后并且迅速恢复;KPI F 的话则是可以看出时间序列在十一的走势跟其余的时间点明显有区别。除此之外,对于一些做旅游,电商等行业的公司,其节假日效应会更加突出一点,而且不同的业务在节假日的表现其实也是不一样的。有的时间序列在节假日当天可能会上涨(电商销售额),有的时间序列在节假日当天反而会下降(订车票,飞机票的订单量)。因此,在对这些时间序列做异常检测的同时,如何避免其节假日效应就是一个关键的问题了。

而在实际处理的时候,通常也会遇到几个常见的问题;

  1. 周期性的多样性:通过实际案例可以看出,对于不同的时间序列,其周期是完全不一样的,而且在不同的周期上也有着完全不同的表现;
  2. KPI 数量巨大:这个通常来说都是智能运维领域中的常见问题;
  3. 周期的漂移:一般来说,通过时间序列的走势我们只能够看出一个大致的变化,但是具体到细节的话,周期是存在一定的波动的。例如不一定恰好是 7 天,有可能是 7 天加减 5 分钟之类的周期。这个跟业务的具体场景有关系,也跟当时的实际情况有关。

于是,基于这些挑战,作者们希望提出一个健壮的机器学习算法来解决这个问题,本文的系统被作者们称之为 Period,正好也象征着解决节假日效应这个寓意。

Period_Fig7
Period 的整体架构

从论文中可以看出 Period 的整体架构如上图所示,包括两个部分:

  1. 离线周期性检测(offline periodicity detection);
  2. 在线适应性异常检测(online anomaly detection adaptation)。

在第一部分,每一条时间序列都会被按天切分成很多子序列(subsequence),然后将其聚集起来,把相似的时间序列放在一类,不相似的放在另外一类;在第二部分,新来的时间序列会根据其具体的日期,分入相应的聚类,然后用该类的时间序列异常检测方法来进行异常检测。

Period_Fig6
Period 的核心思路

从上图可以看到 Period 的核心思路(core idea)。在本文使用的数据中,时间序列的长度较长,一般来说都是好几个月到半年不等,甚至更长的时间。对于一条时间序列(a given KPI),可以将它的历史数据(historical data)进行按天切分,获得多个子序列(sub KPIs)。对于这多个子序列,需要进行聚类以得到不同类别。或者按照日历直接把时间序列的工作日(work day),休息日(off day),春节(spring festival)序列进行切分,将工作日放在一起,休息日放在一起,春节放在一起。把这些子序列进行拼接就可以得到三条时间序列数据,分别是原时间序列的工作日序列(work day subsequence),休息日序列(off day subsequence),春节序列(spring festival subsequence)。然后分别对着三条时间序列训练一个异常检测的模型(例如 Holt-Winters 算法,简写为 HW)。对于新来的时间序列,可以根据当日具体的日期(工作日,休息日或者春节)放入相应的模型进行异常检测,从而进一步地得到最终的结果。

在离线周期性检测的技术方案里面,是需要对时间序列进行周期性检测(Periodicity Detection)。而周期性检测有多个方案可以选择。第一种就是周期图方法(Periodogram),另外一种就是自相关函数(Auto-correlation function)。但是在这个场景下,用这些方法就不太合适了。作者们提出了别的解决方案。

在本文中,作者们提出了一种 Shape-based distance(SBD)的方法,针对两条时间序列 X=(x_{1},x_{2},\cdots,x_{m})Y=(y_{1},y_{2},\cdots,y_{m}),提出了相似性的计算方法。

X_{(s)}=\begin{cases}(0,\cdots,0,x_{1},\cdots,x_{m-s}), &\text{ if } s\geq 0 \\ (x_{1-s},x_{1-s+1},\cdots,x_{m},0,\cdots,0), &\text{ else } s<0.\end{cases}

其中 0 的个数都是 |s|. 进一步可以定义,当 s\in[-w,w]\cap\mathbb{Z} 时,

CC_{s}(X,Y)=\begin{cases}\sum_{i=1}^{m-s}x_{i}\cdot y_{s+i}, &\text{ if } s\geq 0 \\ \sum_{i=1}^{m+s}x_{i-s}\cdot y_{i}, &\text{ else } s<0.\end{cases}

于是,选择令 CC_{s}(X,Y) 归一化之后的最大值作为 X,Y 的相似度,i.e.

NCC(X,Y)=\max_{s\in[-w,w]\cap\mathbb{Z}}\frac{CC_{s}(X,Y)}{\|x\|_{2}\cdot\|y\|}.

而基于 SBD 的距离公式则可以定义为:

SBD(X,Y) = 1-NCC(X,Y).

Period_Fig8
Periodicity Drift

那么为什么需要考虑一个漂移量 s 呢,因为在一些实际的情况下,时间序列是会存在漂移的,例如上图所示。该时间序列在 10 月 30 日,31 日,11 月 1 日 都出现了一个凸起,但是如果考虑它的同比图,其实是可以清楚地看出该时间序列就存在了漂移,也就是说并不是在一个固定的时间戳就会出现同样的凸起,而是间隔了一段时间。这就是为什么需要考虑 s 的由来。

Period_Alg1
聚类的命名算法

通过相似性和距离的衡量工具,我们可以将时间序列进行聚类,然后通过上述算法也可以对每一个聚类的结果进行命名。

Period_Table1
实验数据
Period_Table2
实验数据的聚类结果

在本文中,针对以上六条时间序列,作者们做了详细的分析,也对其余的 50 条时间序列进行了实验。其使用的方法包括 HW,TSD,Diff,MA,EWMA,Donut。在 HW 中,针对不同的日期使用了不同的方法,例如 HW-day,HW-week,HW-period;其余的方法也是针对不同的日期来做的。

Period_Table3
实验方法
Period_Table12
实验效果

从实验效果来看,Period 方法的话相对于其他方法有一定的优势。

结论:Period 方法包括两个部分,第一部分是离线周期性检测,第二部分是在线适应性异常检测。通过这样的方法,可以有效地减缓时间序列异常检测受节假日效应的影响。除此之外,想必未来也会有其余学者提出相应的问题和解决方案,敬请期待。

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

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

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

假设

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 的矩阵 Ww_{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.

时间序列的标签

本篇文章是为了介绍一种基于少量样本标记而获得更多样本的方法,论文的原文是《Label-Less: A Semi-Automatic Labeling Tool for KPI Anomalies》,是清华大学与多家公司(必示科技,中国建设银行等)的合作论文。

在时间序列异常检测中,因为标注的成本比较大,于是需要寻找一种较少而高效地标注时间序列异常点的方法。在该论文中,Alibaba,Tencent,Baidu,eBay,Sogou提供了上千条时间序列(每条时间序列大约是2-6个月的时间跨度),作者们进行了 30 条 KPIs 的标注工作。但是其标注成本依旧是很大的,于是作者们想到了一种异常相似搜索(anomaly similarity search)的算法,目标是对已经标注好的时间序列异常模式进行模版搜索。目的就是达到 label-less,也就是较少的标注而获得更多的标注数据。

在本篇论文中,在异常检测的过程中,作者们使用了时间序列的预测模型(time series prediction models)来获得时间序列的特征,使用了孤立森林(Isolation Forest) 来对时间序列的特征来做无监督的异常检测。并且其效果由于 one class svm 算法和 local outlier factor 算法。在搜索的部分,作者使用了加速版的 DTW 算法(accelerated dynamic time warping approach)来做相似度的搜索和模式的匹配。其中也尝试了各种技巧和方法,包括 constrained DTW,LB Keogh 方法,early stopping 算法等工具。

整个 Label-Less 的架构图如下表示:

Fig2.png

其中的 Operators 指的是业务运维人员,面对着无标记的多条时间序列曲线。系统首先会进行无监督的异常检测算法啊,包括时间序列的预处理(归一化等)操作,然后使用差分(Difference),移动平均算法(moving average),带权重的移动平均算法(weighted moving average),指数移动平均(ewma),holt winters,ARIMA 等算法来做特征的提取。此时,对于不同的时间序列预测工具,我们可以得到不同的预测值,然后把预测值减去实际值并且取绝对值,就得到时间序列的误差序列。i.e. |p_{i} - x_{i}| 就作为数据点 x_{i} 的特征。

在这种情况下,由于用了六个时间序列预测算法,因此原始的时间序列 X (n\times 1) 就可以变成特征矩阵 X' (n\times 1)。对于特征矩阵 X' 可以使用 isolation forest 来做无监督的异常检测并且做阈值的设定;如下图所示:

Fig3.png

而另外的一部分的异常相似搜索(anomaly similarity search)是在第一部分的基础上在做的,Unsupervised Anomaly Detection 会输出疑似异常或者候选异常,并且基于已知的异常模板(Anomaly Template)进行相似度的匹配,此时可以使用 accelerated DTW 算法,选择出最相似的 Top-K 异常,然后运维人员进行标注,得到更多的样本。

由于,对于两条长度分别是 mn 的时间序列,DTW 相似度算法的时间复杂度是 O(mn),因此在搜索的时候需要必要的加速工作。在这种地方,作者们使用了 LB-Kim,LB-Keogh,LB-Keogh-Reverse 算法来做搜索的加速工作。而这些的时间复杂度是 O(m+n)。整体的思路是,如果两条时间序列 qc 的 LB-Kim,LB-Keogh,LB-Keogh-Reverse 的下界大于某个阈值,则不计算它们之间的 DTW 距离。否则就开始计算 DTW。并且在计算 DTW 的时候,如果大于下界,则会提前终止(early stopping),不会继续计算下去。如果都没有大于阈值,则把这个候选曲线和 dist 距离放入列表,最后根据列表中的 dist 来做距离的逆序排列。

整体流程如下:

AnomalySimilaritySearch

其运行速度也比直接使用 DTW 快不少:

Table3.png

Label-Less 的交互页面如下所示:

图(a)表示使用无监督算法获得的疑似异常;

图(b)表示使用异常搜索算法获得的异常结果。

Fig10.png

下图则表示模板,m 表示模板的长度,c 表示相似的异常候选集个数;

Fig11

总结:

整体来看,本文提供了一种通过少量人工标注无监督算法相似度算法来获得更多样本的方法。在候选的时间序列条数足够多的时候,是可以进行时间序列的相似度匹配的。这给未来在运维领域提供海量的时间序列标注数据给予了一定的技术支持。

 

时间序列的联动分析

背景介绍

在互联网公司里面,通常都会监控成千上万的时间序列,用于保障整个系统或者平台的稳定性。在这种情况下,如果能够对多条时间序列之间判断其是否相关,则对于监控而言是非常有效的。基于以上的实际情况,清华大学与 Alibaba 集团在2019年一起合作了论文《CoFlux: Robustly Correlating KPIs by Fluctuations for Service Troubleshooting》,并且发表在 IWQos 2019 上。CoFlux 这个方法可以对多条时间序列来做分析,并且主要用途包括以下几点:

  1. 告警压缩和收敛;
  2. 推荐与已知告警相关的 Top N 的告警;
  3. 在已有的业务范围内(例如数据库的实例)构建异常波动传播链;

kpis.png

CoFlux 的整体介绍

从论文的介绍中来看,CoFlux 的输入和输出分别是:

输入:两条时间序列

输出:这两条时间序列的以下信息

  1. 波动相关性:两条时间序列是否存在波动相关性?
  2. 前后顺序:如果两条时间序列相关,那么它们的前后波动顺序是什么?是同时发生异常还是存在固定的前后顺序?
  3. 方向性:如果两条时间序列是波动相关的,那么它们的波动方向是什么?是一致还是相反?

Remark. CoFlux 的关键点就是并没有对时间序列做异常检测算法,而是直接从时间序列的历史数据(历史半个月或者一个月)出发,判断两条时间序列之间的波动相关性,并且进一步的分析先后顺序与波动方向。

从论文的介绍中来看,CoFlux 的流程图如下图所示:

coflux流程图1

如果两条时间序列 XY 存在波动相关性,则需要输出这两条时间序列的波动先后顺序和是否同向波动。如果两条时间序列 XY 并不存在波动相关性的话,则不需要判断波动先后顺序和是否同向波动。

coflux流程图2

CoFlux 的细节阐述

已知一个长度是 n 的时间序列 S=\{s_{1},\cdots,s_{n}\},对于任意一个 detector,可以得到一条关于 S 的预测值曲线 P=\{p_{1},\cdots,p_{n}\}。于是针对某个 detector 可以得到一个波动特征序列 E=\{\epsilon_{1},\cdots,\epsilon_{n}\},其中 \epsilon_{i} = s_{i} - p_{i}1\leq i\leq n。因此,一个detector 可以对应一个波动序列特征,也是一个时间序列。因此,对于 m 个 detector,可以对应 m 条波动特征序列,并且它们的长度都是 n

在 CoFlux 算法的内部,根据不同的参数使用了总共 86 个 detector,大致列举如下:

  • Difference:根据昨天,七天前的数据来做差分;
  • Holt-Winters:\{\alpha,\beta,\gamma\} \in \{0.2,0.4,0.6,0.8\}
  • 历史上的均值 & 历史上的中位数:1,2,3,4 周;
  • TSD & TSD 中位数:1,2,3,4 周;
  • Wavelet:1,3,5,7 天;
  • 移动平均算法:MA,WMA,EWMA。PS:根据作者们的说法,在这里,MA等方法并不适用。

detectors

根据直觉来看,

  • 对于任何一条时间序列 kpi,总有一个 detector 可以相对准确地提炼到其波动特征;
  • 如果两条时间序列 XY 波动相关,那么 X 的一个波动特征序列与 Y 的一个波动特征序列应该也是相关的;

Remark. 两条时间序列的波动特征可以对齐同一个 detector,也可以不做对齐工作。如果是前者的话,时间复杂度低;后者的话,时间复杂度高。

下图是从时间序列中提取波动特征曲线的案例:

fluxfeatures.png

提炼时间序列的波动曲线特征只是第一步,后续 CoFlux 还有几个关键的步骤:

  • 特征工程的扩大(amplify): 对波动序列特征进行放大,让某些波动序列特征更加明显;
  • Correlation Measurement:用于解决时间序列存在时间前后的漂移,两条时间序列之间存在 lag 的情况,因此需要对其中一条时间序列做平移操作;
  • CoFlux 考虑了历史数据(历史半个月或者一个月)作为参考,并且一个范围内的 kpi 数量不超过 60 条;

下面来一一讲解这些技术方案,对于每一条波动特征曲线(Flux-Features),按照以下几个步骤来进行操作:

Step 1:对波动特征曲线 E=\{\epsilon_{1},\cdots,\epsilon_{n}\} 做 z-score 的归一化,i.e.

\mu = \frac{\sum_{i=1}^{n}\epsilon_{i}}{n},
\delta = \sqrt{\frac{\sum_{i=1}^{n}(\epsilon_{i}-\mu)^{2}}{n}}.

Step 2:对归一化之后的波动特征曲线做特征放大(feature amplification):定义函数 f_{\alpha,\beta}(x) 如下:

f_{\alpha,\beta}(x)= \begin{cases} e^{\alpha\min(x,\beta)} - 1, \text{ when } x\geq 0,\\ -e^{\alpha\min(|x|,\beta)} + 1, \text{ when } x< 0. \end{cases}

E=\{\epsilon_{1},\cdots,\epsilon_{n}\} 放大之后的波动特征曲线(amplified flux feature)就是:\hat{E}=\{f(\epsilon_{1}),\cdots,f(\epsilon_{n})\}.

Step 3:对于两条放大之后的波动特征曲线(amplified flux features)G=\{g_{1},\cdots,g_{\ell}\}H=\{h_{1},\cdots,h_{\ell}\},可以计算它们之间的相关性,先后顺序,是否同向。

G_{s}= \begin{cases} \{0,\cdots,0,g_{1},\cdots, g_{\ell-s}\}, \text{ when } s\geq 0, \\ \{g_{1-s},\cdots,g_{\ell},0,\cdots,0\}, \text{ when } s< 0. \end{cases}

这里的 0 的个数是 |s| 个。其中,-\ell<s<\ell。特别地,当 s=0 时,G_{0}=\{g_{1},\cdots,g_{s}\}=G,那么我们可以定义 G_{s}H 的内积是:R(G_{s},H) = G_{s}\cdot H,

这里的 \cdot 指的是向量之间的内积(inner product)。同时可以定义相关性(Cross Correlation)为:CC(G_{s},H) = \frac{R(G_{s},H)}{\sqrt{R(G_{s},G_{s})\cdot R(H,H)}}.

由于波动有可能是反向的,那么在这里我们不仅要考虑相关性是大于零的情况,也需要考虑小于零的情况。于是,

minCC = \min_{-\ell<s<\ell}CC(G_{s},H),
maxCC = \max_{-\ell<s<\ell}CC(G_{s},H).

则最小值或者最大值的指标分别是

s_{1}=argmin_{-\ell<s<\ell}CC(G_{s},H),
s_{2}=argmax_{-\ell<s<\ell}CC(G_{s},H).


FCC(G,H) = \begin{cases} (minCC, s_{1}), \text{ when } |maxCC|<|minCC|, \\ (maxCC, s_{2}), \text{ when } |maxCC|\geq|minCC|. \end{cases}

从定义中可以看出,FCC(G,H) 是一个元组,里面蕴含着三个信息,分别是相关性,波动方向,前后顺序。FCC(G,H) \in [-1,1],越接近 1 或者 -1 就表示放大之后的波动特征曲线 GH 越相关。正值的 FCC(G,H) 表示 GH 的波动方向相同,是正相关;负值的 FCC(G,H) 表示 GH 的波动方向想法,是负相关。通过对 s<0 或者 s\geq 0 的分析就可以判断先后顺序。因此,CoFlux 方法的是通过对 FCC(G,H) 的分析来得到最终结果的。

在最后的相关性分析里面,其实伪代码正如论文中所示。先考虑是否存在相关性,再考虑基于相关性下的先后顺序和波动方向。

correlationmeasurement

 

CoFlux 的实战效果

从论文中看,CoFlux 的数据集基本上是小于 60 条时间序列曲线。其中包括 CPU,错误率,错误数,内存使用率,成功率等不同的指标。

datasets

datasets2.png

从运行时间上来看,对于一周的时间序列集合(< 60条)而言,CoFlux 基本上能够在 30 分钟内计算完毕,得到最终的运算结果。

executiontime.png

其效果的评价指标基本上就是机器学习中的常见评价指标了,准确率,召回率之类的。

评价指标

从 F1-Score 的评价指标来看,CoFlux 的效果优于其他算法。

experiments.png

告警压缩

如果对时间序列之间进行告警压缩的话,其实可以大量减少运维人员的工作量。在 CoFlux 里面,时间序列曲线被分成了三类,也就是三个颜色最深的模块。因此 21 条时间序列的告警量在实际中有可能只有三条告警。

alarmclustering

告警关联

在实际运维场景中,除了对告警进行压缩之外,也需要对告警进行关联性的分析。例如一条告警发生了,运维人员都希望知道与它相关的其他告警是什么,这样可以方便运维人员定位问题。

alarmcorrelation

构建告警关系链

在一些相对封闭的场景下,例如 mysql 数据库,通过对它里面的时间序列进行分析。不仅可以得到告警之间是否存在相关性,还可以对先后顺序,波动顺序进行分析。

mysql

 

结论

时间序列之间的联动分析是在运维领域场景下的常见技术,不仅可以做告警的压缩,也能够做告警的关联,还能够构建告警的关系链。在未来的工作中,作者们提到将会用深度学习的方法来进行关联和告警的分析,从而进一步加深对时间序列的研究。

时间序列的聚类

在机器学习领域,聚类问题一直是一个非常常见的问题。无论是在传统的机器学习(Machine Learning)领域,还是自然语言处理(Natural Language Processing)领域,都可以用聚类算法做很多的事情。例如在数据分析领域,我们可以把某个物品用特征来描述出来,例如该房子的面积,价格,朝向等内容,然后使用聚类算法来把相似的房子聚集到一起;在自然语言处理领域,通常都会寻找一些相似的新闻或者把相似的文本信息聚集到一起,在这种情况下,可以用 Word2Vec 把自然语言处理成向量特征,然后使用 KMeans 等机器学习算法来作聚类。除此之外,另外一种做法是使用 Jaccard 相似度来计算两个文本内容之间的相似性,然后使用层次聚类(Hierarchical Clustering)的方法来作聚类。

word2vec1

本文将会从常见的聚类算法出发,然后介绍时间序列聚类的常见算法。

机器学习的聚类算法

KMeans — 基于距离的机器学习聚类算法

KMeans 算法的目的是把欧氏空间 \mathbb{R}^{m} 中的 n 个节点,基于它们之间的距离公式,把它们划分成 K 个类别,其中类别 K 的个数是需要在执行算法之前人为设定的。

kmeans1

从数学语言上来说,假设已知的欧式空间点集为 \{x_{1},\cdots,x_{n}\},事先设定的类别个数是 K,当然 K\leq n 是必须要满足的,因为类别的数目不能够多于点集的元素个数。算法的目标是寻找到合适的集合 \{S_{i}\}_{1\leq i\leq K} 使得 argmin_{S_{i}}\sum_{x\in S_{i}}||x-\mu_{i}||^{2} 达到最小,其中 \mu_{i} 表示集合 S_{i} 中的所有点的均值。

上面的 ||\cdot|| 表示欧式空间的欧几里得距离,在这种情况下,除了使用 L^{2} 范数之外,还可以使用 L^{1} 范数和其余的 L^{p},p\geq 1 范数。只要该范数满足距离的三个性质即可,也就是非负数,对称,三角不等式。

层次聚类 — 基于相似性的机器学习聚类算法

层次聚类通常来说有两种方法,一种是凝聚,另外一种是分裂。

hierarchicalclustering1

所谓凝聚,其大体思想就是在一开始的时候,把点集集合中的每个元素都当做一类,然后计算每两个类之前的相似度,也就是元素与元素之间的距离;然后计算集合与集合之前的距离,把相似的集合放在一起,不相似的集合就不需要合并;不停地重复以上操作,直到达到某个限制条件或者不能够继续合并集合为止。

所谓分裂,正好与聚合方法相反。其大体思想就是在刚开始的时候把所有元素都放在一类里面,然后计算两个元素之间的相似性,把不相似元素或者集合进行划分,直到达到某个限制条件或者不能够继续分裂集合为止。

在层次聚类里面,相似度的计算函数就是关键所在。在这种情况下,可以设置两个元素之间的距离公式,例如欧氏空间中两个点的欧式距离。在这种情况下,距离越小表示两者之间越相似,距离越大则表示两者之间越不相似。除此之外,还可以设置两个元素之间的相似度。例如两个集合中的公共元素的个数就可以作为这两个集合之间的相似性。在文本里面,通常可以计算句子和句子的相似度,简单来看就是计算两个句子之间的公共词语的个数。

时间序列的聚类算法

通过以上的描述,如果要做时间序列的聚类,通常来说也有多种方法来做,可以使用基于距离的聚类算法 KMeans,也可以使用基于相似度计算的层次聚类算法。

时间序列的特征提取

之前写过很多时间序列特征提取的方法,无论是常见的时间序列特征,例如最大值,最小值,均值,中位数,方差,值域等内容之外。还可以计算时间序列的熵以及分桶的情况,其分桶的熵指的是把时间序列的值域进行切分,就像 Lebesgue 积分一样,查看落入那些等分桶的时间序列的概率分布情况,就可以进行时间序列的分类。除了 Binned Entropy 之外,还有 Sample Entropy 等各种各样的特征。除了时域特征之外,也可以对时间序列的频域做特征,例如小波分析,傅里叶分析等等。因此,在这种情况下,其实只要做好了时间序列的特征,使用 KMeans 算法就可以得到时间序列的聚类效果,也就是把相似的曲线放在一起。参考文章:时间序列的表示与信息提取。

在提取时间序列的特征之前,通常可以对时间序列进行基线的提取,把时间序列分成基线和误差项。而基线提取的最简单方法就是进行移动平均算法的拟合过程,在这种情况下,可以把原始的时间序列 \{x_{1},\cdots,x_{n}\} 分成两个部分 \{baseline_{1},\cdots,baseline_{n}\}\{residual_{1},\cdots,residual_{n}\}。i.e. x_{i} = baseline_{i} + residual_{i}。有的时候,提取完时间序列的基线之后,其实对时间序列的基线做特征,有的时候分类效果会优于对原始的时间序列做特征。参考文章:两篇关于时间序列的论文。

时间序列的相似度计算

如果要计算时间序列的相似度,通常来说除了欧几里得距离等 L^{p} 距离之外,还可以使用 DTW 等方法。在这种情况下,DTW 是基于动态规划算法来做的,基本想法是根据动态规划原理,来进行时间序列的“扭曲”,从而把时间序列进行必要的错位,计算出最合适的距离。一个简单的例子就是把 y=\sin(x)y=\cos(x) 进行必要的横坐标平移,计算出两条时间序列的最合适距离。但是,从 DTW 的算法描述来看,它的算法复杂度是相对高的,是 O(n^{2}) 量级的,其中 n 表示时间序列的长度。参考文章:时间序列的搜索。

dtw1

如果不考虑时间序列的“扭曲”的话,也可以直接使用欧氏距离,无论是 L^{1}, L^{2} 还是 L^{p} 都有它的用武之地。除了距离公式之外,也可以考虑两条时间序列之间的 Pearson 系数,如果两条时间序列相似的话,那么它们之间的 Pearson 系数接近于 1;如果它们之间是负相关的,那么它们之间的 Pearson 系数接近于 -1;如果它们之间没有相关性,Pearson 系数接近于0。除了 Pearson 系数之外,也可以考虑它们之间的线性相关性,毕竟线性相关性与 Pearson 系数是等价的。参考文章:时间序列的相似性。

除此之外,我们也可以用 Auto Encoder 等自编码器技术对时间序列进行特征的编码,也就是说该自编码器的输入层和输出层是恒等的,中间层的神经元个数少于输入层和输出层。在这种情况下,是可以做到对时间序列进行特征的压缩和构造的。除了 Auto Encoder 等无监督方法之外,如果使用其他有监督的神经网络结构的话,例如前馈神经网络,循环神经网络,卷积神经网络等网络结构,可以把归一化之后的时间序列当做输入层,输出层就是时间序列的各种标签,无论是该时间序列的形状种类还是时间序列的异常/正常标签。当该神经网络训练好了之后,中间层的输出都可以作为 Time Series To Vector 的一种模式。i.e. 也就是把时间序列压缩成一个更短一点的向量,然后基于 COSINE 相似度等方法来计算原始时间序列的相似度。参考文章:基于自编码器的时间序列异常检测算法基于前馈神经网络的时间序列异常检测算法。

总结

如果想对时间序列进行聚类,其方法是非常多的。无论是时间序列的特征构造,还是时间序列的相似度方法,都是需要基于一些人工经验来做的。如果使用深度学习的方法的话,要么就提供大量的标签数据;要么就只能够使用一些无监督的编码器的方法了。本文目前初步介绍了一些时间序列的聚类算法,后续将会基于笔者的学习情况来做进一步的撰写工作。

参考文献

  1. 聚类分析:https://en.wikipedia.org/wiki/Cluster_analysis
  2. Dynamic Time Warping:https://en.wikipedia.org/wiki/Dynamic_time_warping
  3. Pearson Coefficient:https://en.wikipedia.org/wiki/Pearson_correlation_coefficient
  4. Auto Encoder:https://en.wikipedia.org/wiki/Autoencoder
  5. Word2Vec:https://en.wikipedia.org/wiki/Word2vec,https://samyzaf.com/ML/nlp/nlp.html

时间序列的单调性

在时间序列的众多研究方向上,除了时间序列异常检测,时间序列的相似性,时间序列的趋势预测之外,无论是在量化交易领域还是其余领域,时间序列的单调性都是一个重要课题。本文将会对时间序列的单调性作简单的介绍。

连续函数的单调性

导数1

在微积分里面,通常都会研究可微函数的导数,因为导数是反映可微函数单调性的一个重要指标。假设 f(x) 是定义域 (a,b) 上的可导函数,那么某个点 x_{0}\in(a,b) 的导数则定义为:

f'(x_{0}) = \lim_{x\rightarrow x_{0}}\frac{f(x)-f(x_{0})}{x-x_{0}}.

对于区间 (a,b) 上的可导函数 f(x) 而言,假设 x_{0}\in (a,b)。如果 f'(x_{0})>0,那么在 x_{0} 的附近,f(x) 是严格单调递增函数;如果 f'(x_{0})<0,那么在 x_{0} 的附近,f(x) 是严格单调递减函数;如果 f'(x_{0})=0,则基于这个事实无法轻易的判断 f(x)x_{0} 附近的单调性。可以参考这两个例子:(1)f(x)=x^{2}x_{0}=0;(2)f(x) = x^{3}x_{0}=0。这两个例子在 x_{0}=0 的导数都是零,并且第一个例子在 x_{0}=0 附近没有单调性,x_{0}=0 就是最小值点;但是第二个例子在 x_{0}=0 处是严格递增的。

平方函数

立方函数

时间序列的单调性

通常来说,时间序列分成上涨下跌两种趋势。如果要严格来写的话,当 x_{n-i+1}<\cdots<x_{n} 时,表示时间序列在 [n-i+1,n] 这个区间内是严格单调递增的;当 x_{n-i+1}>\cdots>x_{n} 时,表示时间序列在 [n-i+1, n] 这个区间内是严格单调下跌的。但是,在现实环境中,较难找到这种严格递增或者严格递减的情况。在大部分情况下,只存在一个上涨或者下跌的趋势,一旦聚焦到某个时间戳附近时间序列是有可能存在抖动性的。所以我们需要给出一个定义,用来描述时间序列在一个区间内的趋势是上升还是下跌。

考虑时间序列 X_{N} = [x_{1},\cdots,x_{N}] 的一个子序列 [x_{i},x_{i+1},\cdots,x_{j}],其中 i<j。如果存在某个 k\in (i,j] 和一组非负实数 [w_{i}, w_{i+1},\cdots,w_{j}] 使得

\sum_{m=k}^{j}w_{m}x_{m} > \sum_{m=i}^{k-1} w_{m}x_{m}, 其中\sum_{m=k}^{j}w_{m} = \sum_{m=i}^{k-1}w_{m}.

就称时间序列 [x_{i},x_{i+1},\cdots,x_{j}]上涨的趋势。

如果存在某个 k\in (i,j] 和一组非负实数 [w_{i}, w_{i+1},\cdots,w_{j}] 使得

\sum_{m=k}^{j}w_{m}x_{m} < \sum_{m=i}^{k-1} w_{m}x_{m}, 其中 \sum_{m=k}^{j}w_{m} = \sum_{m=i}^{k-1}w_{m}.

就称时间序列 [x_{i},x_{i+1},\cdots,x_{j}]下跌的趋势。

时间序列的单调性 — 均线方法

虽然时间序列是离散的,但是却可以把连续函数的思想应用在上面。

假设现在有一个时间序列是 X = [x_{1},\cdots,x_{N}],可以考虑第 i 个点 x_{i} 附近的单调性,按照导数的思想来看就是:当 k\geq 1 时,

(x_{i+k}-x_{i})/((i+k)-i) = (x_{i+k}-x_{i})/k,
(x_{i} - x_{i-k})/(i-(i-k)) = (x_{i} -x_{i-k})/k.

考虑特殊的情形,假设 k=1,当第一个公式大于零时,表示 x_{i+1}>x_{i},i.e. 处于单调上升的趋势中。当第一个公式小于零时,表示 x_{i}<x_{i-1},i.e. 处于单调下降的趋势中。

但是,时间序列有可能有一定的波动性,也就是说时间序列有可能其实看上去是单调上升的,但是有一定的噪声或者毛刺。所以需要想办法处理掉一些噪声和毛刺。于是,就有人提出了以下几种方法。

双均线1

简单的移动平均算法

在时间序列领域,简单的移动平均算法 (Simple Moving Average) 是最常见的算法之一。假设原始的时间序列是 X=[x_{1},\cdots,x_{N}],如果考虑时间戳 n 的移动平均值,那就是考虑从时间戳 n 开始,历史上某个窗口上面的所有序列的平均值,用数学公式来描述就是:

M_{w}(n) = \frac{x_{n-w+1}+\cdots+x_{n}}{w} = \frac{\sum_{j=n-w+1}^{n}x_{j}}{w},

其中 w\geq 1 指的就是窗口的大小。

命题 1. 假设窗口值 \ell>s\geq 1M_{s}(n) - M_{\ell}(n) >0, 表示短线上穿长线,曲线有上涨的趋势;M_{s}(n) - M_{\ell}(n) <0, 表示短线下穿长线,曲线有下跌的趋势。

在这里,短线指的是窗口值 s 所对应的移动平均线,长线指的是窗口值 \ell 所对应的移动平均线。

证明.
根据条件可以得到,n-\ell+1\leq n-s<n-s+1<n。假设 M_{s}(n) > M_{\ell}(n),那么通过数学推导可以得到:

M_{s}(n) > M_{\ell}(n)
\Leftrightarrow \frac{\sum_{j=n-s+1}^{n}x_{j}}{s} > \frac{\sum_{j=n-\ell+1}^{n}x_{j}}{\ell} = \frac{\sum_{j=n-\ell+1}^{n-s}x_{j} + \sum_{j=n-s+1}^{n}x_{j}}{\ell}
\Leftrightarrow M_{s}(n)=\frac{\sum_{j=n-s+1}^{n}x_{j}}{s} > \frac{\sum_{j=n-\ell+1}^{n-s}x_{j}}{\ell-s} = M_{\ell-s}(n-s),

此时说明 x_{n} 历史上的 s 个点的平均值大于 x_{n-s} 历史上的 \ell - s 个点的平均值,该序列有上涨的趋势。反之,如果 M_{s}(n) < M_{\ell}(n),那么该序列有下跌的趋势。

带权重的移动平均算法

如果窗口值是 w,对于简单移动平均算法,那么 x_{n-w+1}, \cdots, x_{n} 每个元素的权重都是 1/w,它们都是一样的权重。有的时候我们不希望权重都是恒等的,因为近期的点照理来说是比历史悠久的点更加重要,于是有人提出带权重的移动平均算法 (Weighted Moving Average)。从数学上来看,带权重的移动平均算法指的是

WMA_{w}(n) = \frac{x_{n-w+1}+2\cdot x_{n-w+2}+\cdots + w\cdot x_{n}}{1+2+\cdots+w} = \frac{\sum_{j=1}^{w}j \cdot x_{n-w+j}}{w\ \cdot (w+1)/2}.

wma

命题 2. 
假设窗口值 \ell > s,那么WMA_{s}(n) - WMA_{\ell}(n) >0, 表示短线上穿长线,曲线有上涨的趋势;WMA_{s}(n) - WMA_{\ell}(n) <0, 表示短线下穿长线,曲线有下跌的趋势。

在这里,短线指的是窗口值 s 所对应的带权重的移动平均线,长线指的是窗口值 \ell 所对应的带权重的移动平均线。

证明.
根据假设条件可以得到:n-\ell + 1 \leq n-s < n-s < n。假设 WMA_{s}(n) > WMA_{\ell}(n),那么

WMA_{s}(n) > WMA_{\ell}(n)
\Leftrightarrow \frac{\sum_{j=1}^{s} j \cdot x_{n-s+j}}{s\cdot(s+1)/2} > \frac{\sum_{j=1}^{\ell}j\cdot x_{n-\ell +j}}{\ell\cdot(\ell+1)/2} = \frac{\sum_{j=1}^{\ell-s}j\cdot x_{n-\ell+s} + \sum_{j=\ell -s + 1}^{\ell}j\cdot x_{n-\ell + j}}{\ell\cdot(\ell+1)/2}
\Leftrightarrow \frac{\sum_{j=1}^{s} j \cdot x_{n-s+j}}{s\cdot(s+1)/2} > \frac{\sum_{j=1}^{\ell-s}j\cdot x_{n-\ell+s} + \sum_{j=1}^{s}(j+\ell-s)\cdot x_{n- s + j}}{\ell\cdot(\ell+1)/2}
\Leftrightarrow \sum_{j=1}^{s}\bigg(\frac{j}{s\cdot(s+1)/2} - \frac{j+\ell -s}{\ell\cdot(\ell+1)/2} \bigg) \cdot x_{n-s+j} > \frac{\sum_{j=1}^{\ell-s}j\cdot x_{n-\ell+j}}{\ell\cdot(\ell+1)/2}
\Leftrightarrow \sum_{j=j_{0}}^{s}\bigg(\frac{j}{s\cdot(s+1)/2} - \frac{j+\ell -s}{\ell\cdot(\ell+1)/2} \bigg) \cdot x_{n-s+j} > \frac{\sum_{j=1}^{\ell-s}j\cdot x_{n-\ell+j}}{\ell\cdot(\ell+1)/2}
+ \sum_{j=1}^{j_{0}-1} \bigg(\frac{j+\ell -s}{\ell\cdot(\ell+1)/2}- \frac{j}{s\cdot(s+1)/2}\bigg) \cdot x_{n-s+j},

其中 j_{0}=[s\cdot(s+1)/(\ell + s-1)],这里的 [\cdot] 表示 Gauss 取整函数。因为

\frac{j}{s\cdot(s+1)/2} - \frac{j+\ell -s}{\ell\cdot(\ell+1)/2} \geq 0 \Leftrightarrow j \geq \frac{s\cdot(s+1)}{\ell+s-1},

所以不等式两边的系数都是非负数。而 n-\ell + 1 \leq n - s < n-s+1 < n - s + j_{0} -1 < n - s + j_{0} < n,于是距离当前点 x_{n} 的时间序列相比之前的时间序列有上涨的趋势,并且该不等式两边的系数之和是相等的。这是因为

\sum_{j=j_{0}}^{s}\bigg(\frac{j}{s\cdot(s+1)/2} - \frac{j+\ell -s}{\ell\cdot(\ell+1)/2} \bigg) = \frac{\sum_{j=1}^{\ell-s}j}{\ell\cdot(\ell+1)/2} + \sum_{j=1}^{j_{0}-1} \bigg(\frac{j+\ell -s}{\ell\cdot(\ell+1)/2}- \frac{j}{s\cdot(s+1)/2}\bigg)
\Leftrightarrow \sum_{j=1}^{s}\bigg(\frac{j}{s\cdot(s+1)/2} - \frac{j+\ell -s}{\ell\cdot(\ell+1)/2} \bigg) = \frac{\sum_{j=1}^{\ell-s}j}{\ell\cdot(\ell+1)/2},

以上等式易得。于是,当 WMA_{s}(n) >WMA_{\ell}(n) 时,表示时间序列有上涨的趋势;当 WMA_{s}(n) < WMA_{\ell}(n) 时,表示时间序列有下跌的趋势。

指数移动平均算法

指数移动平均算法 (Exponentially Weighted Moving Average) 指的也是移动平均算法,但是它的权重并不是线性递减的,而是呈指数形式递减的。具体来说,如果时间序列是 \{x_{i}, i\geq 1\},那么它的指数移动平均算法就是:

\text{EWMA}(\alpha, i) = x_{1}, \text{ when } i = 1,
\text{EWMA}(\alpha, i) = \alpha \cdot x_{i} + (1-\alpha) \cdot \text{EWMA}(\alpha, i-1), \text{ when } i \geq 2,

在这里 \alpha\in (0,1)

ewma

从数学公式可以推导得出:

\text{EWMA}(\alpha, i) = \alpha x_{i} + \alpha(1-\alpha) x_{i-1} + \cdots \alpha(1-\alpha)^{k}x_{i-k} + (1-\alpha)^{k+1}\text{EWMA}(\alpha, t-(k+1)).

在这种情况下,假设 s<\ell,那么短线和长线则分别是:

\text{EWMA}_{s}(\alpha, n) = \alpha x_{n} + \alpha(1-\alpha) x_{n-1} + \cdots + \alpha(1-\alpha)^{s-2}x_{n-s+2} + (1-\alpha)^{s-1}x_{n-s+1},
\text{EWMA}_{\ell}(\beta, n) = \beta x_{n} + \beta(1-\beta) x_{n-1} + \cdots + \beta(1-\beta)^{\ell-2}x_{n-\ell+2} + (1-\beta)^{\ell-1}x_{n-\ell+1}.

在这里,\alpha 是与 s 相关的值,\beta 是与 \ell 相关的值。

命题 3. 
假设 s<\ell,当 0<\beta<\alpha<\min\{1,1/(s-1)\} 时,\text{EWMA}_{s}(\alpha, n) - \text{EWMA}_{\ell}(\beta, n) > 0, 表示短线上穿长线,曲线有上涨的趋势;\text{EWMA}_{s}(\alpha, n) - \text{EWMA}_{\ell}(\beta, n) <0, 表示短线下穿长线,曲线有下跌的趋势。注:当 s=1 时,1/(s-1) 可以看做 +\infty.

证明.
s=1 时,\text{EWMA}_{s}(\alpha,n) = x_{n}。那么

\text{EWMA}_{s}(\alpha, n) > \text{EWMA}_{\ell}(\beta,n)
\Leftrightarrow x_{n} > \beta x_{n} + \beta(1-\beta) x_{n-1} + \cdots + \beta(1-\beta)^{\ell-2}x_{n-\ell+2} + (1-\beta)^{\ell-1}x_{n-\ell+1}
\Leftrightarrow x_{n} > \beta x_{n-1} + \cdots + \beta(1-\beta)^{\ell-3}x_{n-\ell+2}+ (1-\beta)^{\ell-2}x_{n-\ell+1}.

这表示时间序列有上涨的趋势。反之,当 \text{EWMA}_{s}(\alpha, n) = x_{n} < \text{EWMA}_{\ell}(\beta, n) 时,表示时间序列有下跌的趋势。

s\geq 2 时,根据假设有 0<\beta<\alpha<1/(s-1),并且

\text{EWMA}_{s}(\alpha, n) = \alpha x_{n} + \alpha(1-\alpha) x_{n-1} + \cdots + \alpha(1-\alpha)^{s-2}x_{n-s+2} + (1-\alpha)^{s-1}x_{n-s+1},
\text{EWMA}_{\ell}(\beta, n) = \beta x_{n} + \beta(1-\beta) x_{n-1} + \cdots + \beta(1-\beta)^{\ell-2}x_{n-\ell+2} + (1-\beta)^{\ell-1}x_{n-\ell+1}
= \beta x_{n} + \beta(1-\beta) x_{n-1} + \cdots + \beta(1-\beta)^{s-2}x_{n-s+2} + \beta(1-\beta)^{s-1}x_{n-s+1}
+ \beta(1-\beta)^{s}x_{n-s} + \cdots + (1-\beta)^{\ell-1}x_{n-\ell+1}.

假设 g(x) = x(1-x)^{n},通过计算可以得到 g'(x) = (1-x)^{n-1}(1-(n+1)x),也就是说 g(x)(0, 1/(n+1)) 上是递增函数,在 (1/(n+1), 1) 是递减函数。于是当 0<\beta<\alpha<1/(s-1) 时,

\alpha > \beta,
\alpha(1-\alpha) > \beta(1-\beta),
\cdots
\alpha(1-\alpha)^{s-2} > \beta(1-\beta)^{s-2}.

如果 (1-\alpha)^{s-1} > \beta(1-\beta)^{s-1},那么 \text{EWMA}_{s}(\alpha, n) > \text{EWMA}_{\ell}(\beta, n) 可以写成

(\alpha -\beta)x_{n} +\cdots + (\alpha(1-\alpha)^{s-2}-\beta(1-\beta)^{s-2})x_{n-s+2} + ((1-\alpha)^{s-1}-\beta(1-\beta)^{s-1})x_{n-s+1}
> \beta(1-\beta)^{s}x_{n-s} +\cdots + (1-\beta)^{\ell-1}x_{n-\ell+1},

说明在这种情况下时间序列有上涨的趋势。如果 (1-\alpha)^{s-1} < \beta(1-\beta)^{s-1},那么 \text{EWMA}_{s}(\alpha, n)> \text{EWMA}_{\ell}(\beta, n) 可以写成

(\alpha -\beta)x_{n} + \cdots + (\alpha(1-\alpha)^{s-2}-\beta(1-\beta)^{s-2})x_{n-s+2}
> (\beta(1-\beta)^{s-1} - (1-\alpha)^{s-1})x_{n-s+1} + \beta(1-\beta)^{s}x_{n-s} +\cdots + (1-\beta)^{\ell-1}x_{n-\ell+1},

说明在这种情况下,时间序列有上涨的趋势。

反之,当 \text{EWMA}_{s}(\alpha, n) < \text{EWMA}_{\ell}(\beta, n) 时,也可以使用同样的方法证明时间序列有下跌的趋势。

时间序列的单调性 — 带状方法

根据时间序列的走势,其实可以按照一定的规则计算出它的置信区间,也就是所谓的上界和下界。当最后一些点超过上界或者低于下界的时候,就可以说明这个时间序列的当前的趋势。

控制图1

3-\sigma 控制图

假设时间序列是 X_{N} = [x_{1},\cdots, x_{N}],为了计算某个时间戳 nx_{n} 的走势,需要考虑该时间序列历史上的一些点。假设我们考虑 [x_{1},x_{2},\cdots, x_{n}] 中的所有点,可以计算出均值和方差如下:

\mu = \frac{x_{1}+\cdots+x_{n}}{n},
\sigma^{2} = \frac{(x_{1}-\mu)^{2}+\cdots+(x_{n}-\mu)^{2}}{n}.

那么就可以计算出上界,中间线,下界分别是:

\text{UCL} = \mu + L \cdot \sigma,
\text{Center Line} = \mu,
\text{LCL} = \mu - L \cdot \sigma,

这里的 L 表示系数,通常选择 L=3

命题 4. x_{n} > \text{UCL},那么说明 x_{n} 有上涨的趋势;当 x_{n} < \text{LCL} 时,那么说明 x_{n} 有下跌的趋势;这里的 UCL 和 LCL 是基于 3-\sigma 原理所得到的上下界。

Moving Average 控制图

假设我们考虑的时间序列为 X_{N} = [x_{1},\cdots, x_{N}],那么基于窗口 w 的移动平均值就是

M_{w}(n) = \frac{x_{n-w+1}+\cdots + x_{n}}{w} = \frac{\sum_{j=n-w+1}^{n}x_{j}}{w}.

那么 M_{w}(n) 的方差是

V(M_{w}) = \frac{1}{w^{2}}\sum_{j=n-w+1}^{n} V(x_{j}) = \frac{1}{w^{2}}\sum_{j=n-w+1}^{n}\sigma^{2} = \frac{\sigma^{2}}{w}.

于是,基于移动平均算法的控制图就是:

\text{UCL} = \mu + L\cdot \frac{\sigma}{\sqrt{w}},
\text{Center Line} = \mu,
\text{LCL} = \mu - L \cdot \frac{\sigma}{\sqrt{w}},

这里的 L 表示系数,通常选择 L=3

命题 5. x_{n} > \text{UCL},那么说明 x_{n} 有上涨的趋势;当 x_{n} < \text{LCL} 时,那么说明 x_{n} 有下跌的趋势;这里的 UCL 和 LCL 是基于移动平均算法的控制图所得到的上下界。

macontrolchart

EWMA 控制图

假设 X_{N} = [x_{1},\cdots, x_{N}],那么根据指数移动平均算法可以得到:

z_{i} = x_{1}, \text{ when } i=1,
z_{i} = \lambda x_{i} + (1-\lambda) z_{i-1}, \text{ when } i\geq 2.

进一步分析可以得到:z_{i} 的方差是:

\sigma_{z_{i}}^{2}= \lambda^{2} \sigma^{2} + (1-\lambda)^{2} \sigma_{z_{i-1}}^{2},

于是,
\sigma_{z_{i}}^{2} = \frac{\lambda^{2}}{1-(1-\lambda)^{2}} \sigma^{2} \Rightarrow \sigma_{z_{i}} = \sqrt{\frac{\lambda}{2-\lambda}}\sigma.

因此,基于 EWMA 的控制图指的是:

\text{UCL} = \mu + L\sigma\sqrt{\frac{\lambda}{2-\lambda}},
\text{Center Line} = \mu,
\text{LCL} = \mu - L\sigma\sqrt{\frac{\lambda}{2-\lambda}},

这里的 L 是系数,通常取 L= 3

命题 6. x_{n} > \text{UCL},那么说明 x_{n} 有上涨的趋势;当 x_{n} < \text{LCL} 时,那么说明 x_{n} 有下跌的趋势;这里的 UCL 和 LCL 是基于 EWMA 的控制图所得到的上下界。

ewmacontrolchart

时间序列的单调性 — 柱状方法

macd1

MACD 方法

MACD 算法是比较常见的用于判断时间序列单调性的方法,它的大致思路分成以下几步:

  • 根据长短窗口分别计算两条指数移动平均线(EWMA short, EWMA long);
  • 计算两条指数移动平均线之间的距离,作为离差值(DIF);
  • 计算离差值(DIF)的指数移动平均线,作为DEA;
  • 将 (DIF-DEA) * 2 作为 MACD 柱状图。

用数学公式来详细描述就是:令 \ell = 26, s = 12, signal = 9,基于时间序列 X_{N} = [x_{1},\cdots,x_{N}],可以计算基于指数移动平均的两条线,对于所有的 1\leq n\leq N,有

\text{EWMA}_{s}(\alpha, n) = (1-\alpha) \cdot \text{EWMA}_{s}(\alpha, n-1) + \alpha \cdot x_{n},
\text{EWMA}_{\ell}(\beta,n) = (1-\beta) \cdot \text{EWMA}_{\ell}(\beta, n-1) + \beta \cdot x_{n},

其中

\alpha = \frac{2}{s+1} = \frac{2}{13},
\beta = \frac{2}{\ell+1} = \frac{2}{27}.

进一步可以计算离差值 (DIF) 如下:

\text{DIF}(n) = \text{EWMA}_{s}(\alpha, n) - \text{EWMA}_{\ell}(\beta,n).

\gamma = 2 / (signal + 1),计算 DEA 如下:

\text{DEA}(\gamma, n) = \gamma * \text{DIF}(n) + (1-\gamma) * \text{DEA}(\gamma, n).

最后可以计算 MACD 柱状图,对任意的 \forall \text{ }1\leq n\leq N

\text{MACD}(n) = (\text{DIF}(n) - \text{DEA}(\gamma, n)) * 2.

命题 7. 关于 MACD 的部分性质如下:

  • 当 DIF(n) 与 DEA(n) 都大于零时,表示时间序列有上涨的趋势;
  • 当 DIF(n) 与 DEA(n) 都小于零时,表示时间序列有递减的趋势;
  • 当 DIF(n) 下穿 DEA(n) 时,此时 MACD(n) 小于零,表示时间序列有下跌的趋势;
  • 当 DIF(n) 上穿 DEA(n) 时,此时 MACD(n) 大于零,表示时间序列有上涨的趋势;
  • MACD(n) 附近的向上或者向下的面积,可以作为时间序列上涨或者下跌幅度的标志。

PS:算法可以从指数移动平均算法换成移动平均算法或者带权重的移动平均算法,长短线的周期可以不局限于 26 和 12,信号线的周期也不局限于 9。

 

参考资料

  1. Moving Average:https://en.wikipedia.org/wiki/Moving_average
  2. Double Exponentially Moving Average:https://www.investopedia.com/articles/trading/10/double-exponential-moving-average.asp
  3. Control Chart:https://en.wikipedia.org/wiki/Control_chart
  4. MACD:https://www.investopedia.com/terms/m/macd.asp
  5. Introduction to Statistical Quality Control 6th edition,Douglas C.Montgomery

基于前馈神经网络的时间序列异常检测算法

引言

在时间序列异常检测中,特征工程往往是非常繁琐而复杂的,怎样才能够减少时间序列的特征工程工作量一直是一个关键问题。在本文中,作者们提出了一个新的思路,使用深度学习的办法来进行端到端的训练,从而减少时间序列的特征工程。

提到深度学习,大家都能够想到卷积神经网络(Convolutional Neural Network )在图像识别中的优异表现,能够想到循环神经网络(Recurrent Neural Network)在机器翻译和文本挖掘领域中所取得的成绩。而一旦提到时间序列,一般的人都能够想到使用 ARIMA 模型或者 LSTM 模型来拟合周期型的时间序列,或者使用其他算法来进行时间序列的异常检测。在这篇文章中,既不谈 CNN 和 LSTM 等深度学习模型,也不谈如何使用 LSTM 来拟合时间序列,本文将会介绍如何使用前馈神经网络 FNN 来进行时间序列的异常检测。并且将会介绍如何使用前馈神经网络,来拟合各种各样的时间序列特征。本篇论文《Feedforward Neural Network for Time Series Anomaly Detection》目前已经挂在 Arxiv 上,有兴趣的读者可以自行参阅:https://arxiv.org/abs/1812.08389

时间序列异常检测

时间序列异常检测的目的就是在时间序列中寻找不符合常见规律的异常点,无论是在学术界还是工业界这都是一个非常重要的问题。而时间序列异常检测的算法也是层出不穷,无论是统计学中的控制图理论,还是指数移动平均算法,甚至近些年最火的深度学习,都可以应用在时间序列的异常检测上面。在通常情况下,时间序列的异常点是十分稀少的,正常点是非常多的,因此,通常的套路都是使用统计判别算法无监督算法作为第一层,把有监督算法作为第二层,形成一个无监督与有监督相结合的框架。使用无监督算法可以过滤掉大量的正常样本,将我们标注的注意力放在少数的候选集上;使用有监督算法可以大量的提升准确率,可以把时间序列异常点精确地挑选出来。这个框架之前也说过多次,因此在这里就不再做赘述。

异常检测技术框架1

提到第二层的有监督学习算法,通常来说就包括逻辑回归,随机森林,GBDT,XGBoost,LightGBM 等算法。在使用这些算法的时候,不可避免地就需要构造时间序列的特征,也就是人工撰写特征工程的工作。提到时间序列的特征,一般都会想到各种各样的统计特征,例如最大值,最小值,均值等等。除了统计特征之外,我们还可以使用一些简单的时间序列模型,例如移动平均算法,指数移动平均算法等去拟合现有的时间序列,所得到的拟合值与实际值的差值就可以作为时间序列的拟合特征。除了统计特征和拟合特征之外,我们还可以根据时间序列的走势,例如周期型,毛刺型,定时任务型来构造出时间序列的分类特征,用于时间序列形状的多分类问题。因此,就笔者的个人观点,时间序列的特征大体上可以分成统计特征,拟合特征,周期性特征,分类特征等几大类。

时间序列的特征工程1

在机器学习领域下,可以使用准确率和召回率来评价一个系统或者一个模型的好坏。在这里,我们可以使用 negative 标签来表示时间序列的异常,使用 positive 标签来表示时间序列的正常。因此模型的召回率准确率F1-Score 可以如下表示:

\text{Recall}=\frac{\text{the number of true anomalous points detected}}{\text{the number of true anomalous points}}=\frac{TN}{TN+FP},

\text{Precision}=\frac{\text{the number of true anomalous points detected}}{\text{the number of anomalous points detected}}=\frac{TN}{TN+FN},

\text{F1-Score} = \frac{2 \cdot \text{precision} \cdot \text{recall}}{\text{precision}+\text{recall}}.

Table1

而时间序列异常检测工作也不是一件容易的事情,通常来说它具有以下几个难点:

  1. 海量时间序列。通常情况下,时间序列不仅仅是按照天来收集数据的,有可能是按照小时,甚至分钟量级来收集数据。因此,在一些情况下,时间序列的数量和长度都是非常大的。
  2. 类别不均衡。一般来说,在时间序列异常检测领域,正常样本是非常多的,异常样本是非常少的。在这种情况下,训练模型的时候通常都会遇到类别不均衡的问题。
  3. 样本不完整。通常来说,时间序列异常检测领域,是需要用人工来标注样本的,这与推荐系统是非常不一样的。这种情况下,很难通过人工标注的方式,来获得所有类型的样本数据。
  4. 特征工程复杂。时间序列有着自己的特点,通过特征工程的方式,确实可以获得不少的特征,但是随着时间序列种类的变多,特征工程将会越来越复杂。

基于以上几个难点,本篇论文提出了一种端到端(End to End)的训练方法,可以解决上面的一些问题。

深度学习的简单回顾

其实最简单的深度学习模型还不是 CNN 和 RNN,最简单的深度学习模型应该是前馈神经网络,也就是所谓的 FNN 模型。当隐藏层的层数较少的时候,当前的前馈神经网络可以称为浅层神经网络;当隐藏层的层数达到一定的数量的时候,当前的前馈神经网络就是所谓的深度前馈神经网络。下面就是一个最简单的前馈神经网络的例子,最左侧是输入层,中间有两个隐藏层,最右侧是输出层。

forwardneuralnetworks1

通常来说,前馈神经网络会涉及到必要的矩阵运算,激活函数的设置等。其中,激活函数的选择有很多,有兴趣的读者可以参见 tensorflow 的官网。比较常见的激活函数有 Sigmoid 函数,tanh 函数,relu 函数以及 relu 函数的各种变种形式(Leaky Relu, PreLu, Elu),以及 Softplus 函数等。

详细来说,以上的激活函数的具体函数表达式如下:

\sigma(x) = 1/(1+e^{-x}),

\tanh(x) = \sinh(x)/\cosh(x),

ReLU(x) = \max\{0,x\},

Leaky \text{ }ReLu(x) = \mathcal{I}_{\{x<0\}}\cdot(\alpha x) + \mathcal{I}_{\{x\geq 0\}}\cdot(x), \alpha\in \mathbb{R},

ELU(x) = \mathcal{I}_{\{x<0\}}\cdot(\alpha(e^{x}-1)) + \mathcal{I}_{\{x\geq 0\}}\cdot(x),

PreLU(x) = \mathcal{I}_{\{x_{j}<0\}}\cdot(a_{j}x_{j})+\mathcal{I}_{\{x_{j}\geq 0\}}(x_{j}),

selu(x) = \lambda\cdot(\mathcal{I}_{\{x<0\}}\cdot(\alpha e^{x}-\alpha) + \mathcal{I}_{\{x\geq 0\}}\cdot x), \lambda,\alpha\in\mathbb{R},

softplus(x) = \ln(1+e^{x}).

 

深度学习与时间序列的特征工程

通常来说,基于人工的时间序列特征工程会比较复杂,不仅需要包括均值方差等内容,还包括各种各样的特征,如统计特征,拟合特征,分类特征等。在这种情况下,随着时间的迁移,特征工程将会变得越来越复杂,并且在预测的时候,时间复杂度也会大量增加。那么有没有办法来解决这个问题呢?答案是肯定的。时间序列的一部分特征可以按照如下表格 Table 2 来表示:其中包括均值,方差等特征,也包括拟合特征和部分分类特征。

Table2.png

基于 Table 2,本篇论文的主要定理陈述如下:

Main Theorem. 对于任意正整数 n\geq 1,存在一个前馈神经网络 D 使得对于所有的时间序列 \boldsymbol{X}_{n}=[x_{1},\cdots,x_{n}],该神经网络的输入和输出分别是 \boldsymbol{X}_{n} 和表格 2 中 \boldsymbol{X}_{n} 的特征层。

下面,我们就来尝试使用深度学习模型来构造出时间序列的统计特征。首先,我们可以从几个简单的统计特征开始构造,那就是加法(add),减法(minus),最大值(max),最小值(min),均值(avg),绝对值(abs)。在构造时间序列 X_{n} = [x_{1},\cdots, x_{n}] 的以上统计特征之前,我们可以先使用神经网络构造出这几种运算方法。

加法 add(x,y) = x+y 与减法 sub(x,y) = x-y 的构造十分简单,如下图构造即可:

绝对值函数 abs(x) = |x|,  通过计算可以得到 abs(x) = relu(x) + relu(-x).  所以,可以构造如下的神经网络来表示绝对值函数:

functionABS

最大值函数 \max(x,y), 通过计算可以得到

\max(x,y) = (|x-y| + x+ y)/2.

所以,只要能够使用前面的神经网络来构造出绝对值模块,然后使用加减法就可以构造出最大值函数。

functionMAX

最小值函数 \min(x,y), 通过计算可以得到

\min(x,y) = (x+y-|x-y|)/2.

所以,同样使用前面的神经网络来构造出绝对值模块,然后使用加减法就可以构造出最小值函数。

functionMIN

在这种情况下,只要能够构造出两个元素的最大值,最小值函数,就可以轻易的构造出 n 个元素的最大最小值函数,因为

\max(x_{1},\cdots,x_{n}) = \max(x_{1},\max(x_{2},\max(x_{3},\cdots,\max(x_{n-1},x_{n}))),

\min(x_{1},\cdots,x_{n}) = \min(x_{1},\min(x_{2},\max(x_{3},\cdots,\min(x_{n-1},x_{n}))).

平均值函数 avg 指的是 avg(x_{1},\cdots, x_{n}) = (x_{1}+\cdots + x_{n})/n.

functionAVG

平方函数 y = x^{2}, 这个函数可以使用 Softplus 激活函数来表达。令 Softplus 为

f(x) = softplus(x) = \ln(1+e^{x}),

通过计算可以得到:

f(0) = \ln(2),

Df(x) = \sigma(x), Df(0) = 1/2,

D^{2}f(x) = \sigma'(x) = \sigma(x)\cdot(1-\sigma(x)), D^{2}f(0) = 1/4,

D^{3}f(x) = \sigma''(x), D^{3}f(0) = 0,

因此,Softplus 函数的 Taylor Series 是:

f(x) = softplus(x) = f(0) + Df(0)x+ \frac{1}{2!}D^{2}f(0)x^{2} + \frac{1}{3!}D^{3}f(0)x^{3}+o(x^{3})

= \ln(2) +\frac{1}{2}x+\frac{1}{8}x^{2}+o(x^{3}),

因此,x^{2} \approx 8\cdot(f(x) - \ln(2)-\frac{1}{2}x) = 8\cdot(\ln(1+e^{x})-\ln(2)-\frac{1}{2}x). y=x^{2} 就可以用神经网络来近似表示:

functionPower2

立方函数 y = x^{3}, 这个函数可以使用 Sigmoid 激活函数来表达。因为 Sigmoid 函数的 Taylor Series 是

\sigma(x) = \frac{1}{2}+\frac{1}{4}x-\frac{1}{48}x^{3}+o(x^{3}),

那么 x^{3} \approx -48\cdot(\sigma(x) - \frac{1}{2} -\frac{1}{4}x). y=x^{3} 就可以用神经网络来近似表示:

functionPower3

深度学习与时间序列的统计特征

提到时间序列的统计特征,一般指的都是已知的时间序列 X_{n} =[x_{1},\cdots,x_{n}] 的最大值,最小值等各种各样的统计指标。如果按照上文所描述的,以下特征都可以用神经网络轻松构造出来:

max:

\max_{1\leq i\leq n}\{x_{1},\cdots,x_{n}\},

min:

\min_{1\leq i\leq n}\{x_{1},\cdots,x_{n}\},

avg:

\mu = \sum_{i=1}^{n}x_{i}/n,

variance:

\sigma^{2}= \sum_{i=1}^{n}(x_{i}-\mu)^{2}/n, \text{ where } \mu = \sum_{i=1}^{n}x_{i}/n,

skewness:

\sum_{i=1}^{n}[(x_{i}-\mu)/\sigma]^{3},

kurtosis:

\sum_{i=1}^{n}[(x_{i}-\mu)/\sigma]^{4},

difference:

x_{2}-x_{1}, x_{3}-x_{2},\cdots, x_{n}-x_{n-1},

integration:

\sum_{i=1}^{n}x_{i},

absolute_sum_of_changes:

E=\sum_{i=1}^{n-1}|x_{i+1}-x_{i}|,

mean_change:

\frac{1}{n}\sum_{i=1}^{n-1}(x_{i+1}-x_{i}) = \frac{1}{n}(x_{n}-x_{1}),

mean_second_derivative_central:

\frac{1}{2n}\sum_{i=1}^{n-2}(x_{i+2}-2x_{i+1}+x_{i}),

除了以上比较容易构造的特征之外,还有一类特征只为了计算个数的,例如 count_above_mean,count_below_mean 分别是为了计算大于均值的元素个数,小于均值的元素个数。那么最重要的就是要构造出计数函数 count。

回顾一下 NOT 逻辑计算门是:

1 \rightarrow 0, 0 \rightarrow 1.

这个逻辑门可以使用逻辑回归函数来估计,可以参见 \sigma 函数的图像,当 x>10 的时候,\sigma(x) \approx 1;x<-10 的时候,\sigma(x)\approx 0. 因此,可以使用函数 f(x) =\sigma(-20x+10) 来估计 NOT 逻辑门。

x=1 时,f(x) = f(1) = \sigma(-10) \approx 0;

x=0 时,f(x) = f(0) = \sigma(10)\approx 1.

下面,我们来考虑如何构造出一个函数来判断待测试值 x 是否大于常数 a.

f_{1}(x) = \sigma(-2\cdot 10^{4} \cdot relu(-x+a) + 10), 可以得到

x>a 时,f_{1}(x) = \sigma(10) \approx 1;

x<a-10^{-3} 时,f_{1}(x) = \sigma(-2\cdot 10^{4}\cdot (a-x) + 10)<\sigma(-10) \approx 0.

因此,所构造的函数 f_{1}(x) 近似于判断待测试值 x 是否大于常数 a.

下面,可以构造一个类似的函数来判断待测试值 x 是否小于常数 a.f_{2}(x) = \sigma(-2\cdot 10^{4} \cdot relu(x-a) + 10), 可以得到

x<a 时,f_{2}(x) = \sigma(10)\approx 1;

x>a+10^{-3} 时,f_{2}(x) = \sigma(-2\cdot 10^{4}\cdot (x-a)+10) < \sigma(-10)\approx 0.

因此,所构造的函数 f_{2}(x) 近似于判断待测试值 x 是否小于常数 a.

回到时间序列的特征 count_above_mean 与 count_below_mean,可以先计算出均值 mean,然后计算时间序列 X_{n}=[x_{1},\cdots,x_{n}] 每个点与均值的差值,然后使用前面的神经网络模块计算出大于零的差值个数与小于零的差值个数即可。

functionCountAboveZero

functionCountBelowZero

深度学习与时间序列的拟合特征

时间序列的拟合特征的基本想法是用一些简单的时间序列算法去拟合数据,然后使用拟合数据和真实数据来形成必要的特征。在这里,我们经常使用的算法包括移动平均算法,带权重的移动平均算法,指数移动平均算法等。下面,我们来看一下如何使用神经网络算法来构造出这几个算法。

移动平均算法

移动平均算法指的是,已知时间序列 X_{n} = [x_{1},\cdots,x_{n}], 我们可以使用一个窗口值 w\geq 1 得到一组光滑后的时间序列,具体来说就是:

SMA_{j}=\sum_{k=1}^{w}x_{j-w+k}/w = (x_{j-w+1}+\cdots+x_{j})/w,

特别地,如果针对时间序列的最后一个点,就可以得到:

SMA_{n} = \sum_{k=1}^{w}x_{n-w+k}/w = (x_{n-w+1}+\cdots+x_{n})/w.

因此,当前的实际值与光滑后所得到的值的差值就可以作为特征,i.e. SMA_{n}-x_{n} 就可以作为一个特征。然后根据不同的窗口长度 w\geq 1 就可以得到不同的特征值。

用和之前类似的方法,我们同样可以构造出一个神经网络算法来得到这个特征。

functionSMA

带权重的移动平均算法

带权重的移动平均算法指的是计算平均值的时候将不同的点带上不同的数值,i.e.

WMA_{j} = \sum_{k=1}^{w}k \cdot x_{j-w+k}/\sum_{k=1}^{w}k.

特别地,如果针对时间序列的最后一个点,就可以得到:

WMA_{n} = \sum_{k=1}^{w}k \cdot x_{n-w+k}/\sum_{k=1}^{w}k.

用和之前类似的方法,我们同样可以构造出一个神经网络算法来得到这个特征。

functionWMA

指数移动平均算法

指数移动平均算法指的是在已知时间序列的基础上进行加权操作,而权重的大小是呈指数衰减的。用公式来描述就是,已知时间序列 X_{n} = [x_{1},\cdots,x_{n}],

EWMA_{1}=x_{1},

EWMA_{j} = \alpha \cdot x_{j-1} + (1-\alpha)\cdot EWMA_{j-1}, \forall j\geq 1.

从定义上可以得到:

EWMA_{n}

= \alpha[x_{n-1}+(1-\alpha)x_{n-2}+\cdots+(1-\alpha)^{k}x_{n-(k+1)}] + (1-\alpha)^{k+1}EWMA_{n-(k+1)}

\approx \alpha[x_{n-1}+(1-\alpha)x_{n-2}+\cdots+(1-\alpha)^{k}x_{n-(k+1)}]

因此,只需要构建一个加权求和,然后计算 EWMA_{n}-x_{n} 的取值就可以得到特征。所以,神经网络可以构建为如下形式:

functionEWMA

深度学习与时间序列的周期性特征

在这里,时间序列的周期性特征就是指当前点与昨天同一个时刻,七天前同一个时刻的差值等指标。可以假设时间序列 X_{n} = [x_{week}, x_{yesterday}, x_{today}] 可以拆分成三个部分 x_{week}, x_{yesterday}, x_{today}, 分别是一周前的数据,昨天的数据,今天的数据,假设它们的长度都是 [n/3],最后一点都表示不同天但是同一个时刻的取值。所以,同环比特征

x_{today}[-1] - x_{yesterday}[-1]x_{today}[-1] - x_{week}[-1] 都是可以通过神经网络构造出来。

mean(x_{today}) - mean(x_{yesterday})mean(x_{today}) - mean(x_{week}) 这一类特征也可以构造出来。

有一些特征时用来计算是否高于历史一段时间的最大值,或者低于历史一段时间的最小值,在这里可以先构造 \max, min 等函数,再计算两者的差值即可。例如,我们可以构造一个特征用于计算当前值是否高过昨天的峰值,以及超出的幅度是多少。用公式来表示那就是:

\max\{x_{today}[-1]-\max\{x_{yesterday}\}, 0\},

如果当前值 x_{today}[-1] 大于昨天的最大值,就返回它高出的幅度;否则就返回0。

也可以构造一个特征用于计算当前值是否低于一周前的最低值,以及低于的幅度是多少。用公式来表示那就是:

\min\{x_{today}[-1]-\min\{x_{week}\},0\},

如果当前值 x_{today}[-1] 小于一周前的最低值,就返回它低于的幅度;否则就返回0。

这两个特征只需要使用神经网络表示出 \max, \min, minus 激活函数使用 ReLU 即可。

深度学习与时间序列的分类特征

在时间序列的分类特征里面,有一种特征叫做值分布特征。假设时间序列的值域在 [0,1] 之内,值分布特征的意思是计算出一个时间序列 X_{n} = [x_{1},\cdots,x_{n}] 的取值在 [0,0.1), [0.1,0.2),\cdots,[0.9,1] 这十个桶的个数,进一步得到它们落入这十个桶的概率是多少。这一类特征可以通过之前所构造的 count 函数来生成。因此,分类特征也是可以通过构造神经网络来形成的。

深度学习与时间序列的特征总结

至此,我们已经证明,对于任意长度 n\geq 1,存在一个神经网络,它的输入和输出分别是原始的时间序列与 Table 2 中的时间序列特征层。整体来看,

1. 存在多个前馈神经网络可以生成时间序列的特征;

2. 深度学习+时间序列异常检测可以实现端到端(End to End)的训练过程,也就是说:输入数据是归一化之后的原始数据(normalized raw data),输出的是两个标签(正常&异常),神经网络的权重可以通过大量数据集和目标函数训练出来。

3. 如果神经网络的输入是归一化之后的 raw data,输出是标签 1 或者 0。此时的前馈神经网络需要至少两个以上的隐藏层,才能够达到较好地提取特征的目的。

基于前馈神经网络的时间序列异常检测算法

通过前面的陈述,我们可以构造一个端到端(End to End)的前馈神经网络,意思就是说:前馈神经网络的输入层是原始的时间序列(归一化之后的数据),前馈神经网络的输出层是标签。

在这里,我们考虑的是三天数据的子序列,以 20180810 的 10:00am 为例,考虑当天历史三小时的数据(07:00-10:00),昨天 20180809 前后三小时的数据(07:00-13:00),再考虑一周前 20180803 前后三小时的数据(07:00-13:00)。这样就形成了一个子序列,总共有 903 个点。然后我们可以使用最大最小归一化获得神经网络的输入数据,而输出数据指的就是最后一个点是异常点(label = 0)还是正常(label = 1)。

Figure4

Table3
Figure5

Figure 5 指出了前馈神经网络的结构图,输入层是归一化之后的时间序列原始数据,中间两层是隐藏层,输出层就是异常或者正常的概率值。而中间层的激活函数可以使用 ReLU 或者 Leaky ReLU,在这里我们通过实验发现 Leaky ReLU 的效果略好于 ReLU。而最后一层的激活函数使用的是 Softmax 函数,输出的两个概率值之和永远都是 1。

在这种神经网络结构下,神经网络的参数量级大约是 10 万量级,在这种情况下,使用少量的几百几千个样本几乎是无法训练出来的。在这里,我们使用了大约 10 万 的样本数据,才得到一个还不错的效果。在这里,我们使用 3-Sigma 算法EWMA 控制图算法多项式回归算法孤立森林算法XGBoost + 特征工程前馈神经网络来进行算法的对比。通过数据的对比可以得到,XGBoost 与 DNN 其实差不多,都能够达到实际使用的上线标准。

Table4Table5

Table6

从深度学习的基础知识可以得到,CNN 的中间层可以用来提取图片的特征,因此,这里的前馈神经网络的隐藏层的输出同样可以作为时间序列的特征层。于是,我们通过实验,基于隐藏层的输出可以作为时间序列的隐藏特征,也就是所谓的 Time Series To Vector。通过 Time Series To Vector,我们可以既可以对时间序列进行聚类(KMeans),也可以对时间序列进行 Cosine 相似度的计算,进而得到同一类时间序列和相似的时间序列。

Figure8Figure9

论文的主要结论

从本文的主要定理和实验效果来看,前馈神经网络是一个非常有效地可以用作时间序列异常检测的工具。本篇论文不仅提供了一个端到端的训练方法,并且不需要对时间序列进行特征工程的操作。从实验数据来看,使用前馈神经网络(feedforward neural network)可以得到与 XGBoost 差不多的效果。并且,前馈神经网络隐藏层的输出可以作为时间序列的隐藏特征(Time Series To Vector),使用 Cosine 相似度或者 KMeans 算法就可以对时间序列进行相似度的计算和聚类操作。在时间序列异常检测领域,使用特征工程 + 有监督算法的方法论比较多,而使用端到端的训练方法,也就是前馈神经网络的方法应该还是相对较少的。因此,端到端的前馈神经网络算法应该是本文的方法与其他方法论的最大不同点。

参考文献

  1. 《企业级 AIOps 实施建议》白皮书-V0.6 版本
  2. 《腾讯运维的AI实践》— 2018年4月 GOPS 全球运维大会
  3. Feedforward Neural Network for Time Series Anomaly Detection》,Arxiv,2018年12月18日
  4. Github:https://github.com/Tencent/Metis

Facebook 时间序列预测算法 Prophet 的研究

Prophet 简介

Facebook 去年开源了一个时间序列预测的算法,叫做 fbprophet,它的官方网址与基本介绍来自于以下几个网站:

  1. Github:https://github.com/facebook/prophet
  2. 官方网址:https://facebook.github.io/prophet/
  3. 论文名字与网址:Forecasting at scale,https://peerj.com/preprints/3190/

从官网的介绍来看,Facebook 所提供的 prophet 算法不仅可以处理时间序列存在一些异常值的情况,也可以处理部分缺失值的情形,还能够几乎全自动地预测时间序列未来的走势。从论文上的描述来看,这个 prophet 算法是基于时间序列分解和机器学习的拟合来做的,其中在拟合模型的时候使用了 pyStan 这个开源工具,因此能够在较快的时间内得到需要预测的结果。除此之外,为了方便统计学家,机器学习从业者等人群的使用,prophet 同时提供了 R 语言和 Python 语言的接口。从整体的介绍来看,如果是一般的商业分析或者数据分析的需求,都可以尝试使用这个开源算法来预测未来时间序列的走势。

Prophet 的算法原理

Prophet 数据的输入和输出

prophetexample1

首先让我们来看一个常见的时间序列场景,黑色表示原始的时间序列离散点,深蓝色的线表示使用时间序列来拟合所得到的取值,而浅蓝色的线表示时间序列的一个置信区间,也就是所谓的合理的上界和下界。prophet 所做的事情就是:

  1. 输入已知的时间序列的时间戳和相应的值;
  2. 输入需要预测的时间序列的长度;
  3. 输出未来的时间序列走势。
  4. 输出结果可以提供必要的统计指标,包括拟合曲线,上界和下界等。

就一般情况而言,时间序列的离线存储格式为时间戳和值这种格式,更多的话可以提供时间序列的 ID,标签等内容。因此,离线存储的时间序列通常都是以下的形式。其中 date 指的是具体的时间戳,category 指的是某条特定的时间序列 id,value 指的是在 date 下这个 category 时间序列的取值,label 指的是人工标记的标签(’0′ 表示异常,’1‘ 表示正常,’unknown’ 表示没有标记或者人工判断不清)。

prophetexample2.png

而 fbprophet 所需要的时间序列也是这种格式的,根据官网的描述,只要用 csv 文件存储两列即可,第一列的名字是 ‘ds’, 第二列的名称是 ‘y’。第一列表示时间序列的时间戳,第二列表示时间序列的取值。通过 prophet 的计算,可以计算出 yhat,yhat_lower,yhat_upper,分别表示时间序列的预测值,预测值的下界,预测值的上界。两份表格如下面的两幅图表示。

prophetexample3

prophetexample4

Prophet 的算法实现

在时间序列分析领域,有一种常见的分析方法叫做时间序列的分解(Decomposition of Time Series),它把时间序列 y_{t} 分成几个部分,分别是季节项 S_{t},趋势项 T_{t},剩余项 R_{t}。也就是说对所有的 t\geq 0,都有

y_{t} = S_{t} + T_{t} + R_{t}.

除了加法的形式,还有乘法的形式,也就是:

y_{t} = S_{t} \times T_{t} \times R_{t}.

以上式子等价于 \ln y_{t} = \ln S_{t} + \ln T_{t} + \ln R_{t}。所以,有的时候在预测模型的时候,会先取对数,然后再进行时间序列的分解,就能得到乘法的形式。在 fbprophet 算法中,作者们基于这种方法进行了必要的改进和优化。

一般来说,在实际生活和生产环节中,除了季节项,趋势项,剩余项之外,通常还有节假日的效应。所以,在 prophet 算法里面,作者同时考虑了以上四项,也就是:

y(t) = g(t) + s(t) + h(t) + \epsilon_{t}.

其中 g(t) 表示趋势项,它表示时间序列在非周期上面的变化趋势;s(t) 表示周期项,或者称为季节项,一般来说是以周或者年为单位;h(t) 表示节假日项,表示在当天是否存在节假日;\epsilon_{t} 表示误差项或者称为剩余项。Prophet 算法就是通过拟合这几项,然后最后把它们累加起来就得到了时间序列的预测值。

趋势项模型 g(t)

在 Prophet 算法里面,趋势项有两个重要的函数,一个是基于逻辑回归函数(logistic function)的,另一个是基于分段线性函数(piecewise linear function)的。

首先,我们来介绍一下基于逻辑回归的趋势项是怎么做的。

如果回顾逻辑回归函数的话,一般都会想起这样的形式:\sigma(x) = 1/(1+e^{-x}), 它的导数是 \sigma'(x) = \sigma(x) \cdot(1-\sigma(x)), 并且 \lim_{x\rightarrow +\infty} \sigma(x) = 1, \lim_{x\rightarrow -\infty} \sigma(x) = 0. 如果增加一些参数的话,那么逻辑回归就可以改写成:

f(x) = C / (1 + e^{-k(x-m)}),

这里的 C 称为曲线的最大渐近值,k 表示曲线的增长率,m 表示曲线的中点。当 C=1, k = 1, m =0 时,恰好就是大家常见的 sigmoid 函数的形式。从 sigmoid 的函数表达式来看,它满足以下的微分方程:y'=y(1-y)

那么,如果使用分离变量法来求解微分方程 y'=y(1-y) 就可以得到:

\frac{y'}{y} + \frac{y'}{1-y} = 1 \Rightarrow \ln\frac{y}{1-y} = 1 \Rightarrow y = 1/(1+K e^{-x}).

但是在现实环境中,函数 f(x) = C / (1+e^{-k(x-m)}) 的三个参数 C, k, m 不可能都是常数,而很有可能是随着时间的迁移而变化的,因此,在 Prophet 里面,作者考虑把这三个参数全部换成了随着时间而变化的函数,也就是 C = C(t), k = k(t), m = m(t)

除此之外,在现实的时间序列中,曲线的走势肯定不会一直保持不变,在某些特定的时候或者有着某种潜在的周期曲线会发生变化,这种时候,就有学者会去研究变点检测,也就是所谓 change point detection。例如下面的这幅图的 t_{1}^{*}, t_{2}^{*} 就是时间序列的两个变点。

prophetchangepoint1

在 Prophet 里面,是需要设置变点的位置的,而每一段的趋势和走势也是会根据变点的情况而改变的。在程序里面有两种方法,一种是通过人工指定的方式指定变点的位置;另外一种是通过算法来自动选择。在默认的函数里面,Prophet 会选择 n_changepoints = 25 个变点,然后设置变点的范围是前 80%(changepoint_range),也就是在时间序列的前 80% 的区间内会设置变点。通过 forecaster.py 里面的 set_changepoints 函数可以知道,首先要看一些边界条件是否合理,例如时间序列的点数是否少于 n_changepoints 等内容;其次如果边界条件符合,那变点的位置就是均匀分布的,这一点可以通过 np.linspace 这个函数看出来。

下面假设已经放置了 S 个变点了,并且变点的位置是在时间戳 s_{j}, 1\leq j\leq S 上,那么在这些时间戳上,我们就需要给出增长率的变化,也就是在时间戳 s_{j} 上发生的 change in rate。可以假设有这样一个向量:\boldsymbol{\delta}\in\mathbb{R}^{S}, 其中 \delta_{j} 表示在时间戳 s_{j} 上的增长率的变化量。如果一开始的增长率我们使用 k 来代替的话,那么在时间戳 t 上的增长率就是 k + \sum_{j:t>s_{j}} \delta_{j},通过一个指示函数 \mathbf{a}(t)\in \{0,1\}^{S} 就是

a_{j}(t) = \begin{cases} 1, \text{ if } t\geq s_{j},\\ 0, \text{ otherwise.} \end{cases}

那么在时间戳 t 上面的增长率就是 k + \mathbf{a}^{T}\boldsymbol{\delta}. 一旦变化量 k 确定了,另外一个参数 m 也要随之确定。在这里需要把线段的边界处理好,因此通过数学计算可以得到:

\gamma_{j} = \bigg(s_{j} - m - \sum_{\ell <j} \gamma_{\ell} \bigg) \cdot \bigg( 1- \frac{k + \sum_{\ell < j} \delta_{\ell}}{k + \sum_{\ell\leq j}\delta_{\ell}} \bigg).

所以,分段的逻辑回归增长模型就是:

g(t) = \frac{C(t)}{1+exp(-(k+\boldsymbol{a}(t)^{t}\boldsymbol{\delta}) \cdot (t - (m+\boldsymbol{a}(t)^{T}\boldsymbol{\gamma})},

其中,

\boldsymbol{a}(t) = (a_{1}(t),\cdots,a_{S}(t))^{T},  \boldsymbol{\delta} = (\delta_{1},\cdots,\delta_{S})^{T}, \boldsymbol{\gamma} = (\gamma_{1},\cdots,\gamma_{S})^{T}.

在逻辑回归函数里面,有一个参数是需要提前设置的,那就是 Capacity,也就是所谓的 C(t) ,在使用 Prophet 的 growth = ‘logistic’ 的时候,需要提前设置好 C(t) 的取值才行。

再次,我们来介绍一下基于分段线性函数的趋势项是怎么做的。众所周知,线性函数指的是 y=kx+b, 而分段线性函数指的是在每一个子区间上,函数都是线性函数,但是在整段区间上,函数并不完全是线性的。正如下图所示,分段线性函数就是一个折线的形状。

prophetpiecewiselinear1

因此,基于分段线性函数的模型形如:

g(t)=(k+\boldsymbol{a}(t)\boldsymbol{\delta})\cdot t+(m+\boldsymbol{a}(t)^{T}\boldsymbol{\gamma}),

其中 k 表示增长率(growth rate),\boldsymbol{\delta} 表示增长率的变化量,m 表示 offset parameter。而这两种方法(分段线性函数与逻辑回归函数)最大的区别就是 \boldsymbol{\gamma} 的设置不一样,在分段线性函数中,\boldsymbol{\gamma}=(\gamma_{1},\cdots,\gamma_{S})^{T}, \gamma_{j}=-s_{j}\delta_{j}. 注意:这与之前逻辑回归函数中的设置是不一样的。

在 prophet 的源代码中,forecast.py 这个函数里面包含了最关键的步骤,其中 piecewise_logistic 函数表示了前面所说的基于逻辑回归的增长函数,它的输入包含了 cap 这个指标,因此需要用户事先指定 capacity。而在 piecewise_linear 这个函数中,是不需要 capacity 这个指标的,因此 m = Prophet() 这个函数默认的使用 growth = ‘linear’ 这个增长函数,也可以写作 m = Prophet(growth = ‘linear’);如果想用 growth = ‘logistic’,就要这样写:

m = Prophet(growth='logistic')
df['cap'] = 6
m.fit(df)
future = m.make_future_dataframe(periods=prediction_length, freq='min')
future['cap'] = 6

变点的选择(Changepoint Selection)

在介绍变点之前,先要介绍一下 Laplace 分布,它的概率密度函数为:

f(x|\mu, b) = exp\bigg(-|x-\mu|/b\bigg)/2b,

其中 \mu 表示位置参数,b>0 表示尺度参数。Laplace 分布与正态分布有一定的差异。

在 Prophet 算法中,是需要给出变点的位置,个数,以及增长的变化率的。因此,有三个比较重要的指标,那就是

  1. changepoint_range,
  2. n_changepoint,
  3. changepoint_prior_scale。

changepoint_range 指的是百分比,需要在前 changepoint_range 那么长的时间序列中设置变点,在默认的函数中是 changepoint_range = 0.8。n_changepoint 表示变点的个数,在默认的函数中是 n_changepoint = 25。changepoint_prior_scale 表示变点增长率的分布情况,在论文中, \delta_{j} \sim Laplace(0,\tau),这里的 \tau 就是 change_point_scale。

在整个开源框架里面,在默认的场景下,变点的选择是基于时间序列的前 80% 的历史数据,然后通过等分的方法找到 25 个变点(change points),而变点的增长率是满足 Laplace 分布 \delta_{j} \sim Laplace (0,0.05) 的。因此,当 \tau 趋近于零的时候,\delta_{j} 也是趋向于零的,此时的增长函数将变成全段的逻辑回归函数或者线性函数。这一点从 g(t) 的定义可以轻易地看出。

对未来的预估(Trend Forecast Uncertainty)

从历史上长度为 T 的数据中,我们可以选择出 S 个变点,它们所对应的增长率的变化量是 \delta_{j} \sim Laplace(0,\tau)。此时我们需要预测未来,因此也需要设置相应的变点的位置,从代码中看,在 forecaster.py 的 sample_predictive_trend 函数中,通过 Poisson 分布等概率分布方法找到新增的 changepoint_ts_new 的位置,然后与 changepoint_t 拼接在一起就得到了整段序列的 changepoint_ts。

changepoint_ts_new = 1 + np.random.rand(n_changes) * (T - 1)
changepoint_ts = np.concatenate((self.changepoints_t, changepoint_ts_new))

第一行代码的 1 保证了 changepoint_ts_new 里面的元素都大于 change_ts 里面的元素。除了变点的位置之外,也需要考虑 \delta 的情况。这里令 \lambda = \sum_{j=1}^{S}|\delta_{j}|/S,于是新的增长率的变化量就是按照下面的规则来选择的:当 j>T 时,

\delta_{j}=\begin{cases} 0 \text{, with probability } (T-S)/T \\ \sim Laplace(0,\lambda) \text{, with probability } S/T \end{cases}.

季节性趋势

几乎所有的时间序列预测模型都会考虑这个因素,因为时间序列通常会随着天,周,月,年等季节性的变化而呈现季节性的变化,也称为周期性的变化。对于周期函数而言,大家能够马上联想到的就是正弦余弦函数。而在数学分析中,区间内的周期性函数是可以通过正弦和余弦的函数来表示的:假设 f(x) 是以 2\pi 为周期的函数,那么它的傅立叶级数就是 a_{0} + \sum_{n=1}^{\infty}(a_{n}\cos(nx) + b_{n}\sin(nx))

在论文中,作者使用傅立叶级数来模拟时间序列的周期性。假设 P 表示时间序列的周期,P = 365.25 表示以年为周期,P = 7 表示以周为周期。它的傅立叶级数的形式都是:

s(t) = \sum_{n=1}^{N}\bigg( a_{n}\cos\bigg(\frac{2\pi n t}{P}\bigg) + b_{n}\sin\bigg(\frac{2\pi n t}{P}\bigg)\bigg).

就作者的经验而言,对于以年为周期的序列(P = 365.25)而言,N = 10;对于以周为周期的序列(P = 7 )而言,N = 3。这里的参数可以形成列向量:

\boldsymbol{\beta} = (a_{1},b_{1},\cdots,a_{N},b_{N})^{T}

N = 10 时,

X(t) = \bigg[\cos(\frac{2\pi(1)t}{365.25}),\cdots,\sin(\frac{2\pi(10)t}{365.25})\bigg]

N = 3 时,

X(t) = \bigg[\cos(\frac{2\pi(1)t}{7}),\cdots,\sin(\frac{2\pi(3)t}{7})\bigg]

因此,时间序列的季节项就是:s(t) = X(t) \boldsymbol{\beta},\boldsymbol{\beta} 的初始化是 \boldsymbol{\beta} \sim Normal(0,\sigma^{2})。这里的 \sigma 是通过 seasonality_prior_scale 来控制的,也就是说 \sigma= seasonality_prior_scale。这个值越大,表示季节的效应越明显;这个值越小,表示季节的效应越不明显。同时,在代码里面,seasonality_mode 也对应着两种模式,分别是加法和乘法,默认是加法的形式。在开源代码中,X(t) 函数是通过 fourier_series 来构建的。

节假日效应(holidays and events)

在现实环境中,除了周末,同样有很多节假日,而且不同的国家有着不同的假期。在 Prophet 里面,通过维基百科里面对各个国家的节假日的描述,hdays.py 收集了各个国家的特殊节假日。除了节假日之外,用户还可以根据自身的情况来设置必要的假期,例如 The Super Bowl,双十一等。

prophetholiday1.png

由于每个节假日对时间序列的影响程度不一样,例如春节,国庆节则是七天的假期,对于劳动节等假期来说则假日较短。因此,不同的节假日可以看成相互独立的模型,并且可以为不同的节假日设置不同的前后窗口值,表示该节假日会影响前后一段时间的时间序列。用数学语言来说,对与第 i 个节假日来说, D_{i} 表示该节假日的前后一段时间。为了表示节假日效应,我们需要一个相应的指示函数(indicator function),同时需要一个参数 \kappa_{i} 来表示节假日的影响范围。假设我们有 L 个节假日,那么

h(t)=Z(t) \boldsymbol{\kappa}=\sum_{i=1}^{L} \kappa_{i}\cdot 1_{\{t\in D_{i}\}},

其中 Z(t)=(1_{\{t\in D_{1}\}},\cdots,1_{\{t\in D_{L}\}})\boldsymbol{\kappa}=(\kappa_{1},\cdots,\kappa_{L})^{T}.

其中 \boldsymbol{\kappa}\sim Normal(0,v^{2}) 并且该正态分布是受到 v = holidays_prior_scale 这个指标影响的。默认值是 10,当值越大时,表示节假日对模型的影响越大;当值越小时,表示节假日对模型的效果越小。用户可以根据自己的情况自行调整。

模型拟合(Model Fitting)

按照以上的解释,我们的时间序列已经可以通过增长项,季节项,节假日项来构建了,i.e.

y(t)=g(t)+s(t)+h(t)+\epsilon

下一步我们只需要拟合函数就可以了,在 Prophet 里面,作者使用了 pyStan 这个开源工具中的 L-BFGS 方法来进行函数的拟合。具体可以参考 forecast.py 里面的 stan_init 函数。

Prophet 中可以设置的参数

在 Prophet 中,用户一般可以设置以下四种参数:

  1. Capacity:在增量函数是逻辑回归函数的时候,需要设置的容量值。
  2. Change Points:可以通过 n_changepoints 和 changepoint_range 来进行等距的变点设置,也可以通过人工设置的方式来指定时间序列的变点。
  3. 季节性和节假日:可以根据实际的业务需求来指定相应的节假日。
  4. 光滑参数:\tau= changepoint_prior_scale 可以用来控制趋势的灵活度,\sigma= seasonality_prior_scale 用来控制季节项的灵活度,v= holidays prior scale 用来控制节假日的灵活度。

如果不想设置的话,使用 Prophet 默认的参数即可。

 

Prophet 的实际使用

Prophet 的简单使用

因为 Prophet 所需要的两列名称是 ‘ds’ 和 ‘y’,其中,’ds’ 表示时间戳,’y’ 表示时间序列的值,因此通常来说都需要修改 pd.dataframe 的列名字。如果原来的两列名字是 ‘timestamp’ 和 ‘value’ 的话,只需要这样写:

df = df.rename(columns={'timestamp':'ds', 'value':'y'})

如果 ‘timestamp’ 是使用 unixtime 来记录的,需要修改成 YYYY-MM-DD hh:mm:ss 的形式:

df['ds'] = pd.to_datetime(df['ds'],unit='s')

在一般情况下,时间序列需要进行归一化的操作,而 pd.dataframe 的归一化操作也十分简单:

df['y'] = (df['y'] - df['y'].mean()) / (df['y'].std())

然后就可以初始化模型,然后拟合模型,并且进行时间序列的预测了。

初始化模型:m = Prophet()
拟合模型:m.fit(df)
计算预测值:periods 表示需要预测的点数,freq 表示时间序列的频率。
future = m.make_future_dataframe(periods=30, freq='min')
future.tail()
forecast = m.predict(future)

而 freq 指的是 pd.dataframe 里面的一个指标,’min’ 表示按分钟来收集的时间序列。具体参见文档:http://pandas.pydata.org/pandas-docs/stable/timeseries.html#offset-aliases

prophetdataframefrequency

在进行了预测操作之后,通常都希望把时间序列的预测趋势画出来:

画出预测图:
m.plot(forecast)
画出时间序列的分量:
m.plot_components(forecast)

prophetexample5prophetexample6

如果要画出更详细的指标,例如中间线,上下界,那么可以这样写:

x1 = forecast['ds']
y1 = forecast['yhat']
y2 = forecast['yhat_lower']
y3 = forecast['yhat_upper']
plt.plot(x1,y1)
plt.plot(x1,y2)
plt.plot(x1,y3)
plt.show()

prophetexample7

其实 Prophet 预测的结果都放在了变量 forecast 里面,打印结果的话可以这样写:第一行是打印所有时间戳的预测结果,第二行是打印最后五个时间戳的预测结果。

print(forecast[['ds', 'yhat', 'yhat_lower', 'yhat_upper']])
print(forecast[['ds', 'yhat', 'yhat_lower', 'yhat_upper']].tail())

 

Prophet 的参数设置

Prophet 的默认参数可以在 forecaster.py 中看到:

def __init__(
    self,
    growth='linear',
    changepoints=None,
    n_changepoints=25, 
    changepoint_range=0.8,
    yearly_seasonality='auto',
    weekly_seasonality='auto',
    daily_seasonality='auto',
    holidays=None,
    seasonality_mode='additive',
    seasonality_prior_scale=10.0,
    holidays_prior_scale=10.0,
    changepoint_prior_scale=0.05,
    mcmc_samples=0,
    interval_width=0.80,
    uncertainty_samples=1000,
):

增长函数的设置

在 Prophet 里面,有两个增长函数,分别是分段线性函数(linear)和逻辑回归函数(logistic)。而 m = Prophet() 默认使用的是分段线性函数(linear),并且如果要是用逻辑回归函数的时候,需要设置 capacity 的值,i.e. df[‘cap’] = 100,否则会出错。

m = Prophet()
m = Prophet(growth='linear')
m = Prophet(growth='logistic')

变点的设置

在 Prophet 里面,变点默认的选择方法是前 80% 的点中等距选择 25 个点作为变点,也可以通过以下方法来自行设置变点,甚至可以人为设置某些点。

m = Prophet(n_changepoints=25)
m = Prophet(changepoint_range=0.8)
m = Prophet(changepoint_prior_scale=0.05)
m = Prophet(changepoints=['2014-01-01'])

而变点的作图可以使用:

from fbprophet.plot import add_changepoints_to_plot
fig = m.plot(forecast)
a = add_changepoints_to_plot(fig.gca(), m, forecast)

prophetexample8

周期性的设置

通常来说,可以在 Prophet 里面设置周期性,无论是按月还是周其实都是可以设置的,例如:

m = Prophet(weekly_seasonality=False)
m.add_seasonality(name='monthly', period=30.5, fourier_order=5)
m = Prophet(weekly_seasonality=True)
m.add_seasonality(name='weekly', period=7, fourier_order=3, prior_scale=0.1)

prophetexample9

节假日的设置

有的时候,由于双十一或者一些特殊节假日,我们可以设置某些天数是节假日,并且设置它的前后影响范围,也就是 lower_window 和 upper_window。

playoffs = pd.DataFrame({
  'holiday': 'playoff',
  'ds': pd.to_datetime(['2008-01-13', '2009-01-03', '2010-01-16',
                        '2010-01-24', '2010-02-07', '2011-01-08',
                        '2013-01-12', '2014-01-12', '2014-01-19',
                        '2014-02-02', '2015-01-11', '2016-01-17',
                        '2016-01-24', '2016-02-07']),
  'lower_window': 0,
  'upper_window': 1,
})
superbowls = pd.DataFrame({
  'holiday': 'superbowl',
  'ds': pd.to_datetime(['2010-02-07', '2014-02-02', '2016-02-07']),
  'lower_window': 0,
  'upper_window': 1,
})
holidays = pd.concat((playoffs, superbowls))

m = Prophet(holidays=holidays, holidays_prior_scale=10.0)

 

结束语

对于商业分析等领域的时间序列,Prophet 可以进行很好的拟合和预测,但是对于一些周期性或者趋势性不是很强的时间序列,用 Prophet 可能就不合适了。但是,Prophet 提供了一种时序预测的方法,在用户不是很懂时间序列的前提下都可以使用这个工具得到一个能接受的结果。具体是否用 Prophet 则需要根据具体的时间序列来确定。

参考文献:

  1. https://otexts.org/fpp2/components.html
  2. https://en.wikipedia.org/wiki/Decomposition_of_time_series
  3. A review of change point detection methods, CTruong, L. Oudre, N.Vayatis
  4. https://github.com/facebook/prophet
  5. https://facebook.github.io/prophet/

 

一篇关于时间序列异常检测的论文

近期阅读了一篇论文《Rapid Deployment of Anomaly Detection Models for Large Number of Emerging KPI Streams》,这篇文章基于之前的 ROCKA 系统做了一些额外的工作。ROCKA 系统是用来做时间序列的实时聚类的,而这篇文章是在 ROCKA 系统的基础上增加了时间序列异常检测的功能。通常来说,时间序列异常检测可以使用有监督的方法来解决,参考 Opperentice 系统。而本篇文章使用了半监督学习的思路来解决异常检测的问题,下面来详细分析一下这篇文章的细节,本文的作者把这个系统称为 ADS(Anomaly Detection through Self-training)。

数据集的情况

在论文中,作者使用了两份数据集,分别是已经历史上的 70 条时间序列,另外还有新来的 81 条时间序列。在 ADS 系统中,历史上的 70 条时间序列被划分成 5 类,并且已经可以找出每个类的质心位置,并且每条历史上的时间序列通常来说会大于三个星期(3 weeks)。本篇论文的评价指标是 F-Score,也属于机器学习领域里面比较常用的衡量模型效果的指标。整体来看,这篇文章的数据集大约是 200 条时间序列,时间序列的时间间隔通常来说是五分钟(不过其余的运维场景会有一分钟的数据采集粒度),而一般来说都拥有大半年甚至一年的时间跨度。那么时间点的个数预估是 200 * (1440 / 5) * 365。假设异常的数据:正常的数据 = 1:10000(也就是说平均每条时间序列每周至少发生一次异常),于是这批时间序列数据的异常数据量大约是 200 * (1440 / 5) * 365 / 10000 = 2102,也就是说异常的样本大约是 2102 个左右,剩下的都是正常的样本。PS:当然如果异常的数据:正常的数据的比例大于 1:10000 的话,异常的样本还会更多一些。整体来看,时间序列异常检测是一个样本极其不均衡的场景。

ADS 的系统架构

按照作者之前论文的经验,时间序列异常检测通常都是先做聚类,然后再根据每一个类的特点来做一个异常检测模型,之前的技术架构就是 ROCKA + Opperentice。因为 ROCKA 可以根据时间序列的走势和趋势来进行时间序列的实时分类/聚类,然后 Opperentice 就是做时间序列异常检测的模型。在本文的场景下,作者把 70 条时间序列分成了5 类,因此只需要维护 5 个时间序列的异常检测模型就可以了。当然把时间序列切分成更多的类也是可以的,只是需要维护的时间序列异常检测就变多了,人工成本会加大。

ADS系统架构
ADS 的系统架构
ROCKA系统架构
ROCKA 的系统架构

如果看到上面两幅图,有心的读者一定会发现其实 ADS 就是基于 ROCKA 所做的工作。ADS 先对时间序列进行了分类,然后进行了特征提取的工作,再通过半监督学习模型,最后进行异常检测。也就是说,ADS 会走下面四个步骤:

  1. ADS 先把历史上的时间序列进行聚类;
  2. 通过算法获得每一个类的质心,并且标记出质心曲线的异常点和正常点;
  3. 对新来的时间序列进行实时聚类,划分到合适的类别;
  4. 基于新来的时间序列(没有标记)和历史上的时间序列(有标记)使用无监督算法来重新训练一个新的模型,进行该类别的时间序列异常检测。

ADS 的细节

对于时间序列的聚类框架 ROCKA,之前的一篇 BLOG 里面已经详细介绍过,这里将不会再赘述。而 ADS 的另一个模块就是半监督学习算法 Contrastive Pessimistic Likelihood Estimation(CPLE),详细的论文细节可以参考论文《Contrastive Pessimistic Likelihood Estimation for Semi-Supervised Classification》。CPLE 有几个好处:

  1. CPLE 是半监督学习算法中比较健壮的,因为它并没有过多的假设条件,并且也符合这篇文章的业务场景,同时拥有质心曲线(有标记)和新来的曲线(无标记),使用半监督学习也是符合常理的。除了 CPLE,其实在实战过程中也可以多尝试其他的半监督模型,具体可以参考周志华的《机器学习》。
  2. CPLE 的复杂度比较低,计算快。
  3. CPLE 支持增量学习,因此,当越来越多新的时间序列进入 ADS,这个模型也会随之而调整并提高准确率。

整体来看,ADS = ROCKA + CPLE,而在论文中,它的对比模型就是 ROCKA + Opperentice。而且在 CPLE 中,也使用了与 Opperentice 系统类似的特征,如下图所示。

ADS特征
特征工程

其实,从本质上来看,就是半监督学习与有监督学习在这份数据集合上面的比较。从这篇论文里面所展示的数据来看,CPLE 有一定的优势。

ADS效果对比1
Average best F-scores of ADS, iForest, Donut, Opperentice, ROCKA + Opperentice
ADS效果对比2
The New KPI Streams

整体来看,本篇文章介绍了时间序列异常检测的一种方案,也就是把时间序列先进行聚类的操作,然后根据不同的类来进行异常检测。在异常检测的方法中,不仅可以使用 Random Forest,GBDT,XGBoost 等有监督学习方法,也可以使用 CPLE 等半监督算法。具体在业务中如何使用,其实只能够根据具体的数据来进行合理地选择了。

 

两篇关于时间序列的论文

这次整理的就是清华大学裴丹教授所著的两篇与时间序列相关的论文。一篇是关于时间序列聚类的,《Robust and Rapid Clustering of KPIs for Large-Scale Anomaly Detection》;另外一篇文章是关于时间序列异常检测的,重点检测时间序列上下平移的,《Robust and Rapid Adaption for Concept Drift in Software System Anomaly Detection》。本文将会整理一下这两篇文章的关键技术点。

Robust and Rapid Clustering of KPIs for Large-Scale Anomaly Detection

在互联网公司中,通常会拥有海量的的时间序列,而海量的时间序列就有着各种各样的形状和走势。因此,就有学者提出可以先对时间序列进行分类,然后根据不同的类使用不同的检测模型来进行异常检测。如果要做时间序列的分类,就先需要做聚类的操作,无论从 KMeans,DBSCAN,还是层次聚类来说,都会消耗一定的运算时间。所以,如何在较短的时间内进行聚类或者分类的操作则是这个系统的关键之处。于是,这篇文章提出了一个将时间序列快速聚类的方法。

时间序列 -> 时间序列分类

-> 根据每一类时间序列使用不同的异常检测模型

而在做时间序列聚类的时候,也有着不少的挑战。通常挑战来自于以下几点:

  1. 形状:通常来说,时间序列随着业务的变化,节假日效应,变更的发布,将会随着时间的迁移而造成形状的变化。
  2. 噪声:无论是从数据采集的角度,还是系统处理的角度,甚至服务器的角度,都有可能给时间序列带来一定的噪声数据,而噪声是需要处理掉的。
  3. 平移:在定时任务中,有可能由于系统或者人为的原因,时间序列的走势可能会出现一定程度的左右偏移,有可能每天 5:00 起的定时任务由于前序任务的原因而推迟了。
  4. 振幅:通常时间序列都存在一条基线,而不同的时间序列有着不同的振幅,振幅决定了这条时间序列的振荡程度,而振幅或者基线其实也是会随着时间的迁移而变化的。

从整篇论文来看,ROCKA 系统是为了做实时的时间序列分类判断的。要想做成实时的分类判断,就需要有离线和在线两个模块。其中离线是为了做模型训练或者聚类的,在线是为了使用离线处理好的模块来做曲线分类的。

ROCKA系统架构
ROCKA系统架构

从整个系统来看,离线模块需要做以下几件事情:首先需要收集一批时间序列数据,也就是所谓的 Raw Time Series Data(Raw),通过预处理模块,实施基线提取,再进行聚类的操作,获得相应的聚类结果和质心。在线模块同样也要做类似的事情:首先对于每一条新来的时间序列数据,也就是所谓的 New Time Series Data(Raw),通过预处理模块,实施基线提取,然后使用已经聚类好的离线模块来进行实时的分类。

下面,我们来逐一分析每个模块的作用。

预处理模块(Preprocessing)

通常预处理模块包含几个关键点:

  1. 缺失值:缺失值指的是在该上报数据的时间戳上并没有相应的数据上报,数据处于缺失的状态。通常的办法就是把数据补齐,而数据补齐的方法有很多种,最简单的就是使用线性插值(Linear Interpolation)的方式来补齐。
  2. 标准化:对于一个时间序列而言,有可能它的均值是10万,有可能只有10,但是它们的走势有可能都是一样的。所以在这个时候需要进行归一化的操作。最常见的有两种归一化方法:一种是标准化,另外一种是最大最小值归一化。如果 [x_{1},x_{2}, \cdots, x_{n}] 表示原始的时间序列的话,标准化指的是 \hat{x}_{i} = (x_{i} -\mu) /\sigma,其中 \mu\sigma 分别表示均值和标准差。最大最小值归一化指的是 \hat{x}_{i} = (x_{i} - \min) / (\max - \min),其中 \max, \min 分别表示这段时间内的最大值与最小值。

基线提取模块(Baseline Extraction)

基线提取指的是把时间序列分成基线和剩余项两个部分,假设时间序列是 [x_{1},x_{2},\cdots,x_{n}],基线提取就是:

x_{i} = baseline_{i} + residual_{i},

其中 baseline_{i}, residual_{i} 分别指的是 x_{i} 的基线和剩余项。

在处理基线的时候,有几件事情需要注意:

  1. 异常值的处理:通常需要移除一些明显异常的值,然后使用线性插值等方法来把这些移除的值补上。
  2. 使用简单的移动平均算法加上一个窗口值 w 来提取基线。假设时间序列是 [x_{1},\cdots,x_{n}]SMA_{i} = \sum_{j=i-w+1}^{i} x_{j} / wR_{i} = x_{i} - SMA_{i}。也就是说 x_{i} = SMA_{i} + R_{i}
  3. 提取基线的方式其实还有很多,使用带权重的移动平均算法(Weighted Moving Average),指数移动平均算法(Exponentially Weighted Moving Average)都可以提取基线,甚至使用深度学习中的 Autoencoder 或者 VAE 算法都能够提取基线。

基于密度的聚类算法(Clustering)

使用预处理和基线提取技术之后,可以得到原始时间序列的基线值,然后根据这些基线值来进行时间序列的聚类操作。一般来说,时间序列的聚类有两种方法:

  1. 通过特征工程的方法,从时间序列中提取出必要的时间序列特征,然后使用 KMeans 等算法来进行聚类。
  2. 通过相似度计算工具,对比两条时间序列之间的相似度,相似的聚成一类,不相似的就分成两类。

对于第一种方法而言,最重要的就是特征工程;对于第二种方法而言,最重要的是相似度函数的选择。在这篇文章中,作者选择了第二种方法来进行时间序列的聚类。对于两条时间序列 X = [x_{1},\cdots,x_{m}]Y = [y_{1},\cdots,y_{m}] 而言,为了解决左右平移的问题,需要考虑一个偏移量 |s|,然后计算它们之间的内积。

CC_{s}(X,Y) = \begin{cases}  \sum_{i=1}^{m-s}x_{s+i}\cdot y_{i}, \text{ where } s\geq 0, \\ \sum_{i=1}^{m+s}x_{i} \cdot y_{i-s} \text{ where } s<0.\end{cases}

通过这个偏移量 |s| 就可以计算出最大的相似度,然后计算出两条时间序列之间的距离。i.e.

NCC(X,Y) = \max_{s}\bigg(\frac{CC_{s}(X,Y)}{||X||_{2}\cdot||Y||_{2}}\bigg),

SBD(X,Y) = 1 - NCC(X,Y).

其中 NCC \in [-1,1] 指的是 Normalized version of Cross-Correlation,SBD \in [0,2] 指的是 Shape-based distance。

而聚类的另一个重要指标就是质心的选择,在这里,每个类的质心可以设置为:

\text{Centroid} = argmin_{X \in \text{cluster}_{i}} \sum_{Y \in \text{cluster}_{i}} SBD(X,Y)^{2}.

实时分类(Assignment)

对于一条新的时间序列(Raw Data),同样需要经过预处理,基线提取等步骤,然后计算它与之前每一个质心的距离。然后进行距离的从小到大排序,最小的那一类可能就是所需要的。当然,当最小距离大于某个 threshold ,就说明这条新的时间序列曲线很可能不属于之前的任何一类。通过人工查看之后,可以考虑新增一类,并且更新之前所做的聚类模型。

聚类与时间序列异常检测

如果要做海量的时间序列异常检测的话,通常有以下两种做法。

  1. 先对时间序列进行聚类或者分类,针对不同的时间序列类型来使用不同的模型;
  2. 在时间序列异常检测中加入分类特征。

对于第一种方法而言,需要针对不同形状的时间序列维护不同的模型,而且如果第一层的聚类/分类错误了,那么使用的模型也会出现错误。对于第二种方法而言,关键在于样本的积累和分类特征的构建。

Robust and Rapid Adaption for Concept Drift in Software System Anomaly Detection

这篇文章是关于时间序列异常检测的,而清华大学的 Netman 实验室做时间序列异常检测的相关工作比较多。从 2015 年开始的 Opperentice(Random Forest 模型),Funnel(SST 模型,变更相关),到后来的 Donut(VAE 模型),都是时间序列异常检测的相关文章。而这篇问题提到的 StepWise 系统针对的场景是关于指标的迁移的,所谓概念漂移(Concept Drift)指的就是时间序列会随着变更,发布,调度或者其他事件的发生而导致上下漂移或者左右漂移。一个比较典型的例子就是关于网络流量的漂移,通常来说在某个特点的时间点,时间序列会出现猛跌或者猛涨的情况,但是下跌或者上涨之后的走势和历史数据是及其相似的,只是绝对值上有所变化。

StepWiseExample.png
概念漂移的例子

正如上图所示,在时间戳 08-02 附近,时间序列出现了一个下跌的情况。但是根据历史数据所计算出来的上界(Upper Bound)和下界(Lower Bound)却会把未来一段时间的序列都判断为异常。但是前后的曲线走势却是一样的,其实只有下跌的那一小段时间应该被判断为异常,其他时间都是正常的。基于以上的业务场景,这篇文章的作者就提出了概念漂移(Concept Drift)的一些方法。

在整个 StepWise 系统背后,有两个比较关键的地方。其中第一个关键之处就是如何判断异常点。在这个业务场景下,需要检测的是上图发生暴跌的点。而暴跌或者暴涨只是业务运维用来描述时间序列的一个词语。在统计学领域,这种点通常称为变点(Change Point)。所以概念漂移的检测可以转化为一个变点检测的问题,正是论文里面写的。

StepWise系统架构
StepWise 的系统架构

Insight 1:Concept drift detection can be converted into a spike detection problem in the change score stream.

如果是进行变点检测的话,其实可以参考 2016 年的论文 Funnel:Assessing Software Changes in Web-based Services。里面使用了 Singular Spectrum Transform 来进行检测,并且使用 Difference in Difference 来判断时间序列是否真正出现了异常。关于 SST(Singular Spectrum Transform)的具体细节可以参考 Yasser Mohammad, Toyoaki Nishida 所撰写的 Robust Singular Spectrum Transform。SST 算法是基于 SVD 算法的,有一定的时间复杂度。而基于 SST 又有学者提出了 Robust SST,具体可以详见论文。而 StepWise 的其中两步就是 Detection 和 Classification,其中的 Detection 使用了 Improved SST,Classification 使用了Difference in Difference。而 Funnel 系统的其中两步也是 Improved SST 和 Difference in Difference,这与 Funnel 有异曲同工之妙,Funnel 系统详情请见下图。

Funnel系统架构
FUNNEL系统架构

而突变前后的时间序列可以分别叫做 Old Concept 和 New Concept,由于前后的走势几乎一致,所以本文的第二个关键点就是相似度的判断。

Insight 2:The relationship between new concept and old concept can be almost perfectly fitted by linear regression.

从数学的角度来讲,Insight 2 的陈述是想判断两条时间序列是否相似。假设 X=[x_{1},\cdots, x_{n}]Y = [y_{1},\cdots, y_{n}],那么以下陈述是等价的。

  1. 存在一个线性关系 y = kx 使得二维点集 \{(x_{i},y_{i}), 1\leq i\leq n\} 能够被很好的拟合好,也就是说此刻的方差较小。
  2. [x_{1},\cdots,x_{n}][y_{1},\cdots,y_{n}] 的 Pearson 系数很高;
  3. [x_{1},\cdots,x_{n}][y_{1},\cdots,y_{n}] 标准化(z-score)之后的曲线几乎一致。
  4. 分别存在两个值 \mu_{1},\mu_{2} 使得 [x_{1}/\mu_{1},\cdots,x_{n}/\mu_{1}][y_{1}/\mu_{2},\cdots,y_{n}/\mu_{2}] 几乎一致。

所以,在 StepWise 中,作者通过线性回归的算法来判断 old concept 与 new concept 是否存在线性关系,也就是说这两者是否只是平移的关系。其实也可以尝试上面所说的其余方法。

整体来看,StepWise 大致分成两个关键步骤。首先使用类似 Funnel 系统的思想,先进行异常检测(SST),再使用判断一下是不是因为软件的变更引起的(DID),最后使用一层过滤逻辑(线性拟合)来判断是否出现了概念漂移的情况。在实际使用过程中,无论是异常检测还是过滤逻辑,都需要根据具体的业务来做,很难找到一个固定的模型来解决所有的难题。

 

基于自编码器的时间序列异常检测算法

随着深度学习的发展,word2vec 等技术的兴起,无论是 NLP 中的词语,句子还是段落,都有着各种各样的嵌入形式,也就是把词语,句子,段落等内容转换成一个欧氏空间中的向量。然后使用机器学习的方法来进行文本的聚类和相似度的提取,甚至进行情感分类等操作。那么在表示学习(Representation Learning)方向上,除了刚刚提到的自然语言之外,语音,图像,甚至图论中的Graph都可以进行嵌入的操作,于是就有了各种各样的表示算法。既然提到了表示学习,或者特征提取的方法,而且在标注较少的情况下,各种无监督的特征提取算法就有着自己的用武之地。除了 NLP 中的 word2vec 之外,自编码器(Auto Encoder)也是一种无监督的数据压缩算法,或者说特征提取算法。本文将会从自编码器的基础内容出发,在时间序列的业务场景下,逐步展开基于自编码器的时间序列表示方法,并且最终如何应用与时间序列异常检测上。

自编码器

AutoEncoder3

提到自编码器(Auto Encoder),其实它就是一种数据压缩算法或者特征提取算法。自编码器包含两个部分,分别是编码层(encoder)和解码层(decoder),分别可以使用 \phi\psi 来表示,也就是说:

\phi: X\rightarrow F,

\psi: F\rightarrow X,

\phi,\psi = argmin_{\phi,\psi}||X-(\psi\circ\phi)X||^{2},

其目标函数就是为了拟合一个恒等函数。对于最简单的情况,可以令 X = \mathbb{R}^{n}, F=\mathbb{R}^{m},并且编码器和解码器都是前馈神经网络,也就是说:

z = f(Ax+c),

x'=g(Bx+d),

损失函数就是 L(x,x')=||x-x'||^{2} = ||x-g(Bf(Ax+c)+d)||^{2}, 其中 x\in X=\mathbb{R}^{n}, z\in F =\mathbb{R}^{m}. fg 分别是编码层和解码层的激活函数,A,cB,d 分别是编码层和解码层的矩阵和相应的向量。具体来说它们的矩阵大小分别是 A_{m\times n}, c_{m\times 1}, B_{n\times m}, d_{n\times 1}.

AutoEncoder2

对于自编码器而言,它的输入层的维度等于输出层的维度,隐藏层的维度是需要小于输入层的维度的。只有这样,自编码器才可以学习到数据分布的最显著特征。如果隐藏层的维度大于或者等于输入层的维度,其实是没有任何意义的,具体的解释可以参考下面这个Claim。

Claim. 对于自编码器而言,其中隐藏层的维度 m 一定是要小于输入层的维度 n 的。

Proof. 如果 n=m,那么令 A=B=I_{n}, c=d=0, f=g=id 就可以得到一个自编码器,而这个自编码器对于提取特征没有任何的意义。同理,当 m>n 时,A 是一个 m\times n 矩阵,B 是一个 n\times m 矩阵。从线性代数的角度来看,有无数个矩阵 A, B 满足 BA=I_{n}。这种情况下对于提取特征也是没有意义的。而当 m<n 时,其实无法找到矩阵 A,B 使得 BA=I_{n}. 如果存在 BA=I_{n}, 那么

n = rank(I_{n})=rank(BA) \leq \min\{rank(A),rank(B)\} \leq \min\{m,m\}=m.

这就导致了矛盾。因此,只有在 m<n 的情况下提取特征才是有意义的。

对于自编码器而言,其本质上也是一个神经网络,那么它的激活函数其实不仅可以选择 sigmoid, 还可以使用 tanh,ReLU,LeakyReLU 等其余激活函数,其本质上都是为了拟合一个恒等变换,中间层则作为一个特征提取的工具。在训练的时候,同样是使用反向传播算法,可以使用不同的优化函数,例如 SGD,Momentum,AdaGrad,RMSProp,Adam 等。

在图像领域,有学者尝试使用自编码器来进行图像的重构工作,图像的特征提取等内容,整体来看也能达到不错的效果,请看下图:

AutoEncoder1

从上图来看,基于均方误差的自编码器是无法重构出乒乓球的。由于该自编码器的容量有限,目标函数是均方误差,因此自编码器并没有意识到乒乓球是图片中的一个重要物品。

 

时间序列异常检测:

时间序列异常检测一直是学术界和工业界都关注的问题,无论使用传统的 Holt-Winters,ARIMA,还是有监督算法进行异常检测,都是统计学和传统机器学习的范畴。那么随着深度学习的兴起,是否存在某种深度学习算法来进行异常检测呢?其实是存在的。请看上图,左边一幅图有一个白色的小乒乓球,但是随着自编码器进行重构了之后,白色的小乒乓球已经在重构的图像中消失了。那么根据异常检测的观点来看,小乒乓球其实就可以作为图片中的异常点。只要在图片的局部,重构出来的图片和之前的图片存在着巨大的误差,那么原始图片上的点就有理由认为是异常点。

在这个思想下,针对时间序列异常检测而言,异常对于正常来说其实是少数。如果我们使用自编码器重构出来的时间序列跟之前有所差异的话,其实我们就有理由认为当前的时间序列存在了异常。其实,简单来看,基于自编码器的时间序列异常检测算法就是这样的:

原始时间序列

-> Auto Encoder(Encoder 和 Decoder)

-> 重构后的时间序列

-> 通过重构后的时间序列与原始时间序列的整体误差和局部误差来判断异常点

简单来说,只要输出的时间序列在局部的信息跟原始的时间序列不太一致,就有理由认为原始的时间序列存在着异常。

那么,首先我们需要提取时间序列中的一些子序列,例如我们可以提取今天(today),昨天(yesterday),一周前(week)的数据,基于同样的时间戳把它们重叠在一起,也就是下图这个形式。其中,蓝线表示一周前的数据,黑线表示昨天的数据,红色表示今天的数据。

AutoEncoder4

基于一条很长的时间序列,我们可以提取它的很多子序列,从而构造出很多的片段序列。这些片段序列就可以形成自编码器的输入数据,而自编码器是模拟一个恒等变换,因此它会把有异常的点尽量磨平,而正常的点则保持原样。所以,通过大量子片段来进行训练数据的输入,自编码器就能够得到一个较为合理的权重。得到了一个训练好的自编码器之后,对于任何一个子片段,都可以重构出一个新的片段。例如上面的子片段就可以重构成下图:对于今天的数据(today),那个凸起被直接抹平;对于昨天的数据(yesterday)而言,那个凹下去的部分也被磨平。基于时间序列重构前和重构后的数据差异,可以获得时间序列的异常点。

AutoEncoder5

除此之外,还有很多时间序列的异常点可以被自编码器(AutoEncoder)发现,例如下面四幅图,无论是上涨,还是下跌,其实都可以被自编码器(AutoEncoder)发现异常。

总结

通常来说,在时间序列异常检测场景中,异常的比例相对于正常的比例而言都是非常稀少的。因此,除了有监督算法(分类,回归)之外,基于无监督算法的异常检测算法也是必不可少的。除了 HoltWinters,ARIMA 等算法之外,本文尝试了一种新的异常检测算法,基于深度学习模型,利用自编码器的重构误差和局部误差,针对时间序列的异常检测的场景,初步达到了一个还不错的效果。这种方法可以用来提供部分异常样本,加大异常检测召回率的作用。但是这种方法也有一定的弊端:

  1. 从理论上说,它只能对一个时间序列单独训练一个模型,不同类型的时间序列需要使用不同的模型。这样的话,其实维护模型的成本比较高,不太适用于大规模的时间序列异常检测场景;
  2. 对周期型的曲线效果比较好,如果是毛刺型的数据,有可能就不太适用;因为长期的毛刺型数据就可以看成正常的数据了。
  3. 每次调参需要人为设置一定的阈值,不同的时间序列所需要的阈值是不一样的。

参考文献

  1. Unsupervised Anomaly Detection via Variational Auto-Encoder for Seasonal KPIs in Web Applications, Haowen XU, etc., 2018
  2. Deep Learning, Ian Goodfellow, etc., 2016
  3. https://zr9558.com/2016/06/12/replicator-neural-networks/

 

时间序列的自回归模型—从线性代数的角度来看

Fibonacci 序列

在开始讲解时间序列的自回归模型(AutoRegression Model)之前,我们需要先介绍一下线性代数的基础知识。为了介绍线性代数的基础知识,我们可以先看一个简单的例子。考虑整数序列 Fibonacci 序列,它的通项公式是一个递归函数,每项的取值是由前两项所生成的,其具体的公式就是

F_{n}=F_{n-1}+F_{n-2}

其初始值是 F_{0}=0, F_{1} = 1。按照其递归公式来计算,我们可以详细写出前面的几项,那就是:

0,1,1,2,3,5,8,13,21,34,55,89,144,…

但是,计算 Fibonacci 的通项公式则比计算等差数列和等比数列的通项公式复杂的多,因为这里需要使用线性代数的技巧才能解决这个问题。

求解 Fibonacci 序列的通项公式 --- 矩阵对角化

根据 Fibonacci 数列的递归公式,基于矩阵乘法的定义,Fibonacci 序列可以写成如下形式:

\left( \begin{array}{c} F_{n+2}  \\ F_{n+1}  \\ \end{array}\right)= \left( \begin{array}{cc} 1 & 1 \\ 1 & 0 \\ \end{array}\right) \left( \begin{array}{c} F_{n+1}  \\ F_{n}  \\ \end{array}\right) = A \left( \begin{array}{c} F_{n+1}  \\ F_{n}  \\ \end{array}\right),

\left( \begin{array}{c} F_{n}  \\ F_{n-1}  \\ \end{array}\right)= A \left( \begin{array}{c} F_{n-1}  \\ F_{n-2}  \\ \end{array}\right) = \cdots = A^{n-1} \left( \begin{array}{c} F_{1}  \\ F_{0}  \\ \end{array}\right).

这就意味着我们需要计算出矩阵 A 的幂。在线性代数里面,为了计算矩阵的 n 次方,除了通过矩阵乘法的公式直接计算之外,还有一个经典的技巧,那就是将矩阵对角化。详细来说,如果 m\times m 的矩阵 A 能够对角化,那就是存在可逆矩阵 P 使得

P^{-1}AP = diag(\lambda_{1},\cdots,\lambda_{m})

\implies AP = P diag(\lambda_{1},\cdots,\lambda_{m})

\implies A = P diag(\lambda_{1},\cdots,\lambda_{m})P^{-1}.

其中 D = diag(\lambda_{1},\cdots,\lambda_{m}) 表示一个 m\times m 的对角矩阵,其对角的元素从左上角到右下角依次是 \lambda_{1},\cdots,\lambda_{m}。如果把矩阵 P 写成列向量的形式,i.e. P =(\vec{\alpha}_{1},\cdots,\vec{\alpha}_{m}),那么以上的矩阵方程就可以转换为 A\vec{\alpha}_{i} = \lambda_{i}\vec{\alpha}_{i}, 1\leq i\leq m。进一步来说,如果要计算矩阵 A 的幂,就可以得到:

A^{k} = (PDP^{-1})\cdots(PDP^{-1}) = P D^{k} P^{-1}= P diag(\lambda_{1}^{k},\cdots,\lambda_{m}^{k})P^{-1}.

另外,如果想知道一个矩阵 A 的特征值和特征向量,则需要计算以下多项式的根,i.e. 计算关于 \lambda 的多项式的解,

det(\lambda I - A) = 0,

其中 I 是一个单位矩阵(identity matrix)。

按照以上的思路,如果令

A = \left( \begin{array}{cc} 1 & 1 \\ 1 & 0 \\ \end{array}\right),

可以计算出 A 的两个特征值分别是 \phi=(1+\sqrt{5})/2- \phi^{-1} = (1-\sqrt{5})/2,它们所对应的特征向量分别是:

\vec{\alpha}_{1} = (\phi,1)^{T}, \vec{\alpha}_{2} = (-\phi^{-1},1).

因此直接计算可以得到

F_{k} = \frac{1}{\sqrt{5}}\bigg(\frac{1+\sqrt{5}}{2}\bigg)^{k} - \frac{1}{\sqrt{5}}\bigg(\frac{1-\sqrt{5}}{2}\bigg)^{k}=\frac{\phi^{k}-(-\phi)^{-k}}{\sqrt{5}}.

通过上面的计算方法,为了计算 Fibonacci 数列的通项公式,我们可以先把它转换成一个矩阵求幂的问题,于是我们就能矩阵对角化的方法把 Fibonacci 数列的通项公式求出来。

时间序列的弱平稳性

要讲解自回归模型,就必须提到时间序列的弱平稳性。一个时间序列 \{x_{t}\}_{t\geq 0} 具有弱平稳性(Weak Stationary)指的是:

  1. E(x_{t}) 对于所有的 t\geq 0 都是恒定的;
  2. Var(x_{t}) 对于所有的 t\geq 0 都是恒定的;
  3. x_{t}x_{t-h} 的协方差对于所有的 t\geq 0 都是恒定的。

另外,时间序列的自相关方程(AutoCorrelation Function)指的是对于 h = 1,2,3,\cdots,可以定义 ACF 为

ACF(x_{t},x_{t-h}) = \frac{Covariance(x_{t},x_{t-h})}{\sqrt{Var(x_{t})\cdot Var(x_{t-h})}}.

如果时间序列 \{x_{t}\}_{t\geq 0} 在弱平稳性的假定下,ACF 将会简化为

ACF(x_{t},x_{t-h}) = \frac{Covariance(x_{t},x_{t-h})}{Var(x_{t})}.

时间序列的自回归模型(AutoRegression Model)

AR(1) 模型

AR(1) 模型指的是时间序列 \{x_{t}\}_{t\geq 0} 在时间戳 t 时刻的取值 x_{t} 与时间戳 t - 1 时刻的取值 x_{t-1} 相关,其公式就是:

x_{t}=\delta+\phi_{1}x_{t-1}+w_{t}

这个时间序列 \{x_{t}\}_{t\geq 0} 满足如下条件:

  1. w_{t}\sim N(0,\sigma_{w}^{2}),并且 w_{t} 满足 iid 条件。其中 N(0,\sigma_{w}^{2}) 表示 Gauss 正态分布,它的均值是0,方差是 \sigma_{w}^{2}
  2. w_{t}x_{t} 是相互独立的(independent)。
  3. x_{0},x_{1},\cdots弱平稳的,i.e. 必须满足 |\phi_{1}|<1

如果选择初始条件 x_{0}=1,则可以得到一些 AR(1) 模型的例子如下图所示:

AR Models

从 AR(1) 以上的定义出发,我们可以得到:

  1. E(x_{t}) = \delta/(1-\phi_{1}).
  2. Var(x_{t}) = \sigma_{w}^{2}/(1-\phi_{1}^{2}).
  3. Covariance(x_{t},x_{t-h}) = \phi_{1}^{h}.

Proof of 1. 从 AR(1) 的模型出发,可以得到

E(x_{t}) = E(\delta + \phi_{1}x_{t-1}+w_{t})  = \delta + \phi_{1}E(x_{t-1}) = \delta + \phi_{1}E(x_{t}),

从而,E(x_{t}) = \delta/(1-\phi_{1}).

Proof of 2. 从 AR(1) 的模型出发,可以得到

Var(x_{t}) = Var(\delta + \phi_{1}x_{t-1}+w_{t})

= \phi_{1}^{2}Var(x_{t-1}) +Var(w_{t}) = \phi_{1}^{2}Var(x_{t}) + \sigma_{w}^{2},

从而,Var(x_{t}) =\sigma_{w}^{2}/(1-\phi_{1}^{2}).

Proof of 3.\mu = E(x_{t}), \forall t\geq 0. 从 x_{t} 的定义出发,可以得到:

x_{t}-\mu = \phi_{1}(x_{t-1}-\mu)+w_{t}

= \phi_{1}^{h}(x_{t-h}-\mu) + \phi_{1}^{h-1}w_{t-h+1}+\cdots+\phi_{1}w_{t-1}+w_{t},

从而,

\rho_{h} = Covariance(x_{t},x_{t-h}) = \frac{E((x_{t}-\mu)\cdot(x_{t-h}-\mu))}{Var(x_{t})}=\phi_{1}^{h}.

AR(1) 模型与一维动力系统

特别的,如果假设 w_{t} 恒等于零,就可以得到 x_{t} =\delta + \phi_{1}x_{t-1} 对于所有的 t\geq 1 都成立。也就是可以写成一个一维函数的迭代公式:

f(x) = \phi_{1}x + \delta,

下面我们要计算 f^{n}(x) 的收敛性,这里的 f^{n}(x) = f\circ\cdots\circ f(x) 表示函数 fn 次迭代。

Method 1. 

通过 f(x) 的定义直接计算可以得到:

f^{n}(x) = \phi_{1}^{n}x+ \frac{1-\phi_{1}^{n}}{1-\phi_{1}}\delta,

n\rightarrow \infty,可以得到 f^{n}(x)\rightarrow \delta/(1-\phi_{1})。这与 E(x_{t}) = \delta/(1-\phi_{1}) 其实是保持一致的。

另外,如果 |\phi_{1}|>1,可以从公式上得到 f^{n}(x) \rightarrow \inftyn\rightarrow \infty

Method 2.

将原函数转换成 Lipschitz 函数的形式,i.e. 如果 |\phi_{1}|<1,那么

f(x)-\frac{\delta}{1-\phi_{1}} = \phi_{1}(x-\frac{\delta}{1-\phi_{1}})

\implies |f(x)-\frac{\delta}{1-\phi_{1}}| <\frac{1+|\phi_{1}|}{2}\cdot|x-\frac{\delta}{1-\phi_{1}}|

\implies |f^{n}(x)-\frac{\delta}{1-\phi_{1}}|<\bigg(\frac{1+|\phi_{1}|}{2}\bigg)^{n}\cdot|x-\frac{\delta}{1-\phi_{1}}|.

因为 (1+|\phi_{1}|)/2<1,我们可以得到 \lim_{n\rightarrow\infty}f^{n}(x)=\delta/(1-\phi_{1}). i.e. f^{n}(x) 趋近于 \delta/(1-\phi_{1}).

反之,如果 |\phi_{1}|>1,很容易得到

f(x)-\frac{\delta}{1-\phi_{1}} = \phi_{1}(x-\frac{\delta}{1-\phi_{1}})

\implies |f(x)-\frac{\delta}{1-\phi_{1}}| >\frac{1+|\phi_{1}|}{2}\cdot|x-\frac{\delta}{1-\phi_{1}}|

\implies |f^{n}(x)-\frac{\delta}{1-\phi_{1}}|>\bigg(\frac{1+|\phi_{1}|}{2}\bigg)^{n}\cdot|x-\frac{\delta}{1-\phi_{1}}|.

因此,在 |\phi_{1}|>1 这种条件下,f^{n}(x)\rightarrow \infty as n\rightarrow \infty. 特别地,对于一阶差分方程 x_{t} =\delta + \phi_{1}x_{t-1} 而言,如果 |\phi_{1}|>1,那么 x_{t} 的取值会越来越大,这与现实的状况不相符,所以在时间序列的研究中,一般都会假设 |\phi_{1}|<1

AR(p) 模型

按照之前类似的定义,可以把 AR(1) 模型扩充到 AR(p) 模型,也就是说:

1. AR(1) 模型形如:

x_{t}=\delta+\phi_{1}x_{t-1}+w_{t}.

2. AR(2) 模型形如:

x_{t} = \delta + \phi_{1}x_{t-1}+\phi_{2}x_{t-2}+w_{t}.

3. AR(p) 模型形如:

x_{t} = \delta + \phi_{1}x_{t-1}+\phi_{2}x_{t-2}+\cdots+\phi_{p}x_{t-p}+w_{t}.

AR(p) 模型的稳定性 --- 基于线性代数

对于 AR(2) 模型,可以假定 \delta = 0 并且忽略误差项,因此可以得到简化版的模型形如:

x_{t}= \phi_{1}x_{t-1} + \phi_{2}x_{t-2}.

写成矩阵的形式形如:

\left( \begin{array}{c} x_{t+2}  \\ x_{t+1}  \\ \end{array}\right)= \left( \begin{array}{cc} \phi_{1} & \phi_{2} \\ 1 & 0 \\ \end{array}\right) \left( \begin{array}{c} x_{t+1}  \\ x_{t}  \\ \end{array}\right) = A \left( \begin{array}{c} x_{t+1}  \\ x_{t}  \\ \end{array}\right).

求解其特征多项式则是基于 det(\lambda I - A) = 0,求解可以得到 \lambda^{2}-\phi_{1}\lambda - \phi_{2} =0,i.e. A^{k} = P diag(\lambda_{1}^{k}, \lambda_{2}^{k})P^{-1}。当 \lambda_{1}, \lambda_{2} 都在单位圆内部的时候,也就是该模型 x_{t+2} = \phi_{1}x_{t+1}+\phi_{2}x_{t} 满足稳定性的条件。

对于更加一般的 AR(p) 模型,也就是考虑 p 阶差分方程

x_{t} = \phi_{1}x_{t-1}+\phi_{2}x_{t-2}+\cdots+\phi_{p}x_{t-p}.

可以用同样的方法将其转换成矩阵的形式,那就是:

\left(\begin{array}{c} x_{t+p} \\ x_{t+p-1} \\ \vdots \\ x_{t+1}\\ \end{array}\right) = \left(\begin{array}{ccccc} \phi_{1} & \phi_{2} &\cdots & \phi_{p-1} & \phi_{p} \\ 1 & 0 & \cdots & 0 & 0 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & \cdots & 1 & 0 \\ \end{array}\right) \left(\begin{array}{c} x_{t+p-1} \\ x_{t+p-2} \\ \vdots \\ x_{t} \\ \end{array}\right) = A \left(\begin{array}{c} x_{t+p-1} \\ x_{t+p-2} \\ \vdots \\ x_{t} \\ \end{array}\right)

计算 det(\lambda I - A) = 0,可以得到其特征多项式为:

\lambda^{p}-\phi_{1}\lambda^{p-1}-\phi_{2}\lambda^{p-2}-\cdots-\phi_{p}=0.

当每个特征值都在单位圆盘内部的时候,i.e. |\lambda_{i}|<1, \forall 1\leq i\leq p,该 p 阶差分方程

x_{t} = \phi_{1}x_{t-1}+\phi_{2}x_{t-2}+\cdots+\phi_{p}x_{t-p}

存在稳定性的解。

 

时间序列的搜索

在之前的时间序列相似度算法中,时间戳都是一一对应的,但是在实际的场景中,时间戳有可能出现一定的偏移,但是两条时间序列却又是十分相似的。例如正弦函数 \sin(x) 和余弦函数 \cos(x),只是平移了 \pi/2 个长度而已。本文将会介绍一些基于形状的时间序列的距离算法,并且介绍如何在给定时间序列的情况下,在时间序列数据库中寻找相似的时间序列。

 

基于动态规划的相似度计算方法

DTW 的经典算法

基于动态规划的相似度计算的典型代表就是 DTW(Dynamical Time Warping )和 Frechet 距离。在这里将会主要介绍 DTW 算法。详细来说,DTW 算法是为了计算语音信号处理中,由于两个人说话的时长不一样,但是却是类似的一段话,欧几里德算法不完全能够解决这类问题。在这种情况下,DTW 算法就被发展出来。DTW 算法是为了计算两条时间序列的最佳匹配点,假设我们有两条时间序列 Q 和 C,长度都是 n,并且 Q:\{q_{1},q_{2},\cdots,q_{n}\}C:\{c_{1},c_{2},\cdots,c_{n}\}。首先我们可以建立一个 n\times n 的矩阵,(i,j) 位置的元素是 dist(q_{i},c_{j}),这里的 dist 可以使用 L^{1}, L^{2}, L^{p}, L^{\infty} 范数。其次,我们想找到一条路径,使得这个矩阵的累积距离最小,而这条路则是两条时间序列之间的最佳匹配。在这里,我们可以假设这条路径是 W: \{w_{1},\cdots,w_{K}\},其中 W 的每个元素表示时间序列 Q 中的第 i 个元素和时间序列 C 中的第 j 个元素之间的距离. i.e. w_{k}=(q_{i}-c_{j})^{2}

DTW1

现在我们需要找到一条路径使得

W^{*} = argmin_{W}(\sqrt{\sum_{k=1}^{K}w_{k}}).

这条路径就是动态规划的解,它满足一个动态规划方程:对于 1\leq i\leq n, 1\leq j\leq n,有

DTW(i,j)

= dist(q_{i},c_{j}) + \min(DTW(i-1,j-1), DTW(i-1,j), DTW(i,j-1)).

其初始状态是 DTW(0,0)=0, DTW(i,0)=\infty, DTW(0,j)=\infty, \forall 1\leq i\leq n, 1\leq j\leq n. 最终的取值 DTW(n,n) 就是我们需要的解,也就是两条时间序列的 DTW 距离。按照上面的算法,DTW 算法的时间复杂度是 O(n^{2})。特别地,

  1. 如果 dist(q_{i},c_{j}) = (q_{i}-c_{j})^{2} 时,则 \sqrt{DTW(n,n)} 表示最后的距离;
  2. 如果 dist(q_{i},c_{j}) = |q_{i}-c_{j}| 时,则 DTW(n,n) 表示最后的距离。
  3. 如果 dist(q_{i},c_{j}) = |q_{i}-c_{j}|^{p} 时,则 (DTW(n,n))^{1/p} 表示最后的距离。

Remark. 

DTW 算法不满足三角不等式。例如:x={0}, y={1,2}, z={1,2,2},则

DTW(x,z)=5>DTW(x,y)+DTW(y,z) = 3 + 0 =3.

DTW 的加速算法

某些时候,我们可以添加一个窗口长度的限制,换言之,如果要比较 q[i]c[j] 的话,i 与 j 需要满足 |i-j|\leq w,这里的 w 表示窗口长度。因此算法的描述如下:

初始条件和之前一样。

DTW(i,j) = dist(q_{i},c_{j}) + \min(DTW(i-1,j-1), DTW(i-1,j), DTW(i,j-1)),

这里的 j 取值范围是:对每一个 1\leq i\leq n,需要 j 满足\max(1,i-w) \leq j\leq \min(m,i+w)

 

相似时间序列的搜索

相似的时间序列的搜索问题一般是这样的:

Question 1. 给定一条时间序列 Q 和一个时间序列的数据库 D=\{C_{i}\}_{i=1}^{\infty}。通过某种相似度或者距离计算方法,计算出给定的时间序列 Q 与时间序列数据库中 D 中最相似的时间序列。

Question 2. 给定一条时间序列 Q 和一个时间序列的数据库 D=\{C_{i}\}_{i=1}^{\infty},以及正整数 K。从数据库 D 中寻找与给定的时间序列 Q 最相似的 K 条时间序列。

DTW 算法的下界 LB_Kim

对于两条时间序列 Q 和 C 而言,可以分别提取它们的四个特征,那就是最大值,最小值,第一个元素的值,最后一个元素的值。这样可以计算出 LB_Kim

LBKim(Q,C)

= \max\{|\max(Q)-\max(C)|,|\min(Q)-\min(C)|,|First(Q)-First(C)|,|Last(Q)-Last(C)| \}.

可以证明 LBKim(Q,C)\leq DTW(Q,C).

DTW 算法的下界 LB_Yi

有学者在 LB_Kim 的基础上提出了一种下界的计算方法,那就是 LB_Yi,有兴趣的读者可以参见:efficient retrieval of similar time sequences under time warping, 1998.

DTW 算法的下界 LB_Keogh

但是,如果是基于 DTW 的距离计算方法,每次都要计算两条时间序列的 DTW 距离,时间复杂度是 O(n^{2})。于是就有学者研究是否存在 DTW 距离的下界表示,也就是说找到一个合适的下界,Lower Bound of DTW。每次判断 Lower Bound of DTW 是否小于当前的最小距离,如果下界高于最小距离,就不需要进行 DTW 的计算;否则开始计算 DTW 的值。如果下界的计算速度足够快,并且下界足够精准的话,可以大量的压缩搜索的时间。于是,Keogh 提出了下界的计算方法。

(1)首先定义时间序列 Q 的上下界。i.e. Q:\{q_{1},\cdots,q_{n}\},给定一个窗口的取值 r,得到 U_{i}=\max(q_{i-r},q_{i+r})L_{i} = \min(q_{i-r},q_{i+r})

(2)定义公式:

LBKeogh(Q,C)

= \sqrt{\sum_{i=1}^{n}(c_{i}-U_{i})^{2}I_{\{c_{i}>U_{i}\}} + \sum_{i=1}^{n}(c_{i}-L_{i})^{2}I_{\{c_{i}<L_{i}\}}}.

其中,LBKeogh 满足性质:

对于任意两条长度为 n 的时间序列 Q 和 C,对于任意的窗口 r\geq 1,有不等式 LBKeogh(Q,C)\leq DTW(Q,C) 成立。

所以,可以把搜索的算法进行加速:

Lower Bounding Sequential Scan(Q)
    best_so_far = infinity 
    for all sequences in database
        LB_dist = lower_bound_distance(C_{i},Q)
        if LB_dist < best_so_far
            true_dist = DTW(C_{i},Q)
            if true_dist < best_so_far
                best_so_far = true_dist
                index_of_best_match = i
            endif
        endif
    endfor

在论文 Exact Indexing of Dynamic Time Warping 里面,作者还尝试将 Piecewise Constant Approximation 与 LB_Keogh 结合起来,提出了 LB_PAA 的下界。它满足条件 LBPAA(Q,C)\leq LBKeogh(Q,C)\leq DTW(Q,C).

 

总结

本文初步介绍了 DTW 算法以及它的下界算法,包括 LB_Kim, LB_Keogh 等,以及时间序列数据库的搜索算法。

 

如何理解时间序列?— 从Riemann积分和Lebesgue积分谈起

Riemann 积分和 Lebesgue 积分是数学中两个非常重要的概念。本文将会从 Riemann 积分和 Lebesgue 积分的定义出发,介绍它们各自的性质和联系。

积分

Riemann 积分

Riemann 积分虽然被称为 Riemann 积分,但是在 Riemann 之前就有学者对这类积分进行了详细的研究。早在阿基米德时代,阿基米德为了计算曲线 x^{2} 在 [0,1] 区间上与 X 坐标轴所夹的图形面积,就使用了 Riemann 积分的思想。 他把 [0,1] 区间等长地切割成 n 段,每一段使用一个长方形去逼近 x^{2} 这条曲线的分段面积,再把 n 取得很大,所以得到当 n 趋近于无穷的时候,就知道该面积其实是 1/3。

下面来看一下 Riemann 积分的详细定义。

Riemann Integral1

考虑定义在闭区间 [a,b] 上的函数 f(x)

取一个有限的点列 a=x_{0}<x_{1}<\cdots<x_{n}=b\lambda = \max(x_{i+1}-x_{i}) 表示这些区间长度的最大值,在这里 0\leq i\leq n-1。在每一个子区间上[x_{i},x_{i+1}] 上取出一个点 t_{i}\in[x_{i},x_{i+1}]。而函数 f(x) 关于以上取样分割的 Riemann 和就是以下公式:

\sum_{i=0}^{n-1}f(t_{i})(x_{i+1}-x_{i}).

当我们说该函数 f(x) 在闭区间 [a,b] 上的取值是 s 的意思是:

对于任意 \epsilon>0,存在 \delta>0 使得对于任意取样分割,当 \lambda<\delta 时,就有

|\sum_{i=0}^{n-1}f(t_{i})(x_{i+1}-x_{i}) - s|<\epsilon.

通常来说,用符号来表示就是:\int_{a}^{b}f(x)=s.

用几幅图来描述 Riemann 积分的思想就是:

 

Lebesgue 积分

Riemann 积分是为了计算曲线与 X 轴所围成的面积,而 Lebesgue 积分也是做同样的事情,但是计算面积的方法略有不同。要想直观的解释两种积分的原理,可以参见下图:

RiemannANDLebesgue
Riemann 积分(上)与 Lebesgue 积分(下)

Riemann 积分是把一条曲线的底部分成等长的区间,测量每一个区间上的曲线高度,所以总面积就是这些区间与高度所围成的面积和。

Lebesgue 积分是把曲线化成等高线图,每两根相邻等高线的差值是一样的。每根等高线之内含有它所圈着的长度,因此总面积就是这些等高线内的面积之和。

用再形象一点的语言来描述就是:吃一块汉堡有多种方式

  1. Riemann 积分:从一个角落开始一口一口吃,每口都包含所有的配料;
  2. Lebesgue 积分:从最上层开始吃,按照“面包-配菜-肉-蛋-面包”的节奏,一层一层来吃。

再看一幅图的表示就是:Riemann 积分是按照蓝色的数字顺序相加的,Lebesgue 积分是按照红色的数字来顺序相加的。

Riemann and Lebesgue1

 

基于这些基本的思想,就可以给出 Lebesgue 积分的定义:

简单函数指的是对指示函数的有限线性组合,i.e. \sum_{k}a_{k}I_{S_{k}},这里的 a_{k} 是系数,S_{k} 是可测集合,I 表示指示函数。当 a_{k} 非负时,令

\int(\sum_{k}a_{k}1_{S_{k}})d\mu = \sum_{k}a_{k}\int 1_{S_{k}}d\mu = \sum_{k}a_{k}\mu(S_{k}).

如果 f 是一个非负可测函数时,可以定义函数 f 在可测集合 E 上的 Lebesgue 积分是:

\int_{E}f d\mu = \sup\{\int_{E}sd\mu: \bold{0}\leq s\leq f\},

这里的 s 指的是非负简单函数,\bold{0} 表示零函数,这里的大小关系表示对定义域内的每个点都要成立。

而对于可测函数时,可以把可测函数 f 转换成 f= f^{+}-f^{-},而这里的 f^{+}f^{-} 都是非负可测函数。所以可以定义任意可测函数的 Lebesgue 积分如下:

\int fd\mu = \int f^{+}d\mu - \int f^{-}d\mu..

Riemann 积分与Lebesgue 积分的关系

定义了两种积分之后,也许有人会问它们之间是否存在矛盾?其实,它们之间是不矛盾的,因为有学者证明了这样的定理:

如果有界函数 f 在闭区间 [a,b] 是 Riemann 可积的,则它也是 Lebesgue 可积的,并且它们的积分值相等:

(R)\int_{a}^{b}f(x)dx = (L)\int_{[a,b]}f(x)dx.

左侧是表示 Riemann 积分,右侧表示 Lebesgue 积分。

形象化一点的语言描述就是:无论从角落一口一口地吃汉堡,还是从顶至下一层一层吃,所吃的汉堡都是同一个。

但是 Lebesgue 积分比 Riemann 积分有着更大的优势,例如 Dirichlet 函数,

  1. x 是有理数时,D(x) = 1
  2. x 是无理数时,D(x) = 0.

Dirichlet 函数是定义在实数轴的函数,并且值域是 \{0,1\},无法画出函数图像,它不是 Riemann 可积的,但是它 Lebesgue 可积。

 

时间序列

提到时间序列,也就是把以上所讨论的连续函数换成离散函数而已,把定义域从一个闭区间 [a,b] 换成 \{1,2,3,\cdots\} 这样的定义域而已。所以,之前所讨论的很多连续函数的想法都可以应用在时间序列上。

时间序列的表示 — 基于 Riemann 积分

现在我们可以按照 Riemann 积分的计算方法来表示一个时间序列的特征,于是就有学者把时间序列按照横轴切分成很多段,每一段使用某个简单函数(线性函数等)来表示,于是就有了以下的方法:

  1. 分段线性逼近(Piecewise Linear Approximation)
  2. 分段聚合逼近(Piecewise Aggregate Approximation)
  3. 分段常数逼近(Piecewise Constant Approximation)

说到这几种算法,其实最本质的思想就是进行数据降维的工作,用少数的数据来进行原始时间序列的表示(Representation)。用数学化的语言来描述时间序列的数据降维(Data Reduction)就是:把原始的时间序列 \{x_{1},\cdots,x_{N}\}\{x_{1}^{'},\cdots, x_{D}^{'}\} 来表示,其中 D<N。那么后者就是原始序列的一种表示(representation)。

分段聚合逼近(Piecewise Aggregate Approximation)— 类似 Riemann 积分

在这种算法中,分段聚合逼近(Piecewise Aggregate Approximation)是一种非常经典的算法。假设原始的时间序列是 C = \{x_{1},\cdots, x_{N}\},定义 PAA 的序列是:\overline{C} = \{\overline{x}_{1},\cdots,\overline{x}_{w}\}

其中

\overline{x}_{i} = \frac{w}{N} \cdot \sum_{j=\frac{N}{w}(i-1)+1}^{\frac{N}{w}i} x_{j}.

在这里 1\leq i\leq w。用图像来表示那就是:

PAA

至于分段线性逼近(Piecewise Linear Approximation)和分段常数逼近(Piecewise Constant Approximation),只需要在 \overline{x}_{i} 的定义上稍作修改即可。

符号特征(Symbolic Approximation)— 类似用简单函数来计算 Lebesgue 积分

在推荐系统的特征工程里面,特征通常来说可以做归一化,二值化,离散化等操作。例如,用户的年龄特征,一般不会直接使用具体的年月日,而是划分为某个区间段,例如 0~6(婴幼儿时期),7~12(小学),13~17(中学),18~22(大学)等阶段。

其实在得到分段特征之后,分段特征在某种程度上来说依旧是某些连续值,能否把连续值划分为一些离散的值呢?于是就有学者使用一些符号来表示时间序列的关键特征,也就是所谓的符号表示法(Symbolic Representation)。下面来介绍经典的 SAX Representation。

如果我们希望使用 \alpha 个符号来表示时间序列,那么我们其实可以考虑正态分布 N(0,1),用\{z_{1/\alpha},\cdots,z_{(\alpha-1)/\alpha}\} 来表示 Gauss 曲线下方的一些点,而这些点把 Gauss 曲线下方的面积等分成了 \alpha 段。用 \{l_{1},\cdots,l_{\alpha}\} 表示 \alpha 个字母。

SAX 方法的流程如下:

  1. 正规化(normalization):把原始的时间序列映射到一个新的时间序列,新的时间序列满足均值为零,方差为一的条件。
  2. 分段表示(PAA):\{x_{1},\cdots, x_{N}\} \Rightarrow  \{\overline{x}_{1},\cdots,\overline{x}_{w}\}
  3. 符号表示(SAX):如果 \overline{x}_{i}<z_{1/\alpha},那么 \hat{X}_{i}=l_{1};如果 z_{(j-1)/\alpha}\leq \overline{x}_{i}<z_{j/\alpha},那么 \hat{X}_{i} = l_{j},在这里 2\leq j\leq \alpha;如果 \overline{x}_{i}\geq z_{(\alpha-1)/\alpha},那么 \hat{X}_{i} = l_{\alpha}

于是,我们就可以用 \{l_{1},\cdots,l_{\alpha}\}\alpha 个字母来表示原始的时间序列了。

SAX

时间序列的表示 — 基于 Lebesgue 积分

要想考虑一个时间序列的值分布情况,其实就类似于 Lebesgue 积分的计算方法,考虑它们的分布情况,然后使用某些函数去逼近时间序列。要考虑时间序列的值分布情况,可以考虑熵的概念。

熵(Entropy)

通常来说,要想描述一种确定性与不确定性,熵(entropy)是一种不错的指标。对于离散空间而言,一个系统的熵(entropy)可以这样来表示:

\text{entropy}(X) = -\sum_{i=1}^{\infty}P\{x=x_{i}\}\ln(P\{x=x_{i}\}).

如果一个系统的熵(entropy)越大,说明这个系统就越混乱;如果一个系统的熵越小,那么说明这个系统就更加确定。

提到时间序列的熵特征,一般来说有几个经典的熵指标,其中有一个就是 binned entropy。

分桶熵(Binned Entropy)

从熵的定义出发,可以考虑把时间序列的值进行分桶的操作,例如,可以把 [min, max] 这个区间等分为十个小区间,那么时间序列的取值就会分散在这十个桶中。根据这个等距分桶的情况,就可以计算出这个概率分布的熵(entropy)。i.e. Binned Entropy 就可以定义为:

\text{binned entropy}(X) = -\sum_{k=0}^{\min(maxbin, len(X))} p_{k}\ln(p_{k})\cdot 1_{(p_{k}>0)},

其中 p_{k} 表示时间序列 X 的取值落在第 k 个桶的比例(概率),maxbin 表示桶的个数,len(X) 表示时间序列 X 的长度。

如果一个时间序列的 Binned Entropy 较大,说明这一段时间序列的取值是较为均匀的分布在 [min, max] 之间的;如果一个时间序列的 Binned Entropy 较小,说明这一段时间序列的取值是集中在某一段上的。

总结

在本篇文章中,笔者从 Riemann 积分和 Lebesgue 积分出发,介绍了它们的基本概念,性质和联系。然后从两种积分出发,探讨了时间序列的分段特征,时间序列的熵特征。在未来的 Blog 中,笔者将会介绍时间序列的更多相关内容。

 

时间序列的相似性

在文本挖掘中,可以通过 Word2Vec 生成的向量以及向量的内积,或者根据语义和词性来判断两个词语是否是近义词。在时间序列的挖掘中,同样可以找到一些方法来描述两条时间序列是否相似。

在介绍时间序列的距离之前,笔者感觉需要回顾一下数学中度量空间内积空间的定义。

度量空间

在数学里面,集合 M 上的距离函数定义为 d: M\times M\rightarrow \mathbb{R},其中 \mathbb{R} 表示实数集合,并且函数 d 满足以下几个条件:

  1. d(x,y)\geq 0,并且 d(x,y)=0 当且仅当 x=y;
  2. d(x,y)=d(y,x),也就是满足对称性;
  3. d(x,z)\leq d(x,y)+d(y,z),也就是三角不等式。

满足这三个条件的距离函数称为度量,具有某种度量的集合则叫做度量空间

Remark.

在本文下面的时间序列距离的各种定义中,这些距离不一定满足三角不等式。例如动态时间算法(DTW)就不满足三角不等式。

内积空间

一个内积空间是域 F(其中 F=\mathbb{R} 或者 F=\mathbb{C})上的向量空间 V 与一个内积(映射)所构成,V 上的一个内积定义为正定,非退化的共轭双线性形式,记成 <\cdot,\cdot>:V\times V\rightarrow F,它满足以下设定:

1. 对于任意的 x,y\in V,有 <x,y> =\overline{<y,x>}.

2. 共轭双线性形式指的是:

\forall a\in F, \forall x,y\in V, <ax,y>=a<x,y>,

\forall x,y,z\in F, <x+y,z> = <x,z> + <y,z>.

\forall b\in F, \forall x,y\in V, <x,by> = \overline{b}<x,y>,

\forall x,y,z\in F,<x,y+z> = <x,y>+<x,z>.

3. 非负性:\forall x\in V, <x,x>\geq 0.

4. 非退化:从 V 到对偶空间 V^{*} 的映射:x\mapsto<x,\cdot> 是同构映射。

 

基于欧几里德距离的相似度计算

假设两条时间序列曲线为 X_{T} = \{x_{1},\cdots,x_{T}\}Y_{T} = \{y_{1},\cdots,y_{T}\},于是可以使用欧几里德空间里面的 L^{1}, L^{2}, L^{p}, L^{\infty} 范数来表示两个时间序列之间的距离。用公式来描述就是:

d_{L^{1}}(X_{T},Y_{T}) = \sum_{t=1}^{T}|x_{t}-y_{t}|,

d_{L^{p}}(X_{T}, Y_{T}) = (\sum_{t=1}^{T}|x_{t}-y_{t}|^{p})^{1/p},

d_{L^{2}}(X_{T}, Y_{T}) = (\sum_{t=1}^{T}|x_{t}-y_{t}|^{2})^{1/2},

d_{L^{\infty}}(X_{T},Y_{T}) = \max_{1\leq t\leq T}|x_{t}-y_{t}|.

 

基于相关性的相似度计算方法

Pearson 系数(Pearson Coefficient)

\text{COR}(X_{T},Y_{T}) = \frac{\sum_{t=1}^{T}(x_{t}-\overline{X}_{T})\cdot(y_{t}-\overline{Y}_{T})}{\sqrt{\sum_{t=1}^{T}(x_{t}-\overline{X}_{T})^{2}}\cdot\sqrt{\sum_{t=1}^{T}(y_{t}-\overline{Y}_{T})^{2}}},

其中,

\overline{X}_{T} = \sum_{t=1}^{T}x_{t}/T, \overline{Y}_{T} = \sum_{t=1}^{T}y_{t}/T

Pearson 系数的性质如下:

  1. 如果两条时间序列 X_{T} = Y_{T},则 \text{COR}(X_{T},Y_{T}) =1 表是它们是完全一致的,如果两条时间序列 X_{T} = -Y_{T},则 \text{COR}(X_{T},Y_{T}) = -1 表示它们之间是负相关的。
  2. -1\leq \text{COR}(X_{T},Y_{T})\leq 1.

可以基于 Pearson 系数来制定两条时间序列之间的距离:

d_{COR,1}(X_{T},Y_{T}) = \sqrt{2\cdot(1-COR(X_{T},Y_{T}))},

d_{COR,2}(X_{T},Y_{T}) = \sqrt{\big(\frac{1-COR(X_{T},Y_{T})}{1+COR(X_{T},Y_{T})}\big)^{\beta}},

其中\beta\geq 0.

The First Order Temporal Correlation Coefficient

这个相关性系数与 Pearson 系数类似,但是略有不同,其定义为:

\text{CORT}(X_{T},Y_{T}) = \frac{\sum_{t=1}^{T-1}(x_{t+1}-x_{t})\cdot(y_{t+1}-y_{t})}{\sqrt{\sum_{t=1}^{T-1}(x_{t+1}-x_{t})^{2}}\cdot\sqrt{\sum_{t=1}^{T-1}(y_{t+1}-y_{t})^{2}}},

\text{CORT}(X_{T},Y_{T}) 的性质:

  1. -1\leq \text{CORT}(X_{T},Y_{T}) \leq 1
  2. \text{CORT}(X_{T},Y_{T}) =1 表示两条时间序列持有类似的趋势, 它们会同时上涨或者下跌,并且涨幅或者跌幅也是类似的。
  3. \text{CORT}(X_{T},Y_{T})=-1 表示两条时间序列的上涨和下跌趋势恰好相反。
  4. \text{CORT}(X_{T},Y_{T})=0 表示两条时间序列在单调性方面没有相关性。

基于 CORT,同样可以定义时间序列的距离,用公式描述如下:

d_{CORT}(X_{T},Y_{T}) = \phi_{k}[CORT(X_{T},Y_{T})]\cdot d(X_{T},Y_{T}),

其中,d(X_{T},Y_{T}) 可以用 d_{L^{1}}, d_{L^{p}}, d_{L^{2}}, d_{L^{\infty}}, d_{DTW}, d_{Frechet} 来计算,而

\phi_{k}(u) = 2/(1+\exp(ku)), k\geq 0

是一个递减函数。

基于自相关系数的距离(Autocorrelation-based distance)

假设时间序列是 X_{T} = \{x_{1},\cdots,x_{T}\},对于任意的 k<T,可以定义自相关系数为:

\hat{\rho}_{k} = \frac{1}{(T-k)\sigma^{2}}\sum_{t=1}^{T-k}(x_{t}-\mu)\cdot(x_{t+k}-\mu),

其中 \mu, \sigma^{2} 分别表示该时间序列的均值和方差。该公式相当于是比较整个时间序列 X_{T}=\{x_{1},\cdots,x_{T}\} 的两个子序列的相似度(Pearson 系数),这两个子序列分别是 \{x_{1},\cdots,x_{T-k}\}\{x_{k+1},\cdots,x_{T}\}

于是,通过给定一个正整数 L<T,可以对每一个时间序列得到一组自相关系数的向量,用公式描述如下:

\hat{\rho}_{X_{T}} = (\hat{\rho}_{1,X_{T}},\cdots,\hat{\rho}_{L,X_{T}})^{T}\in \mathbb{R}^{L},

\hat{\rho}_{Y_{T}} = (\hat{\rho}_{1,Y_{T}},\cdots,\hat{\rho}_{L,Y_{T}})^{T}\in\mathbb{R}^{L}.

对于 i>L 的情况,可以假定 \hat{\rho}_{i,X_{T}} = 0\hat{\rho}_{i,Y_{T}} = 0。于是,可以定义时间序列之间的距离如下:

d_{ACF}(X_{T},Y_{T}) = \sqrt{(\hat{\rho}_{X_{T}}-\hat{\rho}_{Y_{T}})^{T}\Omega(\hat{\rho}_{X_{T}}-\hat{\rho}_{Y_{T}})}.

其中的 \Omega 表示一个 L\times L 的矩阵。它有着很多种选择,例如:

(1)\Omega = I_{L} 表示单位矩阵。用公式表示就是

d_{ACFU}(X_{T},Y_{T}) =\sqrt{\sum_{i=1}^{L}(\hat{\rho}_{i,X_{T}}-\hat{\rho}_{i,Y_{T}})^{2}}.

(2)\Omega = diag\{p(1-p),p(1-p)^{2},\cdots,p(1-p)^{L}\} 表示一个 L\times L 的对角矩阵,其中 0<p<1。此时相当于一个带权重的求和公式。

d_{ACFU}(X_{T},Y_{T}) =\sqrt{\sum_{i=1}^{L}p(1-p)^{i}(\hat{\rho}_{i,X_{T}}-\hat{\rho}_{i,Y_{T}})^{2}}.

除了自相关系数(Autocorrelation Coefficients)之外,也可以考虑偏自相关系数(Partial Autocorrelation Coefficients),使用 PACFs 来取代 ACFs。这样,使用同样的定义方式就可以得到 d_{PACFU}d_{PACFG} 两个距离公式。

 

基于周期性的相似度计算方法

这里会介绍基于周期图表(Periodogram-based)的距离计算方法。其大体思想就是通过 Fourier 变换得到一组参数,然后通过这组参数来反映原始的两个时间序列时间的距离。用数学公式来描述就是:

I_{X_{T}}(\lambda_{k}) = T^{-1}|\sum_{t=1}^{T}x_{t}e^{-i\lambda_{k}t}|^{2},

I_{Y_{T}}(\lambda_{k}) = T^{-1}|\sum_{t=1}^{T}y_{t}e^{-i\lambda_{k}t}|^{2}.

其中 \lambda_{k} = 2\pi k/Tk = 1,\cdots,nn=[(T-1)/2]。这里的 [\cdot] 表示 Gauss 取整函数。

(1)用原始的特征来表示距离:

d_{P}(X_{T},Y_{T}) = \frac{1}{n}\sqrt{\sum_{k=1}^{n}(I_{X_{T}}(\lambda_{k})-I_{Y_{T}}(\lambda_{k}))^{2}}.

(2)用正则化之后的特征来描述就是:

d_{P}(X_{T},Y_{T}) = \frac{1}{n}\sqrt{\sum_{k=1}^{n}(NI_{X_{T}}(\lambda_{k})-NI_{Y_{T}}(\lambda_{k}))^{2}},

其中 NI_{X_{T}}(\lambda_{k})=I_{X_{T}}(\lambda_{k})/\hat{\gamma}_{0,X_{T}}NI_{Y_{T}}(\lambda_{k})=I_{Y_{T}}(\lambda_{k})/\hat{\gamma}_{0,Y_{T}}\hat{\gamma}_{0,X_{T}}\hat{\gamma}_{0,Y_{T}} 表示 X_{T}, Y_{T} 的标准差(sample variance)。

(3)用取对数之后的特征表示:

d_{LNP}(X_{T},Y_{T}) = \frac{1}{n}\sqrt{\sum_{k=1}^{n}(\ln NI_{X_{T}}(\lambda_{k})-\ln NI_{Y_{T}}(\lambda_{k}))^{2}}.

 

 

基于模型的相似度计算

Piccolo 距离

基于模型的相似度判断本质上是用一个模型和相应的一组参数去拟合某条时间序列,然后得到最优的一组参数,计算两个时间序列所得到的最优参数的欧几里德距离即可。

ARMA(p,q) 模型有自己的 AR 表示,因此可以得到相应的一组参数 (\pi_{1},\pi_{2},\cdots),所以,对于每一条时间序列,都可以用一组最优的参数去逼近。如果

\hat{\prod}_{X_{T}}=(\hat{\pi}_{1,X_{T}},\cdots,\hat{\pi}_{k_{1},X_{T}})^{T},

\hat{\prod}_{X_{T}}=(\hat{\pi}_{1,X_{T}},\cdots,\hat{\pi}_{k_{1},X_{T}})^{T}

分别表示 AR(k_{1})AR(k_{2}) 对于时间序列 X_{T}Y_{T} 的参数估计,则 Piccolo 距离如下:

d_{PIC}(X_{T},Y_{T}) =\sqrt{\sum_{j=1}^{k}(\hat{\pi}_{j,X_{T}}'-\hat{\pi}_{j,Y_{T}}')^{2}},

其中 k=\max(k_{1},k_{2})\hat{\pi}_{j,X_{T}}'=\hat{\pi}_{j,X_{T}}j\leq k_{1},并且 \hat{\pi}_{j,X_{T}}' = 0k_{1}<j\leq k\hat{\pi}_{j,Y_{T}}'=\hat{\pi}_{j,Y_{T}}j\leq k_{2},并且 \hat{\pi}_{j,Y_{T}}' = 0k_{2}<j\leq k

Maharaj 距离

按照之前的描述,可以增加一个矩阵来修改 Piccolo 距离:

d_{MAH}(X_{T},Y_{T}) =\sqrt{T}(\hat{\prod}'_{X_{T}}-\hat{\prod}'_{Y_{T}})^{T}\hat{V}^{-1}(\hat{\prod}'_{X_{T}}-\hat{\prod}'_{Y_{T}}).

其中 \hat{\prod}'_{X_{T}}\hat{\prod}'_{Y_{T}} 表示 AR(k) 模型对于 X_{T}Y_{T} 的参数估计,和 Piccolo 距离一样。\hat{V} = \sigma_{X_{T}}^{2}R_{X_{T}}^{-1}(k) + \sigma_{Y_{T}}^{2}R_{Y_{T}}^{-1}(k)\sigma_{X_{T}}^{2}\sigma_{Y_{T}}^{2} 表示时间序列的方差,R_{X_{T}}R_{Y_{T}} 表示时间序列的 sample covariance 矩阵。

基于 Cepstral 的距离

考虑时间序列 X_{T} 满足 AR(p) 的结构,i.e. X_{t}=\sum_{r=1}^{p}\phi_{r}X_{t-r}+\epsilon_{t},这里的 \phi_{r} 表示 AR 模型的参数,\epsilon_{t} 表示白噪声(均值为 0,方差为 1 的 Gauss 正态分布)。于是可以从这些参数定义 LPC 系数如下:

\psi_{1}=\phi_{1}

\psi_{h}=\phi_{h}+\sum_{m=1}^{h-1}(\phi_{m}-\psi_{h-m})1<h\leq p

\psi_{h}=\sum_{m=1}^{p}(1-\frac{m}{h})\phi_{m}\psi_{h-m}p<h

所以,LPC 的距离定义是:

d_{LPC, Cep}(X_{T},Y_{T}) =\sqrt{\sum_{i=1}^{T}(\psi_{i,X_{T}}-\psi_{i,Y_{T}})^{2}}.

 

总结

在本文中,介绍了时间序列之间距离的计算方法,包括基于 L^{p} 范数的距离,基于相关性的距离,基于周期图表的计算方法,基于模型的计算方法。

 

 

时间序列的表示与信息提取

提到时间序列,大家能够想到的就是一串按时间排序的数据,但是在这串数字背后有着它特殊的含义,那么如何进行时间序列的表示(Representation),如何进行时间序列的信息提取(Information Extraction)就成为了时间序列研究的关键问题。

就笔者的个人经验而言,其实时间序列的一些想法和文本挖掘是非常类似的。通常来说句子都是由各种各样的词语组成的,并且一般情况下都是“主谓宾”的句子结构。于是就有人希望把词语用一个数学上的向量描述出来,那么最经典的做法就是使用 one – hot 的编码格式。i.e. 也就是对字典里面的每一个词语进行编码,一个词语对应着一个唯一的数字,例如 0,1,2 这种形式。one hot 的编码格式是这行向量的长度是词典中词语的个数,只有一个值是1,其余的取值是0,也就是 (0,…,0,1,0,…,0) 这种样子。但是在一般情况下,词语的个数都是非常多的,如何使用一个维度较小的向量来表示一个词语就成为了一个关键的问题。几年前,GOOGLE 公司开源了 Word2vec 开源框架,把每一个词语用一串向量来进行描述,向量的长度可以自行调整,大约是100~1000 不等,就把原始的 one-hot 编码转换为了一个低维空间的向量。在这种情况下,机器学习的很多经典算法,包括分类,回归,聚类等都可以在文本上得到巨大的使用。Word2vec 是采用神经网络的思想来提取每个词语与周边词语的关系,从而把每个词语用一个低维向量来表示。在这里,时间序列的特征提取方法与 word2vec 略有不同,后面会一一展示这些技巧。

 

时间序列的统计特征

提到时间序列的统计特征,一般都能够想到最大值(max),最小值(min),均值(mean),中位数(median),方差(variance),标准差(standard variance)等指标,不过一般的统计书上还会介绍两个指标,那就是偏度(skewness)和峰度(kuriosis)。如果使用时间序列 X_{T} = \{x_{1},\cdots,x_{T}\} 来表示长度为 T 的时间序列,那么这些统计特征用数学公式来表示就是:

\mu=\frac{1}{T}\sum_{i=1}^{T}x_{i},

\sigma^{2} = \sum_{i=1}^{T}\frac{1}{T}(x_{i}-\mu)^{2},

\text{skewness}(X) = E[(\frac{X-\mu}{\sigma})^{3}]=\frac{1}{T}\sum_{i=1}^{T}\frac{(x_{i}-\mu)^{3}}{\sigma^{3}},

\text{kurtosis}(X) = E[(\frac{X-\mu}{\sigma})^{4}]=\frac{1}{T}\sum_{i=1}^{T}\frac{(x_{i}-\mu)^{4}}{\sigma^{4}} .

其中 \mu\sigma 分别表示时间序列 X_{T} 的均值和方差。

 

时间序列的熵特征

为什么要研究时间序列的熵呢?请看下面两个时间序列:

时间序列(1):(1,2,1,2,1,2,1,2,1,2,…)

时间序列(2):(1,1,2,1,2,2,2,2,1,1,…)

在时间序列(1)中,1 和 2 是交替出现的,而在时间序列(2)中,1 和 2 是随机出现的。在这种情况下,时间序列(1)则更加确定,时间序列(2)则更加随机。并且在这种情况下,两个时间序列的统计特征,例如均值,方差,中位数等等则是几乎一致的,说明用之前的统计特征并不足以精准的区分这两种时间序列。

通常来说,要想描述一种确定性与不确定性,熵(entropy)是一种不错的指标。对于离散空间而言,一个系统的熵(entropy)可以这样来表示:

\text{entropy}(X) = -\sum_{i=1}^{\infty}P\{x=x_{i}\}\ln(P\{x=x_{i}\}).

如果一个系统的熵(entropy)越大,说明这个系统就越混乱;如果一个系统的熵越小,那么说明这个系统就更加确定。

提到时间序列的熵特征,一般来说有几个经典的例子,那就是 binned entropyapproximate entropysample entropy。下面来一一介绍时间序列中这几个经典的熵。

Binned Entropy

从熵的定义出发,可以考虑把时间序列 X_{T} 的取值进行分桶的操作。例如,可以把 [\min(X_{T}), \max(X_{T})] 这个区间等分为十个小区间,那么时间序列的取值就会分散在这十个桶中。根据这个等距分桶的情况,就可以计算出这个概率分布的熵(entropy)。i.e. Binned Entropy 就可以定义为:

\text{binned entropy}(X) = -\sum_{k=0}^{\min(maxbin, len(X))} p_{k}\ln(p_{k})\cdot 1_{(p_{k}>0)},

其中 p_{k} 表示时间序列 X_{T} 的取值落在第 k 个桶的比例(概率),maxbin 表示桶的个数,len(X_{T}) = T 表示时间序列 X_{T} 的长度。

如果一个时间序列的 Binned Entropy 较大,说明这一段时间序列的取值是较为均匀的分布在 [\min(X_{T}), \max(X_{T})] 之间的;如果一个时间序列的 Binned Entropy 较小,说明这一段时间序列的取值是集中在某一段上的。

Approximate Entropy

回到本节的问题,如何判断一个时间序列是否具备某种趋势还是随机出现呢?这就需要介绍 Approximate Entropy 的概念了,Approximate Entropy 的思想就是把一维空间的时间序列提升到高维空间中,通过高维空间的向量之间的距离或者相似度的判断,来推导出一维空间的时间序列是否存在某种趋势或者确定性。那么,我们现在可以假设时间序列 X_{N}: \{x_{1},\cdots, x_{N}\} 的长度是 N,同时 Approximate Entropy 函数拥有两个参数,mr,下面来详细介绍 Approximate Entropy 的算法细节。

Step 1. 固定两个参数,正整数 m 和正数 r,正整数 m 是为了把时间序列进行一个片段的提取,正数 r 是表示时间序列距离的某个参数。i.e. 需要构造新的 m 维向量如下:

X_{1}(m) = (x_{1},\cdots, x_{m})\in\mathbb{R}^{m},

X_{i}(m) = (x_{i},\cdots, x_{m+i-1})\in\mathbb{R}^{m},

X_{N-m+1}(m) = (x_{N-m+1},\cdots, x_{N})\in\mathbb{R}^{m}.

Step 2. 通过新的向量 X_{1}(m),\cdots, X_{N-m+1}(m),可以计算出哪些向量与 X_{i} 较为相似。i.e.

C_{i}^{m}(r) = (\text{number of }X_{j}(m)\text{ such that } d(X_{i}(m), X_{j}(m))\leq r)/(N-m+1),

在这里,距离 d 可以选择 L^{1}, L^{2}, L^{p}, L^{\infty} 范数。在这个场景下,距离 d 通常选择为 L^{\infty} 范数。

Step 3. 考虑函数

\Phi^{m}(r) = (N-m+1)^{-1}\cdot \sum_{i=1}^{N-m+1} \ln(C_{i}^{m}(r)),

Step 4. Approximate Entropy 可以定义为:

\text{ApEn}(m,r) = \Phi^{m}(r)-\Phi^{m+1}(r).

Remark.

  1. 正整数 m 一般可以取值为 2 或者 3,r>0 会基于具体的时间序列具体调整;
  2. 如果某条时间序列具有很多重复的片段(repetitive pattern)或者自相似性(self-similarity pattern),那么它的 Approximate Entropy 就会相对小;反之,如果某条时间序列几乎是随机出现的,那么它的 Approximate Entropy 就会相对较大。

Sample Entropy

除了 Approximate Entropy,还有另外一个熵的指标可以衡量时间序列,那就是 Sample Entropy,通过自然对数的计算来表示时间序列是否具备某种自相似性。

按照以上 Approximate Entropy 的定义,可以基于 mr 定义两个指标 AB,分别是

A = \#\{\text{vector pairs having } d(X_{i}(m+1),X_{j}(m+1))<r \text{ of length } m+1  \},

B = \#\{ \text{vector pairs having } d(X_{i}(m), X_{j}(m))<r \text{ of length } m\}.

其中,\# 表示集合的元素个数。根据度量 d(无论是 L^{1}, L^{2}, L^{\infty})的定义可以知道A\leq B,因此 Sample Entropy 总是非负数,i.e.

\text{SampEn} = -\ln(A/B) \geq 0.

Remark.

  1. Sample Entropy 总是非负数;
  2. Sample Entropy 越小表示该时间序列具有越强的自相似性(self similarity)。
  3. 通常来说,在 Sample Entropy 的参数选择中,可以选择 m = 2, r = 0.2 \cdot std.

 

时间序列的分段特征

即使时间序列有一定的自相似性(self-similarity),能否说明这两条时间序列就完全相似呢?其实答案是否定的,例如:两个长度都是 1000 的时间序列,

时间序列(1): [1,2] * 500

时间序列(2): [1,2,3,4,5,6,7,8,9,10] * 100

其中,时间序列(1)是 1 和 2 循环的,时间序列(2)是 1~10 这样循环的,它们从图像上看完全是不一样的曲线,并且它们的 Approximate Entropy  和 Sample Entropy 都是非常小的。那么问题来了,有没有办法提炼出信息,从而表示它们的不同点呢?答案是肯定的。

首先,我们可以回顾一下 Riemann 积分和 Lebesgue 积分的定义和不同之处。按照下面两幅图所示,Riemann 积分是为了算曲线下面所围成的面积,因此把横轴划分成一个又一个的小区间,按照长方形累加的算法来计算面积。而 Lebesgue 积分的算法恰好相反,它是把纵轴切分成一个又一个的小区间,然后也是按照长方形累加的算法来计算面积。

RiemannANDLebesgue

之前的 Binned Entropy 方案是根据值域来进行切分的,好比 Lebesgue 积分的计算方法。现在我们可以按照 Riemann 积分的计算方法来表示一个时间序列的特征,于是就有学者把时间序列按照横轴切分成很多段,每一段使用某个简单函数(线性函数等)来表示,于是就有了以下的方法:

  1. 分段线性逼近(Piecewise Linear Approximation)
  2. 分段聚合逼近(Piecewise Aggregate Approximation)
  3. 分段常数逼近(Piecewise Constant Approximation)

说到这几种算法,其实最本质的思想就是进行数据降维的工作,用少数的数据来进行原始时间序列的表示(Representation)。用数学化的语言来描述时间序列的数据降维(Data Reduction)就是:把原始的时间序列 \{x_{1},\cdots,x_{N}\}\{x_{1}^{'},\cdots, x_{D}^{'}\} 来表示,其中 D<N。那么后者就是原始序列的一种表示(representation)。

分段聚合逼近(Piecewise Aggregate Approximation)— 类似 Riemann 积分

在这种算法中,分段聚合逼近(Piecewise Aggregate Approximation)是一种非常经典的算法。假设原始的时间序列是 C = \{x_{1},\cdots, x_{N}\},定义 PAA 的序列是:\overline{C} = \{\overline{x}_{1},\cdots,\overline{x}_{w}\}

其中

\overline{x}_{i} = \frac{w}{N} \cdot \sum_{j=\frac{N}{w}(i-1)+1}^{\frac{N}{w}i} x_{j}.

在这里 1\leq i\leq w。用图像来表示那就是:

PAA

至于分段线性逼近(Piecewise Linear Approximation)和分段常数逼近(Piecewise Constant Approximation),只需要在 \overline{x}_{i} 的定义上稍作修改即可。

符号逼近(Symbolic Approximation)— 类似 Riemann 积分

在推荐系统的特征工程里面,特征通常来说可以做归一化,二值化,离散化等操作。例如,用户的年龄特征,一般不会直接使用具体的年月日,而是划分为某个区间段,例如 0~6(婴幼儿时期),7~12(小学),13~17(中学),18~22(大学)等阶段。

其实在得到分段特征之后,分段特征在某种程度上来说依旧是某些连续值,能否把连续值划分为一些离散的值呢?于是就有学者使用一些符号来表示时间序列的关键特征,也就是所谓的符号表示法(Symbolic Representation)。下面来介绍经典的 SAX Representation。

如果我们希望使用 \alpha 个符号,例如 \{l_{1},\cdots,l_{\alpha}\} 来表示时间序列。同时考虑正态分布 N(0,1),用\{z_{1/\alpha},\cdots,z_{(\alpha-1)/\alpha}\} 来表示 Gauss 曲线下方的一些点,而这些点把 Gauss 曲线下方的面积等分成了 \alpha 段。

SAX 方法的流程如下:

Step 1. 正规化(normalization):也就是该时间序列被映射到均值为零,方差为一的区间内。

Step 2. 分段表示(PAA):\{x_{1},\cdots, x_{N}\} \Rightarrow  \{\overline{x}_{1},\cdots,\overline{x}_{w}\}

Step 3. 符号表示(SAX):如果 \overline{x}_{i}<z_{1/\alpha},那么 \hat{X}_{i}=l_{1};如果 z_{(j-1)/\alpha}\leq \overline{x}_{i}<z_{j/\alpha},那么 \hat{X}_{i} = l_{j};如果 \overline{x}_{i}\geq z_{(\alpha-1)/\alpha},那么 \hat{X}_{i} = l_{\alpha}

于是,我们就可以用 \{l_{1},\cdots,l_{\alpha}\}\alpha 个字母来表示原始的时间序列了。

SAX

 

总结

在本篇文章中,我们介绍了时间序列的一些表示方法(Representation),其中包括时间序列统计特征,时间序列的熵特征,时间序列的分段特征。在下一篇文章中,我们将会介绍时间序列的相似度计算方法。

 

How to Convert a Time Series to a Supervised Learning Problem in Python

https://machinelearningmastery.com/convert-time-series-supervised-learning-problem-python/

Machine learning methods like deep learning can be used for time series forecasting.

Before machine learning can be used, time series forecasting problems must be re-framed as supervised learning problems. From a sequence to pairs of input and output sequences.

In this tutorial, you will discover how to transform univariate and multivariate time series forecasting problems into supervised learning problems for use with machine learning algorithms.

After completing this tutorial, you will know:

  • How to develop a function to transform a time series dataset into a supervised learning dataset.
  • How to transform univariate time series data for machine learning.
  • How to transform multivariate time series data for machine learning.

Let’s get started.

How to Convert a Time Series to a Supervised Learning Problem in Python

Time Series vs Supervised Learning

Before we get started, let’s take a moment to better understand the form of time series and supervised learning data.

A time series is a sequence of numbers that are ordered by a time index. This can be thought of as a list or column of ordered values.

For example:

A supervised learning problem is comprised of input patterns (X) and output patterns (y), such that an algorithm can learn how to predict the output patterns from the input patterns.

For example:

For more on this topic, see the post:

Pandas shift() Function

A key function to help transform time series data into a supervised learning problem is the Pandas shift() function.

Given a DataFrame, the shift() function can be used to create copies of columns that are pushed forward (rows of NaN values added to the front) or pulled back (rows of NaN values added to the end).

This is the behavior required to create columns of lag observations as well as columns of forecast observations for a time series dataset in a supervised learning format.

Let’s look at some examples of the shift function in action.

We can define a mock time series dataset as a sequence of 10 numbers, in this case a single column in a DataFrame as follows:

Running the example prints the time series data with the row indices for each observation.

We can shift all the observations down by one time step by inserting one new row at the top. Because the new row has no data, we can use NaN to represent “no data”.

The shift function can do this for us and we can insert this shifted column next to our original series.

Running the example gives us two columns in the dataset. The first with the original observations and a new shifted column.

We can see that shifting the series forward one time step gives us a primitive supervised learning problem, although with X and y in the wrong order. Ignore the column of row labels. The first row would have to be discarded because of the NaN value. The second row shows the input value of 0.0 in the second column (input or X) and the value of 1 in the first column (output or y).

We can see that if we can repeat this process with shifts of 2, 3, and more, how we could create long input sequences (X) that can be used to forecast an output value (y).

The shift operator can also accept a negative integer value. This has the effect of pulling the observations up by inserting new rows at the end. Below is an example:

Running the example shows a new column with a NaN value as the last value.

We can see that the forecast column can be taken as an input (X) and the second as an output value (y). That is the input value of 0 can be used to forecast the output value of 1.

Technically, in time series forecasting terminology the current time (t) and future times (t+1, t+n) are forecast times and past observations (t-1, t-n) are used to make forecasts.

We can see how positive and negative shifts can be used to create a new DataFrame from a time series with sequences of input and output patterns for a supervised learning problem.

This permits not only classical X -> y prediction, but also X -> Y where both input and output can be sequences.

Further, the shift function also works on so-called multivariate time series problems. That is where instead of having one set of observations for a time series, we have multiple (e.g. temperature and pressure). All variates in the time series can be shifted forward or backward to create multivariate input and output sequences. We will explore this more later in the tutorial.

The series_to_supervised() Function

We can use the shift() function in Pandas to automatically create new framings of time series problems given the desired length of input and output sequences.

This would be a useful tool as it would allow us to explore different framings of a time series problem with machine learning algorithms to see which might result in better performing models.

In this section, we will define a new Python function named series_to_supervised() that takes a univariate or multivariate time series and frames it as a supervised learning dataset.

The function takes four arguments:

  • data: Sequence of observations as a list or 2D NumPy array. Required.
  • n_in: Number of lag observations as input (X). Values may be between [1..len(data)] Optional. Defaults to 1.
  • n_out: Number of observations as output (y). Values may be between [0..len(data)-1]. Optional. Defaults to 1.
  • dropnan: Boolean whether or not to drop rows with NaN values. Optional. Defaults to True.

The function returns a single value:

  • return: Pandas DataFrame of series framed for supervised learning.

The new dataset is constructed as a DataFrame, with each column suitably named both by variable number and time step. This allows you to design a variety of different time step sequence type forecasting problems from a given univariate or multivariate time series.

Once the DataFrame is returned, you can decide how to split the rows of the returned DataFrame into X and y components for supervised learning any way you wish.

The function is defined with default parameters so that if you call it with just your data, it will construct a DataFrame with t-1 as X and t as y.

The function is confirmed to be compatible with Python 2 and Python 3.

The complete function is listed below, including function comments.

Can you see obvious ways to make the function more robust or more readable?
Please let me know in the comments below.

Now that we have the whole function, we can explore how it may be used.

One-Step Univariate Forecasting

It is standard practice in time series forecasting to use lagged observations (e.g. t-1) as input variables to forecast the current time step (t).

This is called one-step forecasting.

The example below demonstrates a one lag time step (t-1) to predict the current time step (t).

Running the example prints the output of the reframed time series.

We can see that the observations are named “var1” and that the input observation is suitably named (t-1) and the output time step is named (t).

We can also see that rows with NaN values have been automatically removed from the DataFrame.

We can repeat this example with an arbitrary number length input sequence, such as 3. This can be done by specifying the length of the input sequence as an argument; for example:

The complete example is listed below.

Again, running the example prints the reframed series. We can see that the input sequence is in the correct left-to-right order with the output variable to be predicted on the far right.

Multi-Step or Sequence Forecasting

A different type of forecasting problem is using past observations to forecast a sequence of future observations.

This may be called sequence forecasting or multi-step forecasting.

We can frame a time series for sequence forecasting by specifying another argument. For example, we could frame a forecast problem with an input sequence of 2 past observations to forecast 2 future observations as follows:

The complete example is listed below:

Running the example shows the differentiation of input (t-n) and output (t+n) variables with the current observation (t) considered an output.

Multivariate Forecasting

Another important type of time series is called multivariate time series.

This is where we may have observations of multiple different measures and an interest in forecasting one or more of them.

For example, we may have two sets of time series observations obs1 and obs2 and we wish to forecast one or both of these.

We can call series_to_supervised() in exactly the same way.

For example:

Running the example prints the new framing of the data, showing an input pattern with one time step for both variables and an output pattern of one time step for both variables.

Again, depending on the specifics of the problem, the division of columns into X and Y components can be chosen arbitrarily, such as if the current observation of var1 was also provided as input and only var2 was to be predicted.

You can see how this may be easily used for sequence forecasting with multivariate time series by specifying the length of the input and output sequences as above.

For example, below is an example of a reframing with 1 time step as input and 2 time steps as forecast sequence.

Running the example shows the large reframed DataFrame.

Experiment with your own dataset and try multiple different framings to see what works best.

Summary

In this tutorial, you discovered how to reframe time series datasets as supervised learning problems with Python.

Specifically, you learned:

  • About the Pandas shift() function and how it can be used to automatically define supervised learning datasets from time series data.
  • How to reframe a univariate time series into one-step and multi-step supervised learning problems.
  • How to reframe multivariate time series into one-step and multi-step supervised learning problems.

Do you have any questions?
Ask your questions in the comments below and I will do my best to answer.

Mueen Keogh算法

论文:Exact Discovery of Time Series Motifs

 

Speeded up Brute Force Motif Discovery:

Github:https://github.com/saifuddin778/mkalgo

但是感觉有一行比较奇怪,应该是 Dist_{I(j+offset)}-Dist_{I(j)} < best-so-far,而不是Dist_{I(j)}-Dist_{I(j+offset)} < best-so-far,因为 D_{I(j)} 是递增排列的,并且 best-so-far > 0.

Speeded up brute force motif discovery

Generalization to multiple reference points:

https://github.com/nicholasg3/motif-mining/tree/95bbb05ac5d0f9e90134a67a789ea7e607f22cea

注意:

for j = 1 to m-offset 而不是 for j = 1 to R

nicholasg3 MK_Motif_discovery

MK Motif Discovery

Time Series Clustering with Dynamic Time Warping (DTW)

https://github.com/goodmattg/wikipedia_kaggle