Apriori算法在医疗设备健康管理中的研究与应用

唐 杰 , 程云章

1. 上海理工大学 (上海，200093)2. 上海市肺科医院 (上海，200433)



Apriori算法在医疗设备健康管理中的研究与应用

唐 杰1，2, 程云章1

1. 上海理工大学 (上海，200093)2. 上海市肺科医院 (上海，200433)

目的医院在实施医疗设备精细化健康管理中， 管理系统会产生大量的日志数据， 如何高效利用这些数据， 不仅可以为医疗设备的健康状态进行及时的监控， 而且为潜在的隐患提供支持。方法通过收集血动力工作站、 肺功能仪、 彩色多普勒超声诊断仪等医疗设备的运行日志， 建立事件日志数据库， 分别利用Apriori算法和Apriori优化算法挖掘医疗设备运行时状态的关联规则。结果Apriori优化算法的功能和性能优于Apriori算法。结论Apriori优化算法可以为医疗设备健康管理提供良好的决策支持。

Apriori算法； 关联规则； 医疗设备健康管理

目前， 随着现代信息技术的迅速发展[1]， 医疗设备越来越智能化、 复杂化和种类多样化， 不少关键设备表面上运行正常， 但是后台日志已经产生警告信息， 提示保养、 检查、 维护等信息， 如果忽略这类信息不做及时处理， 一定时间之后极有可能产生更为严重的后果。现有的维修模式是在设备发生故障后再进行检查与维修， 这种模式存在一定的被动性， 医院的设备是有限的， 而现代诊疗方式又高度依赖医疗设备的检查结果， 所以一旦设备出现问题， 其后果可想而知。当前， 多数有源医疗设备都进行了实时监控， 形成了数据量庞大的日志形式反映设备状态的各种数据及参数。这些日志中包含了设备运行时状态的各种特征。利用Apriori算法对医疗设备进行健康管理， 就是根据该设备的运行日志， 从大量杂乱无章的数据中找出隐藏在其中的内在规律， 提取出不同健康状态特征， 对其可能的运行状态进行分类并对其趋势进行预测， 并改进的Apriori算法以适应实际医疗设备健康管理的需要。

1　Apriori算法

为了方便叙述做如下定义[2]：k-项集是含有k个项的项集集合简称。Apriori算法是一种快速挖掘关联规则的算法， 其算法思想[3]是一个可以分为两个运算， 一是合并运算， 用于产生最小支持度的集项， 这些集项记为Ck； 二是过滤运算， 数据的特点产生过滤规则， 对上一步产生的集项Ck进行过滤得到频繁项集Lk。Lk即为目标关联规则集合。Apriori算法的实现过程是用(k-1)-项集去探索k-项集的迭代过程。

(1) 合并运算。首先将项集中的项按字母顺序排序， 然后执行运算， 产生候选项集集合记为C1。

(2) 过滤运算。由于Ck是Lk的超集， 也即是Ck中的项有可以是频繁项也有可能不是频繁项， 因此建立过滤规则， 将Ck中的非频繁的项集都过滤掉， 剩下的即为频繁项集。

输入:DB; min_support。

输出: L, DB中的频繁项.

方法:

L1=find_frequent1-itemsets(D);

Cr={候选项r-项集}

apriori(DB)

{

for(k=2; Lk-1≠φ;k++) {

Ck=apriori_gen (Lk-1);

for each (record r∈DB){ // 扫描DB并作计数

Cr=subset(Ck,r); // 获取子集项r作为候选项集

for each (candidate c∈Cr)

c.count++;

}

Lk={c∈Ck|c.count≥min_support}

}

return L=UkLk;

}

函数apriori_gen用于计算项集的支持度

apriori_gen(Lk-1) // (k-1)-项集

{

for each(itemset l1∈Lk-1){

for each(itemset l2∈Lk-1){

if (has_subset(l1,l2)){

c=l1*l2; // 合并运算生产候选集

if(has_infrequent_subset(c,Lk-1)){

delete c; // 过滤运算， 删除不合适的候选项

}else{

add c toCk};

}

}

returnCk;

}

}

has_subset(l1,l2)

