序列模式挖掘算法在高血压治疗中的研究

张晓宇，谢红薇，孟 亮

(太原理工大学 计算机科学与技术学院，山西 太原 030024)

0 引 言

逐步治疗是针对患有慢性疾病(糖尿病、高血压、哮喘等)的病人采用的一种治疗方法。中国高血压[1,2]基层防治指南中根据高血压病病情的发展，对患者的治疗方法提出：高血压分为轻危高血压、中危高血压和高危高血压。当初诊为轻度高血压时，采取生活方式干预和单种药物(ACEI，CCB，低剂量的固定复方制剂等)治疗的方法，当血压不能得到有效控制时，采用多种药物联合治疗的方法。

本文应用序列模式挖掘算法研究高血压患者服用药物的序列，能够为医生提供参考，缩短诊疗时间，降低医疗成本。

序列模式挖掘最早是由R.Algrawal等提出的，并提出了ApriorAll算法和多阶段迭代算法GSP用于零售行业客户购买行为的研究。SPADE算法是Zaki等提出的序列模式挖掘算法[3]。SPADE算法针对GSP算法需要多次扫描数据库的不足，基于格理论和等价类的思想，采用垂直存储结构，将扫描数据库的次数减少到3次，使时间复杂度降低。

Jenna Reps等[4]指出SPADE适用于医疗数据库，采用SPADE算法研究疾病复发的可能性以及影响疾病复发的一些因素。Aileen等[5]采用了SPADE算法挖掘2型糖尿病患者药物治疗的序列。

然而，SPADE算法存在支持度阈值难以设定的问题。因为频繁序列挖掘的结果对支持度的依赖很大，当使用一个较小的支持度时，可能产生大量冗余的频繁序列，而使用一个较大的支持度阈值，则可能产生较少的频繁序列，可能会丢失一些重要的信息。针对这个问题Hu Y H等[6]提出了基于多支持度的模式挖掘算法、Amphawan K[7,8]提出了top-k频繁模式挖掘、刘瑞阳等[9]将逻辑理论的引入模式挖掘算法优化支持度阈值等。然而，上述方法在实际应用中是很难实现的。本文采用统计学的思想，利用支持度阈值和频繁序列数之间的关系，并考虑电子病历中医疗数据的特性[10]，和高血压患者服药数据的特点，提出了一种改进的SPADE算法，来解决支持度阈值难以设定的问题。

1 相关定义

定义1 项目集合I：I是m个不同的项目组成的集合，记为：I={i1,…,im}。

定义2 项集：项集是从I中选取l个项目的非空集合，记为：{i1,i2,…,il}， 其中项目按升序排列并且l>0。

定义3 序列：序列是项集的有序列表，序列α记为：α1→α2→…→αL，其中αi表示第i个项集(1≤i≤l)，αi也被称为是序列α的一个元素。一个序列有L个项目，该序列被称为L-序列。

定义4 序列数据库：序列数据库SDB(sequence database)，每个序列都有唯一的标示符(sid)，每一个序列的每一个项集都有暂时的项集标示符(eid)即时间戳，在一个序列中，eid是唯一的，并且如果一个序列中项集ei先于项集ej发生，那么ei的eid必须严格大于ej的eid。

定义5 子序列：存在两个序列，一个序列是sa=α1→α2→…→αn， 另一个序列是sb=β1→β2→…→βm， 当且仅当存在1≤i1

定义6 支持度：请参见文献[4]。记为：sup(α)。

定义7 频繁序列：D是一个序列数据库，在D中，如果一个序列模式p的支持度大于支持度阈值(min_sup),并且p的子序列也都是频繁的，那么就称p是频繁的。

定义8 序列模式挖掘：请参见文献[4]。

2 算法描述

2.1 SPADE算法思想

SPADE算法是使用“垂直”数据结构的序列数据库，并采用了格理论的方法，将原来的搜索空间分解成小格，使得扫描数据库的次数减少到3次。为库中每个序列建立一个序号列表，列表中每个序列包含序列号和项目号两个属性，在计算序列支持度时，只需要计算序号列表中包含的不同的序列号的个数。并且将具有相同前缀的等长度序列归并为一个等价类，新生成的序列只会在等价类内部产生。SPADE算法提高了支持度的计算效率，降低了I/O成本。

