基于hadoop與醫(yī)療大數(shù)據(jù)的FP—Growth算法的優(yōu)化研究

黃焯 張維緯

摘要：針對傳統(tǒng) FP-Growth 算法在大規(guī)模數(shù)據(jù)環(huán)境下挖掘效率低下的問題，提出了一種改進(jìn)的 FP-Growth 算法。該算法主要是通過基于頻繁閉項(xiàng)集策略對完備模式樹進(jìn)行剪枝進(jìn)而減小搜索空間規(guī)模，達(dá)到提高算法挖掘效率的目的。并將改進(jìn)后的 FP-Growth 算法的分治策略與分布式計算框架Hadoop的MapReduce編程模式有機(jī)結(jié)合，進(jìn)一步提高了大數(shù)據(jù)環(huán)境下的挖掘效率。實(shí)驗(yàn)證明，基于Hadoop的改進(jìn) FP-Growth 算法的效率較傳統(tǒng) FP-Growth 算法有所提高。

關(guān)鍵詞：數(shù)據(jù)挖掘關(guān)聯(lián)規(guī)則；FP-Growth；HadoopMapReduce

中圖分類號：TP314 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2018）14-0001-02

1 緒論

在本文中，將采用FP-Growth算法進(jìn)行醫(yī)療大數(shù)據(jù)的挖掘和分析，之所以采用FP-Growth算法，是因?yàn)槠浔華priori算法更加方便，僅需2次掃描數(shù)據(jù)庫，就能得到用于數(shù)據(jù)分析的頻繁項(xiàng)集等數(shù)據(jù)。為了提高數(shù)據(jù)挖掘的效率，將傳統(tǒng)的算法并行化改進(jìn)后移植到Hadoop平臺，這是基于云計算的數(shù)據(jù)挖掘的核心過程，也是本文的重點(diǎn)和難點(diǎn)。

2 FP-Growth 算法

FP-Growth 算法使用 FP-tree 直接發(fā)現(xiàn)頻繁項(xiàng)集，避免了候選項(xiàng)集的產(chǎn)生環(huán)節(jié)。

算法原理：算法的第一步是構(gòu)造一棵 FP-tree， FP-tree 體現(xiàn)的是對數(shù)據(jù)的壓縮表示。首先分別讀取每一條事務(wù)，將該事務(wù)映射到 FP-tree 上的一條路徑，不同的事務(wù)可能有相同的前項(xiàng)，那么它們在 FP-tree 上的路徑就有可能重合，路徑越重合，表明數(shù)據(jù)壓縮效果越好， FP-tree 構(gòu)造越成功[1]。最理想的情況下就是每一條事務(wù)都完全相同，或者起碼共享相同的前綴，此時構(gòu)造的 FP-tree 僅包括一條路徑，最不理想的情況是所有事務(wù)都不包含任何相同項(xiàng)，此時 FP-tree 的大小就和事務(wù)數(shù)據(jù)集相同，并沒有起到壓縮數(shù)據(jù)的作用[2]。

產(chǎn)生 FP-tree 后，第二步， FP- Growth算法從底向上探索整棵樹，由 FP-tree產(chǎn)生頻繁項(xiàng)集。 FP- Growth算法不同于Apriori算法，Apriori算法產(chǎn)生的頻繁項(xiàng)集時先產(chǎn)生頻繁 1-項(xiàng)集，然后是頻繁 2-項(xiàng)集，頻繁 3-項(xiàng)集等等。 FP- Growth算法按照結(jié)尾項(xiàng)進(jìn)行頻繁項(xiàng)集的尋找，采用分治策略，將尋找頻繁項(xiàng)集這個大問題劃分為尋找以某個特定項(xiàng)結(jié)尾的所有頻繁項(xiàng)集這樣一個個小問題，進(jìn)而得到解決[3]。

3 改進(jìn) FP-Growth 算法

針對FP-Growth 算法的缺點(diǎn)，對經(jīng)典算法進(jìn)行改進(jìn)，提出使用支持度計數(shù)二維表的方法，從而省去經(jīng)典算法對條件模式基的第一次遍歷，具體算法描述為：

（1） 在第一次遍歷事務(wù)集合T 的同時創(chuàng)建二維向量，記錄每個事務(wù)中各個項(xiàng)兩兩組合出現(xiàn)的支持度計數(shù)。如有事務(wù)“A，B，C，D”，則二維向量表中（A，B）（A，C）、（A，D）、（B，C）、（B，D）、（C，D）項(xiàng)都需要加1。其中向量（C，B）和（B，C）是兩個不同的向量。

