朱習(xí)軍，陳亞楠，董國(guó)華

(青島科技大學(xué) 信息科學(xué)技術(shù)學(xué)院,山東 青島　266061)

Apriori改進(jìn)算法在哮喘病案數(shù)據(jù)挖掘中的應(yīng)用

朱習(xí)軍，陳亞楠，董國(guó)華

(青島科技大學(xué) 信息科學(xué)技術(shù)學(xué)院,山東 青島266061)

摘要：中醫(yī)哮喘病案含有大量醫(yī)家臨床診斷獲得的經(jīng)驗(yàn)數(shù)據(jù)，利用數(shù)據(jù)關(guān)聯(lián)分析方法可以挖掘醫(yī)藥方劑配伍規(guī)律及癥狀與用藥之間的關(guān)聯(lián)關(guān)系.文章主要研究了Apriori算法在挖掘醫(yī)案數(shù)據(jù)時(shí)的性能與不足，并基于計(jì)算機(jī)對(duì)位串邏輯運(yùn)算的快速反應(yīng)，提出Apriori算法的改進(jìn)算法——Apriori-BSO算法，并對(duì)比了兩種算法的運(yùn)行時(shí)效，結(jié)合經(jīng)典Apriori算法，挖掘出頻繁項(xiàng)集及強(qiáng)關(guān)聯(lián)規(guī)則.實(shí)驗(yàn)證明,將Apriori改進(jìn)算法應(yīng)用于哮喘用藥數(shù)據(jù)及癥狀-用藥聯(lián)合數(shù)據(jù)進(jìn)行關(guān)聯(lián)分析，挖掘出的醫(yī)藥方劑配伍規(guī)律及癥狀與用藥之間的關(guān)聯(lián)關(guān)系，在哮喘病案數(shù)據(jù)分析中效果良好，應(yīng)用價(jià)值顯著.

關(guān)鍵詞：關(guān)聯(lián)分析；Apriori算法；哮喘；串邏輯運(yùn)算

現(xiàn)實(shí)世界中事物之間通常存在相互依賴或相互關(guān)聯(lián)的關(guān)系，在已經(jīng)知道某事物的情況下，與其有關(guān)聯(lián)或依賴關(guān)系的事物就可以推斷出來，表述事物之間這種關(guān)聯(lián)關(guān)系或依賴關(guān)系的規(guī)則被稱為關(guān)聯(lián)規(guī)則[1].目前關(guān)聯(lián)規(guī)則在不同的領(lǐng)域都有著重要的應(yīng)用，通過多維關(guān)聯(lián)規(guī)則的研究，分析不同月份、不同地區(qū)、不同部門及其他因素對(duì)債務(wù)與收益的影響，是關(guān)聯(lián)規(guī)則在金融領(lǐng)域的重要應(yīng)用；在零售業(yè)中，利用關(guān)聯(lián)分析對(duì)顧客需求、產(chǎn)品銷售、以及產(chǎn)品的趨勢(shì)與時(shí)尚，挖掘規(guī)則進(jìn)而合理搭配、擺放商品，實(shí)現(xiàn)利潤(rùn)最大化；對(duì)電信業(yè)進(jìn)行關(guān)聯(lián)分析，可以幫助掌握商業(yè)動(dòng)向，識(shí)別出是哪種電信模式，捕捉一些盜用行為，從而能更有效地使用現(xiàn)有資源，使服務(wù)的質(zhì)量得以提升.中醫(yī)哮喘病案[2]含有大量醫(yī)家臨床診斷獲得的經(jīng)驗(yàn)數(shù)據(jù)，采用關(guān)聯(lián)分析的方法能將這些數(shù)據(jù)以知識(shí)的形式表述出來，這對(duì)中醫(yī)數(shù)據(jù)客觀化、醫(yī)家經(jīng)驗(yàn)傳承及醫(yī)療研究都有重要的作用[3].本文通過流程圖及實(shí)例分析了經(jīng)典Apriori算法，并提出一種基于位邏輯運(yùn)算的Apriori算法的改進(jìn)算法，即Apriori-BSO算法，將改進(jìn)算法用于哮喘病案數(shù)據(jù)的關(guān)聯(lián)分析中，挖掘出了哮喘診治中的有價(jià)值的數(shù)據(jù)規(guī)則.

