基于Spark的并行ISOMAP算法

Parallel ISOMAP algorithm based on Spark

为了实现大数据环境下非线性高维数据的降维,提出了基于Spark的并行ISOMAP算法.在该方法中,为了快速求解大规模矩阵的特征值和特征向量,设计并实现了基于Spark的并行块Davidson方法;同时,针对大规模矩阵计算和传输困难的问题,提出了基于RDD分区的行块式矩阵乘法策略,该策略把每个分区中的矩阵行转换成块矩阵,行块式矩阵可不受map算子对RDD逐条计算的限制,并可以利用Spark中的线性代数库参与矩阵级别的运算.实验结果表明,行块式矩阵乘法策略有效提高了矩阵运算的效率,并行块Davidson方法能够快速求解大规模矩阵特征值和特征向量,有效提高了并行ISOMAP算法的性能,表明并行ISOMAP算法可以适应大数据环境下的降维处理.

To reduce the dimension of the nonlinear high-dimensional data in the big data environment,a parallel ISOMAP algorithm based on Spark is proposed,where a Spark-based parallel block Davidson method is designed and implemented to quickly solve eigenvalues and eigenvectors of the large scale matrices.Simultaneously,a row-block matrix multiplication strategy based on RDD partition is proposed for the difficulty of computation and transmission of the large scale matrices,which converts the matrix rows in each partition into block matrices.The row-block matrices are not restricted by the map operator to RDD calculation one by one,and can treat operations at the matrix level by using linear algebraic Library in Spark.The experimental results show that the row-block matrix multiplication strategy effectively improves the efficiency of matrix operations;the parallel block Davidson method can quickly solve the eigenvalues and eigenvectors of the large scale matrices and effectively improve the performance of parallel ISOMAP algorithm;and the parallel ISOMAP algorithm can adapt to dimensionality reduction in the big data environment.