Apriori優化算法在臨床數據挖掘中的應用分析

陳安娜

（漳州衛生職業學院信息技術部，福建漳州 363000）

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

1 關聯規則的基本概念

關聯規則挖掘[1]是指從一個大型事務數據庫中發現項集之間所隱藏的有趣的相關聯系，即從數據集中識別出頻繁項集，然后利用這些頻繁項集創建描述關聯關系規則的過程，產生強關聯規則。

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

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

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

2 Apriori算法優化

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

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

2.1 事務集的布爾矩陣表示

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

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

這里

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

表1 病人就診數據表

圖1 布爾矩陣表示就診數據庫

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

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

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

2.2.2 構建UDISG

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

圖2 矩陣R生成的UDISG

算法1 構建UDISG

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

輸出：UDISG

2.3 基于深度優先的無向項集圖頻繁項集挖掘算法

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

算法2 UDISG頻繁項集發現算法

輸入：UDISG

輸出：頻繁項集L

根據算法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 結果分析

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

3 結語

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

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

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

[3]黃劉生.數據結構[M].北京:經濟科學出版社,2009:100-112.

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

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

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