TL;DR 目前生产环境中的监控数据主要包括两种类型：指标的时间序列数据 (time series)，例如 CPU 利用率指标，和事件序列数据 (events)，例如 out of memory 时间，论文中提出一种事件和时间序列关联分析的方法来提升故障诊断的效率。主要考虑了事件序列与时间序列间三个方面的问题：事件和时间序列 ① 是否存在关联关系 ② 时间先后顺序 ③ 单调性影响。论文实验部分在仿真数据集和真实数据集中验证了算法的有效性。
Problem Statement 下图展示了事件与时间序列的关系，例如 CPU 密集型的程序会导致 CPU 使用率上升，但是磁盘密集型的程序将对 CPU 使用率没有什么影响，因此 CPU 密集型事件与 CPU 使用率上升事件间存在关联但是磁盘密集型的程序与 CPU 使用率上升没有关联。 当故障发生时，考虑这种事件与时间序列的关联有助于提高故障诊断的效率。
故障诊断时需要考虑事件与时间序列间三个方面的问题：
是否存在依赖关系 ：首先需要根据统计关系方法判断事件与时间序列间是否存在关系，虽然不能代表因果关系但是可以两者是关联的。依赖关系的时间顺序 ：判断事件和时间序列发生的顺序，例如事件E E E S S S E E E S S S S S S E E E 依赖的单调性影响 ：通过判断时间序列上升或者降低导致了事件的发生。给定事件序列或时间类型E E E T E = ( t 1 , t 2 , ⋯ , t n ) T_E=(t_1, t_2,\cdots,t_n) T E = ( t 1 , t 2 , ⋯ , t n ) n n n S = ( s 1 , s 2 , ⋯ , s m ) S=(s_1, s_2, \cdots,s_m) S = ( s 1 , s 2 , ⋯ , s m ) m m m T S = ( t ( s 1 ) , t ( s 2 ) , ⋯ , t ( s n ) ) T_S=(t(s_1), t(s_2),\cdots,t(s_n)) T S = ( t ( s 1 ) , t ( s 2 ) , ⋯ , t ( s n ) ) t ( s i ) = t ( s i − 1 ) + τ t(s_i)=t(s_{i-1})+\tau t ( s i ) = t ( s i − 1 ) + τ τ \tau τ
如上图所示，如果事件e i ∈ E e_i\in E e i ∈ E S S S e i e_i e i S S S
假设ℓ k r e a r ( S , e i ) \ell_k^{rear}(S, e_i) ℓ k r e a r ( S , e i ) e i e_i e i k k k ℓ k f r o n t ( S , e i ) \ell_k^{front}(S, e_i) ℓ k f r o n t ( S , e i ) E E E S S S Γ front = { ℓ k front ( S , e i ) , i = 1 ⋯ n } \Gamma^{\text {front }}=\{\ell_{k}^{\text {front }}(S, e_{i}),i=1 \cdots n\} Γ front = { ℓ k front ( S , e i ) , i = 1 ⋯ n } Γ rear = { ℓ k rear ( S , e i ) , i = 1 ⋯ n } \Gamma^{\text {rear }}=\left\{\ell_{k}^{\text {rear }}\left(S, e_{i}\right), i=1 \cdots n\right\} Γ rear = { ℓ k rear ( S , e i ) , i = 1 ⋯ n } S S S k k k Θ \Theta Θ E E E S S S
Algorithm/Model 论文中主要基于最近邻的方法来分析三个方面的关联关系。
最近邻方法 以Γ front \Gamma^{\text {front }} Γ front Γ front = { ℓ k front ( S , e i ) , i = 1 ⋯ n } ) \left.\Gamma^{\text {front }}=\left\{\ell_{k}^{\text {front }}\left(S, e_{i}\right), i=1 \cdots n\right\}\right) Γ front = { ℓ k front ( S , e i ) , i = 1 ⋯ n } ) Θ = { θ 1 , θ 2 , ⋯ , θ n ~ } \Theta=\left\{\theta_{1}, \theta_{2}, \cdots, \theta_{\tilde{n}}\right\} Θ = { θ 1 , θ 2 , ⋯ , θ n ~ } Z = Γ ∪ Θ = { Z 1 , ⋯ , Z p } Z=\Gamma \cup \Theta = \{Z_1,\cdots,Z_p\} Z = Γ ∪ Θ = { Z 1 , ⋯ , Z p } p = n + n ~ p=n+\tilde{n} p = n + n ~
Z i = { ℓ k front ( S , e i ) , if i = 1 , ⋯ , n θ i − n , if i = n + 1 , ⋯ , p Z_{i}=\left\{\begin{array}{ll} \ell_{k}^{\text {front }}\left(S, e_{i}\right), & \text { if } i=1, \cdots, n \\ \theta_{i-n}, & \text { if } i=n+1, \cdots, p \end{array}\right. Z i = { ℓ k front ( S , e i ) , θ i − n , if i = 1 , ⋯ , n if i = n + 1 , ⋯ , p
定义N N r ( x , A ) NN_r(x, A) N N r ( x , A ) { A \ x } \{A\backslash x\} { A \ x } x x x
定义两个子集合A 1 , A 2 A_1,A_2 A 1 , A 2 x ∈ A x\in A x ∈ A
I r ( x , A 1 , A 2 ) = { 1 , if x ∈ A i & & N N r ( x , A ) ∈ A i , 0 , otherwise I_{r}\left(x, A_{1}, A_{2}\right)=\left\{\begin{array}{ll} 1, & \text { if } x \in A_{i} \& \& N N_{r}(x, A) \in A_{i}, \\ 0, & \text { otherwise } \end{array}\right. I r ( x , A 1 , A 2 ) = { 1 , 0 , if x ∈ A i & & N N r ( x , A ) ∈ A i , otherwise
基于最近邻的假设检验量化形式如下
T r , p = 1 p r ∑ i = 1 p ∑ j = 1 r I j ( x , A 1 , A 2 ) T_{r, p}=\frac{1}{p r} \sum_{i=1}^{p} \sum_{j=1}^{r} I_{j}\left(x, A_{1}, A_{2}\right) T r , p = p r 1 i = 1 ∑ p j = 1 ∑ r I j ( x , A 1 , A 2 )
当p p p ( p r ) 1 / 2 ( T r , p − μ r ) / σ r (pr)^{1/2}(T_{r,p}-\mu_r)/\sigma_r ( p r ) 1 / 2 ( T r , p − μ r ) / σ r
μ r = ( λ 1 ) 2 + ( λ 2 ) 2 , σ r 2 = λ 1 λ 2 + 4 λ 1 2 λ 2 2 λ 1 = n / p ， λ 2 = n ~ / p \mu_{r}=\left(\lambda_{1}\right)^{2}+\left(\lambda_{2}\right)^{2},\quad \sigma_{r}^{2}=\lambda_{1} \lambda_{2}+4 \lambda_{1}^{2} \lambda_{2}^{2}\\ \lambda_1=n/p，\quad \lambda_2=\tilde{n}/p μ r = ( λ 1 ) 2 + ( λ 2 ) 2 , σ r 2 = λ 1 λ 2 + 4 λ 1 2 λ 2 2 λ 1 = n / p ， λ 2 = n ~ / p
高斯分布的假设检验如下，
( p r ) 1 / 2 ( T r , p − μ r ) / σ r > α (pr)^{1/2}(T_{r,p}-\mu_r)/\sigma_r > \alpha ( p r ) 1 / 2 ( T r , p − μ r ) / σ r > α α = 1.96 , P = 0.025 \alpha=1.96,P=0.025 α = 1 . 9 6 , P = 0 . 0 2 5 α = 2.58 , P = 0.001 \alpha =2.58,P=0.001 α = 2 . 5 8 , P = 0 . 0 0 1
判断关联存在及其时序 根据最近邻的假设检验方法，如果Γ front \Gamma^{\text {front }} Γ front Θ \Theta Θ S → E S\rightarrow E S → E Γ rear \Gamma^{\text {rear}} Γ rear Θ \Theta Θ E → S E\rightarrow S E → S
判断单调性影响 主要是判断事件E E E E → + S E \stackrel{+}{\rightarrow} S E → + S E → − S E \stackrel{-}{\rightarrow} S E → − S t t t Γ f r o n t \Gamma ^{front} Γ f r o n t Γ r e a r \Gamma ^{rear} Γ r e a r t t t
t s c o r e = μ Γ f r o n t − μ Γ r e a r ( n 1 − 1 ) σ Γ f r o n t 2 + ( n 2 − 1 ) σ Γ r e a r 2 n 1 + n 2 − 2 ( 1 n 1 − 1 n 2 ) t_{s c o r e}=\frac{\mu_{\Gamma^{f r o n t}}-\mu_{\Gamma^{r e a r}}}{\sqrt{\frac{\left(n_{1}-1\right) \sigma_{\Gamma^{f r o n t}}^{2} +\left(n_{2}-1\right) \sigma_{\Gamma^{r e a r}}^{2}}{n_{1}+n_{2}-2}{\left(\frac{1}{n_{1}}-\frac{1}{n_{2}}\right)}}} t s c o r e = n 1 + n 2 − 2 ( n 1 − 1 ) σ Γ f r o n t 2 + ( n 2 − 1 ) σ Γ r e a r 2 ( n 1 1 − n 2 1 ) μ Γ f r o n t − μ Γ r e a r
其中μ Γ f r o n t \mu_{\Gamma^{front}} μ Γ f r o n t μ Γ f r o n t \mu_{\Gamma^{front}} μ Γ f r o n t σ Γ f r o n t \sigma_{\Gamma^{front}} σ Γ f r o n t σ Γ f r o n t \sigma_{\Gamma^{front}} σ Γ f r o n t n 1 = n 2 = n n_1 =n_2=n n 1 = n 2 = n n n n E E E
t s c o r e = μ Γ f r o n t − μ Γ r e a r σ Γ f r o n t 2 + σ Γ r e a r 2 n t_{s c o r e}=\frac{\mu_{\Gamma^{f r o n t}}-\mu_{\Gamma^{r e a r}}}{\sqrt{\frac{\sigma_{\Gamma^{f r o n t}}^{2} + \sigma_{\Gamma^{r e a r}}^{2}}{n}}} t s c o r e = n σ Γ f r o n t 2 + σ Γ r e a r 2 μ Γ f r o n t − μ Γ r e a r
如果t s c o r e > α t_{s c o r e}>\alpha t s c o r e > α E → − S E \stackrel{-}{\rightarrow} S E → − S t s c o r e < − α t_{s c o r e}<-\alpha t s c o r e < − α E → + S E \stackrel{+}{\rightarrow} S E → + S α = 1.96 , P = 0.025 ; α = 2.58 , P = 0.001 \alpha = 1.96, P = 0.025 ; α = 2.58 , P = 0.001 α = 1 . 9 6 , P = 0 . 0 2 5 ; α = 2 . 5 8 , P = 0 . 0 0 1
整体的算法流程如下图所示：
Experiments 论文中采用的数据集如下所示
实验参数参考论文，实验效果如下：
考虑了计算最近邻时的时间序列相似度指标，整体而言 DTW 效果较好。
Thoughts 
