基于GraphX的分布式幂迭代聚类

来源：计算机应用杂志2016年第10期北京时间：

作者：赵军, 徐晓燕

单位：1. 北京航空航天大学 计算机科学与技术系, 北京 100191;2. 国家计算机网络应急技术处理协调中心, 北京 100029

摘要：为解决幂迭代聚类算法并行实现中存在的编程繁琐、效率低下等问题，基于Spark大规模数据通用计算引擎及其GraphX组件，提出了一种在分布式环境下实现幂迭代聚类的方法。首先，利用某种相似性度量方法，将原始数据转换成一个可以视为图的亲和矩阵；然后，通过顶点切割，把行归一化后的亲和矩阵切分成若干个小图，分别存储在不同的机器上；最后，利用Spark基于内存计算的特点，对存储在集群中的图进行多次迭代计算，得到这个图的一个切割，图的每一个划分子图对应一个类簇。在不同规模的数据集和不同executor个数下进行的实验结果表明，基于GraphX的分布式幂迭代聚类算法具有良好的可扩展性，算法运行时间与executor个数呈负相关的线性关系，在6个executor下，与单个executor相比，算法的加速比达到了2.09到3.77。同时，通过与基于Hadoop的幂迭代聚类进行对比，在新闻数量为40000篇时，运行时间降低了61%。

关键词：GraphX,图计算,幂迭代聚类,内存计算,RDD

基金资助：国家973计划项目（2014CB340305）。