韋 哲葉廣健王能才

?

基于頻繁模式增長(zhǎng)算法的2型糖尿病患病風(fēng)險(xiǎn)預(yù)測(cè)的分析研究

韋 哲①②葉廣?、佗谕跄懿泞?/p>

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

［關(guān)鍵詞］數(shù)據(jù)挖掘；Apriori算法；關(guān)聯(lián)規(guī)則；頻繁模式增長(zhǎng)算法；風(fēng)險(xiǎn)分析；糖尿病

韋哲，男，（1963- ），博士，高級(jí)工程師。蘭州軍區(qū)蘭州總醫(yī)院醫(yī)學(xué)工程科、蘭州理工大學(xué)電信學(xué)院，從事醫(yī)學(xué)信息檢測(cè)和處理方面的研究工作。

［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）是由胰島素分泌缺陷和（或）胰島素作用缺陷所引起的，并以慢性高血糖伴碳水化合物、脂肪和蛋白質(zhì)的代謝障礙為特征的慢性疾?。?］。2型糖尿?。╠iabetes mellitus，type 2）又稱為非胰島素依賴型糖尿?。?］。非胰島素依賴型糖尿病的發(fā)病機(jī)制主要是由于人體的胰島素抵抗并胰島素分泌不足所導(dǎo)致的，2型糖尿病患者自身的β細(xì)胞并無(wú)自身免疫性缺陷，其發(fā)病特點(diǎn)是成年發(fā)病，起病比較緩慢，病情也較輕，其比例也占全部糖尿患者的絕大多數(shù)［3-4］。據(jù)統(tǒng)計(jì)，1985年全球糖尿患者有3000萬(wàn)，到1995年這一數(shù)字增長(zhǎng)到1.35億，2000年達(dá)到1.71億，預(yù)測(cè)到2025年將突破3億。龐大的數(shù)字和越來(lái)越快的增長(zhǎng)速度充分表明對(duì)2型糖尿病的研究具有重要的意義［5］。

在挖掘2型糖尿病相關(guān)危險(xiǎn)因素之間關(guān)聯(lián)規(guī)則時(shí)發(fā)現(xiàn)，由于Apriori算法自身的缺陷：①每生成1個(gè)頻繁項(xiàng)集就則須掃描一次數(shù)據(jù)庫(kù)［6］；②由（k-1）頻繁項(xiàng)集生成k項(xiàng)候選項(xiàng)集時(shí)，會(huì)產(chǎn)生許多候選項(xiàng)集，而許多候選項(xiàng)集日后并無(wú)需應(yīng)用，使得2型糖尿病相關(guān)危險(xiǎn)因素的數(shù)據(jù)挖掘等待時(shí)間較長(zhǎng)，執(zhí)行效率較低。本研究針對(duì)2型糖尿病相關(guān)危險(xiǎn)因素關(guān)聯(lián)規(guī)則挖掘數(shù)據(jù)量大、變量屬性眾多等特點(diǎn)，引入一種適用于2型糖尿病相關(guān)危險(xiǎn)因素關(guān)聯(lián)分析的頻繁模式增長(zhǎng)（frequent pattern growth，F(xiàn)P-growth）算法［7］。

1 建立挖掘2型糖尿病相關(guān)危險(xiǎn)因素?cái)?shù)據(jù)規(guī)則

1.1 FP-growth算法

FP-growth算法是一種不產(chǎn)生候選挖掘頻繁項(xiàng)集的，基于頻繁樹（FP-tree）的算法。FP-growth算法采用分治策略，先將提供原始事務(wù)數(shù)據(jù)庫(kù)壓縮到一棵頻繁模式樹（FP-tree）中，且保留項(xiàng)集關(guān)聯(lián)信息，然后將新的數(shù)據(jù)庫(kù)按條件劃分，每個(gè)頻繁項(xiàng)對(duì)應(yīng)一個(gè)條件［8］。

FP-growth算法分為兩個(gè)過(guò)程：①根據(jù)原始事務(wù)數(shù)據(jù)庫(kù)構(gòu)造樹形；②在樹中遞歸挖掘。

（1）FP-growth算法中第一步為經(jīng)典Apriori算法中生成候選項(xiàng)集L1，其產(chǎn)生出基本樹形結(jié)構(gòu)（FP-gree），是FP-growth算法的核心步驟，且為本研究第一次掃描原始數(shù)據(jù)庫(kù)→再一次掃描數(shù)據(jù)庫(kù)，利用每個(gè)事務(wù)中的頻繁項(xiàng)構(gòu)選樹形，找出節(jié)點(diǎn)，按L1規(guī)定的順序加入樹形中。

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

