Outlier Detection Techniques for Process mining Applications

Outlier Detection Techniques for Process Mining Applications

Abstract. Classical outlier detection approaches may hardly fit process mining applications, since in

these settings anomalies emerge not only as deviations from the sequence of events most often registered

in the log, but also as deviations from the behavior prescribed by some (possibly unknown) process

model. These issues have been faced in the paper via an approach for singling out anomalous evolutions

within a set of process traces, which takes into account both statistical properties of the log and the

constraints associated with the process model. The approach combines the discovery of frequent

execution patterns with a cluster-based anomaly detection procedure; notably, this procedure is suited

to deal with categorical data and is, hence, interesting in its own, given that outlier detection has mainly

解决，该方法同时考虑了日志的统计特性和与流程模型相关的约束。该方法将频繁执行模式的

发现与基于集群的缺陷检测过程相结合;值得注意的是，这一过程适合于处理分类数据，因此，

考虑到文献中离群值检测主要是在数值域上进行的研究，它本身就很有趣。论文中提出的所有

算法都已实现并集成到一个系统原型中，该原型已经过全面测试，以评估其可伸缩性和有效性。

1 Introduction

1 引言

Several efforts have recently been spent in the scientific community and in the industry to exploit

data mining techniques for the analysis of process logs [12], and to extract high-quality knowledge on

the actual behavior of business processes (see, e.g., [6,3]). In a typical process mining scenario, a set of

traces (registering the sequencing of activities performed along several enactments) is given to hand and

c).

最近，科学界和业界都在努力开发数据挖掘技术，以分析流程日志[12]，并提取关于业务

流程的实际行为的高质量知识(参见，[6,3])。在一个典型的流程挖掘场景中，会提供一组集合

(记录沿几个规则执行的活动的顺序)，目的是导出一个模型来解释其中记录的所有事件。最后，

“挖掘”模型被用来(重新)设计一个详细的流程模式，能够支持即将到来的实施。例如，图 1右

侧所示的事件日志(关于活动 a、b、…o)可能在输入中给出，目标是派生出一个类似于左侧所示

的模型，根据直观的符号表示一个简化的流程模式，其中优先关系被描述为活动之间的定向箭

头(例如，b 必须在 a 之后执行，并与 c 并发)。

In the paper, this peculiar aspect of process mining is investigated and the problem of singling out

exceptional individuals (usually referred to as outliers in the literature) from a set of traces is addressed.

这些方法应用于流程挖掘应用时，出现了新的挑战:

(C1) On the one hand, looking only at the sequencing of the events may be misleading in some cases.

Indeed, real processes usually allow for a high degree of concurrency, and are to produce a lot of traces

that only differ in the ordering between parallel tasks. Consequently, the mere application of existing

notable fraction of task sequences might have very low frequency in the log. As an example, in Figure

1, each of the traces in {s1, ..., s5} rarely occurs in the log, but it is not to be classified as anomalous.

Indeed, they correspond to a different interleaving of the same enactment, which occurs in 10 of 40

traces.

(C1) 一方面，只看事件的先后次序在某些案例下可能会产生误导。实际上，真正的流程通常

允许高度的并发性，并且会产生许多只在并行任务之间的顺序不同的轨迹。因此，仅仅将现有

的用于顺序数据的离群值检测方法应用于流程日志可能会产生许多假阳性结果，因为有相当一

as some trace might well be supported by a model, yet representing a behavior that deviates from that

observed in the majority of the traces. As an example, in Figure 1, traces

correspond to the

same behavior where all the activities have been executed. Even though this behavior is admitted by the

process model on the left, it is anomalous since it only characterizes 3 of 40 traces.

(C2) 另一方面，考虑到与理想模式的遵从性可能会导致假负性，因为一些轨迹可能很好地得

到模型的支持，但表示的行为却与在大多数轨迹中观察到的行为不同。例如，在图 1 中，轨迹

knowledge about the model for the given process.

面对(C1)和(C2)很复杂，因为在给定的轨迹集合下的流程模型通常是未知的，必须从数据本身

推断。例如，在我们的运行示例中，一个初步的问题是我们如何能够识别

，…，

而没有任何关于给定流程的模型的先验知识。

Addressing this question and subsequently (C1) and (C2) is precisely the aim the paper, where an outlier

detection technique tailored for process mining applications is discussed. In a nutshell, rather than

extracting a model that accurately describes all possible execution paths for the process (but, the

anomalies as well), the idea is of capturing the “normal” behavior of the process by simpler (partial)

models consisting of frequent structural patterns. More precisely, outliers are found by a two-steps

approach:

解决这个问题以及随后的(C1)和(C2)正是论文的目的，其中讨论了为流程挖掘应用量身定制的

离群点检测技术。简而言之，与其提取一个精确描述流程所有可能执行路径的模型(但是，也

包括异常情况)，还不如通过由频繁的结构模式组成的更简单(部分)的模型来捕获流程的“正常”

行为。更准确地说，异常值是通过两步方法找到的: