基于MapReduce的聚类算法的并行化研究

聚类分析是数据挖掘中的重要内容,在工业、商业和科研等领域发挥着越来越重要的作用,然而随着这些领域中产生的数据量高速增长,在传统的计算机上对大规模数据集进行聚类分析需要花费很长的时间。使用并行算法可以有效的解决这一问题。 由Google提出的MapReduce并行计算模型主要是针对海量数据的处理,相对传统的并行计算模型,它由底层对数据分割、任务分配、并行处理、容错等细节问题进行封装,极大的简化了并行程序设计。在使用MapReduce进行并行计算开发时,用户只需集中注意力在自身要解决的并行计算任务上。 k-means算法属于聚类分析中的一种基本划分方法,常采用误差平方和准则函数作为聚类准则,该算法在处理数据集上相对可伸缩且高效率。但面对大规模数据集时,其在计算数据对象间的距离上遇到瓶颈。数据规模变大,则运算次数也随之增大,运算的耗时加长。为了突破这个瓶颈,本文使用MapReduce计算模型,在Hadoop平台上实现k-means算法的并行化。为了进一步提高k-means聚类算法的效率,本文使用canopy算法对k-means算法进行优化,并使用MapReduce计算模型,在Hadoop平台上实现了canopy-k-means算法的并行化。最后在聚类结果的有效性、加速比以及可扩展性上对基于MapReduce的k-means并行算法和canopy-k-means并行算法进行了比较。实验结果表明,这两种并行算法能够得到较好的聚类结果,在大数据集上具有较好的加速比和可扩展性。基于MapReduce的canopy-k-means并行算法比k-means并行算法的聚类结果准确率更高,收敛速度更快。