基于流程挖掘的并行优化算法

邵叱风

摘 要：過程挖掘技术将观察到的行为（即事件日志）与建模的行为（如bpmn模型或petri网）联系起来.可以通过对日志进行挖掘，获得实际业务流程模型，再对其中关联严格结构检测，通过并行优化的方法优化实际业务流程模型.目前的业务流程优化主要是针对管理者或开发者给出的业务流程模型，其与实际运行中的业务流程可能与之有些许偏差，从而影响了优化结果.在此提出一种新方法对业务流程进行优化.首先使用Prom框架中的Alpha Miner及Heuristic miner获得流程模型的Petri Net及C-net结构;然后使用最大分解的方法修复流程模型;针对修复后的模型提出其中高频简单网部分，并发现关联严格结构，使用Colored Petri nets对关联严格结构重新构造为关联并行结构，确定优化结果.该方法通过实际业务流程的研究案例及比较实验进行评估，其结果表明关联并行优化可明显缩短实际业务流程耗时.

关键词：Colored Petri nets;C-net;最大分解;关联严格;关联并行

中图分类号：TP391.9  文献标识码：A  文章编号：1673-260X（2019）10-0066-05

1 引言

1.1 研究背景

随着大数据时代的到来，业务流程的管理拥有举足轻重的地位.业务流程管理的核心内容便是业务流程挖掘及优化，由此对流程挖掘及优化方面的深入研究日益重要.本文着重于修复和优化的方面.修复流程的目标是细化现有流程模型，使它们符合给定的事件日志.优化流程的目标是修改现有的流程模型，使其对应的实际业务流程更加合理、便捷.本文所考虑的修复及优化方法分别称为分解模型修复方法与并行优化算法.假设事件日志描述了正确的和最新的业务流程行为，而流程模型可能是错误的.模型修复后是最新的且正确的，可它表示的流程不一定是最合适的流程.在此，先以实际流程日志为基础，通过执行Prom平台中的Alpha Miner获得实际流程运行初始Petri Net模型，并使用Heuristic miner获得实际流程运行C-net模型，通过分析绘制出最新流程模型，然后使用最大分解算法[1]对流程模型与初始日志进行三步操作：（1）将流程模型和事件日志分解为模型片段和子日志，（2）选择需要修复的片段，（3）使用流程发现算法修复选中的片段.获得修复模型后，进行三步操作：（1）将模型中高频部分提出，（2）检测提取模型中关联严格结构，（3）使用并行优化算法优化提取的模型.最后得到符合实际业务流程的模型优化后的模型.

近年来，过程挖掘[2]是被广泛研究与应用的新兴技术，主要分为以下三个阶段：过程发现、服从性校验、模型完善[3].其中，流程发现是流程挖掘领域中最关键的问题之一，其目的是从事件日志中发现流程模型来描述日志[4]中观察到的行为.在文献中提出了许多流程挖掘技术，例如，在基于Alpha算法的抽取技术[5]和它的变体[6，8，9]，启发式挖掘算法[10]，基于状态空间搜索的遗传算法[11]，基于语言的区域算法[12]，基于状态的区域算法[13]，复杂感知算法[14]，基于正确块结构的算法[15]，和无锁保证算法[16].

1.2 动机案例

通过政府在线采购系统进行采购是当今政府常见的采购方式，本文使用政府采购的在线采购流程作为研究案例来分析所提出的方法，图1给出政府在线采购系统案例的给定模型M.

由于政府采购系统是在不断完善中，所以实际的流程模型是不断变化的，给定的模型M很难保证其是最新的且正确的系统流程模型，如果在此模型上对系统流程模型进行优化，难以达到预期的采购系统模型优化效果.

2 基本概念

定义3 （关联严格）Petri Net模型对应实际业务流程，任意一个变迁均对应有实际操作，如果操作B必须有操作A的结果才可进行，则称操作A、B对应变迁具有关联严格，记CB（A，B）.

如图2所示，其中A，B，C，D如图所示为严格序关系，但在实际流程操作中，操作B的前提为A，操作C的前提为A，操作D的前提为B、C.分别记为CB（A，B），CB（A，C），CB（B，D），CB（C，D）.则可对流程模型进行方案1优化，并不会发生任何阻塞.情况2则可使用方案2进行优化.

3 流程挖掘及修复

本节基于表1政府采购系统的事件日志可以对现有的政府采购系统流程模型进行挖掘及修复.此处采用Prom平台中的Alpha Miner及Mine for a Heuristics Net using Heuristics Miner两个插件对日志进行挖掘处理，并使用最大分解算法对模型进行修复.

