Apriori優(yōu)化算法在臨床數(shù)據(jù)挖掘中的應(yīng)用分析

陳安娜

（漳州衛(wèi)生職業(yè)學(xué)院信息技術(shù)部，福建漳州 363000）

以電子病歷、醫(yī)學(xué)影像、病理參數(shù)、化驗(yàn)結(jié)果等臨床數(shù)據(jù)為基礎(chǔ)建立的醫(yī)學(xué)數(shù)據(jù)庫(kù)是一個(gè)復(fù)雜類(lèi)型數(shù)據(jù)庫(kù)系統(tǒng)，這些臨床信息具有隱私性、多樣性、不完整性、冗余性、異質(zhì)性和缺乏數(shù)學(xué)性質(zhì)的自身特殊性和復(fù)雜性，使得臨床數(shù)據(jù)挖掘與常規(guī)的數(shù)據(jù)挖掘之間存在著較大的差異。關(guān)聯(lián)規(guī)則挖掘是從大量數(shù)據(jù)中發(fā)現(xiàn)項(xiàng)集之間有趣的關(guān)聯(lián)或相關(guān)聯(lián)系，在臨床中常用于疾病相關(guān)因素分析、疾病預(yù)測(cè)等。如何發(fā)現(xiàn)頻繁項(xiàng)集是關(guān)聯(lián)規(guī)則挖掘的核心問(wèn)題，本文提出Apriori改進(jìn)算法，通過(guò)提高發(fā)現(xiàn)頻繁項(xiàng)集的效率，促進(jìn)疾病的診斷與治療。

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

關(guān)聯(lián)規(guī)則挖掘[1]是指從一個(gè)大型事務(wù)數(shù)據(jù)庫(kù)中發(fā)現(xiàn)項(xiàng)集之間所隱藏的有趣的相關(guān)聯(lián)系，即從數(shù)據(jù)集中識(shí)別出頻繁項(xiàng)集，然后利用這些頻繁項(xiàng)集創(chuàng)建描述關(guān)聯(lián)關(guān)系規(guī)則的過(guò)程，產(chǎn)生強(qiáng)關(guān)聯(lián)規(guī)則。

一個(gè)事務(wù)數(shù)據(jù)庫(kù)（事務(wù)集）的關(guān)聯(lián)規(guī)則挖掘描述如下：設(shè)項(xiàng)集I={i1,i2,…,in}，事務(wù)集D={t1,t2,…,tm}，每個(gè)事務(wù)ti（i=1,2,…,m）都是I上的一個(gè)非空子集，每一個(gè)事務(wù)都與一個(gè)唯一的標(biāo)識(shí)符TID(Transaction ID)對(duì)應(yīng)。

關(guān)聯(lián)規(guī)則是一個(gè)項(xiàng)集I的子集組成的蘊(yùn)涵式，即形如A圯B的蘊(yùn)涵式，其中A奐I，B奐I，且A∩B=覫。

支持度s：指A和B這兩個(gè)項(xiàng)集在事務(wù)集D中同時(shí)出現(xiàn)的概率，support(A圯B)=P(A∪B)=|A∪B|/|D|。置信度c：指出現(xiàn)項(xiàng)集A的事務(wù)集D中，項(xiàng)集B也同時(shí)出現(xiàn)的概率，conficence(A圯B)=P(A|B)=P(A∪B)/P(A)。為了發(fā)現(xiàn)有意義的規(guī)則，需要預(yù)先設(shè)定兩個(gè)閾值，即最小支持度（min_sup）和最小置信度（min_conf）。同時(shí)滿足最小支持度和最小置信度的規(guī)則，稱(chēng)為強(qiáng)關(guān)聯(lián)規(guī)則（強(qiáng)規(guī)則）。

2 Apriori算法優(yōu)化

在關(guān)聯(lián)規(guī)則挖掘的整個(gè)過(guò)程中，頻繁項(xiàng)集的產(chǎn)生是核心問(wèn)題。在眾多頻繁項(xiàng)集挖掘算法中，Apriori算法[2]是一種典型的挖掘布爾關(guān)聯(lián)規(guī)則頻繁項(xiàng)集的基本算法。它是利用層次順序搜索的循環(huán)方法來(lái)完成頻繁項(xiàng)集的挖掘工作，首先找出頻繁1-項(xiàng)集L1；然后利用L1來(lái)挖掘頻繁2-項(xiàng)集L2；不斷如此循環(huán)，直到無(wú)法找到更多的頻繁k-項(xiàng)集的集合Lk為止。此算法利用了兩個(gè)基本性質(zhì)：(1)一個(gè)頻繁項(xiàng)集的所有非子集必定也是頻繁的；(2)一個(gè)非頻繁項(xiàng)集的任一超集必定也是非頻繁的。

