基于轨迹聚类种群的遗传过程混成挖掘算法

汤雅惠，朱 锐，李 彤，南峰涛，郑 明，马自飞

(1.云南大学 信息学院，云南 昆明 650500；2.云南省软件工程重点实验室，云南 昆明 650091；3.云南大学 软件学院，云南 昆明 650091；4.云南农业大学 大数据学院，云南 昆明 650201)

0 引言

过程挖掘是现代组织用来管理复杂运作过程的一种重要工具，能从现代信息系统普遍产生的事件日志中抽取过程知识，为相关领域应用中的过程发现、监督和改进提供新的手段[1]。过程挖掘的理念是从事件日志中提取出知识，进而去发现、监控和改进实际过程(即非假定过程)[2]，其目标在于能够快速地发现一个简洁、合理、优质的过程模型，以支持过程的分析与改进。

过程挖掘方法方兴未艾，目前已经出现了许多挖掘算法[3-4]，它们各有各的适用范围以及优缺点。以遗传挖掘(Genetic Process Mining, GPM)算法[5]为例，算法使用模型的4个质量维度作为挖掘导向，相对于其他挖掘算法，更容易生成高质量的过程模型；但由于GPM模仿生物的自然演变，使用迭代的方法挖掘模型，因此对于大型事件日志，种群准备时间和迭代时间将成倍增长，为产生质量较高的合理模型可能需要迭代多次，从而导致算法效率极低。

对大型日志的处理，也是过程挖掘技术面临的难点。现实过程一般较为复杂繁琐，存在大量活动，这会造成事件日志的规模庞大、结构复杂。而一般的过程挖掘算法在处理此类事件日志时效率较低，通常会产生“意大利面”[6]式的极为复杂的过程模型，“意大利面”式过程模型难以理解，对实际过程几乎起不到监控和改进的作用。

针对以上问题，本文提出一种轨迹聚类种群的遗传过程混成挖掘(Genetic process hybrid Mining based on Trace Clustering population, GMTC)算法。该算法从优质初始种群的准备和遗传算子的优化两个方面入手，对遗传挖掘算法进行改进，使得算法能够有效地处理大型日志，生成高质模型。因为初始过程模型的质量越高，达到高质量模型所需的改变就越少，所以GMTC一方面使用聚类轨迹(trace)的方法将事件日志划分成多个小型子日志，对它们分别使用归纳挖掘(Inductive Miner, IM)[7]生成多个过程模型，以此作为遗传挖掘算法的初始种群，代替原有随机生成的低质量的种群，最后使用遗传算法的优化能力从中整合得到高质量的模型；同时，使用对齐日志(alignment)得到的信息指引遗传操作中的突变操作，代替原有的随机突变操作，使种群朝着正确的方向演变，提高种群整体质量，加快算法收敛速度。

本文的主要贡献如下：

(1)使用轨迹聚类以及IM算法对事件日志进行预处理，能有效地为遗传挖掘算法准备优质初始种群．简化遗传挖掘算法的挖掘环境、提高算法效率。

(2)对遗传算子中的突变操作进行改进，使用基于对齐的突变操作代替原有随机突变操作，使突变操作由随机变为有向，从而加快种群优化速度。

(3)提出综合质量函数来平衡评估模型的4个质量维度，使得算法能够生成高综合质量的模型。

1 相关工作

过程挖掘的目标是从事件日志中提取过程相关信息。目前，已经出现了许多挖掘算法[8]，每种算法都有其优缺点和适用对象。如α算法[9]只适用于不带短循环和隐式库所的结构化过程模型；启发式挖掘算法[10]能够较好地处理日志噪声，但是生成模型的拟合度较低，且不能处理非局部选择结构和重复活动；基于区域的挖掘算法[11]得到模型的精确度较高，能有效处理复杂过程结构，但挖掘效率较低且会造成空间爆炸。

遗传挖掘算法由Van Der Aalst等[5]基于遗传算法的思想提出。起初是使用因果矩阵表示模型，但是该表示方法会使模型存在死锁。因此，BUIJS等[12]使用过程树来表示模型，可避免死锁的产生。但仍然难以平衡算法的时间复杂度和挖掘模型质量之间的矛盾，即对于大型日志，为产生一个高质量的模型会耗费大量时间。而本文提出的GMTC算法，从优质初始种群的准备和遗传算子的改进两个方面优化遗传挖掘算法，能高效高质地处理大型事件日志。

