报告人：王文星 作 者:王文星 闻立杰 谭士杰 单 位: 清华大学软件学院

Presentation on theme: "报告人：王文星 作 者:王文星 闻立杰 谭士杰 单 位: 清华大学软件学院"— Presentation transcript:

1 报告人：王文星 作 者:王文星 闻立杰 谭士杰 单 位: 清华大学软件学院
基于完全有限前缀的 完备日志生成算法 报告人：王文星 作 者:王文星 闻立杰 谭士杰 单 位: 清华大学软件学院

2 选题意义及研究现状 背景知识 基于CFP的次序关系 基于前缀的完备日志生成算法 评估框架 清华大学软件学院

3 选题意义及研究现状 背景知识 基于CFP的次序关系 基于前缀的完备日志生成算法 评估框架 清华大学软件学院

4 日志生成算法的意义 为系统行为分析和验证提供数据来源 为过程挖掘算法评估框架提供数据来源

5 研究现状（1） 通过可达图计算Petri网的所有的触发序列 满足TAR关系的日志生成算法（査海平）： 优点：完备关系
缺点：时间空间爆炸，不具备实用性 满足TAR关系的日志生成算法（査海平）： 优点：时间复杂度减小 缺点：并非真正系统执行日志

6 研究现状（2） 满足TAR关系的日志生成算法（査海平）： 三个网的TAR集合同为:AC,BC,CD,CE

7 选题意义及研究现状 背景知识 基于CFP的次序关系 基于前缀的完备日志生成算法 评估框架 清华大学软件学院

8 背景知识 展开网（unfolding）技术： 完备日志：基于特定关系 出现网：|·B|≤ 1, 无环 分支进程：相对独立的运行分支
展开网：最大的分支进程，代表网的行为 完全有限前缀（CFP）：保留展开网全部信息 配置，割 完备日志：基于特定关系 相邻关系 三角关系 长依赖关系 这为我们的算法提供了便利

9 选题意义及研究现状 背景知识 基于CFP的次序关系 基于前缀的完备日志生成算法 评估框架 清华大学软件学院

10 次序关系定义： 二元次序关系：用结构上的相邻或者并发关系来代表行为 隐式依赖:AC 相邻关系:AB,BC 并发关系:BD 传递闭包:ABC
二元次序关系(EAR) TAR0说明时可以增加一个图，带隐藏任务的，与源库所或者汇结库所相连

11 选题意义及研究现状 背景知识 基于CFP的次序关系 基于前缀的完备日志生成算法 评估框架 清华大学软件学院

12 算法设计

13 实例分析 计算得到D与E的子前缀 从初始状态开始执行A，得到{p,r}标识 选择执行D，得到{q,r}标识 选择执行E，得到{p,r}标识
在展开网上，先后执行B,C 得到轨迹ADEBC

14 扩展的次序关系完备日志生成规则 选择冲突原则 优先执行原则 三角关系可满足性原则 长依赖可满足性原则

15 选题意义及研究现状 背景知识 基于CFP的次序关系 基于前缀的完备日志生成算法 评估框架 清华大学软件学院

16 评估框架 日志评估框架： a谱系算法模式挖掘时日志完备性比较： 生成日志质量与性能的比较：

17 评估框架

18 参考文献 ZHA haiping, WANG jianmin, WEN lijie. An Algorithm of Complete Log Generation for Petri Net Models. Journal of System Simulation, 2007,17(1): [查海平，王建民，闻立杰. 一种Petri网模型完备日志生成算法. [J] 系统仿真学报，2007,17(1): ] J.Esparza, S.Romer, and W.Vogler, “An improvement of McMillan’s Unfolding Algorithm,” in TACAs ’96: Proceedings of the Second International Workshop on Tools and Algorithms for Construction and Analysis of Systems. London, UK: Springer-Verlag, 1996, pp W.M.P. van der Aalst, A.J.M.M. weijters, and L. Maruster. Workflow mining:Discovering process models from event logs. IEEE Transactions on Knowledge and Data Engineering, 16(9):1128–1142, 2004. Lijie Wen, Wil M. P. van der Aalst, Jianmin Wang, Jiaguang Sun: Mining process models with non-free-choice constructs. Data Min. Knowl. Discov. 15(2): (2007) A.K.A de Medeiros, B.F. van Dongen, W.M.P. van der Aalst, and A.J.M.M. Weijters, “Process Mining: Extending the A-Algorithm to Mine Short Loops,” Technical Report, Univ. of Technology BeehiveZ系统的下载地址:

19 Thank You!