2.2 改进的SPADE算法思想

2.2.1 算法思想

首先定义一个映射关系f，频繁序列的数目m与支持度阈值min_sup构成的映射关系为：m=f(min_sup)。 先选取一个较小的支持度阈值作为初始值，然后支持度阈值线性递增，分别计算不同min_sup下的m值，当m第一次遇到极值点时，对应的 min_sup为最佳的支持度阈值。将得到的min_sup值作为SPADE算法的支持度阈值，执行SPADE算法。

2.2.2 算法流程图

改进的SPADE算法流程如图1所示。

图1 改进的SPADE算法流程

3 实验处理及结果分析

3.1 数据预处理

本文采用的是一家医疗中心的电子病历数据，从2006年到2009年总计79 746条记录，由于其包含所有患者的记录。数据预处理模型如图2所示。

图2 数据预处理模型

在病历数据库中选取528名高血压患者服用药物的数据，共913条记录，每条记录有4个属性，分别是病历号、就诊时间、药品个数和处方药。数据详细说明见表1。

表1 数据集说明

通过实验得出，由于治疗高血压药品种类丰富而且繁杂，使得序列数据比较稀疏，稀疏的数据导致了得到的挖掘结果不理想，所以本文根据高血压防治指南将高血压药品归类为14个药品类。

药品和药品类别归来说明见表2。

表2 高血压药品和药品类别归类说明

注：其中二氢吡啶类CCB是指二氢吡啶类钙拮抗剂；ACEI是指血管紧张素转换酶抑制剂；ARB是指血管紧张素受体拮抗剂

经过分类汇总后实验数据集(MD)一共有4个属性值，分别是患者的序列号，就诊时间，医生所开处方药的个数，以及药品所属类别。将数据集输入序列数据库中，数据格式见表3。

表3 输入数据格式说明

3.2 支持度阈值的判断及结果

将MD作为判定支持度阈值的特定数据集，应用GSP算法，然后得到支持度阈值的判定结果，结果见表4。

表4 支持度阈值判断结果

由表4可以看出，将min_sup=0.001作为初始值，第一次出现的极值点在min_sup=0.007时，min_sup=0.007时也m=37，与min_sup=0.008时m的值相等，所以最终得到最佳支持度阈值min_sup=0.007。从图3中也可直观的反应出min_sup=0.007时是针对这一数据集的最佳支持度阈值。

图3 数据集MD的 min_sup与m关系

将MD随机平均分为两个数据集MD1，MD2；分别应用GSP算法，得到如图4的结果，当MD数据集减小为原来的一半时，MD1表现为m值在min_sup=0.006时出现第一次极值点，而MD2表现为m在min_sup=0.007时出现第一次极值点；再将MD随机平均分为4个数据集MD3，MD4，MD5，MD6，分别应用GSP算法，发现这4个数据集的m值都在min_sup=0.07时出现第一次极值点，如图5所示。由此可以得出对于特定数据集MD，如果只改变数据集的大小，频繁序列数m都表现在支持度阈值min_sup=0.007时出现第一次极值点，所以再次验证数据集MD的最佳支持度阈值为0.007。

图4 数据集MD1和MD2的min_sup与m关系

图5 数据集MD3、MD4、MD5和MD6的min_sup与m关系

从图6中可以看出平均支持度在0.007时第一次到达极值点，min_sup=0.007时，平均支持度=0.018，min_sup=0.008时，平均支持度=0.018，所以在验证了选取min_sup=0.007是合适的。同时，平均置信度也在0.007时到达第一次极值点，min_sup=0.07时，average confidence=0.1712，min_sup=0.08时，average confidence=0.1712，再次验证了min_sup=0.007是最佳的。

图6 最佳支持度阈值验证

3.3 挖掘频繁序列

将min_sup设置为0.007作为参数，继续执行序列模式挖掘算法，得到频繁序列集F，F集中有37条频繁序列，在表5中列举了一些频繁序列及序列的支持度。

3.4 序列规则的生成

