针对多并发三角形二度循环结构的过程模型挖掘方法
|
摘要
为了在不完备的日志中挖掘含有多并发的三角形二度循环结构的过程模型,在扩展Alpha算法的基础上提出AlphaMatch算法。该算法可以在不包含重复行为序列的日志中,将两个活动匹配成三角形二度循环,并挖掘出含有多并发三角形二度循环的过程模型。首先,根据活动数量关系将构成三角形二度循环的活动分为两类;然后,再根据活动位置关系,使用三角形二度循环活动的首尾标记位置矩阵匹配这两类活动,并且给出足迹矩阵显示活动之间的关系;最后,在ProM平台上进行了大量仿真实验,从模型正确性、挖掘效率、拟合度和精确度四个角度验证了算法能有效挖掘含有多并发的三角形二度循环的Petri网模型。
To mine the process model including multi-concurrent 2-loops of triangles in incomplete logs, an AlphaMatch algorithm based on extended Alpha algorithm was proposed. Two activities in triangle structure could be correctly matched in 2-loops of triangles by AlphaMatch in the log without repeated activity sequence, thus the process model with multi-concurrent 2-loops of triangles could be mined. Firstly, the activities in 2-loops of triangles were divided into two categories according to the number of activities. Then, a matrix of head and tail position of the activities was constructed to match the two categories and a footprint matrix was constructed to show the relationship between activities. Finally, a large number of experiments were carried out on ProM platform from model correctness, mining efficiency, fitness and precison. Experimental results show that the Petri net model including multi-concurrent 2-loops of triangles can be mined efficiently by the proposed algorithm.
To mine the process model including multi-concurrent 2-loops of triangles in incomplete logs, an AlphaMatch algorithm based on extended Alpha algorithm was proposed. Two activities in triangle structure could be correctly matched in 2-loops of triangles by AlphaMatch in the log without repeated activity sequence, thus the process model with multi-concurrent 2-loops of triangles could be mined. Firstly, the activities in 2-loops of triangles were divided into two categories according to the number of activities. Then, a matrix of head and tail position of the activities was constructed to match the two categories and a footprint matrix was constructed to show the relationship between activities. Finally, a large number of experiments were carried out on ProM platform from model correctness, mining efficiency, fitness and precison. Experimental results show that the Petri net model including multi-concurrent 2-loops of triangles can be mined efficiently by the proposed algorithm.
引文
[1]van der AALST W M.Process Minging:Discovery,Conformance and Enhancement of Business Processes[M].Berlin:Springer,2014:5-18.
[2]van der AALST W,WEIJTERS T,MARUSTER L.Workflow mining:discovering process models from event logs[J].IEEE Transactions on Knowledge and Data Engineering,2004,16(9):1128-1142.
[3]WEN L,van der AALST W M,WANG J,et al.Mining process models with non-free-choice constructs[J].Data Mining and Knowledge Discovery,2007,15(2):145-180.
[4]de MEDEIROS A K A,van DONGEN B F,van der AALST W M.Process mining:extending theα-algorithm to mine short loops[R].Eindhoven,Holland:Eindhoven University of Technology,2004:151-165.
[5]WEIJTERS A,van der AALST W,de MEDEIROS A A.Process mining with the heuristics miner-algorithm[R].Eindhoven,Holland:Eindhoven University of Technology,2006:1-34.
[6]MEDEIROS A K A D,WEIJTERS A J M M,AALST W M P V D.Genetic process mining:an experimental evaluation[J].Data Mining and Knowledge Discovery,2007,14(2):245-304.
[7]van der WERF J M E M,van DONGEN B F,HURKENS C A J,et al.Process discovery using integer linear programming[C]//Proceedings of the 2008 International Conference on Applications and Theory of Petri Nets,LNCS 5062.Berlin:Springer,2008:368-387.
[8]van DONGE B,BUSI N,PINNA G,et al.An iterative algorithm for applying the theory of regions in process mining[R].Eindhoven,Holland:Eindhoven University of Technology,2007:36-55.
[9]BERGENTHUM R,DESEL J,LORENZ R,et al.Process mining based on regions of languages[C]//Proceedings of the 2007 International Conference on Business Process Management,LNCS 4714.Berlin:Springer,2007:375-383.
[10]GNTHER C W,van der AALST W M P.Fuzzy mining-adaptive process simplification based on multi-perspective metrics[EB/OL].[2018-06-16].http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=1628DBA2308A214245DDE19D04107610?doi=10.1.1.81.1207&rep=rep1&type=pdf.
[11]林雷蕾,周华,代飞,等.一种挖掘二度循环的扩展Alpha算法[J].计算机集成制造系统,2018,24(3):591-601.(LIN L L,ZHOU H,DAI F,et al.Extendingα-algorithm to mine simplest 2-loops[J].Computer Integrated Manufacturing Systems,2018,24(3):591-601.)
[12]WU B,FU Y.Generating inductive invariants for Petri nets[M]//Advances in Electrical Engineering and Automation,AINSC 139.Berlin:Springer,2012:259-266.
[13]祁宏达,杜玉越,刘伟.一种基于可达标识的过程模型修复方法[J].山东科技大学学报(自然科学版),2017,36(1):118-124.(QI H D,DU Y Y,LIU W.Process model repairing method based on reachable markings[J].Journal of Shandong University of Science and Technology(Natural Science),2017,36(1):118-124.)
[14]明利,李彤,秦江龙,等.面向软件即服务的负载均衡策略建模与分析[J].计算机应用,2017,37(1):24-30.(MING L,LI T,QIN J L,et al.SaaS-oriented modeling and analysis of load balancing strategy[J].Journal of Computer Applications,2017,37(1):24-30.)
[15]HE Z,DU Y,WANG L,et al.An alpha-FL algorithm for discovering free loop structures from incomplete event logs[J].IEEE Access,2018,6:27885-27901.
[16]YANG H,WEN L,WANG J.An approach to evaluate the local completeness of an event log[C]//Proceedings of the 2012 IEEE12th International Conference on Data Mining.Washington,DC:IEEE Computer Society,2012:1164-1169.
[17]van DONGEN B F,de MEDEIROS A K A,VERBEEK H M W,et al.The Pro M framework:a new era in process mining tool support[C]//Proceedings of the 2005 International Conference on Applications and Theory of Petri Nets,LNCS 3536.Berlin:Springer,2005:444-454.
[2]van der AALST W,WEIJTERS T,MARUSTER L.Workflow mining:discovering process models from event logs[J].IEEE Transactions on Knowledge and Data Engineering,2004,16(9):1128-1142.
[3]WEN L,van der AALST W M,WANG J,et al.Mining process models with non-free-choice constructs[J].Data Mining and Knowledge Discovery,2007,15(2):145-180.
[4]de MEDEIROS A K A,van DONGEN B F,van der AALST W M.Process mining:extending theα-algorithm to mine short loops[R].Eindhoven,Holland:Eindhoven University of Technology,2004:151-165.
[5]WEIJTERS A,van der AALST W,de MEDEIROS A A.Process mining with the heuristics miner-algorithm[R].Eindhoven,Holland:Eindhoven University of Technology,2006:1-34.
[6]MEDEIROS A K A D,WEIJTERS A J M M,AALST W M P V D.Genetic process mining:an experimental evaluation[J].Data Mining and Knowledge Discovery,2007,14(2):245-304.
[7]van der WERF J M E M,van DONGEN B F,HURKENS C A J,et al.Process discovery using integer linear programming[C]//Proceedings of the 2008 International Conference on Applications and Theory of Petri Nets,LNCS 5062.Berlin:Springer,2008:368-387.
[8]van DONGE B,BUSI N,PINNA G,et al.An iterative algorithm for applying the theory of regions in process mining[R].Eindhoven,Holland:Eindhoven University of Technology,2007:36-55.
[9]BERGENTHUM R,DESEL J,LORENZ R,et al.Process mining based on regions of languages[C]//Proceedings of the 2007 International Conference on Business Process Management,LNCS 4714.Berlin:Springer,2007:375-383.
[10]GNTHER C W,van der AALST W M P.Fuzzy mining-adaptive process simplification based on multi-perspective metrics[EB/OL].[2018-06-16].http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=1628DBA2308A214245DDE19D04107610?doi=10.1.1.81.1207&rep=rep1&type=pdf.
[11]林雷蕾,周华,代飞,等.一种挖掘二度循环的扩展Alpha算法[J].计算机集成制造系统,2018,24(3):591-601.(LIN L L,ZHOU H,DAI F,et al.Extendingα-algorithm to mine simplest 2-loops[J].Computer Integrated Manufacturing Systems,2018,24(3):591-601.)
[12]WU B,FU Y.Generating inductive invariants for Petri nets[M]//Advances in Electrical Engineering and Automation,AINSC 139.Berlin:Springer,2012:259-266.
[13]祁宏达,杜玉越,刘伟.一种基于可达标识的过程模型修复方法[J].山东科技大学学报(自然科学版),2017,36(1):118-124.(QI H D,DU Y Y,LIU W.Process model repairing method based on reachable markings[J].Journal of Shandong University of Science and Technology(Natural Science),2017,36(1):118-124.)
[14]明利,李彤,秦江龙,等.面向软件即服务的负载均衡策略建模与分析[J].计算机应用,2017,37(1):24-30.(MING L,LI T,QIN J L,et al.SaaS-oriented modeling and analysis of load balancing strategy[J].Journal of Computer Applications,2017,37(1):24-30.)
[15]HE Z,DU Y,WANG L,et al.An alpha-FL algorithm for discovering free loop structures from incomplete event logs[J].IEEE Access,2018,6:27885-27901.
[16]YANG H,WEN L,WANG J.An approach to evaluate the local completeness of an event log[C]//Proceedings of the 2012 IEEE12th International Conference on Data Mining.Washington,DC:IEEE Computer Society,2012:1164-1169.
[17]van DONGEN B F,de MEDEIROS A K A,VERBEEK H M W,et al.The Pro M framework:a new era in process mining tool support[C]//Proceedings of the 2005 International Conference on Applications and Theory of Petri Nets,LNCS 3536.Berlin:Springer,2005:444-454.