王宇 祝永志

摘 要：大數據時代，對大規(guī)模數據的分析和處理提出了更高要求。非負矩陣分解作為一種高效方法被廣泛應用于數據降維和特征提取，有效減少了大規(guī)模數據的復雜運算，但存在計算過程繁瑣的弊端。將分布式平臺Hadoop與非負矩陣分解有機結合，利用Hadoop處理大規(guī)模數據的并行能力與非負矩陣分解自身的數據降維特點，實現較高的加速比。這種方法能高效完成非負矩陣分解的迭代問題，提高算法的計算效率。

關鍵詞：非負矩陣分解；大數據；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 引言

大數據以其特有的規(guī)模大、多樣性、價值高、速度快等特點引起廣泛關注。獲取和掌握大數據成為衡量一個國家綜合國力的重要標志。大數據中包含著難以估量的價值，因此對大數據的存儲方式及分析應用成為研究熱點。

非負矩陣分解（Nonnegative Matrix Factorization，NMF）是將不含負數元素的矩陣進行分解，從而得到兩個低秩矩陣，通過這種方法可更清楚地觀察數據的內部結構，并獲得一定程度的維數約減[1]。PCA、SVD、VQ等矩陣分解算法[2-4]有很大部分數據由非負元素組成，而非負元素能夠更好地貼近實際進行相關處理。NMF克服了多種矩陣分解算法的弊端，作為一種代表性的機器學習和數據挖掘算法，已經廣泛應用于生物醫(yī)學、模式識別、圖像處理、聚類分析等各種領域[5]。

NMF可將一個全為非負元素的矩陣分解為兩個低維非負矩陣相乘的形式，一個顯著問題是被分解的原始矩陣維數一般較大，分解過程會相當復雜。傳統(tǒng)的技術方法及通過單臺計算機處理數據的串行方法無法解決大規(guī)模矩陣問題，加之大規(guī)模矩陣運算的時間復雜度較高，所以NMF并行化算法[6-9]漸漸進入人們視野。雖然很多算法能在一定程度上對NMF算法進行并行化，但一個優(yōu)秀的并行算法[10]應考慮到機器硬件的體系結構，并能更加高效地利用計算機資源。本文提出一種基于Hadoop的NMF并行方法以提高非負矩陣分解過程的乘法迭代效率。

1 Hadoop簡介

數據挖掘和數據分析是處理大數據的關鍵技術，可從中獲取有價值內容。Hadoop是一個比較成熟的分布式系統(tǒng)架構，是Apache基金會開發(fā)的一個開源項目[11]，也是一個實現了Google云計算系統(tǒng)的開源系統(tǒng)，其提供了一個可靠的共享存儲和分析系統(tǒng)，包括實現數據分析和處理的并行計算模型MapReduce[12]，實現數據存儲的分布式文件系統(tǒng)HDFS，分布式數據庫Hbase。隨著研究與應用的深入，加入了越來越多的相關項目，如Zookeeper、Pig、Chukwa、Hive、Mahout、Flume等，見圖1。

Google公司提出的MapReduce是Hadoop的核心組件之一，是用于處理大規(guī)模數據集并行運算的軟件框架，具有多項功能，如數據劃分和任務調度、數據/代碼相互定位、系統(tǒng)優(yōu)化、出錯檢測和恢復等。通過MapReduce可把一個復雜的大型任務按照某種特征分析歸納，然后進行快速處理獲得最終結果[13]。MapReduce思想是化大為小，Mapper負責劃分，即把復雜的任務劃分成多個小型的簡單任務處理[14]。簡單任務指數據或計算的規(guī)模相對原任務大大縮小，通過就近計算原則，將任務分配到存放所需數據的節(jié)點上進行計算。重要的是這些小任務可以并行計算，彼此之間獨立運作互不影響，Reducer負責對map階段產生的簡單任務結果匯總[15]。