Alpha算法是最早应用于过程挖掘的过程发现算法，在2002年被过程挖掘之父Wil van der Aalst提出，后续并被很多研究学者所完善，提出了一系列的扩展alpha算法，比如alpha+、Tsinghua-alpha、alpha++、alpha#、alpha$和alpha*。接下来，我们将详细地介绍这一系列算法。

在过去的十年（上世纪90年代）中, Staffware、IBM MQSeries、COSA等工作流管理系统为结构化业务流程提供通用建模和实施功能。通过创建图形化的流程定义，即单独描述典型案例（工作流实例）生命周期的模型，可以配置这些系统以支持业务流程。除了纯工作流管理系统外，许多其他软件系统都采用了工作流技术。例如，考虑SAP、CRM软件等ERP（企业资源计划）系统，尽管它的承诺，在应用工作流技术时会遇到许多问题。其中一个问题是，这些系统需要工作流设计，也就是说，必须构建一个详细的模型，准确地描述工作流程。为工作流建模绝非易事：它需要对工作流语言有深入的了解。

因此，需要算法来对工作流进行建模，来构造一种可理解的过程模型语言，alpha算法应运而生。

紧邻：x>y当且仅当存在一条轨迹使得活动x后面紧跟着y；

因果：x->y当且仅当x>y且非y>x;

并行：x||y当且仅当x>y且y>x;

无关：x#y当且仅当非x>y且非y>x.

比如在日志L={,,}中，其中的紧邻关系（也叫做直接跟随关系）为

A>B,B>C,C>D，A>C,C>B,B>D,E>F；

Alpha算法不能识别上述两种类别的Petri网，Alpha+算法进行了如下改进：

在预处理步骤中移除长度为1的短循环任务，在后处理步骤中将短循环任务添加到模型的正确位置

示例如下：

一个变迁的执行对应两个事件类型(strat和complete），换言之，事件的执行需要时间，是带有生命周期的，Alpha算法并不能区分这种事件到底是串行短循环还是并行短循环。

所以定义了以下关系：

基础Alpha算法无法处理不可见任务，对应Petri网也就是不可见变迁或者静默变迁。

具体分为SIDE类型、SKIP类型、REDO类型、高级SKIP类型、高级REDO类型以及SWITCH类型，如下图所示：

 对于上述结构，Alpha#算法定义了一种虚假的依赖关系，如下所示：

 如果活动关系满足

a和x是因果关系；y和b是因果关系；y后从来不紧邻x；x后也从来不紧邻b；x和b不并行发生，a和y也不并行发生

这六种基本情况，我们认为存在不可见任务，不可见任务类型的区分如上图所示。

上图中的N2是非自由选择结构，由于变迁A和D，变迁B和E之间存在远程的依赖关系，导致变迁D和变迁E的执行不再是自由的竞争关系，所以基础的Alpha算法不能够发现库所p1和p2. 

对此，Alpha++算法对此进行改进,引入了任务键非紧邻的可达关系，并推导依赖关系。

 从上图我们可以发现，变迁a后面永远跟着ai,不会跟着bj，变迁b后面永远跟着bj,不会跟着ai。那么如果ai的输入变迁集合是bj输入变迁集合的子集的话，则相信a和ai之间存在这种没有被发现的库所p.

 和Alpha+算法的思想差不多一致。

是对Alpha++算法和Aplha#算法的整合。

（1）使用prom6运行的插件svn下载地址：

prom - Revision 46153: /Packages/AlphaMiner/Trunk (tue.nl)

运行界面插件图：

(2）使用pm4py调用Alpha Miner算法的链接地址：

PM4Py - Process Mining for Python (fraunhofer.de)

Alpha算法假设日志是直接跟随关系完备的，用于挖掘不带短循环的SWF-net，SWF-net不含隐式库所，且不能包含如下两种子结构（即XOR-join和AND-join不能同时存在）： 

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

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

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

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

参考文献：

1.《过程挖掘：业务过程的发现、合规和改进》，Wil van der Aalst著，王建民、闻立杰等译；

2.Alpha：Van der Aalst W, Weijters T, Maruster L. Workflow mining: Discovering process models from event logs[J]. IEEE transactions on knowledge and data engineering, 2004, 16(9): 1128-1142.

3.Alpha+:De Medeiros A K A, Van Dongen B F, Van der Aalst W M P, et al. Process mining: Extending the α-algorithm to mine short loops[J]. 2004.

4.Alpha++:Wen L, Van Der Aalst W M P, Wang J, et al. Mining process models with non-free-choice constructs[J]. Data Mining and Knowledge Discovery, 2007, 15(2): 145-180.

5.Alpha$:Guo Q, Wen L, Wang J, et al. Mining invisible tasks in non-free-choice constructs[C]//International Conference on Business Process Management. Springer, Cham, 2016: 109-125.

下一讲将介绍遗传挖掘算法（ETM MIner）。

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