流程挖掘算法综述①

林文祥,刘德生

(航天工程大学 复杂电子系统仿真重点实验室,北京 101400)

流程挖掘是一门新兴的交叉学科,起源于软件工程领域.起初,软件设计者只能根据业务设计师和业务管理者的相关介绍对工作流程进行建模,容易导致流程模型具有主观性和片面性,无法客观反映客户对软件的真实需求;此外,由于业务实际运转过程中的不确定性,容易导致真实的业务流程与事先建好的流程模型存在差异,难以借助模型分析和优化真实的业务流程.流程挖掘技术应运而生,被认为是解决这一问题的可行方案,即使用系统的实际运行事件日志数据,通过流程发现、验证等方法,构建真实的业务流程模型,用于指导真实业务流程的分析和优化[1].

流程挖掘的概念自1998年首次被提出以来,相关技术发展迅速,其算法研究更是热点之一.在20 余年的时间里,流程挖掘的新算法和改进算法层出不穷.本文对流程挖掘算法进行统计学分析,探讨了算法研究的总体情况和发展趋势;基于算法特性将流程挖掘算法分为传统算法和基于计算智能和机器学习技术的算法,对其中主要算法进行简要介绍和对比分析,并提出下一步改进措施.

1 流程挖掘算法研究现状的统计分析

选取Web of Science (WoS)核心合集作为分析流程挖掘总体现状的数据来源,设置检索的时间跨度为1998-2020年,设置检索条件式为“Topic=‘process mining’”and “Topic=‘Algorithm’”,共检索出文献7 085 篇.

图1是将检索的7 085 篇有关流程挖掘算法的文献按照发文年份进行统计分析,由图可知,在流程挖掘发展之初,大约2010年之前,有关算法文章的研究和发表呈现平稳姿态,数目位于100-200 之间,表明这一时间是流程挖掘领域的奠基阶段,研究发现许多经典算法诞生于此时间段内;在2010年之后,每年算法的发文数量呈现指数型增长,在最近两年,年增长数目均在200 以上,表明了当前流程挖掘算法研究正处于爆发期.

图1 1998-2020年外文文献年度趋势

运用CiteSpace[2]对WoS 数据源的文献资料进行分析.上述7 085 篇文献经去重得到6 863 篇独立文献,分析得到突现关键词116 个,其中与算法相关的关键词58 个.算法突现词从一定层面上可以反映在某段时间内的研究热点,甚至可以表明某一算法提出的时间,比如evolutionary algorithm,其突现时间是2007-2010年,这也是遗传挖掘提出并引发相关热点的时候,再比如与模糊挖掘相关的关键词Fuzzy 突现时间为2008-2010年,这也与模糊挖掘算法提出时间接近.此外突现词数量众多反映出流程挖掘相关研究自1998年发展至今,算法提出和改进的相关研究非常多,尤其是2010年以来表现得更加活跃;突现强度前30的关键词如表1所示,其中排名靠前的关键词均与人工智能等前沿领域相关,相关算法在2019年左右开始突现,表明与deep learning、machine learning、artificial intelligence 等领域的结合已成为近两年来流程挖掘算法研究的热点.

表1 1998-2020年排名前30 算法突现词

目前算法的分类方式主要有以下4 种:(1) 根据流程挖掘结果输出的模型表示方式对算法进行分类;(2) 基于应用领域对算法进行分类;(3) 基于算法特性进行分类;(4) 按照时间顺序介绍算法.由于第3 种分类方式具有交叉性小、算法特点明显等优势,所以本文采取基于算法特性的分类方式,将流程挖掘领域算法分为两大类,分别是传统算法和基于计算智能和机器学习技术的算法,并对其中骨干算法进行简短介绍.

2 流程挖掘传统算法

流程挖掘传统算法的主要特点是具有严密的逻辑推理和因果关系,提出时间较早且发展较为成熟,主要包括直接算法、启发式算法和基于概率统计的算法.

2.1 直接算法

直接算法的基本思想是直接对事件日志进行全盘扫描,从中找出具有特定规律的模式.α算法和相关改进算法是此类方法的典型代表[3-7].

