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

A sparse local scaling parallel spectral clustering algorithm based on MPI

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

The spectral clustering algorithm is widely used in many fields because of its advantages of identifying the non-convex data distribution, and effectively avoiding the local optimal solution without the dimension limitation of data points. However, with the growth of the amount and dimension of the data, it is very necessary to reduce the algorithm＇s computation time on the premise of guaranteeing the clustering accuracy. Moreover, besides the data set itself, the factors affecting the clustering quality of the spectral clustering algorithm include the method of solving distance matrix, the scale parameters of similarity matrix and the form of Laplacian matrix. Aiming at the problems mentioned above, we apply the message passing interface （MPI） parallel programming model to the spectral clustering algorithm. The t-nearest neighbor method is then used in the transformation of Laplacian matrix approximation in the spectral clustering algorithm. Meanwhile, we select the local scaling parameter as the self-tuning scaling parameter in the algorithm. Based on the above analysis, we propose a parallel implementation of the sparse local scaling parallel spectral clustering （SLSPSC）, then conduct experiments on four differ- ent data sets, and analyze and compare the results with those of the current parallel spectral clustering （PSC） in running time and clustering quality. Experimental results show that the total computation time of the SLSPSC is greatly reduced when calculating the Laplacian matrix, and the quality of some data sets is improved.