关联规则算法在医疗设备管理系统设计与应用

王士森,徐 慧

(南京同仁医院医学工程部,江苏 南京 211102)

医疗设备管理系统通常包含数据采集与通信、设备基础信息挖掘、设备定位、状态监测等模块,医疗设备管理数据种类繁多,隐匿大量未知数据,信息冗余度较高。对设备定位信息进行高维度挖掘、对设备状态监测进行分类等工作会给医疗设备的日常管理带来沉重负担,降低管理系统运行效率。

关联规则(association rule mining)能够反映海量数据中项集与项集之间的关联性或相关关系,可描述问题产生的原因、后果等信息,因此将关联规则算法用于医疗设备管理,能够从大规模设备运行数据中找到引发设备异常状态的相关因素,获取有效的快速检修依据。关联规则算法应用形式较多,其核心问题在于精准选取关联因素之间的强关联规则。为此,本文重新布局医疗设备管理系统架构,对FP- Growth关联规则算法实施改进,提高医疗设备管理智慧化程度。

1 基于关联规则的医疗设备管理系统

1.1 系统总体架构布局

基于关联规则设计高效率的医疗设备管理系统,如图1所示。

图1 基于关联规则的医疗设备管理系统架构

从图1可知,系统包含5个关键单元。基础感知单元中的传感网络负责实时采集医疗设备的内部运行数据、环境数据;摄像头用于获取医疗设备外部状态信息[1];无线定位基站通过和移动终端交互设备运行信息,将传感器采集的医疗设备数据传输至网关基站。MYSQL数据支持单元存储管理数据,在功能逻辑单元对系统功能逻辑进行布局。公共组件单元利用关联规则对高维信息进行降维。最后,通过用户与系统信息交互将医疗设备管理与“关联规则数据挖掘”连接起来,在应用界面展示最具价值的医疗设备信息。

1.2 基于关联规则的医疗设备异常特征初步降维分析

1.2.1基于FP-Growth算法的关联规则分析原理

基于FP-Growth算法挖掘无线传感网络初始设备监测数据的关联规则,获取特征间的强关联规则,实现特征降维,减少无效计算。FP-Growth算法探析隐藏在事务数据项间的关系形成关联规则,无需产生候选项集,其关联规则生成过程只包含2次数据库扫描,将代表频繁项集的医疗设备数据库压缩[2],使用一棵频繁模式树来表达,即FP树,项集的关联数据存储在FP树中,具体而言,基于FP-Growth算法特征降维的步骤如下:

步骤1,扫描数据集获取项目集中每个项目出现的次数,将项目出现最少次数定义为最小支持度,在将最小支持度以下的项目集予以删除后,由大至小排列初始数据集中的项目。

步骤2,再次扫描数据库,构建降序的频繁项头表和FP树。

步骤3,基于由下至上的顺序查找各项目的条件模式基,递归调用树结构,最小支持度以下项予以剔除。生成单一路径是 FP-Growth算法的终极目标,若迭代出单一路径的树结构可直接列举全部组合,算法结束;反之,应循环调用非单一路径树结构,形成单一路径时终止。

定义医疗设备原始数据全部项的集合用I={i1,i2,…,id}表示,全部事务的集合用T={t1,t2,…,tN}描述。各事务集中的项集均为I的子集。

关联规则分析的支持度与置信度表达式如公式(1)和公式(2)所示,其中支持度计算方法见公式(3):

(1)

(2)

s=|{x|x∈D,rulei∈x}|

(3)

式中:s(X→Y)为关联规则的支持度分析形式;c(X→Y)为关联规则的置信度分析形式;X→Y为关联规则形式,其中X和Y表示不相交的项集;σ(X∪Y)为项集X∪Y的支持度计数;σ(X)为项集X的支持度计数;s为支持度集合;N为事务数量;x为支持度值;D和rulei分别为训练数据集及其规则。关联规则挖掘与分析中统一将集合称为项集。

1.2.2FP-Growth算法改进

1)树空间节省策略。

将采集的医疗设备原始数据(包括运行数据、基本信息数据、定位数据等)作为事务集,挖掘出第一棵子树标记为T1,合并T1的全部子树与剩余分支,并剔除T1;新的逆向FP-Tree出现时递归调用挖掘过程,在仅剩一颗子树并且该子树挖掘完成时终止[3]。对于逆向挖掘匹配而言,剩余子树剔除后递归生成条件树的步骤不可省略,并且条件树规模过大会导致整个算法产生的时间开销与空间开销直线上升。对此,使用单向生成代替原本的FP-Tree生成模式,仅沿用指向配套父节点的指针以缩减树的空间,配合使用约束子树策略,为降低树的冗余结构、优化关联规则挖掘效率提供双重保障[4]。

通过剔除非频繁项父项节点指针来节省树空间的FP-Tree关键伪代码为:

lnput:D,T,最小支持数τ

Output: FP-Tree

1 创建树根root,状态为空;

2 for each transactiontinD;

{

3 for each itemxint

4 向t增加在T中查到的全部x父项集;

5 剔除t中冗余父项集;

6 for each itemxint

7 找出与x一致的项集g,查找范围为候选频繁1-项集G1;

8g的支持度计数=支持度计数+1;

9 层次树T中非频繁项的父项予以剔除;

10 重新排序t中频繁项目;

11 Insert Treeo();

12 end for

13 end for

}

14 end for

2)约束子树策略。

原始数据、节点链表、项头表是FP-Tree的基本数据结构,假设FP-Tree中包含rn<…