针对大型事件日志的挖掘会生成“意大利面”式模型的问题，可以使用聚类事件日志中轨迹的方法划分日志，使得每个聚类的结果簇对应于一个可以由过程模型充分表示的连贯过程轨迹集[6]。文献[13]基于事件日志配置文件对轨迹进行聚类，可以应用于灵活的环境，改进挖掘结果。文献[6]用一种基于通用编辑距离的方法对轨迹进行聚类。文献[14]提出一种基于保守模式的特征集聚类方法。

挖掘算法从事件日志中发现过程模型，合规性检查技术[15]可用于检测日志中的行为和建模行为之间的差异，它通过构造包含事件日志和过程模型之间的最小偏差量的对齐来实现该目的。而合规性检查技术只能发现这些差异，模型的实际修复则只能通过用户来完成。且目前合规性检查技术大都集中在Petri网上[16]，很少有针对过程树的合规性检查。文献[17]通过对齐(alignment)日志的技术来修复Petri网表示的过程模型，使模型符合日志中提出过程树的修复方法，而本文将其方法进行细化，使用对齐日志得到的信息指导遗传挖掘算法中过程树的发现，能够在迭代挖掘的过程中使过程树朝着更符合日志的方向演变。

2 GMTC算法设计

本文提出的GMTC算法总体框架如图1所示。GMTC算法的输入为事件日志，输出为针对该日志挖掘出的过程模型，将算法分为3个模块分别进行说明：①模块一基于马科夫聚类(Markov CLuster, MCL)聚类算法对日志进行划分，首先分析事件日志，选定合适的轨迹属性作为聚类维度，对事件日志中的轨迹进行聚类，将事件日志划分成N个子日志，每个子日志是在所选轨迹属性上的一组相似轨迹的集合；②模块二使用IM算法对N个子日志挖掘生成N个过程模型作为遗传挖掘算法的初始种群；③模块三使用遗传挖掘算法对此N个模型进行优化整合。GMTC算法通过轨迹聚类对事件日志划分的方法，可以减少IM算法一次处理的数据量，提高IM算法的效率，挖掘出具有高简洁度和高精确度的过程模型。以这N个模型作为遗传挖掘算法的初始种群，借助遗传算法的优化能力，从中整合得到高质量的过程模型。GMTC算法将多种算法混成，它们之间优势互补，可以取得单一算法难以实现的高质挖掘结果。目前GMTC算法已经在过程挖掘工具ProM[2]上实现。在分别对各个模块进行说明之前，先给出如下定义。

定义1事件，属性[8]。ε为事件空间，是一组所有可能事件的标识符集合，事件会被不同的属性所标识，比如一个事件可能有一个时间戳、有相关联的成本，或由一个特定的人执行，等。其中：

(1)设N为一组属性名的集合。

(2)对于任意的事件e∈ε以及属性名n∈N，#n(e)是事件e所对应的属性n的值。

(3)如果事件e不包含名为n的属性，则#n(e)=⊥。

定义2案例，轨迹，事件日志[8]。设C为案例空间，即所有可能的案例标识符的集合，案例也具有属性。

(1)对于任意案例c∈C和属性n∈N,#n(c)是案例c的属性n的值。

(2)如果案例c不包含名为n的属性，则#n(c)=⊥。

(4)轨迹是事件σ∈ε*的一个有限序列，其中每个事件只出现一次，即对1≤i≤j≤|σ|，有σi≠σj。

2.1 优质初始种群准备

算法的模块一基于MCL[18]算法划分事件日志。算法将事件日志作为输入，输出是对该日志的轨迹聚类结果，即多个子日志。首先，对事件日志进行分析，选择轨迹的某一属性作为聚类维度，聚类维度决定了聚类结果以及生成子日志的数量；然后算法使用余弦相似度创建轨迹相似性矩阵，事件日志中的每个案例都被映射到一个多维向量上，案例的属性则映射到向量的不同维度上；最后，算法根据向量之间的相似度进行聚类。而在实际过程中，相似的一组轨迹往往对应着包含一致行为的特定过程。对这样的一组轨迹进行挖掘，容易得到较好的挖掘结果。

