[0021] 以下结合附图对本发明作进一步说明。
[0022] 本发明所提供的基于关系矩阵的工作流日志重复任务识别方法的具体实施方式主要分3步(如图2所示)：
[0023] (1)通过分析特定流程结构，定义其产生的运行日志中事件的上下文规则； (2)使用关系矩阵配合流程结构产生的事件上下文规则，检测日志中重复事件的种类和数量；(3)针对划分的候选重复事件，计算两两之间最大相似度，使得每次聚类的事件最有可能由同一个任务产生。
[0024] 为叙述方便，相关定义说明如下：
[0025] 定义1(事件，轨迹，日志)：设e为事件，E为事件集合，T∈E*表示一个有限的活动序列集合，即轨迹。 表示一个轨迹集合，即事件日志。
[0026] 定义2(重复任务，重复事件)：设t为流程模型中的任务，e为轨迹中事件。映射函数f:t→e表示任务经过系统执行之后在日志中产生事件e，集合α(e)表示日志中事件e所对应的任务集合，如果集合|α(e)|>1，则集合α(e)中的任务称为重复任务，日志中事件e称为重复事件。
[0027] 定义3(跟随关系)：设T＝∈L，称ei+1跟随ei，记为ei>L ei+1。
[0028] 定义4(关系矩阵)：轨迹中所有跟随关系的集合称为关系矩阵Casual Matrix，记为CM，可使用三元组表示，其中：(1)E为日志的事件集合；(2)I为前驱事件集合，对于任意e1∈E，若存在e2∈I(e)，则满足e2>L e1；(3)O为后继事件集合，对于任意e1∈E，若存在e2∈O(e)，则满足e1>L e2。
[0029] 如案例一,轨迹分别是T1＝
,T2＝,T3＝，从这3条轨迹中抽取出关系矩阵，如表1:[0030]事件日志e 前驱事件集合I(e) 后继事件集合O(e)
a {} {d}
d {a,b} {b,g,h}
g {d} {j}
h {d} {j}
b {d} {d,j}
j {b,g,h} {}
[0031] 表1关系矩阵
[0032] 其中a为开始活动，j为结束活动。表中每一行包含一个事件e及其前驱事件集合I和后继事件集合O。
[0033] 定义5(候选重复任务)：F(e)＝|e>Le′|表示所有出现在e后面的事件e′的种类数量，P(e)＝|e′>Le|表示所有出现在e前面的事件e′的种类数量，如果事件e满足如下条件：
[0034] max(min(F(e),P(e)),1)>1 (1)
[0035] 则事件e对应的任务称为候选重复任务。在关系矩阵中，候选重复任务的定义反映与其对应的事件的前驱、后继事件个数均大于1。
[0036] 定义6(事件-活动映射函数)：设EL为日志中出现的所有事件集合，集合中的事件可以重复。A是一个活动集合。映射函数l:EL→A是一个满射，表示为每个e∈EL分配一个标签l(e)＝a∈A。类似地，映射函数l′:A→E是一个满射，表示每个a∈A在原始日志中所对应的事件e∈E，记l′(a)＝e∈EL。 Lref＝(L,l)表示日志L在活动A基础上经过映射函数l之后得到的新日志。
[0037] 定义7(重命名事件集合)：β(e)表示事件e∈E经过映射函数l之后得到的事件集合， 如图1中事件d的重命名事件集合为{d1,d2}。
[0038] 定义8(矩阵循环)：序列称为矩阵循环，记为MC，当且仅当：(1)存在序列Ts＝，其中e0为开始事件，对于任意i属于[0,n-1]，在关系矩阵中都存在ei>L ei+1；(2)Ts中除ei+1外的任务没有重复；(3)en+1与序列Ts中下标为k元素相同。
[0039] 定义9(矩阵并行)：序列称为矩阵并行，记为MP，当且仅当：(1)I与O为活动e在关系矩阵中的前驱后继集合，且I∩O＝ {e1,…,en}；(2)S是集合{e,e1,…,en}的一个全排列，对于所有的s∈S，都存在：如果s为任意轨迹T的子序列，则在轨迹中s的前驱事件为split,s的后继事件为join。
[0040] 定义10(后继关系矩阵)：对于事件e,其重命名事件集合β(e)中事件的后继关系的集合称为后继关系矩阵PCM(e)，使用二元组(β(e),O)表示，其中:(1)β(e)为重命名事件集合，表示活动e∈E在经过映射函数l后被分配到的活动集合；(2)O为原始日志中的有限的事件集合。对于任意a∈β(e)，所有的e∈ O都满足l′(a)>L e。关系矩阵中所有事件后继矩阵集合记为PCM。
[0041] (1)标记特殊结构事件
[0042] 循环和并行结构事件会导致判定时产生不必要的划分类别，最终对后续聚类精确度产生影响。如图3(a)所示循环结构中，任务b作为循环的开始节点，其产生的轨迹中事件b满足定义5的判定条件，会被错误地标记为候选重复任务。如图3(b)，并行结构的关系矩阵中b、c行均可得到max(min(2,2),1)>1，故原本不重复的任务也会满足定义5判定条件。因此需要在原始事件日志中通过分析日志事件行为特征，标记出日志中由循环和并行结构产生的事件序列段，这些标记出的事件不参与之后的事件划分操作。
[0043] 日志中识别循环结构的算法执行过程简述如下：输入原始事件日志L,将输入的关系矩阵CM转化成有向图G，开始事件作为开始节点，从有向图G中递归寻找符合定义8的矩阵循环集合mc_list，将得到的循环与原始事件日志L中进行匹配，对轨迹中匹配到的循环结构，标记循环中第一个事件，如果循环结构后下一个事件和循环第一个事件同名，则这个事件同样给予标记，得到日志中连续出现两次的循环结构集合matched_mc_list，最后输出标记了矩阵循环的日志Lc。
[0044] 从日志中识别并行结构的算法过程可以简述如下：输入关系矩阵CM及标记了矩阵c循环的日志L ,先通过关系矩阵得到符合定义9(1)的矩阵并行事件集合mp_set_list，然后再配合定义9(2)得到矩阵并行序列集合mp_list，之后在日志轨迹中寻找符合矩阵并行的子序列，将日志轨迹中与矩阵并行匹配的事件标记新的事件名称，最后输出标记了矩阵循环和矩阵并行的日志Lcp。
[0045] (2)日志事件划分
[0046] 在日志中确定了属于循环结构和并行结构的事件后，使用定义5确定划分类别。在关系矩阵中，对于所有事件e∈E，如果max(min(F(e),P(e)),1)>1，则e被判定为属于重复事件，与其对应的任务t被判定为重复任务。在经过矩阵循环和矩阵并行标记后的日志中，事件的重命名规则为：设Ae为事件e对应的活动集合，对于事件e∈EL，如果存在max(min(F(e),P(e)),1)>1且e没有被标记为矩阵并行和矩阵循环，则：e′∈I(e)，设tag(e′)为与e′对应的活动名称， l(e)＝tag(e′)∈Ae
[0047] 如案例1中事件d满足重复任务条件，d作为重复事件；d的前驱集合中有a，b 两个事件，对于所有的不属于循环和并行结构的任务d，将前驱为事件a的事件d 重命名为d1，前驱为事件b的事件d重命名为d2，得到d对应的活动集合{d1,d2}。
[0048] (3)日志事件聚类
[0049] 日志中的事件已经按照规则被划分成不同的种类，但是在重复事件划分过程中可能存在由于部分结构没有完全重新标记而导致划分不准确的情况，如图 3(c)所示的选择结构，使用max(min(F(e),P(e)),1)>1公式会将任务c判定为重复任务。这种不正确的划分最终将降低流程模型的精确度。
[0050] 针对可能造成的重复事件划分种类过多的情况，采用循环聚类的方法减少重复事件种类，其中聚类采用基于事件最大相似度的算法。对于 计算重命名事件集合β(e)中两两事件之间的最大相似度，选择相似度最高的两个事件进行聚类操作。聚类过程中需要考虑事件的上下文环境，包括事件的前驱和后继事件种类及数量。由于重复事件划分的数量由前驱事件决定，因此在聚类时只考虑重复事件的后继集合。
[0051] 通过计算事件e的后继关系矩阵中两个重命名事件后继集合中相同后继的数量比例计算事件相似度，其计算公式为：
[0052]
[0053] 其中PCMO(a)表示事件a∈β(e)所对应的后继集合，|PCMO(a)|表示事件 a∈β(e)所对应的后继集合的数量。
[0054] 重复任务聚类算法是先构造所有原始事件的后继关系矩阵，设置初始最佳日志为Lp。只要存在事件e后继关系矩阵|PCM(e)|>1，计算β(e)中相似度最高的两个重命名事件e1,e2，更新日志中Lp的事件名称和后继关系矩阵PCM(emax)。如果使用Lp得到的模型精确度大于使用Lbest得到的模型精确度，则Lbest＝Lp。
[0055] 在聚类过程中，每次都将相似度最高的事件合并，即合并一个事件e的重命名集合中的两个重复事件，同时产生临时模型并计算其精确度。最终聚类得到的日志中，对于所有的e∈E都存在|β(e)|＝1,即经过最后一次聚类后得到的重命名事件日志与原始事件日志相同。
[0056] 本发明可用于分析信息系统中工作流模型挖掘，能正确有效地识别工作流日志中的重复任务，提高工作流模型挖掘的精准度及有效性。