1關(guān)聯(lián)規(guī)則基本概念

定義A為一個(gè)由項(xiàng)組成的集合，稱之為項(xiàng)集.若項(xiàng)集A中含有k個(gè)項(xiàng)，那么就稱其為k項(xiàng)集.統(tǒng)計(jì)項(xiàng)集A在事務(wù)數(shù)據(jù)庫D中出現(xiàn)的次數(shù)和事務(wù)數(shù)據(jù)庫D中總事務(wù)的個(gè)數(shù)，用出現(xiàn)次數(shù)除以總事務(wù)數(shù)，即為項(xiàng)集的支持度.如果項(xiàng)集的支持度大于事先設(shè)定的閾值，就稱該項(xiàng)集為頻繁項(xiàng)集.

關(guān)聯(lián)規(guī)則表示事物間的關(guān)聯(lián)關(guān)系，可用類似X?Y的式子來表示，該式中X?I,Y?I并且X∩Y=φ，I為D中所有項(xiàng)的集合.若X∪Y在事務(wù)數(shù)據(jù)庫D中所占的百分比為s%，那么就稱關(guān)聯(lián)規(guī)則X?Y的支持度是s%，事實(shí)上，支持度就是概率值.如果項(xiàng)集X的支持度表示為support(X)，規(guī)則的置信度就用support(X∪Y)/support(X)來表示，實(shí)際上置信度就是一個(gè)條件概率P(Y/X)，支持度與置信度按公式(1)、(2) 計(jì)算.

support(X?Y)=P(X∪Y),

(1)

confidence(X?Y)=P(Y|X),

(2)

也就是說，事物之間的關(guān)系如果滿足了事先設(shè)定的置信度以及支持度，就稱之為關(guān)聯(lián)規(guī)則.

2Apriori及其改進(jìn)算法

2.1　Apriori算法基本思想及性能分析

Apriori算法主要是發(fā)現(xiàn)頻繁項(xiàng)集的過程，事務(wù)中所含頻繁項(xiàng)集僅占一小部分，為避免計(jì)算所有項(xiàng)集的支持度而產(chǎn)生大量的計(jì)算，在Apriori算法中，用已知頻繁項(xiàng)集生成長(zhǎng)度更長(zhǎng)的項(xiàng)集，并將其稱為候選頻繁項(xiàng)集，通過篩選候選頻繁項(xiàng)集得到頻繁項(xiàng)集.生成頻繁項(xiàng)集的過程可依據(jù)以下性質(zhì)：頻繁項(xiàng)集的子集必為頻繁項(xiàng)集.Apriori算法的步驟如下[5].

1)掃描一次數(shù)據(jù)庫D，統(tǒng)計(jì)每個(gè)一項(xiàng)集的支持度計(jì)數(shù)(一個(gè)項(xiàng)集的支持度計(jì)數(shù)是指該項(xiàng)集在數(shù)據(jù)庫中出現(xiàn)的次數(shù))，將滿足最小支持度閾值的一項(xiàng)集加入頻繁一項(xiàng)集L1.

2)連接步.由頻繁(k-1)項(xiàng)集Lk-1中的項(xiàng)進(jìn)行連接操作生成候選k項(xiàng)集，這就是連接步，即JOIN運(yùn)算，具體運(yùn)算情況如下：若p，q∈Lk-1，p={p1,p2,…,pk-2,pk-1},q={q1,q2,…,qk-2,qk-1}，并且當(dāng)1≤i

3)剪枝步.Ck中的項(xiàng)集并不都是是頻繁的，而候選頻繁項(xiàng)集太大會(huì)給算法運(yùn)行帶來很大的計(jì)算開銷，因此有必要對(duì)其進(jìn)行刪減，此時(shí)應(yīng)遵循以下原則：若(k-1)項(xiàng)集不頻繁，那么包含它的k項(xiàng)集必定不是頻繁k項(xiàng)集,所以，當(dāng)候選k項(xiàng)集有不在Lk-1中的(k-1)項(xiàng)集，那么這個(gè)候選k項(xiàng)集不是頻繁的，應(yīng)該把它從Ck中移去.