定义3轨迹相似度矩阵[19]。设L⊆C为一个事件日志，S(L)=(L×L)→[0.0,1.0]指L上所有可能的轨迹相似度矩阵。对于L上轨迹l,l′∈L以及一个相似度矩阵S∈(L)，S(l,l′)表示案例l和l′之间的相似度。

定义4轨迹聚类[19]。设L⊆C为一个事件日志，在L上的一个轨迹聚类是L的一个子日志。一个轨迹聚类TC⊆P(L)是事件日志L上的一组轨迹。每个轨迹都至少是一个轨迹聚类的一部分。

算法的模块二对聚类得到的子日志使用IM算法分别挖掘生成子过程模型。一方面，IM算法能够在多项式时间内挖掘出一个拟合度达到80%以上的高质过程模型。而随机产生的初始种群，拟合度一般在60%左右；另一方面，IM算法使用文献[20]中的高度通用的过程发现框架，可以保证挖掘出来的所有模型都是合理的(sound)[7]，一个合理的模型是没有死锁和其他异常的模型。遗传挖掘算法需要多次评估和改进过程模型，如果模型不合理，则需要花费额外时间对模型进行修复。因此，使用IM算法能够为遗传挖掘算法提供更为优质的初始种群。

模块一以及模块二为遗传挖掘算法准备了优质种群，下面详细介绍模块三，基于遗传挖掘算法的模型优化与整合。

2.2 遗传算法对模型进行优化整合

2.2.1 过程模型的表示方式

文献[21]表明，因为Petri网包含日志中的隐式库所、很难对Petri网定义遗传算子，并且其表达能力在某些情况下十分有限，所以不适合作为遗传挖掘算法执行内部的模型表示方法，而使用因果矩阵表示的模型则可能含有死锁[21]。因此，使用过程树作为算法内部过程模型的表示方式。过程树的主要优点是块结构的过程模型所具有的合理性[22]。遗传挖掘算法需要多次评估和改进过程模型。因为过程树本身就是合理且健全的，所以不必检测和修复不完整的过程模型。而在最终算法结束后，可以将最终生成的过程树转化为Petri网。因此，使用过程树作为遗传算法的内部模型表现形式，使用Petri网作为最终呈现的模型表现形式。

定义5Petri网，已标记网系统[8]。一个Petri网(P,T,F)包含一组库所P(place)、来自P的一组变迁T，以及一组箭头F(arc)⊆(P×T)∪(T×P)。过程模型H中的标记m为每个库所p∈P分配m(p)个托肯。一个网系统H=(P,T,F,m0,mf)是一个有开始标记m0和一个结束标记mf的Petri网(P,T,F)。

定义6过程树[23]。过程树是一个不含圆的有向连接图，第一层节点称为树根，以下各层节点均为上层节点对应的孩子。过程树由运算符节点(非叶子节点)和活动节点(叶子节点)组成。运算符节点表示过程的控制流结构，包括：顺序→、并行∧、排它选择×、非排它选择∨，以及循环；而活动节点代表单个活动变迁。

2.2.2 综合质量函数设置

模型质量的评估主要基于4个质量标准：拟合度(replay fitness)[24]、精确度(precision)[25]、泛化度(generalization)[12]以及简洁度(simplicity)[26]。一个拟合度好的模型能反映事件日志包含的行为；简洁度意味着模型最简单；精确度避免欠拟合，而泛化度则避免过拟合。尽管4个质量标准都有量化方法，但4个质量标准相互竞争，很难在它们之间达到平衡。同时，一般过程挖掘算法只能顾及到部分质量维度[27]，例如，基于区域的挖掘算法产生的过程模型的拟合度和精确度较好，但是泛化度和简洁度较差。文献[26]表明，4个质量维度都十分重要，其中任何一个值较低都将影响挖掘结果。因此，为平衡4个质量维度，提出综合质量(Comprehensive Quality,CQ)函数，GMTC算法在迭代的挖掘模型的过程中使用该函数对模型质量进行监督，将综合质量作为挖掘导向。综合质量函数表示为：

CQ=(Fr+Pe+Gn+Sm)/4。

式中：Fr，Pe，Gn和Sm分别为过程模型在拟合度、精确度、泛化度和简洁度这4方面的度量值。一个模型的综合质量值可以较好地反映模型的综合质量。

