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,1997V 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 应岔上卿之