论文部分内容阅读
迭代计算是对一系列的计算步骤进行反复执行,并将前一次迭代计算得到的结果作为下一次迭代计算的输入,逐渐接近希望得到的目标或结果的计算方法。当迭代计算结果收敛或满足其他计算终止条件时,即认为迭代计算结束,并输出最终的结算结果。由迭代理论可知,当迭代计算函数不满足Lipschitz条件时,迭代结果易收敛到局部最优解。为了解决这一问题,常常采用多组初始输入数据进行多次迭代计算,并从得到的多组结果中,选取质量最好的结果作为迭代计算的最终计算结果。迭代计算是串行地处理多组输入数据,因此会消耗大量的运算时间,并且各次迭代计算之间缺少数据共享。因此,在多组初始输入数据情况下,提高迭代计算的并行处理能力及数据共享能力成为了关键。MapReduce计算框架具有较强的并行处理能力和数据共享能力,并且能够轻松应对大规模数据集的处理任务。本文立足于大规模数据集下利用多组输入数据进行迭代计算的需求,应用MapReduce计算框架提出了多维迭代算法,以提高迭代计算的执行效率。论文的主要工作如下:(1)在多组输入数据情况下,针对传统的迭代算法的运算缺点,我们提出了多维迭代算法的概念。通过对一次迭代计算流程的改进,降低多组输入数据情况下迭代计算的运行时间。同时,利用多维迭代算法,增强迭代计算过程中不同迭代计算过程间数据的共享能力,降低对数据集的读取次数。根据MapReduce计算框架的工作流程,应用MapReduce编程框架针对多组输入数据的情况,编写了多维迭代算法的程序。(2)将Kmeans聚类算法与多维迭代算法进行结合,提出了Mux-Kmeans算法。在分析了Kmeans聚类算法的运行原理后,针对其易收敛到局部最优解的缺点,使用多维迭代算法对其进行了改进。利用三个真实的数据集,在AmazonEC2云平台上,针对Mux-Kmeans的运行效果及计算耗时进行了实验。将Mux-Kmeans的实验结果与相同输入数据下Kmeans的实验结果进行比较,证实了Mux-Kmeans具有提高迭代计算的运行效果及降低计算耗时的作用。(3)将EM聚类算法与多维迭代算法进行结合,提出了Mux-EM算法。在分析了EM聚类算法的运行原理后,针对其易收敛到局部最优解的缺点,使用多维迭代算法对其进行了改进。利用两个真实的数据集,在本地虚拟云平台上,针对Mux-EM的运行效果及计算耗时进行了实验。将Mux-EM的实验结果与相同输入数据下EM的实验结果进行比较,证实了Mux-EM具有提高迭代计算的运行效果及降低计算耗时的作用。通过实验验证,证明了本文提出的多维迭代算法对于在多组输入数据情况下,提高迭代计算效率的可行性和正确性。