一種Apriori改進算法在2型糖尿病危險因素分析中的應用

韋 哲,葉廣健

（1.蘭州軍區蘭州總醫院，甘肅蘭州，730050；2.蘭州理工大學電信學院，甘肅蘭州,730050）

一種Apriori改進算法在2型糖尿病危險因素分析中的應用

韋 哲1,2,葉廣健2

（1.蘭州軍區蘭州總醫院，甘肅蘭州，730050；2.蘭州理工大學電信學院，甘肅蘭州,730050）

目的：為了提高Apriori算法在2型糖尿病相關危險因素分析中的執行效率。方法：2型糖尿病患者的信息來自蘭州某三甲醫院醫學信息科，包括2009年1月至2014年3月的2型糖尿病患者的首次病程記錄及其健康數據檔案。在研究前人對Apriori算法改進的基礎上，并根據2型糖尿病相關危險因素分析中的需要，提出了一種適用于2型糖尿病相關危險因素分析的Apriori算法改進辦法。最后用C#語言對這兩種算法進行編程，對它們的執行效率做了分析。結果：得到了這兩種算法在頻繁項集與支持度、運行時間與記錄數、運行時間與支持度這三個方面的對比圖。結論：這種改進Apriori算法在2型糖尿病相關危險因素的分析中更有執行效率。

數據挖掘；Apriori算法；關聯規則；算法改進

0 引言

糖尿病（Diabetes Mellitus）是由胰島素分泌缺陷和（或）胰島素作用缺陷所引起的，并以慢性高血糖伴碳水化合物、脂肪和蛋白質的代謝障礙為特征的慢性疾病。2型糖尿病（Type 2 Diabetes Mellitus）主要由胰島素抵抗伴隨相對胰島素分泌不足，或胰島素分泌缺陷伴有或不伴有胰島素抵抗而產生，占糖尿病的90%～95%。近年來隨著世界各國社會經濟發展和居民生活水平的提高，生活方式的改變和人口老齡化，糖尿病患病率在世界范圍內呈上升趨勢，已成為最常見的慢性非傳染性疾病之一。預計到2030年全球成人糖尿病總人數將從2000年的1.71億增長到3.66億，增長1.14倍。因此，對2型糖尿病的研究具有重要的意義。

本課題小組在挖掘2型糖尿病相關危險因素之間關聯規則時發現，由于Apriori算法自身的缺陷：①每生成一個頻繁項集就必須掃描一次數據庫；②由（k-1）頻繁項集生成k項候選項集時，會產生許許多多的候選項集，而這些候選項集很多以后是用不到的，使得2型糖尿病相關危險因素的數據挖掘等待時間較長，執行效率較低。針對2型糖尿病相關危險因素關聯規則挖掘數據量大，數據屬性值眾多等特點，并結合前人對Apriori算法的改進方法，本文提出了一種適用于2型糖尿病相關危險因素關聯分析的Apriori算法。

1 建立挖掘規則

1.1 Apriori算法

Apriori算法是一種逐層搜索迭代用法，用k項集搜索（k+1）項集。首先對數據庫進行掃描，統計每一個項的計數，找出大于等于最小支持度的項集，構成頻繁1項集的集合，記為L1。然后，在L1中搜索頻繁2項集，記為L2，再找L3，如下循環下去，直到不能再找到頻繁項集為止。每一次尋找Lk都要掃描一次數據庫。如前所述，Apriori算法挖掘規則的過程分兩步來實現：

a.找到所有頻繁項集L。

b.從頻繁項集L中提取強關聯規則。

第1步是Apriori算法的關鍵所在，是決定此算法性能是否優良的評價關鍵，第2步相對簡單。目前，Apriori算法改進方法大多也是針對第1步。其主要步驟發現頻繁項集過程又分為兩步：連接步和剪枝步。

(1)連接步：為了找到頻繁項集合Lk，需要連接Lk-1與自己產生連接候選項集k-項集的集合。該候選頻繁項項集合記作Ck。設l1和l2是Lk中的項集。記li[j]表示li的第j項。執行連接過程Lk-1Lk-1，其中要求Lk-1的元素 l1和l2可以連接的，如果：（l1[1]= l2[1]）（l1[2]=l2[2]）…（l1[k-2]=l2[k-2]）（l1[k-1] l2[k-1]），連接l1和l2產生的結果項集是l1[1]，l1[2]……l1[k-1]，l1[k-1]。記號li[j]表示li的第j項。

