Apriori算法在醫(yī)療設(shè)備健康管理中的研究與應(yīng)用

唐 杰 , 程云章

1. 上海理工大學(xué) (上海，200093)2. 上海市肺科醫(yī)院 (上海，200433)

?

Apriori算法在醫(yī)療設(shè)備健康管理中的研究與應(yīng)用

唐 杰1，2, 程云章1

1. 上海理工大學(xué) (上海，200093)2. 上海市肺科醫(yī)院 (上海，200433)

目的醫(yī)院在實(shí)施醫(yī)療設(shè)備精細(xì)化健康管理中， 管理系統(tǒng)會(huì)產(chǎn)生大量的日志數(shù)據(jù)， 如何高效利用這些數(shù)據(jù)， 不僅可以為醫(yī)療設(shè)備的健康狀態(tài)進(jìn)行及時(shí)的監(jiān)控， 而且為潛在的隱患提供支持。方法通過(guò)收集血?jiǎng)恿ぷ髡尽?肺功能儀、 彩色多普勒超聲診斷儀等醫(yī)療設(shè)備的運(yùn)行日志， 建立事件日志數(shù)據(jù)庫(kù)， 分別利用Apriori算法和Apriori優(yōu)化算法挖掘醫(yī)療設(shè)備運(yùn)行時(shí)狀態(tài)的關(guān)聯(lián)規(guī)則。結(jié)果Apriori優(yōu)化算法的功能和性能優(yōu)于Apriori算法。結(jié)論Apriori優(yōu)化算法可以為醫(yī)療設(shè)備健康管理提供良好的決策支持。

Apriori算法； 關(guān)聯(lián)規(guī)則； 醫(yī)療設(shè)備健康管理

目前， 隨著現(xiàn)代信息技術(shù)的迅速發(fā)展[1]， 醫(yī)療設(shè)備越來(lái)越智能化、 復(fù)雜化和種類(lèi)多樣化， 不少關(guān)鍵設(shè)備表面上運(yùn)行正常， 但是后臺(tái)日志已經(jīng)產(chǎn)生警告信息， 提示保養(yǎng)、 檢查、 維護(hù)等信息， 如果忽略這類(lèi)信息不做及時(shí)處理， 一定時(shí)間之后極有可能產(chǎn)生更為嚴(yán)重的后果。現(xiàn)有的維修模式是在設(shè)備發(fā)生故障后再進(jìn)行檢查與維修， 這種模式存在一定的被動(dòng)性， 醫(yī)院的設(shè)備是有限的， 而現(xiàn)代診療方式又高度依賴(lài)醫(yī)療設(shè)備的檢查結(jié)果， 所以一旦設(shè)備出現(xiàn)問(wèn)題， 其后果可想而知。當(dāng)前， 多數(shù)有源醫(yī)療設(shè)備都進(jìn)行了實(shí)時(shí)監(jiān)控， 形成了數(shù)據(jù)量龐大的日志形式反映設(shè)備狀態(tài)的各種數(shù)據(jù)及參數(shù)。這些日志中包含了設(shè)備運(yùn)行時(shí)狀態(tài)的各種特征。利用Apriori算法對(duì)醫(yī)療設(shè)備進(jìn)行健康管理， 就是根據(jù)該設(shè)備的運(yùn)行日志， 從大量雜亂無(wú)章的數(shù)據(jù)中找出隱藏在其中的內(nèi)在規(guī)律， 提取出不同健康狀態(tài)特征， 對(duì)其可能的運(yùn)行狀態(tài)進(jìn)行分類(lèi)并對(duì)其趨勢(shì)進(jìn)行預(yù)測(cè)， 并改進(jìn)的Apriori算法以適應(yīng)實(shí)際醫(yī)療設(shè)備健康管理的需要。

1　Apriori算法

為了方便敘述做如下定義[2]：k-項(xiàng)集是含有k個(gè)項(xiàng)的項(xiàng)集集合簡(jiǎn)稱(chēng)。Apriori算法是一種快速挖掘關(guān)聯(lián)規(guī)則的算法， 其算法思想[3]是一個(gè)可以分為兩個(gè)運(yùn)算， 一是合并運(yùn)算， 用于產(chǎn)生最小支持度的集項(xiàng)， 這些集項(xiàng)記為Ck； 二是過(guò)濾運(yùn)算， 數(shù)據(jù)的特點(diǎn)產(chǎn)生過(guò)濾規(guī)則， 對(duì)上一步產(chǎn)生的集項(xiàng)Ck進(jìn)行過(guò)濾得到頻繁項(xiàng)集Lk。Lk即為目標(biāo)關(guān)聯(lián)規(guī)則集合。Apriori算法的實(shí)現(xiàn)過(guò)程是用(k-1)-項(xiàng)集去探索k-項(xiàng)集的迭代過(guò)程。

