论文部分内容阅读
在过去的几年间,快速发展的科学技术引领了数据的爆炸性增长,毫无疑问,人类社会已经进入大数据时代。在大数据时代中隐藏的大规模数据大多以矩阵形式出现,这就意味着对大规模数据的处理,其实就是对大规模矩阵的处理。其中,非负矩阵分解NMF(Nonnegtive Matrix Factorization)作为一种高效的方法,广泛用于数据降维和特征提取方面,可以有效的减少大规模数据的复杂性运算,同时很好的表现出数据的价值,但是却存在计算过程繁琐的弊端。此外,Hadoop作为分布式计算平台活跃在大数据领域,已经与很多算法进行融合形成了新的数据处理模式,使数据运算的效率获得进一步提升。其中,Hadoop平台采用HDFS(Hadoop Distributed System)作为文件系统进行数据存储,结合MapReduce编程模型在对大规模数据的并行处理上取得显著成效。本文首先在学习多种矩阵乘法与分布式平台的基础上,通过研究MPI(Message Passing Interface)和OpenMP(Open MultiProcessing)混合编程的NMF算法,思考了在其他分布式平台上运行的可能性。在深入学习分布式平台Hadoop的同时,进一步对比了多种NMF算法的优劣与多样的矩阵相乘模式。将分布式平台Hadoop与NMF算法有机结合,利用Hadoop处理大规模数据的并行能力与NMF算法自身的数据降维特点,提出了一种新的NMF算法—HNMF(Nonnegtive Matrix Factorization based on Hadoop)算法,来实现较高的加速比。通过这种方法高效的完成非负矩阵分解的迭代更新问题,从而增进算法的计算效率,并且与MPI和OpenMP混合编程下的NMF算法相似规模矩阵的执行时间以及加速比进行比较,证明了其可行性与较高的加速效果。其次,通过研究经典的NMF结果矩阵的更新法则,对比多种矩阵乘法的计算方法,分析NMF算法中包含的矩阵相乘算法的更新步骤,在提出的两种非负矩阵分解算法CNMF(Convex Nonnegtive Matrix Factorization)和TNMF(3-Factor Nonnegtive Matrix Factorization)的基础上,分析了矩阵更新阶段的开销并提出了优化方案,并且通过实验验证了个别MapReduce阶段加速比变化情况,以及随着矩阵中非负元素数量的增多所揭示的执行时间的变化规律。