基于变异反馈的临床路径优化

陈 年，金 涛，王建民

(清华大学 软件学院,北京100084)

1 问题的提出

临床路径是指由一组专业人员制定的，针对某一特定的疾病、诊断或手术的标准化的治疗护理模式。运用临床路径可以起到优化诊疗过程、评估治疗效果、节约医疗资源等作用。根据国家卫计委2017年发布的《医疗机构临床路径管理指导原则》第六、七条要求，医疗机构应当建立临床路径管理工作制度，并成立临床路径管理工作体系，负责临床路径管理工作[1]。

已有的工作大多都集中于临床路径的创建和应用方向，但临床路径创建的数据基础是没有运用临床路径时的医疗数据或者医务人员经验，因此需要经过实践检验。实践发现，虽然符合国家标准的临床路径入径率较高，但变异率往往也很高，多表现为临床路径中缺乏需要的医嘱，这可能是病人病情复杂多变导致的。基于上述情况，对已有临床路径进行优化以降低其变异率，是一个亟待解决的问题。

为解决该问题，本文以已有的临床路径在医院应用后得到的变异医嘱数据为基础，对已有临床路径进行优化以降低其变异率。研究面临的主要挑战有：

(1)医嘱数据是以医嘱为单位的散乱数据，需要处理以得到医嘱阶段等信息。

(2)需要从上述数据中挖掘出可推荐医嘱加入临床路径中。

(3)需要对加入医嘱的数目与降低的变异率加以权衡。

针对以上挑战，在深入分析已有本地临床路径及其在医疗机构应用后得到的医疗数据的基础上，本文首先对常规的遗传算法进行可行性分析，证明其效果达到预期；然后调研了常用的遗传算法改进方法，分析其是否适用于本文研究内容，并将适用的方法实际应用到医疗数据上，进行了性能评估；在上述过程中，发现变异算子与“基因”间关系密切，基于Word2vec得到的医嘱间关系，提出了一种新的变异算子改进方法。

本文工作及思路的整体流程如图1所示，主要贡献包括：

(1)使用遗传算法挖掘得到可推荐医嘱。

(2)针对实际问题，对遗传算法进行了适配和改进，并提出一种新的基于Word2vec的遗传算法变异算子改进方法。

(3)对上述方法进行了试验评估，验证了所提方法的有效性。

2 相关研究

关于遗传算法的综述中，席裕庚等[2]总结得比较全面，但时间偏早，且对基因操作方法的描述过于简洁；葛继科等[3]对基因操作方法的原理和运用方法描述得比较详细，但只涉及了常用的方法；马永杰等[4]全面介绍了遗传算法的原理、发展和运用，但偏向近年来的进展而略过了常用方法。

关于改进遗传算法的研究，杨宇明等[5]讨论了遗传算法运行过程中的一种适应度变换法——线性尺度变换法的实施方法，并给出了具体变换公式及其实施建议；郭晓原[6]对适应度的自适应调整以及选择算子的改进作了深入研究，并将改进后的遗传算法应用在函数优化及PID参数整定问题上;于莹莹等[7]针对旅行商问题，提出了基于贪婪算法生成初始种群和自适应概率调节的遗传算法改进方法，并用伪代码列出了算法整体流程。

关于临床路径挖掘的研究，LANG等[8]从噪声处理、变异探测等7个方面分析了7种过程挖掘算法在临床路径挖掘上的表现，其中效果最好的是WEIJTERS等[9]使用的启发式挖掘算法和DE MEDEIROS等[10]使用的遗传挖掘算法，这两种方法对噪声的鲁棒性强。YANG等[11]分析了2004～2013年的37项研究，探索了临床路径设计的过程发现、变异分析与控制、持续评价与改进3个方面的研究，并分析了这些方法的不足之处。莫天宇[12]和黄俊捷等[13]都作了基于挖掘算法建立临床路径的研究，给出了这些算法的详细使用流程，并介绍了临床路径相关概念。徐啸等[14]提出一种通过主题模型将诊疗活动聚合成主题，然后挖掘得到临床路径模型的方法。

周练[15]和熊富林等[16]总结了Word2vec这一最新技术理论的合集，重点介绍了Word2vec 的核心架构连续词袋模型(Continuous Bag of Words,CBOW)及skip-gram，并对这一技术在中英文语料处理中的应用进行了探讨。

