基于广义后缀树的事件序列频繁情节挖掘算法

D0I:10.13374/i.issn1001-053x.2006.05.039 第28卷第5期 北京科技大学学报 Vol.28 No.5 2006年5月 Journal of University of Science and Technology Beijing May 2006 基于广义后缀树的事件序列频繁情节挖掘算法 曲文龙12》杨炳儒2》张克君2) 1)石家庄经济学院，石家庄0500312)北京科技大学信息工程学院，北京100083 摘要为了有效地挖掘事件序列频繁情节，提出了一种广义后缀树结构发现和存储频繁情节 此结构利用广义后缀概念并且树中只包含频繁情节结点，用频繁情节发生列表逐层构建的方法提 高了建树效率.该方法充分利用了车件序列的有序特点，可用于发现各类频繁情节，实验结果表 明该算法性能优于Apriori-like频繁情节发现算法， 关健词事件序列：频繁情节；数据挖据；广义后缀树 分类号TP311.13 事件序列是按时间或空间连续发生的事件集 进行了逐层划分，因此可以提高发掘的效率，实 合，事件序列中的频繁情节挖掘广泛应用于金融 验表明该方法优于基于Apriori-like的频繁情节 市场、气象预报、网络报警、web使用模式、基因和 发现算法 蛋白值序列分析等众多领域，因此日益受到重视 和关注.交易数据库中的频繁项集发现山和序列 1事件序列频繁情节相关概念 模式挖掘[2是发现交易内项目之间的关联，而事 对事件序列进行知识发现是一个重要的领 件序列中频繁情节挖掘与此不同，频繁情节是发 域.该问题不同于常规交易数据库和序列数据 现事件序列中重复出现的事件组合，发现的是事库，其数据不是交易的集合而是以时间顺序发生 件之间的关联，原有的算法不能直接使用.Man- 的事件流，因此其支持度需重新定义，还需对频繁 nila等提出发现频繁情节的WinEPI和MinEPI 情节加以约束，以防止组合爆炸和产生无意义模 算法3]，前者采用事件持续窗口限制，后者采用 式. 情节最小发生限制.Casa-Garriga提出采用事件 分析事件序列的一个基本问题发现频繁情 间隔限制发现无限长度频繁情节[4].Frank 节，如“B在A后，C在B后”发生多次，则构成一 Hoppner从时间序列的定性行为（状态序列）发现 个频繁情节，即为由一组事件组成的偏序集3] 频繁情节s],Harms提出了事件序列闭情节发现 频繁情节挖掘即发现在序列中的所有频繁出现的 算法[6] 情节，图1给出一个事件序列. 以上算法都是将事件序列通过情节窗口转换 为交易数据库，然后采用基于Apriori--like序列模 BAG DC HBADE BGD FC时间，t 式发现算法，需要生成大量的候选情节且需对事 图1事件序列 件序列反复扫描计数，因此其效率和可用性受到 Fig.I Event sequence 限制，本文针对事件序列的特点提出了一种广义 定义1给定事件类型的集合E,事件是一 后缀树结构，利用广义后缀建立频繁情节树型结 构，利用上层结点的频繁情节发生列表对搜索空 个二元组(A,t),其中A∈E,t是件发生的时 间.事件类型可以包含多个属性，这里只考虑单 间进行划分，在相应的投影子序列中扫描下层情 节，缩小了模式搜索空间.基于广义后缀树的频 一属性 繁情节发现算法(Generalized Suffix Tree Algo- 定义2并件序列S是件类型E上的一个 三元组(s,T,T),其中： rithm,GSTA)不需生成大量候选并且对搜索空间 S=(A1,t1）,(Az,t2),,（Am,tm）》, 收稿日期：200503-14修回日期：2005-10-11 A,∈E,(i=l,…,n)且t,≤ti+1(i=1,…,n),Ts 基金项目：北京市自然科学基金资助项目(No.4022008) 作者简介：曲文龙(1970一)，男，博士研究生：杨炳儒(1943一). 称为茸件序列开始时间，T。称为事件序列结束时 男，教授，博士生导师 间，并且有T≤t,≤T(i=1,…,n)件序列

5 第 卷 第 期 2 8 0 0 ` 年 月 s 2 北 京 科 技 大 学 学 报 J . . r a o l f o n i U v 路 e i y t f o S c 即 i e c a n C T d h e j . 褪沙 o n e B i U n g 0 V 1 . N 2 8 o . 5 M a 0 0 6 y 2 基于广义后缀树的事件序列频繁情节挖掘算法 l 曲 文 龙 ,2 ) 杨炳 儒 2) 张 克君 2) l) 石家庄经济学院 , 石家庄 0 50 0 31 2) 北京科技大学信息工程学院 , 北京 10 0 83 摘 要 为了有效地挖掘事件序列频 繁情节 , 提 出了一种广 义后 缀树结构 发现和 存储频繁情节 . 此结构利用广 义后缀概念并且树 中只包含频繁情节结点 , 用频繁情节发 生列表逐层构建 的方 法提 高了建树效率 . 该 方法充分 利用了事件 序列的有序特 点 , 可 用于发现各 类频繁情节 . 实验结 果表 明该算 法性能优于 A p ir o ir 一 il k e 频繁情节发现算法 . 关扭词 事件序列 ; 频繁情节 ; 数据挖掘 ; 广义后缀树 分类号 T P 3 1 1 . 1 3 事件序列是按时间或空 间连 续发生的事件集 合 , 事件序列中的频 繁情节挖掘 广泛 应 用 于金 融 市场 、 气象预报 、 网络报警 、 w eb 使用模式 、 基 因和 蛋 白值序列分析等众多领域 , 因此 日益 受到 重视 和 关注 . 交易数据库中的频繁项集发现 〔` ]和序列 模式挖掘 z[] 是发现 交易 内项 目之 间的关联 , 而 事 件序列 中频繁情节挖 掘与此 不 同 , 频繁情节是发 现 事件序列 中重 复出现 的事件组 合 , 发现 的是事 件之 间的关联 , 原 有的算法不 能直接使用 . M an - n il a 等提 出 发现 频 繁情节 的 w i nE IP 和 M i nE IP 算法 3[] , 前者采用 事件持续 窗 口 限 制 , 后 者 采用 情节最 小发 生 限制 . C as a 一 G ar ir g a 提 出 采用 事件 间 隔 限 制 发 现 无 限 长 度 频 繁 情 节4[J . rF an k H 叩p en : 从 时间序列 的定性行为(状 态 序列 )发现 频 繁情节【5 〕 , H a mr s 提 出 了 事件序列 闭情节发现 算法 e[] . 以上算法都是将事件序列通 过情节窗 口 转换 为交易数据库 , 然后 采用基 于 A rP i or i 一 lik e 序列 模 式发现算法 , 需要 生 成大量的候选 情节且需 对 事 件序列反 复扫描计数 , 因此 其效 率和 可用性受到 限制 . 本文针对 事件序列 的特点提 出 了一 种广 义 后缀 树结构 , 利 用 广 义后 缀 建立 频繁情节树型结 构 , 利用上 层结点的频 繁情节发生 列表对 搜索空 间进行划分 , 在 相应 的投 影 子 序列 中扫 描下 层情 节 , 缩 小了模式搜索 空 间 . 基 于 广 义后 缀 树的频 繁情 节 发 现 算 法 ( G e n e r a li z e d s u ff i x T r e e A l g o - irt h m , G ST A )不需生成大量候选 并且对搜索 空间 收稿 日期 : 20 0 5习3 一 14 修回 B 期 : 2 0 0 5 一 10 一 1 1 荃盘项 目 : 北京市 自然科学基金资助项 目 ( N o . 4 0 2 2 0 0 8) 作者简介 : 曲文龙 ( 19 70 一 ) , 男 , 博士研究 生 ; 杨炳 儒 ( 19 43 一 ) , 男 , 教授 . 博士 生导师 进 行了逐 层 划分 , 因此 可以提 高发掘的效率 . 实 验表明该方 法 优于 基 于 A rP i or i 一 h k e 的频 繁情 节 发现算法 . 1 事件序列频繁情节相关概念 对事件序 列进 行知识 发现 是 一 个重 要 的领 域 . 该问 题 不 同于 常规交 易数据库和 序列 数据 库 , 其数据不是 交 易的集合而是以 时间顺序发 生 的事件流 , 因此其支持度需重 新定 义 , 还需对频 繁 情节加 以约 束 , 以 防止 组 合爆炸和 产 生无 意 义模 式 . 分析事件序列 的一 个基 本 问题 发现 频 繁情 节 , 如 “ B 在 A 后 , C 在 B 后 ” 发 生多 次 , 则构成一 个频 繁情节 , 即 为由一 组 事件 组 成的偏序集 3[] . 频 繁情节挖掘即发现在序列中的所有频繁出现的 情节 , 图 1 给出一个事件序列 . - ` ` ` - 山曰- ` 曰- ` ` - ` ` B A G D C H B A D E B G D F C 时I’HJ , r 图 1 . 件序列 F lg . 1 E v e . t se q ue 配e 定义 1 给定 事件类型的集合 E , 书件是一 个二元组 ( A , t) , 其中 A 任 E , t 是 事件发 生 的时 间 . 事件类型 可以包含 多 个属 性 , 这 里 只考虑单 一属性 . 定义 2 事件序列 S 是 书件类型 E 上的一个 三 元组 ( 、 , T s , T e ) , 其中 : S = ( ( A l , r ; ) , ( A Z , t Z ) , … , ( A ” , r 。 ) ) , A , e E 、 ( i = 1 , … , n ) 且 t 、镇 t ` 十 一 ( i = 1 , … , n ) , T , 称为 书件序列开 始时 间 , T 。 称为 事件序列结 束时 间 , 并且 有 T s 镇 t , 镇 T 。 ( i = 1 , … , n ) . 事件序列 DOI: 10. 13374 /j . issn1001 -053x. 2006. 05. 039

Vol.28 No.5 曲文龙等：基于广义后绶树的事件序列频繁情节挖超算法 ·491· S是一组按时间（或空间）有序排列的事件 邻).一种方法是采用窗口定义情节的最大持续 定义3情节a定义为一个三元组(V,≤， 期maxduring,.以情节在所有窗口中的出现频率 g),其中V情节中结点的集合，≤是V上的偏 作为其支持度，此方法的缺点是无法发现超过窗 序，g:V→E是情节中的结点到对应事件类型的 口宽度的频繁情节并且对不同长度的频繁情节使 映射，即在情节中事件g(V)的出现必须满足偏 用统一的窗口.另一方法限制相邻事件的最大时 序≤定义的顺序.|a|表示情节a的长度，|a|的 间间隔maxgap,则包含k个事件的情节的窗口宽 值为情节中的结点数V.情节可以用有向无环 度为(k-1)×maxgap,在事件序列S=(s,T, 图(DAG)表示，见图2 T)中窗口总数为T。-T,+win-1.此方法可发 B 现任意长度的情节，其支持度按下式计算： ⑧ ④⑧© A D fr(a,S,wim)=|S.∈w(S,win)la∈Sl W(S,win)! © (1) 图2情节a,月和y 其中，W(S,win)为所有宽度为win=(k-1)× Flg.2 Eplsodes a,B and y maxgap的窗口集合，Sw表示情节发生的窗口子 序列. 如果关系≤为全序（即Hx,y∈V,必有x≤ y或y≤x),则称a为串行情节，例如a.如果关 2频繁情节广义后缀树 系≤为空（即Hx,yEV,x≠y不存在x≤y或y ≤x),则称为并行情节，例如B.同时包含串行并 后缀树是一棵表示每个序列后缀的一种树状 行的情节称混合情节例如Y.如果g:V→E为 数据结构，主要应用于字符串匹配领域].事件 序列频繁情节发现和字符串模式匹配具有内在相 单射则称为a单射情节，即情节a中不存在重复 似性，所以本文对后缀树结构进行改造，称为频繁 发生的事件. 情节广义后缀树，并应用于频繁情节模式发现. 定义4给定情节B=（V,≤'，g)和a= (V,≤，g),如果存在一个单射f:V'→V,使得 一个长为n的字符串S共有n+（n-1)+ …+1=（n2+n)/2=O(n2)个子字符串S[i. 对于Vv∈V'都有g'(v)=g(f(v)成立，并且 ](1≤i≤j≤n),由于一些子串可能相等，事实 Vv,w∈V',≤'w都有f(v)≤f(w)成立，则 上可以利用后级树在O(n)空间列举其所有后缀 称情节a为情节B的一个子情节，记为二a,子 子串. 情节DAG是情节DAG的子图.例如图1中B 定义7长为n的字符串S的后缀树是一颗 是y的子情节. 有n个叶结点的根树，每一内部结点至少有两个 定义5设B=(V,≤'，g)是a=(V,≤， 孩子结点，每个边用一非空子串标记，每一结点发 g)的子情节且|β|<|a,设单射为f:V→V,若 出的边子串的起始字符均不同.对于每一叶结点 存在v,u∈V(v≠u),使得存在f(v')=v(v'∈ i,从根结点到叶结点经历的每个边标记子串的连 V')但不存在f(u')=u(u'∈V'),必有u≤v不 接，对应从第i个位置开始的字符串S的后缀， 成立，则称为a的前缀子情节，称a为B扩充情 松散后缀树：每边对应一个字符，每个结点至 节.当|a|=|B|+1时，则称β为a的相邻前缀 少包含一个孩子结点，本文数据结构基于松散后 子情节，称a为B相邻扩充情节. 缀树.图3给出了字符串ABCAB$的后缀树和 定义6给定情节a=(V,≤，g)和事件序 松散后缀树，$表示串结束符. 列S=(A,t1),（A2,t2),…,（An,tn),T 利用广义后缀树发现频繁场的主要思想如 T),如果存在一个从情节结点到事件的单射h: 下： V→{1，…，n},使得对x∈V都有g(x)= (1)采用广义后缀树发现和存放频繁情节， Ah()成立，并且对x,yEV(x≠y,x≤y)都有 实现共享前缀压缩.构造件序列的完全后缀树 th(r)<th(y)成立，则称情节在件序列的一次发 可以简单的用于频繁情节发现，但需要存放所有 生 出现的情节，需占用大其内存空间.为了发现至 为发现兴趣情节，必须对限制情节中事件的 少出现minsupp次的频繁情节，必须采用相应策 发生的时间接近度加以限制（但不一定全部相 略裁剪树的规模，实际上只需构建至少有minsupp

o V l . o 2 8 N . 5 曲文龙等 : 荃于 广义后级树 的事件序列频萦情节挖掘算法 S 是 一 组按时间 或空间 ) 有序排列 的事件 ( . 定义 3 情 节 a 定义为一 个三元 组 ( V , ( , g ) , 其中 v 情 节 中结 点的集合 , 镇 是 v 上 的偏 序 , :g v ~ E 是情节中的结点到对应 事件类型 的 映射 , 即在情节中事件 g ( v )的 出现 必 须满足 偏 序簇 定 义的顺序 . }aI 表示情 节 a 的长 度 , }al 的 值为情节中的结点数 } V I . 情节可以 用有向无 环 图 ( D A G )表示 , 见 图 2 . 邻) . 一种方 法 是 采用 窗 口 定 义 情节的最 大持续 期 m ax d ur in g , 以情 节在所 有窗 口 中的出 现 频 率 作为其支持度 , 此 方法 的缺 点是 无法 发现 超过 窗 口 宽度的频 繁情节并且对不同长 度的频繁情节使 用统一 的窗口 . 另一方法限 制相邻事件的最 大时 间间隔 m a x ga p , 则包含 k 个事件的情节的窗 口 宽 度为 ( 走 一 l ) x m a x g a p , 在 事件序 列 S = ( : , T , , T e ) 中窗口 总数为 T 。 一 T : + w in 一 1 . 此方法 可发 现 任意长度的情节 , 其支持度按下 式计算 : f r ( a , S , w i n ) = } S w 任 w ( s , w i n ) } a 任 S w } Iw ( S , w i n ) l "@O 图 2 情节 a . 月和 下 F lg . 2 E P l s 闭es a , 月 a n d y 如果 关系( 为全序 ( 即 V x , y 任 v , 必 有 x 簇 y 或 y 成 x ) , 则称 a 为串行情节 , 例如 a . 如果关 系蕊 为空 (即 V x , y 任 v , x 笋 y 不 存在 x 成 y 或 y 成 x ) , 则称为并行情节 , 例如 夕 . 同时包含串行并 行的情节称混 合情节例如 y . 如果 g : v ~ E 为 单射则称为 a 单射情 节 , 即情节 a 中不存在 重 复 发生 的事件 . 定义 4 给定 情节 口= ( ’V , 成 ` , g ’ ) 和 。 = ( v , 簇 , g ) , 如果存在一 个单射 f : v ` ~ v , 使得 对于 V v 任 V ` 都有 g ` ( v ) = g ( f ( v ) )成立 , 并且 V v , w 任 v ’ , v 镇 ’ w 都有 f ( v ) 镇 f ( w )成立 , 则 称情节 。 为情节夕的一个子情节 , 记为 夕二 。 . 子 情节 DA G 是情 节 DA G 的子 图 . 例如 图 1 中 月 是 y 的子情节 . 定义 5 设 月= ( v ` , 镇 ’ , g ’ ) 是 。 = ( v , 簇 , g )的子情节且 }夕! , 如果存在 一个从 情节结点到 事件的单射 h : v ~ 11 , … , n } , 使得 对 V x 任 V 都有 g ( x ) = A * ( , )成立 , 并且对 V x , y 任 v ( x 笋 y , x 镇 y )都有 t * ( , ) < t 、 ( , )成立 , 则 称情节 在 事件序列 的一 次 发 生 . 为发现兴 趣情 节 , 必 须对 限 制情节中 事件的 发生 的时间接近 度 加 以 限 制 ( 但 不 一 定 全 部 相 ( 1 ) 其中 , w ( S , w i n ) 为所有宽度为 w i n = ( 无 一 l ) x m a x ga p 的 窗 口 集合 , S w 表示 情节发生 的窗 口 子 序列 . 2 频繁情节广义后缀树 后缀 树是一棵表示每个序列后缀 的一种树状 数据结构 , 主要 应用于 字符串匹配 领 域 [,] . 事件 序列频繁情节发现 和 字符串模式 匹配具 有内在相 似性 , 所以本文对 后缀 树结构进 行改造 , 称为频繁 情节广义后缀树 , 并应 用于 频繁情 节模式发现 . 一个长 为 , 的字符串 S 共有 , 十 ( n 一 1 ) 十 … + 1 = ( n Z + , ) / 2 = o ( , 2 )个子 字符 串 s [ i 二 j l l( 成 i 镇 j 毛 , ) , 由于 一 些 子 串可能相 等 , 事实 上可以利 用后 缀树在 O ( n ) 空 间列 举其所有后 缀 子 串 . 定义 7 长 为 n 的字符串 S 的后 缀 树是 一颗 有 n 个叶结点的根树 . 每一 内部结点至 少有两个 孩子结点 , 每个边 用一 非空 子 串标记 , 每一结点发 出的边子 串的起始字符均不 同 . 对 于每一 叶结点 i , 从根结点到 叶结点经 历 的每个边标记子 串的连 接 , 对应 从第 i 个 位置 开 始的字符串 S 的后 缀 . 松散 后缀树 : 每边 对应 一 个字 符 , 每个结点至 少包含一 个 孩子结点 . 本文数据结构基 于 松散后 缀树 . 图 3 给出 了字符串 A B 以B $ 的后 缀 树和 松散后缀树 , $ 表示 串结束符 . 利用 广 义 后 缀 树发 现 频 繁场 的主 要 思 想 如 下 : ( 1) 采用 广 义后 缀树发现 和 存放频 繁情 节 , 实现共享前缀压 缩 . 构造 事件序列 的完全 后缀 树 可 以简单的 用于 频 繁情 节 发现 , 但 需要 存放所有 出现 的情节 , 需 占用大 量 内存空 间 . 为 了发 现 至 少 出现 m isn 叩p 次的频 繁情节 , 必 须 采 用 相应 策 略 裁剪树的规模 , 实际 上 只需构建至少 有m isn u p p

·492· 北京科技大学学报 2006年第5期 N(a).supp,发生位置列表N(a).positionlist,,孩 AB 子指针列表N(a).childlist OB Q B BO CABS oc Oc N(a）.positionlist每一项为(ttar,ted）,表 Q4 ● 示该情节一次发生的开始和结束时间，这样设置 QB CABS CABS BO OB 是为了防止情节重叠.另外采用链表结构存放事 Os $0 Os 件序列，每个结点L(A)存放一个事件(A,t) (a) (b) 包括以下域：事件类型L.event∈E,发生时间L 图3后缰树.(a)ABCAB$的后银树：(b)ABCAB$的松散 time,后续事件指针L.next. 后摄树 性质1一个结点所表示的情节β是其子结 Flg.3 Suffix tree;(a)suffix tree of string ABCAB $(b) loose suffix tree of string ABCAB 点表示的情节a的前缀子情节， 证明：设结点N对应的情节为=(V',≤'， 次发生的频繁场景结点 g'),其子结点N.child对应的情节为a=（V, (2)后缀树中每个叶结点表示一个连续的后 ≤，g),E为事件类型集.由于a=(V,≤，g)是 缀（见图3），但无法发现如B·A(*为对模式无 由B=(V',≤'，g)增加一个后续事件e构成，因 贡献的任意类型事件)等的不连续的情节，因此需 此V=V'Ulei,g=gU(e→E),取V'→V的 对后缀概念扩充，称这种有事件间隙的后缀为广 单射为f(v)=v,由定义4可得B是a的子情节. 义后缀，如B"A“也是序列的后缀.称采用这种 另外任给u∈V(u≠e),必有e主u成立，且|a| 方法构造的频繁不完全松散后缀树为广义后缀 =|β|+1，所以B为a的相邻前缀子情节. 树 定理1子结点所表示的情节的支持度小于 (3)广义后缀使后缀树规模急剧增大，因此 其父结点所表示的情节的支持度， 需施加约束以发现感兴趣情节.常用的方法是采 证明：由于父结点情节a=(V,≤，g)是子结 用情节最大持续窗口maxduring,但这样无法保 点情节B=(V',≤'，g)的前缀子情节，再根据定 证发现所有的频繁情节且最大持续窗口难以事先 义6，每当a=(V,≤，g)发生时B=（V',≤'， 估计.因此本文采用一种相邻事件最大间隙限制 g)也必发生，所以子结点场景的发生次数不大于 maxgap,可以发现任意长度的频繁情节，例如图1 父结点场景的发生次数，由|α|<|B|,可得到| 中当最大事件间隙为3时，第一个事件A的后续 W(S,wina)|<|W(S,wing)l,再根据公式(1) 事件为B,C,A,生长出的长为情节为AB,AC和 的支持度定义，可得结论. AA. 该定理表明频繁情节具有与交易数据库中频 (4)对长序列构造完全后缀树时间空间消耗 繁项集apriori特性相似的性质，因此可在树生长 较大，本文提出一种频繁情节位置逐层扩展方法， 的每一层进行支持度剪枝，不会丢失频繁情节. 子结点利用父结点频繁情节位置列表生成，以逐 基于广义后缀树的频繁情节发现算法(GS 层构造广义后缀树.方法利用频繁情节位置列表 TA)首先扫描序列得到所有频繁1-情节的发生 实现对序列的逐层划分，在相应的投影子库上进 位置集，满足最小支持度minsupp的加入情节树 行情节计数，缩小了搜索空间.树的每个结点包 中；对每一频繁1-情节利用其发生位置集，得到 括事件类型E,支持计数supp,频繁情节位置列 所有满足约束的后续事件及极其发生位置集，将 表positionlist,发生时间(tar,tend),利用这种广 频繁后续事件作为该1-情节的孩子结点插入情 义后缀树结构，可以发现满足约束的所有频繁情 节树中；此过程反复进行直到没有后续频繁事件 节 为止.每当一结点的所有后续事件发生位置集产 3 广义后缀树频繁情节挖掘算法 生后，释放该结点的发生位置集，以减少空间耗 费 定义8广义后缀情节树是一颗根树，每个 图4说明树构造过程(maxgap设为1， 结点N对于一个情节a,可以有多个子结点 maxduring=oo,minsupp为2)，由于图1例子中 childlist,情节a表示从根结点root到该结点N 未给出事件发生的准确时间，因此以其位置序号 的结点标签label串连组成的情节.每个结点包 视为时间.其中加外框的结点表示频繁情节（加 括如下域：件标签N(a).label∈E,发生次数 入树中)，无外框的表示不频繁情节（不加入树

北 京 科 技 大 学 学 报 2 0 0 ` 年第 s 期 图 3 后级树 . 《a) A B 〔消旧 $ 的后级树; 《b) A 刀c 今B $ 的松散 后级树 R g . 3 S u m x t溉 ; ( a ) s . m x t 限 o f s td n g A B CA B $ : `b ) I ~ s . m x t 附 o f s td n g 月仪消B $ 次发生的频 繁场景结点 . ( 2) 后缀 树中每个 叶结点 表示 一个 连续的后 缀( 见图 3) , 但无 法发现 如 B ’ A ( * 为对模式无 贡献的任意类型事件 )等的不连 续的情节 , 因此 需 对后缀概 念扩充 , 称这 种有事件间隙的后 缀为广 义后缀 , 如 B ’ A ’ 也是 序列 的后缀 . 称采用 这 种 方法构造 的频 繁不 完全 松 散后 缀树 为 广 义后 缀 树 . ( 3) 广 义后 缀使后 缀 树规 模急 剧 增大 , 因 此 需施 加约 束以发现感兴趣情节 . 常用的方法 是采 用情节最 大持续窗 口 m ax d ur i n g , 但这 样无 法 保 证发现所有的频繁情节且 最大持续窗口 难以事先 估计 . 因此本文采用一 种相 邻事件最 大间 隙限制 m ax ga p , 可以发现 任意 长度的频繁情节 , 例如 图 1 中当最 大事件间隙为 3 时 , 第一 个 事件 A 的后续 事件为 B , C , A , 生长出的长 为情节为 A B , A C 和 A A . ( 4 ) 对长 序列构造 完全 后缀树时间空 间消耗 较大 , 本文 提出一种频繁情节位置逐 层扩展 方法 , 子结点利用父结点频 繁情节位置 列 表生 成 , 以逐 层构造广 义后缀树 . 方法 利用频 繁情节位置 列表 实现对序列 的逐 层 划 分 , 在 相应 的投 影 子 库上进 行情节计数 , 缩 小了搜索空 间 . 树 的每个 结 点包 括事件类 型 E , 支 持计 数 s叩p , 频 繁情节 位置 列 表 娜 i t i o n li s t , 发生 时 间 ( t s t ar t , t 。耐 ) , 利 用这 种广 义后 缀树结构 , 可以发现 满足 约束的所有频繁情 节 . 3 广义后缀树频繁情节挖掘算法 定义 8 广 义 后缀 情 节 树是 一颗 根 树 , 每个 结点 N 对 于 一 个 情 节 a , 可 以 有 多 个 子 结 点 e h ild li s t , 情 节 。 表示 从 根结 点 or t 到 该结点 N 的结点标 签 lab el 串连 组 成 的情节 . 每个 结点 包 括如 下 域 : 事件标 签 N ( a) . lab el e E , 发 生 次 数 N ( 。 ) . , u p p , 发生 位置 fJ 表 N ( 。 ) . 因 s i t i o n li s t , 孩 子指针列表 N ( a ) . e h i ld li s t · N ( 。 ) . op s i t i o n zi s t 每一 项为 ( t : t o r t , r e间 ) , 表 示该情节一次发生 的开 始和 结束时间 , 这 样设 置 是为了防止情节重 叠 . 另外采用 链表结构存放事 件序列 , 每个 结 点 L ( A ) 存放一 个 事件 ( A , t) . 包括以下域 : 事件类型 L . e ve nt 任 E , 发生时间 L . it m e , 后 续 事件指针 L . en xt . 性质 1 一 个结点所表示的情节 月是其子结 点表示 的情节 a 的前缀子情节 . 证明 : 设结点 N 对应 的情节为月= ( v ` , 簇 ` , g ` ) , 其子 结点 N . hc il d 对 应 的情节 为 。 = ( v , 簇 , g ) , E 为事件类型 集 . 由于 。 = ( v , 镇 , g )是 由 月= ( v ` , 镇 ’ , g ’ )增加一 个后续事件 尸 构成 , 因 此 v = v ` U } 。 } , g = g ’ U ( e ~ E ) , 取 v ’ ~ v 的 单射为f( v) = v , 由定义 4 可得 P 是 。 的子情节 . 另外任给 “ 任 V ( “ 笋 召 ) , 必有 。 笠 “ 成立 , 且 }aI = }尹} + 1 , 所 以 P 为 a 的相邻前缀子情节 . 定理 1 子结点 所表示 的情节的支持度小于 其父结点所表示 的情节的支持度 . 证明 : 由于父 结点情节 。 = ( V , ( , g )是子结 点情节 月= ( V’ , 簇 ’ , g ` )的前缀子情节 , 再根据定 义 6 , 每当 a = ( v , 簇 , g ) 发 生 时 夕= ( v ’ , 簇 ` , g ` )也 必发 生 , 所以子结点场景的发生次数不大于 父结点场景的发 生 次数 , 由 }aI < }川 , 可得 到 } w ( s , w i n 。 ) I < } W ( s , w i n , ) I , 再根据公式 ( l ) 的支持度定义 , 可得结论 . 该定理 表明频 繁情节具有与交 易数据库 中频 繁项集 a rP i or i 特性 相似的性质 , 因此 可在树生长 的每一层进 行支持度剪枝 , 不会丢失频繁情节 . 基于 广义 后缀 树的频 繁情 节发 现算 法 ( G S - T A )首先扫描序列 得到 所有频 繁 1 一情节 的发生 位置集 , 满足 最 小支持 度 m isn 叩p 的加入 情节树 中 ; 对 每一频 繁 1一情节 利用其发 生 位置 集 , 得 到 所有满足 约束的后续事件及极 其发生 位置 集 , 将 频 繁后续 事件作为该 1一情节的孩 子结点插 入 情 节树中; 此 过程 反 复进 行直到 没有后 续频 繁事件 为止 . 每当一结点 的所有后续事件发生位置集产 生后 , 释 放该结点的发 生 位 置 集 , 以 减少 空 间耗 费 . 图 4 说 明 树 构 造 过 程 ( m ax g aP 设 为 1 , m a x d u r i n g = co , m i n s u p p 为 2 ) , 由于 图 l 例子 中 未给出事件发生 的准 确时间 , 因此 以 其位置 序号 视 为时间 . 其中加外 框 的结点表 示频 繁情节 ( 加 入树中 ) , 无 外 框的 表 示 不 频 繁 情 节 ( 不 加 入 树 城 · 于 ·

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 ;

·494· 北京科技大学芈报 2006年第5期 (25)free(N.poslist); 有频繁情节p.episodes及其支持计数p.support, (26)return root; 加入到频繁模式集FES中.(3~10)对频繁模式 算法说明：(1)~(2)初始化存放序列的空链， 集的每一模式p,以所有前缀为规则前件后缀为 将序列读入链表中，(3)~(4)初始化每个事件(1 规则后件生成事件预测规则，其信任度为情节力 -情节)的位置列表，扫描序列以建立每个1-情节 的支持度与前件情节g的支持度的比值.由于q 的位置列表集.(5)建立模式树根结点.(6)~ 为p的子情节，因此g的支持度不小于p的支持 (11)对所有出现次数大于最小支持度的事件：将 度，所以g必存在于频繁模式集FES中.travel- 该事件加入频繁1-情节集、将该事件添加为根结 frequent-epi_tree采用深度优先遍历频繁事件树 点的孩子结点、将结点加入待处理队列中，对出现 T,每一结点的情节由父结点的情节和本结点的 次数大于最小支持度的事件释放其位置列表集. 标签node.label串联得到， (12)~(13)若待处理队列不空，反复取出队头结 点N处理.(14)~(15)清空当前情节的后续事 4对并行和混合情节的处理方法 件集，清空每一频繁件的发生位置集，以记录结 算法同样适用于并行和混合情节频繁情节发 点N的后续事件的发生位置.（16)~(18)若当 现，只需在频繁情节树逐层构造过程中允许进行 前情节的后续事件为频繁事件、满足限制，若其位 并行情节扩充.例如设父结点对应的频繁情节为 置未出现在后续事件集中则添加.(19)~(20)对 (AB),需对(AB〉位置集中所有满足限制的后续 后续事件集的每一事件，将其发生位置添加到所 事件的组合进行扩充，设为(AB〉后续出现的满足 属事件类型的发生位置集中，(21)~(24)对当前 限制的事件有C,D,E,设允许的最大并行事件 情节N每一类型的后续事件，若其支持度大于最 为2，则其扩充为(ABC),〈ABD),〈ABE),〈AB 小支持度则创建N的孩子结点，加入该孩子结点 (CD)》,(A(DE)》,(A(CE)》,()表示其中件 到待处理队列中，(25)结点N处理完成后释放 先后顺序无限制.前三个为满足限制的串行扩 其发生位置列表，以减少内存占用， 充，后三个为满足限制的并行扩充，算法中可根据 通过遍历构建的频繁情节模式树可以生成事 发掘任务添加限制，如情节最大持续期等 件预测规则，算法描述如下， 算法2：事件预测规则生成算法 5实验结果 输人：频繁情节模式树T,最小支持数min- 实验目的主要是将本文GSTA算法与基于 supp,最小信任度minconf,序列总长度len. 候选生成的(Aprior-like)的频繁情节发现算法进 输出：预测规则集ruleset. 行比较，以检验其优越性，算法采用VC++6.0 (1)FES=NULL; 实现，运行环境为plII800,256M内存，win2000 (2)FES travel-frequent-epi-tree (T, 平台.实验数据采用Geneva大学ExPASy(Ex- currentpatterr='); pert Protein Analysis System)服务器上的 (3)for each p∈FES PROSITE数据库(http:∥www.expasy.org/ (4)for i=1 to length(p)-1 prosite/index,html)中的表达蛋白序列， (5)generate rule R.rule=p[1..i ]p[i+ PROSITE包含具有生物学意义的DNA和表达 1..length(p)] 蛋白模式，主要用于识别蛋白质序列所属类别. (6)find episodes g in FES such that g.pat- 因为数据集中的模式是已知的，所以实验目的主 tern=p[1..i] 要是对比验证该算法的有效性和优越性.选择 (7)R.supp=p.supp/(len/length(p)); DNA失配修复蛋白(DNA mismatch repair pro- (8)R.conf=p.supp/q.supp teins1,PROSITE entry PS00058)的79个序列组 (9）ifR.supp≥min-supp and R.conf≥ 合并视为一个件序列，将其空间顺序视为时间， min-conf then 在不同序列之间放置结束符$以避免情节跨越不 (10)add R to ruleset; 同序列.序列的总长度为53130，包含20种不同 (11)return ruleset; 事件类型，失配修复蛋白的特征模式为 算法2说明：(1)初始化频繁情节集合FES GFRGEAL.以下对本文提出的GST-based算法 为空.(2)调用travel-.frequent-epi-tree得到所 进行有效性和可伸缩性实验，并与Apriori-like算

. 4 9 4 . 北 京 科 技 大 学 学 报 20 0 ` 年第 s 期 ( 2 5 ) f r e e ( N . p o s li s t ) ; ( 2 6 ) er t u rn or t ; 算法说 明 : ( l) 一 ( )2 初始化存放序列 的空链 , 将序列 读入链 表中 . ( 3) 一 ( 4) 初始化每个 事件 ( 1 一情节 )的位置 列表 , 扫描序列 以建立 每个 1一情节 的位置 列表 集 . ( 5) 建立 模式树根结点 . ( 6) 一 ( 1 1) 对所有出现 次数大于 最小支持度的事件 : 将 该事件加入频繁 1一情节集 、 将该事件添 加 为根结 点的孩 子结点 、 将结点加入待处理 队列 中 , 对出现 次数大于最小支持度的事件释 放其位置 列 表集 . ( 12 ) 一 ( 1 3 )若待处 理 队列不 空 , 反 复取 出队头 结 点 N 处 理 . ( 1 4 ) 一 ( 1 5) 清空 当前情节 的后 续事 件集 , 清空每一频 繁事件的发生位置 集 , 以记录 结 点 N 的后 续事件的发 生 位置 . ( 16) 一 ( 18) 若当 前情节的后续 事件为频 繁事件 、 满足限制 , 若其位 置未出现 在后续事件集中则添加 . ( 19) 一 ( 2 0 )对 后续事件集的每一 事件 , 将其发生 位置 添加到 所 属事件类型的发生 位置集中 . ( 21 ) 一 ( 2 4 )对 当前 情节 N 每一 类型 的后续事件 , 若其支持度大于最 小支持度则 创建 N 的孩子结点 , 加入该 孩 子结点 到待处理 队列 中 . ( 2 5) 结点 N 处 理 完成后 释 放 其发 生 位置列 表 , 以减少 内存占用 . 通过 遍历 构建的频 繁情节模式树可以生成事 件预 测规 则 , 算法描述如 下 . 算法 2 : 事件预测规 则 生成算法 . 翰人 : 频繁情节模式树 T , 最小支持 数 m i n - s u p p , 最小信任度 m i n co n f , 序列总长 度 l e n . 输出 : 预测规则 集 ur les et . ( l ) F E S = N U I J L ; ( 2 ) F E S = t r a v e l 一 f r e q u e n t 一 e p i 一 t er e ( T , e u r r e nt p a t t e r r = ` ’ ) ; ( 3 ) fo r e a e h P e F E S ( 4 ) fo r i = 1 t o l e n g t h ( p ) 一 l ( 5 ) g e n e r a t e r u l e R . r u l e = P [ 1 二 i ]” P [ i + l 二 l e n g t h ( P ) ] ( 6 ) fi n d e p iso d e s 9 i n F E S s u e h t h a t 9 . p a t - t e r n = P [ 1 二 i ] ( 7 ) R . s u p p = P . s u p p / ( l e n / l e n g t h ( P ) ) ; ( 8 ) R . co n f = p . s u p p / q . s u p p ( 9 ) i f R . s u p p 妻 m i n 一 s u p p a n d R . e o n f ) m i n _ e o n f t h e n 10 ) a d d R t o r u l e s e t ; 1 1 ) r e t u r n r u l e s e t : 算法 2 说 明 : ( l) 初 始化频 繁情节 集 合 FE S 为空 . ( 2 ) 调 用 t r a v e l 一 f r e q u e n t 一 e p i 一 t r e e 得 到 所 有频 繁情节 p . eP i sod es 及 其支持计数 P . s 叩op rt, 加入 到频 繁模式集 F E S 中 . ( 3一 1 0) 对 频 繁模式 集的每一 模式 P , 以所有前缀 为规 则前件后缀 为 规则后 件生成事件预测 规 则 , 其信任度 为情节 P 的支持度与前件情节 q 的支持度的比值 . 由于 q 为 P 的子情节 , 因此 q 的支持度不小于 P 的支持 度 , 所以 q 必 存在于频繁模式集 F E s 中 . t ar ve ! - fr eq ue nt 一 e iP 一 tr e e 采用深 度优先遍 历频繁事件树 T , 每一结点的情节由父结点的情节和 本结点的 标签 n o d e . lab el 串联得 到 . 4 对并行和混合情节的处理方法 算法 同样适 用于 并行和混合情节频 繁情节发 现 , 只需在频繁情节树逐 层 构造 过 程 中允 许进 行 并行情节扩充 . 例如设 父结点对应 的频 繁情节为 , 需对 位置 集中所有满足 限制的后 续 事件的组 合进行扩充 , 设为 后续出现的满足 限制的事件有 C , D , E , 设 允许的最大并行 事件 为 2 , 则其扩 充 为 , , , ( A B ( C D ) ) , , , ( )表示 其 中 事件 先后 顺序无 限 制 . 前三 个 为满 足 限制的 串行扩 充 , 后 三个为满足限制的并行扩充 , 算法 中可根据 发掘 任务 添加 限制 , 如情节最 大持续期等 . 5 实验结果 实验 目的 主要 是 将本文 G S T A 算法与基 于 候选生成的 ( A rP i or 一 h k e ) 的频 繁情节发现 算法进 行比较 , 以检验其优越性 , 算法 采用 v C + + 6 . 0 实现 , 运 行环 境为 p l l l 8 0 0 , 2 5 6 M 内 存 , w in2 0 OO 平台 . 实验 数据采用 G e n e v a 大学 E x P A s y ( E x - p e r t p or t e i n A n a l y s i s S y s t e m ) 服 务 器 上 的 P R OS IT E 数 据 库 ( h t t p : / w w w . e x p a s y . o r g / p or s i t以i n d e x . h t m l ) 中 的 表 达 蛋 白 序 列 , P R O SI T E 包含具 有 生 物 学 意 义 的 D N A 和 表达 蛋 白模式 , 主要 用于 识别蛋 白质序列 所 属 类别 . 因为数据集中的模式是 已知的 , 所以 实验 目的主 要 是 对 比验证 该算法 的有效性 和优越 性 . 选 择 D N A 失配 修复蛋 白 ( D N A m i s m a t e h r e p a i r p or - t e i n s l , P R ( )S I T E e n t r y P印0 0 5 8 )的 7 9 个序列组 合并视为一 个 事件序列 , 将其空间顺序视 为时 间 . 在不 同序列之 间放置结束符班 以避 免情节跨越 不 同序列 . 序列的总长度为 5 3 13 0 , 包 含 20 种不 同 事 件 类 型 , 失 配 修 复 蛋 白 的 特 征 模 式 为 G F R G E A L . 以 下对 本 文 提 出 的 G S T 一 bas ed 算法 进行有效性和 可伸缩性实验 , 并与 A rP i or i 一 ilk e 算

