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

邵天會

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

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

1 MapReduce工作原理

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

2 常見的MapReduce化的Apriori算法

2.1 DD算法（Data Distribution）

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

2.2 CaD 算法（Candidate Distribution）

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

2.3 生成頻繁項算法

具體過程如下：

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

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

（3）運行Combiner程序于每個節點，對每個節點Map程序的結果進行Combiner合并，然后將每個節點產生的中間值利用Hash進行分區，針對不同的分區執行Reduce過程。

（4）將第三步生成的不同分區的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 關聯規則算法的發現

經過上述方法獲得頻繁項，進而發現相應關聯規則：

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

（2）利用Map進行鍵值對掃描，進而生成相對應的關聯規則。

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

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

2.5 實例分析

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

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

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

參考文獻

[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日志分析系統的設計[J].廣西大學學報：自然科學版，2011， 36（01）：314-317.

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

作者單位

吉林醫藥學院 吉林省吉林市 132013