劉 藝 張海濤 劉奇燕 石 碩

（1.中國海洋大學(xué)信息科學(xué)與工程學(xué)院 青島 266100）（2.云南中煙工業(yè)有限責(zé)任公司技術(shù)中心 昆明 650024）

1 引言

關(guān)聯(lián)規(guī)則挖掘是從大量事務(wù)數(shù)據(jù)庫中發(fā)現(xiàn)事物之間相關(guān)關(guān)系的一個重要課題，主要采用Apriori算法和FP-growth算法兩種經(jīng)典的方法進(jìn)行挖掘［1］。Apriori算法是在由Agrawal等提出的一種經(jīng)典的關(guān)聯(lián)規(guī)則挖掘算法，該算法采用逐層搜索的迭代方法，進(jìn)行多次掃描數(shù)據(jù)庫，從而得到頻繁項集。然而在數(shù)據(jù)量較大時，由于必須多次掃描數(shù)據(jù)庫以及產(chǎn)生大量的候選集，使得算法運行效率較低。隨后J.Han等提出一種FP-growth算法［2］，將數(shù)據(jù)庫壓縮到一棵頻繁模式樹（FP-tree），對于頻繁模式樹進(jìn)行挖掘從而得到頻繁項集。此種算法只需掃描兩次數(shù)據(jù)庫且不會造成大量候選集的出現(xiàn)，較Apriori算法在運算效率以及空間效率上都有一個量級的提升。然而，F(xiàn)P-growth算法仍存在以下的一些問題：構(gòu)造的FP-tree占用空間較大，重復(fù)遞歸產(chǎn)生大量的子樹，對于空間要求很高［3］。

目前關(guān)聯(lián)規(guī)則分析在醫(yī)療領(lǐng)域上應(yīng)用較為廣泛，主要有以下幾個方面的研究：根據(jù)病人的各項數(shù)據(jù)，對患者進(jìn)行分類在此基礎(chǔ)上提取患有某類疾病患者相關(guān)特征，從而輔助醫(yī)生對患者病情的診斷［4］；通過醫(yī)療處方分析找出某類疾病與醫(yī)療處方間關(guān)系，以輔助醫(yī)生開具處方［5］等，但關(guān)聯(lián)規(guī)則對疾病并發(fā)癥的挖掘研究相對較少且缺少與患者體征相結(jié)合的研究［6］。

針對上述問題，本文基于糖尿病患者并發(fā)癥及其體征的相關(guān)統(tǒng)計數(shù)據(jù)，提出一種改進(jìn)FP-growth算法，算法主要結(jié)合散列表、分解數(shù)據(jù)庫的思想以及在提取規(guī)則時增加約束條件，在提高效率的同時，使得產(chǎn)生的規(guī)則與本文所研究內(nèi)容的相關(guān)性更大。該方法能有效地對糖尿病并發(fā)癥進(jìn)行關(guān)聯(lián)規(guī)則的挖掘，獲得糖尿病與高血壓，高脂血癥，冠心病之間并發(fā)的概率，在此基礎(chǔ)上將糖尿病患者結(jié)合體重指數(shù)進(jìn)行分類，挖掘出體重指數(shù)對于糖尿病并發(fā)癥發(fā)病影響的定量關(guān)系，從而為糖尿病三種主要并發(fā)癥的前期預(yù)防提供參考。

2 方法

2.1 FP-growth算法

FP-growth算法主要采用頻繁模式增長的策略進(jìn)行挖掘，將所有數(shù)據(jù)壓縮至一棵FP-tree，從中遞歸的發(fā)現(xiàn)一些短模式，然后與后綴連接。算法主要分為構(gòu)造FP-tree和挖掘FP-tree兩步，如下表1過程所示。

表1 FP-growth算法過程

關(guān)聯(lián)規(guī)則的挖掘是由FP-growth算法挖掘頻繁項集后，從中獲得滿足最小置信度與最小支持度的強(qiáng)關(guān)聯(lián)規(guī)則［7］。

設(shè)A、B分別為事務(wù)中的兩個項集，關(guān)聯(lián)規(guī)則是形如A?B的蘊含式。關(guān)聯(lián)規(guī)則A?B在事務(wù)數(shù)據(jù)庫中成立，具有支持度support(A?B)，A和B同時出現(xiàn)在事務(wù)中的概率即support(A?B)=P(A∪B)。關(guān)聯(lián)規(guī)則A?B在事務(wù)數(shù)據(jù)庫D中的置信度confidence(A?B)，表示事務(wù)在包含A的條件下同時包含B的概率即confidence(A?B)=P(B|A)。

