一种基于MPI的稀疏化局部尺度并行谱聚类算法的研究与实现

来源：计算机工程与科学杂志2016年第5期北京时间：

作者：李瑞琳1,2，赵永华1，黄小磊2,3

单位：1.中国科学院计算机网络信息中心高性能计算部，北京 100190；2.中国科学院大学,北京 100190；3.中国科学院计算机网络信息中心，北京 100190

摘要：谱聚类算法由于其可识别非凸数据分布、可有效避免局部最优解、不受数据点维数限制等优点，在许多领域得到广泛应用。然而，随着数据量的增大和数据维数的增多，在保证聚类准确性的前提下，尽可能降低计算时间将变得非常必要。此外，影响谱聚类算法聚类质量的因素除数据集本身外，还与所采用的求解距离矩阵的方法、相似性矩阵的尺度参数、Laplacian矩阵形式等多种因素相关。针对以上问题，首先对于大规模数据问题，将MPI并行编程模型应用于谱聚类算法；然后利用t最近邻方法对谱聚类算法中较大维数的Laplacian矩阵进行近似转化，同时用局部尺度（Local Scaling）参数对算法中的尺度参数进行自动调节。基于上述分析，提出了一种谱聚类并行实现算法，即稀疏化局部尺度并行谱聚类算法SLSPSC，并在四个数据集上进行了测试，与现有的并行谱聚类算法PSC在运行时间和聚类质量两方面做了比较分析。实验结果显示，该算法降低了求解Laplacian矩阵的总时间，同时部分数据集聚类质量得到较大提高。

关键词：并行谱聚类,稀疏化,局部尺度,MPI,

基金资助：数学工程与先进计算国家重点实验室开放基金（2014A03 ）