1.2 數(shù)據(jù)挖掘方法

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

1.3 FP-growth算法描述

FP-growth算法首先根據(jù)原始數(shù)據(jù)庫(kù)構(gòu)造FP-tree，然后在FP-tree中挖掘頻繁模式。FP-tree是一種壓縮數(shù)據(jù)結(jié)構(gòu)，由以下3部分構(gòu)成。

（1）FP-tree包含1個(gè)根節(jié)點(diǎn)（null），1個(gè)項(xiàng)目前綴子樹（item prefix subtree）集合作為根節(jié)點(diǎn)的孩子，1個(gè)頻繁項(xiàng)頭表（frequent item header table）。

（2）項(xiàng)前綴子樹中的每個(gè)節(jié)點(diǎn)由項(xiàng)目名、計(jì)數(shù)和節(jié)點(diǎn)鏈3個(gè)域構(gòu)成。分別表示節(jié)點(diǎn)代表的項(xiàng)的名稱，本節(jié)點(diǎn)為止的路徑的事務(wù)數(shù)，指向FP-tree中具有相同項(xiàng)目名的節(jié)點(diǎn)。

（3）頻繁項(xiàng)頭表中每個(gè)條目由項(xiàng)目名和節(jié)點(diǎn)鏈頭2個(gè)域組成。節(jié)點(diǎn)鏈頭指向所有具有相同項(xiàng)目名節(jié)點(diǎn)的第一個(gè)節(jié)點(diǎn)，其FP-growth算法流程如圖1所示。

圖1 FP-growth算法流程圖

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

輸入：事務(wù)數(shù)據(jù)庫(kù)D，按實(shí)際要求設(shè)置最小支持度閾值min_sup

輸出：FP-tree

（1）掃描事務(wù)數(shù)據(jù)庫(kù)D一次，得到頻繁項(xiàng)集和其每個(gè)頻繁項(xiàng)的支持度，并對(duì)頻繁項(xiàng)集合所有頻繁項(xiàng)按其支持度降序排序，得到頻繁項(xiàng)表L；

（2）創(chuàng)建根節(jié)點(diǎn)T，標(biāo)記為（null）；

（3）For事務(wù)數(shù)據(jù)集D中每個(gè)事務(wù)Trans do

（4）對(duì)Trans中所有頻繁項(xiàng)按L排序；

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

（6）調(diào)用insert_tree（［p|P］，T）；

（7）End for

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

輸出：事務(wù)數(shù)據(jù)集D的頻繁項(xiàng)集L；

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

（2）for 路徑P中節(jié)點(diǎn)的每個(gè)組合（記為β） do

①產(chǎn)生項(xiàng)目集β⌒α，其支持度support等于b中節(jié)點(diǎn)的最小支持度數(shù)；

②Return L=L⌒支持度數(shù)大于min_sup的項(xiàng)目集β⌒α

（3）else//包含多個(gè)路徑

①for Tree的頭表中的每個(gè)頻繁項(xiàng)αfdo

②產(chǎn)生一個(gè)項(xiàng)目集β=αf⌒α，其支持度等于αf的支持度；

③構(gòu)造β的條件模式B，并根據(jù)其構(gòu)造β的條件FP-treeβ；

④if Treeβ非空 then

⑤遞歸調(diào)用FP_growth（Treeβ，β）；

⑥end if

⑦end for

⑧end if

（4）產(chǎn)生一個(gè)模式β=αiα，其支持度support =αisupport；

（5）構(gòu)造β的條件模式基，然后構(gòu)造β的條件FP-treeβ；

（6）if Treeβ非空then

（7）調(diào)用FP_growth（Treeβ，β）

2 實(shí)驗(yàn)結(jié)果

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

圖2 兩種算法搜索頻繁項(xiàng)時(shí)間關(guān)系柱狀圖

圖3 兩種算法不同支持度條件下運(yùn)行時(shí)間關(guān)系曲線圖

圖2顯示，當(dāng)對(duì)頻繁1項(xiàng)集進(jìn)行搜索時(shí)，經(jīng)典Apriori算法消耗的時(shí)間，要比FP-growth算法少很多，這是因?yàn)椋笳咴谒阉黝l繁1項(xiàng)集時(shí)，要兩次掃描數(shù)據(jù)庫(kù)，但隨著搜索頻繁項(xiàng)目的長(zhǎng)度增加，F(xiàn)P-growth算法的效率開始要明顯優(yōu)于經(jīng)典Apriori算法，因?yàn)榻?jīng)典算法每次要生成大量無(wú)用候選項(xiàng)集，而FP-grow算法只是在FP-tree這個(gè)極小的數(shù)據(jù)庫(kù)中進(jìn)行遞歸計(jì)算。