2.2 改進(jìn)FP-growth方法

針對FP-growth算法存在的占用空間大等問題以及醫(yī)療數(shù)據(jù)的特點，本文提出一種基于數(shù)據(jù)庫分解［8］以及規(guī)則約束的方法。主要從以下方面進(jìn)行改進(jìn)：

1）基于散列表的改進(jìn)

散列表（Hash table）這種數(shù)據(jù)結(jié)構(gòu)可以直接根據(jù)鍵（Key）來訪問內(nèi)存存儲位置。該結(jié)構(gòu)可以通過計算基于關(guān)鍵值k的散列函數(shù)，將需要查找的數(shù)據(jù)映射到表中的位置，加快了查找速度［9］。

FP-growth算法挖掘過程中，第二遍掃描事務(wù)數(shù)據(jù)庫時，需要將事務(wù)中的項按照支持度遞減的順序排列，此時需建立頭表用于查詢支持度計數(shù)以便進(jìn)行排序，而頭表通常使用的是順序存儲結(jié)構(gòu)。在查詢某項的支持度計數(shù)時需要從第一項開始遍歷直到遍歷到相關(guān)項為之，效率較低。

基于散列表的思想，不使用順序存儲而是使用散列表作為頭表的存儲結(jié)構(gòu)，并構(gòu)造相應(yīng)的散列函數(shù)，在查詢某項的支持度計數(shù)時，直接通過散列函數(shù)映射到對應(yīng)數(shù)據(jù)位置。較遍歷頭表的方式，基于散列表數(shù)據(jù)結(jié)構(gòu)存儲頻繁項列表，提高查找頻繁項集支持度技術(shù)的效率。

2）基于分解數(shù)據(jù)庫思想的改進(jìn)

將事務(wù)進(jìn)行劃分并存儲于鏈表中，對于劃分后的事務(wù)分別進(jìn)行關(guān)聯(lián)規(guī)則的挖掘，無需建立所有事務(wù)的FP-tree。

在FP-growth算法中所構(gòu)造的FP-tree是將整個數(shù)據(jù)庫中的數(shù)據(jù)壓縮至一棵FP-tree中，基于集成了全部數(shù)據(jù)庫信息的FP-tree進(jìn)行關(guān)聯(lián)規(guī)則的挖掘，生成的FP-tree需求的內(nèi)存較大，且影響算法效率。

基于分級數(shù)據(jù)庫的改進(jìn)方法，采用分治的策略，使用鏈表存儲遍歷整個數(shù)據(jù)庫后的結(jié)果，將事務(wù)中的各項根據(jù)支持度遞減進(jìn)行排序，將排序后的事務(wù)根據(jù)其首項分類，生成各個子數(shù)據(jù)庫，對于各子數(shù)據(jù)庫使用FP-growth算法進(jìn)行數(shù)據(jù)挖掘，提高效率的同時節(jié)省了空間。

3）基于強(qiáng)關(guān)聯(lián)規(guī)則左右約束的改進(jìn)

由挖掘算法獲得頻繁項集后，首先找出頻繁項集的所有非空子集，每兩個子集間生成一個關(guān)聯(lián)規(guī)則，計算所有關(guān)聯(lián)規(guī)則組合的置信度，從中選擇大于最小置信度閾值的規(guī)則即為強(qiáng)關(guān)聯(lián)規(guī)則［10］。

例如由頻繁項集I=｛i1，i3，i5｝，由I所產(chǎn)生的非空子集有｛i1，i3｝，｛i1，i5｝，｛i3，i5｝，｛i1｝，｛i3｝，｛i5｝。由非空子集之間進(jìn)行組合產(chǎn)生該頻繁項集的所有關(guān)聯(lián)規(guī)則，計算每項規(guī)則的置信度，輸出大于閾值的規(guī)則。