2.2.3 过程树表示的遗传算子

GMTC算法使用综合质量函数计算种群中所有过程树的综合质量值，按照精英选择比例将综合质量值较高的多个过程树直接保留到下一代，其余过程树则由遗传操作生成。为了得到较好的挖掘结果，种群应当努力做到“好而不同”[26]，一方面，算法应尽可能地访问更大的搜索空间，使种群具有较好的多样性；另一方面，通过遗传操作应当可以有效提高种群中过程树的质量。

遗传操作分为替换(replacement)、交叉(crossover)和突变(mutation)[22]3种。替换操作使用随机产生过程树替换掉种群中质量最低的一部分过程树；交叉操作交换两个过程树之间随机选择的两个子树;替换和交叉操作很难直接提升生成过程树的质量，它们主要用于增加种群多样性，只有突变操作可以提高种群中过程树的质量，它直接对节点操作，包括移除节点、添加节点和变更节点。

遗传挖掘算法中，一般使用随机的方式进行突变操作，即随机选择节点并改变。而基于随机方法的突变操作难以较快地提高过程树的质量。因此，本文使用在计算过程树的拟合度时对齐日志得到的信息来指引突变操作，让突变从随机变为有向，提高搜索的速度与质量，加快遗传算法收敛。具体可见2.3节。

2.3 基于对齐日志的突变操作

对齐技术能够比较过程模型的行为和事件日志中记录的行为，发现他们的共性和偏差[17]。当发现过程模型和事件日志“不一致”时，可以通过发现的偏差对模型进行修复。而对齐技术仅限于发现差异，模型的实际修复则只能通过用户来完成。基于对齐的合规性检查算法，其本质是在模型上逐条重放其对应的轨迹，通常，并非所有活动都能在模型上完全按照次序重放下来，故引入对齐的概念。同时，引入“≫”标识符，表示用来对齐，而并未真正执行的具体任务。

定义7对齐，移动[17]。设N=(P,T,E,l,m0)为一个已标记网系统，l=a1a2a3…am是ε上的一条轨迹，一个移动(move)是一个(b,s)∈(ε∪{≫})×(T∪{≫}){(≫,≫)}，l到N的一个对齐是一个序列α=(b1,s1)(b2,s2)…(bk,sk)。

(1)当且仅当bi=≫且si≠≫，称移动(bi,si)为在模型上的移动(move on model)；

(2)当且仅当bi≠≫且si=≫，称移动(bi,si)为在日志上的移动(move on log)；

(3)当且仅当bi≠≫且si≠≫，称移动(bi,si)为同步的移动(synchronous move)。

GMTC算法中的突变操作使用对齐日志获得的信息有针对性地对过程树进行突变。而在计算种群中过程树的拟合度时，会将过程模型与事件日志对齐。根据对齐时发现的过程树中不符合日志的行为，对过程树进行改进，使得遗传过程挖掘算法种群中的过程树朝着更接近日志的方向演变，从而加快算法收敛。下面详细介绍GMTC算法中突变操作的具体方法。

2.3.1 基于对齐的突变移除

突变操作中的移除节点操作可以去除节点所对应的活动。选取两条对齐结果，以这两条结果为例，如果所选的叶子节点在对齐期间总是被跳过(即活动仅在模型上移动)，则移除关于该叶子的行为，如图2所示；如果所选的叶子节点在对齐期间有时被跳过，则可以为模型添加选择节点及tau活动，如图3所示，包含两个轨迹(a,b,c)和(a,c)的事件日志，(a,b,c)可以完全匹配过程树，轨迹(a,c)则需跳过叶子b才可在模型上移动。为使轨迹更加匹配过程树，可以给叶子b添加一个×操作符父节点、以及一个tau节点作为兄弟节点；由于循环操作节点要求具有3个孩子节点，若该叶节点的父节点为循环节点，则将该节点改为tau活动，如图4所示。

a≫cabc

a≫cabc

a≫cabc

abcabc

2.3.2 基于对齐的突变添加