(2)剪枝步：掃描數據庫，確定Ck中每個候選集的支持度計數。但是，候選集Ck可能很大，為壓縮Ck，可以利用以上算法性質：任何非頻繁項集合的（k-1）-項集都不可能是頻繁項集合k-項集的子集。所以，如果一個候選k-項集的（k-1）項子集不在Lk-1中，則該候選也不可能是頻繁的，因此，從Ck中刪去。

Apriori算法自1994年被R.Agrawal等人提出來以后，在數據挖掘領域得到了廣泛的應用，但是作為第一個關聯規則算法和最經典的關聯規則算法，Apriori算法有其自身的缺點：1)每次生成頻繁項集需要掃描一次數據庫；2)生成許多沒有價值的候選項集。

針對以上兩個缺點，前人提出了很多改進的辦法。文獻[4]提出了基于分片的方法，它的主要改進思路是對于所要求的事務數據庫進行兩次掃描。文獻[5]提出了一個效率高的能夠生成頻繁集的方法，基于雜湊(Hash)的算法。通過實驗我們能夠發現，尋找頻繁項集的主要工作就是生成頻繁2項集的時候，引入雜湊的技術來對頻繁2項集的產生進行了改進。文獻[6]提出了基于采樣的方法，它是基于之前一次掃描事務數據庫時得到的數據，對它進行了詳細的組合以及分析，從中我們可以得到一個改進的辦法，其基本思想是：先采用從事事務數據庫中抽取出來的采樣，得到某些在整個事務數據庫中的一些規則，其中這些規則是可能成立的，然后我們用事務數據庫中剩余的部分去驗證這個規則是否在整個事務庫中都成立。

2 一種適用于2型糖尿病相關危險因素關聯分析的Apriori算法

本課題小組在對2型糖尿病相關危險因素進行數據挖掘的時，從蘭州某三甲醫院醫學信息科提取了3萬余份2型糖尿病患者的首次病程記錄及健康數據檔案。選取了15個相關危險因素，分別為：性別、年齡、文化程度、身體質量指數(BMI)、腰臀比(WHR)、性格、創傷史、飲酒、飲茶、吸煙、睡眠、運動、收入水平、職業、按時三餐。在對這些原始數據進行數據預處理時，我們采取了如下的辦法：以身體質量指數為例，身體質量指數這一項，絕大多數數據都集中在[23，30]之間，可采用等分法劃分以下區間：（0，23]，[24，25]，[26，27]，[28，29]，[30，+]，這5個區間分別對應數字1、2、3、4、5，則BMI這一項可以轉化成如下形式，（0，23]，[24，25]，[26，27]，[28，29]，[30，+]分別對應于B1、B2、B3、B4、B5。最后將這選定的15個相關危險因素轉化為44個屬性值，3萬多個數據44個屬性值，如果采用經典Apriori算法，這個計算量是巨大的，會消很多電腦I/O開銷，并且耗時巨大。對此，本文提出了一種適用于2型糖尿病相關危險因素關聯分析的Apriori算法。

2.1 理論基礎

在對其算法進行改進之前，我們需要了解幾個Apriori算法的相關性質，這能有助于我們更好的對算法進行改進。

性質1：非頻繁項集的超集就一定是非頻繁項集。

性質2：頻繁項集的所有非空子集都是頻繁項集。

性質3：存在一個事物集I， 已知I有著k頻繁項集Lk，如果k頻繁項集Lk可以生成k+1項頻繁集Lk+1，那么必然有著k頻繁項集中項集的個數大于k[7]。

2.2 改進方法

2.2.1 掃描數據庫的改進

掃描數據庫的改進主要是針對經典Apriori算法在生成頻繁項的過程中，每生成一次頻繁項集就必須對數據庫進行一次掃描，將大于等于最小支持度閾值的項集保留，將小于最小支持度閾值的項集剔除這個缺陷。顯然反復掃描數據庫將消耗大量的時間和電腦內存，如果我們減少掃描數據庫的次數，算法的效率將會大大提高。具體的改進辦法如下：

首先，我們需要建立一個二維數組A[m][n]。我們需要對整個事務數據庫的所有項進行統計并排序，使得這些數據有著一定的順序，排序完后對整個事務數據庫進行掃描，對于每個事務里包含的項，我們用1來表示，對于不包含的項，我們用0來表示。然后我們將這些數據都存入之前創建的二維數組當中。存入后，我們再分別求出二維數組里的每列包含1的項的和，得出的結果是1項集的頻繁度。我們再將它與最小支持度進行比較，如果大于或等于最小支持度，那就是頻繁項集，如果小于最小支持度，那就不是頻繁項集，將其刪除。

