﻿ 基于过程挖掘的临床路径Petri网建模
 文章快速检索
 同济大学学报(自然科学版)  2018, Vol. 46 Issue (4): 524-534, 549.  DOI: 10.11908/j.issn.0253-374x.2018.04.016 0

### 引用本文

YU Jianbo, ZHENG Xiaoyun, LI Chuanfeng, DONG Chenyang. Clinical Pathway Modeling by Petri Net Based on Process Mining[J]. Journal of Tongji University (Natural Science), 2018, 46(4): 524-534, 549. DOI: 10.11908/j.issn.0253-374x.2018.04.016.

### 文章历史

Clinical Pathway Modeling by Petri Net Based on Process Mining
YU Jianbo, ZHENG Xiaoyun, LI Chuanfeng, DONG Chenyang
School of Mechanical Engineering, Tongji University, Shanghai 201804, China
Abstract: This paper proposed a clinical pathway Petri net model based on statistical α-algorithm, which integrate the basic Petri net with process mining algorithm based on statistical α-algorithm. This model can obtain medical procedure from event log and build clinical pathway Petri net model on the procedure. The medical procedure could be optimized and improved by analysis of the Petri net model. Simulation results shows that the statistical α-algorithm performs better in accuracy and efficiency than classic α-algorithm. The proposed model is verified on the real data of clinical pathway.
Key words: clinical pathway    statistical α-algorithm    petri net modeling    process mining algorithm

1 基于统计α算法的临床路径Petri网建模方案

 图 1 基于统计α算法的临床路径Petri网建模方案 Fig.1 Scheme of clinical pathway Petri net modeling based on statistical α-algorithm
2 基于统计α算法的过程挖掘

2.1 统计α算法

 图 2 统计α算法流程 Fig.2 Procedure of statistical α-algorithm

Structure活动对{

String FA，第一个活动名称(Ti);

String SA，第二个活动名称(Ti+1);

int F，出现次数=1;

String R，活动关系=顺序关系(默认);

}

 $P(AC({T_i}, {T_{i + 1}})) = \frac{{AC({T_i}, {T_{i + 1}}).F}}{{N{n_r}}}$

Input Wd//事件日志, α//显著性水平

Output Matrix[Array(AC)]//活动关系矩阵

1. Foreach(σi in Wd)

σi←{T1, T2, …, Tj, Tj+1, …}//赋值

j : 1→σi.Length

If (AC(Ti, Ti+1) is exist)then

AC(Ti, Ti+1).F++//活动对频数

Else

AC(Ti, Ti+1).FATi

AC(Ti, Ti+1).SATi+1

P(AC(Ti, Ti+1))= $\frac{{AC\left( {{T_i}, {T_{i + 1}}} \right).F}}{{N * {n_r}}}$

2. Foreach(σ in Wd)

σiA1, A2, …, Aj, Aj+1, …//构造轨迹

σkB1, B2, …, Bj, Bj+1, …//构造轨迹

j : 1→σi.Length

If(AjBj)

End

Output DArray(AC)

3. Foreach (AC in DArray(AC))

ACAC(A, B)

#AC(A, B)←AC(A, C)//同前活动对

AC(A, B)←AC(B, A)//转置活动对

If (P(AC(A, C))> α) then

Dim AC(B, C)

If (P(AC(B, C))> α) then

If (P(AC(B, C))> α) then

B||wC

Else

B#wC

Else

B#wC

A>wB, A>wC

Else

If (P(AC(B, A))> α) then

A||wB

Else

AwB

End.

Output Matrix[Array(AC)]//活动关系矩阵

2.2 重名活动判别规则

(1) 若GA=G′ATP=TPTS=TS，则〈δi(A, n), δi(A, m)〉 $\subset$ U.

(2) 若GA=G′ATP=TPTSTSTS=TSS，且TSS=TS，则〈δi(A, n), δi(A, m)〉$\subset$U.

(3) 若GA=G′ATPTPTS=TSTP=TPP，且TPP=TP，则〈δi(A, n), δi(A, m)〉$\subset$U.

(4) 若GA=G′ATPTPTSTSTP=TPPTPP=TPTS=TSS，且TSS=TS则〈δi(A, n), δi(A, m)〉$\subset$U.

(5) 若GAG′ATP=TPTSTSTS#wTS，则〈δi(A, n), δi(A, m)〉$\subset$U.

