邵天會(huì)

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

【關(guān)鍵詞】云平臺(tái) MapReduce Apriori算法

1 MapReduce工作原理

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

2 常見(jiàn)的MapReduce化的Apriori算法

2.1 DD算法（Data Distribution）

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

2.2 CaD 算法（Candidate Distribution）

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

2.3 生成頻繁項(xiàng)算法

具體過(guò)程如下：

（1）過(guò)InputFormat把事務(wù)集劃分N個(gè)數(shù)據(jù)塊，每個(gè)數(shù)據(jù)塊的格式為（TID，LIST），同時(shí)M個(gè)節(jié)點(diǎn)進(jìn)行獨(dú)立的運(yùn)算各自的數(shù)據(jù)塊，格式中的LIST為事務(wù)標(biāo)志TID相對(duì)應(yīng)的項(xiàng)目號(hào)。

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

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

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

（5）利用局部支持度和最小支持度的閾值進(jìn)行比較獲得局部的頻繁項(xiàng)集。

（6）通過(guò)把各個(gè)局部頻繁項(xiàng)集融合得出全局頻繁項(xiàng)集

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

相應(yīng)的偽代碼：

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

輸出：相應(yīng)的頻繁項(xiàng)集I

I=查找頻繁項(xiàng)集（Ti）

i=2；

While（I not null）{

i++；

Ci=apriori算法結(jié)果；

for 每個(gè)候選集掃描；

Ci=Map（）；}

I=Reduce（）；

Reduce I；

Map程序：

For 每個(gè)屬于Ci的I

EmitInter（I ，局部支持度）；

Reduce（I 局部支持度）；

Result 為0；

For 每個(gè)屬于Ci 的I；

Result=局部支持度的求和；

Emit（本次的I，result）；

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

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

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

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

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

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

2.5 實(shí)例分析

為了驗(yàn)證該算法，進(jìn)行事務(wù)集算法實(shí)例分析，如表1。

按照改進(jìn)的算法進(jìn)行事務(wù)集挖掘流程如圖1所示。

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

參考文獻(xiàn)

[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)的設(shè)計(jì)[J].廣西大學(xué)學(xué)報(bào)：自然科學(xué)版，2011， 36（01）：314-317.

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

作者單位

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