添加节点与移除节点相反，如果所选节点总在日志中出现而未在模型中出现，则添加相应节点。如果被选择的节点与要添加的节点顺序不定，则为他们加入并行父节点，如图5所示，选择节点a，为其添加b兄弟，其父节点为并行操作符节点；类似地，如果两个活动的顺序是一定的，则加入顺序操作节点；如果在每个轨迹中只会出现一个活动，则加入非排它选择操作节点，如图6所示；如果有时候出现一个活动，有时候出现两个活动，选择并行操作节点；最后，如果一个活动被观察到多次，则添加循环操作节点。

a≫ca≫cabcabc

a≫ca≫cabcabc

abca≫c

bac≫ac

a≫ca≫c

b≫ca≫c

2.3.3 基于对齐的突变变更

变更节点操作中，如果选择了运算符节点，则重构该节点下的整个子树。首先，从子树中随机选择两个活动，然后使用添加节点中确认运算符节点的方式选择运算符。只要子树中存在未处理的活动，就会继续选择下一个活动。再次确定运算符，并将其添加到过程树中。重复该过程，直到处理完所有活动。如图7所示，如果选择了顺序操作符进行变更操作，则过程树基于轨迹(a,b,c)和(b,a,c)进行重构。首先选中a和b，添加并行操作符，最后使用顺序操作符添加c。

abc≫a≫cb

bac≫≫acb

通过使用以上3种基于对齐的突变操作，可有效提高种群中过程树的质量。为了验证基于对齐的突变的有效性，分别选取两组事件日志做验证。使用基于随机突变的遗传挖掘算法以及基于对齐突变的遗传挖掘算法分别对两组数据进行挖掘，其他参数均一致，设置种群进化500代后停止。第一组数据是个小型日志，共包含50条轨迹、555个事件(简称数据一)，其模型质量随着挖掘代数变化的对比如图8所示。第二组数据包含200条轨迹、2195个事件(简称数据二)，也分别使用两种挖掘算法，其模型质量随着挖掘代数变化的对比如图9所示。

从图8可以看出，在数据1中使用改进过的遗传算法，最终质量得到了有效提升，且因为改进后的遗传算子可以有效提高过程树的质量，所以比原有遗传挖掘算法收敛更快。图9中，由于数据量较小，改进后的遗传算法得到的模型质量提升没有数据一得到的模型质量提升明显，但依然比改进前的遗传挖掘算法收敛的更早。因此，通过对齐日志所得信息可以有效改进突变操作，使得过程树通过突变操作能显著提升质量，进而加快遗传挖掘算法收敛速度。

2.4 遗传过程混成挖掘算法框架

遗传过程混成挖掘对应于GMTC算法的模块三，算法共有初始化、选择、繁殖以及结束4个步骤。其中，算法的输入是过程树集，输出为优化整合得到的一个完整的模型和其综合质量值。图10是遗传过程混成挖掘算法的流程。首先，为群体中的每个过程树根据综合质量函数计算综合质量值，其次按照一定比例选择其中质量最优的多个过程树，无需任何改变直接保留到下一代，剩下的过程树则使用遗传操作改进。同时设置停止标准，如迭代次数。如果停止条件不满足，则迭代上面的过程直至满足停止标准。通过这种精英选择和遗传操作，每一代种群中最优过程树的综合质量会变得越来越好，末代种群中综合质量值最高的过程树即为最终的挖掘结果。

本文设置种群中综合质量值最高的25%的过程树个体直接保留到下一代；突变操作旨在提高过程树质量，因此选择剩余的过程树中排在前25%的过程树进行突变操作；交叉操作和替换操作旨在增加种群多样性、扩大搜索空间，因而再次选择剩下的过程树中排在前25%的过程树进行交叉操作；综合质量值最低的25%的个体使用替换操作直接替换。算法1是GMTC算法中遗传过程挖掘部分的算法伪代码。

算法1GMTC算法中遗传过程挖掘部分的算法。

输入：日志L；迭代次数m；比率α=0.25；过程树集ProcessTrees={t1,t2,…,tN}。

输出：过程树PT。

过程：

1 for i=1,2,…,m do //迭代m次

2 for tree=t1,t2,…,tNdo //遍历整个过程树集合

3 cquality(tree); //计算每棵树的综合质量值

4 sort(tree); //按照综合质量值高低进行降序排列

5 end for

6 for j=1,2,…,N do

7 if 1≤j<α N then

