2015, Vol. 26
2. 南京大学 软件学院, 江苏 南京 210093;
3. 高维信息智能感知与系统教育部重点实验室南京理工大学, 江苏 南京 210094;
4. 南京大学 计算机科学与技术系, 江苏 南京 210046;
5. 杭州电子科技大学 计算机学院, 浙江 杭州 310018
2. School of Software, Nanjing University, Nanjing 210093, China;
3. Key Laboratory of Intelligent Perception and Systems for High-Dimensional Information, Ministry of Education Nanjing University of Science and Technology, Nanjing 210094, China;
4. Department of Computer Science &Technology, Nanjing University, Nanjing 210046, China;
5. School of Computer, Hangzhou Dianzi University, Hangzhou 310018, China
符合性检查(conformance checking)[1, 2]是过程挖掘(process mining)[2, 3, 4]技术研究的重要内容.在符合性检查过程中,将已知的过程模型与已有的系统日志进行对比,用来检查系统日志记载的实际行为与设计的过程行为是否相符.符合性检查是过程模型仓库(process model repository)[5]的重要功能之一,特别是过程模型查询[6]相关的功能.符合性检查方法的输入为一个过程模型和一个系统日志,输出是该模型与日志符合程度的度量结果.现有算法中,过程模型均使用Petri网(Petri-nets)[7]表示,系统日志均为事件日志(Event Log)[8].如果需要检验的系统模型没有使用Petri网表示,则需要转化为Petri网形式;同样,系统日志也需要首先转化为事件日志.例如,在Web Service领域进行符合性检查时,首先将其系统架构(abstract BPEL)转化为Petri网,将其SOAP Message转化为Event Log,再使用符合性检查方法[9].
使用事件日志进行符合性检查时存在误判的情况,例如,当模型中包含大量选择结构时(非Overfitting[10]结构),即使日志是模型本身的日志,也会因为在模拟执行较多任务时会触发当前执行序列外的其他任务,而误判日志与模型的符合性较低.关于使用事件日志进行符合性检查可能存在的问题的描述见第2.3节和第5节.
基于事件日志可能带来的问题,本文提出了一种基于Token Log的符合性检查的方法.Token Log是一种由工作流相关系统产生的、用以记录系统运行情况的新型日志.不同于事件日志,Token Log关注系统中各种资源的生产、流动与消耗情况,并以此记录系统任务间的关系(详见第2.1节).在符合性检查研究中,使用Token Log替代事件日志的优点有(详见第5节):
(1) 全面检查模型结构正确性与日志行为的完整性,使得检查思路更清晰合理;
(2) 化动态模拟执行为静态结构分析,简化检查过程;
(3) 简化根据计算结果判定是否符合的过程;
(4) 可根据输入模型与日志的特点定制度量参数与判定标准.
为了更加详细、清晰地介绍使用Token Log参与过程模型与系统日志符合性检查研究的方法和优点,本文第1节介绍过程挖掘、Petri网、工作流网、事件日志和符合性检查等相关背景知识.第2节说明Token Log的来源与定义,并详细分析Token与结构间的映射关系.第3节详细介绍模型检查与日志检查的方法.第4节描述判定模型与日志符合程度的过程.第5节详细分析使用Token Log的优点.第6节分析使用Token Log对模型增强的作用.相关实验工具、算法和实现过程在第7节介绍.第8节总结全文的工作并提出对未来工作的设想.
1 背景知识 1.1 过程挖掘与符合性检查过程挖掘技术指通过分析信息系统的日志信息,发现、模拟和增强业务过程的技术,其主要包括过程发现(discovery)、符合性检查(conformance checking)和模型增强(enhancement)这3个研究方向[11]:
· 过程发现指通过分析信息系统的日志信息再现原有过程模型;
· 符合性检查指通过某种计算方法,比较过程模型结构与系统日志行为的匹配程度;
· 模型增强指通过分析系统日志发现过程模型实际运行中出现的错误、意外和瓶颈等情况,并针对这些情况对原过程模型作出相应增强修改.
过程挖掘技术还包括其他一些基础的研究方向,如过程模型的存储[12]、过程模型的形式化描述[5]和过程模型相似度检验[13]等.
符合性检查又称合规性检验,是判断过程模型与系统日志符合程度的过程挖掘技术.文献[1]提出了过程模型与系统日志的匹配程度需要通过Fitness和Appropriateness两种指标衡量,其含义如下:
(1) Fitness用以衡量日志记录的系统行为可被过程模型再现的程度;
(2) Appropriateness用以衡量过程模型再现日志行为时的准确程度与模型本身的简洁程度.
Fitness与Appropriateness通过分析过程模型模拟执行日志时的状态变化算得:
· 计算Fitness时,需要统计每个任务执行时,消耗令牌、新产生令牌、未使用令牌和缺失令牌的数目;
· 计算Appropriateness时,需要统计每个任务执行时,所有可能被触发的任务数目.
符合性检查过程中对两种指标的分析与统计,不仅是为了判断过程模型与日志的匹配程度,同时也为增强过程模型提供了潜在的途径.
1.2 建模工具Petri网与工作流网Petri网是一种常用于描述并发过程模型的建模工具,例如,文献[14,15,16]均使用Petri网为过程模型建模.图 1是使用Petri网表示的医院门诊管理系统的简化过程模型.本文使用该例子是为了说明本文描述的检查方法适用于包含各种特殊结构的模型.
 | Fig. 1 Simplified process model of hospital for outpatient图 1 医院门诊流程简化模型 |
