SCoS:基于Spark的并行谱聚类算法设计与实现

摘要

谱聚类是一种比传统聚类算法更为高效的算法,其建立在谱图理论基础上,并将聚类问题转化为图的最优划分问题.与传统k-means算法不同的是,谱聚类算法不仅能够在任意形状的样本空间上实现聚类,而且可以收敛至全局最优解.然而,谱聚类算法的计算开销较大,不仅需要计算任意两个样本之间的相似性,而且还需要计算Laplacian矩阵的特征向量.因此,在大规模数据场景下,谱聚类算法存在计算耗时过长甚至无法完成计算的问题.为了解决谱聚类算法在大规模数据场景下的计算性能问题,使得谱聚类算法能够应用在大数据集上,文中基于Apache Spark分布式并行计算框架研究并实现了大规模并行谱聚类算法SCoS,对算法流程中的每个计算步骤进行了并行化.具体的,SCoS主要实现了相似度矩阵构建与稀疏化过程的并行化、Laplacian矩阵构建与正规化过程的并行化、正规化Laplacian矩阵特征向量计算的并行化以及k-means聚类的并行化.为了降低谱聚类算法中大规模样本相似性计算的开销,SCoS采用了基于多轮迭代的并行计算方式实现大规模样本之间的相似性计算.针对大规模谱聚类算法中耗时较长的Laplacian矩阵特征向量求解问题,SCoS基于ScaLAPACK实现了特征向量的并行化求解,同时文中也实现了近似特征向量计算算法,并且对比分析了精确特征向量计算与近似特征向量计算对于谱聚类算法的性能影响.为了进一步提升大规模谱聚类算法的性能,SCoS采取了矩阵稀疏化表示与存储、Laplacian矩阵乘法优化以及k-means聚类中距离计算放缩剪枝等多种优化手段,尽可能地减少计算开销、存储空间开销以及数据传输开销.实验表明,SCoS不仅在聚类效果上要优于传统的聚类算法,而且具有较高的运行效率,特别是在大规模数据集下,仍具有较高的计算性能,并表现出了良好的数据可扩展性和系统可扩展性.