4)掃描一次數(shù)據(jù)庫D,計(jì)算Ck中各個(gè)項(xiàng)集的支持度.

5)通過對(duì)比支持度閾值，刪除候選k項(xiàng)集Ck中小于支持度閾值的項(xiàng)集，其余項(xiàng)集組成頻繁k項(xiàng)集的集合Lk.

循環(huán)運(yùn)行步驟2)~5)，一直到不能再生成新的頻繁項(xiàng)集集合為止.由以上步驟可以看出,Apriori算法能夠生成所有滿足最小支持度閾值的頻繁項(xiàng)集.

圖1　Apriori算法流程圖

根據(jù)前述Apriori算法的步驟，設(shè)計(jì)算法運(yùn)行流程，見圖1.

由以上算法的運(yùn)行過程可以看出，Apriori算法存在時(shí)間消耗方面的局限性，一是由候選項(xiàng)集產(chǎn)生頻繁項(xiàng)集過程對(duì)海量數(shù)據(jù)庫的多趟掃描；二是用JOIN步產(chǎn)生候選項(xiàng)集時(shí)k-1頻繁項(xiàng)集與k-1頻繁項(xiàng)集的連接需要保證其k-2項(xiàng)是相同的且k-1項(xiàng)不同，這也增加了算法的計(jì)算量，而且連接步產(chǎn)生的候選項(xiàng)集也會(huì)很多，并隨著頻繁1項(xiàng)集的增多而不斷增多，比如說如果頻繁1項(xiàng)集有5個(gè)，那么候選2項(xiàng)集就有10個(gè)，如果頻繁1項(xiàng)集有1000個(gè)，那么候選2項(xiàng)集就有個(gè)，如果頻繁1項(xiàng)集有10 000個(gè)，得到的候選2項(xiàng)集就會(huì)有個(gè)，多達(dá)107個(gè)，這個(gè)計(jì)算量是非常大的.

2.2　改進(jìn)Apriori算法

針對(duì)Apriori算法可能會(huì)多趟掃描數(shù)據(jù)庫與產(chǎn)生大量候選項(xiàng)集方面的問題，基于位串的邏輯運(yùn)算對(duì)其進(jìn)行改進(jìn)，將該改進(jìn)算法記為Apriori-BSO算法.

基于位串邏輯操作的改進(jìn)Apriori算法主要是針對(duì)計(jì)算機(jī)對(duì)位串的快速反應(yīng)，利用數(shù)學(xué)中“位”的概念[7]，把事物數(shù)據(jù)庫D中的每個(gè)事物I用一個(gè)位串來表示.根據(jù)“位”的邏輯運(yùn)算找出項(xiàng)集的支持度計(jì)數(shù)，結(jié)合經(jīng)典Apriori算法，挖掘出頻繁項(xiàng)集及強(qiáng)關(guān)聯(lián)規(guī)則.整個(gè)算法步驟如下.

1)設(shè)定支持度與置信度閾值.

2)掃描數(shù)據(jù)庫，依次對(duì)事務(wù)庫中的每個(gè)項(xiàng)在事務(wù)中出現(xiàn)與否用“1”，“0”表示，若出現(xiàn)則記為“1”，未出現(xiàn)記為“0”，從而將事務(wù)庫中的每個(gè)項(xiàng)在各個(gè)事務(wù)中的出現(xiàn)表示為一組位串.統(tǒng)計(jì)每個(gè)項(xiàng)對(duì)應(yīng)的位串中“1”的個(gè)數(shù)，即為該項(xiàng)的支持度計(jì)數(shù).選取支持度計(jì)數(shù)大于閾值的候選項(xiàng)作為頻繁1項(xiàng)集L1中的項(xiàng).

圖2　Apriori-BSO算法流程圖

