基于Petri网行为轮廓的网上购物流程挖掘方法

王倩倩， 王丽丽

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

0 引言

流程挖掘是一种从实际业务执行日志中发现结构化流程信息的过程[1].流程挖掘技术能够从现代信息系统普遍产生的事件日志中抽取信息，通过建立清晰的流程模型，保证构建的流程模型与实际的流程执行过程保持一致，从而监测和改进原过程模型[2].目前，过程发现技术面临的主要问题是事件日志往往不能包含一个业务流程模型的所有信息(如不完整日志)，从而导致所挖掘的流程模型与实际业务流程不一致.文献[3]给出了流程模型与事件日志一致性程度的3种度量维度(合适度、精度、泛化)，但是这3种度量维度不能明确表达活动之间的因果关系和并行关系.文献[4]提出了一种从日志的活动发生顺序来推断业务流程模型的算法，但该方法只能发现简单的业务流程模型.M.Rovani等[5]和高立哲等[6]基于流程挖掘ProM平台和事件日志，挖掘医疗业务流程，但该方法仍不适合结构复杂的流程模型.针对以上问题，M.Weidlich等[7]以Petri网行为轮廓作为基线来计算新的服从指标，该方法通过有效计算行为轮廓，避免了基于状态空间指标的性能问题，从而能够清晰表达活动之间复杂的业务流程关系.本文受文献[7]的启发，提出一种基于Petri网行为轮廓的网上购物流程挖掘方法，并结合实例验证本文方法的有效性.

1 基本概念

定义1[8](流程模型) 一个网P=(A,ai,a0,C,F,T)称作流程模型，满足以下条件：

1)A是活动节点,A≠∅；C是控制节点，C≠∅.

2)ai,a0∈A，ai是起始活动，a0是结束活动.

3)F⊆((A{a0})∪C)×((A{ai})∪C)是流关系.

4)T:C{and,or,xor}是关于控制节点类型的函数.

定义2[9](流程模型的弱序关系) 若P=(A,ai,a0,C,F,T)为一个流程模型，εP是执行序列的集合，弱序关系≻P⊆(A×A)包含所有(x,y)， 存在一个执行序列σ=n1,…,nm，σ∈εP，∀i,j∈{1,…,m-1}且j

定义3[9](流程模型的行为轮廓) 若P=(A,ai,a0,C,F,T)为一个流程模型，∀(x,y)∈(A×A)满足下面关系：

1)若x≻Py且y≻/Px， 则称x和y之间为严格序关系，记作x→Py；

2)若x≻/Py且y≻/Px， 则称x和y之间为排他性关系，记作x+Py；

3)若x≻Py且y≻Px， 则称x和y之间为交叉序关系，记作x‖Py.

定义4[7](执行序列，事件日志) 若Petri网P=(A,ai,a0,C,F,T)为一个流程模型，σP为P的一个发生序列σP∈{ai}·A*·{a0}， 事件日志L是执行序列σP的集合.

定义5[9](流程模型的因果行为轮廓) 若P=(A,ai,a0,C,F,T)为一个流程模型，则：

1)共现关系≫P，∀(x,y)∈(A×A)满足∀σ=n1,…,nm，σ∈εP,ni=x,nj=y，∀i,j∈{1,…,m}， 且i≠j.

定义6[7](日志的行为轮廓) 若LP=n1,…,nm是流程模型P=(A,ai,a0,C,F,T)的一个日志，对于∀(x,y)∈(AL×AL)满足：

1)若x≻Ly且y≻/Lx， 则称x和y之间为严格序关系，记作x→Ly；

2)若x≻Ly且y≻Lx， 则称x和y之间为交叉序关系，记作x‖Ly.

称所有关系的集合为日志的行为轮廓，记作BL={→L,‖L}.

定义8[7](包容谓词) 给定两个行为关系R,R′∈{→,→-1,+,‖}， 当R=R′和R=‖， (R∈{→,→-1}∧R′=+)中有一个成立时，则称R和R′满足包容谓词关系，记作S(R,R′).

2 基于行为轮廓的网上购物挖掘算法

本文提出的基于Petri网行为轮廓的网上购物流程挖掘算法，首先通过分析事件日志的活动关系确定行为轮廓关系，以此挖掘出一个初始的流程模型；然后测量流程模型与事件日志的服从程度，并将其与标准的服从程度值进行对比，以此来判断该流程模型是否需要进一步优化.