(1) 合并運(yùn)算。首先將項(xiàng)集中的項(xiàng)按字母順序排序， 然后執(zhí)行運(yùn)算， 產(chǎn)生候選項(xiàng)集集合記為C1。

(2) 過(guò)濾運(yùn)算。由于Ck是Lk的超集， 也即是Ck中的項(xiàng)有可以是頻繁項(xiàng)也有可能不是頻繁項(xiàng)， 因此建立過(guò)濾規(guī)則， 將Ck中的非頻繁的項(xiàng)集都過(guò)濾掉， 剩下的即為頻繁項(xiàng)集。

輸入:DB; min_support。

輸出: L, DB中的頻繁項(xiàng).

方法:

L1=find_frequent1-itemsets(D);

Cr={候選項(xiàng)r-項(xiàng)集}

apriori(DB)

{

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

Ck=apriori_gen (Lk-1);

for each (record r∈DB){ // 掃描DB并作計(jì)數(shù)

Cr=subset(Ck,r); // 獲取子集項(xiàng)r作為候選項(xiàng)集

for each (candidate c∈Cr)

c.count++;

}

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

}

return L=UkLk;

}

函數(shù)apriori_gen用于計(jì)算項(xiàng)集的支持度

apriori_gen(Lk-1) // (k-1)-項(xiàng)集

{

for each(itemset l1∈Lk-1){

for each(itemset l2∈Lk-1){

if (has_subset(l1,l2)){

c=l1*l2; // 合并運(yùn)算生產(chǎn)候選集

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

delete c; // 過(guò)濾運(yùn)算， 刪除不合適的候選項(xiàng)

}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]

}

// 使用先驗(yàn)知識(shí)

//c為k-項(xiàng)集候選項(xiàng);

//Lk-1為(k-1)-項(xiàng)集頻繁項(xiàng)

has_infrequent_subset(c,Lk-1)

{

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

if(s∈Lk-1)

return FALSE;}

return TRUE;

}

Apriori算法是重要的關(guān)聯(lián)規(guī)則挖掘算法。但是其算法流程上存在 多次掃描數(shù)據(jù)庫(kù)和產(chǎn)生大量的候選項(xiàng)集兩個(gè)瓶頸。對(duì)此， 國(guó)內(nèi)外的學(xué)者都提出了不少優(yōu)化辦法來(lái)克服這兩個(gè)瓶頸。文獻(xiàn)[4]提出了動(dòng)態(tài)項(xiàng)集計(jì)數(shù)算法(DIC)， 該算法采用Trie樹(shù)作為項(xiàng)集計(jì)數(shù)的數(shù)據(jù)結(jié)構(gòu)， 最多只要掃描兩次數(shù)據(jù)庫(kù)， 而且產(chǎn)生的候選項(xiàng)集較小， 因此具有較好的效率。文獻(xiàn)[5]提出了采樣算法， 該算法從數(shù)據(jù)源中按照某個(gè)規(guī)則隨機(jī)選取一個(gè)樣本數(shù)據(jù)集， 對(duì)這個(gè)樣本數(shù)據(jù)集挖掘出關(guān)聯(lián)規(guī)則， 然后用數(shù)據(jù)庫(kù)中的其余數(shù)據(jù)驗(yàn)證得到的關(guān)聯(lián)規(guī)則。

文獻(xiàn)[6]提出了劃分挖掘算法， 該采用了劃分的思想， 成功解決內(nèi)存不足的問(wèn)題。

2　Apriori算法優(yōu)化

在醫(yī)療設(shè)備健康管理過(guò)程中對(duì)醫(yī)療設(shè)備的運(yùn)行日志建立事件日志數(shù)據(jù)庫(kù)， 通過(guò)分析發(fā)現(xiàn)該事件日志數(shù)據(jù)庫(kù)存在著一定規(guī)律。利用這些規(guī)律對(duì)Apriori算法進(jìn)行優(yōu)化[7]， 使得優(yōu)化后的算法不再需要多長(zhǎng)掃描數(shù)據(jù)庫(kù)和合并運(yùn)算來(lái)產(chǎn)生頻繁項(xiàng)集， 提高了處理效率， 使得優(yōu)化后的Apriori算法更適合設(shè)備健康管理系統(tǒng)， 能快速地挖掘出有用的規(guī)則。

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中的每個(gè)元素是不是包含Ck