3)根據(jù)L1生成項(xiàng)序列S,S={L1中項(xiàng)位串的集合}.對(duì)每個(gè)項(xiàng)編碼，生成編碼位串：編碼長(zhǎng)度為事物庫所含單項(xiàng)的個(gè)數(shù)，如果某個(gè)單項(xiàng)在生成的項(xiàng)集的項(xiàng)中出現(xiàn)，相應(yīng)項(xiàng)序列位置記為“1”，否則為“0”.

4)對(duì)Lk-1進(jìn)行連接操作.對(duì)Lk-1中的項(xiàng)編碼位串依次進(jìn)行邏輯“或”操作，并統(tǒng)計(jì)結(jié)果位串中所含“1”的個(gè)數(shù)，若為k，將加入候選k項(xiàng)集Ck.

5)對(duì)生成Ck中的項(xiàng)對(duì)應(yīng)的Lk-1的項(xiàng)位串進(jìn)行邏輯“與”操作，最終得到的結(jié)果為Ck中對(duì)應(yīng)項(xiàng)的項(xiàng)位串，項(xiàng)位串中“1”的個(gè)數(shù)，即為該候選項(xiàng)的支持度計(jì)數(shù)，將支持度計(jì)數(shù)大于閾值的候選項(xiàng)作為頻繁k項(xiàng)集Lk中的項(xiàng).重復(fù)以上步驟，直到對(duì)Lk所含單項(xiàng)個(gè)數(shù)小于(k+1)，停止算法.

算法運(yùn)行流程如圖2所示.

該算法用到的性質(zhì)如下.

性質(zhì)1：頻繁k項(xiàng)集的子集也必定是頻繁的.

性質(zhì)2： 頻繁k項(xiàng)集中單項(xiàng)的個(gè)數(shù)少于(k+1)則生不成頻繁(k+1)項(xiàng)集.

在相同條件下，使用java語言，采用UCI上提供的大型數(shù)據(jù)集進(jìn)行測(cè)試，Apriori-BSO算法對(duì)比經(jīng)典Apriori算法，其運(yùn)行處理數(shù)據(jù)的時(shí)間對(duì)比結(jié)果如圖3所示.

圖3　Apriori-BSO算法與經(jīng)典Apriori算法運(yùn)行時(shí)間比較

結(jié)果證明，隨著處理數(shù)據(jù)記錄條數(shù)的增加，改進(jìn)算法比經(jīng)典算法的運(yùn)行時(shí)間大幅減少.

3Apriori-BSO算法在醫(yī)藥數(shù)據(jù)挖掘中的應(yīng)用

3.1　中醫(yī)數(shù)據(jù)采集與規(guī)范

本文中所用到的哮喘醫(yī)案數(shù)據(jù)，主要來自青島海慈醫(yī)療集團(tuán)中醫(yī)呼吸科臨床數(shù)據(jù)，如圖4所示.其中共有哮喘醫(yī)案296例.

圖4　青島海慈醫(yī)院中醫(yī)呼吸科臨床數(shù)據(jù)

中醫(yī)醫(yī)案數(shù)據(jù)因其特殊性，存在不少問題和困惑，如病、證、癥、證名等概念模糊，證型診斷標(biāo)準(zhǔn)不規(guī)范，對(duì)某證特異性指標(biāo)的刻意追求，辨證分型不統(tǒng)一等.目前中醫(yī)學(xué)界證名紛雜、各證之間界限不清，出現(xiàn)一證多名、同證異名、以病為證、以證為病的現(xiàn)象.因此，在研究中醫(yī)醫(yī)案數(shù)據(jù)之前，應(yīng)首先規(guī)范醫(yī)案數(shù)據(jù).

