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

摘要

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