将频繁序列生成序列规则这里采用Zhang X Y等[11]提出的将序列的最后一项作为规则的结论，序列中除最后一项的所有项作为规则的条件生成序列规则的方法。这里针对特殊的1-频繁序列，将空集作为条件，将1-频繁序列作为结论来生成规则。例如1-频繁序列(<{噻嗪类利尿剂}>)，它生成的规则为(<{}>-> <{噻嗪类利尿剂}>)表示初次诊断为高血压的患者，医生根据其各项指标给患者的处方可能是噻嗪类利尿剂类的药物。

表5 频繁序列

本文在生成序列规则时选取最小置信度为0.01，将频繁序列生成序列规则共37个，表6中列举了部分序列规则。其中<{β受体阻滞剂}>=><{ACEI，噻嗪类利尿剂，β受体阻滞剂}>，表示患者之前用药是β受体阻滞剂类，由于病情恶化，之前的药物不足以控制血压时，医生可能开出的处方药是ACEI类，噻嗪类利尿剂类和β受体阻滞剂类，3种药物联合治疗。

表6 部分序列规则说明

3.5 规则可视化

下面将挖掘得到的规则实现可视化处理，如图7为序列规则图。

图7 序列规则

4 结束语

本文提出了一种改进的SPADE算法，解决了SPADE算法支持度阈值难以设定的问题。根据支持度阈值和频繁序列数目的关系，选择变化曲线上第一个极值点对应的支持度阈值为最佳支持度阈值。

将改进的SPADE算法应用于研究高血压患者服药历史的序列数据，挖掘频繁序列模式，然后将频繁序列模式转换为序列规则可以为患者逐步药物治疗提供指导。

将得到的高血压患者服药的序列规则结合患者的各项身体指标用于推荐，是下一步工作重点。

[1]World Health Organization.A global brief on hypertension[M].Geneva.WHO,2013:7-15.

[2]HUANG Fei,XIE Hongwei,HAO Xiaoyan.An intelligent classification system used for identifying cardiovascular risk level of hypertensive[J].Science Technology and Engineering,2014,14(7):204-211(in Chinese).[黄飞,谢红薇,郝晓燕.高血压患者心血管风险水平智能分层系统[J].科学技术与工程,2014,14(7):204-211.]

[3]Kumar K M V M,Srinivas P V S,Rao C R.Sequential pattern mining with multiple minimum supports by MS-SPADE[J].International Journal of Database Management Systems,2012,9(5):285-292.

[4]Reps J,Garibaldi J M,Aickelin U,et al.Discovering sequential patterns in a UK general practice database[C]//Procee-dings of IEEE-EMBS International Conference on Biomedical and Health Informatics.Piscataway:IEEE,2012:960-963.

[5]Wright A P,Wright A T,Mccoy A B.The use of sequential pattern mining to predict next prescribed medications[J].

Journal of Biomedical Informatics,2015,53(C):73-80.

[6]Hu Y H,Wu F,Liao Y J.An efficient tree-based algorithm for mining sequential patterns with multiple minimum supports[J].Journal of Systems & Software,2013,86(5):1224-1238.

[7]Amphawan K,Lenca P,Surarerks A.Mining top-k,regular-frequent itemsets using database partitioning and support estimation[J].Expert Systems with Applications,2012,39(2):1924-1936.

[8]Amphawan K,Lenca P.Mining top-k frequent-regular closed patterns[J].Expert Systems with Applications,2015,42(21):7882-7894.

[9]LIU Duanyang,FENG Jian,LI Xiaofen.Logic-based frequent sequential pattern mining algorithm[J].Computer Science,2015,42(5):260-264(in Chinese).[刘端阳,冯建,李晓粉.一种基于逻辑的频繁序列模式挖掘算法[J].计算机科学,2015,42(5):260-264.]

[10]Huang Z,Dong W,Bath P.On mining latent treatment patterns from electronic medical records[J].Data Mining and Knowledge Discovery,2015,29(4):914-949.

[11]Zhang X Y.Research on sequential pattern mining algorithm in recommendation of hypertensive drugs[D].Taiyuan:Taiyuan University of Technology,2017.