过程一致性估计：采样与近似方法

### 过程一致性估计：采样与近似方法 在过程挖掘领域，准确且高效地评估事件日志与过程模型之间的一致性至关重要。本文将介绍一种基于轨迹采样和结果近似的增量方法，以提高一致性检查的效率。 #### 1. 预备知识 - **事件和事件日志**：我们采用基于活动集合 $A$ 的事件模型。信息系统记录的事件与这些活动之一的执行相关。所有事件的集合记为 $E$。一个过程的单次执行，即轨迹，被建模为事件序列 $\xi \in E^*$，且每个事件最多出现在一个轨迹中。事件日志是轨迹的集合，$L \subseteq 2^{E^*}$。例如，用小写字母 $\{r, p, f, u, s\}$ 表示事件，对应过程模型中的大写字母 $\{R, P, F, U, S\}$ 表示的活动。具有相同活动执行序列的不同轨迹属于同一轨迹变体。 - **过程模型**：过程模型定义了过程中活动之间的执行依赖关系。为了简化，我们抽象出具体的过程建模语言，关注模型定义的行为。即过程模型定义了一组执行序列 $M \subseteq A^*$，这些序列表示导致过程达到最终状态的活动执行序列。例如，某个模型定义了执行序列 $\langle R, P, F, U, S\rangle$ 和 $\langle R, F, P, U, S\rangle$，可能还包括 $U$ 的额外重复。 - **对齐**：最先进的一致性检查技术通过构建轨迹与模型执行序列之间的对齐来检测偏差。轨迹 $\xi$ 与模型 $M$ 之间的对齐 $\sigma(\xi, M)$ 是一系列步骤，每个步骤包含一个事件 - 活动对，或者如果事件或活动没有对应项，则为跳过符号 $\perp$。例如，对于非一致轨迹 $\xi_1$，其对齐如下： ```plaintext Trace ξ1: r p f f u s Execution sequence: R P F ⊥ U S ``` 通过为跳过步骤分配成本，可以构建轨迹相对于模型所有执行序列的成本最优对齐。最优对齐使得能够量化不一致性。具体而言，日志相对于给定模型的适应度计算如下： \[ \text{fitness}(L, M) = 1 - \frac{\sum_{\xi \in L} c(\xi, M)}{\sum_{\xi \in L} c(\xi, \varnothing) + |L| \times \min_{x \in M} c(\langle\rangle, \{x\})} \] 其中，$c(\xi, M)$ 是最优对齐 $\sigma(\xi, M)$ 的聚合成本。分母捕获了每个轨迹的最大可能成本。使用标准成本函数（所有跳过步骤成本相等），示例日志 $\{\xi_1, \xi_2, \xi_3, \xi_4\}$ 的适应度值为 0.9。此外，对齐还可以检测不一致性的热点。通过定义偏差分布，可以捕获活动作为一致性违规一部分的相对频率。对于日志 $L$ 和模型 $M$，该分布基于最优对齐中的跳过步骤得出，形式化为活动包 $dev(L, M) : A \to \mathbb{N}_0$。活动 $a \in A$ 的相对偏差频率为 $f_{dev(L,M)}(a) = \frac{dev(L, M)(a)}{|dev(L, M)|}$。 #### 2. 基于采样的一致性检查 - **统计采样框架**：为了实现基于采样的一致性检查，我们将其视为一系列二项式实验。在解析日志时，某些轨迹可能提供与先前轨迹相似或等效的一致性信息。为了评估这一点，我们定义了一致性函数 $\psi : 2^{E^*} \times M \to X$，其中 $\psi(L, M)$ 是日志 $L$ 与模型 $M$ 之间的一致性结果。基于此，我们定义随机布尔谓词 $\gamma(L', \xi, M)$ 来捕获轨迹 $\xi$ 是否为与模型 $M$ 的一致性提供新信息： \[ \gamma(L', \xi, M) \Leftrightarrow d(\psi(L', M), \psi(\{\xi\} \cup L', M)) > \epsilon \] 其中，$d : X \times X \to \mathbb{R}_0^+$ 是量化一致性结果之间距离的函数，$\epsilon \in \mathbb{R}_0^+$ 是松弛参数。如果纳入轨迹 $\xi$ 使一致性结果的变化超过 $\epsilon$，则它为 $L'$ 增加了新信息。我们利用信息新颖性的概念进行假设检验，确定何时采样的轨迹足以理解日志与模型的整体一致性。基于二项式分布的正态近似，计算最小样本大小 $N$： \[ N \geq \frac{1}{2\delta} \left(-2\delta^2 + z^2 + \sqrt{z}\right) \] 其中，$z$ 对应于 $1 - \alpha$（单侧假设检验）的标准化正态随机变量的实现。例如，当 $\alpha = 0.01$ 和 $\delta = 0.05$ 时，$N \geq 128$。经过 128 个无新信息的轨迹后，我们可以以 0.99 的置信度停止采样，因为剩余日志中找到新信息的概率小于 0.05。基于上述公式，基于采样的一致性检查框架的算法如下： ```plaintext Algorithm 1. Framework for Sample-Based Conformance Checking input : L, an event log; M, a process model; N, a number of failed trials to observe; γ, a predicate that holds true, if a trace provides new information; ψ, a conformance function. output: ψ(L′), the conformance results for sampled traces. 1 L′, ˆL ← ∅; /* The sampled logs, overall and for current experiment series */ 2 i ← 0 ; ```