3.1 政府采购流程日志挖掘（Alpha-algorithm、Heuristic miner）

对表1中的日志进行挖掘操作，此处（默认插件设置）可获得如图3、4所示Petri net流程模型及C-net流程模型.

由图4中C-net流程模型的Fitness=0.999可知，此刻的因果网能极大程度上表达日志1中的流程.结合图3中Petri net流程模型，可得最新日志1中的政府采购流程模型如图5所示.此刻的初步流程模型相较于给定的模型M已经多出了t6、t14、t20三个操作流程，可见保持最新且正确的流程模型是极其困难的.故在对系统流程进行优化时最好采用最新的日志进行挖掘，以获得相对更适应当前系统的流程模型.

3.2 政府采购流程日志修复（最大分解法）

对图5中的初步流程模型及表1中的日志使用最大分解法优化，如图6所示，此刻获得的实时流程模型在初始状态时，增加了2个Token，根据实际业务流程分析可知，t6，t14两个操作与另外两个系统有交互操作，相较于初步流程模型更加细化了.

4 业务流程中关联严格并行优化算法

过程模型的Petri网模型的性能分析通常从以下评估指标中观察，例如有效性，适应性，过程周期时间，效率和过程成本.过程周期时间和效率是相关的，并且难以测量有效性和适应性.故在此主要性能评价指标选用流程周期长度.在Petri网中主要依靠实体token的数据传递来实现时间参数的计算，其中业务流程平均周期时间计算公式为：

其中InToken.Time初始为0，在这里我们假设所有变迁在token输入库所后立刻发生，即Waiting.Time=0.n是流程个数，m是每个流程的变迁个数.在模型优化过程中，分析变迁之间的关联严格关系，并设计如下所示的ProcessOptimization算法.

该算法包括流程模型中的变迁的重新组合，以及有色Petri网形式的输出，其中不同的颜色对应于不同的分支，通过并发的方式减少流程耗时.还有对颜色petri网colorSet以及对应颜色路径耗时的输出，最后使用冒泡排序对耗时进行排序输出.鉴于重新构造系统模型会改变原先流程，可能会使某些系统的开发维护产生大量工作，所以在保证优化效率及资源合理利用前提下，建议对流程中部分高频片段进行优化.

5 实验评估

并行优化算法主要思想即结合关联严格结构，重新构造为并发结构，以减少流程耗时.首先对任意模型（例如图2模型），设InToken.Time=0及Waiting.Time=0，且任意Act.Timei>0，采用并行操作前的流程耗时为：

Total.Time=Act.TimeA+Act.TimeB+Act.TimeC+Act.TimeD

优化方案1中流程耗时为：

Total.Time=Act.TimeA+max{Act.TimeB，Act.TimeC}Act.TimeD

显然

max{Act.TimeB，Act.TimeC}<Act.TimeB+Act.TimeC

优化方案2中流程耗时为：

Total.Time=Act.TimeA+max{（Act.TimeB+Act.TimeD），Act.TimeC}

显然

max{（Act.TimeB+Act.TimeD），Act.TimeC}<Act.TimeB+Act.TimeC+Act.TimeD

无论任意并发执行方案，均缩短了流程执行耗时.说明了并行优化的可行性.

5.1 实验设置

对于图6使用最大分解获得的实时流程模型，其中的高频事件如图7.不妨取出如图8所示模型进行优化实验.其关联严格关系CB（t7，t8），CB（t7，t9），CB（t9，t10），CB（t8，t11），CB（t10，t11）.

5.2 实验结果分析

5.2.1 仿真实验

将高频部分代入算法进行优化，对于模型重构部分有如图9所示过程.

5.2.2 结果评估

使用表2中周期参数，使用计算公式

计算，设InToken.Time=0及Waiting.Time=0，可得如图11所示完成流程各阶段耗时.

选择处理时间减少率作为评估处理效率的指标，并且处理时间减少率用于反映处理优化之后整个处理时间减少的影响.从上述模拟计算得出，优化前后图所示业务流程的平均周期分别为28.5天和19.5天，整体流程时间缩短率为31.6%.因此，所采取的优化措施是正确的，有效地减少了图3的业务流程周期，并提高了流程执行的效率.因此，该过程的成本降低到一定程度，此优化算法是实际可行的.

最終优化模型如图12所示，相较于给定的模型M增加了3个变迁及三个初始Token，反映了当前系统与其他系统的交互，且在场地安排流程实行了优化，大大缩短了流程耗时.基于模型挖掘的并行优化算法在实际流程优化中是极符合优化要求的.

