李淋淋，倪建成，曹 博，于苹苹，姚彬修

(1.曲阜师范大学 信息科学与工程学院，山东 日照 276826；2.曲阜师范大学 软件学院，山东 曲阜 273100)

基于Spark框架的并行聚类算法

李淋淋1，倪建成2，曹 博1，于苹苹1，姚彬修1

(1.曲阜师范大学 信息科学与工程学院，山东 日照 276826；2.曲阜师范大学 软件学院，山东 曲阜 273100)

针对传统K-means算法在处理海量数据时存在距离计算瓶颈及因迭代计算次数增加导致内存不足的问题，提出了一种基于Spark框架的SBTICK-means(SparkBasedTriangleInequalityCanopy-K-means)并行聚类算法。为了更好地解决K值选取的盲目性和随机性的问题，该算法利用Canopy进行预处理得到初始聚类中心点和K值；在K-means迭代计算过程中进一步利用距离三角不等式定理减少冗余计算、加快聚类速度，结合Spark框架实现算法的并行化，充分利用Spark的内存计算优势提高数据的处理速度，缩减算法的整体运行时间。实验结果表明，SBTICK-means算法在保证准确率的同时大大提高了聚类效率，与传统的K-means算法、Canopy-K-means算法和基于MapReduce框架下的该算法相比，在加速比、扩展比以及运行速率上都有一定的提高，从而更适合应用于海量数据的聚类研究。

K-means；Spark；大数据；Hadoop；MapReduce

0 引 言

K-means聚类算法因其执行简单、快速、易于并行化，并可以提供直观结果等优点而成为数据挖掘和非监督式学习中的流行算法[1]，但它也存在以下问题[2]：K值(簇数)是人为确定的，在对数据不了解的情况下很难给出合理的K值；初始中心点的选择是随机的，若选择到较为孤立的点，会严重影响聚类结果；算法在每次迭代时都需要进行大量的距离计算来确定新的聚类中心，然而其中许多计算都是冗余的；……