·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 例子 中 未给出事件发生 的准 确时间 , 因此 以 其位置 序号 视 为时间 . 其中加外 框 的结点表 示频 繁情节 ( 加 入树中 ) , 无 外 框的 表 示 不 频 繁 情 节 ( 不 加 入 树 城 · 于 ·