Vol.28 No.5 曲文龙等：基于广义后绶树的事件序列频繁情节挖超算法 ·495· 法的运行时间进行对比实验 实验3：考察本文GSTA算法与Apriori-like 实验1：考察不同最小支持数minsupp下发 算法在相同条件下的运行时间.蛋白质序列总长 现的不同长度频繁情节的数目.表1为最小间隔 度为53130，取maxgap=1,maxduring=o,两种 maxgap=1和maxduring=∞时的发掘结果，表2 频繁情节发现算法在最小支持数minsupp取不同 为最小间隔maxgap=2和maxduring=o时的发 值时的运行时间见图7.可见本文算法的运行时 掘结果.随着最小支持数minsupp的增大，得到 间小于Apriori-like的算法，分析其原因：一是算 的各长度(L2~L7)的频繁情节数会减少，当 法不需生成大量候选情节，二是在情节计数时只 maxgap=2时产生的得到各长度的频繁情节数目 需对逐层划分的投影子集进行搜索，不需对序列 均大于maxgap=1的频繁情节数目.实验中发现 进行多次完全扫描 了特征频繁模式GFRGEAL 60 50 表1不同支持数下的频繁情节数(maxgap=1) ●Apriori-like 40 GSTA Table I Number of requent episodes with different min-support 30 maxgap=1) Minsupp L2 L3 14L5 L6 L7 10 382 1771394 238 187 153 06102六30403060708090T00 最小支持数阀值 20 363 554 98 65 48 38 40 315 107 33 20 14 8 图7GSTA与Aprior-lke算法运行时间比较 Flg.7 Runtime comparison between GSTA algorithm and Apri- 60 279 38 8 5 3 1 ori-like algorithm 80 247 10 0 0 0 0 表2不同支持数下的频紫情节数(mAxgaP=2) 6 结论 Table 2 Number of frequent episodes with different min-support 现有的基于Aprior-like的频繁情节挖掘算 maxgap 2) 法，采用候选生成一剪除的试错策略，其缺点是需 Minsupp 12 L3 14 LS 16 L7 生成大量候选情节且需要反复进行件序列扫 40 361 1731390 321 376485 描.针对事件序列的有序特性，提出一种基于广 80 315 45564 41 50 59 义后缀树的事件序列频繁情节挖掘算法GSTA. 140 266 68 5 2 3 该方法采用广义后缀树发现和存储频繁情节，树 200 217 60 0 0 0 生成过程采用广度优先逐层剪枝策略以缩减树规 模，采用频繁情节发生位置集实现搜索空间的划 实验2：考察不同规模数据下运行时间.蛋白 质序列总长度为53l30,取maxgap=1,maxduring 分，使得模式搜索只在投影子集中进行，有效缩减 =o∞.由图6可见当minsupp取值较小时，随数 了搜索空间，提高了模式发现效率，实验表明该 算法优于基于Aprior--like的频繁情节发掘算法. 据规模增大，频繁情节数目迅速增加，运行时间增 进一步的工作是发现事件序列频繁闭情节，以有 长速度较快.而当minsupp适当取值时，运行时 效的缩减模式空间，进一步提高发掘算法的性能. 间随数据规模的增长接近线性，表明该算法具有 较好的可伸缩性 参考文献 30 25 -e-minsupp=10 [1]Agrawal R,Srikant R.Fast algorithms for mining association 20 ◆minsupp-20 rules//Proceedings of the 20th International Conference on minsupp=30 15 Very Large Data Bases.Santiago.1994:487 1 [2]Srikant R.Agrawal R.Mining sequential patterns:generaliza- 以 tions and performance improvements//Proceedings of the In ternational Conference on Extending Database Technology. 20 30 40 数据集规模kB Avignon,1996:3 (3]Mannila H.Toivonen H,Verkamo A 1.Discovery of frequent 图6不同数据规模下算法的运行时间 episodes in event sequences.Finland:Department of Computer Flg.6 Algorithm runtime of dlfferent data scales Science,University of Helsinki,1997

