事件重叠下的频繁串行情节发现算法

事件重叠下的频繁串行情节发现算法卓鹏，肖波，蔺志青北京邮电大学电信工程学院，北京 (100876)E-mail ：charpn@摘 要：在事件序列的数据挖掘中, 一个重要的步骤就是发现频繁情节。

一旦发现频繁情节就能导出描述该序列行为的情节规则。

H. Mannila 等人提出的WINEPI 算法没有考虑多个事件出现在同一时间点的问题，而这一问题在电信告警中却普遍存在。

为此，本文提出一种合适的改进算法，较好地处理了这一问题。

关键词：数据挖掘，事件序列，频繁情节，事件重叠中图分类号：TP3111．引言大多数数据挖掘和机器学习技术都是用于分析无序数据集。

然而，在有的应用领域中， 待分析数据集内在有序。

例如，在通信网络运行中，每天都会产生大量告警。

这些告警就可以视为一个事件序列，其中每个事件均有相应的发生时间。

H. Mannila 等人提出了基于事件序列的数据挖掘算法WINEPI [1], 该算法用于在事件序列中发现频繁情节[1]，从而进一步得出事件间的关联规则。

然而在庞大的通信网络中，同类，异类设备网元的时间无法统一，导致告警事件的时间存在一定的误差，给告警事件的分析带来很大的困难。

故有必要采取时间折叠处理[2]，即在一段时间内发生的事件认为是在同一时间点发生的,这就导致了在同一个时间点存在多个事件的情况出现，我们称这一现象为事件重叠。

在文献[1]中并未考虑这一点，本文将就此提出一个合理的改进方法，使WINEPI 算法适用于事件重叠的情况。

2．概念情节是指事件序列上相互邻近并且满足一定结构关系的事件类型的集合。

事件序列是指一系列先后发生的事件组成的有序事件集合，每个事件都有一个与其相关联的发生时间。

在情节发现中相邻这个概念是用窗口来表示，它是事件序列上满足一定时间宽度要求的一段序列。

频繁情节发现的目的就是在给定的事件序列上，依照给定的窗口宽度，挖掘出所有频繁出现的情节的集合，进而在此基础上发现情节规则，作为对事件序列上事件之间规律的描述。

下面给出相关的基本定义：定义 2.1 给定一个事件类型集合E ，事件是一个形如(, )A t 的二元组，其中A E ∈是一个事件类型，t 是一个整数，它对应于事件发生的时间。

定义 2.2 一个事件序列s是E 上的三元组(,,)s e s T T ，1122(,),(,),,(,)n n s A t A t A t =L 是一个有序的序列事件集合，且(1,...,)i A E i n ∈=，1(1,...,1)i i t t i n +≤=−。

并且，s T 和e T 是整数：s T 是事件序列的起始时间，e T 是事件序列的结束时间，(1,...,)s i e T t T i n ≤<=。

定义 2.3 一个在事件序列s ＝(,,)s e s T T 上的窗口就是这样一个事件序列w = (w , s t , e t )，其中 s t <e T ，且e t >s T ，w 由 s 中所有满足s e t t t ≤<的二元组 (,)A t 所组成。

e s t t −称为窗口w 的宽度，记做()w width 。

给定事件序列s 和一个整数win ，我们把事件序列s 上所有()w width win =的窗口w 构成的集合记作 (,)s win w 。

根据上述定义，一个事件序列的第一个窗口仅包含事件序列中的第一个时间点，最后一个窗口仅包含事件序列中的最后一个时间点。

这样在事件序列两端点附近的事件与在事件序列中间的事件都将在同样多的窗口中得到考虑。

给定事件序列s＝(,,)s e s T T 和窗口宽度win ，那么(,)s win w 中的窗口数目是1e s T T win −+−。

有了上述预备知识后, 接下来开始定义情节(episode) 与子情节(subepisode).定义 2.4 一个情节α就是一个三元组(V , ≤, g)，其中V 为节点集，≤为V 上的偏序关系，:g V E →为从节点到事件类型的映射。

情节α的含义就是：g(V)中的事件以偏序关系≤所指定的次序发生。

情节α的所含的事件数目记作|α|，值为|V |。

如果偏序关系≤是无序的（即对任意 x, y ∈V ，x ≠y ，则 x ≤/y 成立），则称情节α是并行的。

如果偏序关系≤是固定的（即对所有的x, y ∈V ，都有 x ≤y 或 y ≤x ），则情节α是串行的。

如果没有某个事件类型在一个情节中出现两次或两次以上，即映射g 是单射的，则我们称这样的情节是单射情节。

本文下面的讨论只考虑单射串行情节，在不加特别说明的情况下，下面所说的情节都是指单射串行情节。

定义 2.5 如果存在单射:'f V V →，对任意'v V ∈，都有'()(())g v g f v =，对任意,'v w V ∈，有'v w ≤则也有()()f v f w ≤，那么称情节(',',')V g β=≤是情节(,V α=≤,)g 的子情节，记为βαp 。

当且仅当βαp 时，情节α是β的超情节。

如果βαp 且αβ/p ，则记为βαp 。

我们现在考虑情节在事件序列中发生的含义。

直观上，情节的节点需要在序列中有相应的节点，并且事件类型相同，情节的偏序关系也满足。

