基于拟间接依赖的流程挖掘优化分析

曹 蕊，方贤文，王丽丽

CAO Rui,FANG Xianwen,WANG Lili

安徽理工大学 数学与大数据学院，安徽 淮南 232001

College of Mathematics and Big Data,Anhui University of Science and Technology,Huainan,Anhui 232001,China

1 引言

随着信息技术的快速发展，业务流程管理占据着举足轻重的作用。业务流程挖掘优化作为业务流程管理的核心内容之一，对流程挖掘优化方面进行深入的研究显得至关重要。因此，先以行为轮廓为基础，得到初始模型，然后通过执行日志，运用基于整数线性规划算法的约束条件集找出具有拟间接依赖关系的变迁对并对初始模型进行调整，最后，挖掘出符合需求的业务流程模型。

目前，关于流程挖掘的研究已做了相当多的工作。文献[1]研究了流程发现技术的应用从场景中去发现各个成分的内部行为。在事件日志的基础上，提出了一种方法：（1）导出特征间的信息流，（2）确认特征的内部行为，（3）发现模块内的特征的顺序。对于每一个模块，使用该方法得到一个合理的工作流模型。文献[2]中的流程发现旨在从给定事件日志中更好地获取描述流程模型的行为，然而不频繁行为的存在影响获取模型的精确性。通过Inductive Miner，利用切操作过滤不频繁行为，挖掘得到合理的流程模型。把该方法和现有的挖掘方法在质量和性能方面作对比，说明该方法的有效性。文献[3]中描述从不完备的事件日志中发现流程模型结构，分析不完备日志对过程发现的影响，引入概率行为关系，利用这些关系处理不完备日志，给出一个基于这些概率关系的算法，用作重新发现流程模型语言。文献[4]考虑在间接继承的基础上，把日志作为输入，利用矩阵表示日志的可达到关系，顺序、排他、循环、平行，把日志分离成子日志，不断迭代，自动发现流程模型块结构。文献[5]提出了一种基于定位事件日志的通用的过程发现方法。该方法已在ProM和实验结果表明，位置信息确实有助于提高发现模型的质量。文献[6]提出了一种通用的流程挖掘框架预测、关联和聚集基于事件日志的动态行为。文献[7]提出了一种可构成的方法，从事件日志中发现块结构的流程模型。文献[8]提出了基于不同程度信息进行队列挖掘。文献[9]利用整数线性规划的方法挖掘业务流程模型。

考虑事件间的拟间接依赖关系能有效提高业务流程挖掘的效果，但目前相关研究比较少，文献[10]开展了相关研究，给出了一个基于拟间接依赖关系的挖掘方法，但是在查找其行为方面具有一定的难度，基于此，本文提出了基于拟间接依赖的流程挖掘优化分析的新方法。该方法以Petri网的行为轮廓理论为基础，建立初始模型。通过基于整数线性规划的约束条件找出具有拟间接依赖的变迁（事件）对，并对初始模型进行调整。最后挖掘出符合需求的业务流程模型。

2 基本概念

这一部分给出本文所需要的基本概念，首先给出Petri网的形式化定义。

定义1[11]（Petri网）一个Petri网PN=(P,T,F)是一个三元组，满足以下条件：

（1）P是有限库所集，T是有限变迁集。