文中利用的數(shù)據(jù)挖掘方法主要是通過關(guān)聯(lián)規(guī)則方法尋找中醫(yī)哮喘診治過程中中藥方劑的配伍規(guī)律及癥狀-用藥規(guī)律，因此，涉及到的數(shù)據(jù)有中藥數(shù)據(jù)、癥狀數(shù)據(jù)，本文首先將中藥名字統(tǒng)一化，如中藥“浙貝母”，有的中醫(yī)師習(xí)慣書寫簡(jiǎn)稱“浙貝”，統(tǒng)一為“浙貝母”.將中藥名稱規(guī)范后，把中醫(yī)呼吸科中出現(xiàn)的中藥從1開始編號(hào).通過數(shù)據(jù)庫中條件語句查詢，對(duì)出現(xiàn)在296例哮喘病案數(shù)據(jù)中的中藥編號(hào)并統(tǒng)計(jì)，結(jié)果如表1所示.

表1　哮喘病案中的中藥編號(hào)及統(tǒng)計(jì)數(shù)據(jù)

根據(jù)海慈醫(yī)院的哮喘癥狀分級(jí)量化方案，將哮喘的普通癥狀分級(jí)量化，并對(duì)其編號(hào)，如表2所示.

表2　哮喘普通癥狀編號(hào)表

四診方面的癥狀主要涉及到舌象與脈象及大魚際掌紋陰陽性.對(duì)哮喘病案中出現(xiàn)的舌象信息進(jìn)行分類編號(hào)，如表3所示.

表3　舌象編號(hào)表

根據(jù)哮喘病案中出現(xiàn)的脈象信息對(duì)其分類編號(hào)，如表4所示.

表4　脈象編號(hào)表

大魚際掌紋陰陽性用p表示，p0表示“陰”，p2表示“陽”.

3.2　哮喘醫(yī)案數(shù)據(jù)挖掘

將改進(jìn)算法用于中醫(yī)哮喘醫(yī)藥數(shù)據(jù)挖掘，把支持度閾值設(shè)為35%，置信度閾值設(shè)為75%.用Apriori-BSO算法對(duì)規(guī)范后的中藥數(shù)據(jù)進(jìn)行處理，發(fā)現(xiàn)的頻繁項(xiàng)集及關(guān)聯(lián)規(guī)則如圖4所示.

圖4　頻繁項(xiàng)集及關(guān)聯(lián)規(guī)則結(jié)果圖

根據(jù)圖1中對(duì)應(yīng)的中藥編號(hào)結(jié)合圖4中的處理結(jié)果，得到從中醫(yī)哮喘醫(yī)藥數(shù)據(jù)中挖掘到的關(guān)聯(lián)規(guī)則及其對(duì)應(yīng)的置信度與支持度，見表5.

表5　中醫(yī)哮喘醫(yī)藥數(shù)據(jù)關(guān)聯(lián)關(guān)系　%

從表5中可以得到如下結(jié)論：麻黃、杏仁、射干具有強(qiáng)相關(guān)性，而且通過咨詢專家發(fā)現(xiàn)這個(gè)組合藥對(duì)也是中醫(yī)臨床上常用來治哮喘的組合之一，該結(jié)論是有價(jià)值的.

設(shè)定支持度為15%，置信度為50%，用Apriori-BSO算法對(duì)哮喘用藥與癥狀的關(guān)聯(lián)關(guān)系進(jìn)行挖掘，發(fā)現(xiàn)的關(guān)聯(lián)規(guī)則如表6所示.

表6　中醫(yī)哮喘用藥與癥狀關(guān)聯(lián)關(guān)系　%

從表6中可以得到以下結(jié)論：陳皮對(duì)咯痰癥狀有緩解作用，前胡對(duì)咳嗽癥狀有緩解作用，葶藶子、白果配對(duì)組合對(duì)喘息有緩解作用，葶藶子、蘇子配對(duì)組合對(duì)喘息和胸悶都有緩解作用，葶藶子對(duì)喘息有緩解作用，杏仁對(duì)舌象呈白苔，脈象為浮脈或滑脈都有改善作用，通過與專家溝通也發(fā)現(xiàn)，上述發(fā)現(xiàn)是有價(jià)值的.

4結(jié)語