Petri网是由变迁(transition)、库所(place)及其之间弧线(arc)组成的动态模型系统.本文Petri网使用表达式PN=(P,T,F)表示,P是库所集合,T是变迁集合,F是弧线集合.更多关于Petri网的介绍见文献[17].图 1的Petri网中存在一些特殊的结构:
· 变迁B和变迁I组成了一个循环结构,而变迁J自身形成一个循环结构;
· 变迁F是一个非自由的选择结构,即:如果F由变迁D触发,则变迁G被执行;如果F由K触发,则变迁L被选择执行.图 1同时是一个合理的(sound)工作流网(workflow net,简称WF-net)[18].工作流网是给工作流过程模型建模的Petri网子类.
一个Petri网可以称为一个工作流网,必须满足:
(1) 有唯一的开始库所;
(2) 有唯一的结束库所;
(3) 每一个节点都必须在某一个从开始库所到结束库所的路径上.
而一个工作流网被称为一个合理的工作流网,必须满足:
(1) 所有任务都可以潜在被执行(所有任务都在某一个可以执行的路径上),即,活性(live);
(2) 每次从开始库所填入一个令牌开始执行,以结束库所中遗留一个令牌结束执行,即,有界性(bounded).
工作流网的合理性要求过程模型执行时既没有死锁(dead lock)也没有活锁(live lock).本文使用的所有过程模型均为合理的工作流网.
1.3 事件日志系统日志是过程挖掘研究的起点,目前,所有被使用的系统日志均为事件日志(event log).事件日志由事件组成,并满足3个假设条件:
(1) 每个事件(event)关联一个任务(task);
(2) 每个事件关联一个运行实例(case)[8]的ID;
(3) 所有事件按照执行的先后顺序排列.
在过程挖掘相关研究中,首先从事件日志中获取每个运行实例的任务串(task trace).例如,表 1是图 1某事件日志的实例任务串(最后一列为实例出现的次数,即case numbers).
|
Table 1 An example of event log of the process model in Fig. 1 表 1 所示过程模型的事件日志实例列表 |
表 1共有7个运行实例,每个实例出现的频率不同,且列出的运行实例并不包含过程模型执行时所有可能的任务序列.最后一列(case numbers)被用来计算实例占整个日志的权重,每个实例按此权值参与计算日志整体与过程模型的符合性.
2 新型日志Token Log本节主要介绍本文所使用的Token Log的相关内容.首先阐述Token的含义,介绍Token Log的内容,并说明如何产生Token Log;然后阐述使用Token Log替换事件日志的核心动机;最后详细说明Token Log的特性.
2.1Token的含义及内容文献[19]描述了一种Artifact-Centric工作流过程模型,它以某种实际存在的(concrete)、编号的(identifiable)和自描述的(self-describing)信息块为中心,如业务实体(business entity)和业务记录(business record),这些一直存在于模型中的信息块被称为Artifact.文献[20]中有关于Artifac-Centric工作流过程模型的实例与应用描述.在Artifact-Centric过程模型中,根据Artifact状态与内容的改变,可推理出各个任务间的执行关系.但多数工作流中并不存在完整生命周期定义的Artifact实体,难以通过该实体的状态与内容的改变推理出任务间关系.一般工作流过程模型中,每两个存在依赖关系的任务间会存在资源和执行权限等信息的流动,这些信息就是任务执行的前置与后置条件.将这些信息看作更细粒度的类似Artifact的实体,通过记录这些实体便可获得任务间的依赖关系.在Petri网中,令牌被用来代表任务的前置与后置条件,借鉴此概念,本文使用令牌(token)代表工作流过程中两个任务间流动的信息,并通过记录这些信息的生产者与使用者获取任务间的关系.Token的详细描述如下:
oken代表任务间流动的信息,不同Token代表不同种类的信息.Token由一个任务生产并传递给另一个任务.产生Token的任务称为生产任务(produce task,简称PT),接收Token的任务称为消费任务(consume task,简称CT).每一个Token都记录了自己的生产任务与消费任务.
一个任务执行后可能产生多个Token;同样,一个任务执行时可能需要多个输入Token.为便于区分这些同时被消费与同时被生产的Token,为每个Token标记生产与消费时间.Token的生产时间与消费时间即为生产任务与消费任务的执行时间,使用执行ID(execute ID,简称EID)标记,定义如下:
定义1(执行ID). 执行ID(execute ID,简称EID)是每个运行实例中,每个任务执行时分配的唯一执行标记.
不同实例中的任务执行可能会有相同的EID.Token Log中也包含过程执行的不同实例(case),使用Case ID (CID)标记.每一个任务的每一次执行都可以通过组合(CID,EID)唯一确定.表 2是图 1过程模型最终可以参与计算的Token Log示例(添加EID),有两个执行实例,对应于表 1中的Case 4,Case 5和Case 6.在事件日志中两个用于表示并发结构的不同实例(Case 5和Case 6)在Token Log中被相同的Token内容表示.表 1中的Case 1与Case 2在Token Log中也是这样.这说明,使用Token Log替代事件日志将减少参与计算的实例数目.
|
|
Table 2 Example of Token Logs for Case 4, Case 5 and Case 6 shown in Table 1表 2 表 1中图 1结构的Case 4,Case 5和Case 6的对应Token Log示例 |
根据上述Token含义,不仅在YAWL(yet another workflow language)[21]工作流引擎上实现打印Token Log,还在Petri网建模工具PIPE上开发了模拟执行工作流模型,并产生Token Log的插件.
在YAWL引擎中,YIdentifier作为标记业务过程状态的实体在工作流网中流动,作用类似于Petri网中的令牌[22];YCondition作为存放YIdentifier的容器,作用类似于Petri网中的库所[22].任务(YTask)执行前需要判断其输入YCondition中是否包含足够的YIdentifier;任务执行时需要删除对应输入YCondition中对应的YIdentifier;任务执行完毕需要向输出YCondition中填入对应的YIdentifier.实验中,首先在源代码中修改YIdentifier定义,添加生产任务与消费任务属性.任务执行时,设定输入YIdentifier的消费任务,并打印YIdentifier信息;任务执行后,设定输出YIdentifier的生产任务.但由打印结果发现:YIdentifier在工作流网中为引用传递,YCondition中只持有YIdentifier的引用.任务改变某个YIdentifier属性时,会对所有持有该YIdentifier引用的YCondition产生影响.
最终,实验选择在YAWL中添加新Token对象:
· 任务执行完时新建Token并设定生产任务,然后传递给输出YCondition;
· 任务执行开始时设定输入Token的消费任务并打印Token信息,随即回收该Token.
实验中,使用YAWL引擎生成Token Log的核心时序图如图 2所示(YEngine是管理所有运行过程实例的对象,YNetRunner是独立执行一个过程实例的对象).
 | Fig. 2 Process of making Token Log in YAWL图 2 YAWL引擎中打印Token Log原理图 |
其中,方法consume(×),print(×)和produce(×)为添加的核心方法:
· consume(×)主要工作为获取任务输入库所中的Token并设定当前任务为消费任务;
· print(×)主要工作为打印所有消费的Token信息生成Token Log;
· produce(×)主要工作为新建Token并输入到输出库所中.
本文描述的研究工作中,同时完成了在Petri网建模工具PIPE中开发模拟执行工作流过程模型并产生Token Log的插件,并在本文实验过程中使用了该插件生成的Token Log.该插件的执行原理与YAWL中生成Token Log的原理相同.
关于该插件的详细介绍与使用说明见第7.1节.
2.3 使用Token Log的动机除误判情况外,在符合性检查中使用事件日志,更难以避免过程模型Overfitting与Underfitting时对检查结果的干扰[10].过程模型Overfitting指过程模型可以生成参与检查的事件日志之外的很多其他日志内容,过程模型Underfitting指过程模型通过包含重复任务恰好能够生成参与比较的事件日志的内容[4].图 3展示了与表 1中Event Log对应的Overfitting与部分Underfitting过程模型.
 | Fig. 3 Overfitting and Underfitting processes of the log shown in Table 1[1]图 3 表 1事件日志的Overfitting与Underfitting模型[1] |
使用事件日志进行符合性检查会受到Overfitting与Underfitting结构影响的原因是:没有直接检查日志对模型所有可能产生的执行路径的覆盖程度,而是通过统计可能触发多少非可执行路径进行间接检查.然而,本文提出了直接统计日志内容是否覆盖过程模型所有可能执行路径(即,日志完整性)的方法.但如果直接描述过程模型允许的所有可能执行路径,则会出现状态空间爆炸.因此,本文通过统计模型中特殊结构结点允许的所有行为是否被日志内容覆盖,以判断整个模型是否被覆盖.由于使用事件日志难以描述过程模型中的特殊结构,所以本文选择使用可以唯一确定过程模型特殊结构结点的Token Log.使用Token Log进行符合性检查的主要工作包括:
(1) 基于日志内容判断过程模型结构的正确性(详见第3.1节);
(2) 基于过程模型结构判断Token Log内容的完整性(详见第3.2节).
在使用Token Log时,不再需要动态模拟执行过程模型,而只要根据Token间匹配关系与模型特征结构的对应关系(详见第2.3节),静态分析并计算日志与模型的符合程度,即使用Token Log将简化检查过程.新的检验方法将通过唯一的计算结果判断匹配程度,且可以根据日志与模型的实际情况自定义相关计算参量及判断标准.使用Token Log的优点详见第5节.
2.4Token与结构的映射关系使用Token Log优化符合性检查的基础是,一组特定关系的Token与过程模型特征结构之间的映射关系.本节首先介绍过程模型特征结构与Token间匹配关系,然后给出Token匹配关系与特征结构间的映射关系.
2.4.1 过程模型的特征结构任何复杂的工作流过程模型均有几种简单的局部结构[7]组成.这些简单的局部结构包括:
(1) 顺序结构,如图 4(a)和图 4(b)所示;
 | Fig. 4 Substructures in process models图 4 过程模型中的局部结构 |
