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

陳安娜

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

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

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

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

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

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

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

2 Apriori算法優(yōu)化

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

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

2.1 事務集的布爾矩陣表示

對于任一給定的事務集D，令

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

這里

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

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

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

2.2 無向項集圖的定義與構建

2.2.1 無向項集圖(Undirected itemsets graph，UDISG)

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

2.2.2 構建UDISG

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

圖2 矩陣R生成的UDISG

算法1 構建UDISG

輸入：事務集D，最小支持度min_sup

輸出：UDISG

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

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

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

輸入：UDISG

輸出：頻繁項集L

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

2.4 結果分析

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

3 結語

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

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

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

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

[4]孔芳,錢雪忠.關聯(lián)規(guī)則挖掘對Apriori算法的一種改進研究[J].計算機工程與設計,2008,29(17):138-140.

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

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