孙慧明 杜玉越

摘 要：为了在不完备的日志中挖掘含有多并发的三角形二度循环结构的过程模型，在扩展Alpha算法的基础上提出AlphaMatch算法。该算法可以在不包含重复行为序列的日志中，将两个活动匹配成三角形二度循环，并挖掘出含有多并发三角形二度循环的过程模型。首先，根据活动数量关系将构成三角形二度循环的活动分为两类;然后，再根据活动位置关系，使用三角形二度循环活动的首尾标记位置矩阵匹配这两类活动，并且给出足迹矩阵显示活动之间的关系;最后，在ProM平台上进行了大量仿真实验，从模型正确性、挖掘效率、拟合度和精确度四个角度验证了算法能有效挖掘含有多并发的三角形二度循环的Petri网模型。

关键词：过程挖掘;并发结构;三角形二度循环;过程模型;Petri网

中图分类号： TP311

文献标志码：A

文章编号：1001-9081（2019）03-0851-07

Abstract： 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.

Key words： process mining; parallel structure; 2-loops of triangles; process model; Petri net

0 引言

随着计算机、互联网的发展，越来越多的企业采用信息系统处理业务，这些信息系统会产生大量的日志文件。过程挖掘作为一门新兴学科，旨在从这些日志文件中提取有价值的过程相关信息。过程挖掘主要有过程发现（Process Discovery）、合规性检查（Process Conformance）和过程改进（Process Enhancement）三个方面的应用。过程发现是过程挖掘中最富有挑战性的任务之一[1]。通常，过程发现就是使用不包括任何先验信息的事件日志生成模型的过程。过程模型主要有以下两个方面的价值：1）有利于管理者了解业务流程，进行业务流程优化，从而提高业务效率;2）利用过程模型和日志信息相结合可以发现当前业务流程中出现的不合规问题，从而推动工艺流程的改进。

在得到模型后，一般采用拟合度、精确度、简化度和泛化度这四个标准评价过程模型。拟合度表示日志中的迹在模型中重演的能力;精确度表示模型重演日志的能力;简化度表示模型的复杂程度;泛化度表示模型允许未来行为的能力。拟合度和精确度是判断过程模型最重要的两个标准。

针对过程发现中出现的问题，国内外学者提出了诸多过程发现的算法。文献[2]提出的Alpha算法根据活动的次序判断活动之间的关系，但是无法挖掘短循环（只含有一个活动或者两个活动组成的循环）。文献[3]提出的Alpha++算法解决了非自由选择结构的问题。文献[4]提出Alpha+算法来挖掘短循环，但是要求日志是完全完备的。然而，当日志只满足局部完备性，Alpha及其扩展算法均不能挖掘出正确的模型。文献[5]提出的启发式过程挖掘算法根据依赖关系重演日志，在不完备的、有噪声的日志处理上有很大优势，并且可以用于处理噪声和不完备性，但是对于短循环处理能力一般。文献[6]将遗传算法思想用于过程挖掘，该方法有着良好的并行能力，日志处理速度快，但是当短循环隐藏在规模很大的模型中时，效率并不是很高。文献[7]提出的整数线性规划（Integer Linear Programming， ILP）算法在一定程度上能解决短循环挖掘问题，但是日志处理速度慢，效率低。文献[8-9]提出基于区域的过程挖掘方法能够表达更加复杂的控制流结构，并且能够较好地平衡“过拟合”和“欠拟合”，但是当过程模型包含大量活动时，会出现“状态空间爆炸”和无法处理噪声的问题。文献[10]提出的模糊挖掘方法在处理噪声和不完备性上有很大优势，并且得到的过程模型较为简洁。文献[11]将二度循环划分为三角形二度循环和菱形二度循环，并提出紧邻度模型来挖掘二度短循环。紧邻度模型在一定程度上能够解决该问题。但是紧邻度模型是依据相关性计算的概率模型，依赖于大量日志。当日志量比较少或者三角形二度循环中的活动紧邻行为较少时，识别三角形二度循环存在一定局限性，即对于多个三角形二度循环并发时，匹配三角形二度循环中的活动很容易出现偏差。文献[12]提出的Inductive Miner算法挖掘的模型有着较高的拟合度，但是挖掘含有三角形二度循环结构的日志时，挖掘的结果模型往往是过拟合的。当日志中不包含“abab……aba”行为序列时，即活动a先发生，b紧跟着发生，a紧跟b再次发生，b再次紧跟a发生，反复进行上述活动，最后以活动a结束。我们本文稱这种行为序列为三角形二度循环的循环显式行为。针对上述情况，当前方法均不能有效挖掘出日志对应的正确过程模型。此外，三角形二度循环结构是一种重要的工业生产流程，广泛出现在模具生产、零件加工、柔性制造、精密仪器生产、医疗器械生产、传感器生产等诸多领域，通常代表着对某一高精度零件的多次调整和加工。挖掘含有该类结构的过程模型，对企业了解并改进精密零件的生产流程有着重要意义。综上所述，在不包含三角形二度循环显式行为的不完备日志中，挖掘过程模型是本文的研究重点。