(3) 选择(or-split)和或同步(or-join):库所有多个输出和库所有多个输入,如图 4(f)和图 4(g)所示;
(4) 单步循环(one loop)[8]:一个任务即是一个库所的输入也是该库所的输出,如图 4(h)所示;
(5) 特殊的隐式库所(Implicit place)[8]:两个任务由多个库所直接连接,如图 4(c)所示.
这些简单的局部结构在本文提出的符合性检查中作为过程模型的特征结构,用于判断Token Log是否覆盖这些特征结构允许的所有行为.
2.4.2 Token间匹配关系在第2.1节中提到,最终参与计算的Token Log中所有内容相同的运行实例都会被归并,并统计其出现次数,所以Token中的Case ID信息指代了一类运行实例.Token的完整定义如下:
定义2(Token). Token是Token Log中的条目,使用5元组token=(CID,PT,CT,PEID,CEID)表示,其中,CID表示Token所在实例的Case ID,PT和CT分别表示Token的生产任务和消费任务,PEID和CEID分别表示生产任务与消费任务在生产与消费Token时的EID.
本文Token之间的关系被称为匹配(match)关系.由Token定义可知,Token t1=(CID1,PT1,CT1,PEID1,CEID1)由CT1在CEID1执行中被消耗,而CT1在此执行之后必然生产另一个Token t2=(CID1,PT2,CT2,PEID2,CEID2),其中,PT2=CT1且PEID2=CEID1.此时,t1和t2被称为顺序匹配(sequential match).但是,有一类特殊的Token,它们由同一个任务生产和消费,但是在两次不同的执行中.这一类Token将不与其他Token进行关系匹配,即:在发现匹配关系时,发现这些特殊Token的优先级更高.这一类Token称为单步循环标记(one loop marking):
定义3(单步循环标记). Token t=(CID,PT,CT,PEID,CEID)是一个单步循环标记当且仅当PT=CT.所有的单步循环标记Token组成的集合为OLM={(CID,PT,CT,PEID,CEID)|PT=CT}.
类似顺序匹配关系,Token间还有其他各种匹配关系.在定义匹配关系时,首先排除单步循环标记的Token.所有匹配关系的定义如下:
定义4(顺序匹配). Token t1=(CID1,PT1,CT1,PEID1,CEID1)与t2=(CID1,PT2,CT2,PEID2, CEID2)称为顺序匹配关系当且仅当:t1ÏOLM,t2ÏOLM,CID1=CID2,CT1=PT2,CEID1=PEID2.
定义5(并发匹配,and-split match). Token t1=(CID1,PT1,CT1,PEID1,CEID1)与t2=(CID1,PT2,CT2,PEID2, CEID2)称为并发匹配关系当且仅当:t1ÏOLM,t2ÏOLM,CID1=CID2,PT1=PT2,PEID1=PEID2.
定义6(同步匹配,and-join match). Token t1=(CID1,PT1,CT1,PEID1,CEID1)与t2=(CID1,PT2,CT2,PEID2, CEID2)称为同步匹配关系当且仅当:t1ÏOLM,t2ÏOLM,CID1=CID2,CT1=CT2,CEID1=CEID2.
定义7(多路匹配,multi-path match). Token t1=(CID1,PT1,CT1,PEID1,CEID1)与t2=(CID1,PT2,CT2,PEID2, CEID2)称为多路匹配关系当且仅当:
t1ÏOLM,t2ÏOLM,CID1=CID2,PT1=PT2,PEID1=PEID2,CT1=CT2,CEID1=CEID2.
如果两个Token只是在同一个运行实例中而没有任务执行ID相同,即相同的执行任务必定在同一个运行实例中执行了多次,这个结构中存在循环结构,因此,Token间的这种关系称为循环匹配,具体定义如下:
定义8(循环匹配,loop match). Token t1=(CID1,PT1,CT1,PEID1,CEID1)与t2=(CID1,PT2,CT2,PEID2,CEID2)称为循环匹配当且仅当:CID1=CID2,PEID1¹PEID2,CEID1¹CEID2,且满足以下任意条件:
(1) PT1=PT2,CT1=CT2;
(2) PT1¹PT2,CT1=CT2;
(3) PT1=PT2,CT1¹CT2.
2.4.3 Token匹配关系与特征结构间的映射首先通过Token间的匹配关系定义可知:只有部分匹配关系可以唯一确定某些特征结构,其他关系则可能与多种特征结构对应.表 3给出了映射关系f(Token匹配关系®特征结构),其中,特征结构为图 4中的结构.
|
|
Table 3 Mapping from matches between Tokens to substructures shown in Fig. 4 表 3 Token匹配关系到特征结构(图 4)的映射关系 |
从特征结构到Token间匹配关系的映射指:当过程模型中存在某种特征结构时,其对应的完整Token Log必定包含满足哪种匹配关系的Token.例如,当过程模型结构中有单步循环时(如图 4(h)所示),Token Log中肯定包含Token t满足t是一个单步循环标记.在根据特征结构确定Token间的匹配关系时,主要确定特征结构库所中填入的Token间匹配关系.表 4给出了完整的映射关系f(特征结构®Token匹配关系)及各条件的编号(便于下文引用).
|
|
Table 4 Mapping from substructures in models to matches between Tokens 表 4 特征结构到Token匹配关系的映射 |
使用Token Log的符合性检查方法分为两个部分:使用日志内容检查模型结构的正确性;使用模型特征结构检查日志内容的完整性.第3.1节主要介绍衡量模型结构正确性的方法,第3.2节详细介绍衡量日志内容完整性的方法.
3.1 检查模型结构的正确性模型结构的正确性通过将日志Token正确填入模型的程度衡量,此处过程模型与Token的关系分为能够填入与不能填入:能够填入指Token在日志中拥有的所有匹配关系都能够正确填入过程模型;不能填入指Token拥有的匹配关系中存在不能正确填入模型的部分.为了判断过程模型是否可以正确填入Token,首先需要将日志中的所有Token间的匹配关系找到,这些关系包括表 3中的所有匹配关系.例如,表 5是一个可能是图 1对应Token Log中实例的Token列表.
|
|
Table 5 A running case in the token log of the process in Fig. 1 表 5 图 1对应Token Log中的一个运行实例 |
表 6展示了表 5中Token间所有匹配关系,其中没有多路匹配关系和循环匹配关系.
|
|
Table 6 Matches between tokens in Table 5 表 6 表 5中Token间的匹配关系 |
过程模型正确填入单个匹配关系的程度使用变量dap(degree of accepting pair)表示,且dapÎ[0, 1],即,dap的取值不是非0即1.如图 5中,将顺序匹配关系(t6,t8)填入模型时,t6不能填入而t8能够填入,则可以将该关系的dap值设为0.5或其他界于0,1之间的某个数.在确定单个匹配关系的dap值时,可以根据对结果精确程度的要求标记匹配关系被正确填入的程度.根据每一个匹配关系的dap值,可以确定整个实例正确填入过程模型的程度,该值称为dac(degree of accepting case),计算方法如下:
 | Fig. 5 Result of putting tokens in Table 6 into the model in Fig. 1图 5 表 6匹配关系填入图 1模型中的结果 |
公式1. 令l是日志中的匹配关系种类,mi是日志中某一实例中某种匹配关系的个数,wiÎ(0,1)是这种匹配关系在符合性检查中的重要程度,dac表示该实例正确填入过程模型的程度,则:
$dac = \sum\limits_{i = 0}^l {\left( {{w_i} \times \frac{{\sum\limits_{j = 0}^{{m_i}} {da{p_j}} }}{{{m_i}}}} \right)} ,,\sum\limits_{i = 0}^l {{w_i}} = 1.$
衡量匹配关系正确填入的程度时,不同匹配关系的标准不同.例如,并发匹配关系没有顺序匹配关系不被填入时,对整个实例影响比较大(如果顺序匹配不被填入,则可能是整个运行序列存在问题).所以在衡量dac时,使用wi表示每一种匹配关系的重要程度,为方便计算,令wiÎ(0,1).每一个运行实例的dac值决定了整个日志能够正确填入过程模型的程度,使用dal(degree of accepting log)表示,其计算方法如下.
公式2. 令n是日志中的实例个数,ck是每个实例在整个日志中出现的次数,dack是每个实例正确填入过程模型的程度,dal表示整个日志能够正确填入过程模型的程度,则:
$dal = \frac{{\sum\limits_{k = 0}^n {({c_k} \times da{c_k})} }}{{\sum\limits_{k = 0}^n {{c_k}} }}.$
dal表示所有匹配关系能正确填入过程模型的平均程度,每一个匹配关系都按照其重要程度参与计算.最终,dalÎ[0, 1],0表示所有的匹配关系都不能正确填入过程模型,1表示所有的匹配关系都能够正确填入.例如,将表 6中的匹配关系填入图 1模型中得到结果如图 5所示.
如图 6所示:假设每个匹配关系中有一个Token可填入则其dap是0.5,两个都填入dap是1,且w单步循环标记=0.1,w顺序匹配=0.5,w并发匹配=0.2,w同步匹配=0.2,则dac=0.8107.dac=0.8107表示这个运行实例中每个匹配关系平均有81.07%的内容能够被正确填入过程模型.此处计算的只是一个运行实例,而不是整个日志.假设日志中还包含表 2中CID=4的运行实例(dac=1 )且出现10次,则最终dal=(0.8107x100+1x10)/(100+10)=0.8279.
 | Fig. 6 Example model containing all typical substructures图 6 包含各种特征结构的过程模型实例 |
