针对长事件序列的高效合规检查方法,显著降低计算开销。
Conformance Checking for Less: Efficient Conformance Checking for Long Event Sequences
- 采用滑动窗口分割长序列,逐段对齐提升可扩展性。
- 在多个数据集上实现最优或近似最优结果,速度远超传统方法。
- 支持预定义与发现的过程模型,适合工业级日志分析场景。
随着传感器和预测模型产生的长事件序列(称为轨迹)日益普遍,基于对齐的合规检查在面对大规模数据日志时因寻找最优对齐的指数级复杂度而变得计算不可行。为缓解这一可扩展性挑战,本文提出ConLES,一种面向长事件序列的滑动窗口合规检查方法,保留了对齐方法的可解释性。ConLES将轨迹分割为可管理的子轨迹,并逐段与预期行为对齐,显著缩小搜索空间的同时保持整体准确性。该方法利用捕捉轨迹与过程模型结构特性的全局信息,实现有依据的对齐决策并剔除看似局部最优但实际不佳的路径。在多个数据集上的性能评估表明,ConLES优于当前领先的最优及启发式算法,在长轨迹上始终达到最优或近似最优解。相比其他难以处理长序列的方法,ConLES大幅减少搜索空间、高效可扩展,并首次同时支持预定义与发现的过程模型,成为长事件序列合规检查的可行且领先方案。
原文摘要 · Abstract (English)
Long event sequences (termed traces) and large data logs that originate from sensors and prediction models are becoming increasingly common in our data-rich world. In such scenarios, conformance checking-validating a data log against an expected system behavior (the process model) can become computationally infeasible due to the exponential complexity of finding an optimal alignment. To alleviate scalability challenges for this task, we propose ConLES, a sliding-window conformance checking approach for long event sequences that preserves the interpretability of alignment-based methods. ConLES partitions traces into manageable subtraces and iteratively aligns each against the expected behavior, leading to significant reduction of the search space while maintaining overall accuracy. We use global information that captures structural properties of both the trace and the process model, enabling informed alignment decisions and discarding unpromising alignments, even if they appear locally optimal. Performance evaluations across multiple datasets highlight that ConLES outperforms the leading optimal and heuristic algorithms for long traces, consistently achieving the optimal or near-optimal solution. Unlike other conformance methods that struggle with long event sequences, ConLES significantly reduces the search space, scales efficiently, and uniquely supports both predefined and discovered process models, making it a viable and leading option for conformance checking of long event sequences.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。