基于頻繁模式增長算法的2型糖尿病患病風險預測的分析研究

韋 哲葉廣健王能才

?

基于頻繁模式增長算法的2型糖尿病患病風險預測的分析研究

韋 哲①②葉廣健①②王能才①

［摘要］目的：分析基于頻繁模式增長（FP-growth）算法的2型糖尿病患病風險預測，避免經典Apriori算法在2型糖尿病相關危險因素分析中執行效率低的缺陷。方法：選取蘭州某醫院醫學信息科2009年1月至2014年3月的2型糖尿病患者的首次病程記錄資料及其健康數據檔案，根據2型糖尿病相關危險因素分析中的需要，引入更適用于2型糖尿病相關危險因素分析的FP-growth算法。采用C#語言對經典Apriori算法和FP-growth算法進行編程，對比分析兩種算法的執行效率。結果：通過對比分析得到兩種算法在運行時間與記錄數據以及運行時間與支持度兩個方面的對比值。結論：FP-growth算法在預測2型糖尿病相關風險因素的分析中執行效率更高，能夠找到更多的糖尿病風險因素。

［關鍵詞］數據挖掘；Apriori算法；關聯規則；頻繁模式增長算法；風險分析；糖尿病

韋哲，男，（1963- ），博士，高級工程師。蘭州軍區蘭州總醫院醫學工程科、蘭州理工大學電信學院，從事醫學信息檢測和處理方面的研究工作。

［First-author’s address］ 1.Lanzhou General Hospital， Lanzhou Military Area Command， Lanzhou， Gansu，730050， China. 2.School of Electrical Engineering and Information Engineering， Lanzhou University of Technology，Gansu， Lanzhou 730050，China.

糖尿病（diabetes mellitus，DM）是由胰島素分泌缺陷和（或）胰島素作用缺陷所引起的，并以慢性高血糖伴碳水化合物、脂肪和蛋白質的代謝障礙為特征的慢性疾病［1］。2型糖尿病（diabetes mellitus，type 2）又稱為非胰島素依賴型糖尿病［2］。非胰島素依賴型糖尿病的發病機制主要是由于人體的胰島素抵抗并胰島素分泌不足所導致的，2型糖尿病患者自身的β細胞并無自身免疫性缺陷，其發病特點是成年發病，起病比較緩慢，病情也較輕，其比例也占全部糖尿患者的絕大多數［3-4］。據統計，1985年全球糖尿患者有3000萬，到1995年這一數字增長到1.35億，2000年達到1.71億，預測到2025年將突破3億。龐大的數字和越來越快的增長速度充分表明對2型糖尿病的研究具有重要的意義［5］。

在挖掘2型糖尿病相關危險因素之間關聯規則時發現，由于Apriori算法自身的缺陷：①每生成1個頻繁項集就則須掃描一次數據庫［6］；②由（k-1）頻繁項集生成k項候選項集時，會產生許多候選項集，而許多候選項集日后并無需應用，使得2型糖尿病相關危險因素的數據挖掘等待時間較長，執行效率較低。本研究針對2型糖尿病相關危險因素關聯規則挖掘數據量大、變量屬性眾多等特點，引入一種適用于2型糖尿病相關危險因素關聯分析的頻繁模式增長（frequent pattern growth，FP-growth）算法［7］。

1 建立挖掘2型糖尿病相關危險因素數據規則

1.1 FP-growth算法

FP-growth算法是一種不產生候選挖掘頻繁項集的，基于頻繁樹（FP-tree）的算法。FP-growth算法采用分治策略，先將提供原始事務數據庫壓縮到一棵頻繁模式樹（FP-tree）中，且保留項集關聯信息，然后將新的數據庫按條件劃分，每個頻繁項對應一個條件［8］。

FP-growth算法分為兩個過程：①根據原始事務數據庫構造樹形；②在樹中遞歸挖掘。

（1）FP-growth算法中第一步為經典Apriori算法中生成候選項集L1，其產生出基本樹形結構（FP-gree），是FP-growth算法的核心步驟，且為本研究第一次掃描原始數據庫→再一次掃描數據庫，利用每個事務中的頻繁項構選樹形，找出節點，按L1規定的順序加入樹形中。

（2）通過遞歸搜索發現一些滿足條件的短模式，并與后綴連接得到長模式［9］。在經典Apriori算法中，連接的定義是：為了找到頻繁項集合Lk，需要連接Lk-1與自己產生連接候選項集k-項集的集合。該候選頻繁項集合記作Ck。設l1和l2是Lk中的項集。記li［j］表示li的第j項。執行連接過程Lk-1∞Lk-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項。同理，在FP-growth算法中，連接是為了找到在某一特定條件下的頻繁項集合。但基于第一步建立的FP-tree，已經不必每一次都掃描原始數據庫，而是搜索條件頻繁項集，條件頻繁項集一般情況要比原始數據庫小很多，這樣就極大降低了搜索開銷，提高了算法的效率［10］。

1.2 數據挖掘方法