如第2.3节所说,计算日志覆盖过程模型特征结构的能力是为了避免Overfitting,Underfitting及其类似结构对判断的误导,但其前提是已经通过过程模型对于日志的行为正确性初步判断日志与模型可能匹配.
日志内容的完整性通过日志中Token匹配关系是否能满足过程模型中每个特征结构的要求衡量.匹配关系满足特征结构要求指,匹配关系中包含了这个特征结构可能产生的所有匹配关系.本文讨论的过程模型中特征结构及其对匹配关系的要求见表 4.
3.2.1 识别过程模型特征结构获取过程模型的特征结构,关键在于获取这些结构中的库所.循环节点中就包含了单步循环库所、多步循环起始与结束库所和循环中在主路径[23]上的非起始、结束库所.以图 6为例,P6是单步循环库所,P1和P3为多步循环的起始与结束库所,P2是循环路径在主路径上的普通库所.
在符合性检查中,需要让计算机通过计算获取这些库所信息.本文根据Petri网中T-不变量(T-Invariant),S-不变量(S-Invariant)[7]理论对过程模型进行分解,获取特征结构的库所.T-不变量,S-不变量的定义如下:
定义9(关联矩阵、T-不变量、S-不变量)[23]:
(1) 所有Petri-net PN=(P,T,F)均可以表示为一个集合P与集合T基于集合F的关联矩阵A;
(2) T-不变量是方程A×X=0的整数解,其解的本质是模型中所有保持点火变迁数目稳定的循环点火序列,其中,非0标记的变迁表示在点火序列中;
(3) S-不变量是方程AT×X=0的整数解,其解的本质是模型中所有保持Token数目稳定的循环点火序列,其中,非0标记的库所表示在点火序列中;
(4) T-不变量有解当且仅当过程模型是合理的,S-不变量有解当且仅当过程模型是有界的.
本文使用的过程模型均为合理WF-Net,因此,T-不变量、S-不变量一定有解.T-不变量结果拆分所有的选择结构;S-不变量结果拆分所有并发结构.为拆分模型中所有选择与并发结构,在开始库所与结束库所上添加变迁Q形成循环结构.例如,在计算图 6不变量时,首先添加任务Q使得整个模型成为一个大的循环结构,如图 7所示.
 | Fig. 7 Circular model of Fig. 6 after adding Q图 7 图 6结构添加任务Q形成整体循环结构 |
