唐 杰 , 程云章

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

?

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

唐 杰1，2, 程云章1

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

目的醫(yī)院在實施醫(yī)療設(shè)備精細化健康管理中， 管理系統(tǒng)會產(chǎn)生大量的日志數(shù)據(jù)， 如何高效利用這些數(shù)據(jù)， 不僅可以為醫(yī)療設(shè)備的健康狀態(tài)進行及時的監(jiān)控， 而且為潛在的隱患提供支持。方法通過收集血動力工作站、 肺功能儀、 彩色多普勒超聲診斷儀等醫(yī)療設(shè)備的運行日志， 建立事件日志數(shù)據(jù)庫， 分別利用Apriori算法和Apriori優(yōu)化算法挖掘醫(yī)療設(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è)備越來越智能化、 復(fù)雜化和種類多樣化， 不少關(guān)鍵設(shè)備表面上運行正常， 但是后臺日志已經(jīng)產(chǎn)生警告信息， 提示保養(yǎng)、 檢查、 維護等信息， 如果忽略這類信息不做及時處理， 一定時間之后極有可能產(chǎn)生更為嚴(yán)重的后果。現(xiàn)有的維修模式是在設(shè)備發(fā)生故障后再進行檢查與維修， 這種模式存在一定的被動性， 醫(yī)院的設(shè)備是有限的， 而現(xiàn)代診療方式又高度依賴醫(yī)療設(shè)備的檢查結(jié)果， 所以一旦設(shè)備出現(xiàn)問題， 其后果可想而知。當(dāng)前， 多數(shù)有源醫(yī)療設(shè)備都進行了實時監(jiān)控， 形成了數(shù)據(jù)量龐大的日志形式反映設(shè)備狀態(tài)的各種數(shù)據(jù)及參數(shù)。這些日志中包含了設(shè)備運行時狀態(tài)的各種特征。利用Apriori算法對醫(yī)療設(shè)備進行健康管理， 就是根據(jù)該設(shè)備的運行日志， 從大量雜亂無章的數(shù)據(jù)中找出隱藏在其中的內(nèi)在規(guī)律， 提取出不同健康狀態(tài)特征， 對其可能的運行狀態(tài)進行分類并對其趨勢進行預(yù)測， 并改進的Apriori算法以適應(yīng)實際醫(yī)療設(shè)備健康管理的需要。

1　Apriori算法

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

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

(2) 過濾運算。由于Ck是Lk的超集， 也即是Ck中的項有可以是頻繁項也有可能不是頻繁項， 因此建立過濾規(guī)則， 將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并作計數(shù)

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

for each (candidate c∈Cr)

c.count++;

}

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

}

return L=UkLk;

}

函數(shù)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; // 合并運算生產(chǎn)候選集

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

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

2　Apriori算法優(yōu)化

在醫(yī)療設(shè)備健康管理過程中對醫(yī)療設(shè)備的運行日志建立事件日志數(shù)據(jù)庫， 通過分析發(fā)現(xiàn)該事件日志數(shù)據(jù)庫存在著一定規(guī)律。利用這些規(guī)律對Apriori算法進行優(yōu)化[7]， 使得優(yōu)化后的算法不再需要多長掃描數(shù)據(jù)庫和合并運算來產(chǎn)生頻繁項集， 提高了處理效率， 使得優(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中的每個元素是不是包含Ck

if (u is the subset of x)

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

}

}

}

returnCk;

}

}

3　驗證測試

為了驗證Apriori優(yōu)化算法的功能和性能， 設(shè)計如圖1所示設(shè)備事件日志數(shù)據(jù)庫作為測試樣本， 數(shù)據(jù)內(nèi)容包括血動力工作站、 肺功能儀、 彩色超聲診斷儀等設(shè)備的運行日志。

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

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

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

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

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

4　結(jié)束語

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

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

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

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

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

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