针对多个并发的三角形二度循环，本文扩展Alpha算法，提出基于三角形二度循环活动首次和最后一次被标记位置的挖掘算法AlphaMatch，该算法只需要日志满足局部完备性要求，并且不需要含三角形二度循环的显式行为。通过大量仿真实验，从模型正确性、挖掘效率、拟合度和精确度四个角度进行了对比分析，验证了本文方法的有效性。

定义7 日志的完备性[16]。设a、b为日志中任意两个活动，并且b可以直接跟在a后发生，称满足a >L b的行为在迹中至少出现一次的日志为局部完备性日志;称满足包含模型可能产生的所有活动序列的日志为完备性日志。

2 过程模型挖掘算法

本章以图1中塑料浇筑模具生产过程模型为例，引出相关概念并详细描述算法过程。图1中字母代表活动含义如下：e：准备生产原料;k：制胚;a：测量模具上凹槽;b：打磨抛光上凹槽;c：测量模具下凹槽;d：打磨抛光下凹槽;j：拼接上下凹槽; f：塑料模具定型。

与经典的Alpha算法相比，AlphaMatch算法先将主体活动和回调活动进行分类;再将主体活动与回调活动进行匹配;最后返回正确的匹配二元组集合MTL。以L1为例，经过AlphaMatch算法挖掘并分析得到活动间的关系如表3所示。由表3可知，活动a与b，c与d均被匹配在一起，最后得出L1对应的模型如图2所示，该模型与图1一致。

3 仿真实验

本文算法已经在ProM平台[17]实现（包含详细代码的ProM工程以及实验日志获取网址为https：//pan.baidu.com/s/1b9Js_KhDXXEqqYdEV8QrLw）。实验步骤如下：1）安装必要的Java环境;2）通过上述链接下载该ProM工程;3）将工程添加进入Eclipse中;4）进入ProM平台，导入日志;5）输入AlphaMatch搜索该算法，选中并单击该算法，即可挖掘日志对应的Petri网模型。

本文以图3所示的滚珠轴承的生产过程模型为例，模型中变迁代表的活动含义如下：o：制胚;i：套圈退火;j：车削加工;k：热处理;l：滚珠粗磨;m：滚珠清洗;n：保持器切削加工;e：准备半成品胚子;a：套圈细磨抛光;b：套圈测量;c：滚珠细磨抛光;d：滚珠测量;g：保持器细磨抛光;h：保持器测量;f：轴承安装。通过以下步骤获取不含有三角形二度循环显式行为的局部完备日志：1）输入如图3所示含有三个并发的三角形二度循環的滚珠轴承生产的过程模型;2）运行ProM中的Perform a simple simulation of a （stochastic） Petri net插件得到原模型的初始日志;3）将步骤2）生成的所有初始日志中包含三角形二度循环显式行为的迹删除，得到实验需要的不完备日志。本文进行实验的日志属性如表4所示，表中的4个日志均为缺乏循环显式行为的不完备日志，并且日志中不包含重复序列。

实验比较了AlphaMatch算法、Alpha+算法、ILP算法和IMF（Inductive Miner-inFrequent）算法[17]挖掘的结果。3.1节主要从模型正确性和挖掘效率上对比4种算法挖掘的模型，3.2节分别分析4个模型的拟合度和精确度。

3.1 挖掘模型分析

本节对比Alpha+算法、ILP算法、Inductive Miner-infrequent（IMF）算法以及AlphaMatch算法的挖掘结果。导入日志L2、L3、L4、L5。四种算法挖掘模型效率如图4所示，由图4可知Alpha+算法挖掘模型用时最少，Inductive Miner-infrequent（IMF）算法次之，两种算法用时差别很小;ILP算法在4个算法中用时最长;本文算法比上述两种算法用时多，但本文算法用时远比ILP算法用时要少。

