王宇 祝永志

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

關(guān)鍵詞：非負(fù)矩陣分解；大數(shù)據(jù)；Hadoop；并行

DOIDOI：10.11907/rjdk.181120

中圖分類(lèi)號(hào)：TP312

文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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.

英文關(guān)鍵詞Key Words：nonnegative matrix factorization；big data； Hadoop； parallel

0 引言

大數(shù)據(jù)以其特有的規(guī)模大、多樣性、價(jià)值高、速度快等特點(diǎn)引起廣泛關(guān)注。獲取和掌握大數(shù)據(jù)成為衡量一個(gè)國(guó)家綜合國(guó)力的重要標(biāo)志。大數(shù)據(jù)中包含著難以估量的價(jià)值，因此對(duì)大數(shù)據(jù)的存儲(chǔ)方式及分析應(yīng)用成為研究熱點(diǎn)。

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

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

1 Hadoop簡(jiǎn)介

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

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