以α算法[3]为例.α算法首先基于日志定义了4 种活动间的次序关系(以同一日志W中的活动a和b为例),分别是伴随关系a＞Wb、因果关系a→Wb、并行关系a||Wb和无关关系a#Wb;接着根据4 种次序关系进一步构造5 种控制流结构,分别是顺序模式、选择分叉模式、选择合并模式、并行分叉模式和并行合并模式.

图2即为5 种控制流结构Petri 网的表现形式,其中,图2(a)是顺序结构,要求满足的次序关系是a→Wb;图2(b)是选择分叉结构,要求满足的次序关系是a→Wb,a→Wc并且b#Wc;图2(c)是选择合并结构,要求满足的次序关系是a→Wc,b→Wc,并且a#Wb;图2(d)是并行分叉结构,要求满足的次序关系是a→Wb,a→Wc,并且b||Wc;图2(e)是并行合并结构,要求满足的次序关系是a→Wc,b→Wc并且a||Wb.α算法分类得到事件日志中各活动间关系,在5 种控制流结构的基础上,输出完整的以工作流网为表示形式的流程模型.

图2 α 算法中的典型控制流结构

α算法的提出促进了流程挖掘的快速发展,目前仍是流程挖掘领域的主流算法之一.但是,因为该算法不能处理带有非自由选择结构、短循环结构、重复任务和不可见任务等复杂结构的流程模型,很多学者基于α算法做了深入研究并提出改进措施.其中,α+算法[4]可用于处理流程模型中具有长度为1 或2的短循环结构;α++算法[5]则能发现依赖关系大于1的隐式依赖关系;α#算法[6]针对的是隐式变迁问题;α*算法[7]则是可以处理重复活动.到目前未止还没有一种可以综合上述所有优点的成熟的算法,文献[8]在此方面做了有益的探索和尝试,使α算法初步具备同时处理多种复杂结构的能力.

2.2 启发式算法

α算法的应用需要一个重要前提,即日志完备且没有噪声.噪声指的是记录错误的日志数据或者流程执行出现异常所记录的数据,这在流程实际运行的时候必然会出现.为解决流程挖掘中的日志噪声问题,研究人员提出了启发式算法[9,10].

噪声日志是指出现频次明显低于其他行为的特定行为[11],这是基于流程运行的稳定性的一种假设,即噪声日志在正确日志中所占比例很小.启发式算法的基本思想是基于此基本假设,在挖掘事件日志时,考虑流程实例出现的频率,从概率统计的角度识别噪声,通过设定阈值,将低频实例作为噪声过滤掉.文献[9]首次提出了启发式挖掘算法,其基本思想是在挖掘事件日志时,使用频率来刻画一对活动之间因果关系的强度,并以依赖度度量,通过事件日志中不同活动之间的连接数计算得到依赖度,依赖度低于某个阈值的日志即视为噪声,将之过滤后输出相应的控制流结构形成流程模型.文献[10]对启发式挖掘步骤进行了详细介绍,可总结如下.

1) 挖掘依赖图.其中包括计算活动间依赖度,形成活动依赖表,再设定阈值构造活动间依赖图.图3(a)是一个构造的依赖图的例子[12],其中活动用字母代替,活动间关系用有向弧表示,并在相应有向弧标明活动间的依赖关系,此环节中低频噪声已通过阈值被过滤.

图3 C-net 构造过程

2) 在依赖图基础上确定并行和选择分支,通过定义并行选择结构判断的计算公式a⇒Wb∧c=和设定阈值,当计算值小于某一阈值时被当作选择结构处理,大于某一阈值时则被当作并行结构处理.图3(b)是构建成功的一个C-net 例子,在依赖图的基础上对选择或并行关系进行了标识[12].

启发式算法在应对噪声问题上走出了创新的一步,但基于频率阈值的对低频事件一刀切也会导致错误删除有效的低频行为,已有学者考虑这个问题后提出了一些解决方法.就目前而言,在针对噪声处理问题上启发式思想仍是主流,并未出现更多可供选择的噪声处理方法.

2.3 基于概率统计的算法

