时序数据与事件的关联分析

文章是:”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。

Figure1

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

(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 nZ_{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}}\}是随机选择的。

对于集合 Ax\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)

Figure3

如果前面的子序列\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

其中参数可以设置为:

\alpha = 1.96 for P=0.025

\alpha = 2.58 for P=0.001

 

算法综述:

algorithm

其中,5,6行是为了计算相关性,D_{r} 是 True 表示 \Gamma^{rear} 有异常,否则表示正常;D_{f} 是 True 表示 \Gamma^{front} 有异常,否则表示正常。

7-13行是 E\rightarrow S 的情形,因为\Gamma^{rear} 异常,同时 \Gamma^{front} 正常,说明事件导致了时间序列的变化。7-13行是为了计算 t_{score} 的范围,判断是显著的提升还是下降。

14-20行是 S\rightarrow E 的情形,因为\Gamma^{front} 异常,就导致了事件的发生。14-20行是为了计算 t_{score} 的范围,判断是显著的提升还是下降。

参数:

时间序列的长度 k 可以设置为第一次达到顶峰的长度,

最邻近的元素个数 r=\ln(p),其中p是样本的总个数。

Figure5

Figure6

其他算法:

(1)Pearson Correlation

(2)J-Measure Correlation

 

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s