提出高效算法，从不确定事件日志中快速找出最可能的前K条执行路径。
Ranking the Top-K Realizations of Stochastically Known Event Logs
- 基于事件独立性假设，设计O(Kn)时间复杂度的排序算法。
- 实验表明，前K条路径比单一最优路径更能反映真实情况。
- 适合处理带概率的复杂流程日志，提升过程挖掘的可靠性。
事件日志中常存在不确定性，如记录错误、数据质量问题或活动识别使用概率模型。随机已知事件日志通过编码多个可能的事件实现，但其可能的执行路径数量随日志规模呈指数增长，导致穷举不可行。因此，文献建议仅考虑最可能的前K条路径。本文实现了一种高效算法，在事件独立性假设下以O(Kn)时间复杂度计算事件日志的前K条最可能实现路径，其中n为日志中不确定事件数。该算法被用于分析前K条路径相比单条最优路径在不同输入数据特性下的有效性。结果表明，前K条路径的优势取决于日志长度和事件概率分布。研究凸显了前K排名在提升不确定性感知流程挖掘技术方面的潜力。
原文摘要 · Abstract (English)
Various kinds of uncertainty can occur in event logs, e.g., due to flawed recording, data quality issues, or the use of probabilistic models for activity recognition. Stochastically known event logs make these uncertainties transparent by encoding multiple possible realizations for events. However, the number of realizations encoded by a stochastically known log grows exponentially with its size, making exhaustive exploration infeasible even for moderately sized event logs. Thus, considering only the top-K most probable realizations has been proposed in the literature. In this paper, we implement an efficient algorithm to calculate a top-K realization ranking of an event log under event independence within O(Kn), where n is the number of uncertain events in the log. This algorithm is used to investigate the benefit of top-K rankings over top-1 interpretations of stochastically known event logs. Specifically, we analyze the usefulness of top-K rankings against different properties of the input data. We show that the benefit of a top-K ranking depends on the length of the input event log and the distribution of the event probabilities. The results highlight the potential of top-K rankings to enhance uncertainty-aware process mining techniques.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。