此类算法是概率统计相关算法在流程挖掘中的应用,具有明显的或潜在的概率模型,揭示了特定数据点之间的相关性概率,与流程挖掘需要得到活动连接概率、现象发生频率等契合度高,因此在流程挖掘领域发挥重要作用.常见于流程挖掘领域的概率统计算法有:马尔可夫(Markov)模型[13],随机活动图(SAG)算法[14],增量分析[15],Apriori 算法[16,17],随机Petri 网等.

马尔可夫模型[13]是一个具有无后效性的随机过程,表示系统从一个状态n转移到另一种状态n+1 只取决于系统在n时刻的状态,即未来状态的选择仅与系统当前状态相关,而与之前的状态无关,并将系统从一个状态转移到另一个状态的概率称之为状态转移概率.业务流程也可看作一个随机过程,它描述了系统从一个任务状态到另一个任务状态.由于流程的任务在时间t具有任务状态,因此业务流程被视为具有有限状态的马尔可夫链,文献[13]设计了一种基于马尔可夫转移矩阵的自动业务流程建模方法,可推导任务间所有可能的逻辑关系且不受日志质量影响.

随机活动图(SAG)[14]是有着明确定义的元组,包括节点、边、活动、活动分配函数、转移概率、开始节点和结束节点,由于随机活动图和工作流模型的基本元素都是活动,可用随机活动图的构建方式发现日志中活动关系.文献[14]通过对SAG 活动节点和工作流实例的节点进行映射,并要求SAG 活动尊重实例活动之间的时间依赖性,用随机活动图作为工作流模型的中间表现形式,再进行工作流模型转换.

与α算法和启发式算法专注于流程发现不同,概率统计算法可用在流程挖掘的优化方面,如利用Apriori算法进行关联规则挖掘[18],从而找出高效的工作组合;再比如利用Markov 模型的两个活动先后发生概率得到流程执行的路由概率,从而检测流程是否异常[19].概率统计方法识别流程模型中的缺陷和问题应用较为广泛.

3 基于计算智能和机器学习的流程挖掘算法

此类流程算法主要来自于数据挖掘相关技术在流程挖掘领域的应用,相比于传统流程挖掘算法,此类技术的整体成熟性还不够,大部分还未能达到很好的挖掘效果,但兴盛的计算智能和机器学习浪潮未必不能给流程挖掘领域带来不一样的前进方向.

3.1 基于智能优化的流程挖掘算法

智能优化算法在流程挖掘领域具有天然的优势,一是可以处理大多数的控制流结构,并且挖掘结果具有很高准确率;二是算法鲁棒性好,可以很好地处理噪声;三是基于局部次序关系的全局搜索,有利于得到全局优化的结果;四是适应度函数的自由设置,便于得到更符合用户倾向的流程模型.常见的在流程挖掘中使用的搜索算法有:遗传算法[20]、模拟退火算法[21]、禁忌搜索算法[22]、和粒子群[23]等.

智能优化算法的基本框架[22]如图4所示.

图4 智能优化算法基本框架

(1)智能优化算法的初始化.算法初始化要考虑两个方面因素:一是算法本身原理,如遗传算法需要生成初始种群,而模拟退火算法和禁忌搜索算法仅需生成一个初始个体;二是要考虑流程挖掘的特点,主要就是如何表示各流程个体以适应于智能优化技术,可采用因果矩阵或Petri 网等表现形式.

(2)计算流程模型的适应度.适应度是判断算法停止的主要依据,流程模型的适应度主要参考4 个评价指标:拟合度、泛化度、精确度和简单度,四者相互制约,从中寻求平衡是难点.

(3)智能优化算法停止的条件.算法停止条件可自行定义,常用的有:一是适应度函数若干轮计算后达到预设数值,二是算法的循环次数达到设定的上限,三是适应度函数的值经历若干次计算未发生变化或变化量小于设定阈值等.

