计算机视觉中的注意力机制

January 23, 2019 zr9558 2 Comments

引言

在机器翻译（Machine Translation）或者自然语言处理（Natural Language Processing）领域，以前都是使用数理统计的方法来进行分析和处理。近些年来，随着 AlphaGo 的兴起，除了在游戏AI领域，深度学习在计算机视觉领域，机器翻译和自然语言处理领域也有着巨大的用武之地。在 2016 年，随着深度学习的进一步发展，seq2seq 的训练模式和翻译模式已经开始进入人们的视野。除此之外，在端到端的训练方法中，除了需要海量的业务数据之外，在网络结构中加入一些重要的模块也是非常必要的。在此情形下，基于循环神经网咯（Recurrent Neural Network）的注意力机制（Attention Mechanism）进入了人们的视野。除了之前提到的机器翻译和自然语言处理领域之外，计算机视觉中的注意力机制也是十分有趣的，本文将会简要介绍一下计算机视觉领域中的注意力方法。在此事先声明一下，笔者并不是从事这几个领域的，可能在撰写文章的过程中会有些理解不到位的地方，请各位读者指出其中的不足。

LSTM_1

注意力机制

顾名思义，注意力机制是本质上是为了模仿人类观察物品的方式。通常来说，人们在看一张图片的时候，除了从整体把握一幅图片之外，也会更加关注图片的某个局部信息，例如局部桌子的位置，商品的种类等等。在翻译领域，每次人们翻译一段话的时候，通常都是从句子入手，但是在阅读整个句子的时候，肯定就需要关注词语本身的信息，以及词语前后关系的信息和上下文的信息。在自然语言处理方向，如果要进行情感分类的话，在某个句子里面，肯定会涉及到表达情感的词语，包括但不限于“高兴”，“沮丧”，“开心”等关键词。而这些句子里面的其他词语，则是上下文的关系，并不是它们没有用，而是它们所起的作用没有那些表达情感的关键词大。

在以上描述下，注意力机制其实包含两个部分：

注意力机制需要决定整段输入的哪个部分需要更加关注；
从关键的部分进行特征提取，得到重要的信息。

通常来说，在机器翻译或者自然语言处理领域，人们阅读和理解一句话或者一段话其实是有着一定的先后顺序的，并且按照语言学的语法规则来进行阅读理解。在图片分类领域，人们看一幅图也是按照先整体再局部，或者先局部再整体来看的。再看局部的时候，尤其是手写的手机号，门牌号等信息，都是有先后顺序的。为了模拟人脑的思维方式和理解模式，循环神经网络（RNN）在处理这种具有明显先后顺序的问题上有着独特的优势，因此，Attention 机制通常都会应用在循环神经网络上面。

虽然，按照上面的描述，机器翻译，自然语言处理，计算机视觉领域的注意力机制差不多，但是其实仔细推敲起来，这三者的注意力机制是有明显区别的。

在机器翻译领域，翻译人员需要把已有的一句话翻译成另外一种语言的一句话。例如把一句话从英文翻译到中文，把中文翻译到法语。在这种情况下，输入语言和输出语言的词语之间的先后顺序其实是相对固定的，是具有一定的语法规则的；
在视频分类或者情感识别领域，视频的先后顺序是由时间戳和相应的片段组成的，输入的就是一段视频里面的关键片段，也就是一系列具有先后顺序的图片的组合。NLP 中的情感识别问题也是一样的，语言本身就具有先后顺序的特点；
图像识别，物体检测领域与前面两个有本质的不同。因为物体检测其实是在一幅图里面挖掘出必要的物体结构或者位置信息，在这种情况下，它的输入就是一幅图片，并没有非常明显的先后顺序，而且从人脑的角度来看，由于个体的差异性，很难找到一个通用的观察图片的方法。由于每个人都有着自己观察的先后顺序，因此很难统一成一个整体。

在这种情况下，机器翻译和自然语言处理领域使用基于 RNN 的 Attention 机制就变得相对自然，而计算机视觉领域领域则需要必要的改造才能够使用 Attention 机制。

LSTM_3

基于 RNN 的注意力机制

通常来说，RNN 等深度神经网络可以进行端到端的训练和预测，在机器翻译领域和或者文本识别领域有着独特的优势。对于端到端的 RNN 来说，有一个更简洁的名字叫做 sequence to sequence，简写就是 seq2seq。顾名思义，输入层是一句话，输出层是另外一句话，中间层包括编码和解码两个步骤。