导入日志L2，Alpha+算法挖掘结果如图5所示。由于日志不是完全完备的，所以Alpha+算法只挖掘出活动a、b、c、d、g、h之间的并发关系和活动的因果关系。此时Alpha+算法并没有挖掘出3个回调活动与其他活动之间的关系，所以图5的模型中存在3个独立变迁，与原模型有很大差别，因此，该模型是不合理的。

图6为ILP算法挖掘的模型，与Alpha+相比，该算法得到的模型不存在独立变迁，并且该方法正确地挖掘出了活动间的关系，得到的模型与原模型一致。但是该算法挖掘速度较慢，效率较低，耗时最长。

图7为Inductive Miner - infrequent（IMF）IMF算法挖掘的模型，该算法没有进行活动的匹配，而是将回调活动和主体活动分成两个部分，并且加入了大量不可见变迁，这导致模型结构相对比较复杂。除此之外，若先发生主体活动a，另外两个主体活动还没发生的情况下，3个回调活动中的任意一个都可以紧跟活动a发生。这种情况下产生的序列可能是原模型无法产生的，例如序列“aha”。因此，图7中的模型是不合理的。

图8为本文算法挖掘的模型。与Alpha+算法挖掘的模型相比，图8所示的模型正确地把活动匹配在一起，并且没有独立变迁的存在;与ILP算法相比，本文算法挖掘模型用时较少，效率高;与Inductive Miner - infrequent（IMF）IMF算法挖掘的模型相比，图8的模型不会产生原模型无法得到的序列，并且该模型与原模型一致。

综上所述，从算法挖掘模型上看，本文算法挖掘的模型与原模型一致，与其他算法相比，有着较大优势。本节是从模型整体的角度进行对比分析，3.2节分别从拟合度和精确度角度，进一步对挖掘的模型进行分析。

3.2 精确度和拟合度分析

本节从拟合度和精确度的角度分析四种结果模型。导入由原模型生成的不同规模，不同完备性的日志L2、L3、L4、L5。4个日志中L5含有迹的数量最多，完备性最强。通过ProM平台的Replay a Log on Petri Net for Conformance Analysis插件，输入模型和日志，得出四种算法所挖掘模型的拟合度，统计结果如图9所示。其中AlphaMatch算法、Inductive Miner - infrequent（IMF）IMF算法和ILP算法得到的拟合度一直都是1，拟合度要高于Alpha+算法。但是由于Inductive Miner - infrequent（IMF）IMF算法将主体活动和回调活动分成两块挖掘，导致模型还可能产生类似于“ada”“aha”等原模型不能产生的序列。因此，该模型是一种不合理的“过拟合”模型。由于上文中4个的日志都不是Alpha+算法所要求的完全完备日志，Alpha+算法无法得到回调活动间的关系，因此Alpha+算法得到模型的拟合度相对较低。

利用ProM中的Check Precision based on Align-ETConformance插件得到四種算法的精确度，统计结果如图10所示。由于Alpha+算法挖掘的模型中出现3个独立变迁，所以得到模型的精确度最低。由于Inductive Miner - infrequent（IMF）IMF算法挖掘的模型能产生大量原模型无法产生的活动序列，所以该算法得到模型的精确度也不高。由于ILP算法挖掘出的模型与原模型也一致，所以精确度与本文算法相同。但ILP算法挖掘出正确模型耗时最长。相比之下，本文算法挖掘用时较低，精确度更高。

综上所述，本文算法在挖掘效率上优于ILP算法，在所得到模型的拟合度上优于Alpha+算法，在精确度上优于Alpha+算法和Inductive Miner - infrequent（IMF）IMF算法。

4 结语

现有算法在挖掘多并发三角形二度循环时，挖掘的结果模型很容易与原模型出现偏差。本文提出一种能挖掘多并发三角形二度循环的新方法。首先依据三角形二度循环活动的数量特征将活动分为主体活动和回调活动;其次，依据活动首次和最后一次在迹中出现的位置，采用剪枝的思想，逆向将不正确的活动匹配删除，从而得到正确的活动匹配;最后，将算法以插件形式在ProM平台实现，经过大量实验分析，验证了本文算法能够正确有效地挖掘多并发三角形二度循环，并且该方法得到的模型有着最高的精确度和拟合度。但是本文算法也有一定的局限性，没有考虑重名活动等复杂情况的干扰，并且在挖掘效率上表现平庸，后续将对本文算法作出改进。

参考文献 （References）

[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 [C]// International Conference on Business Process Management. Springer-Verlag， 2007：328-343.

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 IEEE 12th 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 ProM 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.