论文部分内容阅读
数据的爆炸性增长已经成为目前机器学习和数据挖掘领域中的重要问题。面对如此迅速增长的数据,一般数据挖掘算法可能已经不再适用,需要设计并行化的算法并利用集群来并行化处理。在算法的并行化中,迭代类型的算法因为它所具备的特征不仅是计算密集型也是数据密集型,从而具有一定难度。研究有效和合理的并行化算法,已经势在必行。目前有许多并行化技术,MapReduce是目前较好的并行手段之一。结合Hadoop并行计算环境,算法研究人员能够集中精力在并行算法研究本身上。本文基于Hadoop MapReduce编程框架对海量数据处理中迭代类算法进行了并行化研究,从Pegasos算法着眼研究随机梯度下降类算法的并行化,从Kmeans算法的并行化着眼研究期望最大化类算法的并行化,给出实验和分析,总结这两类算法的并行化特征和难点,并给出并行思路。研究工作和成果主要如下：(1)对目前的数据挖掘算法并行化方法进行分析,着重探讨迭代类算法并行化思路,并分析并行算法的评价指标。(2)提出了一种针对海量数据的并行化Pegasos算法P-Pegasoso迭代类算法中梯度下降算法是一种常见的优化算法。P-Pegasos算法将并行化随机梯度下降算法的思想应用进来,首先将分布在各个计算节点上的海量数据并行随机打散成若干份数据子集。接着,再在每一份数据子集上执行基于随机梯度下降的Pegasos算法得出若干个局部优化结果,最后将这若干个结果进行均值融合得到最终结果。通过大量实验说明该算法是正确有效的,比其他并行化算法速度快,而且具有很好的加速性能和效率。同时进一步说明了梯度下降类算法的并行化具有很好的并行性能。(3)提出了一种针对海量数据的并行化Kmeans算法MR-P-Kmeanso Kmeans算法是另一常见的优化算法期望最大化算法的变种算法。MR-P-Kmeans通过不断重复的MapReduce作业完成Kmeans的迭代过程,直到Kmeans算法收敛。该算法能够完成单机Kmeans算法所不能完成的海量数据聚类任务,并且也有较好的加速效果和效率；同时该算法也存在着一定缺点,即时间相对较长,仅适用于无须太多迭代步骤就能快速收敛的EM类算法。