November | 2017 | ZHANG RONG

文章是：”Correlating Events with Time Series for Incident Diagnosis” 是微软在2014年的工作，并且发表在KDD上。

本文提出了一种无监督和统计判别的算法，可以检测出事件（E）与时间序列（S）的关联关系，并且可以检测出时间序列（S）的单调性（上升或者下降）。在这篇文章中，选择的事件有CPU（Memory, Disk）Intensive Program，Query Alert；选择的时间序列有 CPU（Memory）Usage，Disk Transfer Rate。时间序列的特点是它们的值域范围都是[0,1]。

Table1

案例是：时间序列是CPU的Usage，事件是Disk Intensive task和CPU intensive task。

关联关系的挖掘分成三个部分：

（1）是否存在关联性（Existence of Dependency）：在事件（E）与时间序列（S）之间是否存在关联关系。

（2）关联关系的因果关系（Temporal Order of Dependency）：是事件（E）导致了时间序列（S）的变化还是时间序列（S）导致了事件（E）的发生。

（3）关联关系的单调性影响（Monotonic Effect of Dependency）：用于判断时间序列（S）是发生了突增或者是突降。

基本概念：

给定一个事件序列（E），事件发生的时间戳是 $T_{E}=(t_{1},\cdots,t_{n})$ ，这里n表示有n个事件发生。时间序列（S）表示为 $S=(s_{1},\cdots,s_{m})$ ，这里的m表示时间序列的长度。时间序列的时间戳可以选择一个等差序列，等差用 $\tau$ 来表示，并且 $T_{S}=(t(s_{1}),\cdots,t(s_{n}))$ ，and $t(s_{i}) =t(s_{i-1})$ + $\tau$ 。

用 $e_{i}$ 来表示某个事件， $\ell_{k}^{rear}(S,e_{i})$ 表示序列S在事件 $e_{i}$ 之后的长度为k的子序列， $\ell_{k}^{front}(S,e_{i})$ 表示序列S在事件 $e_{i}$ 之前的长度为k的子序列。如果事件E与时间序列S之间存在关联关系，那么

$\Gamma^{front}=\{\ell_{k}^{front}(S,e_{i}), i=1,\cdots,n\}$ 和

$\Gamma^{rear}=\{\ell_{k}^{rear}(S,e_{i}),i=1,\cdots,n\}$ 应该是不一样的。

定义一：如果事件序列E和时间序列S是相关的，并且 $S->E$ ，当且仅当 $\Gamma^{front}=\{\ell_{k}^{front}(S,e_{i}), i=1,\cdots,n\}$ 和随机选择的子序列分布不一致。

定义二：如果事件序列E和时间序列S是相关的，并且 $E->S$ ，当且仅当 $\Gamma^{rear}=\{\ell_{k}^{rear}(S,e_{i}),i=1,\cdots,n\}$ 和随机选择的子序列分布不一致，并且 $\Gamma^{front}=\{\ell_{k}^{front}(S,e_{i}), i=1,\cdots,n\}$ 和随机选择的子序列分布一致。

定义三：如果事件序列E和时间序列S是相关的，那么 $S->E$ 或者 $E->S$ 。

定义四：如果 $E->S$ (or $S->E$ )，并且时间序列相比E之前是增加了，那么记为 $E\stackrel{+}{\longrightarrow} S$ (or $S\stackrel{+}{\longrightarrow} E$ )。如果 $E->S$ (or $S->E$ )，并且时间序列相比E之前是减少了，那么记为 $E\stackrel{-}{\longrightarrow} S$ (or $S\stackrel{-}{\longrightarrow} E$ )。

方法论：

第一步：最邻近算法（类似kNN）（Nearest Neighbor Method）

在计算时间序列之间距离的时候，使用DTW算法或者DTW-D算法会优于L1或者L2算法。

用 $\Gamma^{front}$ 来做例子， $\Gamma^{front}=\{\ell_{k}^{front}(S,e_{i}), i=1,\cdots,n\}$ ， $\Theta =\{\theta_{1},\cdots,\theta_{\tilde{n}}\}$ 是随机选择的， $Z=\Gamma \cup \Theta$ ，可以标记为 $Z_{1},\cdots,Z_{p}$ ，其中 $p=n$ + $\tilde{n}$ 。 $Z_{i}=\ell_{k}^{front}(S,e_{i})$ when $1\leq i\leq n$ ， $Z_{i}=\theta_{i-n}$ when $n$ + $1\leq i\leq p$ 。可以使用记号 $A=A_{1}\cup A_{2}$ ，其中 $A_{1}=\Gamma^{front}$ ， $A_{2}=\Theta=\{\theta_{1},\cdots,\theta_{\tilde{n}}\}$ 是随机选择的。