而基于 RNN 的注意力机制指的是，对于 seq2seq 的诸多问题，在输入层和输出层之间，也就是词语（Items）与词语之间，存在着某种隐含的联系。例如：“中国” -> “China”，“Excellent” -> “优秀的”。在这种情况下，每次进行机器翻译的时候，模型需要了解当前更加关注某个词语或者某几个词语，只有这样才能够在整句话中进行必要的提炼。在这些初步的思考下，基于 RNN 的 Attention 机制就是：

建立一个编码（Encoder）和解码（Decoder）的非线性模型，神经网络的参数足够多，能够存储足够的信息；
除了关注句子的整体信息之外，每次翻译下一个词语的时候，需要对不同的词语赋予不同的权重，在这种情况下，再解码的时候，就可以同时考虑到整体的信息和局部的信息。

LSTM_4

注意力机制的种类

从初步的调研情况来看，注意力机制有两种方法，一种是基于强化学习（Reinforcement Learning）来做的，另外一种是基于梯度下降（Gradient Decent）来做的。强化学习的机制是通过收益函数（Reward）来激励，让模型更加关注到某个局部的细节。梯度下降法是通过目标函数以及相应的优化函数来做的。无论是 NLP 还是 CV 领域，都可以考虑这些方法来添加注意力机制。

LSTM_5

计算机视觉领域的 Attention 部分论文整理

下面将会简单的介绍几篇近期阅读的计算机视觉领域的关于注意力机制的文章。

Look Closer to See Better：Recurrent Attention Convolutional Neural Network for Fine-grained Image Recognition

在图像识别领域，通常都会遇到给图片中的鸟类进行分类，包括种类的识别，属性的识别等内容。为了区分不同的鸟，除了从整体来对图片把握之外，更加关注的是一个局部的信息，也就是鸟的样子，包括头部，身体，脚，颜色等内容。至于周边信息，例如花花草草之类的，则显得没有那么重要，它们只能作为一些参照物。因为不同的鸟类会停留在树木上，草地上，关注树木和草地的信息对鸟类的识别并不能够起到至关重要的作用。所以，在图像识别领域引入注意力机制就是一个非常关键的技术，让深度学习模型更加关注某个局部的信息。

RA_CNN_1

在这篇文章里面，作者们提出了一个基于 CNN 的注意力机制，叫做 recurrent attention convolutional neural network（RA-CNN），该模型递归地分析局部信息，从局部的信息中提取必要的特征。同时，在 RA-CNN 中的子网络（sub-network）中存在分类结构，也就是说从不同区域的图片里面，都能够得到一个对鸟类种类划分的概率。除此之外，还引入了 attention 机制，让整个网络结构不仅关注整体信息，还关注局部信息，也就是所谓的 Attention Proposal Sub-Network（APN）。这个 APN 结构是从整个图片（full-image）出发，迭代式地生成子区域，并且对这些子区域进行必要的预测，并将子区域所得到的预测结果进行必要的整合，从而得到整张图片的分类预测概率。

RA_CNN_2

RA-CNN 的特点是进行一个端到端的优化，并不需要提前标注 box，区域等信息就能够进行鸟类的识别和图像种类的划分。在数据集上面，该论文不仅在鸟类数据集（CUB Birds）上面进行了实验，也在狗类识别（Stanford Dogs）和车辆识别（Stanford Cars）上进行了实验，并且都取得了不错的效果。

RA_CNN_4

从深度学习的网络结构来看，RA-CNN 的输入时是整幅图片（Full Image），输出的时候就是分类的概率。而提取图片特征的方法通常来说都是使用卷积神经网络（CNN）的结构，然后把 Attention 机制加入到整个网络结构中。从下图来看，一开始，整幅图片从上方输入，然后判断出一个分类概率；然后中间层输出一个坐标值和尺寸大小，其中坐标值表示的是子图的中心点，尺寸大小表示子图的尺寸。在这种基础上，下一幅子图就是从坐标值和尺寸大小得到的图片，第二个网络就是在这种基础上构建的；再迭代持续放大图片，从而不停地聚焦在图片中的某些关键位置。不同尺寸的图片都能够输出不同的分类概率，再将其分类概率进行必要的融合，最终的到对整幅图片的鸟类识别概率。

因此，在整篇论文中，有几个关键点需要注意：

分类概率的计算，也就是最终的 loss 函数的设计；
从上一幅图片到下一幅图片的坐标值和尺寸大小。

