自适应谱聚类算法并行实现及优化

Parallel Implementation and Optimization of Self-Tuning Spectral Clustering Algorithm

谱聚类算法是基于谱图分割理论的聚类方法,其对高维、非凸数据分布问题有很好的聚类效果。但对大规模数据问题的聚类,该方法存在着计算时间和存储空间等方面的瓶颈。本文给出了一个自适应的谱聚类并行算法,通过局部计算和异步循环通信并行方法,最大限度减少了并行谱聚类中数据通信次数,并通过计算与通信重叠策略,进一步降低了并行算法的通信开销。在并行算法实现中,将自主开发的最优预条件共轭梯度法并行求解器PLOBPCG用于谱聚类的特征降维。在中科院的"元"超级计算机上,通过对两类大规模数据聚类的测试表明,在2048核上的加速比接近线性加速,并行效率达到96%以上。

Spectral clustering algorithm is a clustering method based on spectral segmentation theory,which has a good clustering effect on high-dimensional and non-convex data distribution problems.However,there are some bottlenecks in the clustering of large scale data,such as computation time and storage space.In this paper,a parallel self-tuning spectral clustering algorithm is proposed.By means of local calculation and asynchronous loop communication,the number of data communication in parallel spectral clustering is minimized.In order to further reduce the communication overhead,a method of computing and communication overlap is used.In the parallel algorithm implementation,the self-developed locally optimal block preconditioned conjugate gradient method parallel solver PLOBPCG is applied to the feature reduction of spectral clustering.On the supercomputer＂Era＂of Chinese Academy of Sciences,the clustering test of two types of large-scale data shows that the speedup ratio of the 2048 core is nearly linear,and the parallel efficiency is above 96%.