Cousera过程挖掘7-Module2-Alpha Algor

前情回顾：

分类

1、α算法的输入

我们不需要看一个activity的时间戳之类的信息，我们只需要关注具体活动内容和先后顺序，我们将其转换为一条一条的轨迹信息（trace），

Trace

下面的例子更加有代表性：

Log L1包含了6条Traces

上图中的a、b、c、d代表的是一个一个的activity

2、α算法的目的

目的

即把Log L1输入α算法，我们能够自动得到一个WF-net，这个WF-net就是我们想要的过程模型。

3、α算法的基础

在了解具体的α算法之前，我们需要先明确一些术语关系

• Dieect Succession “>”：

  Log L1有如上case
  那么我们说：
  image.png
  只要字母X直接出现在字母Y的前面，那么X>Y就成立

• Causality “—>”： 如果x>y且没有出现过y>x的情况则成立
  

  —>

• Parallel “||”：如果x>y且y>x则成立

• Choice “#”：如果没有出现过x>y且没有出现过y>x则成立

下面介绍由上述这些基本元素构成的一些α算法中的结构：

• 注意，下面的pattern的描述就是能够推出上述结构的必要条件
• XOR-split即Exclusive Choice 排他选择，意思就是工作流中的一个点，基于决定或者工作流中的数据，流向若干个分支中的一个。 只能选择其中一个分支，另外一个分支将不会走下去。
  XOR-split pattern

• AND-split 即 平行拆分（Parallel Split）表示工作流中从一个线程中的一个点拆分为在多个线程中平行执行的多个活动。a的完成激活了b、c的同时执行。例子：活动"付款"激活了"发送货物"以及"通知顾客"的执行。
  AND-split pattern

• XOR-join 即 简单合并（Simple Merge），表示 d或c完成后，d即被激活，不要求d、c都完成。
  

  XOR-join pattern

• AND-join即 同步（Synchronization），表示工作流中的多个活动在一个点上汇合成一个线程。例如活动"归档"在"发票"和"收款"全部完成后被激活。要求b、c都被完成，d才会被激活。
  

  AND-join pattern

上面AND-join和XOR-join进行对比，发现

4、α算法详解步骤1-找Activity

规则1

• T：代表所有的活动activity的集合
• t：代表一个活动
• σ：代表一条轨迹（上面是活动按顺序排列）
• L：代表所有轨迹的集合

同时，每一个在L中的activity相当于一个在α（L）中的transition

规则2、3

这两条规则主要是说一个trace的第一个actiivty和最后一个activity是我们需要关注的地方，并分别用TI和TO来代表这个的集合

介绍一个很有用的工具——Footprint Matrix

Footprint Matrix

上图中a行b列是“->”的标志，表明L3 Trace中存在a->b的关系

给出上图的这个Footprint Matrix之后，我们才开始去利用如下的α算法具体的执行步骤去创建模型（这个模型似乎使用Petri Net来表示的）。

4、α算法详解步骤2-找Place

第二步 规则4

注意这里规则4中：set A和set B之间的关系，我们这里要求：

• set A和set B中放入的元素各自不能相互follow
• 从set A和set B中各自任取一个activity，要求它们之间必须是之间前后相继的关系

规则5 规则6 规则7、8

5、经典α算法的局限性

使用α算法要求事件日志必须具有完备性，比如我们已知日志集为
{AEBCDF、ABECDF、ABCDEF}，其对应的真实模型是

真实模型

但是因为这个日志集为{AEBCDF、ABECDF、ABCDEF}，显然不具备完备性

何为完备性？即对于包含并行结构的复杂过程来说，它要求每对具有并行关系的活动都必须在日志中交叉出现（如B和C具有并行关系，那么BC和CB都必须出现在Trace中）

所以，我们对这个日志集用α算法进行建模，我们会得出如下的模型结果

不正确的建模结果