只要获得了这些指标，就可以把整个 RA-CNN 网络搭建起来。

大体来说，第一步就是给定了一幅输入图片 $X$ ，需要提取它的特征，可以记录为 $W_{c}*X$ ，这里的 $*$ 指的是卷积等各种各样的操作。所以得到的概率分布情况其实就是 $p(X) = f(W_{c}*X)$ ， $f$ 指的是从 CNN 的特征层到全连接层的函数，外层使用了 Softmax 激活函数来计算鸟类的概率。

第二步就是计算下一个 box 的坐标 $(t_{x}, t_{y})$ 和尺寸大小 $t_{\ell}$ ，其中 $t_{x}, t_{y}$ 分别指的是横纵坐标，正方形的边长其实是 $2*t_{\ell}$ 。用数学公式来记录这个流程就是 $[t_{x}, t_{y}, t_{\ell}] = g(W_{c}*X)$ 。在坐标值的基础上，我们可以得到以下四个值，分别表示 $x, y$ 两个坐标轴的上下界：

$t_{x(t\ell)} = t_{x} - t_{\ell}, t_{x(br)} = t_{x} + t_{\ell},$

$t_{y(t\ell)} = t_{y} - t_{\ell}, t_{y(br)} = t_{y} + t_{\ell}.$

局部注意力和放大策略（Attention Localization and Amplification）指的是：从上面的方法中拿到坐标值和尺寸，然后把图像进行必要的放大。为了提炼局部的信息，其实就需要在整张图片 $X$ 的基础上加上一个面具（Mask）。所谓面具，指的是在原始图片的基础上进行点乘 0 或者 1 的操作，把一些数据丢失掉，把一些数据留下。在图片领域，就是把周边的信息丢掉，把鸟的信息留下。但是，有的时候，如果直接进行 0 或者 1 的硬编码，会显得网络结构不够连续或者光滑，因此就有其他的替代函数。

在激活函数里面，逻辑回归函数（Logistic Regression）是很常见的。其实通过逻辑回归函数，我们可以构造出近似的阶梯函数或者面具函数。

sigmoid_1

对于逻辑回归函数 $\sigma(x) = 1/(1+e^{-kx})$ 而言，当 $k$ 足够大的时候， $\sigma(x) \approx 1$ 当 $x \geq 0$ ； $\sigma(x) \approx 0$ 当 $x<0$ 。此时的逻辑回归函数近似于一个阶梯函数。如果假设 $x_{0}<x_{1}$ ，那么 $\sigma(x-x_{0}) - \sigma(x-x_{1})$ 就是光滑一点的阶梯函数， $\sigma(x-x_{0}) - \sigma(x-x_{1}) \approx 0$ 当 $x < x_{0} \text{ or } x > x_{1}$ ； $\sigma(x-x_{0}) - \sigma(x-x_{1}) \approx 1$ 当 $x_{0}\leq x\leq x_{1}$ 。

因此，基于以上的分析和假设，我们可以构造如下的函数： $X^{attr} = X \odot M(t_{x}, t_{y}, t_{\ell}),$ 其中， $X^{attr}$ 表示图片需要关注的区域， $M(\cdot)$ 函数就是 $M(t_{x}, t_{y}, t_{\ell}) = [\sigma(x-t_{x(t\ell)}) - \sigma(x-t_{x(br)})]\cdot[\sigma(y-t_{y(t\ell)}) - \sigma(y-t_{y(br)})],$ 这里的 $\sigma$ 函数对应了一个足够大的 $k$ 值。

当然，从一张完整的图片到小图片，在实际操作的时候，需要把小图片继续放大，在放大的过程中，可以考虑使用双线性插值算法来扩大。也就是说：

$X_{(i,j)}^{amp} = \sum_{\alpha,\beta=0}^{1}|1-\alpha-\{i/\lambda\}|\cdot|1-\beta-\{j/\lambda\}|\cdot X_{(m,n)}^{att},$

其中 $m = [i/\lambda] + \alpha, n = [j/\lambda] + \beta$ ， $\lambda$ 表示上采样因子， $[\cdot], \{\cdot\}$ 分别表示一个实数的正数部分和小数部分。

