[0045] 为了使本发明的目的、技术方案及优点更加清楚明白，以下结合附图及实施例，对本发明进行详细说明。
[0046] 相反，本发明涵盖任何由权利要求定义的在本发明的精髓和范围上做的替代、修改、等效方法以及方案。进一步，为了使公众对本发明有更好的了解，在下文对本发明的细节描述中，详尽描述了一些特定的细节部分。对本领域技术人员来说没有这些细节部分的描述也可以完全理解本发明。
[0047] 如图1所示，本发明的一种基于轨迹重演的业务流程剩余活动序列预测方法，包括以下步骤：
[0048] S1.输入原始日志文件 其中 由 条流程轨迹σ＝组成，每条流程轨迹σ由|σ|个事件 e＝(CaseID,Activity,Resource,StartTime,CompleteTime,attr1,attr2,…attrN)组成，其中CaseID代表事件所属的实例，Activity代表事件执行的活动，Resource代表事件执行所需的资源，StartTime和CompleteTime分别代表该事件的开始时间和结束时间，attr1,attr2,…attrN代表该事件的其余N个属性，日志的活动集合被记为A。
[0049] S2.根据CompleteTime对 中的流程轨迹排序后生成训练数据。
[0050] S3.将训练数据中的流程轨迹拆分为前缀轨迹和对应的后缀轨迹，前缀轨迹 pt＝为轨迹σ的前k个事件，而其对应的后缀轨迹st为轨迹σ的后 |σ|‑k个事件。
[0051] S4.使用过程挖掘算法从训练数据中挖掘Petri网PN。本实施例中，使用的过程挖掘算法为Inductive Miner算法，其挖掘得到的Petri网表达式如下：
[0052] PN＝(P，T，F，A，π，M)
[0053] 其中P＝{p0,p1,…,p|P|‑1}为Petri网中的库所集合，|P|表示Petri网中库所的数量，每个库所持有非负数量的托肯，库所pi持有的托肯数目被记为β(pi)； T＝{t0,t1,…,t|T|‑1}为Petri网中的变迁集合，|T|表示Petri网中变迁的数量； F＝(P×T)∪(T×P)是连接库所和变迁的有向弧集合；A为日志的活动集合；π是一个映射函数，用于将变迁ti∈T与A中的活动或者不可观察活动相关联，其中与不可观察活动相关联的变迁为隐藏变迁；M＝[β(p0),β(p1),…,β(p|P|‑1)]是Pet ri网中托肯的分布情况，也被称为Petri网的标识，M的初始状态记为Minit。
[0054] S5.使用轨迹重演技术将训练数据中的每个前缀轨迹pt在S4挖掘得到的Petri 网上逐个进行轨迹重演得到Petri网中托肯的分布情况，记为执行上下文 BehavContext(pt)；轨迹重演过程中，遍历pt的每个事件对应的变迁t，判断其是否满足使能条件即其输入集合的库所是否都持有托肯；对于不满足使能条件即没有持有托肯的库所pi采用以下方法使其满足托肯要求：首先判断是否有库所pj与其存在由隐藏变迁组成的最短路径，如果存在则触发该条路径上的隐藏变迁，即pj中的托肯数目减一，pi中的托肯数目加一，如果不存在，则将pi中的托肯数目额外加一。
[0055] 本实施例中，该S5步骤具体包含以下步骤：
[0056] S51.对于前缀轨迹pt，首先将其执行上下文信息BehavContext(pt)初始化为一个空矩阵；然后将Petri网的初始托肯分布即Minit拼接至BehavContext(pt)；
[0057] S52.按序遍历pt的每个事件，根据π映射函数获取对应的变迁t，并判断t是否满足使能条件，即其输入集合°t中的每个库所是否持有托肯，如果满足则执行步骤S521，否则，执行步骤S522；
[0058] S521.触发变迁t，即将变迁t的输入集合中°t每个库所的托肯数目减一，其输出集合t°中每个库所的托肯数目加一，并更新Petri网的托肯分布M，然后执行S5 3，其更新计算步骤如下：
[0059]
[0060] M＝[β(p0)，β(p1)，...，β(p|P|‑1)]
[0061] S522.获取°t中未持有托肯的库所集合，记为PTokenMissing；获取除°t中库所之外，当前持有托肯的库所集合，记为PToken；对于PTokenMissing中的每个库所pi，判断是否存在库所pj∈PToken与其存在由隐藏变迁组成的最短路径，如果存在则触发该条路径上的隐藏变迁，即pj中的托肯数目减一，pi中的托肯数目加一，使得pi满足托肯要求；如果还存在未满足托肯要求的库所，手动将其托肯数目加一；最后执行步骤S521；
[0062] S53.将当前Petri网的托肯分布M拼接至BehavContext(pt)。
[0063] 图2展示了一个轨迹重演的例子，即将活动序列为
的轨迹σ在Petr i网中重演的示例。如图所示，在起始状态，仅库所p0存在托肯，因此当前Petri 网的标识为pn.Minit＝[1,0,0,0,0,0]。当进行重演时，σ的第一个活动A对应的变迁为t0，t0目前为使能状态。因此触发t0，库所p0的托肯被消耗而库所p1中会产生一个托肯，从而得到新标识pn.M＝[0,1,0,0,0,0]。之后执行活动C，C对应的变迁为处于使能状态的t2，执行之后p1中的托肯被消耗，而p3中产生一个托肯，获得新标识pn.M＝[0,0,0,1,0,0]。下一个执行活动为F，其对应的变迁为t5，而此时t5并未达到使能状态，因此使用隐藏变迁使其强制满足使能条件。t5的输入集合为库所p4，目前持有托肯的库所为p3。通过对Petri网的分析可以观察到p3和p4之间可以通过隐藏变迁th2相连。因此，触发th2使p3的托肯转移至p4，此时的标识 pn.M＝[0,
0,0,0,1,0]。最后，触发变迁t5以完成整条轨迹的重演，获得最终的标识pn.M＝[0,0,0,0,
0,1]，即为该轨迹重演后得到的执行上下文。
[0064] S6.基于步骤S5得到的执行上下文BehavContext(pt)，计算其与训练数据中其他所有前缀轨迹的执行相似度TBS(σ1,σ2)，然后从中为其选取TBS(σ1,σ2) 最大的候选前缀轨迹集合Spt，其计算公式如下所示：
[0065]
[0066]
[0067] 其中，Eqij表示两条轨迹σ1,σ2在执行第i个活动之后在第j个库所的托肯数量的等价性，BehavContext(σ1)ij表示σ1在执行第i个活动之后在第j个库所的托肯数量，BehavContext(σ2)ij表示σ2在执行第i个活动之后在第j个库所的托肯数量， |σ1|和|σ2|分别代表轨迹σ1和σ2的事件数。
[0068] S7.对流程轨迹中每个属性的重要性即属性权重进行计算，具体步骤如下：
[0069] S71.首先对流程轨迹的属性进行筛选，删除无关属性后形成新属性集合D；被删除的无关属性一般为与流程执行相关但与流程分析无关的属性。本实施例中，被删除的无关属性为用于编号的ID属性，例如如案例ID属性和事件ID属性。
[0070] S72.从训练数据中随机选择10％流程轨迹，并将它们的前缀轨迹集合记为 S′pt，对于S′pt中的每条前缀轨迹，根据以下属性序列相似度计算公式为其从剩余90％的训练数据中选取 条最相似的前缀轨迹记为SimPTi，其中属性序列相似度计算公式如下：
[0071]
[0072] 其中 和 为流程轨迹σ1和σ2中由属性 的属性值构成的有序序列，即属性序列； 表示经过归一化的 和 之间的欧式距
离， 表示 和 之间的Demerau‑Levinstain
距离。
[0073] 其中需注意的是，对于欧式距离 的计算，如果σ1和σ2的序列长度不一致，则使用后向零填充法使其统一。
[0074] S73.对于每个属性 统计S′pt中所有前缀轨迹的剩余活动序列与SimPTi的剩余活动序列之间的相似度CDi，从而得到相似度向量 根据该相似度向量计算得到最终的属性权重向量W，具体公式如下：
[0075]
[0076]
[0077] 其中，ActSeq1和ActSeq2代表两条活动序列，DL_Dist(ActSeq1,ActSeq2) 表示两条活动序列的Demerau‑Levinstain距离，l1和l2分别代表两条活动序列的长度；W是属性权重向量， 为新属性集合, 为新属性的数量，wi表示属性 的权重。
[0078] S8.针对待预测的当前流程轨迹，计算其与所述候选前缀轨迹集合Spt中的每条流程轨迹之间基于属性的轨迹相似度TS(σ1,σ2,W)，即两者之间所有属性序列相似度的加权和，其计算公式如下：
[0079]
[0080] S9.经过S8的计算后，筛选出Spt中基于属性的轨迹相似度最大的一条流程轨迹，并将其剩余活动序列作为当前流程轨迹的预测剩余活动序列。
[0081] 下面基于上述S1～S9方法流程，通过实施例进一步展示其技术效果。
[0082] 实施例
[0083] 本实施例步骤与具体实施方式前述步骤相同，在此不再进行赘述。下面就部分实施过程和实施结果进行展示：
[0084] 本实施例选用四个来源于4TU Centre for Research Data(https://data.4tu.nl/) 的真实数据集进行实验。数据集的介绍如下，其特征如表1所示。
[0085] Helpdesk：此数据集包含来自意大利软件公司服务台的自2010年1月至 2014年1月的票务管理流程执行信息。日志中的所有案例均始于在票务管理系统中插入新票证，结束于关闭票证。
[0086] Sepsis：Sepsis数据集来源于荷兰某医院，记录了由ERP系统记录的医院败血症患者的诊断流程，包括病人注册挂号开始直至出院的所有事件。
[0087] BPIC2013 Incidents：BPIC2013数据集是来自Volvo IT Belgium的事件日志，包含来自名为VINST的事件和问题管理系统的事件。在数据集中主要分为两种类型的实例，即处理事件的实例和处理问题的实例。本章对数据集进行过滤得到所有处理事件的案例，即BPIC2013 Incidents，并在这些案例上进行实验。
[0088] BPIC2012O/BPIC2012W/BPIC2012W去重：BPIC2012数据集是从荷兰金融学院获取的事件日志，代表全球融资组织内个人贷款或者透支的申请流程。该流程可以分为与申请相关的三个子流程，即BPIC2012A、BPIC2012O和 BPIC2012W。本章使用BPIC2012O、BPIC2012W进行实验。特别地，由于 BPIC2012W数据集中包含大量的自循环，即单个事件活动会被连续执行数次，这些自循环可能会影响最终的预测结果。将BPIC2012W数据集进行了处理，即对于一些重复执行的事件，仅保留第一个事件而删除冗余的事件，经过处理之后的数据集被称为BPIC2012W去重数据集。本实施例也同样采用 BPIC2012W去重数据集进行了实验。
[0089] 表1数据集特征表
[0090]
[0091] 为验证本发明技术方案的技术效果，本实施例选取Demerau编辑距离相似度对预测结果进行衡量，其主要用于衡量两条序列之间转换所需的单字符操作次数(插入、删除、替换和交换)，DL距离相似度计算公式如下：
[0092]
[0093] 其中ActSeq1和ActSeq2代表两条活动序列，DL_Dist(ActSeq1,ActSeq2)表示它们的DL距离，l1和l2分别代表它们的长度。
[0094] 利用本发明方法在六个数据集上进行实验并计算每个数据集的平均DL距离相似度的结果如表2所示。对每个数据集过滤特定长度前缀轨迹之后的平均 DL距离相似度进行了统计。即对于Sepsis、BPIC2013 Incidents、BPIC2012O 和BPIC2012W数据集，分别计算过滤长度小于2、5和10的前缀轨迹之后的平均DL距离相似度。由于Helpdesk全部和BPIC2012W去重数据集的平均轨迹长度小于其余四者，因此对其计算过滤长度小于2、4和6之后的平均DL距离相似度。由表可知，不同数据集间相似度差异较大。在所有的情况下， Helpdesk为表现最佳的数据集，BPIC2012W去重次之，而BPIC2012W的表现则最差。根据表格中的数据，还可以发现对于大多数数据集而言，滤除一些短前缀轨迹会使得整体的相似度更高。
[0095] 表2实验结果表
[0096]
[0097] 以上所述的实施例只是本发明的一种较佳的方案，然其并非用以限制本发明。有关技术领域的普通技术人员，在不脱离本发明的精神和范围的情况下，还可以做出各种变化和变型。因此凡采取等同替换或等效变换的方式所获得的技术方案，均落在本发明的保护范围内。
