论文部分内容阅读
聚类是数据分析和管理最基础的算法之一,它已经被广泛应用于计算机科学及其相关领域。然而海量数据的出现使得传统的聚类算法受到了极大的挑战,例如聚类算法的可扩展性差、效率低等。目前,以MapReduce为代表的云计算技术越来越受到商业界和学术界的关注,并且MapReduce已经发展成为最流行的海量数据处理模型之一。本文研究云计算环境下海量数据的并行聚类算法,重点是在MapReduce处理模型中对k-means、k-means++和scalable k-means++聚类算法的研究,目的是提高这些聚类算法的可扩展性和效率。论文完成的工作和主要的研究成果如下：在MapReduce并行处理框架下,针对k-means++初始化方法序列化特性导致其可扩展性差并且需要大量MapReduce作业迭代的问题,本文提出了并行可扩展的k-means++聚类算法,它的初始化方法仅需要一次MapReduce作业迭代就可以选出k个中心点,在Map阶段运行标准的k-means++初始化算法,而在Reduce阶段运行加权的k-means++初始化算法。这种方法不仅提高了k-means++聚类算法在处理海量数据时的效率,而且它被证明是k-means最优聚类结果的O(α2)近似,其中α=8(2+Ink)。考虑到MapReduce并行处理框架下scalable k-means++聚类算法的初始化方法每次迭代仍然需要启动两个MapReduce作业的缺点,通过Map阶段的过采样技术以及Reduce阶段的修正技术,提出了快速的scalable k-means++聚类算法。它的每次迭代仅需要一个MapReduce作业,节省了大量的I／O成本和时间,提高了scalable k-means++聚类算法的效率。MapReduce环境下的k-means聚类算法在处理海量的倾斜数据时会导致Reduce任务的负载不均衡,使得Reduce任务的运行时间差异较大,整个聚类算法的运行时间变长,严重降低了云计算平台的资源利用率。针对此问题本文提出了基于抽样估计的数据划分方法。该方法采用抽样估计理论对原始数据进行分析处理,并根据提出的C2和CSC划分方法得到较好的数据划分方案,最后把该方案应用于MapReduce k-means聚类算法中,实验结果表明此方法平衡了Reduce任务的负载,缩短了聚类算法的运行时间。