T-不变量、S-不变量方程的解都不唯一,但其有一组由0,1组成的最小半正解,即文献[24]中提出的LMST-不变量(legal minimal semi-positive T-invariant).图 7模型最终的T-不变量、S-不变量的最小半正解见表 7、表 8.
|
|
Table 7 Legal minimal semi-positive T-invariant of the model in Fig. 7 表 7 图 7模型T-不变量最小半正解 |
|
|
Table 8 Legal minimal semi-positive S-invariant of the model in Fig. 7 表 8 图 7模型S-不变量最小半正解 |
根据表 7可以获得循环和选择结构,具体识别过程如下(“条件”指表 4中条件):
(1) 根据不包含Q的解确定内部循环,包括{G}和{B,C,E,F},可确定单步循环库所P6,需要满足条件10;
(2) 根据包含Q的解确定主路径{A,B,C,D,J,K,L,M}和{A,B,J,K,L,M,H,I},根据多步循环与主路径的交叉任务B和C,确定循环结点库所P1和P3,分别满足条件6和条件8.并确定循环主路径库所P2,满足条件1;
(3) 根据两条主路径确定选择分支{C,D}和{H,I},并确定选择库所P2和P6,分别满足条件7和条件9.
在表 8结果中,标记为0的所有库所都是在某些点火路径上不被使用的.根据S-不变量定义可知:它们是并发或同步结构中的库所,并可根据原过程模型确定其具体类别,过程如下:
(1) 确定所有标记为0的库所,它们是可能处于同一个并发结构的库所组合,将这样的组合构成的集合称为潜在并发库所组合集(set of potential parallel places’ combination,简称PC):
$PC = \left\{ {\left\{ {{P_9},{P_{10}},{P_{11}}} \right\},\left\{ {{P_9},{P_{10}},{P_4}} \right\},\left\{ {{P_7},{P_8},{P_4}} \right\},\left\{ {{P_7},{P_8},{P_{11}}} \right\}} \right\}.$
定义10(潜在并发库所组合集). 令合理WF-net PN= (P,T,F)的初始与结束库所分别为i,o,任务Q以o为输入、以i为输出,集合PC={PC1,PC2,…,PCn}称为PN的潜在并发库所组合集当且仅当:PCiÎPC且PCi为PN¢=(P,TÈ{Q},FÈ{(o,Q),(Q,i)})的S-不变量最小半正解的某个解中所有标记为0的库所组合.
定义11(并发分支库所集,set of places in parallel branch,简称PPB). 令PN=(P,T,F)是一个合理WF-net,PN中一个并发结构的分支中所有的库所组成的集合称为PN的一个并发分支库所集,缩写为PPB.
定理1. 令PC={PC1,PC2,…,PCn}是PN=(P,T,F)的潜在并发库所组合集,且"pÎP¢={P1,P2,…,Pn}满足pÎP.令PiÎP¢,PCjÎPC,若:(PiÎPCjÙ"PkÎP(k¹i)ÞPkÎPCj)Ù(PiÏPCjÙ"PkÎP(k¹i)ÞPkÏPCj),则P¢可能是PN的一个PPB.如果原模型中包含一个包含且仅包含P¢中所有元素的顺序结构,则P¢是一个PPB.
证明:在定理中,PiÎPCjÙ"PkÎP(k¹i)ÞPkÎPCj指:如果Pi在某一个潜在并发库所组合中,则P¢中其他元素都一定在这个组合中.PiÏPCjÙ"PkÎP(k¹i)ÞPkÏPCj指:如果Pi不在某个组合中,则P¢中其他任意的元素都不在这个组合中.潜在并发库所组合就是:所有可能在同一个并发分支上的所有库所,但是可能由多个并发结构的并发分支组成,但是每一个并发分支的所有库所都作为一个整体存在,作为一个整体存在于潜在并发库所组合中的、还有共享并发分支的多个并发结构中非共享并发分支的其他所有并发分支的库所组合.例如,图 1中从p< span lang="EN-US" xml:lang="EN-US">3到p9的结构为两个共享并发分支的并发结构,其S-不变量中包含两个解:{p4,p6,p8}和{p5,p7},其中,{p4,p6,p8}是多个并发分支非共享分支的组合.此时,P¢={p4,p6,p8}就不是PPB,即原模型中不存在包含且仅包含{p4,p6,p8}的顺序结构. & nbsp; □
定理2. 令集合P与P¢是合理WF-net PN的两个PPB,则P与P¢属于PN的同一个并发结构当且仅当:
"PCjÎPC,若$PiÎPÙPiÎPCjÞóPkÎPCjÙPkÎP¢.
证明:条件$PiÎPÙPiÎPCjÞóPkÎPCjÙPkÎP¢指:PPB P与P¢不能同时出现在一个潜在并发库所组合中.根
据潜在并发库所组合(即S-不变量)的定义可知:两个PPB出现在同一个潜在并发库所组合中,则必然不是同一个并发结构中的不同分支;同时,如果两个PPB不属于同一个并发结构,则一定会同时出现在某个潜在并发库所组合中.因此,根据前两个结论可知,如果两个PPB总是不出现在同一个潜在并发库所组合中,则必定是同一个并发结构的不同分支.&nb sp; □
(2) 根据定理1,从上述PC中获取的并发分支库所集有{P9,P10},{P7,P8},{P4}和{P11};根据定理2,属于同一个并发结构的并发分支库所集组合为{P9,P10}与{P7,P8},{P4}与{P11}.
(3) 最后在并发分支的库所中,根据原过程模型找到所有的并发(P7,P9)和同步(P8,P10)库所对,它们应满足条件4和条件5.其中,只包含一个库所的并发分支库所集均为特殊隐式库索(P4,P11),它们应满足条件3.
(4) 模型中其他没有在上述库所中且不是开始与结束库所的库所,均为主路径上普通库所,其满足条件2.
3.2.2 度量日志覆盖能力使用日志平均覆盖特征结构行为的能力衡量日志完整性.特征结构中,库所被体现的程度使用dcp(degree of covering place)表示,dcpÎ[0, 1].例如,日志需要满足的条件只能达到一半,则令dcp=0.5.根据每个库所的dcp值确定该类特征结构中所有库所被体现的平均程度.每种特征结构的重要程度不同,使用w表示其权重,wÎ[0, 1]. dcm定义如下:
公式3(degree of covering model). 令PN是合理WF-net,TL是Token Log,PN有n种特征结构,mi是每种特征结构中对应库所或库所对的个数,wi是每种特征结构对符合性检查的重要程度,dcp是每种结构中每种库所被TL体现的程度,则TL体现PN的程度dcm为
$dcm = \sum\limits_{i = 0}^n {\left( {{w_i} \times \frac{{\sum\limits_{j = 0}^{{m_i}} {dc{p_j}} }}{{{m_i}}}} \right)} ,其中,\sum\limits_{i = 0}^n {{w_i}} = 1.$
例如,计算表 5实例对图 1模型覆盖程度时(假设表 5内容即为Token Log的内容),首先要通过第3.2.1节的方法获取所有特征结构中的库所,结果见表 9.
|
|
Table 9 Places of special substructures of the model shown in Fig. 1 表 9 图 1模型中特征结构对应的特殊库所统计 |
由表 9可知,该计算中非循环的选择结构与并发结构对判断结果更为重要.在计算dcm前,首先将所有Token关联到对应的库所中(如图 8所示),再进行计算.
根据填入库所中的Token判断日志是否满足库所的要求并确定其dcp:
(1) p3中t5是单步循环标记,满足条件,dcp=1;
(2) p2只有t2,不满足条件,dcp=0;p1中只有t1,同样不满足条件,dcp=0;
(3) p3只包含t4,dcp=0.5;p7只包含t11,dcp=0.5;p5与p9也是dcp=0.5;
(4) (p4,p5)与(p6,p7)中都包含了匹配的Token,dcp=1;(p5,p8)与(p7,p8)的p8没有Token,不满足要求,dcp=0.
 | Fig. 8 Result of putting tokens in Table 5 into the model in Fig. 1图 8 将表 5中Token填入图 1模型中 |
确定各种特征结构的平均dcp后,算得dcm=0.5,表示日志能够平均覆盖模型中每种特征结构的一半行为,日志很不完整.但表 5的日志仅含一个实例,若添加表 2的CID=4的实例,则过程中被执行的路径将如图 9所示.
 | Fig. 9 Running paths of Fig. 1 after adding the case CID=4 of Table 2 into the log in Table 5图 9 表 5日志中添加表 2中CID=4的实例后,图 1模型的运行路径 |
此时,除了循环结构的平均dcp为0,其他均为1,所以dcm=0.9.如果再添加表 2中CID=5的实例,则模型中所有路径都会被标记执行,即库所中包含满足所有条件的Token,其dcm=1.该结果表示日志包含了所有模型能够生成的日志内容.
如果模型是Overfitting结构,则日志覆盖其允许行为的程度会很低,因此可以判定符合性较低.但如果模型是Underfitting结构,此时日志恰好包含其能够覆盖其行为(dcm=1),且模型能够生成所有日志内容(dal=1).此时,该如何排除对Underfitting结构的误判呢?排除对Underfitting结构误判的关键在于计算T-不变量、S-不变量时,计算的并不是Underfitting结构的本身,而是实际录入的模型.如果结构是Underfitting结构,则会包含很多重复的任务,如图 3中的N3.但是在本文的方法中,录入变迁与库所的关联矩阵时,不会区分重复的任务,即所有重复任务都最终对应一个任务,如图 3中的N3录入的是图 10中的结构.
 | Fig. 10 Model the checking method recognized by reading N3 in Fig. 3图 10 图 3中N3实际录入的关联矩阵对应的模型,即去除重复任务的结构 |
通过去除重复任务的关联矩阵计算出的S-不变量将表明:模型中包含很多的特殊隐式库所结构,则要求日志中包含满足这些隐式库所要求的Token匹配关系.但日志中并没有这些Token匹配关系,则最终的dcm会比较低,由此排除对Underfitting结构的误判.
4 综合dal与dcm判断符合性dal表示过程模型能够生成日志内容的能力,dcm表示日志覆盖模型所有允许行为的能力.过程模型与日志匹配的充分必要条件为:(1) 模型要能够正确填入日志中的所有内容(dal=1);(2) 日志要包含模型能够生成的所有内容(dcm=1).
(1) 仅有dal(模型正确性)是不够的.过程模型如果与日志内容不匹配,则可能只能正确填入日志中很少的内容,或者是可以正确填入日志中所有的内容,但同时还可以填入很多日志中没有的内容(即 Overfitting结构).因此,dal值大于标准值,只是模型与日志匹配的必要条件而不是充分条件;
(2) 仅有dcm(日志完整性)是不够的.日志与模型不匹配,则可能日志中包含的模型能够生成的日志内容很少,或者日志包含了所有模型能够生成的日志内容,但是同时包含了很多模型不能生成的日志内容.因此,dcm值大于标准值,只是日志匹配模型的必要条件而不是充分条件.
但即使模型能够生成日志所有内容,日志也恰好包含模型能够生成的所有内容,如果模型是Underfitting结构,也会影响对符合性的判断.由于合理的工作流网中有重复的任务,因此,本文在计算dcm时删除模型中所有的重复任务(具体解释见第3.2.2节)以排除Underfitting结构对判断的影响.
理论上,只有当dal=1且dcm=1时才判定过程模型与日志完全匹配.但实际比较过程中,由于某些因素,即使是完全匹配,其dal和dcm也达不到1.表 10列出了这些影响因素.
|
|
Table 10 Factors of the model and log affecting their match and their impacts 表 10 模型与日志中影响完全匹配的因素及其表现 |
日志不完整指参与检查的日志不是某过程模型的完整日志,没有包含所有运行实例或者某些运行实例中有内容缺失.因为内容缺失,日志对模型特征结构行为的覆盖程度也会降低,即dcm降低.日志不纯净指日志中包含了其他过程模型中的运行实例或某些运行实例中包含错误的任务信息,导致模型不能完全正确填入日志内容,即dal降低.模型中存在隐藏任务指,这些任务在日志中会被记录,但是在模型中没有体现,这样会产生日志不纯净的效果,即dal降低.不可见任务指存在于模型中却没有被日志记录下的任务,这样的任务会导致日志无法覆盖模型的所有特征结构的行为,从而降低dcm值.在计算dcm时,为了排除Underfitting结构的影响,将模型中所有的重复任务看作是同一个任务,所以如果模型中真实存在重复任务而又不是Underfitting结构,则会导致日志无法完全覆盖模型特征结构,即dcm被降低.
根据dcm的影响因素确定其能容忍的最小值,根据dal的影响因素确定其能容忍的最小值.这些影响因素与日志和模型的具体情况密切相关,不同的日志与模型受这些因素的影响程度不同,最终确定dal与dcm需要参考具体的日志与模型.
5 使用Token Log的优点分析第1.1节简单介绍了基于事件日志的符合性检查方法,该方法存在误判的情况.例如:过程中有较多选择结构时,与其对应的日志进行符合性检查时会产生如下情况:(1) 模拟执行时,所有任务序列均可被再现,即Fitness达到最大;(2) 选择结构的输入任务执行后,接着只能执行一个选择分支,则必然有当前执行的任务序列外的其他任务处于可能被触发状态;又由于该结构中的选择结构较多,则所有任务串中平均可能被触发的其他任务会比较多,即Appropriateness较低;(3) 预测结果应该是该模型与日志完全符合,但最终结果会受到Appropriateness的影响,产生误判情况;或者 ,使用由多个并发结构组成的模型与只包含顺序结构的事件日志(二者有相同的任务集合)进行检查时,会有如下情况:(1) 在模拟执行每一个任务序列时,都会有极少数的并发结构的任务无法执行,但是多数任务都能够顺利执行,即Fitness值会接近最大值;(2) 执行所有非并发结构任务时都不会触发该任务序列以外的其他任务,即Appropriateness值也会接近最大值;(3) 根据前两者判断,该模型与日志有较高的符合性,但实际上该模型与日志的结构存在巨大差异,不可能有较高的符合性.
结合误判问题及第2.3节介绍的使用Token Log的动机,本节将详细介绍引言中提出的在符合性检查中使用Token Log的4个优点.
5.1 全面的检查方案在符合性检查中,日志代表了模型实际运行的行为,而模型代表了产生日志行为的原结构.图 11表示了使用两种日志进行符合性检查的不同过程.实线代表使用Token Log,虚线代表使用事件日志.使用事件日志进行检查时,以日志行为为基础判断日志对结构描述的完整性,将判断的依据局限在已有日志行为中.如果参与检查的日志不会导致模型产生非当前任务序列的行为,而模型真实存在日志内容外的其他行为(图 11中的模型允许的其他日志内容),则会误判日志已经完全反映了模型允许的行为.
 | Fig. 11 Differences between conformance checking with Token Log and Event Log图 11 使用Token Log与使用Event Log进行符合性检查的方法示意图 |
使用Token Log时,基于日志与模型符合的充分必要条件,将符合性检查拆分为两部分:以实际行为为准检查模型结构的正确性;以模型结构为准检查日志行为的完整性.检查中不会有参考行为的遗漏(图 11中More Log部分).
5.2 化动态模拟为静态分析使用事件日志进行符合性检查时,要动态模拟执行参与检查的过程模型,即参照已有日志内容一步步推进模型的执行.然而,真实的过程模型执行是一个自然且难以宏观控制的过程,任务的并行由真实的多线程或者多进程,甚至是多处理器完成.实现该检查过程是再现过程模型的所有可能状态并且在每个状态上执行统计与分析的过程,其空间与时间开销非常大.
然而,使用Token Log进行符合性检查时不会遇到这些困难.整个过程中只有静态分析而没有动态执行.使用Token Log的过程中,可预见的实现难点只有计算Token匹配关系和分析模型特征结构.判断Token匹配关系时只需要判断同一个实例中Token的匹配关系,而且日志中Token个数与参与执行的任务个数呈线性相关,因此花费的空间与时间代价不会达到再现过程模型状态空间.因此,使用Token Log的符合性检查过程相对简单.
5.3 简化判定过程使用事件日志进行符合性检查的方法中,模型与日志的匹配程度通过包含5个度量参数的组合结果衡量.但是根据这些变量的定义,无法直接通过有一个模型与一个日志计算出来的这些结果判定其是否匹配.只能通过比较多组不同模型与日志计算出来的值,确定哪些模型与日志更可能匹配.在多组数据比较的时候,需要权衡各变量的影响权重,不可简单地看哪组数据中较大的变量多就更加匹配.而且,如果参与比较的模型与日志比较多,就更难从中选出匹配的组合.
使用Token Log时,最终衡量符合性的变量只有两个:dal与dcm.可先计算一个衡量参量初步判定模型与日志是否匹配,再决定是否需要计算另一个衡量参数.
5.4 定制判定标准参与符合性检查的日志与模型可能都存在一定的问题,如日志不完整、模型中有不可见任务或者重复任务等,在计算符合性的时候需要将这些因素纳入考虑,要在一定程度上根据日志与模型的实际情况,灵活调整对判定标准.使用Token Log检查日志与模型的符合性,就可以满足这种要求.在检查中,不仅可以根据对符合性要求的不同严格程度确定不同的dap,dcp及两种wi的取值,还可以根据日志与模型的实际情况确定对dal与dcm的容忍程度.使用事件日志时,计算衡量参量的方法是唯一的,没有将模型与日志的特殊情况纳入考虑.如果一个不完整的日志与一个完整的日志同时与一个模型进行符合性检查,使用事件日志得到的结果是只有完整的日志是符合的,而使用Token Log得到的结果可能是两个日志都是符合的,更加符合实际情况.
6 对模型增强的促进判定日志与模型相互符合后,可以根据日志记录的过程行为,分析与发现模型中存在的问题,对过程模型改进.在本文使用的符合性检查方法中,分析与发现模型中可能存在的问题包括:
(1) 日志中信息不完整的Token,指没有生产者或者没有消耗者的Token.这类Token表明模型中存在行为不可见的任务(invisible task),指原结构中存在这些任务,但是没有在日志中记录下来.这种问题可能出现在实现软件系统的过程中,发现与修正这些问题有助于增强过程行为的可视化,便于发现与解决问题;
(2) 日志中Token因模型中没有对应任务而无法填入,说明任务在行为中有记录,但是在模型中没有出现.这种情况说明过程模型在实现阶段发生了变化,但没有在建模工作中更新.在系统管理与维护过程中,系统模型与现实系统保持一致非常重要;
(3) 日志中Token因没有对应库所而无法填入模型,说明任务间的顺序关系没有在模型中体现.日志中Token间匹配关系无法在模型中找到对应的结构,也说明了同样的问题;
(4) 模型中没有填入Token的库所可能表示该库所所在的执行路径没有被执行或者有异常情况.在选择结构的库所中,还可以统计流向不同分支的Token比例,可能对应于不同业务流程被选择的不同概率.可以针对这些统计信息,对不同业务的条件作修改,以达到业务平衡或突出某种业务的执行.
例如,使用只包含表 5实例的Token Log与图 1的过程模型进行符合性检查,得到dal=0.8107,dcm=0.5,考虑到日志的极其不完整性和模型中不可见任务存在的可能性,判定这样的结果即表示其二者匹配.然后,按照日志修改模型,并将日志中所有的Token(黑色点圆)填入模型中,即可得到图 12.
 | Fig. 12 Putting all tokens in Table 5 into the modified model of Fig. 1图 12 将表 5中所有Token填入修改后的图 1过程模型中 |
填入Token的过程中,发现t3与t6无法找到一个相同的相关任务,若这个任务存在,两者间的顺序关系便成立,这个任务很可能就是一个不可见任务.添加了潜在的不可见任务M后,t3与t6均可以填入模型中.图中黑色实心三角形表示库所中还应该填有的其他Token,这些Token集中在选择结构的库所中,表示在已有的日志行为中,某些业务路径还没有被执行.例如,任务B到任务I的选择、任务C到任务K的选择.根据这些信息,可以调整过程中相关业务逻辑,促使某些没有被执行的业务被执行.
使用Token Log进行符合性检查的过程中,还有很多其他的统计信息对模型的增强有着重要的指导作用.其关键是针对Token填入模型时发生的各种情况具体分析,发现模型中对应的问题,从而给出解决方案.
7 工具与实验本节主要介绍基于开源工具PIPE与ProM开发的实验工具、算法及实验过程,主要包括在Petri网建模与分析工具PIPE中开发的Token Log生成插件和在过程挖掘实验工具ProM中开发的Token Log实例去重插件与符合性检查插件.
7.1 生成Token LogPIPE是开源的Petri网建模与分析工具,支持用户自定义插件.为验证过程模型执行中能够产生并记录符合Token Log格式的日志内容,结合PIPE工具开发了模拟执行过程模型并生成Token Log的插件.
7.1.1 模拟执行算法该插件的目标是:使用单线程模拟执行过程模型的并发、选择和循环等结构,同时实现一个过程模型的多个实例同时执行.生成的日志是多个运行实例内容交叉的结果.为满足该需求,本文提出了模拟执行算法.本文将描述算法的核心内容,使用到的相关数据结构及方法仅简单描述,内容如下:
(1) 过程模型通过库所(place)列表(PlaceList)和任务(task)列表(TaskList)表示,库所记录它所有的输入任务(InputTasks)和输出任务(OutputTasks),任务记录它所有的输入库所(InputPlaces)和输出库所(OutputPlaces);
(2) 每个任务执行条件为其输入库所中均填有Token,该Token与第2.1节定义相同;
(3) 在任务执行后,所有填入Token的库所使用非空库所队列(NonEmptyPlaceQueue)记录,如果进入非空库所队列的库所并没有可执行的输出任务,则移入库所等待队列(PlaceWaitingQueue);
(4) 获取库所可执行输出任务的方法getReadyTask(×),判断标准是该任务的所有输入库所中均含Token;如果该库所有多个输出任务且都已经至少执行过1次则随机选择一个.
(5) 模拟执行任务的方法executeTask(×),其效果是从任务所有输入库所中移除一个Token,并向所有输出库所中填入新Token;其输出所有被使用的Token;
(6) 打印被使用的Token信息的方法printTokens(×),只有在Token被消耗时才打印;
(7) 初始化过程模型的输入库所initModelInput(×)方法,其工作是在模型输入库所中填入新Token,并将输入库所添加到NonEmptyPlaceQueue中.在执行过程中,随机执行该方法则可实现多个实例同时运行的效果.如果其执行的次数达到约定的实例个数,则不再执行它;
(8) 非空库所队列的removeEmpty(×)用来移除不含Token的库所,addNewNonEmpty(×)用来添加任务执行后被填入新Token的库所;库所等待队列也有removeEmpty(×)方法,作用与非空库所队列的相同,它的getReady(×)方法则用来获取队列中包含可执行输出任务的库所.
根据以上数据结构与方法定义,模拟执行过程模型的算法见算法1.
算法1. 模拟执行过程模型的算法.
Input: PlaceList; TaskList; numCase;
Global: NonEmptyPlaceQueue; PlaceWaitingQueue;
Related Methods: getReadyTask(×); executeTask(×); initModelInput(×); printToken(×);
Output:Token Log
Begin:
initModelInput(×);
while ((Place p=NonEmptyPlaceQueue.getHead(×))!=null){
Task t=p.getReadTask(×);
if (t!=null){
UsedTokens tokens=t.executeTask(×);
printToken(tokens);
NonEmptyPlaceQueue.addNewNonEmpty(×);
NonEmptyPlaceQueue.removeEmpty(×);
PlaceWaitingQueue.removeEmpty(×);
if (!PlaceWaitingQueue.isEmpty(×)){
NonEmptyPlaceQueue.add(PlaceWaitingQueue.getReady(×));
}
if (numCase>0){
if initModelInput(×) by random is OK then numCase=numCase-1;
}
}else{
PlaceWaitingQueue.add(p);
}
}
End
算法核心过程是不停地从非空库所队列中取出库所,获取可执行任务并模拟执行,其关键是维护非空库所队列.非空库所队列的改变均发生在任务执行后.首先,任务执行可能需要非当前选中库所中的其他Token,则要将新的空库所移除队列.任务执行后会向某些库所中添加新的Token,则要将新非空库所加入队列.任务执行后,可能导致某些非空库所没有可执行的输出任务,则要将该非空库所加入到库所等待队列.库所等待队列用来保证非空库所在确定可以执行后再添加到非空库所队列中,避免直接加入后导致的下次遇到时还是没有可以执行的输出任务.因此在任务执行后,还需要将库所等待队列中有可执行输出任务的库所添加到非空库所队列中.
为实现模拟多个实例同时运行的效果,在执行过程中添加了随机启动新实例的过程.如果启动的实例个数达到预设值,则停止启动新实例.为实现交叉打印Token Log信息,所有的运行实例都使用同一个非空库所队列.通过Token携带的CaseID信息,有效管理不同实例的运行状态,同时为每一个运行实例维护一个时钟信息.
7.1.2 实验插件使用上述模拟执行算法在PIPE中开发了模拟执行过程模型且生成Token Log的插件,图 13为使用该插件模拟执行100个病人去医院看病的过程所打印的Token Log(为了使生成的Token Log格式整齐,在导入图 1模型后,将任务名称修改成两个字),且每列均使用虚线框标记了其内容名称.
 | Fig. 13 Part of the Token Log of the model in Fig. 1图 13 图 1模型生成的Token Log部分内容示例 |
如图 13所示,日志中不仅包含了每个Token的5个信息,同时,所有的Token也按照出现的顺序排列:
· 首先,同一个实例的Token按照在系统的产生的顺序排列.例如,所有CID为1的Token均按照产生顺序出现(黑色实线框标记),该顺序正是其PEID增长的顺序;
· 再者,该系统是一个医院的门诊系统,每一个实例代表一个病人看病的过程.病人看病都需要排队,每个病人都必须在所有先于其挂号的病人完成叫号之后参与叫号.如果病人迟到,则重新参与叫号,需要等所有在其被迟到处理前参与叫号与挂号的病人被叫号后才能再次被叫号.
该日志将被用于与图 1模型的符合性检查中.
7.2Token Log预处理上述生成的日志中包含100个实例,但很多实例是相同的(看病流程相同).因此在用于符合性检查前,需要对日志进行预处理,将所有相同的运行实例合并,并统计其出现次数.本节首先描述日志预处理算法,然后描述基于该算法在ProM中开发的预处理插件.
7.2.1 Token Log预处理算法该算法用于统计Token Log中各交叉出现实例出现的次数.为快速统计出相同实例,首先遍历所有的日志内容,将同一个实例的内容添加到同一个链表中.向已有链表中插入Token的过程见算法2.
算法2. 向实例的Token链表中插入Token的算法.
Input: Token token; LinkedListáTokenñ tokenList;
Output: The last token in of tokenList.
Begin:
lastToken=tokenList.getLast(×);
if (lastToken.caseID==token.caseID){
tokenList.getFirstFromTail (where tmp.CT==token.PT and tmp.CEID==token.PEID);
tokenList.insertAfterTmp(tmp,token);
if (token.isTail(×))
lastToken=token;
}
return lastToken;
End
按上述方法添加Token时,链表里的Token会按照执行顺序排列,如果两个实例内容相同,则对应链表内容必然相同;如果两个实例相同,则其链表最后一个Token的PEID和链表长度必然相同.首先,将所有实例的链表按照其长度与最后一个PEID分配到不同的小组中,则只有在同一个小组中的实例才可能内容相同.这样不仅减少了实例间比较的次数,同时可以使用多线程并行处理各小组实例内容.在数据量非常大的情况下,还可以使用多台机器分别处理多个小组以充分提高计算效率.整个预处理过程的算法表示见算法3.
算法3. Token Log的预处理算法.
Input: Token Log;
Output: Numbers of cases.
Begin:
for (Token t in Token Log){
if (LinkedList for t doesn’t exist){
Create LinkedList for the case of t;
}
tmpToken=Insert t into the LinkedList for the case of t;
if (tmpToken is the last one of the case){
Split the list by tmpToken’s PEID and lengh into different Groups;
}
}
Handle different groups separately with multi-threads, multi-processes, or multi-computers);
End
本文提出的预处理算法,通过:
(1) 整理实例中Token执行顺序;
(2) 将实例内容分组和
(3) 使用节点内容不断将链表分组
的方法,有效避免了直接比对各实例内容是否相同的低效做法,提高了日志预处理效率.
7.2.2 ProM中预处理插件图 14展示了根据上述预处理算法在ProM中开发的预处理插件处理图 14日志的结果.结果表明:实验中使用的日志文件中共有27个不同的实例,出现次数如柱状图所示.
 | Fig. 14 Statistics of merging same cases in the log图 14 日志查重的统计结果 |
