黃焯 張維緯

摘要：針對(duì)傳統(tǒng) FP-Growth 算法在大規(guī)模數(shù)據(jù)環(huán)境下挖掘效率低下的問(wèn)題，提出了一種改進(jìn)的 FP-Growth 算法。該算法主要是通過(guò)基于頻繁閉項(xiàng)集策略對(duì)完備模式樹(shù)進(jìn)行剪枝進(jìn)而減小搜索空間規(guī)模，達(dá)到提高算法挖掘效率的目的。并將改進(jìn)后的 FP-Growth 算法的分治策略與分布式計(jì)算框架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

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

1 緒論

在本文中，將采用FP-Growth算法進(jìn)行醫(yī)療大數(shù)據(jù)的挖掘和分析，之所以采用FP-Growth算法，是因?yàn)槠浔華priori算法更加方便，僅需2次掃描數(shù)據(jù)庫(kù)，就能得到用于數(shù)據(jù)分析的頻繁項(xiàng)集等數(shù)據(jù)。為了提高數(shù)據(jù)挖掘的效率，將傳統(tǒng)的算法并行化改進(jìn)后移植到Hadoop平臺(tái)，這是基于云計(jì)算的數(shù)據(jù)挖掘的核心過(guò)程，也是本文的重點(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)的是對(duì)數(shù)據(jù)的壓縮表示。首先分別讀取每一條事務(wù)，將該事務(wù)映射到 FP-tree 上的一條路徑，不同的事務(wù)可能有相同的前項(xiàng)，那么它們?cè)?FP-tree 上的路徑就有可能重合，路徑越重合，表明數(shù)據(jù)壓縮效果越好， FP-tree 構(gòu)造越成功[1]。最理想的情況下就是每一條事務(wù)都完全相同，或者起碼共享相同的前綴，此時(shí)構(gòu)造的 FP-tree 僅包括一條路徑，最不理想的情況是所有事務(wù)都不包含任何相同項(xiàng)，此時(shí) FP-tree 的大小就和事務(wù)數(shù)據(jù)集相同，并沒(méi)有起到壓縮數(shù)據(jù)的作用[2]。

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

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

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

（1） 在第一次遍歷事務(wù)集合T 的同時(shí)創(chuàng)建二維向量，記錄每個(gè)事務(wù)中各個(gè)項(xiàng)兩兩組合出現(xiàn)的支持度計(jì)數(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）是兩個(gè)不同的向量。

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

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

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

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

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

4 代碼編寫(xiě)與算法打包

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

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

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

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

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

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

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

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

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

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

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

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

（7）控制臺(tái)執(zhí)行命令hadoopfs–cat hdfs：//localhost：9000/user/output/result.txt就可以在控制臺(tái)中查看程序執(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

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

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

6 小結(jié)

對(duì)FP-Growth算法進(jìn)行了不足之處的改進(jìn)，在Windows環(huán)境中搭建Hadoop的運(yùn)行環(huán)境，并將算法運(yùn)用到Hadoop分布式中，對(duì)龐大的糖尿病患者數(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-樹(shù)的最大頻繁項(xiàng)目集研究[D]. 哈爾濱：哈爾濱理工大學(xué)，2009.

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