《Data Science and Management》：An optimized backbone-based process layout generation method using integer programming and heuristics to enhance user comprehension
编辑推荐：
过程挖掘（Process Mining, PM）是一门专注于从信息系统收集的事件日志中提取关于业务流程的有价值见解的学科。过程挖掘的一个关键组成部分是可视化过程模型，旨在将复杂过程转化为清晰直观的图形表示。此类可视化创造了透明度，并且可以叠加合规性与性能诊断。
过程挖掘（Process Mining, PM）是一门专注于从信息系统收集的事件日志中提取关于业务流程的有价值见解的学科。过程挖掘的一个关键组成部分是可视化过程模型，旨在将复杂过程转化为清晰直观的图形表示。此类可视化创造了透明度，并且可以叠加合规性与性能诊断。最近，一种稳定的图形布局算法被引入，通过保留过程主干（backbone）——最能代表事件日志的活动序列——来增强模型可读性。基于主干的过程布局提供了一个关键优势：即使应用过滤器，主干仍然保持完整。因此，与其他布局方法相比，节点位置变化最小，使用户更容易在过滤视图中定位相关节点和边。尽管有这些好处，仍然存在若干阻碍过程理解的挑战。在本文中，研究人员识别了现有布局方法中的关键问题，包括不必要的反向边、受限的水平对齐、非正交的主干结构以及贪心式的节点放置。为了解决这些局限性，研究人员提出了一种增强的过程布局生成方法，该方法将整数规划（Integer Programming, IP）与启发式技术相结合。研究人员使用真实世界的事件日志评估了该方法，显示了反向边、边交叉和边长的显著减少，以及节点正交性和布局对称性的改善。一项定性的用户研究进一步证实了研究人员提出的布局相对于现有基准方法的强烈偏好，展示了其在改进过程模型理解方面的有效性。
**论文解读：基于整数规划与启发式的优化主干过程布局生成方法**
**研究背景与问题**
过程挖掘（Process Mining, PM）旨在从信息系统的事件日志中提取业务流程知识，其核心环节之一是过程模型的可视化。清晰直观的布局能显著提升用户对流程的理解，而布局质量受多个因素影响，如节点正交性、对称性、边交叉数、边长、边正交性和流程一致性。近年来，基于主干（backbone）的过程布局方法通过保留最频繁活动序列来增强模型稳定性和可读性，尤其在过滤条件下节点位置变化小，便于用户追踪。然而，现有主干布局方法存在四大局限：不必要的反向边（破坏流程一致性）、禁止水平边（导致空间浪费与误导性先后关系）、非正交的主干排列（增加边长与正交性损失）以及贪心式节点分布（造成布局不对称并增加边交叉）。这些缺陷阻碍了用户对过程模型的理解，亟需改进。为此，研究人员开展本研究，旨在通过结合整数规划（Integer Programming, IP）与启发式技术，提出一种增强的主干过程布局生成方法，以提升布局质量和用户理解。该论文发表在《Data Science and Management》。
**研究内容与结论**
研究人员基于Sugiyama框架，提出了一套包含直接跟随图（Directly Follows Graph, DFG）生成、主干确定、秩分配、虚拟节点生成、组件平衡、交叉最小化和节点定位的完整流程。在秩分配步骤中，通过整数规划最小化反向边并允许水平边，将循环节点置于同秩以更准确表示并发关系；组件平衡步骤采用整数规划优化左右节点数量差，实现对称布局；节点定位步骤通过将布局分为左、主干、右三个区域分别进行紧致化处理，保持主干的线性结构。方法在五个真实事件日志（weblog、hospital log、BPI 2017、BPI 2018、BPI 2019）上进行了定量评估，与Mennens等人（2021）的基准方法比较，在反向边数、平衡度、边交叉数、边长和节点正交性五个指标上显著优于基准，尽管在边正交性上略逊。定性的用户研究（27名参与者）进一步证实：大多数参与者认为研究人员提出的布局在任务辅助性、可读性和美观性上更优，尤其对循环结构识别和紧凑性给予积极评价。此外，运行时间分析显示研究人员的方法在三个主要步骤（秩分配、组件平衡、节点定位）上均快于基准方法。
**关键技术方法**
研究采用的关键技术方法包括：1）整数规划（Integer Programming, IP）：用于秩分配阶段，以最小化反向边和秩数，同时允许水平边；用于组件平衡阶段，以最小化主干两侧节点数差异。2）启发式技术：在节点定位阶段，通过基于中位数的坐标初始化和紧致化打包（packcut）算法，将布局分为左、主干、右三部分分别处理，保持主干线性。3）交叉最小化：采用Gansner等人的方法，分别在左右子图上独立执行，减少边交叉。4）数据来源：使用五个公开与内部事件日志（BPI 2017、BPI 2018、BPI 2019、医院日志、网站日志），涵盖个人贷款申请、农业补贴支付、采购订单处理、医院管理和用户浏览等不同领域。
**研究结果**
**6.1 定量评估** 在五个事件日志上以五种过滤比例（100%、80%、60%、40%、20%）进行25次实验，使用六项指标衡量。结果显示：在反向边数上，研究人员的方法在21/25实验中少于基准；在平衡度上，23/25实验优于基准；在边交叉、边长和节点正交性上，研究人员的方法在所有实验中一致优于基准；仅边正交性略差（19/25基准占优）。这得益于整数规划对秩分配的优化和紧凑布局。
**6.2 定性评估** 27名参与者对BPI 2019和医院日志的布局进行对比，回答四项任务（如找最频繁序列、找前驱后继、找循环对），并从任务辅助性、可读性和美观性三方面投票。结果显示：在BPI 2019日志上，任务辅助性偏好77.8%（基准14.8%），可读性偏好74.1%（基准25.9%），美观性偏好63.0%（基准22.2%）；在医院日志上，偏好更强（任务辅助性74.1%，可读性和美观性均92.6%）。参与者主要认为研究人员的方法更紧凑、循环可见、对称性好；少数偏好基准者认为其更空旷、视觉更简单。
**6.3 运行时间** 在秩分配、组件平衡和节点定位三个步骤中，研究人员的方法均比基准快，主要由于整数规划求解器的高效预解与并行处理，以及更少的虚拟节点数。
**讨论与结论**
讨论指出，该方法对主干选择相对稳健（基于前三频繁变体时布局质量波动小）。但存在局限性：水平边可能部分干扰严格自上而下的流程顺序；优化目标固定，无法自适应调整；评估仅与单一基准比较，未包括商业工具（如Celonis）或通用图布局算法；定性任务较基础，未涉及瓶颈检测或变体比较；未分析约束（如非互惠节点必须不同秩）的影响；未研究过滤时布局的稳定性。未来方向包括：深入研究水平边对理解的影响；开发自适应、偏好感知的布局生成；定义布局稳定性度量；探索AI驱动的过程布局生成（该优化方法可作为高质量训练数据）。
**结论翻译**：本研究提出了一种改进的基于主干的过程布局生成方法，旨在解决现有方法中的关键局限，如不必要的反向边、水平边的限制、非线性的主干对齐以及不平衡的节点分布。通过将整数规划与启发式技术相结合，所提出的框架增强了秩分配、虚拟节点生成、组件平衡和节点定位。该方法在五个真实世界事件日志上进行了评估，并与基准方法相比，在反向边数、边交叉、边长、节点正交性和布局对称性等核心指标上取得了改进。这些改进在不同过程复杂度和过滤条件下保持一致。一项定性的用户研究进一步验证了这些发现：参与者更偏好所提出的布局，认为其结构更清晰、视觉更平衡、更支持流程解释。用户还发现由于布局的有序呈现，路径追踪、循环检测和活动标签阅读更为容易。