（3）F=(P×T)⋃(T×P）表示PN 的流关系。

在Petri网PN中存在一种弱序关系，即包含T×T所有的变迁对(x,y)中存在一个发生序列δ=t1t2…tn，当i∈{1,2,…,n-1}时，i＜j≤n有ti=x且tj=y,x≻y，依据这种弱序关系定义了行为轮廓。

定义2[12]（Petri网的行为轮廓）PN=(P,T,F)是一个Petri网，对任意的变迁对(x,y)∈(T×T)，满足下列关系之一：

则以上几种行为关系构成Petri网的行为轮廓。

定义3[13]（事件日志）T是任务集，σ∈T*是一个执行集，L∈Ρ(T*)是一个事件日志。Ρ(T∗)是T∗的幂集，L⊆T*。

定义4[14]（前缀闭包）设L=[＜ABC…XYZ＞1002,＜ACB…YXZ＞1262,…,＜ABC…ZXY＞1232]是事件日志，A,B,C,…,Y,Z均是事件即任务，则L的前缀闭包是={ε,＜A＞,＜AB＞,＜AC＞,＜ABC＞,＜ACB＞,…,＜ABC…XYZ＞,＜ACB…YXZ＞,…,＜ABC…ZXY＞}，其中，ε是空序列。

3 基于拟间接依赖的流程挖掘优化分析方法

3.1 事件间拟间接依赖关系

任何一个业务流程模型的两个事件间都存在两种因果依赖关系：直接依赖关系和间接依赖关系。如果仅仅考虑事件之间的直接因果关系，不能够准确地从事件日志中挖出业务流程来满足组织或者企业的需求，因此，还需要查找出事件之间的间接依赖关系。事件之间拟间接依赖关系的概念如定义5所示。

定义5（拟间接依赖关系）T是事件集（任务集），L∈Ρ(T*)是事件日志，Lˉ是事件日志L的前缀闭包，设t1,t2∈T是T中的两个事件（Petri网模型的两个变迁），t1,t2之间具有拟间接依赖关系，记作t1∝t2，当且仅当不等式组，n∈{1,2,3,…}成立。

其中，对于L的前缀闭包Lˉ中的每一条执行的事件日志，xi(t1),yi(t2)的值可能不同，当t1发生时，xi(t1)是两个事件（变迁对）之间的库所的输入弧数目，当t2发生时，yi(t2)是两个事件（变迁对）之间的库所的输出弧的数目，i∈{1,2,…,n}，n∈{1,2,3,…}。

从事件之间拟间接依赖关系的定义可知，t1∝t2，称t1与t2满足拟间接依赖关系，即t2对于t1有依赖关系，通俗地说，t2是否发生取决于t1。由此可知，t1与t2之间存在着一个库所，使t1与t2之间形成另一条通路，这个库所的存在保证了t1与t2之间的拟间接依赖关系。具体的拟间接依赖关系可以参考图1，图中的变迁对A与C之间存在库所p1，B与D之间存在库所p2，A与C之间以及B与D之间均具有拟间接依赖关系。

图1 拟间接依赖关系的Petri网模型

3.2 基于拟间接依赖的流程挖掘优化分析算法

对于基于整数线性规划流程发现算法的基本约束体，由于每条执行日志不同，则一个库所前后变迁t1,t2发生的 xi(t1)，yi(t2）的值不同，i∈{1,2,…,n}，n∈{1,2,3,…}，则对应的线性不等式 xi(t1)+yi(t2)≥0(i∈{1,2,…,n}，n∈{1,2,3,…})也不一样。若每个线性不等式的右边部分大于等于零即不等式组成立，则该库所可以添加到流程模型中的这两个变迁t1,t2之间且t1,t2具有拟间接依赖性关系，这样就挖掘出了两个变迁的拟间接依赖关系（文中的事件集以Petri网的变迁集为例）。

Petri网的业务流程模型的变迁间除了具有直接依赖关系外，还往往具有间接依赖关系。如果仅仅从记录事件日志中挖掘出只含有直接依赖关系的流程模型，该模型并不能有效地拟合日志中的行为。因此，挖掘含有拟间接依赖关系的业务流程模型具有重要的意义。

有关业务流程挖掘的研究已做了相当多的工作。其中，α算法能够从事件日志中挖掘出合理的模型，但是，当涉及到挖掘特殊的流程模式（例如拟间接依赖关系）时，它具有很大的局限性。基于此，提出了基于整数线性规划流程发现算法的基本约束条件集找出流程模型中的具有拟间接依赖关系的变迁对，并且接受该变迁对间的库所，最终挖掘出流程模型中的拟间接依赖关系。

本文提出的基于拟间接依赖的流程挖掘优化分析的算法是以事件日志的行为轮廓关系为基础，首先分析事件日志的行为轮廓，根据行为轮廓关系建立初始模型。然后找出具有拟间接依赖的变迁对，并在执行具有拟间接依赖的变迁对的日志下，建立基于整数线性规划流程发现算法的基本约束表，通过不等式的成立来验证具有拟间接依赖的变迁对之间的库所的存在性。最后，得出符合需要的业务流程模型。具体的算法如算法1所示。

算法1基于拟间接依赖的流程挖掘优化

输入：事件日志

输出：Petri网模型

步骤1处理所有提取到的事件日志L，按照实例数从大到小排列日志，例如 {τ1,τ2,…,τn}，n∈{1,2,3,…}，τ1,τ2,…,τn∈L 。

步骤2根据定义，遍历每个事件日志，计算出事件日志的行为轮廓关系即各个变迁对t1,t2（其中t1,t2∈L）的行为轮廓关系，得出行为轮廓关系表（这里仅给出主要的关系，即→，+，‖），然后建立初始Petri网模型M0。

步骤3在初始模型M0的基础上，找出预拟间接依赖关系的变迁对t1,t2，t1是该库所前变迁，t2是该库所后变迁，然后执行含有此变迁对的迹，得到执行日志，建立执行日志表格。

步骤4对于由步骤3得到的执行日志，求出其前缀闭包Lˉ，即执行日志的子日志集。根据子日志集，找出基于整数线性规划的流程发现算法的基本约束条件体C1,C2,…,Cn，其中n∈{1,2,3,…}。计算预拟间接依赖关系的变迁对间的库所的输入弧和输出弧的数目（分别记为x(t1)，y(t2)其中，t1是该库所前变迁，t2是该库所后变迁）。然后建立约束体表格，转入步骤5。

步骤5根据步骤4中的约束体表格，可知对于不同的执行的日志，计算得到的x(t1)，y(t2)可能不同。为此，对于每一条日志，得到不同的约束条件Ci,i∈{1,2,…,n}，n∈{1,2,3,…}，变迁对之间的库所的输入弧和输出弧的数目分别记作 xi(t1),yi(t2),i∈{1,2,…,n}，n∈{1,2,3,…}。然后计算不等式组若不等式组成立，则该库所被该模型接受，且与该库所直接连着的变迁对具有拟间接依赖关系。否则，该库所被拒绝。执行步骤6。

步骤6步骤5中得到的被接受的库所则保留在该模型中。即挖掘出符合需求的模型，最后，输出最终符合需求的Petri网优化模型M1。

4 实例分析

为了验证上述算法的可行性，给出简单的实例，即衣服购买业务流程。记录的事件日志包括以下事件，分别用大写英文字母表示，其中，（A）顾客存包、（B）进入商场、（C）挑选衣服、（D）完成挑选、（E）新顾客选择支付方式、（F）老顾客选择支付方式、（H）刷 VIP卡、（I）银行卡支付、（J）走出商场。具体的事件日志如表1所示。

表1 事件日志L

首先将事件轨迹按照实例数从大到小排列，结果为 ：{ABCDEGIJ（2017），ABCDKCDFGHJ（2015），ACBDKCDKCDFGHJ（2013），ACBDFGHJ（2000），ABCDKCDKCDEGIJ（1997），ABCDKCDKCDKCJ（256），ACBDJ（157）}，依次记为 τ1，τ2，τ3，τ4，τ5，τ6，τ7。根据这些日志的行为轮廓关系，建立行为轮廓关系表，如表2所示。

表2 行为轮廓关系表

根据事件日志的行为轮廓关系，可以得到衣服购买的初始Petri网模型M0，如图2所示。

图2 初始模型M0

从初始模型M0中可以发现变迁对F和H，E和I具有预拟间接依赖关系，执行含有该变迁对的序列，可以得到执行日志，见表3。

表3 执行日志

表4 约束体表

图3 具有拟间接依赖关系的优化模型M1

对于上述实例，如果用α算法可以从事件日志中挖掘出合理的初始模型M0，但变迁对F和H以及变迁对E和I的拟间接依赖关系被忽视。而通过基于整数线性规划流程发现算法的基本约束条件集可以找出F和H以及E和I的拟间接依赖关系，从而得到符合需求的业务流程模型。

5 结束语

本文在现有研究的基础上，给出了基于拟间接依赖的流程挖掘优化分析方法。在事件日志下，找出各个任务即事件的行为轮廓关系，建立初始模型。通过基于整数线性规划流程发现算法的基本约束条件找到被初始模型接受的库所，则该库所前后两个变迁具有拟间接依赖关系，该库所保留在初始模型中，得到了满足需求的具有拟间接依赖关系的业务流程模型。

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

参考文献：

[1]Van Der Werf J M E M，Kaats E.Discovery of functional architectures from event logs[C]//International Workshop on Petri Nets and Software Engineering，2015：227-243.

[2]Leemans S J J，Fahland D，Van Der Aalst W M P.Discovering block-structured process models from event logs containing infrequent behaviour[C]//International Conference on Business Process Management.[S.l.]：Springer International Publishing，2013：66-78.

[3]Leemans S J J，Fahland D，Van Der Aalst W M P.Discovering block-structured process models from incomplete event logs[M]//Application and Theory of Petri Nets and Concurrency.[S.l.]：Springer International Publishing，2014：91-110.

[4]Boushaba S，Kabbaj M I，Bakkoury Z.Process discovery：Automated approach for block discovery[C]//2014 International Conference on Evaluation of Novel Approaches to Software Engineering（ENASE），2014：1-8.

[5]Van Der Aalst W M P，Kalenkova A，Rubin V，et al.Process discovery using localized events[C]//International Conference on Applications and Theory of Petri Nets and Concurrency.[S.l.]：Springer International Publishing，2015：287-308.

[6]De Leoni M，Van Der Aalst W M P，Dees M.A general process mining framework for correlating，predicting and clustering dynamic behavior based on event logs[J].Information Systems，2016，56：235-257.

[7]Leemans S J J，Fahland D，Van Der Aalst W M P.Discovering block-structured process models from event logs-a constructive approach[C]//International Conference on Applications and Theory of Petri Nets and Concurrency.Berlin Heidelberg：Springer，2013：311-329.

[8]Senderovich A，Leemans S J J，Harel S，et al.Discovering queues from event logs with varying levels of information[C]//International Conference on Business Process Management.[S.l.]：Springer International Publishing，2015：154-166.

[9]Van Der Werf J M E M，Van Dongen B F，Hurkens C A J，et al.Process discovery using integer linear programming[J].Fundamenta Informaticae，2009，94（3/4）：387-412.

[10]化佩，方贤文，刘祥伟.基于拟间接依赖的过程模型挖掘方法[J].计算机科学，2016，43（11）：94-97.

[11]Smirnov S，Weidlich M，Mendling J.Business process model abstraction based on behavioral profiles[C]//8th International Conference on Service-oriented Computing，San Francisco，December 7-10，2010.Berlin Heidelberg：Springer，2010，6470：1-16.

[12]Weidlich M，Polyvyanyy A，Desai N，et al.Process compliance measurement based on behavioral profiles[J].Advanced Information Systems Engineering，2010，6051：499-514.

[13]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.

[14]Van Zelst S J，Van Dongen B F，Van Der Aalst W M P.Filter techniques for region-based process discovery，Technical Report 15-4[R].BPM Center.org，2015.