8 Save_1=remain(ProcessTrees);//对综合质量值较高的在前25%的过程树直接保留至下一代

9 end if

10 if αN≤j<2α N then

11 select(ProcessTrees);

12 crossover(ProcessTrees); //对剩余的过程树中排在前25%的过程树进行交叉操作

13 Save_2=remain(ProcessTrees);

14 end if

15 if 2αN≤j<3 α N then

16 select(ProcessTrees);

17 mutation(ProcessTrees); //再次选择剩下的过程树中排在前25%的过程树进行突变操作

18 Save_3=remain(ProcessTrees);

19 end if

20 if 3 αN≤j≤4α N then

21 select(ProcessTrees);

22 replacement(ProcessTrees); //对最后剩下的树进行替代操作

23 Save_4=remain(ProcessTrees);

24 end if

25 end for

26 repeatProcessTrees=Save_1∪Save_2∪Save_3∪Save_4 ;

27 end for

28 PT=selectMAX(repeatProcessTrees);//选择质量最好的一棵过程树作为输出

3 实验

3.1 实验数据

本文使用8组数据来验证所提出的GMTC算法。第一组数据为根据一定的模型使用过程日志生成器(Process Log Generator, PLG)[28]生成的模拟日志，简记为TP;第二组数据是某市政府执行建筑许可申请程序过程的真实日志，数据参见文献[29]，简记为CL。事件日志均遵守MXML标准[30]，CL组日志的大小是TP组的10倍。TP组实验采用某城市地铁的购票过程，如图11所示，首先，系统进行路线展示(A)，其次顾客可以进行路线选择(B)，然后需要确定目的地(C)和乘坐人数(D)，系统会根据目的地和乘坐人数生成付款信息(E)，接下来，顾客可以选择投币支付(F)、刷卡支付(G)或是取消订单(L)，投币支付可以找零(H)，支付成功后系统显示投币支付成功(J)或者刷卡支付成功(I)，最后，系统生成单据(K)；过程结束。TP组实验事件日志来源于使用PLG工具对图12中的某地铁购票过程生成的1 000个过程轨迹，共包含8 108个事件，大小是2.81 MB。事件日志同时也包含轨迹级别和事件级别的属性。

CL组数据来源于CoSeLoG项目，整个事件日志记录了5个不同的市政府执行建筑许可申请程序的情况，分为5个事件日志。选取其中一个事件日志，首先对其进行过滤，以去除不完整和异常的案例。过滤后的日志中包含593条轨迹，17 817个事件，大小是19.4MB。事件日志总共有16个轨迹级别的属性，包括许可证组成的部分、计划结束日期和负责人等。事件级别的属性包含活动标签、执行时间戳和涉及的人力资源等。

剩下6组为公开数据集[32-36]，Traffic fine数据为道路交通精细管理过程[32]，经过滤处理后大小为42 MB，CCC19[33]数据为一致性检查挑战数据，经过滤处理后大小为1.53 MB，Loan application数据[34]为贷款申请过程数据，经过滤处理后大小为1.19 KB；Representational bias数据[35]为代表性偏差测试数据，经过滤后大小为2.8 MB；Benchmarking logs-choose数据[36]为测试算法的可扩展性数据，其中包含选择循环结构，其大小为2.6 MB；Benchmarking logs-parallel数据[36]也是测试算法的可扩展性数据，其中包含并行结构，其大小为184 KB。

实验的运行平台为Intel dual-core i7-3770 CPU(3.0 GHz)且具有12 G RAM的PC上。

3.2 实验设计方案及参数设置

实验设计方案如下：

(1)对TP组事件日志使用MCL聚类算法划分为多个子日志，使用IM算法分别挖掘子日志，分析挖掘结果，为GMTC算法准备初始种群。

(2)对TP组事件日志分别使用GPM算法和GMTC算法进行挖掘，对比挖掘时间和挖掘获得模型质量。

(3)对CL组事件日志分别使用GPM算法和GMTC算法进行挖掘，对比挖掘时间和挖掘获得模型质量。

(4)对TP组及CL组事件日志分别使用GPM算法和GMTC算法进行挖掘，设置不同的迭代次数，对比不同迭代次数下的综合质量值变化。

