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

IT资讯 3670 Views

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

案例是:时间序列是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),事件发生的时间戳是,这里n表示有n个事件发生。时间序列(S)表示为,这里的m表示时间序列的长度。时间序列的时间戳可以选择一个等差序列,等差用来表示,并且,and +

来表示某个事件,表示序列S在事件之后的长度为k的子序列,表示序列S在事件之前的长度为k的子序列。如果事件E与时间序列S之间存在关联关系,那么

 和

应该是不一样的。

定义一:如果事件序列E和时间序列S是相关的,并且,当且仅当和随机选择的子序列分布不一致。

定义二:如果事件序列E和时间序列S是相关的,并且,当且仅当和随机选择的子序列分布不一致,并且和随机选择的子序列分布一致。

定义三:如果事件序列E和时间序列S是相关的,那么或者

定义四:如果 (or ),并且时间序列相比E之前是增加了,那么记为 (or )。如果 (or ),并且时间序列相比E之前是减少了,那么记为 (or )。

方法论:

第一步:最邻近算法(类似kNN)(Nearest Neighbor Method)

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

来做例子, , 是随机选择的,,可以标记为,其中+ when  when +。可以使用记号,其中是随机选择的。

对于集合  而言, 表示中距离x最近的第r个元素,对于两个不相交的集合 和 ,可以定义方程:

 when ,

 when otherwise.

该方程表示x与x的第r个最近的邻居是否在同一个子集内。

定义

,

在这里+表示样本的总个数,表示集合A的第i个元素。从直觉上讲,如果小,则说明两类samples 混合得非常好,表示无异常情况;如果大,则说明两类samples 有区分度,很多元素与它的邻居集中在某个子集里面,说明  这个集合与 有区分度。

根据文献里面的观点,当p足够大的时候,遵循标准Gauss分布,其参数是++,

++

根据传统的Gauss分布Test方法,有显著的不同,当,在这里,参数可以按照以下标准设置:

 for 

 for 

如果存在显著性偏差,那么说明应该返回异常的标识。类似的,如果使用并且它与存在显著性偏差,那么说明应该返回异常的标识。

 

第二步:关联顺序的挖掘(Mining Existence and Temporal Order)

如果前面的子序列与随机选择的子序列有显著偏差,那么说明时序的变化导致了事件的发生,

如果后面的子序列与随机选择的子序列有显著偏差,那么说明事件导致了时序的变化,

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

 

第三步:单调性的影响类型(Mining Effect Type)

现在需要判断时间序列是突增还是突降了,需要引入的概念。

对于而言,其中n是E中的事件个数。就可以定义为:

.

那么,如果,可以得到  或者 ;如果,可以得到  或者 

其中参数可以设置为:

 for 

 for 

 

算法综述:

其中,5,6行是为了计算相关性, 是 True 表示  有异常,否则表示正常; 是 True 表示  有异常,否则表示正常。

7-13行是  的情形,因为 异常,同时  正常,说明事件导致了时间序列的变化。7-13行是为了计算  的范围,判断是显著的提升还是下降。

14-20行是  的情形,因为 异常,就导致了事件的发生。14-20行是为了计算  的范围,判断是显著的提升还是下降。

参数:

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

最邻近的元素个数 ,其中p是样本的总个数。

其他算法:

(1)Pearson Correlation

(2)J-Measure Correlation

相关文章推荐:

1.深度学习与强化学习

欢迎大家关注公众账号数学人生

(长按图片,识别二维码即可添加关注)

如未说明则本站原创,转载请注明出处:NULL » 时序数据与事件的关联分析