在此過程中，產(chǎn)生了多條關(guān)聯(lián)規(guī)則并需要對其進(jìn)行計算，對于本研究中的事務(wù)而言，我們期望得到糖尿病并發(fā)癥相關(guān)的關(guān)聯(lián)規(guī)則，則只需要糖尿病相關(guān)項出現(xiàn)在關(guān)聯(lián)規(guī)則的左部，而其他并發(fā)癥的相關(guān)項只需要出現(xiàn)在關(guān)聯(lián)規(guī)則的右部?；谶@一需求，對于強(qiáng)關(guān)聯(lián)規(guī)則的獲取進(jìn)行改進(jìn)，增加關(guān)聯(lián)規(guī)則左右部的約束，減少產(chǎn)生無趣的關(guān)聯(lián)規(guī)則條數(shù)，同時可減少在生成強(qiáng)關(guān)聯(lián)規(guī)則過程中的計算量，運算效率得到了提升［11］。

2.3 方法步驟

本文主要結(jié)合散列表、數(shù)據(jù)庫分解、關(guān)聯(lián)規(guī)則左右部約束對FP-growth算法進(jìn)行了改進(jìn)，具體步驟如下：

1）第一次掃描數(shù)據(jù)庫D，獲取頻繁1-項集以及事務(wù)中每個項的支持度計數(shù)，按照支持度計數(shù)遞減排列保存于L中，將L存儲于散列表中構(gòu)造相應(yīng)函數(shù) F（k）。

2）分解數(shù)據(jù)庫

（1）第二次掃描數(shù)據(jù)庫D，使用步驟1）中所構(gòu)造的散列函數(shù)F（k）查詢每個事務(wù)中項的支持度計數(shù)，按照支持度計數(shù)遞增進(jìn)行排列，得到數(shù)據(jù)庫記為D1。

（2）掃描數(shù)據(jù)庫D1，依據(jù)L中項的順序，將事務(wù)按照首項分類存儲到鏈表Ki中，含有相同首項的事務(wù)存儲到同一鏈表項下，形成如下圖1所示結(jié)構(gòu)。從中提取所有首項為項 Ii（i=1，2，…，n）的事務(wù)，將這些事務(wù)存儲于鏈表Ki中。

圖1 鏈表結(jié)構(gòu)圖

（3）從鏈表 Ki導(dǎo)出首項為 Ii（i=1，2，…，n-1，n）的事務(wù)，將事務(wù)中的項按照支持度計數(shù)遞減排列生成數(shù)據(jù)庫D2，對于D2使用FP-growth算法步驟進(jìn)行挖掘，輸入數(shù)據(jù)庫D2輸出頻繁項集。

（4）將D2中事務(wù)從數(shù)據(jù)鏈表中刪除，同時刪除D2事務(wù)中的首項，根據(jù)其后繼項將刪除首項的事務(wù)重新添加到數(shù)據(jù)鏈表中。

（5）重復(fù)步驟（3）、（4）直至數(shù)據(jù)鏈表為空。合并每次挖掘的結(jié)果，即為數(shù)據(jù)庫D所有的頻繁項集。

3）獲取關(guān)聯(lián)規(guī)則

從獲得的頻繁關(guān)聯(lián)項中提取關(guān)聯(lián)規(guī)則，在由頻繁關(guān)聯(lián)項生成非空集合時，對所生成關(guān)聯(lián)規(guī)則的左右部進(jìn)行約束。設(shè) F=｛F1，F(xiàn)2，F(xiàn)3｝為事務(wù)中項的約束標(biāo)記，對于事務(wù)中的項設(shè)置三種約束，分別如下：F1表示，項只能出現(xiàn)在關(guān)聯(lián)規(guī)則的左部；F2表示，項只能出現(xiàn)在關(guān)聯(lián)規(guī)則的右部；F3表示，項既可以出現(xiàn)在項的左部又可以出現(xiàn)在項的右部。將事務(wù)中的項根據(jù)需要進(jìn)行相應(yīng)的約束標(biāo)記后計算置信度與支持度，從而獲得關(guān)聯(lián)規(guī)則。

3 實驗驗證

3.1 實驗數(shù)據(jù)

為了驗證本文算法的有效性，同時挖掘糖尿病并發(fā)癥與體重這一體征間的關(guān)聯(lián)規(guī)則，從某醫(yī)療機(jī)構(gòu)采集了患者的相關(guān)個人信息以及部分體征信息?；颊吣挲g集中在50歲～70歲之間，數(shù)據(jù)中記錄了患者患有的疾病及相關(guān)并發(fā)癥（包括：糖尿病、高血壓、高脂血癥、冠心?。┮约安轶w所獲得體征信息具體數(shù)值（包括：體重指數(shù)、收縮壓、舒張壓、空腹血糖、糖化血紅蛋白、總膽固醇、甘油三酯），數(shù)據(jù)結(jié)構(gòu)如圖2所示。從中獲取本實驗所需的數(shù)據(jù)，包括患者所患有的疾病以及并發(fā)癥、體重指數(shù)，經(jīng)過預(yù)處理后進(jìn)行實驗。