综上所述，①目前关于遗传算法综述类的文献少有算法性能的定量对比；②关于改进遗传算法的研究;通常把重点放在某一步骤的改进方法上；③关于临床路径挖掘的研究则专注于算法之间的性能对比，而非算法内不同改进方法的对比。本文结合上述三者，将改进遗传算法应用于临床路径挖掘问题，并对不同改进方法的效果进行了对比。

3 相关定义与数据预处理

3.1 相关定义

定义1临床路径。由一组专业人员制定的，针对某一特定的疾病、诊断或手术的，标准化的治疗护理模式。

定义2医嘱项目。临床路径的最小粒度单位，是诊疗过程中使用的关于饮食、用药、医疗耗材、检查或手术等方面的指示，每项医嘱只对应一项内容。

定义3临床路径阶段。临床路径的粒度单位，是诊疗过程的一种划分。

定义4临床诊疗日。患者诊疗过程中有诊疗记录的某一天。

临床路径与诊疗实例示例如图2所示。

定义5变异医嘱项目。若医院人工制定的临床路径在当前和下一阶段均不包含该医嘱项目，则该医嘱项目被视为变异医嘱项目。

定义6入径率。病例进入临床路径第二阶段，且第一阶段内的异常医嘱项目不超过 20%，即视为入径病例，否则未入径。

(1)

定义7变异率。病例在入径的基础上，全部诊疗过程存在变异医嘱项目，即视为变异病例。

(2)

定义8最大医嘱数。单阶段可以向临床路径新增的医嘱的最大数目，是“新增医嘱——降低变异率效果”关系的一种制约方法。(需要制约方法的原因是：如果可以无限制地新增医嘱，只要将所有变异医嘱加入临床路径就可以将变异率降至零，但这种临床路径过于“通用”而少“具体针对性”。)

3.2 数据基础

本文实验采用北京清华长庚医院提供的“腹股沟疝临床路径”及其部分时间段内的43个腹股沟疝病人的医嘱数据。原始数据以医嘱记录(即一次医嘱项目的使用记录)为基本单位，每条数据都有47个数据项，共计1 173条。

3.3 数据预处理

数据预处理流程如图3所示，主要分为3个步骤：提取数据、划分阶段、识别变异医嘱。

(1)一条医嘱记录了将近50个数据项，首先要找出所需的重要数据项。本文中提取并使用的数据项及其意义如下：

医嘱号(ORDER_NO)为每条医嘱记录的独特编号，类似于数据库中的NO。

医嘱名称(ORDER_NAME)为医嘱项目的中文名称，如“Ⅰ级护理”。

医嘱代号(CLINIC_ITEM_CODE)为代表医嘱的英文字母+数字编号，如“G05-101”代表“Ⅰ级护理”。

患者编号(PATIENT_ID)为每个患者的独特编号。

来访编号(VISIT_ID)为每次来访的独特编号，与患者编号是“n对1”的关系。

医嘱时间(TIME)为医嘱记录对应的时间，精确到秒。

(2)分析上述数据项，得到病人——诊疗日——医嘱项目的对应关系，然后根据阶段的起止时间划分诊疗日对应的临床路径阶段。

阶段的划分有3个基本性质：

1)诊疗日内多阶段。一个诊疗日可以对应多个连续阶段。

2)诊疗日间阶段单调不减。时间上靠后的诊疗日的阶段不可能比时间上靠前的诊疗日阶段靠前。

3)诊疗日内医嘱无序。考虑到实际情况，同一诊疗日内的医嘱项目不区分先后。

(3)基于上述性质以及医嘱项目—诊疗日的对应关系，可以辨别出与临床路径不吻合的变异医嘱及其对应的阶段。

预处理得到的数据是当前临床路径的完整模型、每个阶段的变异医嘱列表以及各种数据项之间的对应关系，其中临床路径模型的数据结构如图4所示。

4 优化方法

临床路径优化问题，换言之就是如何从医嘱数据中提取出可推荐医嘱的问题，优化流程如图5所示。

本章基于医疗数据和人工制定的临床路径，在第3章数据预处理的基础上，重点介绍了如何使用挖掘算法得到推荐医嘱项，以及对遗传挖掘算法进行改进的方法。具体内容如下：

在将遗传算法应用于临床路径优化问题前，首先需要进行可行性分析，确认这一思路的可行性，设计了运用遗传算法挖掘得到所需信息的流程；在可行性分析实验中，发现常规遗传算法存在效率低下等问题，对遗传算法进行了改进，对各种改进方法的效果进行了评估，并结合Word2vec提出一种新的变异算子改进方法。