本文通過分析經(jīng)典Apriori算法的性能與不足，基于計(jì)算機(jī)對(duì)位串邏輯運(yùn)算的快速反應(yīng)，提出Apriori算法的改進(jìn)算法，并在相同條件下對(duì)比了兩種算法的運(yùn)行時(shí)效；將采集到的哮喘醫(yī)案數(shù)據(jù)規(guī)范化并采用改進(jìn)Apriori算法對(duì)哮喘用藥數(shù)據(jù)及癥狀-用藥聯(lián)合數(shù)據(jù)進(jìn)行關(guān)聯(lián)分析，挖掘出了哮喘醫(yī)藥方劑配伍規(guī)律及癥狀與用藥之間的關(guān)聯(lián)關(guān)系，經(jīng)與專家溝通，證實(shí)了挖掘出的規(guī)則是有價(jià)值的.

參考文獻(xiàn)：

[1] 黃穗,劉劍.一個(gè)牙科電子病歷系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[J].計(jì)算機(jī)工程，2004，30(4)：167-169.

[2] 趙霞，汪受傳，韓新民,等.小兒哮喘中醫(yī)診療指南[J].中醫(yī)兒科雜志，2008,4(3):4-6.

[3] 朱文峰.中醫(yī)診斷學(xué)[M].北京:人民衛(wèi)生出版社,1999.

[4] 鄭舞,劉國(guó)萍.常見數(shù)據(jù)挖掘方法在中醫(yī)診斷領(lǐng)域的應(yīng)用概況[J].中國(guó)中醫(yī)藥信息雜志,2013,20(4):103-107.

[5] 李雄飛,李軍.數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)[M].北京:高等敎育出版社,2003.

[6] Brauckhoff D,Dimitropoulos X,Wagner A,et al.Anomalyextraction in backbone networks using association rules[J].IEEE/ACM Transactions on Networking(TON),2012,20(6):1788-1799.

[7] 王偉.關(guān)聯(lián)規(guī)則中的Apriori 算法的研究與改進(jìn)[D].青島:中國(guó)海洋大學(xué),2012.

[8] 李成.智能數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)[M].西安:西安電子科技大學(xué)出版社,2006.

[9] 董國(guó)華,朱習(xí)軍.中醫(yī)肺病科電子病歷系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)[J].軟件,2014,35(3):17-19.

[10] Qian Y,Liang J,Song P,et al.Evaluation of the decision performance of the decision rule set from an ordered decision table[J].Knowledge-based Systems,2012,36:39-50.

(編輯武峰)

中圖分類號(hào)：TP311;R203

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1674-358X(2015)03-0008-07

收稿日期：2015-07-10

基金項(xiàng)目：國(guó)家自然科學(xué)基金項(xiàng)目(51375427)；江蘇省自然科學(xué)基金項(xiàng)目(BK20131232)；江蘇省產(chǎn)學(xué)研聯(lián)合創(chuàng)新資金項(xiàng)目(BY2014117-08)

作者簡(jiǎn)介：曾勵(lì)(1957-)，男，四川威遠(yuǎn)人，教授，博士，碩士生導(dǎo)師，主要從事磁懸浮及控制、無軸承電動(dòng)機(jī)、抽油機(jī)螺桿泵技術(shù)等研究.

The Application of Improved Apriori Algorithm in Axthma Cases Data Mining

ZHU Xijun,CHEN Yanan,DONG Guohua

(College of Information Science and Technology, Qingdao University of Science and Technology, Qingdao 266061,China)

Abstract:TCM asthma case contains a lot of empirical data obtained by physicians in clinical diagnosis,using data correlation analysis methods to mine the rule of medicine prescription compatibility and the incidence relation between symptoms and medication.The article analyzes and studies the performance and disadvantages of Apriori algorithm by examples, and proposes an improved Apriori algorithm called Apriori-BSO algorithm based on the fast response of computer's logic operations in bit strings. Combined with the classic Apriori algorithm,it then compares the running aging of the two algorithms to mine the frequent item sets and strong association rules.The experiments showed that the improved Apriori algorithm is valuable in the data analysis of asthma cases when it is applied to the correlation analysis of asthma medication data and the symptoms-medication data in mining the rule of medicine prescription compatibility and the incidence relation between symptoms and medication.

Key words:correlation analysis; Apriori algorithms; asthma; bit strings operation