本研究在對2型糖尿病相關危險因素進行數據挖掘時，選取蘭州某醫院醫學信息科提取了3萬余份2型糖尿病患者的首次病程記錄及健康數據檔案［11］。選取的相關因素分別為：年齡、性別、收縮壓、舒張壓、血脂、遺傳病史、飲食、腰臀比、吸煙情況、飲酒情況、運動情況、學歷和工作性質［3，12-13］。在對這些原始數據進行數據預處理時，將選定的相關危險因素轉化為34個屬性值，如年齡在＞65歲、40～65歲、＜40歲、高收縮及高舒張壓等。而如此龐大的數據量如果采用經典Apriori算法，其計算量是巨大的，會消耗很多電腦I/O開銷，并且耗時巨大，因此本研究嘗試引入FP-growth算法。

1.3 FP-growth算法描述

FP-growth算法首先根據原始數據庫構造FP-tree，然后在FP-tree中挖掘頻繁模式。FP-tree是一種壓縮數據結構，由以下3部分構成。

（1）FP-tree包含1個根節點（null），1個項目前綴子樹（item prefix subtree）集合作為根節點的孩子，1個頻繁項頭表（frequent item header table）。

（2）項前綴子樹中的每個節點由項目名、計數和節點鏈3個域構成。分別表示節點代表的項的名稱，本節點為止的路徑的事務數，指向FP-tree中具有相同項目名的節點。

（3）頻繁項頭表中每個條目由項目名和節點鏈頭2個域組成。節點鏈頭指向所有具有相同項目名節點的第一個節點，其FP-growth算法流程如圖1所示。

圖1 FP-growth算法流程圖

FP-growth算法的具體描述如下。

輸入：事務數據庫D，按實際要求設置最小支持度閾值min_sup

輸出：FP-tree

（1）掃描事務數據庫D一次，得到頻繁項集和其每個頻繁項的支持度，并對頻繁項集合所有頻繁項按其支持度降序排序，得到頻繁項表L；

（2）創建根節點T，標記為（null）；

（3）For事務數據集D中每個事務Trans do

（4）對Trans中所有頻繁項按L排序；

（5）對排序后的頻繁項表以［p|P］表示，其中p是L第一個元素，而P是頻繁項表中除去p后剩余元素組成的項表；

（6）調用insert_tree（［p|P］，T）；

（7）End for

輸入：FP-tree，項集a（初值為空），最小支持度min_sup；

輸出：事務數據集D的頻繁項集L；

（1）L初值為空；if Tree只包含單個路徑P then

（2）for 路徑P中節點的每個組合（記為β） do

①產生項目集β⌒α，其支持度support等于b中節點的最小支持度數；

②Return L=L⌒支持度數大于min_sup的項目集β⌒α

（3）else//包含多個路徑

①for Tree的頭表中的每個頻繁項αfdo

②產生一個項目集β=αf⌒α，其支持度等于αf的支持度；

③構造β的條件模式B，并根據其構造β的條件FP-treeβ；

④if Treeβ非空 then

⑤遞歸調用FP_growth（Treeβ，β）；

⑥end if

⑦end for

⑧end if

（4）產生一個模式β=αiα，其支持度support =αisupport；

（5）構造β的條件模式基，然后構造β的條件FP-treeβ；

（6）if Treeβ非空then

（7）調用FP_growth（Treeβ，β）

2 實驗結果

（1）為了對比FP-growth算法和經典Apriori算法的性能和效率，用C#語言對這兩種算法進行編程，并用這兩種模型分別對數據平均長度為4，平均頻繁項長度為2，10000條數據（T4I2D10000）的隨機數據庫進行分析，實驗硬件條件為CPU為Intel i5處理器，內存為4 G，操作系統為WIN 8系統。得出經典Apriori算法和FP-growth算法搜索不同長度頻繁項和不同支持度條件下的運行時間對比，如圖2和圖3所示。

圖2 兩種算法搜索頻繁項時間關系柱狀圖

圖3 兩種算法不同支持度條件下運行時間關系曲線圖

圖2顯示，當對頻繁1項集進行搜索時，經典Apriori算法消耗的時間，要比FP-growth算法少很多，這是因為，后者在搜索頻繁1項集時，要兩次掃描數據庫，但隨著搜索頻繁項目的長度增加，FP-growth算法的效率開始要明顯優于經典Apriori算法，因為經典算法每次要生成大量無用候選項集，而FP-grow算法只是在FP-tree這個極小的數據庫中進行遞歸計算。

圖3表示的是兩種算法在不同支持度閾值條件下，算法效率的對比。研究發現，當最小支持度要求在4%時，經典算法運行時間要比FP-growth算法高，而隨著支持度減小，FP-growth算法的效率要明顯優于經典算法。這是因為，支持度決定著一個數據庫搜索出來的關聯規則的復雜程度：支持度越小，關聯規則越復雜。研究表明，FP-grow算法在數據維度大、數據結構復雜、數據量巨大的數據庫的分析中，要比經典算法有優勢。