（2）利用遞歸方式創(chuàng)建α條件下（ α≠{Null}）的條件FP 子樹時，無須兩次遍歷條件模式基（其中第一次遍歷條件模式基可得到支持度計數(shù)列表，第二次遍歷條件模式基可插入樹節(jié)點(diǎn)從而創(chuàng)建FP 樹）。支持度計數(shù)列表可以從支持度計數(shù)二維向量列表中獲得。抽取二維向量表中的與Ei相關(guān)的行、列值，將對應(yīng)行列值相加即可得到條件α下，Ei與其他項(xiàng)的支持度計數(shù)。其中Ei為當(dāng)前項(xiàng)。

（3）遍歷條件模式基，創(chuàng)建FP 子樹的同時創(chuàng)建新的支持度計數(shù)二維向量表。例如表1 所示的事務(wù)集合T，要求min_Sup=25%，由此可得支持度計數(shù)最小為5（17×25%= 4.25）。根據(jù)經(jīng)典算法中的原則，遍歷一次事務(wù)集合T 可獲得項(xiàng)頭表如表2 所示。本改進(jìn)點(diǎn)在此遍歷中需要多做一項(xiàng)工作，即生成支持度計數(shù)二維向量表。首先創(chuàng)建如表3 所示的空二維向量表1。另外將二維表中的所有相關(guān)項(xiàng)對計數(shù)值初始化為0。在第一次遍歷事務(wù)集合時，對于T1 需要更新其在項(xiàng)頭表中的頻繁度計數(shù)。同時獲取T1 的所有兩兩項(xiàng)組合：{A，F(xiàn)}。T1 中只有一個符合條件的組合，將該組合對應(yīng)的計數(shù)值加1。用同樣的方式處理T2、T3等事務(wù)。T15 中包含的項(xiàng)集對有{A，B}{A，C}{A，D}{B，D}{C，D}，故對應(yīng)于此6 個組合的項(xiàng)對支持度計數(shù)也需要加1。用同樣的方式處理T16、T17，最終可獲得表3所示的支持度計數(shù)二維列表[4]。

此支持度計數(shù)二維列表中記錄了所有項(xiàng)兩兩組合在事務(wù)集合中出現(xiàn)的頻率。由于算法不關(guān)心支持度計數(shù)小于特定值的，因此在獲得該表后需要對其進(jìn)行必要的刪減。根據(jù)支持度計數(shù)列表顯示，F(xiàn) 項(xiàng)、G 項(xiàng)、H 項(xiàng)是不滿足min_Sup的項(xiàng)不在算法考慮范圍內(nèi)，故刪除與此3 項(xiàng)相關(guān)的支持度計數(shù)二維表中的行與列。調(diào)整后的支持度計數(shù)二維表如表4 所示。

由于E為有效支持度計數(shù)列表中最小的項(xiàng)，故首先增長為{E}，從調(diào)整后的支持度計數(shù)二維表中提取與E 相關(guān)的所有行列可見{A，E}：2+0、{B，E}：1+0、{C，E}：0+0、{D，E}：4+0。由此無須遍歷所有事務(wù)集合可得到α條件下的支持度計數(shù)表為L_E={D：4，A：2，B：1，C：0}。

當(dāng)α增長為{D}時，獲取支持度計數(shù)二維表中第4 行與第4 列關(guān)于D 的所遇支持度計數(shù)信息可得α條件下支持度計數(shù)表為L_D={E：0+4，A：4+0，B：2+0，C：1+0}，同樣無須遍歷海量事務(wù)集合T 即可得到α條件下支持度計數(shù)的所有信息。

4 代碼編寫與算法打包

本研究中使用Eclipse集成開發(fā)環(huán)境進(jìn)行代碼的編寫，Hadoop平臺內(nèi)置了分詞和計數(shù)的程序，只需要將輸入文件存放到指定輸入目錄中，以的方式將輸入文件通過代碼簡單設(shè)置，就可以通過Hadoop內(nèi)置計數(shù)程序執(zhí)行得到需要的結(jié)果。

由于Hadoop內(nèi)置計數(shù)程序默認(rèn)是讀取.txt文件，可以很好地得到計數(shù)結(jié)果，但該論文中研究對象為糖尿病患者數(shù)據(jù)集，數(shù)量多達(dá)10W條，存放方式以Excel文件的方式保存，不能被內(nèi)置計數(shù)程序直接讀取，所以需要編寫一個轉(zhuǎn)換程序，將Excel文件中的數(shù)據(jù)轉(zhuǎn)換成內(nèi)置計數(shù)程序可以識別的類型。

將通過工具類獲取到的Excel數(shù)據(jù)作為規(guī)則關(guān)聯(lián)算法的原始數(shù)據(jù)，進(jìn)行頻繁項(xiàng)集的挖掘，應(yīng)用到改進(jìn)的FP-Growth算法中。

最后將編寫好的工程打包為.jar的Java執(zhí)行文件，拷貝到Hadoop工作空間目錄中，同時將Excel數(shù)據(jù)文件拷貝到輸入目錄中，輸入對應(yīng)的命令即可進(jìn)行分布式計算。

5 實(shí)驗(yàn)過程和實(shí)驗(yàn)結(jié)果