正式地，情节α＝（V ,≤,g ）在事件序列 1122s=((,),(,),,(,),,)n n s e A t A t A t T T 〈〉L 中发生，当且仅当存在一个从V 的节点到 s 中事件的单射 h:{1,,n}V →L ，满足对于所有的x V ∈，有()()h x g x A =，并且对任何,x y V ∈，如果有x y ≤(x y ≠)，则有()()h x h y t t <。

定义 2.6 已知某事件序列s 和窗口宽度为win , 情节α在s中的出现频率定义为其在所有窗口中出现情节α的比率, 即:|{w (,)| occurs in w}|(,,)|(,)|s win fr s win s win w w αα∈= 给定一个频繁度阈值min_fr ，如果(,,)fr s win α≥min_fr ，则α是频繁的。

我们感兴趣的任务是从一个给定的情节集合ε中，发现所有的频繁情节。

这个集合可以是所有的并行情节或所有的串行情节。

给定s，win ，min_fr ，对应的频繁情节集合我们记为 (,,min_)s F win fr 。

3．事件重叠下的发现算法针对同一时间点存在多个事件这一问题，在并行情节挖掘中显然没有任何影响，但在串行情节中，我们就有必要考虑，如果这几个在同一时间点的事件事实上是存在先后关系的，只是由于各种原因我们在记录的时候把它们弄成同一时间，则我们在对串行情节挖掘时，就有必要考虑其原有的有序性。

故以下只讨论对文献[1]中的算法5，也就是在事件序列中串行情节的识别算法进行分析和改进。

3.1 原算法简要描述算法5使用的是自动机(automaton)[1]机制，它能接受特定的候选情节，忽略其他的输入。

其思想是对于每个串行情节α有一个自动机，在实际程序中有多个自动状态机。

自动状态机的状态变化反映了窗口中出现了α的什么样的前缀。

在每次串行情节α的第一个事件进入窗口的时候，我们对α初始化一个新的自动机。

当这个事件离开窗口的时候，便删除当初初始化的这个自动机。

当α的某个自动机达到完全接收状态，便标志着α已经完全包含在窗口中，并且此时如果没有α的其他自动机已经达到完全接收状态，我们就在α.inwindow中保存当前窗口的起始时间。

当处于完全接收状态的自动机删除时，并且此时如果没有α的其他自动机正处于完全接收状态，就可以对α.freq_count累加相应的保持整个α在窗口中的窗口数。

多个自动机达到同一状态是多余的，因为它们会进行同样的跃迁，产生同样的信息。

保留最近一个到达相同状态的就足够了，因为它也是最后被删除的。

因此，对于α，至多需要|α|个自动机。

对于每一个自动机，我们需要知道它什么时候应该被删除。

于是，我们用一个大小为|α|的数组来记录α的所有自动机的生成时间。

α.initialized[i]用来纪录最近那个达到它的第i个状态的自动机的初始化时间。

∈，为了有效的访问和遍历自动机，按照如下的方式来组织。

对于每一个事件类型A Eα的项，意思是指情节α正在等接受A的自动机存到链表waits(A)。

这个链表包含形如(,)xA t时，链表waits(A)被遍历。

待它的第x个事件。

当窗口滑动进入事件(,)在窗口的一次移动中，waits(A)中的自动机的跃迁保存在链表transitions中。

跃迁用α表示，意思是指情节α得到了它的第x个事件，并且该同类自动机中的最近的初始x t(,,)化时间是t。

对于自动机的旧状态的修正是立即的，但是对于新状态需要等到所有的跃迁都识别完之后才能确定，这是为了不丢掉任何有用的信息。

为了能方便的删除离开了窗口的自动机，建立链表beginsat(t)，通过链表beginsat(t)来索引删除过期的自动机。

3.2 该进算法描述现在我们来考虑事件重叠的合理处理方式，我们可以考虑该时间点上所有告警的全排列，当然在挖掘结果出来后，应该是只有一种排列是对的。

我们对该全排列下所能影响到的自动机全部都进行处理。

例如：同一时间点发生4个告警A, B, C, D。

针对串行情节AÆCÆDÆF，只需对A, B, C, D按AÆBÆCÆD的排列（不唯一）进行处理；对情节GÆDÆBÆAÆE，只需对A,B,C,D按DÆCÆBÆA的排列（不唯一）即进行处理。

实际处理中，我们不可能给出所有全排列，再用情节在全排列中逐一检验。

这是因为要完成全排列非常耗时，而且时间增长是n！，假如12项全排列耗时2秒，则13项全排列要耗时2*13秒！由于事实上最后只有一组排列被认为是正确的，故可以用另一种考虑方式，我们只需对某一排列，如AÆBÆCÆD进行不断遍历，这样每次相关的自动机总能得到一次处理，最多经过4次遍历，所有应该被处理得自动机就都完全得到处理。

对于同一时间有n个告警的情况只需遍历n次就足够了，而不是全排列的n！次。

由于等待第一个事件的自动机都在第一次遍历告警时得到处理，在第n次遍历中被处理的自动机至少是等待第n个事件发生的自动机。

故我们只在第一次遍历中，处理等待第一个事件的自动机，而在以后的遍历中，只处理waits(A)中等待第2个事件的自动机。

这样就可以保证在处理中不会产生多余也不会漏掉可能的自动机。