圖2 體征信息

3.2 預(yù)處理

由于實驗數(shù)據(jù)存在不規(guī)范等問題，在數(shù)據(jù)挖掘前，針對上述數(shù)據(jù)特點從以下幾個方面進(jìn)行相關(guān)預(yù)處理工作：

1）數(shù)據(jù)選擇：從所有數(shù)據(jù)中隨機(jī)選擇5517條數(shù)據(jù)作為實驗數(shù)據(jù)。

2）數(shù)據(jù)清洗：去除噪聲，噪聲指的是存在著錯誤或異常的數(shù)據(jù)，同時去除一些無關(guān)數(shù)據(jù)。

3）數(shù)據(jù)變換：將數(shù)據(jù)集變量轉(zhuǎn)換成整數(shù)型的數(shù)據(jù)，分別使用數(shù)字1～5代表糖尿病，高血壓，高脂血癥，冠心病，肥胖這五種疾病，將每個患者的患病情況作為一個事務(wù)。本研究選用BMI≥28作為肥胖的標(biāo)準(zhǔn)，而根據(jù)通用標(biāo)準(zhǔn)體重指數(shù)在24～27.9之間則視為超重，在數(shù)據(jù)預(yù)處理中發(fā)現(xiàn)大部分患者屬于超重的狀態(tài)，所以選用一個較高的標(biāo)準(zhǔn)。

本文主要研究糖尿病及其并發(fā)癥的關(guān)聯(lián)規(guī)則，以及肥胖對于并發(fā)癥的影響，因此選用兩組數(shù)據(jù)分別進(jìn)行實驗，經(jīng)過處理的數(shù)據(jù)如圖3（a）（b）所示。圖3（a）包含糖尿病及其三種主要并發(fā)癥，用于研究糖尿病與其并發(fā)癥的關(guān)聯(lián)規(guī)則。圖3（b）包括糖尿病并發(fā)癥及肥胖?jǐn)?shù)據(jù)，用于研究肥胖對于糖尿病并發(fā)癥發(fā)病概率的影響。

圖3

3.3 仿真分析

3.3.1 關(guān)聯(lián)規(guī)則分析

表1、表2為使用本文提出的改進(jìn)的FP-growth算法進(jìn)行挖掘的結(jié)果。由于都定義了最小支持度閾值和最小置信度閾值Minimum Suppport Threshold=0.05，Minimum ConfidenceThreshold=0.1，在關(guān)聯(lián)規(guī)則滿足條件時，才會作為一條關(guān)聯(lián)規(guī)則。此外，本研究還引入了作用度（Lift）作為另外一個標(biāo)準(zhǔn)來提高關(guān)聯(lián)規(guī)則的準(zhǔn)確度。作用度是可信度與期望可信度的比值，其計算公式為Lift(A?B)=P(B/A)P(B)，只有在作用度大于1時，此條規(guī)則才被視為有意義的規(guī)則，即是規(guī)則中兩個事物呈正相關(guān)的關(guān)系。

表2、表3所表示的含義如下：對于關(guān)聯(lián)規(guī)則A?B，Suppport（支持度）表示同時患有多種疾病A和B的概率，Confidence（置信度）表示在患有A種疾病的情況下，同時患有B種疾病的概率。

表2 糖尿病與高血壓、高脂血癥、冠心病關(guān)聯(lián)規(guī)則

表3 糖尿病并發(fā)肥胖與高血壓、高脂血癥、冠心病關(guān)聯(lián)規(guī)則

通過表2糖尿病與高血壓、高脂血癥、冠心病關(guān)聯(lián)規(guī)則可以看出，同時患有糖尿病及高血壓的概率最大Suppport(1?2)=15.896，糖尿病并發(fā)高血壓的概率也是最大Confidence(1?2)=35.840，其次是高脂血癥，再次是冠心病。