4.1 各部分输入与输出

(1)整体输入：基于医疗数据建立的当前临床路径模型、每个阶段的变异医嘱列表。

(2)整体输出：每个阶段的最优医嘱组合、得到最优解平均所需时间。

(3)遗传算法输入：适应度函数、变异医嘱列表、最大医嘱数。

(4)遗传算法输出：最优医嘱组合、种群变化数据等。

(5)Word2vec输入：病人——医嘱数据、临床路径包含的医嘱列表。

(6)Word2vec输出：医嘱对应的向量。

4.2 改进遗传算法

遗传算法的基本思想是“模拟自然进化过程，搜索最优解”，其通用流程如图6所示，下面介绍各步骤的改进方法。

4.2.1 自定义适应度函数

使用遗传算法的目的是在限定可新增医嘱的最大数目的条件下，找到最能降低变异率的医嘱组合。基于该目的，适应度函数应设定为将医嘱组合加入临床路径后变异率降低的数值，但在可行性分析时发现变异率变化范围过小等问题，考虑到遗传算法的效果已经得到证明(详见5.1节)，性能评估部分改用“减少的变异医嘱数”作为适应度。

L代表该医嘱组合，Lo代表旧临床路径对应的医嘱列表，则L的适应度为：

Fitness(L)=Variations(Lo)-Variations(Lo∪L)。

(3)

用变异医嘱数作为评判标准的优势在于提高区分度，从临床意义上看，即使无法使病人由变异病人转为正常，降低使用的变异医嘱数也是一种优化。不足之处是，变异医嘱数与变异率并非线性关系，两种指标应结合使用。在可行性研究的基础上，变异率已经优化至最低，因此采用变异医嘱数作为适应度。

4.2.2 自定义编码

编码方式是遗传算法的核心，关系到后续环节的方案选取。常用如下编码方式：

(1)采用实数编码 可行性分析实验中选用了这种编码方式。具体流程如下：

1)设定最大医嘱数n。

2)用实数列表X代替医嘱列表。存在按什么顺序编号，编号的意义是什么的问题。

3)以减少的变异医嘱数y作为评判标准，得到适应度函数f(X)=y。这一函数的实际意义是：如果向现有临床路径中插入这n个医嘱，数据中有y个病人会从变异转为正常。

4)针对函数f，使用遗传算法找到使y尽可能高的X的较优解。

具体到临床路径优化问题上，编码过程如图7所示。

(2)采用非数值编码 非数值编码的优点是列表内元素直接代表医嘱，相互独立，无需解释医嘱间关系，且在“选择”操作时比较方便。其缺点是选用医嘱数量固定，不能灵活取舍。具体流程如下：

1)设定最大医嘱数n。

2)用整数列表X代替医嘱列表。

3)以减少的变异医嘱数y作为评判标准，得到适应度函数f(X)=y。这一函数的实际意义是：如果向现有临床路径中插入这n个医嘱，数据中有y个变异医嘱转为正常医嘱。

4)针对函数f，使用遗传算法找到使y尽可能高的X的较优解。

(3)采用二进制编码 二进制编码的优点是没有限制新增医嘱的数量，因此在“交叉”和“变异”操作时比较方便，而且可以简便地加入、修改惩罚函数。其缺点是向量稀疏，效率较低。具体流程如下：

1)设定惩罚函数p(n)，其中n为新增医嘱数。

2)用二进制列表X代替医嘱列表。

3)减少的变异医嘱数y作为评判标准，得到适应度函数f(X)=y-p(n)。这一函数的实际意义是：如果向现有临床路径中插入这n个医嘱，数据中有y个变异医嘱转为正常医嘱，但考虑到新增医嘱的代价，扣除p(n)。

4)针对函数f，使用遗传算法找到使y-p(n)尽可能高的X的较优解。

4.2.3 选择算子改进方法

在进行选择之前，先对适应度进行归一化处理。

常用的选择方法如下：

(1)随机采样/轮盘赌 其基本思想是“某个体被选择的概率与其适应度成正比”，具体方法是根据旧种群中个体的适应度决定选中概率，然后随机复制一个个体加入新种群，重复直至新种群被填满。