2.2.2 剪枝步的改進

我們把性質3的思想應用于剪枝步的改進。在經典A即priori算法中運用的是性質2進行剪枝處理，非頻繁項集的超集就一定是非頻繁的，但是應用這樣方法處理完后，生成的候選項集中還是會存在許多冗余的頻繁項集，這樣沒有減少計算量。我們現在應用性質3的方法，先計算|Lk-1(n)|，如果其中存在|Lk-1(n)|k-1的元素，那么就將包含有這些元素的項集刪除，得到一個新的頻繁項集，再與自身連接，得到此時的候選項集的結合。

2.2.3 布爾矩陣的改進

矩陣的改進也同樣采用了性質3的思想。已知一個候選k項集，我們需要對矩陣進行掃描，來得到k頻繁項集，我們在掃描的同時，對矩陣進行壓縮。也就是說我們在計算支持度時，與每列中含有“1”的個數進行對比，如果包含“1”的個數小于或是等于k時，那么我們就將這一行從數組中刪除，等之后再次進行掃描時，我們就無需掃描該行，從而達到了將事務庫進行了縮減，減少了算法掃描數據庫所用的時間，提高了算法的效率。

2.3 算法描述

輸入：交易數據庫D，最小支持度閾值min_sup

輸出：可以產生規則的所有頻繁項集L

(1)Initalzing Arrary(D,A[m][n+1]);

(2)L1=find_frequent_1_itemset(A[m][n]);

(3) for(k=2;Lk-1;k++)｛

(4) Ck=apriori_gen(Lk-1,min_sup);

(5) for each cCk;

(6) for(i=1,in;i++)

(7) if(A[i][C[1]])(A[i][C[2]])…(A[i] [C[k]]

(8) c.count++;

(9)｝

(10)Lk=｛cCk|c.countmin_sup｝;

(11)return L=UkLk

3 實驗結果

為了證實改進的Apriori算法的性能，用C 語言對這兩種

圖1 頻繁項集與支持度的關系

圖2 運行時間與記錄數的關系

圖3 運行時間與支持度的關系

算法進行編程，并用這兩種模型分別對預處理后的2型糖尿病相關危險因素初始集進行數據挖掘，實驗硬件條件為CPU為Intel i5處理器，內存為4G，操作系統為WIN 8系統。分別從頻繁項集與支持度、運行時間與記錄數、運行時間與支持度這三個方面進行考量。實驗結果如下圖1至圖3所示。

[1] Wild S,Roglic G,et al.Global prevalence of diabetes-Estimates for the year 2000 and projections for 2030[J].Diabetes Care,2004,27(5):1047-1053.

[2] 黃曉霞,蕭蘊詩.數據挖掘應用研究及展望[J].計算機輔助工程, 2001: 23-29.

[3] 邵峰晶,于忠清.數據挖掘原理與算法[M].科學出版社, 2009,8:1-2.

[4] Purnami.A new expert system for diabetes disease diagnosis using modified spline smoothsupportvector machine[J].Computational Science and Its Applications,2010,3:83-92.

[5] Rakesh Agrawa,Jerry Kiernan.Water marking Relation Databases.Proceeding of the 28th VLDB Conference,Hong Kong,China,2002.

[6] R.Agrawal,T.Imielinski and A.Swami.Mining association rules between sets of items in large databases[A].In Proc.of the ACM SIGMOD Intl Conf. on Mangagement of Data[C].

[7] 邵峰晶,于忠清.數據挖掘原理與算法[M].北京:中國水利水電出版社,2003

One Apriori Algorithm in the Application of Analyzing Risk Factors of Type 2 Diabetes

Wei Zhe1,2,Ye Guangjian2
(1.Lanzhou General Hospital,Lanzhou Military Area Command, Gansu ,Lanzhou 730050,China；2. School of Electrical Engineering and Information Engineering,Lanzhou University of Technology, Gansu, Lanzhou，730050,China)

Purpose:We do it to improve the efficiency of analyzing risk factors of type 2 diabetes. Method: We use the patients’ data from the information department of one tertiary referral hospital in Lanzhou which include course note of disease and their health record form January 2009 to March 2014.We find out one improved algorithm applies to analyze risk factors of type 2 diabetes based on original Apriori algorithm and it’s requirement.And we analyze the efficiency by programming both of the algorithms with C# .Result: We can analyze the chart of frequent item and support degree,time and number of records,time and support degree. Conclusion: This new improved Apriori algorithm has a high efficiency in analyzing risk factors of type 2 diabetes.

Data mining;Apriori algorithm;Association rules;Algorithm improve