第一讲-流程挖掘（Process Mining）学习日志之概念简介

大家好，欢迎来到IT知识分享网。

过程挖掘概念简介

参考：PROCESS MINING：Discovery,Conformance and Enhancement of Business Processes

1 引言

过程挖掘的目标就是：从事件数据中提取过程相关的信息。

1.1建模的局限性

过程挖掘，即从事件日志中提取有价值的过程相关信息，是对现有业务过程管理(BPM)方法的补充。BPM是一个学科，它结合了信息技术和管理科学的知识，并将其应用于运作业务过程。近年来，由于BPM具有显著提高生产力和节约成本的潜力，得到了广泛重视。业务过程管理可以看成是WFM (Workflow Management，工作流管理) 的扩展。WFM主要关注于业务流程自动化，而BPM的范围更为广泛：从过程自动化、过程分析到过程管理和工作分配。一方面，BPM的目标是改进那些可能未使用信息技术的业务过程，例如通过模拟仿真对业务过程进行建模和分析，管理层可能会获得通过提升服务水平来减少成本的思路；另一方面，BPM常常通过软件来管理、控制和支持运作流程，这也是WFM的初衷。传统的WFM技术主要关注以“机械的”方式完成业务过程自动化，并不关注人为因素和对管理的深度支持。

过程感知的PAISs(Process-Aware Information Systems，信息系统)包含传统的WFM系统，同时也包含能提供更大灵活性和支持特定任务的系统，例如大型的ERP(Enterprise Resource Planning，企业资源规划)系统(如SAP、Oracle)、CRM(CustomerRelationship Management，客户关系管理)系统、基于规则的系统、呼叫中心系统、高端中间件(如WebSphere)等，均可以看作过程感知的信息系统，尽管它们没有必要使用通用的工作流引擎来管理过程。事实上，这些信息系统都拥有明确的过程概念，也就是说，它们都能感知自己所支持的过程。数据库系统或电子邮件程序也会被用来执行某些业务过程中的某些步骤，但是这些软件工具无法“感知”用到它们的过程，即它们并不主动参与过程的管理和编排。一些作者使用术语BPMS(BPM System,业务过程管理系统)，或简单的使用PMS(Process Management System，过程管理系统)，来表达能够“感知”自己所支持的业务过程的系统。我们使用术语PAIS来强调它的范围远比传统的工作流技术要广。

BPM和PAIS的共同点在于它们都依赖于过程模型。存在许多建模业务过程的表示语言(例如Petri网、BPMN、UML和EPC)，而表示的语言共同点在于都从过程所包含的活动(和可能的子过程)的角度来描述过程，这些活动的顺序由因果依赖关系决定。此外，过程模型也可以描述时间特性、指明数据的创建和使用(例如对决策建模),或者规定资源和过程的交互方式(例如角色、分配规则、优先级等)。

1.2 一个使用Petri网表达的简单例子

1.3 过程模型是用来做什么的？

• 洞察:在建模的过程中,引发建模者从不同的角度审视过程；
• 讨论:利益相关者可以使用模型来组织讨论；
• 文档化:过程被文档化,用于指导人们行动或明晰目标(参见质量管理)；
• 验证:分析过程以发现系统或程序中的错误(如潜在的死锁)；
• 性能分析:可以使用仿真等技术来发现对响应时间、服务水平等造成影响的因素；
• 模拟:模型能够使最终用户”播放”出不同的场景,从而为设计者提供反馈；
• 规约:模型可以在一个 PAIS系统实现前描迷它,因此可以作为开发者和最终用户管理人员之间的”合同”;
• 配置:模型可以用来配置信息系统。

显然，过程模型在大型组织中扮演着重要的角色。当重新设计过程并引入新的信息系统时，过程模型会用于多种场景。通常会用到两类模型：(a)非形式化模型和(b)形式化模型(也叫做“可执行”模型)。非形式化模型用于讨论和归档，而形式化模型则用于分析和实施(即过程的实际执行)。前一种(a)对应于，示意高层次过程的“PowerPoint图”;而后一种(b)对应于从运行代码中捕获的过程模型。非形式化模型通常是模糊的，而形式化模型往往关注点非常聚焦并且十分详细，便于利益相关者理解。这里，我们提出另一种观点：与模型的种类——非形式化或形式化无关，一种反映模型与现实是否一致的观点。一个用于配置工作流管理系统的过程模型可能与现实保持良好的合规性，因为该模型会驱使人们按照其指定的方式去工作。不幸的是，大多数手工建立的模型都与现实严重脱节，并且只能提供手头过程的一种理想化视图。此外，允许进行严谨分析的形式化模型可能对实际过程帮助甚微。

