(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202211144571.3 (22)申请日 2022.09.20 (71)申请人 山东理工大 学 地址 255020 山东省淄博市张店区新村西 路266号 (72)发明人 刘聪　沈晓林　李会玲　郑凯　 李彩虹　王雷　王志强　 (74)专利代理 机构 广州市华学知识产权代理有 限公司 4 4245 专利代理师 冯炳辉 (51)Int.Cl. G06F 30/20(2020.01) G06K 9/62(2022.01) (54)发明名称 基于流程树分解和轨迹匹配策略的合规性 检测方法与系统 (57)摘要 本发明公开了一种基于流程树分解和轨迹 匹配策略的合规性检测方法与系统， 包括： 1)获 取事件日志和流程模型， 用流程树作为流程模型 的建模表示； 2)将流程树分解为子流程树； 3)在 分布式平台Spark上为事件日志中的轨迹从子流 程树中匹配最优子模型； 4)进行轨迹和最优子模 型的合规性检测； 5)重复步骤3) ‑4)， 直到完成所 有轨迹和其最优子模型的合规性检查， 收集合规 性检查结果， 合并生成整个事件日志的合规性检 查结果。 本发明通过流程模型转化、 分解流程树、 轨迹匹配和分布式计算， 可处理各种流程模型， 能有效提高原有合规性检查方法的效率， 在合理 时间内得到大型流程模型与真实事件日志的合 规性检查结果， 定位流程模型和事件日志之间的 偏差。 权利要求书4页 说明书9页 附图5页 CN 115470640 A 2022.12.13 CN 115470640 A 1.基于流 程树分解和轨 迹匹配策略的合 规性检测方法， 其特 征在于， 包括以下步骤： 1)获取基础数据， 即事 件日志和流 程模型， 用流 程树作为流程模型的建模表示； 2)将从步骤1)中所 得的流程树分解为子流程树； 3)在分布式平台Spark上为事件日志中的轨迹从步骤2)中得到的子流程树中匹配最优 子模型； 4)进行轨 迹和最优子模型的合 规性检测； 5)重复步骤3) ‑4)， 直到完成所有轨迹和其最优子模型的合规性检测， 收集合规性检测 结果， 合并生成整个事 件日志的合 规性检测结果。 2.根据权利要求1所述的基于流程树分解和轨迹匹配策略的合规性检测方法， 其特征 在于： 在步骤1)中， 获取事件日志L和流程模型M， 所述事件日志是一个有限事件序列的集 合， 每一个有限事件序列被称为一条轨迹； 若流程模型的流程建模表示不是流程树， 将之转 化为流程树PT， 所述流程树是由内部结点和叶结点组成的， 其内部结点是操作符结点， 操作 符结点指定如何从控制流角度组合 流程树的子树， 叶结点代 表活动。 3.根据权利要求2所述的基于流程树分解和轨迹匹配策略的合规性检测方法， 其特征 在于： 在步骤2)中， 将从步骤1)中所 得的流程树分解为子流程树， 具体包括以下步骤： 2.1)设定分解参数DM， 分解选择结点数量的阈值X_CUT是步骤1)中所得流程树PT中根 节点为顺序结点、 并发结点 或选择结点的子树中的选择结点的总数量除以D M， 根据X_CUT得 到分解流程树的最大层数ML， 用公式(1)计算流程树的最大分解层数中能分解选择结点的 数目； 所述选择结点是流程树的操作符结点， 指定执行其子树中的一个子树； 所述顺序结点 指定按照从左往右的顺序以此执行它的子树； 所述并发结点指 定其所有子树能够以任意顺 序同时执 行； NML＝X_CUT‑NML‑1                                         (1) 式中， NML是流程树的最大分解层数ML中分解选择结点的数目， X_CUT是分解选择结点数 量的阈值， NML‑1是前ML‑1层中选择 结点的数量； 2.2)初始化设定当前流程树T为PT， 设定当前访问结点C_N为流程树PT的根结点， 当前 层数Layer＝1， 已分解选择 结点数目X_C＝0； 2.3)首先进行层数判定， Layer>ML时， 直接将当前流程树放入子树列表S_T中； Layer＝ ML时， 若最大层已分解选择结点数目X_C大于NML则将当前流程树放入子树列表S_T中， 返回 子树列表S_T； Layer< ML时， 进行 下列步骤2.4) ‑2.7)； 2.4)判断当前访问结点C_N的类型： ①若为顺序结点、 并发结点或选择结点， 则获取当前访问结点C_N的所有子树和子结 点， 并判断子结点类型进行相应操作： a、 若当前结点的子结点全为叶结点和循环结点， 不再向下遍历分解子树， 此时： 若当前 结点C_N为顺序操作符或并发操作符， 则将当前流程树T放入子树列表S_T中； 若当前结点C_ N为选择操作符， 则将当前结点下的所有子流程树放入子树列表S_T中， 并且当L＝ML最大层 已分解选择 结点数目X_C加一； 返回子树列表S_T； b、 若当前结点的子结点中有顺序结点、 并发结点和选择结点， 按从左到右的顺序对以 这些结点为根节 点的所有子树进 行遍历分解， 设置当前层树Layer ＝Layer+1， 当前流程树T权　利　要　求　书 1/4 页 2 CN 115470640 A 2为子树， 当前访问结点C_N 为子树根结点； ②若当前访问结点C_N为循环结点， 不再遍历分解， 将当前流程树放入子树列表S_T中 并返回子树列表S_T； 2.5)用列表T_S_T存 储返回的子树列表S_T， 判断当前 结点的类型： ①若当前结点为选择操作符， 将当前结点的所有子树分解得到的列表T_S_T中所有的 子树放入子树列表S_T中， 返回子树列表S_T； ②若当前结点为顺序操作符或并发操作符， 获取到当前结点的所有子树分解得到的列 表T_S_T并放入临时列表temp中， 对临时列表temp中所有的子树列表 中的子树进行排列组 合， 获得子树组合的集 合COM； 2.6)每次从步骤2.5)中获得的COM中取出一个子树组合， 将组合中的每棵子树按照其 在当前流程树T的当前结点C_N中的位置进行重组： 删除流程树T中此位置原 来的子树， 并将 组合中的子树设为当前结点的子树， 获得一棵重组流程树放入列表G_T中， 遍历 COM， 直到处 理完COM中所有的组合， 得到重组流程树的列表G_T， 将G_T中所有子树放入子树列表S_T中 并返回子树列表S_T； 2.7)迭代向下进行步骤2.3) ‑2.4)， 直到遍历到叶结点或若最大层已分解选择结点数 目X_C大于NM； 迭代向上进行步骤2.5) ‑2.6)， 直到返回流程树PT根结点的子树列表S_T， 即 为分解流程树P_T得到的所有子流 程模型。 4.根据权利要求3所述的基于流程树分解和轨迹匹配策略的合规性检测方法， 其特征 在于， 在步骤3)中， 在分布式平台Spar k上为事件日志中的轨迹从步骤2)中得到的子流程树 中匹配最优子模型， 具体包括以下步骤： 3.1)从Hadoop分布式文件系统中以弹性分布数据集的形式读取步骤1)中得到的事件 日志L， 事 件日志L会被自动分区划分到不同的从节点上； 所述弹性分布数据集是Spark提供的主要抽象结构， 是能够进行并行操作的跨集群节 点分区的元素集合， 即将事件 日志拆分为多个子日志分片， 子日志分片以分区为单位存储 到Hadoop分布式文件系统各个结点上； 3.2)将事件日志L转化为标准XES格式， 生成标准事件日志， 将步骤2)得到的所有子流 程树转换为用Petri网表示的子模 型， 并将所有子模型封装为广播变量使用， 广播变量会被 分发到各个节点； 所述Petri网是由库所、 变迁和有向弧构成的三元组； 所述广播变量是在 每个节点保存的分布式的共享只读变量； 3.3)在分布式环境中并行地进行轨迹匹配以及轨迹和子模型的合规性检测， 根据公式 (2)为标准事 件日志中每条轨 迹匹配一个最优子模型； 式中， Scorei为第i个子模型的得分， TraceSet为当前轨迹的活动集合， Neti为第i个子 模型的活动集 合， 得分最高的子模型即为当前轨 迹的最优子模型。 5.根据权利要求4所述的基于流程树分解和轨迹匹配策略的合规性检测方法， 其特征 在于， 在步骤4)中， 进行轨 迹和最优子模型的合 规性检测， 具体包括以下步骤： 4.1)选择基于对齐的合规性检测方法或基于托肯重演的合规性检测方法作为合规性 检测的基准方法；权　利　要　求　书 2/4 页 3 CN 115470640 A 3