通過表3糖尿病并發(fā)肥胖與高血壓、高脂血癥、冠心病關(guān)聯(lián)規(guī)則表示患有肥胖癥的糖尿病患者與其三種并發(fā)癥的患病概率，可以看出，患有高血壓的可能性最大，其次是高脂血癥，再次是冠心病。此結(jié)果與糖尿病并發(fā)癥結(jié)果一致，在此基礎(chǔ)上，研究進(jìn)一步發(fā)現(xiàn)，體重指數(shù)超重的糖尿病患者并發(fā)高血壓、高脂血癥、冠心病的概率均較體重指數(shù)正常的糖尿病患者高。

從實驗結(jié)果來看，肥胖是糖尿病患者并發(fā)高血壓、高脂血癥、冠心病的一個重要危險因素，應(yīng)對此引起重視。

3.3.2 算法效率對比

為了進(jìn)一步驗證本文算法的有效性，與經(jīng)典Apriori算法和FP-growth算法的效率進(jìn)行了對比分析，使用同樣的數(shù)據(jù)，分別設(shè)置最小支持度閾值為2%、4%、6%、8%、10%比較三種算法的運行時間，結(jié)果如圖4所示。

可以看出，如果事務(wù)數(shù)量相等，最小支持度越大，算法的時間效率越高。三種算法對比發(fā)現(xiàn)，在每一個設(shè)置的最小支持度情況下，本文所提出的改進(jìn)算法運行時間最短，F(xiàn)P-growth算法運行時間次之，而Apriori算法的運行時間最長，而且最小支持度越小，算法的運行時間差值越大。由此可見，本文所采用的改進(jìn)的FP-growth算法能夠更加高效地進(jìn)行關(guān)聯(lián)規(guī)則的挖掘。

圖4 算法運行效率對比圖

3.3.3 關(guān)聯(lián)規(guī)則數(shù)量對比

在提高效率的基礎(chǔ)上，本文對關(guān)聯(lián)規(guī)則的輸出進(jìn)行了條件約束，使用如下約束：對于5（肥胖），只能出現(xiàn)在關(guān)聯(lián)規(guī)則的左部，使用F1進(jìn)行約束標(biāo)記；對于2（高血壓），3（高脂血癥），4（冠心病），只能出現(xiàn)在關(guān)聯(lián)規(guī)則的右部，使用F2進(jìn)行約束標(biāo)記；對于1（糖尿?。?，既可以出現(xiàn)在關(guān)聯(lián)規(guī)則的左部，又可以出現(xiàn)在關(guān)聯(lián)規(guī)則的右部，使用F3進(jìn)行標(biāo)記。經(jīng)過改進(jìn)后的算法所得出的關(guān)聯(lián)規(guī)則數(shù)量較原算法有所減少，從而減少了計算量提高算法效率，同時減少不感興趣的規(guī)則的出現(xiàn)，提高了所得關(guān)聯(lián)規(guī)則的有效性。

圖5為本文改進(jìn)的FP-growth算法與FP-growth算法使用相同數(shù)據(jù)進(jìn)行實驗所得關(guān)聯(lián)規(guī)則數(shù)量的對比?？梢钥闯?，使用位置約束后的改進(jìn)算法較原經(jīng)典算法所生成的關(guān)聯(lián)規(guī)則數(shù)量明顯減少，可有效減少計算量同時避免產(chǎn)生研究所不感興趣的關(guān)聯(lián)規(guī)則。

圖5 關(guān)聯(lián)規(guī)則數(shù)量對比圖

4 結(jié)語

本文在經(jīng)典FP-growth算法的基礎(chǔ)上，提出一種更為高效的改進(jìn)FP-growth算法，該算法對關(guān)聯(lián)規(guī)則的產(chǎn)生進(jìn)行了約束，增強(qiáng)了所產(chǎn)生規(guī)則的有效性，提高了運行效率。在對于糖尿病及主要并發(fā)癥（高血壓、高脂血癥、冠心?。╆P(guān)聯(lián)規(guī)則挖掘的基礎(chǔ)上，進(jìn)一步研究了患有肥胖癥的糖尿病患者與其主要并發(fā)癥之間的發(fā)病率關(guān)系，為糖尿病并發(fā)癥的預(yù)防診斷等提供了一定的參考性，同時本研究發(fā)現(xiàn)肥胖對于糖尿病并發(fā)癥發(fā)病率有顯著影響，這對于醫(yī)務(wù)人員以及患者都有一定的參考價值。