Abstract: Process discovery is one of the important areas of process mining research,and its goal is to generate business process models by analyzing event logs.However,existing process discovery methods are inefficient when dealing with large-scale logs.To better analyze the models and improve efficiency,the decomposition process discovery has become a hot topic in the research field,aiming to decompose complex process models into smaller and simpler sub-models.Refined Process Structure Tree (RPST) is a graph decomposition technique that takes a directed graph as input and a hierarchical tree structure composed of single-input and single-output segments as output.However,the application of RPST to mine the model lacks in quality.To overcome the shortcomings of the existing methods and to improve the quality of the model,a decomposition process discovery method based on footprint matrix was proposed.The footprint matrix was obtained based on the order relationship between logs,and the concept of Relation-Refined Process Structure Tree (R-RPST) was proposed for decomposing the causal dependency graph between activities.According to the decomposed picture segments,the sub-logs were generated,and the sub-models were obtained using existing mining methods.Finally,sub-models were merged based on the footprint matrix to determine the branching structure of boundary activities.The proposed method had been implemented based on the ProM platform,and experiments were conducted to compare the proposed method with existing process discovery methods using publicly available real logs and simulated logs such as BPI Challenge and ETM.The experimental results showed that the proposed method was time efficient and the obtained models were of high quality.

Key words: process discovery, decomposition, refined process structure tree, footprint matrix

摘要： 模型挖掘是流程挖掘研究的重要领域之一,其目标是通过分析事件日志生成业务流程模型。然而,现有模型挖掘方法在处理大规模日志时效率较低。为更好地分析模型并提高效率,分解模型挖掘成为研究领域的热点,旨在将复杂流程模型分解为更小、更简单的子模型。精简流程结构树（RPST）是一种以有向图为输入,以单入单出片段构成的层次树状结构为输出的图分解技术。但应用RPST挖掘模型在质量上有所欠缺,为克服现有方法的不足并提高模型质量,提出基于足迹矩阵的分解模型挖掘方法。根据日志间次序关系得到足迹矩阵,提出关系精简流程结构树（R-RPST）的概念,用于分解活动间因果依赖图。根据分解后的图片段生成子日志,利用已有挖掘方法得到子模型,最后基于足迹矩阵判断边界活动的分支结构合并子模型。所提方法已基于ProM平台实现,利用BPI Challenge、ETM等公开真实日志及仿真日志与已有模型挖掘方法进行对比实验。结果表明,所提方法时间效率较高,得到的模型质量较高。

关键词: 模型挖掘, 分解, 精简流程结构树, 足迹矩阵