基于Petri网行为轮廓的网上购物流程挖掘算法的步骤如下：

输入：事件日志，服从性阈值

输出：网上购物Petri网模型

步骤1 对事件日志L={n1,n2,…,ni},i=1,2,…,k进行预处理，按照发生频数f(x)大小进行排序.

步骤2 选择发生频数f(x)>M的几条日志序列(M为经验阈值)，然后根据日志序列中活动间行为轮廓的弱序关系构造序列活动关系表.

步骤3 根据活动关系表构造活动间行为轮廓表，然后利用行为轮廓表建立初始Petri网模型.

步骤4 根据行为轮廓计算事件日志与初始模型的服从性.以α为服从性的标准值，若服从性高于α， 则输出模型；反之，返回到步骤2进行模型优化，且令步骤2中的M=M-N, 其中N为每次减小的步长.

步骤5 重复步骤4， 当服从性大于α或M-N<0， 输出模型.

3 实例分析

系统中发生的事件被记录在日志中，它对理解系统的活动至关重要，特别是在用户交互较少的应用程序中.由于事件日志包含事件的属性较多，本文仅抽取事件中的活动序列来挖掘网上购物流程.

本文以某app网上购物系统记录的事件日志为例进行挖掘.网上购物业务流程信息系统中日志处理后所包含的活动P={A,B,C,D,E,F,G,H,I,J,K,L,Y}， 其中〈A,B,C,E,F,Y,G,I,L〉为事件日志中的一个发生序列.以下是该app处理过后的一个事件日志：

Φ=[〈A,B,C,E,F,Y,G,I,L〉80,〈A,B,C,E,F,Y,G,H,J,K,L〉56,〈A,B,D,E,F,Y,G,H,J,K,L〉33,〈A,B,C,E,F,Y,G,H,J,K,L〉20,〈A,B,C,E,Y,F,G,I,L〉63,〈A,B,D,E,Y,F,G,I,L〉43,〈A,B,D,E,G,I,L〉49]，

其中A,B,C,D,E,F,G,H,I,J,K,L,Y分别表示登录、购买商品、在线支付、到付、下单、接单、发货、因质量拒货、收货、理赔、取消订单、交易结束、略过.这个事件日志中包含7个不同的发生序列，每个序列发生的次数不同，序列的上标表示发生次数,例如〈A,B,C,E,F,Y,G,I,L〉80表示序列〈A,B,C,E,F,Y,G,I,L〉发生了80次.

下面利用本文提出的流程挖掘算法，对上述app给出的网上购物事件日志进行挖掘，以此验证本文提出算法的可行性.

1)将所有的日志序列按照发生序列及发生次数进行排序：{ABCEFYGIL(80)，ABCEYFGIL(63)，ABCEFYGHJKL(56)，ABDEGIL(49)，ABDEYFGIL(43)，ABDEFYGHJKL(33)，ABCEFYGHJKL(20)}.

当经验阈值M=45时，选择发生次数大于等于45的序列建立活动关系表，并计算各活动间行为关系的个数.表1为根据日志中活动的行为轮廓建立的活动关系表.

表1 活动关系表

2)根据行为轮廓的定义，找出活动间的行为关系，结果如表2所示.

表2 活动间的轮廓关系表

3)根据表2列出的行为关系，结合Petri网的基础结构，构造出初始模型Model_1，如图1所示.

图1 初始模型

4)计算服从程度.依据定义计算模型与日志之间的服从性，得εcLP=0.673.取α=0.95作为服从性的标准值[7]，因εcLP=0.673<0.95， 因此需要进行优化.重新选择发生频数M(M⟸M-N)， 其中取N=10.优化后的模型如图2所示.

5)计算优化模型Model_2与日志的服从性，得εcLP=0.981. 该值表明，模型与事件日志具有较高的服从程度，符合要求，输出模型.

4 结论

本文给出的基于Petri网行为轮廓的网上购物流程挖掘方法，不仅能够清晰地表达活动之间复杂的业务流程关系,而且能够提高网上购物流程模型的运行效率，具有一定的应用价值.在流程挖掘过程中，本文仅对出现在执行日志中的活动进行了研究，但在实际执行过程中有些活动可能被隐藏或者被堵塞，即存在隐藏变迁和阻塞变迁等问题，因此今后将探讨隐藏变迁和阻塞变迁的问题，以提高本文方法的有效性.