V o l 。 2 8 N o 。 5 曲文龙等 : 基千 广义后级树 的事件序列频滚情节挖拥算法 . 4 9 5 法 的运行时间进行对 比实验 . 实验 1 : 考察不 同最小 支持数 m i n su p p 下发 现 的不 同长度频繁情节的数 目 . 表 1 为最小间隔 m a x g a p = 1 和 m a x d u r i n g = co 时的发掘结果 , 表 2 为最 小间隔 m a x g a p = 2 和 m a x d u r i n g = co 时的发 掘结果 . 随着最小支 持数 m i n su p p 的增大 , 得 到 的各长 度 ( L Z 一 L 7 ) 的频 繁情 节 数 会 减少 , 当 m a x ga p = 2 时产生 的得 到 各长度的频 繁情节数 目 均大于 m ax g ap = 1 的频繁情节数 目 . 实验中发现 了特征频 繁模式 G F R G E A L 实验 3 : 考察本文 G S T A 算法 与 A p r i o r i 一 li k e 算法在相同条件下的运行时间 . 蛋 白质序列 总长 度为 5 3 13 0 , 取 m a x g a p = l , m a x d u r i n g = co , 两 种 频繁情节发现 算法 在最 小支持数 m isn 叩p 取不 同 值时的运 行时间见图 7 . 可见本文 算法 的运 行时 间小于 A rP ior i 一 lik e 的算法 , 分析其原 因 : 一 是 算 法 不需 生成大量候选情节 , 二是 在情节计数时只 需对逐 层划 分的投 影 子 集进行搜索 , 不 需 对 序列 进行多次完全扫描 . 60 50 裹 l 不 同支持数下 的频萦情节数 《 . 旧犯. p 二 l) aT b l e I N帅be r o f r 叫 ue n t e P i s司xl es w i th d . r fe 悦 n t 耐 n 一 s u P脚rt 《m a x g a p 二 l ) M i n s u P P ZL L 3 I J 4 L S 6L L 7 10 38 2 1 7 7 1 3 9 4 2 38 18 7 15 3 20 3 6 3 5 5 4 98 6 5 4 8 3 8 4 0 3 15 10 7 3 3 2 0 14 8 6 0 2 7 9 38 8 5 3 1 80 24 7 10 0 0 0 0 ~ A P r i o ir 一 lik e - ` ~ 0 G S I’A 4 nUn 几j, 宜岔卑间之 ` 听 丫卜一一一~ 山 一 ~ 0 三 , 伙 . 认 , l。 ` 认 , 认 , 仪 汁 一 森 。认 双。 U I U ` U J U 斗U J U O U I U 6 U , U I 几月」 最小支持数闹值 图 7 G s T A 与 A p南伟“ ke 算法运行时间比较 F lg . 7 R u n ti嵌 co m aP d so n 比 t w e n G盯 A a l沙 d t h m a n d A p d · 耐 · Iik e a l go d th m 衰 2 不 同支持橄下 的知 , 情节橄 《 . . 比 , p 二 2) T a b l e Z N姗晚 r Of f找门 ue n t e p l .目 es iw t h d f fe enr t m l n 一 s u p侧甘 t 《 m a x 朗p 二 2 } M i n s u P P LZ L 3 4L L S 6L L 7 4 0 3 6 1 17 3 1 3 9 0 3 2 1 3 7 6 4 8 5 80 3 1 5 4 5 5 6 4 4 1 5 0 5 9 14 0 2 6 6 6 8 5 2 3 6 2 0 0 2 1 7 6 0 0 0 0 实验 2 : 考察不 同规 模数据下运 行时间 . 蛋 白 质序列总 长度 为 5 3 1 3 0 , 取 m a 犯 a p = 1 , m a x d u r i n g = co . 由图 6 可 见当 m i n su p p 取值较小时 , 随数 据规模增大 , 频繁情节数 目迅速 增加 , 运行时间增 长速度较快 . 而 当 m isn 叩p 适 当取值时 , 运 行时 间随数据规 模的增长接近 线性 , 表明该算法 具 有 较好的可伸缩性 . 6 结论 现有 的基 于 A rP io 卜 h k e 的频 繁情 节挖 掘算 法 , 采用候选生成一剪除的试错策略 , 其缺点是需 生成大量候选情节且 需 要 反 复进 行事件序列 扫 描 . 针对 事件序列 的有序特性 , 提 出 一 种基 于 广 义后 缀树的 事件序列 频 繁情节挖 掘算法 G S T A . 该方 法 采用 广义后 缀树发 现 和 存储频 繁情节 , 树 生 成过 程采用广度优先逐 层剪枝策略以缩减树规 模 , 采用 频 繁情 节发生 位置 集实 现 搜索空 间 的划 分 , 使得 模式搜索 只在投 影子 集中进行 , 有效 缩 减 了搜索空 间 , 提高 了 模式发 现 效率 . 实 验表明该 算法 优于 基 于 A p ir or 一 h k e 的频 繁情 节发掘算法 . 进一步 的工 作是发现 事件序列 频 繁闭情节 , 以有 效的缩减模式空 间 , 进一步提高发 掘算法的性能 . 二 塑 二华 图 ` 不同数据 数 规 据 模 集 下 规模 算法 爪 B 的运 华 行时间 F lg . 6 A lgo d th m r u n t im e of d l fet 件at d a t a aSC les 参 考 文 献 [ l ] gA r a w a l R , S r ik a n t R . F a s t a gl o r i t h m s of r m i n i n g 。 ~ i a t ion r u l e s / P ocr e e d i n g s o f t h e 2 0 t h I n t e rn a t i o n a l ( 二o n f e r e n e e o n V e r y aL r g e aD t a aB se . aS n t iag o . 19 9 4 : 4 8 7 [ 2 了 S r i k a n t R . gA ar w a l R . M i n i n g s e q u e n t i a l 邵 r r e m s : 沙 n aer li z a - t i o n s a n d p e r of rm a n e e im p or v e m e n t s / P ocr e d : n g s o f t h e I n - t e rn a t i o n a l oC n f e r e n e e o n E x t e n d i n g D a t a b , T ce h n o吨 y . A v i g on n . 19 9 6 : 3 〔3 ] M a n n i l a H . T o ivo n e n H , v e r k a m o A 1 . D i` o v e r y o f f r叫 u e n t e p i , x l e s i n e v e n t s eq u e n e e s . F i n l a n d : D e Pa r t m e n t o f oC m P u t e r 灰i e n e e . U n i v e r s i t y o f H e l s i n k i . 1 9 9 7 应岔上卿之

