09 | March | 2018 | ZHANG RONG

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

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

度量空间

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

$d(x,y)\geq 0$ ，并且 $d(x,y)=0$ 当且仅当 $x=y$ ;
$d(x,y)=d(y,x)$ ，也就是满足对称性；
$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 系数的性质如下：

如果两条时间序列 $X_{T} = Y_{T}$ ，则 $\text{COR}(X_{T},Y_{T}) =1$ 表是它们是完全一致的，如果两条时间序列 $X_{T} = -Y_{T}$ ，则 $\text{COR}(X_{T},Y_{T}) = -1$ 表示它们之间是负相关的。
$-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\leq \text{CORT}(X_{T},Y_{T}) \leq 1$
$\text{CORT}(X_{T},Y_{T}) =1$ 表示两条时间序列持有类似的趋势，它们会同时上涨或者下跌，并且涨幅或者跌幅也是类似的。
$\text{CORT}(X_{T},Y_{T})=-1$ 表示两条时间序列的上涨和下跌趋势恰好相反。
$\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/T$ ， $k = 1,\cdots,n$ ， $n=[(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}}' = 0$ 当 $k_{1}<j\leq k$ 。 $\hat{\pi}_{j,Y_{T}}'=\hat{\pi}_{j,Y_{T}}$ 当 $j\leq k_{2}$ ，并且 $\hat{\pi}_{j,Y_{T}}' = 0$ 当 $k_{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 系数如下：