本實(shí)驗(yàn)中的原始數(shù)據(jù)來源于http：//archive.ics.uci.edu/ml/datasets/Diabetes+130-US+hospitals+for+years+1999-2008美國130家醫(yī)院1999-2008年的10W條糖尿病數(shù)據(jù)集。在該原始數(shù)據(jù)中，每條數(shù)據(jù)包含屬性50多個，經(jīng)過數(shù)據(jù)預(yù)處理之后，將最終的數(shù)據(jù)屬性保留在11個，分別是max_glu_serum（最大葡萄糖血清）、A1Cresult（A1C測試結(jié)果）、metformin（二甲雙胍）、glimepiride（格列美脲）、glipizide（格列吡嗪）、glyburide（格列本脲）、rosiglitazone（羅格列酮）、insulin（胰島素）、change（糖尿病藥物是否有變化）、diabetesMed（是否有任何糖尿病藥物處方）、readmitted（重新入院的日子）。將處理之后的文件以Excel文件保存至本地磁盤中，下面將詳細(xì)描述實(shí)驗(yàn)步驟。

（1）通過編寫預(yù)處理算法對原始數(shù)據(jù)進(jìn)行預(yù)處理，將算法中的文件輸入路徑和輸出路徑設(shè)置為正確路徑即可。

（2）運(yùn)行本地cmd控制臺，進(jìn)入到hadoop目錄中，通過start-all.cmd命令啟動hadoop，打開瀏覽器輸入：localhost：50070進(jìn)入到hadoop文件管理系統(tǒng)。

（3）輸入命令hadoopfs –put D：＼datas.xls hdfs：//localhost：9000/user/wcinput將處理后的數(shù)據(jù)文件上傳到hadoop的文件系統(tǒng)中

（4）將編寫好的關(guān)聯(lián)規(guī)則改進(jìn)FP-Growth算法打包為fpgrowth.jar文件，放到hadoop工作空間的workplace/test目錄下。

（5）通過控制臺進(jìn)入到工作空間workplace/test目錄下，執(zhí)行命令hadoop–jar fpgrowth.jar hdfs：//localhost：9000/user/wcinput/datas.xls hdfs：//localhost：9000/user/output

（6）通過瀏覽器可以查看當(dāng)前hadoop文件系統(tǒng)中，輸出路徑下多出一個result.txt文件，改文件則是算法最終執(zhí)行結(jié)果

（7）控制臺執(zhí)行命令hadoopfs–cat hdfs：//localhost：9000/user/output/result.txt就可以在控制臺中查看程序執(zhí)行結(jié)果。

diabetesMed--Yes：readmitted-->30， diabetesMed--Yes

insulin--Steady：diabetesMed--Yes， insulin--Steady

readmitted-->30， insulin--Steady

diabetesMed--Yes， readmitted-->30， insulin--Steady

metformin--Steady：diabetesMed--Yes， metformin--Steady

readmitted--<30：diabetesMed--Yes， readmitted--<30

change--Ch：diabetesMed--Yes， change--Ch

readmitted-->30， change--Ch

diabetesMed--Yes， readmitted-->30， change—Ch

通過改進(jìn)的FP-Growth算法求出的頻繁項(xiàng)集清晰的打印在控制臺中，可以明確地看出有糖尿病處方藥及胰島素狀態(tài)為Steady的患者和有糖尿病處方藥及糖尿病藥物發(fā)生變化的患者將有很大風(fēng)險在30天后再次入院；若只有又糖尿病處方藥的患者，則有風(fēng)險在30天內(nèi)再次入院。

該實(shí)驗(yàn)結(jié)果達(dá)到了預(yù)期目標(biāo)：挖掘糖化血紅蛋白測量對醫(yī)院再入院率的影響。

6 小結(jié)

對FP-Growth算法進(jìn)行了不足之處的改進(jìn)，在Windows環(huán)境中搭建Hadoop的運(yùn)行環(huán)境，并將算法運(yùn)用到Hadoop分布式中，對龐大的糖尿病患者數(shù)據(jù)進(jìn)行挖掘處理，最終得到挖掘結(jié)果，完成了預(yù)期目標(biāo)。

參考文獻(xiàn)：

[1] 蘇沖.基于最大頻繁項(xiàng)集的搜索引擎查詢結(jié)果聚類方法[D].哈爾濱：哈爾濱工業(yè)大學(xué)，2009.

[2] 王越.分布式關(guān)聯(lián)規(guī)則挖掘的方法研究[D].重慶：重慶大學(xué)，2003.

[3] 朱孟杰.基于改進(jìn)FP-樹的最大頻繁項(xiàng)目集研究[D]. 哈爾濱：哈爾濱理工大學(xué)，2009.

[4] 楊云.FP-Growth算法的改進(jìn)[J] .計算機(jī)工程與設(shè)計，2010，31（7） ：1506-1509.