基于MapReduce的多維迭代算法的研究與實(shí)現(xiàn).pdf

1、迭代計(jì)算是對(duì)一系列的計(jì)算步驟進(jìn)行反復(fù)執(zhí)行，并將前一次迭代計(jì)算得到的結(jié)果作為下一次迭代計(jì)算的輸入，逐漸接近希望得到的目標(biāo)或結(jié)果的計(jì)算方法。當(dāng)?shù)?jì)算結(jié)果收斂或滿足其他計(jì)算終止條件時(shí)，即認(rèn)為迭代計(jì)算結(jié)束，并輸出最終的結(jié)算結(jié)果。由迭代理論可知，當(dāng)?shù)?jì)算函數(shù)不滿足Lipschitz條件時(shí)，迭代結(jié)果易收斂到局部最優(yōu)解。為了解決這一問題，常常采用多組初始輸入數(shù)據(jù)進(jìn)行多次迭代計(jì)算，并從得到的多組結(jié)果中，選取質(zhì)量最好的結(jié)果作為迭代計(jì)算的最終計(jì)算結(jié)果。

2、迭代計(jì)算是串行地處理多組輸入數(shù)據(jù)，因此會(huì)消耗大量的運(yùn)算時(shí)間，并且各次迭代計(jì)算之間缺少數(shù)據(jù)共享。因此，在多組初始輸入數(shù)據(jù)情況下，提高迭代計(jì)算的并行處理能力及數(shù)據(jù)共享能力成為了關(guān)鍵。
　　MapReduce計(jì)算框架具有較強(qiáng)的并行處理能力和數(shù)據(jù)共享能力，并且能夠輕松應(yīng)對(duì)大規(guī)模數(shù)據(jù)集的處理任務(wù)。本文立足于大規(guī)模數(shù)據(jù)集下利用多組輸入數(shù)據(jù)進(jìn)行迭代計(jì)算的需求，應(yīng)用MapReduce計(jì)算框架提出了多維迭代算法，以提高迭代計(jì)算的執(zhí)行效率。論文的主要

3、工作如下：
　　(1)在多組輸入數(shù)據(jù)情況下，針對(duì)傳統(tǒng)的迭代算法的運(yùn)算缺點(diǎn)，我們提出了多維迭代算法的概念。通過對(duì)一次迭代計(jì)算流程的改進(jìn)，降低多組輸入數(shù)據(jù)情況下迭代計(jì)算的運(yùn)行時(shí)間。同時(shí)，利用多維迭代算法，增強(qiáng)迭代計(jì)算過程中不同迭代計(jì)算過程間數(shù)據(jù)的共享能力，降低對(duì)數(shù)據(jù)集的讀取次數(shù)。根據(jù)MapReduce計(jì)算框架的工作流程，應(yīng)用MapReduce編程框架針對(duì)多組輸入數(shù)據(jù)的情況，編寫了多維迭代算法的程序。
　　(2)將Kmeans聚類

4、算法與多維迭代算法進(jìn)行結(jié)合，提出了Mux-Kmeans算法。在分析了Kmeans聚類算法的運(yùn)行原理后，針對(duì)其易收斂到局部最優(yōu)解的缺點(diǎn)，使用多維迭代算法對(duì)其進(jìn)行了改進(jìn)。利用三個(gè)真實(shí)的數(shù)據(jù)集，在AmazonEC2云平臺(tái)上，針對(duì)Mux-Kmeans的運(yùn)行效果及計(jì)算耗時(shí)進(jìn)行了實(shí)驗(yàn)。將Mux-Kmeans的實(shí)驗(yàn)結(jié)果與相同輸入數(shù)據(jù)下Kmeans的實(shí)驗(yàn)結(jié)果進(jìn)行比較，證實(shí)了Mux-Kmeans具有提高迭代計(jì)算的運(yùn)行效果及降低計(jì)算耗時(shí)的作用。
　　

5、(3)將EM聚類算法與多維迭代算法進(jìn)行結(jié)合，提出了Mux-EM算法。在分析了EM聚類算法的運(yùn)行原理后，針對(duì)其易收斂到局部最優(yōu)解的缺點(diǎn)，使用多維迭代算法對(duì)其進(jìn)行了改進(jìn)。利用兩個(gè)真實(shí)的數(shù)據(jù)集，在本地虛擬云平臺(tái)上，針對(duì)Mux-EM的運(yùn)行效果及計(jì)算耗時(shí)進(jìn)行了實(shí)驗(yàn)。將Mux-EM的實(shí)驗(yàn)結(jié)果與相同輸入數(shù)據(jù)下EM的實(shí)驗(yàn)結(jié)果進(jìn)行比較，證實(shí)了Mux-EM具有提高迭代計(jì)算的運(yùn)行效果及降低計(jì)算耗時(shí)的作用。
　　通過實(shí)驗(yàn)驗(yàn)證，證明了本文提出的多維迭代算法