·496· 北京科技大学学报 2006年第5期 [4]Casa-Garriga G.Discovering unbounded episodes in sequential [6]Harms S.Deogun J,Saquer J.et al.Discovering representa- data//Proceedings of the 7th European Conference on Princi tive episodal association rules from event sequences using fre ples and Practice of Knowledge Discovery in Databases.Cav- quent closed episode sets and event constraints//Proceedings of tat-Dubvrovnik,2003:83 the 2001 IEEE International Conference on Data Mining.Cal- [5]Hoppner F.Discovery of temporal patterns-leaming rules ifornia,2001:603 about the qualitative behaviour of time series//Proceedings of [7]Kosaraju S R.Fast pattern matching in trees//Proceedings of the 5th European Conference on Principles and Practice of the 30th IEEE Symposium on Foundations of Computer Sci- Knowledge Discovery in Databases.Freiburg,2001:192- ence.New York,1989:178 203 Mining algorithm of frequent episodes in an event sequence based on generalized suffix-tree QU Wenlong1.2),YANG Bingru2),ZHANG Kejun2) 1)Shijiazhuang University of Economics,Shijiazhuang 050031,China 2)Information Engineering School,University of Science and Technology Beijing,Beijing 100083.China ABSTRACT In order to mine frequent episodes from an event sequence efficiently,an algorithm based on generalized suffix-tree was proposed to discover and store frequent episodes,which uses the concept of gen- eralized suffix and contains only frequent episodes'nodes.The occurrence list of frequent episodes was used layer-upon-layer to improve the efficiency of the tree.The algorithm make full use of the order character of an event sequence and may discover the variety of frequent episodes.Experimental results show that the proposed algorithm is superior in runtime to Apriori-like frequent episodes mining algorithm. KEY WORDS event sequence;frequent episodes;data mining;generalized suffix tree

