劉 藝 張海濤 劉奇燕 石 碩

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

1 引言

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

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

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

2 方法

2.1 FP-growth算法

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

表1 FP-growth算法過程

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

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

2.2 改進FP-growth方法

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

1）基于散列表的改進

散列表（Hash table）這種數據結構可以直接根據鍵（Key）來訪問內存存儲位置。該結構可以通過計算基于關鍵值k的散列函數，將需要查找的數據映射到表中的位置，加快了查找速度［9］。

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

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

2）基于分解數據庫思想的改進

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

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

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

3）基于強關聯規(guī)則左右約束的改進

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

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

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

2.3 方法步驟

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

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

2）分解數據庫

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

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

圖1 鏈表結構圖

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

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

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

3）獲取關聯規(guī)則

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

3 實驗驗證

3.1 實驗數據

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

圖2 體征信息

3.2 預處理

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

1）數據選擇：從所有數據中隨機選擇5517條數據作為實驗數據。

2）數據清洗：去除噪聲，噪聲指的是存在著錯誤或異常的數據，同時去除一些無關數據。

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

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

圖3

3.3 仿真分析

3.3.1 關聯規(guī)則分析

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

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

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

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

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

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

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

3.3.2 算法效率對比

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

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

圖4 算法運行效率對比圖

3.3.3 關聯規(guī)則數量對比

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

圖5為本文改進的FP-growth算法與FP-growth算法使用相同數據進行實驗所得關聯規(guī)則數量的對比?？梢钥闯觯褂梦恢眉s束后的改進算法較原經典算法所生成的關聯規(guī)則數量明顯減少，可有效減少計算量同時避免產生研究所不感興趣的關聯規(guī)則。

圖5 關聯規(guī)則數量對比圖

4 結語

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