Apriori算法結(jié)構(gòu)簡(jiǎn)單，易于理解，但由于數(shù)據(jù)庫(kù)的規(guī)模一般都很大，在每進(jìn)行一次迭代的時(shí)候要掃描一次數(shù)據(jù)庫(kù)，多次掃描數(shù)據(jù)庫(kù)導(dǎo)致開(kāi)銷(xiāo)非常大；同時(shí)，在迭代過(guò)程中要在內(nèi)存中產(chǎn)生處理和保存候選頻繁項(xiàng)集，可能產(chǎn)生大量候選項(xiàng)，統(tǒng)計(jì)支持度非常耗時(shí)，從而影響頻繁項(xiàng)集的挖掘效率?，F(xiàn)在基于文獻(xiàn)[5]所給的病人就診數(shù)據(jù)進(jìn)行算法優(yōu)化分析，產(chǎn)生頻繁項(xiàng)集。

2.1 事務(wù)集的布爾矩陣表示

對(duì)于任一給定的事務(wù)集D，令

f：D→R，其中：R=f(D)=(rij)n×m.

這里

于是，事務(wù)集D經(jīng)過(guò)一次掃描后，在f的作用下映射成布爾矩陣R。對(duì)于文獻(xiàn)[5]所給的病人就診數(shù)據(jù)庫(kù)，如表1所示，可映射成圖1所示的布爾矩陣R。

表1 病人就診數(shù)據(jù)表

圖1 布爾矩陣表示就診數(shù)據(jù)庫(kù)

2.2 無(wú)向項(xiàng)集圖的定義與構(gòu)建

2.2.1 無(wú)向項(xiàng)集圖(Undirected itemsets graph，UDISG)

(1)UDISG(V，E)中，V表示結(jié)點(diǎn)集，是數(shù)據(jù)庫(kù)中癥狀和疾病的集合{v1,v2,…vn}，每個(gè)結(jié)點(diǎn)包含結(jié)點(diǎn)名稱(chēng)、結(jié)點(diǎn)出現(xiàn)次數(shù)和指向關(guān)聯(lián)結(jié)點(diǎn)的指針三個(gè)屬性。(2)UDISG（V，E）中，E表示邊集，是邊的集合，包含邊的名稱(chēng)和邊出現(xiàn)次數(shù)兩個(gè)屬性。

2.2.2 構(gòu)建UDISG

設(shè)最小支持度為20%，即每個(gè)頻繁項(xiàng)集至少有2個(gè)以上的支持。(1)掃描矩陣R，R中的每個(gè)項(xiàng)集作為一個(gè)結(jié)點(diǎn)，各項(xiàng)集的支持度計(jì)數(shù)為矩陣行向量之和。構(gòu)成無(wú)向項(xiàng)集圖的結(jié)點(diǎn)必須滿足最小支持度的要求。(2)兩結(jié)點(diǎn)（病狀或疾?。┲g的邊可以通過(guò)矩陣R中對(duì)應(yīng)行向量的運(yùn)算來(lái)確定。當(dāng)結(jié)點(diǎn)A、B對(duì)應(yīng)的行向量按位不為空，且與運(yùn)算所得的行向量之和不小于最小支持度時(shí)，則結(jié)點(diǎn)A、B之間有一條邊存在，A、B對(duì)應(yīng)的矩陣行向量與運(yùn)算后，各位之和就是邊出現(xiàn)的次數(shù)。圖2給出了圖1所示的布爾矩陣而生成的無(wú)向項(xiàng)集圖。邊出現(xiàn)的次數(shù)不小于2，則結(jié)點(diǎn)A與結(jié)點(diǎn)B之間存在一條邊。

圖2 矩陣R生成的UDISG

算法1 構(gòu)建UDISG

輸入：事務(wù)集D，最小支持度min_sup

輸出：UDISG

2.3 基于深度優(yōu)先的無(wú)向項(xiàng)集圖頻繁項(xiàng)集挖掘算法