. 4 9 6 . 北 京 科 技 大 学 学 报 2 0 0` 年第 s 期 [ 4 ] C sa 一 G a r iga G . 压 vosc e ri n g u n 场 nu dde e P i s《 x」se i n Se q u e n t ila d a t a / P o e d i n g s fo t h e 7 t h E u ro Pe a n Cb n f e r nce e no P h n e i - p l e : na d P r ca t i e e o f K now lde g e 肠 sc o v e斗 i n D a t a b sae . Ca v - t a t 一 D u b v ro vn ik , 20 0 3 : 8 3 H o p p n e r F . 以 cs o 理斗 o f t em 卯 r al 囚t t em -s lae m i呀 ru les a场 u t t he q u al i t at i v e be h a v olu r of t lme se it es / P ocr e d i吃 s of t h e s t h E u or eP a n C冶n fe r e n e e on P ir n e iP l e s a n d P r a e t i e e o f K n o w lde g e D i cos v e r y i n aD t a ha s e s . F r e ib u r g . 2 00 1 : 1 9 2 一 20 3 〔6 ] [ 5 ] H a rm s S , 】) 泊 g un J , aS q u e r J . e t al . D i cos ve ir 呀 re P ~ n t a · t i v e e p i汉 x l a l ~ i a t oln ru les f orm e v e n t 卿 ue n e es us i n g f r e - q u e n t e los de e p i 别 x l e se t s a n d e ve n t co n s t r a i n t s / P ocr e d i吃 5 o f t h e 2 0 0 1 IE E E I n t e rn a t io n a l oC n f e r e n e e on aD t a M i n i n g . C a l - iof m i a . 2 0 0 1 : 6 0 3 K o as r aj u 5 R . F as 、 p at t e m m a t e hi叱 i n t r 。 / P ocr e de i n g s of t h e 3 0 t h IE EE S卿 p o s i u m o n oF u n d a t i o n s o f C冶m p u t e r 段i - e n c e . N e w Y o r k , 19 8 9 : 1 7 8 M i n i n g a l g o r i t h m o f f r e q u e n t e p i s o d e s s u f fi x 一 t r e e e v e n t s e q u e n e e b a s e d o n g e n e r a li z e d Q u we , l o n g ` , 2 ) , 以N G B i n g r “ 2 ) , 刀认 N G ejK u 。 2 ) l ) S hij iaz h u a n g U n i v e sr i t y of E e o on m i e s , S hij iaz h u a n g 0 5 0 0 3 1 , C 瓦an 2 ) I n of arm r i o n E n g i n e r i n g 反h co l , U n ive rs i t y o f cS i cen e an d T ce h n o 】。 g y Be ij i n g , Be ij i n g 10 00 8 3 , C h i n a A BS T R A C T I n o r d e r t o m ine f r e q u e n t e p i os d e s f orm a n ve e n t se q u e n e e e f fi e i e n t l y , a n a lg o r i t h m b a se d o n g e n e r a li z e d s u f fi x 一 t r e e w a s p or 因 s e d t o d i s co v e r a n d s t o r e f r e q u e n t e p iso d e s , w h i e h u se s t h e co n e e p t o f g e n - e r a li z e d s u ff i x a n d e o n t a i n s o n ly f r e q u e n t e p iso d e s ’ n o d e s . T h e o e e u r r e n e e li s t o f f r e q u e n t e p iso d e s w a s u s e d l a y e r 一 u P o n 一 l a y e r t o im p r o v e t h e e f fi c i e n e y o f t h e t r e e . T h e a lg o r i t h m m a k e f u ll u s e o f t h e o r d e r e h a r a e t e r o f a n e v e n t s e q u e n c e a n d m a y d i s co v e r t h e v a r i e t y o f f r e q u e n t e p i s o d e s . E x P e r im e n t a l r e s u l t s s h o w t h a t t h e p or P o s e d a lg o r i t h m 1 5 s u P e r i o r i n r u n t im e t o A p r i o ir 一 li k e f r e q u e n t e p iso d e s m i n i n g a lg o r i t h m . K E Y W O R D S e v e n t s e q u e n e e ; f er q u e n t e P iso d e s : d a t a m i n i n g : g e n e r a li z e d s u ffi x t r e e