在分类（Classification）和排序（Ranking）部分，RA-CNN 也有着自己的方法论。在损失函数（Loss Function）里面有两个重要的部分，第一个部分就是三幅图片的 LOSS 函数相加，也就是所谓的 classification loss， $Y^{(s)}$ 表示预测类别的概率， $Y$ 表示真实的类别。除此之外，另外一个部分就是排序的部分， $L_{rank}(p_{t}^{(s)}, p_{t}^{(s+1)}) = \max\{0,p_{t}^{(s)}-p_{t+1}^{(s+1)}+margin\},$ 其中 $p^{(s)}$ 表示在第 $s$ 个尺寸下所得到的类别 $t$ 的预测概率，并且最大值函数强制了该深度学习模型在训练中可以保证 $p_{t}^{(s+1)} > p_{t}^{(s)} + margin$ ，也就是说，局部预测的概率值应该高于整体的概率值。

$L(X) = \sum_{s=1}^{3}\{L_{cls}(Y^{(s)},Y^{*})\} + \sum_{s=1}^{2}\{L_{rank}(p_{t}^{(s)},p_{t}^{(s+1)})\}$ .

RA_CNN_3

在这种 Attention 机制下，可以使用训练好的 conv5_4 或者 VGG-19 来进行特征的提取。在图像领域，location 的位置是需要通过训练而得到的，因为每张图片的鸟的位置都有所不同。进一步通过数学计算可以得到， $t_{\ell}$ 会随着网络而变得越来越小，也就是一个层次递进的关系，越来越关注到局部信息的提取。简单来看，

$\frac{\partial L_{rank}}{\partial t_{x}} \propto D_{top} \odot \frac{\partial M(t_{x},t_{y},t_{\ell})}{\partial t_{x}},$

这里的 $\odot$ 表示元素的点乘， $D_{top}$ 表示之前的网络所得到的导数。

当 $x\rightarrow t_{x(t\ell)}$ ， $\frac{\partial M}{\partial t_{x}}<0;$

当 $x \rightarrow t_{x(br)}$ ， $\frac{\partial M}{\partial t_{x}}>0;$

其余情况， $\frac{\partial M}{\partial t_{x}}=0.$

当 $y\rightarrow t_{y(t\ell)}$ ， $\frac{\partial M}{\partial t_{y}}<0;$

当 $y \rightarrow t_{y(br)}$ ， $\frac{\partial M}{\partial t_{y}}>0;$

其余情况， $\frac{\partial M}{\partial t_{y}}=0.$

当 $x \rightarrow t_{x(t\ell)}\text{ or } x \rightarrow t_{x(br)}\text{ or } y \rightarrow t_{y(t\ell)}\text{ or } y \rightarrow t_{y(br)},$ $\frac{\partial M}{\partial t_{\ell}}>0;$

其余情况， $\frac{\partial M}{\partial t_{\ell}}<0.$

因此， $t_{\ell}$ 在迭代的过程中会越来越小，也就是说关注的区域会越来越集中。

RA-CNN 的实验效果如下：

Multiple Granularity Descriptors for Fine-grained Categorization

这篇文中同样做了鸟类的分类工作，与 RA-CNN 不同之处在于它使用了层次的结构，因为鸟类的区分是按照一定的层次关系来进行的，粗糙来看，有科 -> 属 -> 种三个层次结构。

MC_CNN_1

因此，在设计网络结构的过程中，需要有并行的网络结构，分别对应科，属，种三个层次。从前往后的顺序是检测网络（Detection Network），区域发现（Region Discovery），描述网络（Description Network）。并行的结构是 Family-grained CNN + Family-grained Descriptor，Genus-grained CNN + Genus-grained Descriptor，Species-grained CNN + Species-grained Descriptor。而在区域发现的地方，作者使用了 energy 的思想，让神经网络分别聚焦在图片中的不同部分，最终的到鸟类的预测结果。

MC_CNN_2 MC_CNN_3

Recurrent Models of Visual Attention

在计算机视觉中引入注意力机制，DeepMind 的这篇文章 recurrent models of visual attention 发表于 2014 年。在这篇文章中，作者使用了基于强化学习方法的注意力机制，并且使用收益函数来进行模型的训练。从网络结构来看，不仅从整体来观察图片，也从局部来提取必要的信息。

DeepMind_1

DeepMind_2 DeepMind_3

整体来看，其网络结构是 RNN，上一个阶段得到的信息和坐标会被传递到下一个阶段。这个网络只在最后一步进行分类的概率判断，这是与 RA-CNN 不同之处。这是为了模拟人类看物品的方式，人类并非会一直把注意力放在整张图片上，而是按照某种潜在的顺序对图像进行扫描。Recurrent Models of Visual Attention 本质上是把图片按照某种时间序列的形式进行输入，一次处理原始图片的一部分信息，并且在处理信息的过程中，需要根据过去的信息和任务选择下一个合适的位置进行处理。这样就可以不需要进行事先的位置标记和物品定位了。

