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