基于Spark的K-means改进算法的并行化实现

Parallel Implementation of Improved K-means Algorithm Based on Spark

针对传统K-means算法在处理海量数据时,存在计算复杂度高和计算能力不足等问题,提出了SKDkmeans(Spark based kd-tree K-means)并行聚类算法.该算法通过引入kd-tree改善初始中心点的选择,克服传统Kmeans算法因初始点的不确定性,易陷入局部最优解的问题,同时利用kd-tree的最近邻搜索减少K-means在迭代中的距离计算,加快聚类速度,并在Spark平台上实现了该算法的并行化,使其适用于海量数据聚类,最后通过实验验证了算法具有良好的准确率和并行计算性能.

In view of the problems that when processing massive data the traditional K-means is highly complex and insufficient in computation, a SKDk-means （Spark based kd-tree K-means） parallel clustering algorithm has been proposed. The algorithm improves the choice of initial center point by introducing kd-tree and overcomes the problem that the traditional K-means algorithm is easy to fall into the local optimal solution due to the uncertainty of the initial point. During K-means iterative calculation, the redundant computation has been reduced and clustering speed has been accelerated by the nearest neighbor search of kd-tree. The parallelization of the algorithm is realized on the spark platform and it is applied to the massive data clustering. Finally, the experimental results show that the algorithm has good accuracy and parallel computing performance.