(5)对TP组、CL组事件日志分别使用α算法的改进算法α#[31]、IM、Heuristic以及整数线性规划(Integer Linear Programming, ILP)算法进行挖掘，计算综合质量，与GMTC算法挖掘的结果进行对比。

(6)对6个公开数据集分别使用α算法的改进算法α#、IM、Heuristic、ILP以及GPM算法进行挖掘，计算综合质量，与GMTC算法挖掘的结果进行对比。

在GPM算法和GMTC算法的对比实验中，迭代次数均设置为1 000代，且由于种群数量越少，算法的时间花销则越少[22]，GPM算法的初始种群数量与GMTC算法中初始种群的数量设置一致，同时GMTC算法的种群数量为通过MCL聚类轨迹最终输出的子日志的个数。

3.3 实验结果与分析

为得到合适的聚类结果，需要对事件日志进行分析，TP组事件日志中，轨迹属性Traceatt：paytype表示顾客支付的方式，因为不同的支付方式对应的购票过程存在明显差异，使用相同的支付方式的购票过程相似度更高，所以使用此轨迹属性作为聚类维度。

如图12所示为使用聚类维度付款方式(Traceatt：paytype)对TP组事件日志进行聚类的结果，其中每个圆代表一个簇，圆的面积代表簇中包含的轨迹数目的多少。将它们导出为子日志，进行挖掘分析。聚类维度Paymethod对应cash1的输出为一个簇，其中包含236条轨迹，将其作为第一个子日志Sublog1输出；第2个簇的聚类维度Paymethod对应的属性值为cash2，簇中共含有268条轨迹，将其作为第2个子日志Sublog2输出；第3个簇的聚类维度Paymethod对应card，其中包含416条轨迹，将其作为第3个子日志Sublog3输出；而聚类维度Paymethod对应于其他的值的簇，共有80个，每个簇仅包含一条轨迹，将这80个簇作为第4个子日志Sublog4输出。对聚类之后的4个子日志分别使用IM算法挖掘，得到如图13～图16所示的4个子日志的挖掘结果。

对挖掘结果进行分析，可以发现子日志Sublog1挖掘获得模型对应的场景是顾客投币支付，系统找零的情况；子日志Sublog2挖掘获得模型对应的场景是顾客投币支付，系统不找零的情况；子日志Sublog3挖掘获得模型对应的场景是顾客刷卡支付的情况；子日志Sublog4挖掘获得模型对应的场景是顾客取消支付的情况。由此可知，通过对事件日志进行分析，找到合适的聚类维度进行MCL轨迹聚类，可以有效地将在所选聚类维度上相似的轨迹划分到同一个簇里。同时采用GPM算法对事件日志进行挖掘，表1是挖掘获得模型的质量维度对比，可以看到GMTC在原有算法的基础上缩短了1.7%的综合质量值，且在时间上缩短了3.7%。TP组实验由于数据量不大，使用两种算法的时间差异不太明显。

其次，对CL组的数据进行实验。分析CL组事件日志发现，由于相同的负责人负责同种类型的建筑许可，而同种类型的建筑许可申请过程比较相似，以Responsible_actor作为维度进行聚类，图17是聚类结果。Responsible_actor对应的属性值是负责人的编号，size是聚类中包含的轨迹数目。聚类结果为7个簇，分别对应7个不同的负责人所负责的许可证类型。将7个簇输出为7个子日志，对它们分别应用IM算法挖掘，生成7棵过程树。然后使用挖掘获得的7棵过程树作为GMTC算法中遗传挖掘模型集成整合部分的输入，图18是GMTC算法最终得到的模型(部分)。由表1可见，GMTC算法对于数据量较大的情况，比GPM算法有着显著的时间效率提高。同时在综合质量值方面，也比GPM算法高出3.3%。

表1 TP组、CL组数据使用GPM算法与GMPC算法挖掘获得的模型质量与时间对比

与此同时，综合质量值随着迭代次数的变化而变化。图19及图20是对TP组以及CL组数据采用GMTC算法与GPM算法进行挖掘时模型的综合质量值随迭代次数的变化。两组实验中，GMTC算法的初始种群综合质量值相对GPM算法更高，而随着迭代次数的增加，种群中的平均综合质量值不断增高，最终的模型得到了较好的综合质量。同时，迭代次数达到1 000代以上，综合质量值将很难继续上升。此时，两组实验中的GMTC算法与GPM算法均已收敛。