6 结束语

本文在已有研究的基础上，给出了基于过程挖掘的并行优化方法.首先使用Prom框架中的Alpha Miner及Heuristic miner获得流程模型的Petri Net及C-net结构;然后使用最大分解的方法修复流程模型;针对修复后的模型提出其中高频部分（模型优化可能会修改流程逻辑，针对高频大量事件，减少系统二次开发工作量，相对提高优化的实际意义），并发现关联严格结构，使用Colored Petri nets对关联严格结构重新构造为关联并行结构（通过不等式证明并发操作减少耗时的可行性），确定优化后流程模型结构.

未来关于过程挖掘进行优化的研究还有很多工作去做.例如，在基于整数线性规划的约束体下，从包含大量事件的日志中挖掘满足需求的实时业务流程模型.

参考文献：

〔1〕Mitsyuk， A.A.， Lomazova， I.A.， Shugurov， I.S.， and van der Aalst， W.M.P.， Process model repair by detecting unfitting fragments， Supplementary Proceedings of AIST 2017， CEUR-WS.org， 2017.

〔2〕宋健，方贤文，王丽丽.基于流程切的过程模型挖掘方法[J].计算机科学，2019，46（7）：1-7.

〔3〕VANDERASLST W， WEIJTERS T， MARUSTER L. Process Mining： Discovery， Conformance and Enhancement of Business Processes[M]. Springer-Verlag， Berlin， 2011.

〔4〕Wil van de. Aalst， Arya Adriansyah， Ana Karla Alves de Medeiros， Franco Arcieri， Thomas Baier， Tobias Blickle， Jagadeesh Chandra Bose， Peter van den Brand， Ronald Brandtjen， Joos Buijs， et al.， Process mining manifesto， in： Business Process Management Workshops， Springer， 2012， pp.169–194.

〔5〕Wil van der Aalst， Ton Weijters， Laura Maruster， Workflow mining：Discovering process models from event logs， IEEE Trans. Knowl. Data Eng.16 （9） （2004） 1128–1142.

〔6〕L. Wen， J. Wang， W.M. Aalst， et al.， A novel approach for process mining based on event types， J. Intell. Inf. Syst. 32 （2） （2009） 163–190.

〔7〕L. Wen， W.M. Aalst， J. Wang， et al.， Mining process models with non-free-choice constructs， Data Min. Knowl. Discov. 15 （2） （2007）145–180.

〔8〕L. Wen， J. Wang， J. Sun， Mining invisible tasks from event logs， in： Advances in Data and Web Management， Springer， 2007， pp. 358–365.

〔9〕L. Wen， J. Wang， W.M.P. van der Aalst， B. Huang， J. Sun， Mining process models with prime invisible tasks， Data Knowl. Eng. 69 （10） （2010） 999–1021.

〔10〕A.J.M.M. Weijters， Wil M.P. van der Aalst， A.K. Alves De Medeiros， Process mining with the heuristics miner algorithm， in： Tech. Rep， Vol. 166， Technische Universiteit Eindhoven， WP， 2006， pp. 1–34.

〔11〕A.K. Alves De Medeiros， A.J.M.M. Weijters， Wil M.P. van der Aalst， Genetic process mining： a basic approach and its challenges， in： Business Process Management Workshops， Springer， 2006， pp. 203–215.

〔12〕Robin Bergenthum， J？rg Desel， Robert Lorenz， Sebastian Mauser， Process mining based on regions of languages， in： Business Process Management， Springer， 2007， pp. 375–383.

〔13〕Josep Carmona， Jordi Cortadella， Michael Kishinevsky， A region-based algorithm for discovering petri nets from event logs， in： Business Process Management， Springer， 2008， pp. 358–373.

〔14〕Chathura C. Ekanayake， Marlon Dumas， Luciano Garc？a-Bauelos， Marcello La Rosa， Slice， mine and dice： Complexity-aware automated discovery of business process models， in： International Conference on Business Process Management， Springer， 2013.

〔15〕Sander J.J. Leemans， Dirk Fahland， Wil M.P. van der Aalst， Discovering block-structured process models from incomplete event logs， Lecture Notes in Comput. Sci. 8489 （2014） 311–329.

〔16〕Adriano Augusto， Raffaele Conforti， Marlon Dumas， Marcello La Rosa， Split miner： discovering accurate and simple business process models from event logs， in： IEEE International Conference on Data Mining， 2017.