(2)排序选择 先对个体适应度进行排序，然后按顺序手动分配概率。这种方法需要靠经验手动决定个体保存的概率，或者用其他算法经实验得到最好的参数，考虑到本文探讨的是遗传算法的效率，这么做是本末倒置，因此没有选用此方法。

(3)随机比赛 随机选出旧种群中的一部分个体，将其中适应度最高的一个加入新种群，重复直至新种群被填满。考虑到本文研究的问题得到适应度所需计算时间较短，该方法与轮盘赌没有本质区别，因此没有选用。

常用的改进方法如下：

(1)最优个体保留 将旧种群中适应度最高的个体直接保留到新种群中，确保全局收敛。

(2)适应度尺度变换 基本思想是“缩放适应度，使其符合需要”。这里选用自适应线性尺度变换，前期适应度差距较大时缩小差距，防止前期较优个体迅速统治整个种群，后期适应度差距较小时放大差距，使变异出的更优秀个体能迅速扩大优势，跳出局部最优解，缩放参数与适应度的最值和平均值相关。缩放公式[5]如下：

(4)

(5)

判断前后期的界限依靠经验。经过实验发现，本文研究的问题中适应度差距普遍偏小，因此直接进入后期放大阶段。

4.2.4 交叉算子改进方法

“交叉”操作首先将种群中的个体两两配对，然后互换一些基因。

常用的交叉方法如下：

(1)单点交叉 随机设置一个交叉点，两个个体互换该点前或者后的基因，可以理解成一种特殊的双点交叉，且效果一般比双点交叉差，因此没有选用。

(2)双点交叉 随机设置两个交叉点，两个个体互换两点之间的基因，适用于二进制编码。

(3)多点交叉 交叉点大于2，介于双点交叉和均匀交叉之间，因此没有选用。

(4)均匀交叉 每个基因都有一定概率与另一个个体相同位置上的基因互换，要求交叉的两个个体长度相同。

(5)算术交叉 两个个体线性组合成新的个体，适用于实数编码，因此没有选用。

(6)启发式交叉 需要引入专业知识，因此没有选用。

4.2.5 变异算子改进方法

“变异”操作的目的是引入新基因。常用的变异方法如下：

(1)均匀变异 每个个体的每个基因都有小概率变异。

(2)常规位变异 每个个体都有一定概率发生变异，当确定一个个体发生变异后，再随机指定发生变异的基因。这与均匀变异没有太大差别，因此没有选用。

(3)自适应变异 根据种群情况自我调整概率。这里选用概率自适应二元突变，个体间两两配对，由两个个体的相似度决定变异概率，越相似变异概率越高，反之则越低。

(4)高斯变异 类似“正态分布随机数”，只适用于实数编码，因此没有选用。

此外，本文提出了一种基于Word2vec方法得到的医嘱向量，判断基因变异成不同基因的概率的改进方法(详见4.3节)，适用于非数值编码。

4.3 引入Word2vec方法

Word2vec是一类通过学习训练语料获得词向量的语言模型，其核心架构分为CBOW和skip-gram两种。两种架构都由输入层、隐藏层、输出层组成，不同之处在于CBOW模型通过上下文预测当前词，skip-gram模型则通过当前词预测上下文。本文中使用的不是模型的预测能力，而是其隐藏层(即词向量)，因此在两种架构上都作了尝试。

本文提出了一种新的遗传算法变异算子改进方法，其基本原理如下：

(1)如果两个词语经常在一句话里出现，说明二者存在关联；同理，如果两个医嘱项目经常被一起使用，说明存在关联。

(2)Word2vec模型可以发现这种关联，将词语转换为词向量，同理可以将医嘱转换为医嘱向量。

(3)在遗传算法的变异过程中，尤其是后期，局部最优解和更好的解之间的差距往往只是一个医嘱，而且两者的这一个医嘱通常存在关联，类似“换药(大)”和“换药(小)”。将医嘱向量应用于变异过程，趋向于变异为关联较大的医嘱，有利于摆脱局部最优解。

基于病人——文本、医嘱——词语的类推，通过病人——医嘱数据，训练得到医嘱对应的词向量以及医嘱之间的相似度，在“变异”操作时，每一个变异的基因按照其与其他基因的相似度，依照轮盘赌方法变异成新的基因，具体流程如图8所示。从本质上看，这是一种基于“基因”间关系修改变异概率以加快收敛速度的改进方法。

5 实验与效果评估