(6) 若GAG′ATPTPTS=TSTP#wTP，则〈δi(A, n), δi(A, m)〉$\subset$U.

(7) 若GAG′ATPTPTP#wTPTSTSTS#wTS，则〈δi(A, n), δi(A, m)〉$\subset$U.

(8) 若GAG′ATPTPTP#wTPTSTSTS=TSSTSS=TS，则〈δi(A, n), δi(A, m)〉$\subset$U.

(9) 若GAG′ATSTSTS#wTSTPTPTP=TPPTPP=TP，则〈δi(A, n), δi(A, m)〉$\subset$U.

2.3 集成重名活动判别和统计α算法的过程挖掘方法

 图 3 基于重名活动判别和统计α算法的过程挖掘方案 Fig.3 Scheme of process mining that based on statistical α-algorithm and cognominal activity identification

(1) 原始数据的筛选.获取数据库中结构完整、数据量较大的完备事件日志.

(2) 工作分解结构.将事件日志中的工作流按照其阶段、内容分成若干部分，从而可以减少每一部分包含的活动数目，降低算法运行时间，提高准确度.

(3) 数据预处理.将事件日志中的活动进行重命名排序操作，为重复活动判别做准备.

(4) 重复活动判别.以流程轨迹为单位，对其中出现的重名活动进行分析，根据分析结果重新修正活动命名，为活动关系识别做准备.

(5) 活动关系识别.采用本文提出的统计α算法，提取工作流程知识，分析活动之间的依赖关系，得到活动关系矩阵.

(6) 得到结果并修正.根据上一步骤中得到的活动关系矩阵，并将模型问题还原到实际问题之中.

3 基于过程挖掘算法的临床路径Petri网模型

CP－net需要满足以下5条约束：

(1) 起止唯一性：有且仅有一个piP满足·pi= $\emptyset$; 有且仅有一个poP满足po·=$\emptyset$.临床路径的起止分别为病人的最初状态和最终状态，这个状态是唯一的.

(2) 无孤性：不存在pP，使得·pp·=$\emptyset$; 不存在tT，使得·tt·=$\emptyset$.病人状态不可能单独存在，同样地，单独存在的诊疗活动也不可能出现在事件日志中.

(3) 有界性：对于$\forall$ pP$\forall$MR(M0)，存在一个非负整数k，都有kM(p)，即任何状态下，库所的令牌总是有限个的，不存在没有输入库所的变迁.在临床路径中，每一个诊疗活动的开展都是以病人当前状态为基础的.

(4) 无死锁：对于$\forall$tT，都可以通过执行某一变迁序列从而最终使得t使能.即在临床路径中出现的诊疗活动都是有机会实施的，无法实施的诊疗活动不能包含在临床路径中.

(5) 无活锁：对于最终库所poM(po)=Wpo, po)，保证最终托肯数量为零.在临床路径中一旦到达病人最终状态，不再进行该病种的任何诊疗活动.如果后续其他活动出现，则判定为路径跳转.

 图 4 活动关系Petri网描述 Fig.4 Description of activity relation in Petri net

(1) 若a·∩·b$\emptyset$b·∩·a=$\emptyset$a, b $\notin$ U，则awb(因果关系)

(2) 若a·∩·b= $\succ$ a= $\prec$ b，则a>wb(顺序关系)

(3) 若OR－split∈·a∩·bOR－join∈a·∩b·，则a#wb(选择关系)

(4) 若AND－split∈·a∩·bAND－join∈a·∩b·则a||wb(并行关系)

W为活动集合T上的事件日志，给定显著性系数为α，统计α算法α定义如下：

(1) XW={AC(a, b)| $\forall$ a, bW, a·∩·b= $\succ$ a= $\prec$ b}

