大规模非负矩阵分解的可扩展并行算法研究

Non-negative Matrix Factorization (NMF) is a basic mathematical method for machine learning and data mining, which has been successfully used in many fields. However, due to the high computation complexity of NMF, the parallelization of NMF has attracted a wide spread attention in recent years. Designing the high scalable parallel NMF algorithm is an important research topic. In the proposal, we intend to study the combination of in-memory computing technique and graphics processing unit (GPU) acceleration technique based fast parallel NMF algorithm, as well as the parallel NMF algorithm with sparseness constraints. Large memory and GPU resource of computing node in a heterogeneous cluster environment are fully utilized to realize high efficient NMF computation. The factors which may affect algorithm scalability are analyzed, and a variety of optimization methods are conducted to improve the performance of parallel NMF. The proposed algorithm will be compared with current OpenMP, MPI, GPU and MapReduce based parallel NMF algorithms. Through this study, we will eventually obtain a high scalable parallel NMF algorithm, which can be automatically scaled to support processing ultra-large high-dimensional NMF. Finally, the proposed parallel NMF algorithm will be applied in a real scenario of commodity recommendation to perform the scalability verification and evaluation. This study will further expand the application fields of NMF, and provides an important method for feature extraction, recommender systems, information retrieval and etc.

非负矩阵分解(NMF)是机器学习和数据挖掘中的一种基本数学方法，已被成功应用于多个领域，但由于其计算复杂度较高，近年来其并行化求解受到了广泛的关注。设计高可扩展的并行化NMF算法是目前重要的研究课题。本项目拟研究基于内存计算技术和基于图形处理器(GPU)加速技术相结合的快速NMF可扩展并行算法，并研究加稀疏性约束的NMF并行算法，充分利用异构集群中节点的大内存和GPU资源实现高效的求解。分析影响并行算法可扩展性的因素，结合多种优化手段，提高算法性能，并将其与目前的基于OpenMP、MPI、GPU和MapReduce的并行NMF算法进行比较。将最终获得高度可扩展的并行化的NMF算法，算法能够自动扩展至支持处理超大规模高维非负矩阵的分解。最后，在真实的商品推荐应用场景中进行非负矩阵分解算法的验证及性能测试。该研究将进一步拓展非负矩阵分解的应用体系，为特征提取、推荐系统、信息检索等提供重要手段。

非负矩阵分解(NMF)是机器学习和数据挖掘中的一种基本数学方法，已被成功应用于多个领域，但由于其计算复杂度较高，近年来其并行化求解受到了广泛的关注。设计高可扩展的并行化NMF算法是目前重要的研究课题。本项目研究了基于内存计算技术和基于图形处理器(GPU)加速技术相结合的快速NMF可扩展并行算法，充分利用异构集群中节点的大内存和GPU资源实现高效的求解。在项目执行期间，共发表了11篇相关论文，实现了基于MPI+OpenMP的并行非负矩阵分解算法，实现了基于GPU的并行非负矩阵分解算法，提出了一种Spark和GPU融合的框架，并实现了基于GPU+Spark的并行非负矩阵分解算法。利用GPU和Spark的各自优势，该算法能够自动扩展至支持处理超大规模高维非负矩阵的分解，并在协同过滤推荐的场景下，进行了算法性能测试，取得了较好效果。该研究将进一步拓展非负矩阵分解的应用体系，加速非负矩阵分解的速度，为特征提取、推荐系统、信息检索等提供重要手段。