过程挖掘(Process Mining)3

您所在的位置:网站首页 招商会议流程策划方案树状图 过程挖掘(Process Mining)3

过程挖掘(Process Mining)3

2023-08-05 01:51| 来源: 网络整理| 查看: 265

流程树(Process Tree)

    流程模型具有与事件日志无关的不期望的属性都是不合理的(unsound),诸如Petri网、WF网、BPMN模型、EPCs、YAWL模型以及UML活动图等都有可能出现死锁(deadlocks)、活锁(livelocks)和其他缺陷等不合理的属性,而流程挖掘方法挖掘的这些基于图的流程模型有可能就是不合理的。而因果网C-nets通过更松的语义(more relaxed semantics)来解决会有不合理出现的问题。另一种解决方法就是使用块结构模型(block-structured models),这种模型从结构上就是合理的。流程树就是这样的一种块结构模型,它是一种分层流程模型(hierarchical process model),其内结点(inner nodes非叶子结点)是操作符(operators如序列符、选择符),叶子结点(leaves)是活动(activities)。     同因果网一样,流程树也是为流程发现量身定做的流程建模语言,现已经产生了一系列归纳流程发现(inductive process discovery)技术可以挖掘流程树。 下图给出了一个流程树例子,以及流程树包含的操作符和特殊活动,该流程可以文本表示为→(a,↺(→(∧(×(b,c),d),e),f ),×(g,h)) 在这里插入图片描述

图1 一个流程树例子

    图中显示了四种类型的操作符:→(序列组合,sequential composition),×(排他选择,exclusive choice),∧(并行组合,parallel composition)以及↺(重复循环,redo loop)。     顺序操作符其孩子按顺序(从左到右)执行,如上图流程根是顺序操作符,叶子结点活动a是它的最左的结点,因此第一个发生,随后依次发生重复循环redo孩子结点和排他选择孩子结点。     重复循环操作符首先执行其最左边的孩子,并且可以执行其它孩子结点到循环回到最左边的孩子(意味着最左边孩子必须首尾都出现),上图流程中的重复循环结构↺(→(∧(×(b,c),d),e),f ),其最左边孩子是→(∧(×(b,c),d),它将第一个发生,并在执行其他孩子结点后回到这个结点。     排他选择和并行组合很容易理解。需要注意的是,有些结构表示虽然不同,但是产生的行为却是一致的,比如→(a,a,a)和∧(a,a,a)它们都产生行迹。 沉默活动τ是不可观察的,由于重复循环操作符的语义的特殊要求,τ通常用在该操作符的最左边孩子,从而使该结构可能出现的行迹具有很大的自由性。     有了上面的解释,下面给出流程树的定义:

定义1(流程树,Process tree) 令A⊆𝓐是一个有限的活动集,且τ ∉ A,⊕={→,×,∧,↺}是流程树操作符。 • 如果a∈A∪{τ},那么Q=a是一棵流程树, • 如果Q1,Q2,…,Qn(n≥1)是流程树,且操作符⊕∈{→,×,∧},那么Q=⊕(Q1,Q2,…,Qn)是一棵流程树, • 如果Q1,Q2,…,Qn(n≥2)是流程树,那么Q=↺(Q1,Q2,…,Qn)是一棵流程树。

    流程树的形式化定义很容易理解,这是常规树形数据结构的定义,对于四种操作符,redo比较特殊,再强调一下。redo至少需要两个孩子结点,是第一个孩子结点(最左边孩子结点)是“do” part,其他孩子结点称为“redo” part,对于redo得到的行迹,总是这样的结果,所有redo的第一个孩子经常是沉默活动。     流程树可以转换为工作流网,下图给出了流程树结构的转换规则,沉默活动τ的引入是为了保持WF-net的结构。同样下面的映射规则也可以很容易的迁移到其他建模语言上如BPMN、YAWL、EPCs等。 在这里插入图片描述

流程树到工作流网映射图

    将流程树转换为工作流网使我们可以使用现有的一致性检验和性能分析技术。但是流程树的语义也可以直接推导(而不需要引入WF-nets),为了定义流程树的语义,我们引入两个针对序列的操作:拼接(·)(concatenation)和打乱(◇)(shuffle)。 拼接操作将两个序列拼接起来,比如序列σ1,σ2 ∈ A∗ ,σ1·σ2=σ1σ2。拼接操作也可以应用到两个序列集合S1和S2,S1·S2表示两个集合的笛卡尔连接,并且S1的序列先于S2的序列。记⊙1≤i≤n Si = S1 · S2 ··· Sn表示n个序列集合的有序拼接序列集合。     打乱操作将两个序列中的事件随机互相插入行成一个新序列,并且事件顺序保持原来序列的顺序,如◇={,,,,,}。同样打乱操作可以应用到两个序列集合中,S1◇S2 = {σ ∈ σ1 ◇ σ2 | σ1 ∈ S1 ∧ σ2 ∈ S2}。记◇1≤i≤n Si = S1◇S2 ◇···◇Sn表示n个序列集合的打乱交叠序列集合。     现在可以定义流程树的语义了:

定义2(流程树的语义) 令Q∈𝒬A是定义在A上的流程树,𝓛(Q)是Q的语言(language),即可以由它生成的行迹的集合,𝓛(Q)递归定义为: •𝓛(Q)={},如果Q=a∈A, •𝓛(Q)={} ,Q=τ(沉默活动) , •𝓛(Q)=⊙1≤i≤n 𝓛(Qi),如果 Q = →(Q1,Q2,…,Qn), •𝓛(Q)=∪1≤i≤n 𝓛(Qi),如果 Q = ×(Q1,Q2,…,Qn), •𝓛(Q)=◇1≤i≤n 𝓛(Qi),如果 Q = ∧(Q1,Q2,…,Qn), •𝓛(Q)={σ1·σ’1·σ2·σ’2 ··· σm ∈ A∗| m≥1∧∀1≤j≤mσj∈𝓛(Q1)∧∀1≤j



【本文地址】


今日新闻


推荐新闻


CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3