{

returnl1[1]=l2[1]∧(l1[2]=l2[2])∧...∧(l1[k-2]=l2[k-2])∧(l1[k-1]

}

// 使用先验知识

//c为k-项集候选项;

//Lk-1为(k-1)-项集频繁项

has_infrequent_subset(c,Lk-1)

{

for each((k-1)-subset s of c){

if(s∈Lk-1)

return FALSE;}

return TRUE;

}

Apriori算法是重要的关联规则挖掘算法。但是其算法流程上存在 多次扫描数据库和产生大量的候选项集两个瓶颈。对此， 国内外的学者都提出了不少优化办法来克服这两个瓶颈。文献[4]提出了动态项集计数算法(DIC)， 该算法采用Trie树作为项集计数的数据结构， 最多只要扫描两次数据库， 而且产生的候选项集较小， 因此具有较好的效率。文献[5]提出了采样算法， 该算法从数据源中按照某个规则随机选取一个样本数据集， 对这个样本数据集挖掘出关联规则， 然后用数据库中的其余数据验证得到的关联规则。

文献[6]提出了划分挖掘算法， 该采用了划分的思想， 成功解决内存不足的问题。

2　Apriori算法优化

在医疗设备健康管理过程中对医疗设备的运行日志建立事件日志数据库， 通过分析发现该事件日志数据库存在着一定规律。利用这些规律对Apriori算法进行优化[7]， 使得优化后的算法不再需要多长扫描数据库和合并运算来产生频繁项集， 提高了处理效率， 使得优化后的Apriori算法更适合设备健康管理系统， 能快速地挖掘出有用的规则。

apriori_gen(Lk-1)

{

for each(itemset pu∈Lk-1){

for each(itemset qv∈Lk-1){

if((u.item1=v.item 1)∧(u.item2=

v.item2)∧...∧(u.item k-2=v.item k-2)){

x=u∪v

for each (itemset u∈Lk-1){ //扫描所有Lk-1中的元素

for each (itemset c∈Ck) //扫描所有Ck中的元素

//判断Lk-1中的每个元素是不是包含Ck

if (u is the subset of x)

x.count++;Ck= {x∈Ck| x.count = k };

}

}

}

returnCk;

}

}

3　验证测试

为了验证Apriori优化算法的功能和性能， 设计如图1所示设备事件日志数据库作为测试样本， 数据内容包括血动力工作站、 肺功能仪、 彩色超声诊断仪等设备的运行日志。

图1　测试数据的流程结构图

将两个算法在相同的硬件配置条件：Intel(R) Core i5-6500 3.2 GHz主频、 8 GB的内存、 1 TB硬盘、 Windows 7操作系统环境下， 对Apriori算法和Apriori优化算法效率和功能进行测试， 比较Apriori算法和Apriori优化算法的运行时间和运行结果输出， 对比测试输出结果。Apriori优化算法的挖掘结果包含了在Apriori算法的输出结果， 这说明Apriori算法挖掘出了大量无用的关联规则。Apriori优化算法挖掘出的的关联规则数量较少， 并且计算时间随着频繁项项数的增加而小于Apriori算法。实验结果如图2和图3所示。

图2　两种算法运行时间与Item的数量关系

图2所示的是Apriori算法和Apriori优化算法的运行时间与Item的数量关系。由图2可知， Apriori优化算法和Apriori算法的计算时间随记录数目的增加而随之增加， 不过Apriori优化算法的增长幅度较小而趋于平缓， 而Apriori算法随着频繁项数量的增加运行时间而迅速增加。图3两个算法运行时间与最小支持度的关联， 由图3可知Apriori算法受最小支持度的影响比较大， 计数时间随着最小支持度提高而降低， 而Apriori优化算法比较稳定。

图3　算法运行时间与min_support的关系

4　结束语

本文提出了一种Apriori优化算法用于医疗设备健康管理中的关联规则挖掘。经过实验验证， Apriori优化算法能够挖掘出设备健康情况的关联规则， 这些关联规则表明了设备运行参数与设备健康状态之间的关系， 为医疗设备管理人员更好地管理设备提供了良好的决策支持。

[1] 周发超, 王志坚, 叶枫, 等.关联规则挖掘算法 Apriori 的研究改进 [J].计算机科学与探索, 2015, 9(9):1075-1083.

[2] 杨 楠. 基于关联规则Apriori算法的Web日志挖掘研究与实现 [D]. 成都：成都理工大学,2012.

[3] 罗 可, 贺才望. 基于 Apriori 算法改进的关联规则提取算法[J].计算机与数字工程, 2006,36(4)：48-51..

[4] 杨 斌, 万胜春. 数据挖掘在大型医疗设备故障诊断中的应用研究[J].中国医疗设备, 2007, 22(10):40-43.

[5] 范 明, 孟小峰, 译. 数据挖掘概念与技术 [M]. 北京: 机械工业出版社, 2012.

[6] Brin S, Motwani R, Ullman JD, et al. 1997. Dynamic itemset counting and implication rules for market basket data [J]. ACM SIGMOD Record, 1997,26(2):255.

[7] Toivonen H. Sampling large databases for association rules [A]// Proceedings of 22th VLDB Conf., Bombay, India[C]. 1996, 134-145.

[8] Savasere A, Omiecinski E, Navathe S. An efficient algorithm for mining association rules in large databases[A]//VLDB'95[C].1995,432-443.

Apriori Algorithm and Its Application in Medical Equipment Health Management

TANG Jie1，2， CHENG Yunzhang1

1. University of Shanghai for Science and Technology (Shanghai， 20093)2. Shanghai Pulmonary Hospital (Shanghai，200433)

Objective When hospitals implement the fine health management on medical equipments, the management system will generate a lot of log data, and the efficient use of these date could monitor the health status of medical equipment timely, and provide support for potential hazards as well.MethodsCreate an event log database through collecting log data from blood running station, spirometer, color Doppler ultrasound and other medical equipment, and then apply the optimization algorithms and Apriori algorithm respectively, to find out the association rules of medical equipment under running states.ResultsThe improved Apriori algorithm shows a better function performance than Apriori algorithm.ConclusionThe improved Apriori algorithm can provide good decision support for medical equipment health management.

Apriori algorithm， association rule， medical equipment health management

10.3969/j.issn.1674-1242.2016.03.004

唐杰，E-mail:13764658845@163.com

TP399

A

1674-1242(2016)03-0135-04

2016-07-12)