模型如果不能很好地与现实联系起来，那么它的价值会十分有限。当与模型相关的人无法信任这些模型时，它们就变成了“纸老虎”。例如，对一个实际的过程而言，如果模型是真实过程的一个理想化版本，那么对这个模型进行仿真实验会毫无意义。这就好比是—基于一个理想模型——做出错误的重新设计的决定。按照一个忽视现实的过程模型去实现一个项目也是十分危险的。一个建立在理想化模型基础上的系统对于最终用户来说可能是毁灭性的和不可接受的，一个很好的例证就是大多数参考模型(reference model)的质量都十分有限。参考模型被用在大型企业系统中(例如SAP)，同时也被用于归档特定分支机构的过程，像NVVB(Nederlandse Vereniging Voor Burgerzaken，即荷兰公民协会)的模型就描述了荷兰直辖市的核心过程。此处的想法在于让“最佳实践”在不同企业组织中共享。然而不幸的是，这些模型的质量与期望相去甚远。例如，SAP参考模型对SAP实际支持的过程帮助非常少，事实上，超过20%的SAP模型含有严重的瑕疵(死锁、活锁等)。这些模型与现实脱节，并对最终用户价值甚微。

鉴于(a)对过程模型的兴趣(b)大量的事件数据以及©手工模型有限的质量，将事件数据与过程模型结合起来将是很有意义的。采用这种方法，实际的过程可以被发现，现有的过程模型也能够被评估和改进，这正是过程挖掘致力于达到的目标。

2 过程挖掘

过程挖掘是一门相对年轻的研究学科，它一方面位于机器学习和数据挖掘之间，另一方面又位于过程建模与分析中。过程挖掘的理念是通过从事件日志中提取出知识，从而去发现、监控和改进实际过程(即非假定的过程),而事件日志在如今的系统中是很容易获得的。

如图1.4所示，过程挖掘建立了两种连接，一是实际过程与其数据的连接；二是实际过程与过程模型的连接。正如1.1节中所解释的，数字世界和物理世界的融合日益深入。如今的信息系统记录了海量的事件，经典的WFM系统(如Staffware和COSA)、BPM系统(如Pallas Athena的BPMlone、Pegasystems的SmartBPM、FileNet、Global360,以及Lombardi Software的Teamwork)、ERP系统(如SAP Business Suite、Oracle E-Business Suite,以及Microsoft Dynamics NAV)、PDM系统(如Windchill)、CRM系统(如Microsoft DynamicsCRM和SalesForce)、中间件(如IBM的WebSphere和Cordys Business Operations Platform)和医疗信息系统(如Chipsoft和Siemens Soarian)都提供了对已执行的活动的详细信息。

图1.4将这些数据称为事件日志(event log)。所有上述提到的PAIS都会直接提供事件日志。但是，绝大多数信息系统用非结构化的形式存储这些信息，例如，这些事件数据分散在多个表中，或者需要从交换消息的子系统中分离出来。在这种情况下，事件数据虽然存在，但是获取它却要下一番工夫，因此数据提取是过程挖掘工作不可或缺的组成部分。

假设我们能够顺序地记录事件，每一个事件都代表一个活动(即明确定义的过程步骤)并且与一个特定的案例相关(一个过程实例)。举例来说，我们考虑图1.1所示的索赔申请处理过程，这里的案例就是某个申请，并且每个案例都记录了一条由事件组成的轨迹。一个可能的轨迹例子是<register request,examine casually,check ticket,decide,reinitiaterequest,check ticket,examine thoroughly,decide,pay compensation>,此处使用活动名来表示事件。但是，decide事件在不同时间出现了两次(轨迹中的第四个和第八个事件),产生了不同的结果，也可以由不同的人员执行。显然，区分这两次决定是必要的。因此大多数事件日志都会保存事件的额外信息。事实上，过程挖掘技术常常需要使用事件的额外信息，例如，执行或发起这个活动的资源(如人员或设备)、事件的时间戳或是事件中记录下来的数据信息(如订单的大小)。

如图1.4所示，事件日志可以用于3种类型的过程挖掘场景。

过程挖掘的第一类应用是发现。发现技术使用不包括任何先验信息的事件日志生成模型。第六讲文章将会讲到的α算法,这种算法是利用一个事件日志生成一个Petri网，这个Petri网能够解释该日志记录的行为。例如，对于图1.1中的过程，如果给出充足的执行样本，α算法能够在不使用任何附加信息的情况下，自动地构造出Petri网。如果事件日志中包含有关资源的信息，这种技术也能够发现资源相关的模型，例如，一个显示组织中的人员如何协作的社交网络。

