基于Hadoop的非负矩阵分解算法研究

王宇 祝永志

摘 要：大数据时代，对大规模数据的分析和处理提出了更高要求。非负矩阵分解作为一种高效方法被广泛应用于数据降维和特征提取，有效减少了大规模数据的复杂运算，但存在计算过程繁琐的弊端。将分布式平台Hadoop与非负矩阵分解有机结合，利用Hadoop处理大规模数据的并行能力与非负矩阵分解自身的数据降维特点，实现较高的加速比。这种方法能高效完成非负矩阵分解的迭代问题，提高算法的计算效率。

关键词：非负矩阵分解；大数据；Hadoop；并行

DOIDOI：10.11907/rjdk.181120

中图分类号：TP312

文献标识码：A 文章编号：1672-7800（2018）010-0085-03

英文摘要Abstract：In the past few years，the rapid development of science and technology has led to the explosive growth of data，especially biological data.Therefore，higher requirements for large-scale data analysis are put forward and processing research is of great concern.Nonnegative matrix factorization as an efficient method，widely used for data dimensionality reduction and feature extraction，can effectively reduce the complexity of large-scale data，as well as show the value of the data，but there are some disadvantages of complex calculation.Higher speedup is achieved by combining of the distributed platform Hadoop and NMF，and using parallel capability of Hadoop to deal with large-scale data as well as the data dimensionality reduction features of NMF.This method can efficiently complete the nonnegative matrix factorization iteration problem and improve the efficiency of the algorithm.

英文關键词Key Words：nonnegative matrix factorization；big data； Hadoop； parallel

0 引言

大数据以其特有的规模大、多样性、价值高、速度快等特点引起广泛关注。获取和掌握大数据成为衡量一个国家综合国力的重要标志。大数据中包含着难以估量的价值，因此对大数据的存储方式及分析应用成为研究热点。

非负矩阵分解（Nonnegative Matrix Factorization，NMF）是将不含负数元素的矩阵进行分解，从而得到两个低秩矩阵，通过这种方法可更清楚地观察数据的内部结构，并获得一定程度的维数约减[1]。PCA、SVD、VQ等矩阵分解算法[2-4]有很大部分数据由非负元素组成，而非负元素能够更好地贴近实际进行相关处理。NMF克服了多种矩阵分解算法的弊端，作为一种代表性的机器学习和数据挖掘算法，已经广泛应用于生物医学、模式识别、图像处理、聚类分析等各种领域[5]。

NMF可将一个全为非负元素的矩阵分解为两个低维非负矩阵相乘的形式，一个显著问题是被分解的原始矩阵维数一般较大，分解过程会相当复杂。传统的技术方法及通过单台计算机处理数据的串行方法无法解决大规模矩阵问题，加之大规模矩阵运算的时间复杂度较高，所以NMF并行化算法[6-9]渐渐进入人们视野。虽然很多算法能在一定程度上对NMF算法进行并行化，但一个优秀的并行算法[10]应考虑到机器硬件的体系结构，并能更加高效地利用计算机资源。本文提出一种基于Hadoop的NMF并行方法以提高非负矩阵分解过程的乘法迭代效率。

1 Hadoop简介

数据挖掘和数据分析是处理大数据的关键技术，可从中获取有价值内容。Hadoop是一个比较成熟的分布式系统架构，是Apache基金会开发的一个开源项目[11]，也是一个实现了Google云计算系统的开源系统，其提供了一个可靠的共享存储和分析系统，包括实现数据分析和处理的并行计算模型MapReduce[12]，实现数据存储的分布式文件系统HDFS，分布式数据库Hbase。随着研究与应用的深入，加入了越来越多的相关项目，如Zookeeper、Pig、Chukwa、Hive、Mahout、Flume等，见图1。

Google公司提出的MapReduce是Hadoop的核心组件之一，是用于处理大规模数据集并行运算的软件框架，具有多项功能，如数据划分和任务调度、数据/代码相互定位、系统优化、出错检测和恢复等。通过MapReduce可把一个复杂的大型任务按照某种特征分析归纳，然后进行快速处理获得最终结果[13]。MapReduce思想是化大为小，Mapper负责划分，即把复杂的任务划分成多个小型的简单任务处理[14]。简单任务指数据或计算的规模相对原任务大大缩小，通过就近计算原则，将任务分配到存放所需数据的节点上进行计算。重要的是这些小任务可以并行计算，彼此之间独立运作互不影响，Reducer负责对map阶段产生的简单任务结果汇总[15]。