业务流程对齐的近似计算：基于松弛标记法

# 业务流程对齐的近似计算：基于松弛标记法 ## 1. 引言 一致性检查预计将在未来几年成为流程挖掘中增长最快的领域。其核心在于将事件数据与流程模型对齐，以提升组织内流程模型的价值。然而，现有的对齐计算技术要么复杂，要么仅适用于特定类型的模型，在处理大型输入时，往往无法得出结果。 在某些情况下，近似计算是可行的。例如，当需要用事件日志中的信息增强模型，或通过重放日志来动画化模型时。本文提出了一种基于流程模型偏序表示的近似对齐方法，利用松弛标记技术，在计算时间上实现了显著加速，同时能得到合理的近似结果。 ## 2. 相关工作 此前已有多种计算对齐的方法： - **A*算法**：用于计算特定类型流程模型的最优对齐。 - **自动化规划**：将对齐问题映射为自动化规划实例。 - **自动机技术**：基于自动机的对齐计算技术。 - **近似对齐**：如基于Petri网结构理论的递归范式等，在降低计算需求的同时，可能无法保证结果的可执行性或最优性。 本文方法是现有方法的替代方案，在计算时间和内存要求受限，且可接受次优解的场景下具有优势。 ## 3. 预备知识 ### 3.1 Petri网、展开和流程挖掘 一个由标记Petri网系统定义的流程模型可表示为元组 $N = \langle P, T, F, m_0, m_f, \Sigma, \lambda\rangle$，各参数含义如下： |参数|含义| | ---- | ---- | |$P$| 库所集合 | |$T$| 变迁集合（$P \cap T = \emptyset$） | |$F$| 流关系，$F \subseteq (P \times T) \cup (T \times P)$ | |$m_0$| 初始标识 | |$m_f$| 最终标识 | |$\Sigma$| 动作字母表 | |$\lambda$| 为每个变迁标记动作或标记为静默 | Petri网的语义通过 firing 序列定义。一个变迁 $t$ 在标识 $m$ 下被启用，当且仅当其所有前置库所被标记。变迁 firing 后，会从前置库所移除令牌，并在后置库所放置令牌。 一个有限且完整的 Petri 网展开前缀 $\pi$ 是一个有限无环网，隐式表示了 Petri 网的所有可达状态及在这些状态下启用的变迁。 行为轮廓用于指导对齐搜索，定义如下： - **严格顺序关系**：$x \leadsto y$，若存在 Petri 网的一个运行，其中 $x$ 出现在 $y$ 之前，且 $y$ 不会出现在 $x$ 之前。 - **排他顺序关系**：$x + y$，若 $x$ 不会出现在 $y$ 之前，且 $y$ 也不会出现在 $x$ 之前。 - **交错顺序关系**：$x \parallel y$，若存在 Petri 网的一个运行，其中 $x$ 出现在 $y$ 之前，且存在另一个运行，其中 $y$ 出现在 $x$ 之前。 日志是字母表 $\Sigma$ 上的有限单词集合，对齐是模型的一个完整运行 $\gamma$，与观察到的轨迹 $\sigma$ 具有最小编辑距离。 ### 3.2 松弛标记算法 松弛标记（RL）是一类基于局部信息进行函数优化的迭代算法，从约束满足的角度出发。给定一组变量 $V = \{v_1, \ldots, v_n\}$，算法的目标是为每个变量分配一个值（标签）。变量 - 标签分配由一组约束 $C$ 进行奖励或惩罚。 以下是 RL 算法的伪代码： ```plaintext /* Start in a uniformly distributed labelling P */ P := {{p11 . . . p1m1}, . . . , {pn1 . . . pnmn}}; /* Time step counter */ s := 0; repeat /* Compute the support Sij that each label receives from the current weights for the labels of the other variables and the constraints ```