过程挖掘的第二类应用是合规性。这里，一个已知的过程模型将与它产生的事件日志相比较。合规性检测可以被用来检查记录在日志中的实际情况是否和模型相吻合。例如，有一个过程模型，模型中说明大于一百万欧元的支付订单需要进行两次检查，对事件日志的分析可以发现这条规则是否被执行。另外一个例子是检测被称为“双人原则”的准则——即某些特定的活动不能由同一个人来完成。通过扫描一个需要满足此准则的模型所产生的事件日志，我们可以发现潜在的欺诈事件。因此，合规性检测可以用来侦查、定位与解释偏差，并测量这些偏差的严重程度。

过程挖掘的第三类应用是改进。其理念是利用实际过程产生的事件日志来扩展或改进一个已存在的过程。虽然合规性检测度量了模型和现实的契合度，过程挖掘的第三种类型旨在改变和扩展已知模型。改进的一种类型是修复，即修改模型使其更好地反映现实业务。例如，如果两个活动被建模为顺序关系，而在现实中它们可以以任意顺序发生，那么这个模型就应该被修正为能够正确地反映这一情况。改进的另一种类型是扩展，即通过过程模型和日志其他属性关联给模型增加一个新的视角。一个例子是给已知的过程模型扩展性能数据。例如，利用“索赔申诉”模型日志中的时间戳信息，我们可以在图1.1的模型基础上显示出瓶颈、服务水平、生产周期和频率。类似的，图1.1可以扩展出资源信息、决策规则和质量指标等。

如前所述，图1.1和图1.2所示的过程模型只显示了控制流。但是，当过程模型被扩展时，新视角将被添加。此外，发现和合规性技术并不局限于控制流。例如，一个人可以发现一个社交网络，并利用事件日志检查一些组织模型的有效性。因此，除了上述3个彼此正交的挖掘类型(发现、合规性和改进),还可以识别过程模型的不同视角。

迄今为止，大多数案例都假定过程挖掘是离线完成的，也就是说，过程都被事后分析，以便知道它们能否被改进或更好地被理解。但是，越来越多的过程挖掘技术能够被用于在线分析，我们将其称为运作支持，例如，在偏差实际发生的时候检测出不合规性。另一个例子是对正在运行的案例进行时间预测，即给定一个已经被执行了一部分的案例，可以通过与其相似案例的历史信息来估算它的剩余执行时间，这表明“过程挖掘频谱”十分广泛，并不局限于过程发现。事实上，如今的过程挖掘技术确实能支持图1.3所示的整个BPM生命周期。过程挖掘不仅仅与设计和诊断/需求阶段相关，更与实施/监控和调整阶段相关。

3 分析示例日志

过程发现所用的过程挖掘算法可以将表1.2中所示的信息转换为过程模型。例如，基础的α算法123可以利用表1.2中的输入数据发现前文描述的Petri网。图1.5展示了利用紧凑标签得到的结果模型。我们很容易检查表1.2中所有的6条轨迹在模型中都能得到。让我们重演第一个案例的轨迹<a,b,d,e,h>,来查看轨迹是否“fits”(即符合)模型。在图1.5所示的初始标识中，因为“start”库所中有托肯，a确实是使能的。在a发生后“cl”和“c2”被标记，即两个库所中均含有托肯。b在此标识下也是使能的，它的执行使得“c2”和“c3”中拥有托肯。现在我们执行<a,b>而剩下<d,e,h>。下一个时间d确实是使能的，它执行后的标识使e使能(库所“c3”和“c4”中有托肯)。e发生使得标识变为仅“c5”中有一个托肯。这个标识使最后一个事件h使能。在执行完h之后，该案例如所期望的结束了，剩下一个托肯在库所“end”中。类似地，表1.2中的另外5条轨迹都可以被检查出在该模型中是能出现的，并且所有轨迹都会得到只有一个托肯在库所“end”中的标识结果。

图1.5展示的Petri网同样允许没有在表1.2中出现的轨迹发生。例如，轨迹<a,d,c,e,f,b,d,e,g>和<a,c,d,e,f,c,d,e,f,c,d,e,f,c,d,e,f,b,d,e,g>也是可能的。这是一个理想的现象，因为我们的目的并不仅仅是表达事件日志中的特定轨迹集合。过程挖掘算法需要概括日志中的行为，来展示一个尽量不会被下一个观测集推翻的过程模型。过程挖掘的一个挑战就是如何平衡“过拟合”(模型太特殊，只允许几种“特殊情况”发生)和“欠拟合”(模型太通用，允许无关的行为发生)。

当比较事件日志和模型时，这个例子看上去很好地在“过拟合”和“欠拟合”中找到了平衡点。所有案例都从a开始，在e或h结束。每个e的前边都有d和两个检查活动(b和c)之一。此外，e后边跟着f、g或h。重复执行的b、c、d和e说明这里存在循环。这些特性都被图1.5所示的网充分捕捉到了。

