Abstract: K-means is a classical clustering algorithm. Distributed computing is utilized to improve its scalability on large-scale data in recent years. However, traditional disk-based distributed systems still have a large amount of I/O consumption. This paper extends the machine learning library MLlib in Spark, a memory-based distributed platform with low I/O consumption and good fault tolerance mechanism. This paper develops a RDD-based index layer, which exploits a two-level index comp to rising multiple index strategies, including R-tree, quad tree, KD-tree and Ball tree. By overriding the data partitioning methods, this paper optimizes K-means algorithm by preprocessing the points with close spatial distance. The index layer is used to store the general information of the corresponding point set so that the search space pruning can be used in K-means algorithm. The experimental results show that the index layer can prune the search space by more than 40%, and improve the efficiency by 21% compared to the na?ve distributed K-means algorithm.

Key words: K-means, clustering algorithm, Spark, R-tree, quad tree, KD-tree, Ball-tree

摘要： K-means是经典的聚类算法，为了适应大规模数据，很多研究利用分布式计算提高其扩展性。但传统基于磁盘的分布式系统仍然存在大量I/O消耗，在基于内存的Spark系统上实现，在继承Spark平台低读写消耗和良好容错性等优点的基础上，扩展了Spark的机器学习MLlib库，在此之上增加一个索引层，引入包含多种策略的基于RDD的双级索引机制，采用新的数据划分方式，对空间距离相近的点的信息进行预处理，利用索引存储其对应的点集的概括信息，以便在K-means算法中对搜索空间剪枝，从而达到对K-means算法的优化。实验结果表明，索引层能够剪枝搜索空间达40%以上，相对无优化的分布式K-means，提升效率达21%，具有较好的可扩展性。

关键词: K-means算法, 聚类算法, Spark系统, R树, 四叉树, KD树, Ball树