基于约束子树概念生成FP-Tree的过程中,定义CPath表示与首棵子树挖掘并存的根至节点的子路径,该子路径将根节点作为端点的概率为0;M表示终结点,M支持度计数即为CPath的支持度频度计数,约束子树就是那些受约束子路径限制的子树的组合[5]。为了明确支持度频度计算,在运用约束子树策略时添加一个数组结构块,节点频度计数存储在该结构块中。综上,在引入树空间节省策略与约束子树策略辅助下,FP-Growth算法的时间用量大大缩小,存储空间开销同步降低。

1.3 基于K-means算法的深医疗设备异常信息深度挖掘

对于隐藏异常数据,FP-Growth算法很难通过关联规则进行状态评判,对此基于K-means算法对隐藏数据实施无监督聚类分析——分析医疗设备数据的相似度。异常数据就是离群的数据,可以通过其断定医疗设备的状态。

以关联规则分析后的医疗设备异常特征作为数据样本,K-means算法预设k个初始簇中心点与k个簇数,按照邻近原则向簇中心点代表的簇分配中心点;单簇范围内其新的簇中心点即为利用该簇内全部点重新求取的簇的样本点均值;分配点并更新簇中心点以迭代的方式实现,终止条件是类簇中心点无显著变化和完成预设的迭代次数,二者满足其一即可。本文对传统K-means算法挖掘医疗设备状态信息的步骤进行了优化与改进,以便高性能获取医疗设备中隐藏的状态信息:

步骤1,医疗设备运行信息预处理。求取各个医疗设备数据样本点的密度值,预设一个用以判断样本点是否为孤立点或噪声点的阈值,从而分离出医疗设备样本点中的孤立部分和噪声部分并删除[6],减少冗余点对设备运行特征相似度判定的影响。

步骤2,初始簇中心点选取。以候选初始中心点集为基础,基于最大最小距离原则选取k个数据对象作为初始聚类中心。

步骤3,求取余下医疗设备样本与簇中心的距离,基于均值更新簇中心,均值为k个新的簇中心;再次求取每个簇的样本点均值,并更新簇中心。

步骤4,循环操作步骤3直到满足终止条件,即分类出k个最终簇。

通过上述步骤输出的结果即为医疗设备异常数据的分类结果,可用于判断医疗设备的运行状态,系统据此进行异常预警。

2 测试分析

基于本文优化的FP-Growth算法、K-means算法搭建了医疗设备管理系统,基于无线通信协议实现信息传输。将3台呼吸机、3台麻醉机、2台佩戴型设备、2台院外监测设备作为管理对象。为了准确评估本文系统在医疗设备状态关联规则挖掘方面的优缺点,分别基于传统FP-Growth算法、约束子树FP-Growth算法开发了医疗设备管理系统,进行对比测试。

2.1 系统界面测试

图2所示为本文系统的医疗设备异常监测界面,图像内容为001号呼吸机的异常信息提示。

图2 医疗设备异常监管界面

由界面图可知,该呼吸机存在气道压力过低的问题,通过关联规则分析得知该设备可能存在呼出阀漏气、管道泄漏、面罩(插管)漏气的情况,给出了呼吸机出现异常状态的可能原因,为医护人员提供了检修方向。界面同时给出了警报发出的时间、医疗设备的位置信息。

2.2 系统关联规则生成测试

本文改进的FP-Growth算法将医疗设备运行数据集划分为I1、I2、I3、I4、I5、I6、I7项集。最小支持阈值设置关乎医疗设备状态关联规则挖掘的效果,较小的阈值会导致冗余规则频繁,不能反映关键性信息;较大的最小支持阈值则会导致强关联规则被剔除。本次测试依据阈值预设经验分别设定最小支持度(minsupport)为0.5,最小置信度(minconfidence)为0.8,系统对医疗设备异常信息进行关联规则分析过程中,支持度计数情况见表1,关联规则挖掘结果见表2。

表1 支持度计数统计

表2 关联规则挖掘结果

表2中的数据符合最小支持与最小置信度阈值情况,同时满足支持度≥0.5且置信度≥0.8,所以其结果被视为有效的医疗设备关联规则挖掘结果,属于强关联规则。

统计3种关联规则挖掘算法支持下系统的信息处理效率,见表3。

表3 不同系统的关联规则挖掘时间开销 单位:s

表3数据显示,本文系统挖掘医疗设备状态关联规则的效率最高,且无显著波动,展现了较大的效率优势。这是因为本文系统使用改进后的FP-Growth算法进行关联规则挖掘,使用单向生成模式代替原本FP-Tree生成模式,仅保留指向配套父节点的指针以缩减树的空间,配合使用约束子树策略和双重路径减少了树的冗余结构,从而提高关联规则挖掘效率。此外,本文系统改进FP-Growth算法的最小支持度生成策略,删除低于最小支持度的项集,具有较高的合理性,避免挖掘过多的规则信息,减少了时间消耗。

3 结束语

本文基于改进FP-Growth算法对医疗设备信息实施初步降维处理后减少了信息冗余程度,存储在系统中的信息价值较高,一定程度上减少了系统的负载量、提高了信息处理效率。此外,本文系统基于改进K-means算法对医疗设备的异常信息进行分类,能够准确判断设备存在的问题并发出警报。虽然通过关联规则分析可以得知医疗设备状态的关联性,但是设备异常状态的判断属于隐藏的暗知识,需要进一步实施数据挖掘聚类。本文系统利用K-means算法补充关联规则分析的不足,使得医疗设备管理系统的建设更加完善与全面。