if (u is the subset of x)

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

}

}

}

returnCk;

}

}

3　驗(yàn)證測(cè)試

為了驗(yàn)證Apriori優(yōu)化算法的功能和性能， 設(shè)計(jì)如圖1所示設(shè)備事件日志數(shù)據(jù)庫(kù)作為測(cè)試樣本， 數(shù)據(jù)內(nèi)容包括血?jiǎng)恿ぷ髡尽?肺功能儀、 彩色超聲診斷儀等設(shè)備的運(yùn)行日志。

圖1　測(cè)試數(shù)據(jù)的流程結(jié)構(gòu)圖

將兩個(gè)算法在相同的硬件配置條件：Intel(R) Core i5-6500 3.2 GHz主頻、 8 GB的內(nèi)存、 1 TB硬盤(pán)、 Windows 7操作系統(tǒng)環(huán)境下， 對(duì)Apriori算法和Apriori優(yōu)化算法效率和功能進(jìn)行測(cè)試， 比較Apriori算法和Apriori優(yōu)化算法的運(yùn)行時(shí)間和運(yùn)行結(jié)果輸出， 對(duì)比測(cè)試輸出結(jié)果。Apriori優(yōu)化算法的挖掘結(jié)果包含了在Apriori算法的輸出結(jié)果， 這說(shuō)明Apriori算法挖掘出了大量無(wú)用的關(guān)聯(lián)規(guī)則。Apriori優(yōu)化算法挖掘出的的關(guān)聯(lián)規(guī)則數(shù)量較少， 并且計(jì)算時(shí)間隨著頻繁項(xiàng)項(xiàng)數(shù)的增加而小于Apriori算法。實(shí)驗(yàn)結(jié)果如圖2和圖3所示。

圖2　兩種算法運(yùn)行時(shí)間與Item的數(shù)量關(guān)系

圖2所示的是Apriori算法和Apriori優(yōu)化算法的運(yùn)行時(shí)間與Item的數(shù)量關(guān)系。由圖2可知， Apriori優(yōu)化算法和Apriori算法的計(jì)算時(shí)間隨記錄數(shù)目的增加而隨之增加， 不過(guò)Apriori優(yōu)化算法的增長(zhǎng)幅度較小而趨于平緩， 而Apriori算法隨著頻繁項(xiàng)數(shù)量的增加運(yùn)行時(shí)間而迅速增加。圖3兩個(gè)算法運(yùn)行時(shí)間與最小支持度的關(guān)聯(lián)， 由圖3可知Apriori算法受最小支持度的影響比較大， 計(jì)數(shù)時(shí)間隨著最小支持度提高而降低， 而Apriori優(yōu)化算法比較穩(wěn)定。

圖3　算法運(yùn)行時(shí)間與min_support的關(guān)系

4　結(jié)束語(yǔ)

本文提出了一種Apriori優(yōu)化算法用于醫(yī)療設(shè)備健康管理中的關(guān)聯(lián)規(guī)則挖掘。經(jīng)過(guò)實(shí)驗(yàn)驗(yàn)證， Apriori優(yōu)化算法能夠挖掘出設(shè)備健康情況的關(guān)聯(lián)規(guī)則， 這些關(guān)聯(lián)規(guī)則表明了設(shè)備運(yùn)行參數(shù)與設(shè)備健康狀態(tài)之間的關(guān)系， 為醫(yī)療設(shè)備管理人員更好地管理設(shè)備提供了良好的決策支持。

[1] 周發(fā)超, 王志堅(jiān), 葉楓, 等.關(guān)聯(lián)規(guī)則挖掘算法 Apriori 的研究改進(jìn) [J].計(jì)算機(jī)科學(xué)與探索, 2015, 9(9):1075-1083.

[2] 楊 楠. 基于關(guān)聯(lián)規(guī)則Apriori算法的Web日志挖掘研究與實(shí)現(xiàn) [D]. 成都：成都理工大學(xué),2012.

[3] 羅 可, 賀才望. 基于 Apriori 算法改進(jìn)的關(guān)聯(lián)規(guī)則提取算法[J].計(jì)算機(jī)與數(shù)字工程, 2006,36(4)：48-51..

[4] 楊 斌, 萬(wàn)勝春. 數(shù)據(jù)挖掘在大型醫(yī)療設(shè)備故障診斷中的應(yīng)用研究[J].中國(guó)醫(yī)療設(shè)備, 2007, 22(10):40-43.

[5] 范 明, 孟小峰, 譯. 數(shù)據(jù)挖掘概念與技術(shù) [M]. 北京: 機(jī)械工業(yè)出版社, 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)