图21和图22是TP组与CL组事件日志分别使用α#、IM、Heuristic、ILP以及GMTC算法(迭代1 000次)挖掘获得模型的质量对比。在TP组中，由于数据量较小，基本每种挖掘算法的4个质量维度都可以达到较高的数值，α#算法以及IM算法则达到了较高的拟合度。但在其他3个质量维度以及综合质量值方面则是GMTC算法更占优势。而在CL组中，由于事件日志数据量较大，除了GMTC外的4种算法挖掘获得模型的综合质量值都偏低。挖掘获得模型的质量维度中，α#算法以及IM算法的精确度、Heuristic的精确度及简洁度、ILP算法的拟合度的数值都过于偏低，说明传统挖掘算法在对较大数据量的事件日志进行挖掘时，其准确度较低。而GMTC算法的4个质量维度值都较为稳定，且仍然取得了较高的综合质量值。由此可知，对于一般挖掘算法难以处理的大型事件日志，GMTC算法能够挖掘出较为精确且综合质量值较高的过程模型。

同时，对6个公开数据集分别使用α#、IM、Heuristic、ILP以及GMTC算法挖掘模型，对比模型质量，如图23～图28所示。由图可见，对于6个数据集挖掘所生成模型的共同的特征是，相对于其他算法，GPM算法以及GMTC算法得到的模型的综合质量较高。这是由遗传挖掘算法使用质量维度作为挖掘的导向而决定的，同时，GMTC算法的4个质量维度均较为稳定，相较于其他算法，波动幅度不大。这是由于使用了综合质量函数，为4个质量维度赋予了同样的权值，且GMTC算法的综合质量也达到了最高。在其他算法中，IM算法所得的模型具有较高的拟合度，但简洁度偏低。Heuristic算法简洁度较高，拟合度则不太理想；ILP算法能够获得较高的拟合度和简洁度，但精确度和泛化度则偏低。尽管每种算法均有其优势，但是对于不同的数据，算法挖掘出的模型的不同质量维度的数值波动较大，而GMTC算法使用质量维度作为模型的挖掘导向，无论对于何种数据，4个质量维度都较为稳定且可以达到较高的综合质量。

同时，分别记录6个公开数据集使用GPM算法和GMTC算法挖掘所用的时间。如表2所示，Loan application与Benchmarking logs-parallel两组数据集由于数据量较小，GMTC算法所体现的时间优势不够明显，而对于Traffic fine这种较大的数据集，GMTC算法相比于GPM算法能够节省大量时间。同时，挖掘所用时间并不仅仅取决于数据量大小，CCC19的数据量并不大，但仍旧耗时较长，这是由其结构复杂度较高导致的。

表2 6组公开数据集分别使用GPM与GMPC算法挖掘所用时间 s

以上实验结果表明，GMTC算法能够均衡多种算法的优势，使得其挖掘结果的综合质量均高于其他4种挖掘算法以及GPM算法的挖掘结果，且当面临较大的事件日志时，相较于GPM算法，GMTC算法能够节省大量时间。究其原因，一方面是提升遗传挖掘算法的初始种群的质量所致，另一方面是由于基于对齐突变，可使得种群的质量“好上加好”。

4 结束语

本文提出一种基于轨迹聚类种群的遗传过程混成挖掘算法，该算法将3种挖掘算法结合，能有效简化挖掘环境，提高遗传挖掘算法初始种群的质量。同时，使用对齐日志得到的信息指引突变操作代替原有的随机突变操作，用有向代替随机，能有效地提高模型质量，加快算法收敛速度。通过实验结果可以看出，相比其他单一的过程挖掘算法，GMTC算法在模型质量方面存在明显优势，而相比于GPM算法，对于较大数据量的事件日志，在效率上也有显著提升。GMTC算法为当前过程挖掘领域所面临的大型事件日志的挖掘问题提供了一种新思路和新的解决方法。但由于GMTC算法的特性，更适用于具有多样性的大型事件日志的处理，日志数据需要具有足够多样性的轨迹聚类子类，该混成算法才可能有效，而对于小型日志，算法的优势则不够明显。因此,下一步工作将从小型日志入手，提出相关的解决方法。