本章介绍实验结果及结果评估。

5.1 遗传算法可行性评估

本节介绍遗传算法对于临床路径路径变异率影响的实验效果，实验中采用北京清华长庚医院提供的“腹股沟疝临床路径”及其部分时间段内的 43 个腹股沟疝病人的医嘱数据。

表1所示为不同优化方法对变异率的降低效果对比。

表1 与其他算法算法的对比

可以看到，遗传算法在将复杂度降低到可接受程度的同时，效果接近甚至等同于直接遍历，具备实用价值。

5.2 遗传算法性能评估

本节介绍遗传算法经过不同方法改进后，在临床路径优化问题上的不同表现。如图9所示为非数值编码前提下，不同方法改进的遗传算法的效率对比；如图10所示为二进制编码前提下，不同方法改进的遗传算法的效率对比。

图9中的“count”指是最大医嘱数，考虑到非数值编码情况下没有惩罚机制，最大医嘱数等于选用的医嘱数。因此，count越大，计算代价越大，变异率降低得越多。对效率的评价指标是“达到最优解平均所需时间”，单位为s，由于遗传算法的随机性较大，视count数不同，每组实验重复20～30次取平均值。

改进的方法用编号表示：①尺度变换;②最优保存;③引入Word2vec;④均匀交叉;⑤双点交叉;⑥均匀变异;⑦自适应变异。其中引入Word2vec方法经预实验发现CBOW架构和skip-gram架构效果相差不大，因此采用二者的平均值。

图9说明，按效率从高至低排序，尺度变换+最优保存>尺度变换≈最优保存>经典遗传算法(即没有使用任何方法改进)，但当count数占变异医嘱总数比例太大时，进行尺度变换的代价可能超过其对收敛速度的提高效果。而引入Word2vec方法得到医嘱向量后，当count=5时效率下降，count=10时持平，count=20时效率提高，说明其对收敛速度的提高效果在count较大时更加明显。考虑到word2vec得到医嘱向量的准确度和数据量大小直接相关，而且直接按欧氏距离判断医嘱关系然后影响变异率只是对医嘱向量的粗浅应用，这一方法在院级或更大级别的数据集上可能有更好的实用前景。总体而言，非数值编码情况下，改进后的遗传算法性能提高了约50%～55%。

图10说明，按效率从高至低排序，均匀交叉+自适应变异>均匀交叉+均匀变异>双点交叉+均匀变异。考虑到交叉和变异相互独立，均匀交叉+自适应变异的组合效果最好。二进制编码情况下，改进后的遗传算法性能提高了约77%。

6 结束语

结合实验，本文结论如下：

(1)遗传算法用于优化临床路径的效果接近甚至相当于遍历(即最优解)，且计算时间远低于遍历，具备可行性。

(2)关于遗传算法各种改进方法对性能的提升，非数值编码效果最好的是轮盘赌、尺度变换、最优保存、均匀交叉、自适应变异的组合，二进制编码效果最好的是轮盘赌、均匀交叉、自适应变异的组合，性能分别提升了50%和77%。

(3)在上述效果最好的改进方法的基础上，结合Word2vec方法后，count较大情况下的性能提高了约5%。

本文仍存在以下不足：

(1)文中只测试了常用的遗传算法改进方法，没有涉及最新研究成果。

(2)由于本文研究重点是算法应用于实际问题的性能分析，也由于数据本身限制，实验中没有考虑医嘱跨阶段、药物剂量等问题。

(3)Word2vec方法效果并不明显，主要原因是现有数据不足以反映出医嘱间的完整关系，因此得到的只是改进的趋势，仍有较大的改进空间。

(4)只考虑了新增医嘱，没有修改已有临床路径，主要是因为删改路径需要多方面考量，而本文的目的只是获得可供参考的推荐医嘱。

基于上述问题，今后可从以下方向进行改进：

(1)补充遗传算法的其他改进方法，如小生境、灾变算子等。

(2)补充细节部分，以便应用于实际。涉及到药物剂量、价格、医保等问题，需要与专业医务人员合作。

(3)在更好的神经网络架构和更大数据集基础上，对医嘱间关系进行进一步分析。此外，将Word2vec得到的医嘱向量直接用于调整概率的思路太过直接，应该在分析向量特性后设计更好的运用方法。

(4)与医务人员合作，分析医嘱权重，进一步给出临床路径修改意见。