李 莉

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

0 引 言

过程挖掘是工作流管理的一个子领域[1]。它在数据挖掘与业务流程管理的协同方面发挥着非常重要的作用，并极大地增强了商业智能技术。目前主要分为三种类型[2](1)发现：将事件日志作为输入，并在不使用任何先验信息的情况下生成模型，这是最突出的过程挖掘技术；(2)一致性检查识别事件日志中记录的现实是否符合模型，反之亦然；(3)增强：利用事件日志中记录的实际过程执行信息来扩展或改进现有的过程模型。

业务流程旨在实现某些目标，即流程目标。目标通常通过一些基本特征[3](例如它们的类型和属性)以及它们与其他目标和需求模型的其他元素的链接来建模。Fani Sani[4]等人提出在过程发现中应用子组发现，并将案例的属性作为子组分类的主要依据。Yukun Cao提出了一个属性驱动的层次聚类框架[5]，可以在用户指定的案例属性的基础上比较案例集之间的行为差异，结果表明从聚类的案例组中发现的模型比基于完整日志发现的模型具有更好的质量。

本文的研究就是将过程发现和目标相结合，发现具有不同属性案例的子目标。其余部分如下，第1节是相关的概念;第2节提出了子目标发现算法，并进行了详细阐述;第3节是实验部分;第4节是文章的总结和展望。

1 基本概念

定义1(事件日志)：A是活动的集合，一个事件日志是A上的序列的一个多集，即L∈M(A*)。σ∈A*是L中的一条迹。

定义2(迹和案例)C代表案例的集合，对于c∈C，存在一个映射函数πa:C→V,将案例的属性值映射到案例上，πa(c)=v代表案例c中属性a的值为v。

一个事件是一个活动的执行，可以被定义为ε=I×C×E×R×T,其中I是事件标识符的集合，C是案例标识符的集合，E是活动的集合，R是资源的集合，T是时间戳的集合。

2 基于案例属性和时间相关性发现子目标

2.1 基于案例属性对案例进行分组

在许多案例中，一些案例子集存在偏差，这些偏差可能是由具有特定人群产生。比如在手机购票过程中，由于操作失误而产生购票过程中断现象的人群大多数都是比较年长的群体，导致购票失败结果的各种操作则是需要改进的地方。在对不完整的案例进行研究时，首先将案例基于属性分类，得到具有特定类别标签的的子集。

子日志是基于所选案例的案例属性值的分组，是一个非重叠的案例集，只包含一个案例属性值。给定一个事件日志L，案例属性a∈A，对于所有的子日志Lv∈P(L,a)⊆P(L)φ，ULv∈P(L,a)Lv=L,Lv是完整事件日志中属性值为v的子日志，v∈V是案例属性a的一组案例属性值且∀Lv≠Lv′∈P(L,a)，Lv∩Lv′=φ。

算法1实现了案例基于属性的分组，首先将案例的属性映射到集合中，选择需要参照分组的的属性，将属性的取值范围进行划分，根据所选的属性范围划分出不同的子组，具体的算法思想如下：

算法1 基于案例属性的分类算法

Input:L,CBOutput:L1,…Li1 Function π∈(A→(C→UV))2 for all L ,c∈Cdo 3 πa(c)=v4 vi∈V5 ai∈A6 if πai(C)=vi and vi∈V then7 return Li8 i=i+19 endif10 repeat 11 return L1,…Li

在对案例进行基于属性的分组后，得到具有特定属性的子日志。对于分类后的子日志，可以应用各种过程挖掘算法发现子日志的主要流程模型，与原流程模型可能存在不同，存在原模型中缺失的活动。针对这些具有特定属性的流程模型，无法确定模型中的子目标，就需要明确目标与子目标之间的时间相关性，从而确定子目标。

2.2 时间相关性

在事件日志挖掘过程中，目标和子目标之间存在时间相关性，我们可以从多层事件日志中挖掘目标的细化模式-子目标。通过时间戳属性，可以看出在一系列的事件中，目标的实现在其子目标实现之后发生。

目标间的时间相关性模式：时间相关模式对子目标实现和父目标的实现施加时间约束，D为目标，d1…dn为子目标，d1…dn→D代表目标在所有子目标完成之后发生，目标和子目标之间存在顺序相关性，要求每个子目标实现的时间间隔完全包含在父目标实现的时间间隔中。

