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

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 )的子情节且 }夕! < } 。 } , 设单射为 f : V’ ~ v , 若 存在 v , “ 任 v ( v 笋 “ ) , 使得 存在 f( ’v ) 二 v( v’ 任 v ` )但不 存在 f ( u ` ) = u ( v ` 任 v ` ) , 必有 u 簇 v 不 成立 , 则称 夕为 口 的前缀子情节 , 称 。 为月扩充情 节 . 当 } 。 } = }月} 十 1 时 , 则称 月为 。 的相 邻前缀 子情节 , 称 。 为月相邻扩充情节 . 定义 6 给 定情节 。 = ( v , 蕊 , g ) 和 事件序 列 S = ( ( A l , t l ) , ( A Z , t Z ) , … , ( A , , r , ) , T s , T e > , 如果存在 一个从 情节结点到 事件的单射 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 对并行和混合情节的处理方法 算法 同样适 用于 并行和混合情节频 繁情节发 现 , 只需在频繁情节树逐 层 构造 过 程 中允 许进 行 并行情节扩充 . 例如设 父结点对应 的频 繁情节为 <A B > , 需对 <A B >位置 集中所有满足 限制的后 续 事件的组 合进行扩充 , 设为 <A B >后续出现的满足 限制的事件有 C , D , E , 设 允许的最大并行 事件 为 2 , 则其扩 充 为 <A B C > , <A B D > , <A B E > , ( A B ( C D ) ) , <A ( D E ) > , <A ( CE ) > , ( )表示 其 中 事件 先后 顺序无 限 制 . 前三 个 为满 足 限制的 串行扩 充 , 后 三个为满足限制的并行扩充 , 算法 中可根据 发掘 任务 添加 限制 , 如情节最 大持续期等 . 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 算