(2) DXW={AC(a, b)| $\exists$ σ, σ'∈WAC(a, b)≠AC′(a, b), AC(A, b)∈σ, AC′(a, b)∈σ′}

(3) TW={tT|t∈AC, AC.Pα}

(4) Ti={tT|$\exists$σWt=first(σ)}

(5) To={tT|$\exists$σWt=last(σ)}

(6) PW={p(a, b)|(a, b)∈XW}∪{iW, oW},

 $P\left( {a, b} \right) = \left\{ \begin{array}{l} 1, {\rm{ }}当\;a{ > _w}b或\;a{ \to _w}b\\ 2, 当\;a = AND{\rm{ - split}}\\ OR - {\rm{split/join}}, 当{\# _w}b \end{array} \right.$

(7) FW={(a, p(a, b))|aAC(a, b)∈DXW}∪{b, p(a, b))|bAC(a, b)∈DXW}∪{(a, $\prec$ b)|a, bAC(a, b)∈XW, AC(a, b)$\notin$DXW}∪{(iW, t)|tTI}∪{(t, oW)|tTO}

(8) α(W)={PW, TW, FW}

 图 5 基于过程挖掘算法的临床路径Petri网建模过程 Fig.5 Procedure of clinical pathway modeling based on process mining

(1) 得到事件日志.从原始数据开始，首先需要获得构建CP－net必需的事件日志，这是过程挖掘的基础，也是CP－net主体网络的基本构成.

(2) 得到活动关系矩阵.对于每个单病种事件日志，首先按照定义生成活动对，得到活动对集合XW，同时计算每个活动对的出现概率，据此按照规则去除噪声数据得到变迁集合TW.接下来通过比对得到待判断活动对集合DXW以及活动每条流程轨迹的起始和终止变迁集合TiTo.对于集合DXW，需要通过遍历该集合，利用统计α算法识别每一个活动对的活动关系，结合XW集合中已知的活动对关系，构造活动关系矩阵.

(3) 构造主网络.在得到的活动关系矩阵以及变迁集合TW基础上按照α(W)定义的第6条生成相应的库所集合PW，并由PWTWTiTo得到主网络的流关系集合FW.

(4) 构造CP－net.在主网络形成之后，根据原始数据中对资源的分配得到容量函数K，根据每项诊疗活动的开展条件得到流关系的权函数W，根据病人的初始状态得到CP－net的初始标识M0，由此便得到最终的CP－net模型.

4 试验与结果分析

4.1 仿真数据试验

 图 6 算法准确度对比 Fig.6 Comparison of accuracy
 图 7 算法运行时间比较 Fig.7 Comparison of runtime

 图 8 仿真数据Z1的Petri网模型(部分)截图 Fig.8 Petri net model of data Z1(part)

α系列算法由于其对噪声的消除不够，因而常常出现过拟合的问题.而统计α算法在进行活动关系判断之前，将其中的噪声进行消除，而这种消除的方式则是通过对于活动概率的统计进行的，因此，统计α算法的结果在拟合度上往往接近100%.

(1) 结构完整性.通过对模型和事件日志中活动的对比，该模型并没有包含仿真数据中出现的所有活动，根据计算，该模型的拟合度为98.2%，若对照对仿真数据Z1中噪声的设定，该模型几乎没有包含任何噪声信息，很好地消除了事件日志中的噪声.

(2) 行为完整性.这里重点考察仿真数据中添加的特殊结构.该模型由于其对于因果关系没有直接的体现，因此在因果关系方面略有不足.但是对并行、选择等关系模型都能精准地表现出来.

(3) 可达性.通过对于关键结构点的托肯分布以及变迁使能条件的分析，该模型可达率为100%.

4.2 临床路径建模试验

 图 9 锁骨骨折手术监护期临床路径Petri网模型截屏 Fig.9 The Petri net model of clavicle fracture

(1) 结构完整性.不同于仿真数据中噪声随机的产生，该日志经过人工分析，噪声存在于事件日志中活动偶尔出现的缺失和错位，噪声量并不大，因此最终得到的模型在拟合度方面表现很好，结构完整性高达99.3%.

(2) 行为完整性.首先，该病种的事件日志中，存在着5对重名活动，模型准确地将重名活动识别出来，并分辨出其中一对为非重复性重名活动，重名活动判别准确率为100%.其次，该事件日志中存在的特殊关系较多，模型成功识别并表达出3处并行结构和2处选择结构，对于并行结构和选择结构的识别准确率为100%.对于因果关系该模型同样没有直接表现出来，属于模型欠缺的地方.通过模型还可以发现，最后一处的选择结构为2层选择结构的嵌套，对于该处的选择结构可以进行如下理解：在手术完成后并经过基本护理后，需要对病人的状态进行询问和定义，若病人状态良好让病人正常休息、正常进食即可完成整个临床路径; 若病人出现身体疼痛等生理问题，需要进行“疼痛护理”活动，为病人缓解病痛; 若病人出现心理不安，则需要进行“心理护理”活动，为病人缓解压力.总之，该模型对于特殊活动关系的反映率达到了90%.

(3) 可达性.该模型不存在死锁之处，短循环也存在着循环次数的限制，可达率为100%.

4.3 显著性系数敏感性分析

5 结语

 [1] LANG M, BVRKLE T, LAUMANN S, et al. Process mining for clinical workflows: Challenges and current limitations[J]. Studies in Health Technology & Informatics, 2008, 136: 229 [2] COOK J E, WOLF A L. Automating process discovery through event-data analysis[C]//Proceedings of the 17th international conference on Software engineering. [S. l. ]: ACM, 1995: 73-82. [3] AGRAWAL R, GUNOPULOS D, LEYMANN F. Mining process models from workflow logs[C]//International Conference on Extending Database Technology. Berlin Heidelberg: Springer, 1998: 467-483. [4] HAMMORI M, HERBST J, KLEINER N. Interactive workflow mining-requirements, concepts and implementation[J]. Data & Knowledge Engineering, 2006, 56(1): 41 [5] AALST W V D, WEIJTERS T, MARUSTER L. Workflow mining: Discovering process models from event logs[J]. IEEE Transactions on Knowledge & Data Engineering, 2004, 16(9): 1128 [6] MEDEIROS A K A D, Dongen B F V, AALST W M P V D, et al. Process mining for ubiquitous mobile systems: An overview and a concrete algorithm[C]// International Workshop on Ubiquitous Mobile Information and Collaboration Systems. [S. l. ]: Springer, 2004: 151-165. [7] WEN L, AALST W M P V D, WANG J, et al. Mining process models with non-free-choice constructs[J]. Data Mining & Knowledge Discovery, 2007, 15(2): 145 [8] WEN L, WANG J, SUN J. Mining invisible tasks from event logs[C]// Joint, asia-pacific web and international conference on web-age information management conference on advances in data and web management. [S. l. ]: Springer-Verlag, 2007: 358-365. [9] 李嘉菲, 刘大有, 杨博. 过程挖掘中一种能发现重复任务的扩展α算法[J]. 计算机学报, 2007, 30(8): 1436 LI Jiafei, LIU Dayou, YANG Bo. Process mining: An extended α-algorithm to discovery duplicate tasks[J]. Chinese Journal of Computers, 2007, 30(8): 1436 [10] WEN L, WANG J, AALST W M P V D, et al. A novel approach for process mining based on event types[J]. Journal of Intelligent Information Systems, 2009, 32(2): 163 DOI:10.1007/s10844-007-0052-1 [11] QUAGLINI S, STEFANELLI M, LANZOLA G, et al. Flexible guideline-based patient careflow systems[J]. Artificial Intelligence in Medicine, 2001, 22(1): 65 DOI:10.1016/S0933-3657(00)00100-7 [12] GRANDO M A, GLASSPOOL D W, FOX J. Petri nets as a formalism for comparing expressiveness of workflow-based clinical guideline languages[C]// International Conference on Business Process Management. [S. l. ]: Springer, 2008: 348-360. [13] 赵艳丽, 江志斌, 李娜. 基于分层赋时着色Petri网的临床路径建模[J]. 上海交通大学学报, 2010(2): 252 ZHAO Yanli, JIANG Zhibing, LI Na. Modeling of clinical pathway based on hierarchical timed colored Petri net[J]. Journal of Shanghai Jiaotong University, 2010(2): 252 [14] 田燕, 马晓普, 张新刚, 等. 基于Petri网的临床路径评估与优化[J]. 计算机科学, 2013, 40(5): 193 TIAN Yan, MA Xiaopu, ZHANG Xingang, et al. Evaluation and optimization of clinical pathway based on Petri net[J]. Computer Science, 2013, 40(5): 193 [15] WEERAPONG S, POROUHAN P, PREMCHAISWADI W. Process mining using α-algorithm as a tool: A case study of student registration[C]//2012 10th International Conference on ICT and Knowledge Engineering. Bangkok: IEEE, 2012: 213-220. [16] AALST W M P V D, DONGEN B F V, HERBST J, et al. Workflow mining: A survey of issues and approaches[J]. Data & Knowledge Engineering, 2003, 47(2): 237