DeepMind_4

正如上图所示，enc 指的是对图片进行编码， $r_{i}^{(1)}$ 表示解码的过程， $x_{i}$ 表示图片的一个子区域。而 $y_{s}$ 表示对图片的预测概率或者预测标签。

Multiple Object Recognition with Visual Attention

这篇文章同样是 DeepMind 的论文，与 Recurrent Models of Visual Attention 不同之处在于，它是一个两层的 RNN 结构，并且在最上层把原始图片进行输入。其中 enc 是编码网络， $r^{(1)}_{i}$ 是解码网络， $r_{i}^{(2)}$ 是注意力网络，输出概率在解码网络的最后一个单元输出。

deep_recurrent_attention_model_1

在门牌识别里面，该网络是按照从左到右的顺序来进行图片扫描的，这与人类识别物品的方式极其相似。除了门牌识别之外，该论文也对手写字体进行了识别，同样取得了不错的效果。

deep_recurrent_attention_model_3

实验效果如下：

总结

本篇 Blog 初步介绍了计算机视觉中的 Attention 机制，除了这些方法之外，应该还有一些更巧妙的方法，希望各位读者多多指教。

参考文献

Look Closer to See Better：Recurrent Attention Convolutional Neural Network for Fine-grained Image Recognition，CVPR，2017.
Recurrent Models of Visual Attention，NIPS，2014
GitHub 代码：Recurrent-Attention-CNN，https://github.com/Jianlong-Fu/Recurrent-Attention-CNN
Multiple Granularity Descriptors for Fine-grained Categorization，ICCV，2015
Multiple Object Recognition with Visual Attention，ICRL，2015
Understanding LSTM Networks，Colah’s Blog，2015，http://colah.github.io/posts/2015-08-Understanding-LSTMs/
Survey on the attention based RNN model and its applications in computer vision，2016

时间序列

时间序列的聚类

January 21, 2019 zr9558 Leave a comment

在机器学习领域，聚类问题一直是一个非常常见的问题。无论是在传统的机器学习（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 相似度等方法来计算原始时间序列的相似度。参考文章：基于自编码器的时间序列异常检测算法，基于前馈神经网络的时间序列异常检测算法。

总结

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

参考文献

聚类分析：https://en.wikipedia.org/wiki/Cluster_analysis
Dynamic Time Warping：https://en.wikipedia.org/wiki/Dynamic_time_warping
Pearson Coefficient：https://en.wikipedia.org/wiki/Pearson_correlation_coefficient
Auto Encoder：https://en.wikipedia.org/wiki/Autoencoder
Word2Vec：https://en.wikipedia.org/wiki/Word2vec，https://samyzaf.com/ML/nlp/nlp.html

时间序列

时间序列的单调性

January 8, 2019 zr9558 Leave a comment

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

连续函数的单调性

导数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 1$ ， $M_{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$ ，那么短线和长线则分别是：

在这里， $\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)$ 时，也可以使用同样的方法证明时间序列有下跌的趋势。

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

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

$3-\sigma$ 控制图

假设时间序列是 $X_{N} = [x_{1},\cdots, x_{N}]$ ，为了计算某个时间戳 $n$ 下 $x_{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

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

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。

参考资料

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

ZHANG RONG

Monthly Archives: January 2019

计算机视觉中的注意力机制

引言

注意力机制

基于 RNN 的注意力机制

注意力机制的种类

计算机视觉领域的 Attention 部分论文整理

Look Closer to See Better：Recurrent Attention Convolutional Neural Network for Fine-grained Image Recognition

Multiple Granularity Descriptors for Fine-grained Categorization

Recurrent Models of Visual Attention

Multiple Object Recognition with Visual Attention

总结

参考文献

时间序列的聚类

机器学习的聚类算法

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

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

时间序列的聚类算法

时间序列的特征提取

时间序列的相似度计算

总结

参考文献

时间序列的单调性

连续函数的单调性

时间序列的单调性

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

简单的移动平均算法

带权重的移动平均算法

指数移动平均算法

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

$3-\sigma$ 控制图

Moving Average 控制图

EWMA 控制图

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

MACD 方法

参考资料

zr9558's Blog