王志刚，陈名辉，赵振凯

（湖南师范大学数学与计算机学院，长沙 410081）

一种YARN和Spark框架的网格聚类方法

王志刚，陈名辉，赵振凯

（湖南师范大学数学与计算机学院，长沙 410081）

分布式计算为大数据的处理提供一种新的平台，能有效提升算法的执行速度。在DBSCAN算法基础上提出一种数据分网格算法，该算法将每个分区上的数据集划分成以Eps半径为边长的单元格数据块，将查找Eps邻域的范围缩小到数据对象的八个相邻单元格之内，从而提高查找Eps邻域的速度及聚类速度，具有较好的加速比和扩展率。同时还优化分区聚类合并方法。

分布式计算；DBSCAN；Spark；YARN；Tachyon

0 引言

分布式计算平台具有易于扩展、学习、使用和部署等特点，是一种简洁抽象的并行编程环境。用户只需要关注解决自己的并行计算任务，而不需关注细节实现。

加州伯克利大学AMP实验室最先推出Spark，但直到2014年才开始大幅度发展。目前，较流行运用Hadoop的MapReduce[1]实现并行数据挖掘，算法K-means和DBSCAN是其主要代表。文献[2]提出了基于Hadoop的K-means、DBSCAN、近邻传播算法和谱聚类算法的MapReduce编辑模型。文献[3]提出了DBSCAN增量聚类算法的MapReduce实现。文献[4]提出了网格控制因子的DBSCAN聚类算法，并用MapReduce对聚类算法进行封装，提高了算法的效率。文献[5]利用数据分箱和网格划分技术，通过对核心点生成无向图后进行广度优先搜索生成聚类，是一种效率较高的网格DBSCAN算法。文献[6]对各个局部数据集采取不同的参数值分别进行聚类，最后合并各局部聚类结果。文献[7]的DPDGA算法在数据划分时利用遗传算法获得较优的初始聚类中心，据此中心点划分数据集，对各局部数据集分别使用DBSCAN算法进行聚类，最后合并各局部数据集的聚类结果。……