(4)智能优化算法的寻优操作.该步骤是智能优化算法在流程挖掘领域应用的核心步骤,目的是通过寻优操作提升个体或群体的适应度.不同算法寻优方式不同,需要把流程挖掘任务中的概念根据算法进行抽象,对算法进行适应性修改.例如基于遗传算法的流程挖掘算法,在抽象个体表示为因果矩阵后,需要对针对基因的交叉、变异和选择等策略修改针对因果矩阵的操作,这些操作是否合理和有效将成为优化算法输出结果优劣的主要影响因素.

智能优化算法随着计算效率的提高而越来越受追捧,这也反映了智能优化算法的不足,即算法执行时间过长,执行效率不高,利用智能优化算法对业务流程进行离线分析尚还可以,但流程挖掘的发展趋势是支持在线运行,目前从效率来看仍有较大差距.

3.2 模糊挖掘

传统流程挖掘技术有很多显现或者隐含的假设,使其在结构化流程上表现良好,但应用于结构化程度低的流程,无法提供具有洞察力的模型.这不是说传统技术挖掘的模型不正确,而是挖掘的模型显示了所有细节,没有从事件日志本身提供任何有意义的抽象,因此对于流程分析师来说是无用的.模糊挖掘技术[24]就是针对此类现象,实现了流程模型的挖掘和自适应简化,其基本步骤如下:

(1)首先创建初始模型

将日志中的所有事件类型都被转换为活动节点,其重要性由一元重要性来表示.对于事件类之间的优先关系,采用相应的有向边进行连接.这条边由二元重要性和相关性来描述.

(2)将下列3 种转换方法应用于流程模型,依次简化流程模型的特定方面.

1) 二元关系中的冲突解决

若活动A发生后执行B,定义A对于B的相对重要性为rel(A,B),同理B对于A的相对重要性为rel(B,A),根据相对重要性处理3 种冲突情况.

一是两个冲突关系rel(A,B)和rel(B,A)的相对重要性均超过先前设定的保留阈值,则A→B和B→A都将被保留;二是至少一个冲突关系的相对重要性低于该阈值,计算确定两个关系的相对重要性之间的偏移量.如果偏移值超过先前设定的比率阈值,则移除不重要的边;三是至少一个关系的相对重要性低于保留阈值,并且它们的偏移小于比率阈值,则两个边都从过程模型中移除.

2) 边的过滤

如图5所示,首先定义可配置的效用比ur,即带有权重的考虑两活动之间的二元重要性和二元相关性,计算得到有效选取值 Util.后进行归一化得到Normal Util.,再与设定参数删除值Co相比较,删除小于阈值的边.

图5 过滤节点A 输入边的过程

3) 节点聚合和抽象

借鉴数据挖掘中的模糊聚类方法,模糊挖掘提出了结点聚集的方法,对于流程模型中重要性较低但是相关性却很高的多个结点采用聚集的方式,同时基于结点参数删除值的大小移除孤立且重要性低的结点[25].

模糊挖掘技术对于解决传统流程挖掘技术挖掘的“意大利面式”的流程模型具有显著的作用,在发现开发人员编码过程[26]和查找恶意软件[27]等方面发挥了作用.模糊挖掘算法针对不同的事件日志可通过配置合理参数得到有效的流程模型,从适用范围来讲较大.但优点也是缺点,针对不同的应用场景,如何找到正确的参数是一件耗时耗力的事.模糊挖掘的发展需要得到高适应性的默认参数设置或易操作的合理参数寻找方式,提高算法在实际应用中的可使用性.

3.3 决策挖掘

事件日志中包含着大量的事件属性信息,如时间戳、执行者和一些附加数据等,目前的流程挖掘算法更多的是利用前两个属性来构造反映因果相关性的流程模型,即基于控制流视角的流程发现,而对日志中其他数据利用较少,无法解释活动为何被选择执行.机器学习算法[28]已经成为从大量数据中提取知识的广泛采用的手段,文献[29]最早提出了决策挖掘的概念,通过决策树分析技术分析日志中的各种数据信息如何影响具体的流程实例进行决策,即得到决策规则,关注流程挖掘的案例视角.

决策挖掘也称之为决策点分析,旨在挖掘与业务流程路由相关的数据信息.现有的决策挖掘算法可分为3 个步骤.