我们现在考虑一个只包含两条轨迹<a,b,d,e,h>和<a,d,b,e,h>,即原始日志中的案例1和案例4的事件日志。对于这个日志，α算法构建出图1.6所示的Petri网。该模型只允许两条轨迹，并且刚好就是小型事件日志中的那两条轨迹。b和d被建模成并行的，因为它们可以以任意顺序执行。对于大型和复杂的模型，发现并发是十分重要的。通常如果不对并发建模，会得到一个庞大的“意大利面式”|的模型，其中相同的活动要被重复建模(重名任务)。

a算法只是众多过程发现算法中的一个。对于现实的日志而言，很多更高级的算法被用来解决“过拟合”和“欠拟合”的平衡问题，并且能够处理“不完备”(即由于大量的选择，日志只包含可能行为的很小一部分)和“噪音”的情况(即日志包含特殊/罕见的行为，这些行为不该被自动纳入模型)。本书会阐述一些典型算法并指导读者进行选择。在这一节中，我们用Petri网描述发现的过程模型，因为Petri网是一种简洁的表示过程的方式，并有明确而简洁的语义。尽管如此，大多数挖掘技术都独立于特定的表达形式。例如，图1.5中的Petri网模型可以被(自动地)转换为图1.2中的BPMN模型。

正如1.3节所述，过程挖掘不仅仅被应用于过程发现。事件日志可以被用于检查合规性和改进现有模型。此外，还可以从不同的视角进行考虑。为了解释这点，让我们考察表1.3中的事件日志。

前6个案例和以前相同。不难看出，第7个轨迹<a,b,e,g>不可能符合图1.5所示的模型。模型要求在执行e之前先执行d,但是d并没有在日志中出现，这说明票据在做出决策和支付索赔前没有被检查。合规性检测技术致力于发现这种差异。当检查该事件日志其余部分的合规性时可以发现，案例8和案例10也同样不符合。案例9虽然与之前的轨迹都不同，但可以由该模型产生。轨迹<a,b,d,e>(即案例8)的问题在于没有结论活动(拒绝支付或同意支付)。轨迹<a,c,d,e,f,b,d,g>(案例10)的问题在于航空公司在做出最终决策前就支付了赔偿。注意，合规性可以从两个角度解释：(a)模型没有反映现实行为(“模型错误”)和(b)现实偏离期望的模型(“事件日志错误”)。当模型是描述性的，即用来描述或预测现实时，采用第一种观点。当模型作为一种准则，即用来规范或指导现实行为时，采用第二种观点。

表1.1所示的原始事件日志也包含了资源、时间戳和成本的信息，这些信息可以被用于发现其他视角、检查非纯控制流模型的合规性，或者使用附加信息对模型进行扩展。例如，可以基于个体间的互动模式派生出一个社交网络，该社交网络可以基于“工作交接”关系，个体x执行某活动在因果上先于个体y执行某活动这种情况越频繁，x和y的关系就越强。图1.7展示了一个面向控制流的模型，可以使用1.3节中提到的另外3个主要视角来扩展这个模型。通过分析表1.1中的事件日志，我们可以发现Sara是唯一一个执行活动“decide”和“reinitiate request”的人，这说明有一个“经理角色”而Sara是唯一一位拥有该角色的人。活动“examine thoroughly”只有Sue和Sean执行，这说明一些“专家”角色与该活动相关。其余活动由Pete、Mike和Ellen执行，这说明有一些“助理角色”,如图1.7所示。用于组织过程挖掘的技术1会发现诸如此类的组织结构，并通过角色将活动和资源联系起来。利用日志中的资源信息，组织视角可以被添加到过程模型上。相似地，时间戳和频率信息可以被用来在模型上添加性能相关的信息。图1.7显示，从某一项检测(活动b或c)到实际决策(活动e)之间花费的时间是可以被测量的，如果这段时间过长，可以使用过程挖掘来诊断出现了哪些问题，并发现可能导致问题的原因。如果事件日志包含案例相关的信息，那么这些信息可以被用来分析过程中的决策点。例如，通过决策点分析，我们可以知道当请求的索赔金额大于800欧元时往往会被拒绝。

过程挖掘可以使不同的视角交叉关联起来，从而发现令人惊异的结论。类似发现的例子有：“被Sean审查的请求往往被拒绝得更频繁”、“票据在审查之后被检查的请求往往花费更多时间”、“索赔金额少于500欧元的请求往往不需要更多的迭代就结束了”。此外，这些视角可以被联系到合规性问题上。例如，Pete可能涉及较多未被正确处理的请求。这些例子告诉我们，在分析含有个体信息的事件日志时需要考虑隐私问题。