过程挖掘技术的研究与应用

邓璐娟，董东晓，陈欣欣

(郑州轻工业学院 计算机与通信工程学院，河南 郑州 450002)

过程挖掘技术的研究与应用

邓璐娟，董东晓，陈欣欣

(郑州轻工业学院 计算机与通信工程学院，河南 郑州 450002)

由于业务流程日益复杂多变，并且流程模型设计者对于业务流程的理解主观性较强，大多数通过人工建立的过程模型都与现实情况存在较大偏差，使用过程挖掘技术能够很好地解决这一问题。针对典型的工作流系统中索赔事件流程的日志，对其建模流程进行分析，使用过程挖掘工具ProM进行挖掘得到对应的过程模型。实验结果表明，通过过程挖掘技术所得到的过程模型与实际的业务流程相符，与人工流程建模相比，提高了效率，降低了成本。

过程挖掘；事件日志；挖掘算法

Abstract: Because the business process is increasingly complicated, and the process model for business process designer’s understand has strong subjectivity, most process models established artificially have a big deviation with reality. Using process mining technology can solve this problem well. In view of the log of the claim event process in the typical workflow system, the modeling process is analyzed, and the corresponding process model is obtained by using the process data mining tool ProM. The experimental results show that the process model is consistent with the actual business process, and the process model is very efficient and can reduce the cost.

Key words:process mining; event log; mining algorithm

0 引言

企业资源规划系统(ERP)、供应链管理系统(SCM)、客户关系管理系统(CRM)和工作流管理系统(WFM)等在企业中得到了广泛的应用。这些信息系统和它们所支持的业务运作流程结合非常紧密。面对复杂的、快速多变的业务流程，工作流建模技术遇到了问题，例如，由于流程设计者对于业务流程的理解不到位，使得设计出的工作流模型与实际的业务流程存在偏差。此外，系统中记录了数量众多的事件，从这些宝贵的事件数据中提取有价值的信息也比较困难。过程挖掘技术的出现能很好地解决这些问题，使用过程挖掘技术进行企业流程建模不需要依赖业务流程领域的专家知识，只需要提供记录这些流程的数据就能够根据这些流程数据自动生成对应的过程模型，并且这种过程模型的生成方法是领域独立的[1]。

1 过程挖掘技术的应用

通过对事件日志中的数据进行分析提取得到过程相关的信息，从而自动地发现过程模型的技术就是过程挖掘。过程挖掘涉及机器学习、数据挖掘、过程建模与分析等多个领域的知识[1]。过程挖掘技术通过对事件日志的处理和分析发掘日志中所包含的业务过程模型，过程挖掘建立了两种连接，一是实际过程与其数据的连接；二是实际过程与过程模型的连接。这种自动生成过程模型的技术不仅能够最大限度地减少建模过程中人为因素的干扰，使得过程模型与实际过程更加吻合，而且还提高了建模效率。

事件日志是进行过程挖掘的基础，一份高质量的事件日志能为过程挖掘的实施提供很多便利。如图1所示，事件日志主要用于三种类型的过程挖掘场景:第一种应用是发现，即使用不包括任何先验信息的事件日志生成过程模型；第二种应用是合规性检查，即使用一个已知的过程模型与它产生的事件日志相比较，验证过程模型是否与日志中的实际情况相吻合；第三种应用是改进，其理念是利用实际过程产生的事件日志来扩展或改进一个已经存在的过程。

图1 三种主要的过程挖掘场景

表1中显示了处理索赔申请过程所对应的一个可能日志的一部分，每一行代表一个事件，事件按照不同的案例进行分组。在具体的挖掘过程中只用到了事件日志中的部分信息，过程挖掘的最低要求是每个事件都能对应一个案例和一个活动，并且一个案例中的事件是有序的。因此，表中的“案例ID”和“活动”这两个列代表了过程挖掘对于事件日志的最低要求。

表1 索赔申请事件部分日志

在真实的工作流系统中，事件日志以挖掘可扩展标记语言(Mining eXtensible Markup Language,MXML)文件的形式保存过程挖掘工具ProM对其操作，MXML也是当前存储和交换事件日志的事实上的标准。采用IEEE Task Force on Process Mining小组定义的XES(eXtensible Event Stream)格式，则描述的事件流程的日志如下所示。

……

……

……

对这个事件，采用α算法进行挖掘。L表示基于某个活动集合T的事件日志，T⊆A，则α(L)可以如下定义：

(1)TL={t∈T∃σ∈Lt∈σ}

(2)TI={t∈T∃σ∈Lt=first(σ)}