（2）將FP-growth算法在通用數據挖掘工具SPSS Clementine 12.0進行建模，并對預處理后的2型糖尿病病歷數據進行分析，最小置信度設為40%，前項支持度閾值設為10%，前項數設為3，得到輸出的部分結果如圖4所示。

圖4 部分關聯規則挖掘結果示圖

在圖4中以第一行為例，表示同時具有＞65歲、WHR高和經常醉酒三個因素的情況下，出現2型糖尿病的概率是67.667%，因此可以得出6個最高治病性的因素：即年齡＞65歲、高收縮壓、無運動、經常醉酒、WHR過高和經常高熱飲食。

3 結論

仿真結果表明，經典Apriori算法［14］在搜索所有滿足條件的頻繁項集時，生成大量的無用候選項集，極大的降低了算法的效率，而FP-grow算法能夠有效減少頻繁項的生成數目，提高算法效率；同時，在不同支持度條件下，兩種算法的效率也不同：經典算法更適用于支持度大，結構較簡單的數據，而FP-growth算法更適用于支持度較低，結構更復雜的數據。

對糖尿病電子病歷數據FP-growth算法的建模，找出了年齡＞65歲、高收縮壓、無運動、經常醉酒、WHR過高和經常高熱飲食這6種致病程度最高的風險因素，對輔助預防2型糖尿病有一定的指導意義。

參考文獻

［1］Cho YS，Chen CH，Hu C.Meta-analysis of genome-wide association studies identifies eight new loci for type 2 diabetes in east Asians［J］. Nat Genet，2011，44（1）：67-72.

［2］呂琴.血清尿酸與2型糖尿及糖尿病腎病的關系研究［D］.武漢：華中科技大學，2013.

［3］Chen G，McAlister FA，Walker RL，et al. Cardiovascular outcomes in framingham participants with diabetes：the importance of blood pressure［J］.Hypertension，2011，57（5）：891-897.

［4］Patil BM，Joshi RC，Toshniwal D.Association rule for classification of Type-2 diabetic patients［C］.2010 Second International Conference on Machine Learning and Computing，2010：34-38.

［5］王海鵬.我國診斷糖尿病疾病經濟負擔趨勢預測研究［D］.濟南：山東大學，2013.

［6］Agrawal R.Database Mining：A performance perspective［J］.IEEE Transactions on Knowledge and Data Engineering，1993，5（6）：914-925.

［7］白晶.Apriori算法及其在智能小區用電分析中的應用研究［D］.北京：華北電力大學，2014.

［8］Totad SG，Geeta RG.Batch incremental processing for FP-tree construction using FP-growth algorithm［J］.Knowledge and Information Systems，2012，33（2）：475-490.

［9］Gruca.Improvement of FP-growth algorithm for mining description-oriented rules［C］.3rd International Conference on Man-Machine Inter actions（ICMMI），2014，242：183-192.

［10］H Genther，M Glesner.Automatic generation of a fuzzy classification system using fuzzy clustering methods［C］.Proceedings of the 1994 ACM Symposium on Applied Computing，1994：180-183.

［11］賈偉平.中國人2型糖尿病遺傳機制與個體化醫療［J］.醫學信息，2014，9，13（9）：726-724.

［12］董會敏，高秋菊，閆玉英.體重指數、腰圍預測成人高血壓和（或）糖尿病的危險程度及交互作用分析［J］.鄭州大學學報（醫學版），2013，32（6）：678-680.

［13］王超.中國成人超重和肥胖及主要危險因素對糖尿病發病的影響［D］.北京：北京協和醫學院中國醫學科學院，2014.

［14］韋哲，于啟炟，辛邁，等.基于Apriori算法的高危人群2型糖尿病預測研究［J］.中國醫學裝備，2015，12（1）：45-47.

①蘭州軍區蘭州總醫院醫學工程科 甘肅 蘭州 730050

②蘭州理工大學電信學院 甘肅 蘭州 730050

［文章編號］1672-8270（2016）05-0045-04 ［中圖分類號］ R197.324

［文獻標識碼］A

DOI:10.3969/J.ISSN.1672-8270.2016.05.015

作者簡介

收稿日期：2016-01-17

Analysis for risk factors of type 2 diabetes mellitus based on FP-growth algorithm

WEI Zhe， YE Guang-jian， WANG Neng-cai

China Medical Equipment，2016，13（5）:45-48.

［Abstract］ Objective: We do it to solve the problem of low efficiency in analyzing risk factors of type 2 diabetes mellitus by Apriori Algorithm. Methods: We used 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 found out that the FP-growth algorithm analyzes risk factors of type 2 diabetes better. And we analyzed the efficiency by programming FP-growth and Apriori algorithm with C#. Results: We can analyze the run time and recorded data， time and support degree. Conclusion: The FP-growth algorithm has a higher efficiency in analyzing risk factors of type 2 diabetes mellitus.

［Key words］Data mining； Apriori algorithm； Association rules； FP-growth algorithm； Risk analysis； Diabetes mellitus