2.2.1 事件发生的时间间隔

一个案例中有多条日志，对于案例中的每条日志，每个事件发生的时间间隔不是一个固定值，定义一条日志中事件发生的时间间隔为：

hk=sk+1-sk

其中，sk+1为日志中第(k+1)个活动发生的时间，sk为日志中第(k)个活动发生的时间。

2.2.2 事件持续时间

对于每个事件都有开始时间和结束时间，这种情况称为事件持续时间，定义每个事件的持续时间为：

φk=fk-sk

其中，fk为日志中第(k)个活动结束的时间。

在一个活动周期中，假设正常情况下事件发生的时间间隔、事件持续时间、和该活动的截止时间戳分别用表示，可能的取值范围为：

hk∈{hmin,…,hmax}

2.2.3 基于时间相关性判定子目标算法

在算法2中的输入是基于属性分类后的子日志，对于从子日志中挖掘出的过程模型，相比完整日志挖掘出的模型有相同点和不同点，导致子目标无法确定。需要保证子目标事件的发生是包含在一个完整的迹中的一部分，由此提出了算法2。

算法2 基于目标与子目标的时间相关性判定子目标

Input: L1,…LiOutput :ξ={d1…dn} 1 Function Time ( L,ξ)2 for ∀Ek∈Li do3 if hk=sk+1-sk∈{hmin,…,hmax} then4 if φk=fk-sk<φd then5 if fk

算法2主要是应用了子目标与目标之间的时间相关性来判断子目标，由于子目标的发生要满足时间间隔在父目标实现的时间间隔中以及最终的活动时间戳之前两个条件，符合这个区间的活动视为子目标。

3 实 验

为了验证提出的子目标的概念对过程挖掘模型精度的影响，在PROM框架中采用真实数据进行实验对比。

3.1 实验设置

采用事件日志集(receipt phase of an environmental permit application process)进行实验，下表1是案例的详细情况，每个案例的事件数(min=1,max=25),每个案例的事件类别(min=1,max=15)。选取案例的一个属性(迹长度)作为研究的对象，将不同日志长度的案例进行分类，然后进行流程树挖掘。

表1 receipt phase of an environmental permit application process

3.2 对比分析

由流程树的结构性质，从图1中可以看出流程主要分为7个部分，活动(T07-1 Draft intern advice aspect 1)是基于属性进行过滤后的最后一个活动，根据子目标与目标发生的时间相关性，活动(T07-1 Draft intern advice aspect 1)可以作为案例的一个子目标进行研究。对完整的案例进行过滤操作，将活动(T07-1)作为最终的目标进行过程挖掘，挖掘出的结果如下图3所示，可以看出与图2中的流程树具有不同的结构层次。

图1 折叠流程树(1-5)

图2 折叠流程树(6-10)

图3 以活动(T07-1)为结束活动的流程树挖掘结果

对比图3中挖掘出的流程树模型与完整真实案例间的F-measure，通过计算得出F-measuresub≈0.99，F-measure=0.92

3.3 实验总结

为了便于对比和分析，将合成数据以及真实案例中子目标对应的流程树和原模型通过上述方法计算适合度、精确度以及F1-measure，具体的值如下图4所示。

图4 完整日志和子日志的F1-measure

通过对案例原始模型和对应子目标群体计算F-measure，完整的日志被分成多个子日志，从这些子日志中发现的模型只能捕获完整日志的部分行为，因此图4中子日志的流程树模型的适合度降低，由于附加行为的减少，精确度提升。但是提出的基于属性对日志进行划分的方法提高了过程模型的质量，得到的F-measure(sublog)大于原模型的值。

4 结 语

因为事件日志中可能包含不同特征的案例信息，将这些不同的案例放在一起分析可能会导致某些重要现象的丢失。为了解决这个问题，将案例中事件的属性以及目标和子目标之间的时间相关性应用到过程发现中，提高了过程发现模型的整体质量。

实验是基于于迹的长度属性进行分类，后续可以将事件类型和资源属性添加进去考虑，可以使得案例分析更具有针对性，得出的优化方案更加专业。