Vol.28 No.5 曲文龙等：基于广义后级树的事件序列频繁情节挖掘算法 ·493· 中).根据图1的序列BAGDCHBADEBGDFC得 繁的，因此树裁剪不会剪除频繁情节；另一方面任 到每个事件的位置索引，即1-episode的位置列 何频繁情节对应结点的父结点为该情节的子情 表；1-episode的位置列表中A/B/C/D为频繁， 节，一定是频繁的，不会被剪除；因此该频繁情节 插入情节树中，E/F/H不频繁，删除其位置列 生成算法可以发现所有满足约束的频繁情节. 表；对每一频繁1-episode,例如A根据其位置列 基于后缀树的频繁情节发现算法(GSTA)如 表(2)(8)找到其后续事件进行扩充，得到AD位 下： 置列表(8,9)表示情节AD的开始时间8和结束 算法1：基于后缀树的频繁情节发现 时间9，AG位置列表(2,3)，由于AG和AD的出 输人：事件序列S,事件类型E,最小支持度 现次数都小于minsupp,因此不加入情节树且不 min-supp,事件最大间隔maxgap,情节最大持续 再进行扩充 期maxduring. root 输出：频繁情节模式树T. (1)sequence=createlink(null); (2)read S to sequence in order; 42) □5)回(4X9)EF.□3)H (8) 15) 13)(10)(14) (12)(6) (3)for each eEE position-list(e)=NULL; (4)scan sequence to fill position-list(e) D G A1,2)G D(3.4) (8.9)(23) （7.8(11,12)(5.6)(4,5) (12.13) (5)root createtreenode node,null,0, null); G D (3)(7.9 (3.5) (6)for each e∈E 图4广义频繁情节后骤树的构建 (7)if I position-list (e)/Ismin-supp Flg.4 Construction of the generallzed frequent episodes suffix- then tree (8)root.child createnode (node,e,I posi- tion-list(e)l,position-list(e)); 当maxgap=2,对当前频繁情节结点后续两 个事件进行扩充，如2-episode的位置列表为(1， (9)add e to frequent-event; 2)(7,8),其扩充情节为BAG(1,3)BAD(1,4) (10)append node to active-queue; BAD(7,9)BAE(7,10),由于BAD发生次数≥ (11)else free(position-list(e)); (12)while active_queue not empty minsupp,.所以加入树中，并继续扩充为BADC(2, (13)N=fetchfirstnode(active-queue); 5)BADH(2,6)BADE(7,10)BADB(7,11),由 于发生次数均<minsupp,所以不加入树中 (14)set next-event-set=NULL (15)for each eE position-list (e)= maxgap=2时的FrequentEpisodeTree的构造结果 NULL; 见图5. (16)for each posE N.poslist root (17)if pos.next.A frequent-event and (（pos.next.time-pos,endtimes≤maxgap and A2X8)@(1X7XII)©5X15)回(4X9X13)回(3X12) pos.next.time-pos.starttimemaxduring) D(2.46.8) ☑(1,2(7.8) 回3.412,13) and pos.next.A not existed in next-event-set then ⊙(1,47.9) 回3,512.14) (18)add pos.next to next-event-set; 图5 maxgap=2时的广义频繁情节后缀树 (19)for each Enext-event-set Fig.5 Generallzed frequent episodes suffix-tree when maxgap (20)add p to position-list(p.event); =2 (21)for each e frequent-event 定理2该算法可以发现所有满足约束的频 (22)if Iposition-set(e)/(IsI+level(N)- 繁情节， l)≥min-supp then (23)N.child createnode node,e,posi- 证明：算法逐层剪除了不频繁情节所对应的 结点，由定理1，其子结点对应的情节一定是不频 tion-list(e),position-list(e)); (24)append node to active-queue;V o l 。 8 o N 2 . 5 曲文龙等 : 基 于广义后级 树的事件序列频繁情节挖掘算法 . 9 3 4 . ) 中 . 根据图 的序列 1 A B G G A B B H C E D r D D 得 C F 到每个事件 的位置 索 引 , 即 1 一 e iP so d e 的 位 置 列 表 ; 1 一 e iP so de 的位置 列 表 中 A / B / C / D 为频繁 , 插入情 节 树 中 , E / F / H 不频 繁 , 删 除其位 置 列 表 ; 对 每一 频繁 1 一 e iP so ds , 例如 A 根据 其位置 列 表 ( 2 ) ( 8) 找到 其后续 事件进 行扩充 , 得 到 A D 位 置 列表 ( 8 , 9) 表示情 节 A D 的开 始时间 8 和 结束 时间 9 , A G 位置 列表 ( 2 , 3) , 由于 A G 和 A D 的出 现 次数都小于 m isn 叩p , 因 此 不 加 入 情 节树且 不 再进行扩充 . } r o ot } ; 。 ; : C . 、、 、 · n .(79) ( 1 . 3 ) ( 3 , 5 ) F ig . 4 t l . ee 图 4 广义预 赞情节后级树的构趁 C ons t r u e t ion o f t h e 乎 ne ra li z 曰 r r eq ue n t e p l s 回es s u m x · 当 m a x g a p = 2 , 对 当前频 繁情节结 点后 续 两 个事件进行扩 充 , 如 2 一 e iP so d e 的位置 列 表为 (1 , 2) ( 7 , 8 ) , 其扩 充情 节为 B A G ( 1 , 3) B A D ( 1 , 4) B A D ( 7 , 9) B A E ( 7 , 10 ) , 由于 B A D 发生 次数 ) m in su p p , 所 以加 入树中 , 并继续 扩 充为 B A D C ( 2 , 5 ) B A D H ( 2 , 6 ) B A D E ( 7 , 10 ) B A D B ( 7 , 1 1 ) , 由 于发 生 次 数 均 < m isn uP p , 所 以 不 加 入 树 中 . m a x g a p = 2 时的 F r e q u e n t E p iso d e T r e e 的构造结果 见 图 5 . } or ` } 回赢 . 赢烹召 ( 斋赫确 (3 x ,2 ) 赫 , 占 ( 3 . 5 )( ,么 二 2 时的广义频致情节后组树 ,乙` , p 饰 1 扭 古 、于. (2 , 4 ` 6 ’ ” F ig . 5 G e ne ar ll z e d r六月此n t e p i翻川” s u nr x · t溉 叨 he n m a x g a - = 2 定理 2 该算法 可以发 现 所 有 满足约 束的频 繁情节 . 证明 : 算法逐 层 剪除了不 频 繁情节所对 应 的 结点 , 由定理 1 , 其 子结点 对应 的情 节一 定是 不频 繁的 , 因此 树裁剪不 会剪除频 繁情节 ; 另一方面 任 何频 繁情节 对 应 结 点 的父 结点 为该 情节 的子情 节 , 一 定是 频 繁的 , 不 会被剪除 ; 因此 该频 繁情节 生成算法 可以发现 所有满足 约束的频繁情节 . 基于后 缀树的频 繁情节发 现 算法 ( G S T A ) 如 下 : 算法 1 : 基于 后缀树的频 繁情节发现 . 输人 : 事件序列 S , 事件类 型 E , 最 小支 持度 m in 一 su P , 事件最 大 间隔 m ax g ap , 情节 最大持续 期 m a x d u r i n g . 翰出 : 频 繁情节模式树 T . ( 1 ) S e q u e n e e = 。 r e a t e li n k ( n u ll ) : ( 2 ) : e a d 5 t o s e q u e n e e i n o r d e r ; ( 3 ) fo r e a e h e e E p o s i t i o n 一 li s t ( e ) = N U L I J ; ( 4 ) s e a n s e q u e n e e t o fi ll oP s i t i o n 一 li s t ( e ) ( 5 ) r o t = e r e a t e t r e e n o d e ( n o d e , n u ll , 0 , n u ll ) ; ( 6 ) fo r e a e h e 任 E ( 7 ) if 1 p o s i t i o n 一 li s t ( 。 ) l / 1 5 } ) m i n 一 s u p p t h e n ( 8 ) or t . 。 h i ld = 。 r e a t e n o d e ( n o d e , e , }因 5 1 - t i o n 一 li s t ( e ) } , p o s i t i o n 一 li s t ( e ) ) : ( 9 ) a d d 。 t o f r e q u e n t 一 e v e n t ; ( 10 ) a p p e n d n o d e t o a e t i v e 一 q u e u e ; ( 1 1 ) e l s e f r e e ( p o s i t i o n 一 li s t ( e ) ) ; ( 12 ) w h i l e a e t i v e 一 q u e u e on t e m P t y ( 13 ) N = f e t e h fisr t n o d e ( a e t i v e 一 q u e u e ) ; ( 14 ) s e t n e x t 一 e v e n t 一 s e t = N U I J I J ( 1 5 ) f o r e a e h 。 任 E p o s i t i o n 一 li s t ( 。 ) = N U I J L ; ( 16 ) f o r e a e h p o s 任 N . p o s li s t ( 1 7 ) i f 因 5 . n e x t . A f r e q u e n t 一 e v e n t a n d ( p o s . n e x t . t im e 一 p o s . e n d t im e 成 m a x g a p a n d p o s . n e x t . t im e 一 p o s . s t a r t t im e ( m a x d u r i n g ) a n d P o s . n e x t . A n o t e x i s t e d i n n e x t 一 e v e n t 一 s e t t h e n ( 1 8 ) a d d op s . n e x t t o n e x t 一 e v e n t 一 s e t ; ( 1 9 ) fo r 。 a e h P 任 n e x t 一 e v e n t 一 s e t ( 2 0 ) a d d 户 t o p o s i t i o n 一 li s t ( 户 . e v e n t ) ; ( 2 一) fo r e a e h e 任 f r e q u e n t 一 e v e n t ( 2 2 ) i f } p o s i t i o n 一 s e t ( e ) }/ ( } 5 } + l e v e l( N ) - 1 ) ) m i n 一 s u p p t h e n ( 2 3 ) N . 。 h i ld = c r e a t e n o d e ( n o d e , e , 1 p o s i - t i o n 一 li s t ( e ) } , p o s i t i o n 一 li s t ( e ) ) ; ( 2 4 ) a p p e n d n o d e t o a e t i v e 一 q u e u e ;