基于云平臺MapReduce的Apriori算法研究

邵天會

摘 要 隨著醫(yī)療大數(shù)據(jù)劇增，醫(yī)療數(shù)據(jù)體現(xiàn)的價值更加明顯，而傳統(tǒng)的數(shù)據(jù)分析方案已經(jīng)無法滿足日益增長的數(shù)據(jù)要求，數(shù)據(jù)挖掘技術的更新更加體現(xiàn)出重要性，針對醫(yī)療數(shù)據(jù)挖掘算法的改進優(yōu)化成為瓶頸，Apriori算法進行醫(yī)療數(shù)據(jù)的應用中發(fā)現(xiàn)眾多優(yōu)點，特別是基于興趣度的改進算法，讓醫(yī)療數(shù)據(jù)挖掘體現(xiàn)出更多的價值，并對改進的算法進行MapReduce化進行模型實驗，獲得更多的醫(yī)療價值。

【關鍵詞】云平臺 MapReduce Apriori算法

1 MapReduce工作原理

MapReduce是通過JAVA開發(fā)并簡化了編程模型，讓缺乏相關經(jīng)驗的程序員不需要了解底層，高效的開發(fā)分布式程序。MapReduce對大數(shù)據(jù)并行處理有突出的優(yōu)點，尤其針對超過1TB數(shù)據(jù)更加明顯，主要包括Map （映射）和Reduce （規(guī)約）兩個步驟，中心思想是“任務分解，結果合并”。

2 常見的MapReduce化的Apriori算法

2.1 DD算法（Data Distribution）

CD算法的優(yōu)點是不必要將候選集分布到每個節(jié)點，只要分割原始的事務集，從而掃描事務集的次數(shù)得到極大的降低。CD算法的缺點是隨著節(jié)點數(shù)量的增加，內(nèi)存的浪費也會同比增加。DD算法與CD算法不當節(jié)點數(shù)量不斷增加，消耗的內(nèi)存不斷增長，在進行數(shù)據(jù)處理的過程中，處于事務集和候選集的交互節(jié)點，明顯增加了交互次數(shù)，導致開銷增大。

2.2 CaD 算法（Candidate Distribution）

DD算法的缺點產(chǎn)生原因在于頻繁項集發(fā)生于每次的計算，如果某個節(jié)點出現(xiàn)停滯，其他節(jié)點需要等待，這樣無形中消耗了時間。CaD算法解決了這個問題，在進行第一次計算時，每個節(jié)點通過頻繁項集獨立產(chǎn)生候選集Cm。同時，事務集也被有選擇地分配給各個節(jié)點以獨立計算的計數(shù)。這樣大大減少了候選集對節(jié)點的依賴。

2.3 生成頻繁項算法

具體過程如下：

（1）過InputFormat把事務集劃分N個數(shù)據(jù)塊，每個數(shù)據(jù)塊的格式為（TID，LIST），同時M個節(jié)點進行獨立的運算各自的數(shù)據(jù)塊，格式中的LIST為事務標志TID相對應的項目號。

（2）通過程序Map的執(zhí)行，每個數(shù)據(jù)塊分別生成各自對應的局部候選項集，此時的候選集算法應用經(jīng)典的Apriori算法，然后計算每個局部的候選項集的支持度，并且輸出對應的中間值對。

（3）運行Combiner程序于每個節(jié)點，對每個節(jié)點Map程序的結果進行Combiner合并，然后將每個節(jié)點產(chǎn)生的中間值利用Hash進行分區(qū)，針對不同的分區(qū)執(zhí)行Reduce過程。

（4）將第三步生成的不同分區(qū)的Reduce結果進行候選集支持度求和，進而由局部支持度得到全局支持度。

（5）利用局部支持度和最小支持度的閾值進行比較獲得局部的頻繁項集。

（6）通過把各個局部頻繁項集融合得出全局頻繁項集

（7）迭代重復操作，直到算法完成。

相應的偽代碼：

輸入：事務集分塊后Ti，最小支持度的閾值m-sup；

輸出：相應的頻繁項集I

I=查找頻繁項集（Ti）

i=2；

While（I not null）{

i++；

Ci=apriori算法結果；

for 每個候選集掃描；

Ci=Map（）；}

I=Reduce（）；

Reduce I；

Map程序：

For 每個屬于Ci的I

EmitInter（I ，局部支持度）；

Reduce（I 局部支持度）；

Result 為0；

For 每個屬于Ci 的I；

Result=局部支持度的求和；

Emit（本次的I，result）；

2.4 關聯(lián)規(guī)則算法的發(fā)現(xiàn)

經(jīng)過上述方法獲得頻繁項，進而發(fā)現(xiàn)相應關聯(lián)規(guī)則：

（1）數(shù)據(jù)按照行分塊，即每行對應一個數(shù)據(jù)塊，每個數(shù)據(jù)塊生成一個鍵值對（L，li），L作為偏移量，li為數(shù)據(jù)塊生成的項。

（2）利用Map進行鍵值對掃描，進而生成相對應的關聯(lián)規(guī)則。

（3）對第二部生成的關聯(lián)規(guī)則進行Reduce規(guī)則約束，把結果進行輸出并保存。

（4）把預先設置的閾值和我們生成的關聯(lián)規(guī)則中的置信度進行對比從而得出算法的關聯(lián)規(guī)則。

2.5 實例分析

為了驗證該算法，進行事務集算法實例分析，如表1。

按照改進的算法進行事務集挖掘流程如圖1所示。

由此得出經(jīng)過改進的MapReduce化的Apriori算法實現(xiàn)了頻繁項集的挖掘，得出（{A，B}，{B，C}）為頻繁項集。這僅僅是簡單的事務集挖掘，隨著事務集數(shù)量的增多，結點分配運算的增加，大數(shù)據(jù)挖掘效率提升更加顯著。

參考文獻

[1]http：//Hadoop.apache，org/hdfs.

[2]Amazon simple storage service（Amazon S3）[OL]. http：//aws.amazon.com/s3/，2009.

[3]Amazon simple queuing service （Amazon SQS）[OL].http：//aws.amazon.com/sqs/， 2009.

[4]劉永增，張曉景，李先毅.基于Hadoop/Hive的web日志分析系統(tǒng)的設計[J].廣西大學學報：自然科學版，2011， 36（01）：314-317.

[5]MongoDB官網(wǎng)[DB/0L]，http：//www. Mongodb.org/display/docs/home.

作者單位

吉林醫(yī)藥學院 吉林省吉林市 132013