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

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

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

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

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

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