计算匹配程度分两个步骤:计算模型正确填入日志的程度(dal);计算日志覆盖模型所有可能行为的程度(dcm).根据第3节描述的方法,在ProM中开发了对应的插件,输入是过程模型和预处理之后的Token Log,输出包括DAL结果(如图 15所示)和DCM结果(如图 16所示).图 15展示了过程模型匹配所有Token间关系的结果.左边的表格统计了所有实例的出现次数,包含的Token间关系类型和数量,能被模型再现的数量及相关DAP值.图 16的右边展示了日志包含各种特征结构的程度(DCP)值与由此计算出的日志包含整个模型的程度(DCM)值.
 | Fig. 15 Statistics of the degree of the model in constructing the token log图 15 过程模型生成Token匹配关系的能力统计 |
 | Fig. 16 Statistics for the degree of the log covering the model图 16 日志覆盖模型的DCM计算结果 |
实验中,使用医院流程模型的Token Log进行符合性检查.为避免日志与模型完全一致,事先将Token Log部分信息删除,结果得出DAL=0.995,DCM=0.857.根据该结果可以判定,日志与模型相符合.判定结果与事实相符.实验结果表明了本文提出的基于Token Log的符合性检验方法的可行性与正确性.在实验中,每种匹配关系被模型再现的程度值是预先设定的,其影响每个实例DAC值的比重也是按照其出现的次数占所有匹配关系出现次数比重计算的,因此,在结果界面上没有调整相关匹配程度定义与比重定义的按钮.同样,在计算DCM的过程中,所有的计算参数都是预先设定的,没有给出调整的操作区域,在后续的研究中将进一步完善实验工具.
8 总结与展望本文提出了一种基于新型日志的符合性检查技术.符合性检查技术用于检查过程模型与系统日志的符合程度.在已有的符合性检查方法中,使用的系统日志为事件日志,并通过按照事件日志内容模拟执行过程模型的方法计算符合程度.该方法的主要缺点是:将模型结构的检查范围局限在已有的事件日志范围内,并没有判断日志行为的完整性,由此产生各种误判情况.例如,如果模型中包含大量选择结构,则即使日志是模型本身的日志,也会因为模拟执行较多任务时都会触发当前序列外的其他任务而误判日志与模型的符合性较低.或者,如果模型中只包含少数的并发结构和多数的顺序结构,则即使日志只包含顺序结构的内容且非该模型对应日志时,也会因为在模拟执行时只有个别任务会导致模型无法继续执行,但其他多数任务可以执行而误判日志与模型有较高的符合性.
本文提出的基于Token Log的符合性检查技术,将检查过程分为使用日志内容检查模型结构的正确性和使用模型特征结构检查日志内容的完整性两个部分,并使用统计结果dal表示模型结构匹配日志内容的程度和统计结果dcm表示日志内容覆盖模型行为的程度,使得检查过程更加全面和清晰,检查结果更加准确.同时,本文提出的新技术可以通过计算结果直接判断模型与日志是否符合,简化了已有技术通过权衡多个计算结果以判断是否符合的过程.本文不仅结合实例详细阐述了使用新型日志进行符合性检查的过程,同时通过实验验证了该方法的可行性与准确性.在实验中,提出了模拟执行过程模型以生成Token Log的算法和统计Token Log中相同实例个数的Token Log预处理算法.
在本文的研究工作基础上,还可以进一步探究在真实工作流系统中实现获取Token Log和存储Token Log的方法,为大规模应用本文提出的符合性检查技术提供数据基础.在日志数量非常庞大时,如何更加高效地实现日志中相同实例的统计也值得深入研究.同时,在本文提出的符合性检查技术基础上,可以进一步细化计算过程,添加根据模型与日志特点确定的自定义判断标准,以进一步灵活运用该技术.
致谢 感谢审稿专家提出的宝贵意见和建议.| [1] | Rozinat A, van der Aalst WMP. Conformance checking of process based on monitoring real behavior. Information Systems, 2008, 33(1):64-95 . |
| [2] | Van der Aalst WMP, Adriansyah A, van Dongen B. Replaying history on process models for conformance checking and performance analysis. WIREs Data Mining and Knowledge Discovery, 2012,2(2):182-192 . |
| [3] | Van der Aalst WMP, Weijters AJMM. Process mining: A research agenda. Computers in Industry, 2004,53(3):231-244 . |
| [4] | Van der Aalst WMP. Process discovery: Capturing the invisible. Computational Intelligence Magazine, 2010,5(1):28-41 . |
| [5] | La Rosa M, Reijers HA, van der Aalst WMP, Dijkman RM, Mendling J, Dumas M, Garcia-Banuelos L. APROMORE: An advanced process model repository. Expert Systems with Applications, 2011,38(6):7029-7040 . |
| [6] | Yan Z, Dijkman R, Grefen P. Fast business process similarity search with feature-based similarity estimation. In: Robert M, Tharam D, Pilar H, eds. Proc. of the Move to Meaningful Internet Systems: OTM 2010. Berlin, Heidelberg: Springer-Verlag, 2010. 60-77 . |
| [7] | Murata T. Petri nets: Properties, analysis and applications. Proc. of the IEEE, 1989,77(4):541-580 . |
| [8] | Van der Aalst WMP, Weijters AJMM, Maruster L. Workflow mining: Discovering process models from Event Logs. IEEE Trans. on Knowledge and Data Engineering, 2004,16(9):1128-1142 . |
| [9] | Van der Aalst WMP, Dumas M, Ouyang C, Rozinat A, Verbeek E. Conformance checking of service behavior. ACM Trans. on Internet Technology, 2008,8(3) . |
| [10] | Van der Aalst WMP, Rubin V, Verbeek HMW, van Dongen BF, Kindler E, Günther CW. Process mining: A two-step approach to balance between underfitting and overfitting. Software & Systems Modeling, 2010,9(1):87-111 . |
| [11] | Wang JM, Wen LJ. Discovering process knowledge from Event Logs. Communications of the CCF, 2012,8(6):63-68 (in Chinese with English abstract). |
| [12] | Li J, Wen LJ, Wang JM. Process model storage mechanism based on Petri net edit distance. Computer Integrated Manufacturing Systems, 2013,19(8):1832-1841 (in Chinese with English abstract). |
| [13] | Wang SH, Wen LJ, Wei DS, Wang JM, Yan ZQ. SSDT matrix-based behavioral similarity algorithm for process models. Computer Integrated Manufacturing Systems, 2013,19(8):1822-1831 (in Chinese with English abstract). |
| [14] | Fan GS, Yu HQ, Chen LQ, Liu DM. Fault diagnosis and handling for service composition based on Petri nets. Ruan Jian Xue Bao/ Journal of Software, 2010,21(2):231-247 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/3790.htm |
| [15] | Song M, Wei ZX, Yin GS. Evolution analysis of data flow oriented internet ware service. Ruan Jian Xue Bao/Journal of Software, 2013,24(12):2797-2813 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/4396.htm |
| [16] | Wu D, Feng DG, Lian YF, Chen K. Efficiency evaluation model of system security measures in the given vulnerabilities set. Ruan Jian Xue Bao/Journal of Software, 2012,23(7):1880-1898 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/ 4112.htm |
| [17] | Yuan CY. Principals and Application of Petri Net. Beijing: Publishing House of Electronics Industry, 2004 (in Chinese). |
| [18] | Van der Aalst WMP, Weijters T, Maruster L. The application of Petri nets to workflow management. Journal of Circuits, Systems and Computers, 1998,8:21-66 . |
| [19] | Hull R. Artifact-Centric business process models: Brief survey of research results and challenges. In: Meersman R, Tari Z, eds. Proc. of the Move to Meaningful Internet Systems: OTM 2008. LNCS, Berlin, Heidelberg: Springer-Verlag, 2008. 1152-1163 . |
| [20] | Xu W, Su JW, Yan ZM, Yang J, Zhang L. An artifact-centric approach to dynamic modification of workflow execution. In: Herrero P, Kumar A, Reichert M, Qing L, Ooi BC, Damiani E, Schmidt DC, White J, Hauswirth M, Hitzler P, Mohania M, eds. Proc. of the Move to Meaningful Internet Systems: OTM 2011. LNCS, Berlin, Heidelberg: Springer-Verlag, 2011. 256-273 . |
| [21] | Van der Aalst WMP, ter Hofstede AHM. YAWL: Yet another workflow language. Information System, 2005,30(4):245-275 . |
| [22] | YAWL foundation. YAWL-Technical Manual (version 2.1). 2010. |
| [23] | Ge JD, Hu H, Lu J. A transformation approach from workflow net to PERT diagram based on invariants. Acta Electronica Sinica, 2008,36(5):893-898 (in Chinese with English abstract). |
| [24] | Ge JD, Hu HY, Zhou Y, Hu H, Wang DY, Guo XB. A decomposition approach with invariant analysis for workflow coordination. Chinese Journal of Computers, 2012,35(10):2169-2181 (in Chinese with English abstract). |
| [11] | 王建民,闻立杰.从日志数据中挖掘过程知识.中国计算机学会通讯,2012,8(6):63-68. |
| [12] | 李婕,闻立杰,王建民.基于Petri网编辑距离相似性的过程模型存储机制.计算机集成制造系统,2013,19(8):1832-1841. |
| [13] | 汪抒浩,闻立杰,魏代森,王建民,闫志强.基于任务最短跟随距离矩阵的流程模型行为相似性算法.计算机集成制造系统,2013, 19(8):1822-1831. |
| [14] | 范贵生,虞慧群,陈丽琼,刘冬梅.基于Petri网的服务组合故障诊断与处理.软件学报,2010,21(2):231-247. http://www.jos.org.cn/ 1000-9825/3790.htm |
| [15] | 宋敏,韦正现,印桂生.面向数据流的网构软件服务动态演化分析.软件学报,2013,24(12):2797-2813. http://www.jos.org.cn/1000-9825/4396.htm |
| [16] | 吴迪,冯登国,连一峰,陈恺.一种给定脆弱性环境下的安全措施效用评估模型.软件学报,2012,23(7):1880-1898. http://www.jos.org.cn/1000-9825/4112.htm |
| [17] | 袁崇义.Petri网原理与应用.北京:电子工业出版社,2004. |
| [23] | 葛季栋,胡昊,吕建.一种基于不变量的从工作流网到PERT图的转换方法.电子学报,2008,36(5):893-898. |
| [24] | 葛季栋,胡海洋,周宇,胡昊,王栋毅,过小波.一种基于不变量的工作流协同模型分解方法.计算机学报,2012,35(10):2169-2181. |