对于集合 $A$ ， $x\in A$ 而言， $NN_{r}(x,A)$ 表示 $A-\{x\}$ 中距离x最近的第r个元素，对于两个不相交的集合 $A_{1}$ 和 $A_{2}$ ，可以定义方程：

$I_{r}(x,A_{1},A_{2})=1$ when $x\in A_{i} \&\& NN_{r}(x,A)\in A_{i}$ ,

$I_{r}(x,A_{1},A_{2})=0$ when otherwise.

该方程 $I_{r}(x,A_{1},A_{2})$ 表示x与x的第r个最近的邻居是否在同一个子集内。

定义

$T_{r,p}=\frac{1}{pr}\sum_{i=1}^{p}\sum_{j=1}^{r}I_{j}(x_{i},A_{1},A_{2})$ ,

在这里 $p=n$ + $\tilde{n}$ 表示样本的总个数， $x_{i}$ 表示集合A的第i个元素。从直觉上讲，如果 $T_{r,p}$ 小，则说明两类samples $A_{1},A_{2}$ 混合得非常好，表示无异常情况；如果 $T_{r,p}$ 大，则说明两类samples $A_{1},A_{2}$ 有区分度，很多元素与它的邻居集中在某个子集里面，说明 $A_{1}$ 这个集合与 $A_{2}$ 有区分度。

根据文献里面的观点，当p足够大的时候， $(pr)^{\frac{1}{2}}(T_{r,p}-\mu_{r})/\sigma_{r}$ 遵循标准Gauss分布，其参数是 $\mu_{r}=(\lambda_{1})^{2}$ + $(\lambda_{2})^{2}$ , $\sigma_{r}^{2}=\lambda_{1}\lambda_{2}$ + $4\lambda_{1}^{2}\lambda_{2}^{2}$ ,

$\lambda_{1}=n/p=n/(n$ + $\tilde{n})$ , $\lambda_{2}=\tilde{n}/(n$ + $\tilde{n})$ 。

根据传统的Gauss分布Test方法， $\Gamma^{front}$ 和 $\Theta$ 有显著的不同，当 $(pr)^{\frac{1}{2}}(T_{r,p}-\mu_{r})/\sigma_{r}^{2}>\alpha$ ，在这里，参数可以按照以下标准设置：

$\alpha = 1.96$ for $P=0.025$ ，

$\alpha = 2.58$ for $P=0.001$ 。

如果 $\Gamma^{front}$ 和 $\Theta$ 存在显著性偏差，那么说明 $\Gamma^{front}$ 应该返回异常的标识。类似的，如果使用 $\Gamma^{rear}$ 并且它与 $\Theta$ 存在显著性偏差，那么说明 $\Gamma^{rear}$ 应该返回异常的标识。

第二步：关联顺序的挖掘（Mining Existence and Temporal Order）

如果前面的子序列 $\Gamma^{front}$ 与随机选择的子序列 $\Theta$ 有显著偏差，那么说明时序的变化导致了事件的发生， $S\rightarrow E$ 。

如果后面的子序列 $\Gamma^{rear}$ 与随机选择的子序列 $\Theta$ 有显著偏差，那么说明事件导致了时序的变化， $E\rightarrow S$ 。

在Figure 3中，CPU Intensive Program 导致了 CPU Usage，并且 CPU Usage 导致了 SQL Query Alert。

第三步：单调性的影响类型（Mining Effect Type）

现在需要判断时间序列是突增还是突降了，需要引入 $t_{score}$ 的概念。

对于 $\Gamma^{front}=\{\ell_{k}^{front}(S,e_{i}), i=1,\cdots,n\}$ 和 $\Gamma^{rear}=\{\ell_{k}^{rear}(S,e_{i}), i=1,\cdots,n\}$ 而言，其中n是E中的事件个数。 $t_{score}$ 就可以定义为：

$t_{score}=\frac{\mu_{\Gamma^{front}} - \mu_{\Gamma^{rear}}}{\sqrt{\frac{\sigma_{\Gamma^{front}}^{2}+\sigma_{\Gamma^{rear}}^{2}}{n}}}$ .

那么，如果 $t_{score}>\alpha$ ，可以得到 $E\stackrel{-}{\longrightarrow}S$ 或者 $S\stackrel{-}{\longrightarrow} E$ ；如果 $t_{score}<-\alpha$ ，可以得到 $E\stackrel{+}{\longrightarrow}S$ 或者 $S\stackrel{+}{\longrightarrow} E$ 。