(3)TO={t∈T∃σ∈Lt=last(σ)}

(4)XL={(A,B)A⊆TL∧A≠Ø∧B⊆TL∧B≠Ø∧∀a⊆A∀b⊆Ba→Lb∧∀a1,a2⊆Aa1#La2∧∀b1,b2⊆Bb1#Lb2}

(5)YL={(A,B)∈XL∀(A′,B′)∈XLA⊆A′∩B⊆B′⟹(A,B)=(A′,B′)}

(6)PL={P(A,B)(A,B)∈YL}∪{iL,oL}

(7)FL={(a,p(A,B))(A,B)∈YL∧a∈A}∪{(p(A,B),b)(A,B)∈YL∧b∈B}∪{(iL,t)t∈TI}∪{(t,oL)t∈To}

(8)α(L)=(PL,TL,FL)

第一步，检查出现在日志中的活动(TL)，这些活动对应着最终生成的工作流网中的变迁。第二步要找出开始活动的集合TI，即在轨迹中出现在第一个位置的所有活动的集合。第三步要找出结束活动的集合TO，即在轨迹中出现在最后一个位置的所有活动的集合。第四步要确定工作流网中的库所以及它们之间的连接关系XL。A中任何一个元素不能紧跟同集合内的其他元素，即对于所有的a1,a2∈A都有a1#La2，对于集合B中的元素也是同样的要求，B中的元素都可以紧跟A中任意元素后边，反之不然，即对于所有的(a,b)∈A×B，有a→Lb。所有满足要求的A，B对构成的结合就是XL。第五步是要精简库所。如果把XL中的每个元素都作为一个库所，库所规模就很大，因此对库所进行精简，只保留“最大的”(A,B)，即(A′,B′)记为YL。第四步和第五步是α算法的核心。第六步是要得到库所PL。每一个元素(A,B)∈YL都对应着一个库所P(A,B)，这个库所连接了A和B中的变迁，此外，PL还包含一个唯一的源库所iL和一个唯一的汇结库所oL。第七步是要生成工作流网中的弧。TI中的所有变迁都以iL作为输入库所，TO中的所有变迁都以oL作为输出库所。所有P(A,B)都以A作为输入节点，以B作为输出节点。最终得到一个Petri网α(L)=(PL,TL,FL)如图2所示。

图2 α算法挖掘结果

从4个维度来衡量挖掘算法的质量，即拟合度(fitness)、精确度(precision)、泛化度(generalization)和简洁度(simplicity)。拟合度是指得到的过程模型应该允许事件日志所反映的行为发生，一个拟合度良好的模型能够重演日志中大部分轨迹；精确度是指得到的过程模型不应该允许与事件日志中所反映的行为完全无关的行为出现；泛化度是指得到的过程模型应该泛化事件日志中的行为例子；简洁度是指得到的过程模型应该越简单越好。这4个质量标准是相互竞争的，因此在这4个标准间取得平衡是一项挑战。α算法虽然不能很好地满足这4个质量标准，但是α算法是更高级的挖掘方法的基础。

2 过程挖掘技术的现状

1995年COOK J E等人第一次提出了过程挖掘的概念,并且提出了RNet、KTail和Markov三种过程挖掘算法[2-3]，挖掘出的过程模型用有限状态机表示；德国的HERBST J等人[4]提出了三个能够处理重复任务的算法，分别为：MergeSeq、SplitSeq以及SplitPar。荷兰Eindhoven大学教授AALST W V D的团队和国际其他机构及院校合作，取得了一系列的成果[5-8]，在挖掘算法方面，提出了α算法、启发式挖掘算法以及区域挖掘算法等优秀算法；于2004年研发出开源过程挖掘工具ProM，发展到今天ProM已经集成了几百个过程挖掘与分析插件，成为过程挖掘的事实标准。AALST W V D为过程挖掘的研究奠定了理论和实践基础，极大地推动了过程挖掘技术的发展。

国内过程挖掘的研究起步较晚，但也取得了一些显著的成果。清华大学范玉顺教授是国内过程建模领域较早的研究者，针对目前工作流管理系统在描述能力和柔性上存在的严重不足，通过扩展传统活动网络模型，提出了一种基于协调理论和反馈机制的新的过程建模方法[9-10]。清华大学王建民教授在文献[11-13]中指出过程挖掘的研究迅速发展，各种挖掘算法不断出现，但是过程挖掘数据集和过程挖掘算法评判却没有统一标准。为此，王建民教授提出了一种针对不同应用需求选择过程挖掘算法的框架。针对α算法的不足，清华大学的闻立杰进行了扩展和改进[14-15]，提出的α++算法、α#算法以及β算法，突破了非自由选择结构、不可见任务这两大开放性过程挖掘的问题。文献[16-18]中针对现有成批处理工作流调度方法的不足，利用微粒群算法的智能优化原理，提出一种动态分组调度优化模型；为了解决了现有工作流挖掘方法无法挖掘出工作流实例方面模型的问题，通过分析描述了业务过程实际执行情况的事件日志中活动输入输出等数据的特点，提出了一种基于工作流网的工作流实例方面模型挖掘方法。

3 过程挖掘技术的瓶颈与发展方向

过程挖掘作为一个新兴技术领域在当前的研究中存在下面一些困难与挑战：

(1)对于复杂结构和特殊结构的挖掘。虽然启发式挖掘算法能够处理不完备的日志和日志中的噪音，但对于日志中存在的重复或孤立的活动以及特殊循环结构还不能很好地处理。文献[19-20]中基于启发式算法做了一些改进，使之对特殊复杂结构的挖掘能力有一定的提升。

(2)对于挖掘结果的验证困难。通过挖掘算法得到的结果要进行交叉验证，交叉验证的问题之一就是缺少反例，也就是说日志只提供了可能发生的行为，但却没有提供不可能发生的行为。文献[21-22]提供一种可能的解决方案，即插入人工生成的反面事件。

(3)在线过程挖掘(比如提供预测和推荐)。随着云计算和大数据技术的发展以及计算能力的提升，人们对于数据实时性的要求越来越高，所以在线过程挖掘将会是过程挖掘的一个重要发展方向。

[1] AALST W V D. 过程挖掘[M]. 王建民，闻立杰，等，译.北京：清华大学出版社, 2014.

[2] COOK J E, WOLF A L. Automating process discovery through event-data analysis[C]. International Conference on Software Engineering. IEEE, 1995:73-73.

[3] COOK J E. Software process validation: quantitatively measuring the correspondence of a process to a model[J]. Acm Transactions on Software Engineering & Methodology, 1999, 8(2):147-176.

[4] HERBST J, KARAGIANNIS D. Integrating machine learning and workflow management to support acquisition and adaptation of workflow models[J]. Intelligent Systems in Accounting Finance & Management, 1998, 9(2):745-752.

[5] AALST W V D, ADRIANSYAH A, MEDEIROS A K A D, et al. Process mining manifesto[J]. Lecture Notes in Business Information Processing, 2011, 99:169-194.

[6] AALST W M P V D, REIJERS H A, WEIJTERS A J M M, et al. Business process mining: an industrial application[J]. Information Systems, 2007, 32(5):713-732.

[7] AALST W V D. Process mining: discovery, conformance and enhancement of business processes[M]. Springer Publishing Company, Incorporated, 2011: 1018-1019.

[8] AALST W M P V D, SCHONENBERG M H, SONG M. Time prediction based on process mining[J]. Information Systems, 2011, 36(2): 450-475.

[9] 范玉顺. 工作流管理技术基础[M]. 北京：清华大学出版社, 2001.

[10] 罗海滨, 范玉顺,吴澄. 工作流技术综述[J]. 软件学报, 2000, 11(7): 899-907.

[11] Wang Jianmin, WONG R K, Ding Jianwei, et al. Efficient selection of process mining algorithms[J]. IEEE Transactions on Services Computing, 2013, 6(4):484-496.

[12] Wang Jianmin, Jin Tao, WONG R K, et al. Querying business process model repositories: a survey of current approaches and issues[J]. World Wide Web-internet & Web Information Systems, 2014, 17(3):427-454.

[13] Wang Jianmin, Song Shaoxu, Zhu Xiaochen, et al. Efficient recovery of missing events[J]. Proceedings of the VIDB Endowment, 2013, 6(10): 841-852.

[14] 闻立杰. 基于工作流网的过程挖掘算法研究[D]. 北京：清华大学, 2007.

[15] Wen Lijie, AALST W M, Wang Jianmin, et al. Mining process models with non-free-choice constructs[J]. Data Mining & Knowledge Discovery, 2007, 15(2):145-180.

[16] 文一凭. 工作流实例方面的调度与挖掘方法研究[D]. 长沙：中南大学, 2013.

[17] 陈志刚, 文一凭, 康国胜. 成批处理工作流动态分组调度优化方法[J]. 计算机集成制造系统, 2012, 18(8):1693-1699.

[18] 文一凭, 刘洁. 工作流模型挖掘算法及其应用研究[J]. 计算机技术与发展, 2008, 18(7):93-95.

[19] 鲁法明, 曾庆田, 段华,等. 一种并行化的启发式流程挖掘算法[J]. 软件学报, 2015, 26(3):533-549.

[20] 朱锐, 李彤, 莫启,等. 启发式并行化单触发序列挖掘算法[J]. 计算机集成制造系统, 2016, 22(2):330-342.

[21] GOEDERTIER S, MARTENS D, BAESENS B, et al. Process mining as first-order classification learning onlogs with negative events[C]. Business Process Management Workshops, BPM 2007 International Workshops, BPI, BPD, CBP, ProHealth, RefMod, semantics4ws, Brisbane, Australia, September 24, 2007, Revised Selected Papers， 2007:42-53.

[22] GOEDERTIER S, MARTENS D, VANTHIENEN J, et al. Robust process discovery with artificial negative events[J]. Journal of Machine Learning Research, 2009, 10(9):1305-1340.

[23] 石杰. 云计算环境下的数据挖掘应用[J]. 微型机与应用, 2015, 34(5):13-15.

2017 TI杯全国大学生物联网设计竞赛完美收官

2017年9月15日，无锡讯——由教育部高等学校计算机类专业教学指导委员会主办，全球领先模拟和嵌入式处理半导体厂商德州仪器(TI)(NASDAQ: TXN)协办的“2017 TI杯全国大学生物联网设计竞赛”(以下简称“竞赛”)决赛日前于无锡完美收官。

TI杯全国大学生物联网设计竞赛迄今已成功举办四届，旨在以学科竞赛推动专业建设，以物联网行业项目和创新产品激发高校学生的创造力和创业活力，推动创新创业教育的持续开展。

本次竞赛共吸引了来自国内500余所高校的1 500多支代表队、1 700余名指导教师和6 500余名学生的积极报名参赛。经过线上预赛和华东、华中及西南、东北、华北和西北的全国5个分赛区的激烈角逐，共有120支团队入围全国总决赛。最终，来自哈尔滨工业大学的Hit Elites团队凭借“Mr. Piano-远程键盘乐器教学系统”项目脱颖而出，斩获本届TI杯特等奖。

此外，本届大赛增设了线上投票环节，经过紧张激烈的6小时投票与互动，来自深圳大学-小白智能团队的“基于CC3200和DLP技术的智能鱼缸”、南京工业大学-InnoDrive团队的“汽车辅助驾驶系统”以及北京理工大学-503团队的“基于CC3200的声音定位智能婴儿车”三个设计作品荣获本届TI杯最佳人气奖。

万物相连已不是梦想，随着科技脚步日新月异，物联网正以成倍的速度发展中。作为最早进军物联网市场的全球性半导体设计制造公司之一， TI已成为可为物联网应用提供广泛模块芯片的供应商——从节点到网关再到云端，TI提供众多的产品及解决方案，包括微控制器、处理器、有线/无线连接、传感器、信号链和电源管理解决方案等。

TI一直积极参与到物联网工程专业的学科建设中。目前，TI已经在600多所大学中建立了超过3 000个数字信号处理、模拟及微控制器实验室，每年有超过30万名学生通过TI的实验室和各类活动进行实践。在本次物联网设计竞赛中，TI向各参赛队提供了7种物联网设计套件，包括TI CC3200 LaunchPad开发板、CC2650 LaunchPad开发板和CC2650STK套件等。同时，TI还提供了TI Design参考设计、无线技术选型指南、传感器方案、MCU选择参考、电池管理设计参考等丰富的资源，参赛队伍在作品中可使用TI的设计套件，完成创意满分的物联网设计。

在TI的全球战略中，大学计划是极为重要的组成部分。今年是TI大学计划进入中国的第21年，TI仍将不遗余力地在全球范围内推行大学计划，通过这个孕育科学技术人才的摇篮，与自身技术创新发展相结合，培养更多掌握世界先进技术的高级专业人才。

(TI供稿)

Research and application of process mining technology

Deng Lujuan, Dong Dongxiao, Chen Xinxin

(College of Computer and Communication Engineering,Zhengzhou University of Light Industry, Zhengzhou 450002, China)

TP311

A

10.19358/j.issn.1674- 7720.2017.18.004

邓璐娟，董东晓，陈欣欣.过程挖掘技术的研究与应用[J].微型机与应用，2017,36(18)：11-14，17.

2017-02-26)

邓璐娟(1964-)，女，博士，教授，主要研究方向：软件工程、工作流建模。

董东晓(1991-)，男，硕士，主要研究方向：软件工程、工作流建模。

陈欣欣(1993-)，女，硕士，主要研究方向：软件工程。