在我们相继推出了其中6种代表性的流程挖掘算法之后，我们将其简单地进行总结，并从整体上对流程挖掘算法进行概述，从而去了解流程发现的历史进程。接下来，我们将详细地介绍流程发现算法。

1.背景介绍

在《流程挖掘：业务流程的发现、合规和改进》一书中，曾介绍流程挖掘的目标是从事件数据中提取过程相关的信息，比如，通过观察企业系统中的事件数据，自动地发现流程模型。

流程挖掘指的是从事件日志中提取有价值的流程相关信息，是对现有业务流程管理(BPM）方法的补充。BPM是一个学科，它结合了信息技术和管理科学的知识，并将其应用于运行业务过程。

流程挖掘主要包括流程发现、合规性检查、流程改进及其增强三方面。

流程发现是指使用不包括任何先验信息的事件日志生成模型，模型能够更直观地表达或者解释事件日志记录的行为；

合规性检查简单来说就是将发现的模型与它产生的事件日志相比较，被用来检查记录在日志中的实际情况是否与模型相吻合。合规性检查可以用来侦查、定位与解释偏差，并测量这些偏差的严重程度。

流程改进与增强的理念是利用实际流程产生的事件日志来扩展或改进一个已存在的流程，其中的一个类型是修复，即修改模型使其更好地反映现实业务。另一个类型是扩展，即通过流程模型和日志其他属性关联给模型增加一个新的视角(比如资源、时间等视角)。

除此之外，流程挖掘还包括预测性监控，流程自动化等方面。

我们可以看出，流程发现是流程挖掘技术的第一步，为此，有许多不同的流程发现算法被提出。下面我们将对这些算法进行简单概括，比较不同流程发现算法的差异。

2.流程发现算法发展历程

我们查阅了相关文献，对流程挖掘算法有了大致地了解，流程发现算法的大致历史发展进程如下。

Alpha系列算法。Alpha算法是流程发现的第一个算法，此算法是由van der Aalst等人（2002年）提出，该算法定义了四种活动间的关系来发现流程模型。基础Alpha Miner假定日志是完整的，即所有可能的直接跟随关系都存在，它不能处理噪声、不完整的事件日志，并且无法识别短循环、映射非局部依赖关系和处理非自由选择结构。许多研究人员致力于改进和扩展Alpha Miner，提出了不同的算法来解决这些限制，具体如下：

 （1）短循环（alpha+，Tsinghua-alpha）;

   (2)不可见任务（alpha#、alpha$）;

 （3）非自由选择(alpha++、alpha$);

   (4) 重名任务(alpha*).

详细介绍请参考以往博客：Alpha Miner及其系列算法

Heuristic Miner算法。该方法是由Weijters& van der Aalst在2003提出的。该方案扩展了Alpha算法，并考虑了直接跟随活动关系的频率，计算相关性/频率表以获得一个启发式网络，该算法被称为启发式挖掘。它能够处理噪声，并允许在手动设计的模型和执行过程之间进行比较。该算法是最常用和定制的，因为它保证了良好的拟合度，但不能提供完全的合理性，因为不常出现的路径没有纳入模型中。该算法并在不完整和嘈杂的日志上始终表现得更好。虽然已经证明，启发式Miner在存在噪声的情况下能够实现相对良好的拟合度和精确度，但当应用于大型真实事件日志时，它仍然会输出类似意大利面条和不可靠的过程模型。

详细介绍请参考以往博客：Heuristic Miner（启发式挖掘算法）

Social Miner。van der Aalst、Reijers和Song（2005）分析了企业信息系统事件日志中的社会计量学和社会网络分析（SNA），从而分析了社会网络，确定了互动模式，并评估了个人在组织中的角色。该方法侧重于用个体之间不同的关系模式来低估流程偏离正常流程的情况。

参考文献：van der Aalst, W. M. P., Reijers, H. A., & Song, M. (2005). Discovering social networks  from event logs. Computer Supported Cooperative Work (CSCW), 14 (6), 549–593. doi: 10.1007/s10606- 005- 9005- 9 . 

Genetic Miner。van der Aalst和de Medeiros等人（2005年）提出了遗传过程挖掘方法，该方法基于因果关系作为个体的代表，并试图模拟种群进化。它考虑了Petri网和矩阵表示之间的关系，计算了从给定事件日志中发现模型的遗传算法。它利用精英主义来选择当前世代中为下一代保留的最适合的样本，并使用交叉和变异的概念来构建种群元素。

详细介绍请参考以往博客：遗传挖掘算法

Integer Liner Programming(ILP) miner。Jansen Vullers等人（2006年）基于整数规划技术创建了一种新算法。它们表明，可以使用目标函数搜索最佳设置，并应用整数规划技术。该方法寻找方程组的所有解，并通过整数编程技术实现最小化函数。要实现这一点，需要提前一步将事件驱动的流程链（EPC）转换为事件驱动的流程链（C-EPC）。

Wil、van der Aalst、Rubin和Günther（2006）提出了一种两步miner方法，包括在第一步中构造转换系统，在第二步中，使用区域理论将生成的转换系统转换为Petri网。第二步由名为Petrify的ProM插件实现，以获得Petri网。Petrify在许多计算Petri网的工作中都有应用，它可以扩展到评估特定约束。

参考文献：

Jansen-Vullers, M., van der Aalst, W., & Rosemann, M. (2006). Mining configurable  enterprise information systems. Data & Knowledge Engineering, 56 (3), 195–244. doi: 10.1016/j.datak.20 05.03.0 07 . 

Wil, M. P. , van der Aalst, B. V. D. E. K. , Rubin, V. A. , & Günther, C. (2006). Process 
mining: A two-step approach using transition systems and regions.

A declarative miner (DecMiner)。Lamma等人（2007）提出了一种结合归纳逻辑编程（ILP）和归纳约束逻辑（ICL）算法的声明式miner（DecMiner）。ICL具有一种学习功能，在这种功能中，积极和消极的解释逐渐转化为规则，例如活动的先决条件。ICL的每次迭代都会发现新的子句，并转换添加到理论中的规则及其各自的解释。

参考文献：Lamma, E. , Mello, P. , Montali, M. , Riguzzi, F. , & Storari, S. (2007). Inducing declarative logic-based models from labeled traces. In G. Alonso, P. Dadam, & M. Rose- 
mann (Eds.), Business process management (pp. 344–359). Berlin, Heidelberg: 
Springer Berlin Heidelberg . 

Fuzzy Miner，它提供了一种根据一元和二元重要性进行简化的方法。这种方法对于非结构化过程以及可视化活动和连接度量的相关性非常有用（Günther& van der Aalst，2007）。这种方法结合了制图中的复杂拓扑概念，如分类、抽象、强调和定制。然而，模糊挖掘并不能保证流程模型是合理的。

参考文献：C.W. Gunther, W.M.P. van der Aalst, Fuzzy mining—adaptive process simplification based on multi-perspective metrics, in: G. Alonso, P. Dadam, M. Rosemann (Eds.), Proceedings of the 5th International Conference on Business Process Management, BPM 2007, Lecture Notes in Computer Science, vol.4714, Brisbane, Australia, Springer, September24–28,2007,pp. 328–343.

Region-based Miner。同年，提出了基于区域的流程发现。在区域理论中，将一组状态转换为一个转换系统，以寻求所有状态在确定的区域上达成一致。在基于状态的区域中，可以识别出节点集，也称为区域，它们指的是一个简化的部分，可用于构造包含最小网行为的Petri网。Bergenthum、Desel、Lorenz和Mauser（2007a）提出的一种基于语言的区域的挖掘算法，旨在就语言与合成的一致性达成一致，以解决这一过程挖掘挑战。

参考文献：

Bergenthum, R., Desel, J., Lorenz, R., & Mauser, S. (2007a). Process mining based 
on regions of languages. In Lecture notes in computer science (pp. 375–383). 
Springer Berlin Heidelberg. doi: 10.1007/978- 3- 540- 75183- 0 _ 27 . 

Inductive Miner。Leemans等人（2013）提出了一个可扩展的框架，被称为Inductive Miner(归纳式挖掘算法)。其目的是发现块结构的流程模型，这些模型是可靠的，适合事件日志上的观察行为。该算法以发现流程模型的最小信息为特征。归纳式挖掘算法提供了多项式时间复杂度，提供了可行的计算成本。归纳式挖掘算法似乎具有高保真度，也被认为适用于处理复杂模型抽象中事件记录的可变性。它还包含了几个标准，如：频率分析、聚类、偏差和欺诈检测、时间和瓶颈分析、总体愿景、过程理解和结果价值评估，所有这些都包含在同一个解决方案中（Leemans et al.，2013）。

详细介绍请参考以往博客：Inductive Miner

Multi-paradigm Miner。由De Smedt等人（2014）提出，多范式挖掘算法通过程序性和声明性约束进行复合。这种组合试图从这两种方法中提取最佳发现，然后提供对流程模型的见解。这是混合之前的两种算法执行的，它们是启发式挖掘和声明挖掘。

参考文献：De Smedt, J. , De Weerdt, J. , & Vanthienen, J. (2014). Multi-paradigm process mining: Retrieving better models by combining rules and sequences. In R. Meersman, 
H. Panetto, T. Dillon, M. Missikoff, L. Liu, O. Pastor, & T. Sellis (Eds.), On the 
move to meaningful internet systems: Otm 2014 conferences (pp. 446–453). Berlin, 
Heidelberg: Springer Berlin Heidelberg . 

Evolutionary Tree Miner。 Evolutionary Tree Miner（ETM）是一种改进的遗传算法，在2014年由Buijs J C A M提出，它首先生成一组随机流程树。在每次迭代中，它为种群中的每棵树计算一个整体适应度值(overall fitness)，并将突变应用于其中的一个子集。该算法迭代直到满足停止条件，并返回总体适应度最高的树。Molka等人提出了另一种生成结构化模型的遗传发现算法。后一种算法在原理上与ETM相似，主要区别在于用于产生突变的一组更改操作。

 详细介绍请参考以往博客：遗传挖掘算法

Structured Miner。在2016年，AugustoA等人提出了Structured Miner通过放宽始终生成结构化过程模型的要求来解决这一限制，以实现更高的精度。Structured Miner没有直接发现结构化模型，而是首先应用启发式挖掘算法来获得准确但可能是非结构化甚至是不可靠的模型。然后，它应用最大限度地构造已发现模型的技术，并应用启发式来简化模型并消除不合理之处。然而，结构化挖掘算法的区块结构化方法在应用于现实生活中的事件日志时，往往无法生成合理的流程模型。

参考文献：AugustoA,ConfortiR,DumasM,LaRosaM,BrunoG(2016)Automateddiscoveryofstructuredprocess
models: Discover structured vs. discover and structure. In Proceedings of ER, LNCS 9974. Springer.

Fodina Miner。提出Fodina算法的vanden Broucke和Weerdt（2017）扩展了启发式算法，以包含特定的功能。该方法对噪声具有鲁棒性，并且能够识别重复活动。另一个相关贡献是灵活性，允许插入用户选择以优化发现过程。该方法是Heuristics Miner的一个变体，它避免了Heuristics Miner产生的某些类型的死锁。然而，当应用于现实生活中的事件日志时，Fodina Miner生成了大型且往往不可靠的模型。

参考文献：vanden Broucke, S. K., & Weerdt, J. D. (2017). Fodina: A robust and flexible heuristic process discovery technique. Decision Support Systems, 100 , 109–1 18. doi: 10. 
1016/j.dss.2017.04.005 . 

Split Miner。Split Miner是在2018年由Adriano Augusto提出来的。Split Miner结合了一种新的方法来过滤由事件日志产生的直接跟随关系图(DFG），以及一种识别分割网关组合的方法，该组合能够准确地捕获DFG中相邻节点之间的并发性、冲突和因果关系。Split Miner也是一种自动流程发现方法，可以保证生成无死锁的并发进程模型，同时不限于生成块结构的流程模型。

详细介绍请参考以往博客：Split Miner

3.总结

近20多年时间，流程发现算法不断被提出并完善，形成了一整套强大的算法库，能帮我们更好地处理事件日志，确保发现的流程模型是简单、易于理解、可靠的。

关于流程发现算法的内容我们暂且介绍到此，后续或许会进行继续完善。

接下来，我们将对流程挖掘的其他方面进行介绍。

如需进行相关的了解或者交流，欢迎私信或者加入QQ群：

最后

以上就是忧虑铅笔为你收集整理的【流程发现算法概述】1.背景介绍2.流程发现算法发展历程3.总结的全部内容，希望文章能够帮你解决【流程发现算法概述】1.背景介绍2.流程发现算法发展历程3.总结所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。