(1)使用已有控制流挖掘算法挖掘出业务流程的控制流模型.

(2)识别过程模型中的决策点.

以Petri 网为例,若Petri 网中某一库所对应了多个输出弧,则可被判定为决策点.

(3)使用决策树分析过程模型中的决策点.

在对过程模型中的决策点进行识别之后,需要判定过程实例的数据属性是否对实例的决策产生影响,即决策规则挖掘,其思想就是将每一个决策点转换为一个分类问题,具体类别则是作出的不同决策[30].

如图6,决策树会构建出一个树状模型.模型存在一个根节点、多个决策结点和多个叶子结点.其中根结点对应了样本的全部数据集,而根结点到叶结点的路径则对应一个决策序列.叶结点则对应的是决策树最后的判断结果,决策结点设置数据属性,把每个结点包含的样本数据集合根据属性测试条件分别划分到其子节点中.

图6 决策树模型

决策树挖掘提出来之后,很多学者针对其进行了深入的研究和改进.文献[31]针对流程日志与流程模型不一致会影响挖掘结果的问题,提出了增加一致性检验步骤;文献[32]则是提出在决策点挖掘时同时考虑外部数据信息和内部各决策点的结构关系,提升了决策点决策规则挖掘的全面性和准确性.决策挖掘主要针对案例视角,运用机器学习相关技术填补了空白,但在实际应用中还面临许多难题,包括工作流日志数量好坏直接影响决策挖掘结果、非Petri 网模型的决策点挖掘等问题,还需要更进一步的研究探索.

4 算法比较

前述各类流程挖掘算法的优缺点如表2所示.

表2 流程挖掘算法特点

直接算法以α算法及其系列算法[3-7]代表,在流程挖掘发展初期诞生,发展成熟,根据活动间依赖关系发现流程模型,原理清晰,计算简单,但不能处理许多复杂结构和噪声,后期虽有学者针对性改进,但至今仍没有能够处理所有复杂结构的完善算法;启发式算法[9,10]解决了噪声处理问题,基于活动间发生频率来去除噪声,缺点是易误删低频有效行为,导致挖掘模型不能反映实际情况;基于概率统计的算法[13-17]在处理特定问题时效果显著,可用于流程优化或者改进算法,缺点是适用范围不大,依附性强;基于智能优化的流程挖掘算法[20-23]可以处理大多数的控制流结构和噪声,有利于得到全局的优化结果,通过设置适应度函数便于得到倾向性模型,不足在于算法效率太低,容易产生死锁等问题,可在质量和效率两方面进行改进;模糊挖掘[24]可用于处理现实生活中“意大利面式”的流程模型,但需要获得合适参数来进行过滤,可使用性较差;决策挖掘[29]关注案例视角,发现流程走向的原因,便于研究人员分析,但是易受事件日志影响.

流程挖掘算法各类算法都有其优越性,可解决特定领域的特定问题,但各算法也存在着明显短板,改进难度大.从整体上看,流程挖掘算法发展呈现烟囱式,目前并无一个算法可以解决绝大多数问题,探索之路任重而道远.

5 总结

流程挖掘是对客观世界中的业务流程、工作流程、信息流程进行发现、验证和优化的有效手段,目前已经成为系统工程和数据应用工程的研究热点.流程挖掘算法是流程挖掘的核心,直接影响流程挖掘效率和挖掘结果质量.现有的流程挖掘算法中,以直接算法、启发式算法和概率统计算法等为代表的传统算法具有执行效率高的优点,但对日志噪声、复杂结构、有效低频行为等问题的处理上难以兼顾,通常需要组合运用以达到理想效果;以智能优化、模糊挖掘和决策挖掘等算法为代表的新型算法在处理上述问题方面具有独到的优势,且更容易获得全局优化结果,但执行效率会随着挖掘算法的复杂程度而降低,在应用时需要在挖掘效率和挖掘质量上综合考虑.随着计算机算力的不断提升,挖掘算法复杂度对执行效率的制约将逐渐降低,基于计算智能和机器学习的挖掘算法将以其高质量的挖掘效果成为今后流程挖掘算法的主要发展趋势.