圖3表示的是兩種算法在不同支持度閾值條件下，算法效率的對(duì)比。研究發(fā)現(xiàn)，當(dāng)最小支持度要求在4%時(shí)，經(jīng)典算法運(yùn)行時(shí)間要比FP-growth算法高，而隨著支持度減小，F(xiàn)P-growth算法的效率要明顯優(yōu)于經(jīng)典算法。這是因?yàn)?，支持度決定著一個(gè)數(shù)據(jù)庫(kù)搜索出來(lái)的關(guān)聯(lián)規(guī)則的復(fù)雜程度：支持度越小，關(guān)聯(lián)規(guī)則越復(fù)雜。研究表明，F(xiàn)P-grow算法在數(shù)據(jù)維度大、數(shù)據(jù)結(jié)構(gòu)復(fù)雜、數(shù)據(jù)量巨大的數(shù)據(jù)庫(kù)的分析中，要比經(jīng)典算法有優(yōu)勢(shì)。

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

圖4 部分關(guān)聯(lián)規(guī)則挖掘結(jié)果示圖

在圖4中以第一行為例，表示同時(shí)具有＞65歲、WHR高和經(jīng)常醉酒三個(gè)因素的情況下，出現(xiàn)2型糖尿病的概率是67.667%，因此可以得出6個(gè)最高治病性的因素：即年齡＞65歲、高收縮壓、無(wú)運(yùn)動(dòng)、經(jīng)常醉酒、WHR過(guò)高和經(jīng)常高熱飲食。

3 結(jié)論

仿真結(jié)果表明，經(jīng)典Apriori算法［14］在搜索所有滿足條件的頻繁項(xiàng)集時(shí)，生成大量的無(wú)用候選項(xiàng)集，極大的降低了算法的效率，而FP-grow算法能夠有效減少頻繁項(xiàng)的生成數(shù)目，提高算法效率；同時(shí)，在不同支持度條件下，兩種算法的效率也不同：經(jīng)典算法更適用于支持度大，結(jié)構(gòu)較簡(jiǎn)單的數(shù)據(jù)，而FP-growth算法更適用于支持度較低，結(jié)構(gòu)更復(fù)雜的數(shù)據(jù)。

對(duì)糖尿病電子病歷數(shù)據(jù)FP-growth算法的建模，找出了年齡＞65歲、高收縮壓、無(wú)運(yùn)動(dòng)、經(jīng)常醉酒、WHR過(guò)高和經(jīng)常高熱飲食這6種致病程度最高的風(fēng)險(xiǎn)因素，對(duì)輔助預(yù)防2型糖尿病有一定的指導(dǎo)意義。

參考文獻(xiàn)

［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型糖尿及糖尿病腎病的關(guān)系研究［D］.武漢：華中科技大學(xué)，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］王海鵬.我國(guó)診斷糖尿病疾病經(jīng)濟(jì)負(fù)擔(dān)趨勢(shì)預(yù)測(cè)研究［D］.濟(jì)南：山東大學(xué)，2013.

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

［7］白晶.Apriori算法及其在智能小區(qū)用電分析中的應(yīng)用研究［D］.北京：華北電力大學(xué)，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］賈偉平.中國(guó)人2型糖尿病遺傳機(jī)制與個(gè)體化醫(yī)療［J］.醫(yī)學(xué)信息，2014，9，13（9）：726-724.

［12］董會(huì)敏，高秋菊，閆玉英.體重指數(shù)、腰圍預(yù)測(cè)成人高血壓和（或）糖尿病的危險(xiǎn)程度及交互作用分析［J］.鄭州大學(xué)學(xué)報(bào)（醫(yī)學(xué)版），2013，32（6）：678-680.

［13］王超.中國(guó)成人超重和肥胖及主要危險(xiǎn)因素對(duì)糖尿病發(fā)病的影響［D］.北京：北京協(xié)和醫(yī)學(xué)院中國(guó)醫(yī)學(xué)科學(xué)院，2014.

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

①蘭州軍區(qū)蘭州總醫(yī)院醫(yī)學(xué)工程科 甘肅 蘭州 730050

②蘭州理工大學(xué)電信學(xué)院 甘肅 蘭州 730050

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

［文獻(xiàn)標(biāo)識(shí)碼］A

DOI:10.3969/J.ISSN.1672-8270.2016.05.015

作者簡(jiǎn)介

收稿日期：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