蔡洪山

摘要：随着处理数据规模的迅速增长，对算法的执行速度要求越来越高。Kmean是聚类分析分析中的一个经典算法，虽然其已在Hadoop平台上有并行化实现，但Hadoop的计算模型并不适合像Kmeans这种迭代计算。Spark被看作下一代大数据并行处理框架，非常适合进行迭代计算。该文论述了Kmeans算法在Spark平台上的并行原理，给出了实现方法，并通过实验证明该实现能够快速完成在大数据集上的聚类。

关键词：Kmeans；并行化；Spark；大数据；聚类

中图分类号：TP312 文献标识码：A 文章编号：1009-3044（2016）04-0074-02

Research of Parallelized Kmeans Algorithm on Spark

CAI Hong-shan

（Anhui University of Science and Technology， School of Computer Science and Engineering，Huainan 232001， China）

Abstract： With the mount of data to deal with growing rapidly， peoples requirement on the execution speed of algorithms is higher and higher. Kmeans algorithm， which is a classical one in cluster analysis， has been implemented on Hadoop platform； but programming paradigm implemented by Hadoop is not good at addressing iterative computation such Kmeans. Spark ， which is regarded as the next-generation data processing engine， excels at iterative computation. This paper discusses how Kmeans algorithm is executed parallel on spark and shows the implementation. The result turns out that the method work fine on large data set.

Key words： Kmeans algorithm； parallelization； big data； spark

聚类是一种无监督学习的过程[1]，它是在没有给定分类的情况下，通过计算数据之间预先指定的属性上的相识性，将数据划分为相交或不相交的簇。聚类分析作为数据挖掘领域中一种工具，已经在许多领域广泛应用[2]，包括生物学，信息检索。当前，现实和虚拟世界的数据产生速度越来越迅猛，聚类计算任务所面临的数据规模越来越大，k-means算法是一种常用而有效的聚类算法，但其串行计算方法的时间复杂度比较高[3]，处理能力存在局限性。因此如何实现其并行化以处理海量数据是一个很有价值的研究方向。

Hadoop是目前广泛使用的并行计算平台[4]，但Hadoop的MapReduce比不适合迭代计算。在Hadoop的计算模型中[5]，一个任务只有map和reduce两个阶段，复杂的计算需要多个的Job完成，Job之间的依赖关系是由开发者自己管理的；并且map阶段的中间结果要写到本地磁盘，这对需要多次迭代才能完成的计算显然是不合适的。而迭代计算在数据处理中是很常见的，尤其在机器学习、数据挖掘、信息检索等领域[6]，很多算法都是运用多次迭代完成的。……