本算法遍歷無(wú)向項(xiàng)集圖是采用深度優(yōu)先（DFS）[3]搜索策略。過(guò)程描述如下：(1)從圖中的任意一個(gè)結(jié)點(diǎn)vi出發(fā)，搜索UDISG；(2)結(jié)點(diǎn){vi}組成了滿足最小支持度min_sup的頻繁1-項(xiàng)集L1；(3)任意一對(duì)相鄰結(jié)點(diǎn){vi，vj}組成了滿足最小支持度min_sup的頻繁2-項(xiàng)集L2；(4)圖中存在n(n≥3)個(gè)結(jié)點(diǎn)的環(huán)，并且這n個(gè)結(jié)點(diǎn)的所有子集都是頻繁的，則這n個(gè)結(jié)點(diǎn){vi，vj,…,vn}組成了滿足最小支持度min_sup的頻繁n-項(xiàng)集Ln。

算法2 UDISG頻繁項(xiàng)集發(fā)現(xiàn)算法

輸入：UDISG

輸出：頻繁項(xiàng)集L

根據(jù)算法2，可推出圖2中包含的頻繁1-項(xiàng)集L1={S1，S2，A1，A2}；頻繁2-項(xiàng)集L2={{S1，S2}，{S1，A1}，{S1，A2}，{S2，A1}，{S2，A2}}；頻繁3-項(xiàng)集L3={{S1，S2，A1}，{S1，S2，A2}}。

2.4 結(jié)果分析

以上將優(yōu)化的Apriori算法應(yīng)用在文獻(xiàn)[5]給出的病人就診數(shù)據(jù)挖掘的實(shí)例中，產(chǎn)生的頻繁項(xiàng)集與文獻(xiàn)[5]利用基本的Apriori算法產(chǎn)生的頻繁項(xiàng)集結(jié)果一致。與基本的Apriori算法相比，優(yōu)化的Apriori算法有以下優(yōu)點(diǎn)：(1)使用優(yōu)化的Apriori算法只需掃描一次病人就診數(shù)據(jù)庫(kù)，而基本的Apriori算法需要反復(fù)掃描數(shù)據(jù)庫(kù)，在文獻(xiàn)[5]中使用基本的Apriori算法需要對(duì)病人就診數(shù)據(jù)庫(kù)進(jìn)行3次掃描；(2)優(yōu)化的Apriori算法遍歷一次無(wú)向項(xiàng)集圖即可得到新的頻繁項(xiàng)集，因此當(dāng)事務(wù)集和最小支持度發(fā)生變化時(shí)，可以動(dòng)態(tài)生成頻繁項(xiàng)集，而基本的Apriori算法會(huì)產(chǎn)生大量的候選項(xiàng)集。在遍歷圖時(shí)，DFS的時(shí)間復(fù)雜度是由結(jié)點(diǎn)的個(gè)數(shù)、頻繁項(xiàng)集的長(zhǎng)度和鄰接表的長(zhǎng)度決定，因此執(zhí)行時(shí)間要遠(yuǎn)遠(yuǎn)小于基本的Apriori算法。

3 結(jié)語(yǔ)

通過(guò)分析基本的Apriori算法存在的問(wèn)題，從事務(wù)集映射的布爾矩陣出發(fā)，提出了一種基于無(wú)向項(xiàng)集圖UDISG頻繁項(xiàng)集挖掘優(yōu)化算法。利用病人就診數(shù)據(jù)庫(kù)進(jìn)行應(yīng)用分析，比較兩種算法，證明了優(yōu)化算法的有效性，對(duì)臨床數(shù)據(jù)挖掘具有一定的指導(dǎo)作用。

[1]張承江.醫(yī)學(xué)數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘[M].北京:中國(guó)中醫(yī)藥出版社,2008:90-99.

[2]崔雷.醫(yī)學(xué)數(shù)據(jù)挖掘[M].北京:高等教育出版社,2006:47-52.

[3]黃劉生.數(shù)據(jù)結(jié)構(gòu)[M].北京:經(jīng)濟(jì)科學(xué)出版社,2009:100-112.

[4]孔芳,錢(qián)雪忠.關(guān)聯(lián)規(guī)則挖掘?qū)priori算法的一種改進(jìn)研究[J].計(jì)算機(jī)工程與設(shè)計(jì),2008,29(17):138-140.

[5]王華,胡學(xué)鋼.基于關(guān)聯(lián)規(guī)則的數(shù)據(jù)挖掘在臨床上的應(yīng)用[J].安微大學(xué)學(xué)報(bào):自然科學(xué)版,2006,30(2):21-25.

[6]崔貫勛,李梁.關(guān)聯(lián)規(guī)則挖掘中Apriori算法的研究與改進(jìn)[J].計(jì)算機(jī)應(yīng)用,2010,30(11):2952-2955.