基于MapReduce的主成分分析算法研究

发布时间：2018-05-27 00:25

本文选题：主成分分析 + 奇异值分解　；参考：《计算机科学》2017年02期

【摘要】：随着MapReduce并行化框架的流行,各种数据挖掘算法的并行化也成为了当下研究的热点。主成分分析(Principle Components Analysis,PCA)算法的并行化也得到了越来越多的关注。通过对目前PCA算法的并行化研究的成果进行总结,发现这些PCA算法并行程度并不完全,特别是特征值计算过程。整个PCA算法流程分为两个阶段:相关系数矩阵求解阶段和矩阵的奇异值分解(Singular Value Decomposition,SVD)阶段。通过当前最流行的并行框架MapReduce,融合矩阵的QR分解,提出了一种奇异值分解的并行实现方法。利用随机产生的不同维度大小的双浮点矩阵比较并行奇异值分解相对传统串行环境下的算法效率的提升情况,并分析算法效率。之后,将并行奇异值分解融合到PCA算法中,同时提出相关系数矩阵的并行计算过程,将PCA计算的两个部分完全并行化。利用不同维度的矩阵对提出的并行PCA算法与已存在的未完全并行PCA算法、常规的PCA算法的运算速度进行比较,分析完全并行化PCA算法的加速比,最终得出所提算法在处理一定规模的大数据情况下的时间消耗要少许多。
[Abstract]:With the popularity of the MapReduce parallelization framework, the parallelization of various data mining algorithms has become a hot topic in the present research. The parallelization of the Principle Components Analysis (PCA) algorithm has also been paid more and more attention. By summarizing the achievements of the parallel research of the current PCA algorithm, the PCA algorithms are found. The parallel degree is not complete, especially the eigenvalue calculation process. The whole PCA algorithm process is divided into two stages: the correlation coefficient matrix solution phase and the matrix singular value decomposition (Singular Value Decomposition, SVD) stage. A singular value decomposition is proposed through the current most popular parallel framework MapReduce, the QR decomposition of the fusion matrix. The parallel singular value decomposition is used to compare the efficiency of parallel singular value decomposition (SVD) to the efficiency of the algorithm in the traditional serial environment, and the algorithm efficiency is analyzed. Then, the parallel singular value decomposition is fused into the PCA algorithm, and the parallel computation process of the correlation coefficient matrix is proposed, and the PCA is calculated. The two parts of the calculation are completely parallelized. Using the matrix of different dimensions, the proposed parallel PCA algorithm is compared with the existing incomplete parallel PCA algorithm and the conventional PCA algorithm, and the acceleration ratio of the fully parallelized PCA algorithm is analyzed. Finally, the time consumption of the proposed algorithm is obtained under the large data conditions at a certain scale. A lot less.
【作者单位】：东北大学计算机科学与工程学院;东北大学软件学院;
【基金】：国家杰出青年科学基金资助项目(61225012,71325002) 国家自然科学基金资助项目(61572123) 高等学校博士学科点专项科研基金优先发展领域资助课题(20120042130003)资助
【分类号】：TP301.6

【相似文献】