超越任务与网关：探索BPMN模型

### 超越任务与网关：探索 BPMN 模型 #### 1. 子流程识别复杂度分析 子流程识别过程分为多个步骤，每个步骤都有其对应的复杂度。 - 第一步：涉及属性处理，复杂度为 $O(|EL|\cdot2^a)$，其中 $a$ 是属性数量，$|EL|$ 是日志中的事件数量。 - 第二步：复杂度主要由 SPIDER 决定，为 $O(a \cdot m\log m)$，若将 $m$ 上界设为 $|EL|$，则变为 $O(a \cdot |EL|\log|EL|)$。同时，确定每个主键 - 外键依赖的方向，复杂度为 $O(|EL|\cdot k)$，若定义 $N$ 为事件类型簇的数量且 $k < N^2$，则复杂度变为 $O(|EL|\cdot N^2)$。 - 第三步：对每个事件类型簇遍历一次日志，复杂度为 $O(|EL| \cdot N)$，该复杂度被上一步的复杂度所主导。 - 最后一步：流程发现，其复杂度取决于所选的流程发现方法，暂不纳入本次分析。 综上，子流程识别的复杂度为 $O(|EL|\cdot2^a + a \cdot|EL|\log|EL|+ |EL|\cdot N^2)$（不包括流程发现步骤）。 #### 2. 识别边界事件、事件子流程和标记 此部分介绍了重构 BPMN 模型的启发式方法，主要包括以下几个方面： - **识别中断边界事件**：通过算法 2 检查子流程 $s$ 是否由中断事件触发。输入对应子流程 $s$ 调用的活动 $a_s$，检查从 $a_s$ 到 $p$ 的结束事件是否存在不经过任何活动或 AND 网关的路径，统计日志中包含 $a_s$ 的跟踪数量以及 $a_s$ 为最后一个事件的跟踪数量。若后者至少等于前者，则将子流程标记为“由中断事件触发”，该启发式方法使用阈值 $t_{vint}$。 ```python # 算法 2：isInterruptingEvent def isInterruptingEvent(as, p, Lp, tvint): if there exists a path in p from as to an end event of p without activities and AND gateways: # 初始化边界事件数量和跟踪数量 BoundaryEvents = 0 Traces = 0 for trace tr in Lp: if there exists an event e1 in tr such that e1.et = label(as): if there not exists an event e2 in tr such that e2.et != label(as) and e2.τ >= e1.τ: BoundaryEvents = BoundaryEvents + 1 Traces = Traces + 1 if BoundaryEvents >= Traces * (1 - tvint): return True return False ``` - **识别中断边界定时器事件**：算法 3 检测子流程 $s$ 是否由定时器边界事件触发。首先从 $p$ 的日志中提取包含 $a_s$ 执行的所有跟踪，计算每个跟踪中 $a_s$ 出现与第一个事件的平均时间差，统计该时间差等于平均时间差（允许一定误差）的跟踪数量。若满足条件的跟踪数量大于或等于包含 $a_s$ 执行的跟踪数量，则将子流程标记为“由中断边界定时器事件触发”，可使用百分比阈值 $p_{vtimer}$ 来处理噪声。 ```python # 算法 3：isTimerInterruptingEvent def isTimerInterruptingEvent(as, Lp, tvtimer, pvtimer): TimerEvents = 0 timeDifftot = 0 timeDifferences = [] for trace tr in Lp: if there exists an event e1 in tr such that e1.et = label(as): e2 = first event of tr timeDifftot = timeDifftot + (e1.τ - e2.τ) timeDifferences.append(e1.τ - e2.τ) timeDiffavg = timeDifftot / len(timeDifferences) for diff in timeDifferences: if timeDiffavg - timeDiffavg * tvtimer <= diff <= timeDiffavg + timeDiffavg * tvtimer: TimerEvents = TimerEvents + 1 return TimerEvents >= len(timeDifferences) * pvtimer ``` - **识别事件子流程