宋丹丹, 翟俊海,2, 李 艷,2, 齊家興

1(河北大學(xué) 數(shù)學(xué)與信息科學(xué)學(xué)院,河北 保定 071002) 2(河北大學(xué) 河北省機(jī)器學(xué)習(xí)與計(jì)算智能重點(diǎn)實(shí)驗(yàn)室,河北 保定 071002)

1 引 言

極限學(xué)習(xí)機(jī)(Extreme Learning Machine,ELM)是Huang等[1]提出的訓(xùn)練單隱含層前饋神經(jīng)網(wǎng)絡(luò)的一種算法，它與傳統(tǒng)的算法不同，隨機(jī)生成輸入層到隱含層的連接權(quán)和隱含層結(jié)點(diǎn)的偏置，隨后用Moore-Penrose偽逆方法求解隱含層到輸出層的權(quán)值.研究人員只需手工控制隱含層節(jié)點(diǎn)的個(gè)數(shù)，調(diào)整參數(shù)的過(guò)程無(wú)需人工干預(yù)，收斂速度快，泛化能力強(qiáng).

近十年來(lái)，ELM的理論和應(yīng)用有了很大的發(fā)展.Huang等[2]證明了ELM具有很好的SLFNs通用逼近能力，利用常見(jiàn)的激活函數(shù)，就能夠?qū)W習(xí)到所有參數(shù)，能夠得到傳統(tǒng)FNN的最優(yōu)泛化邊界.Wang等[3]利用初始局部誤差模型(LGEM)研究了ELM的泛化能力.為應(yīng)對(duì)不同的實(shí)際應(yīng)用，研究人員提出了多種ELM的變體.例如，在ELM分類器優(yōu)化方面，Bai等[4]提出了一種稀疏ELM(S-ELM)，用不等式約束代替了傳統(tǒng)ELM模型中的等式約束，大大減少了存儲(chǔ)空間和測(cè)試時(shí)間.與支持向量機(jī)相似，帶有不等式約束的S-ELM也會(huì)導(dǎo)致二次規(guī)劃問(wèn)題.然而，由于沒(méi)有涉及偏置項(xiàng)，S-ELM在訓(xùn)練中比svm更有效.翟等[5]提出了一種改進(jìn)靈敏度分析的在線自適應(yīng)極限學(xué)習(xí)機(jī)算法，該算法引入了新型的計(jì)算靈敏度的方法，降低了算法復(fù)雜度和訓(xùn)練時(shí)間并提高了預(yù)測(cè)精度.在集成方面，Lan等[6]提出了一種在線序列ELM(EOS-ELM)集成，該集成以多個(gè)獨(dú)立訓(xùn)練的OS-ELM的平均預(yù)測(cè)作為最終預(yù)測(cè).EOSELM進(jìn)一步提高了OS-ELM的預(yù)測(cè)精度,實(shí)現(xiàn)了ELM算法在線序列數(shù)據(jù)方面的擴(kuò)展.翟等[7]提出了一種用模糊積分集成重復(fù)訓(xùn)練極限學(xué)習(xí)機(jī)的數(shù)據(jù)分類方法，與其他集成ELM不同，該方法能很好地刻畫(huà)ELM基本分類器之間的交互作用，而且具有更好的泛化性能.處理噪聲或缺失數(shù)據(jù)方面，Horata等[8]提出了三種改進(jìn)的ELM算法：1)基于迭代重加權(quán)最小二乘(IRWLS-ELM)的ELM算法；2)基于多元最小邊緣平方(mlt-ELM)的ELM；3)基于一步重加權(quán)mlt(rmlt-ELM)的ELM.在IRWLS中，通過(guò)M-estimate函數(shù)對(duì)訓(xùn)練數(shù)據(jù)進(jìn)行迭代加權(quán)，通過(guò)降低異常值的權(quán)重，可以逐漸減小異常值的影響.在MLTS-ELM和RMLTSELM中，引入了基于最小協(xié)方差行列式(MCD)估計(jì)的多元最小二乘估計(jì)(MLTS)，提高了ELM對(duì)異常值的魯棒性.Man等[9]提出了一種基于有限脈沖響應(yīng)的ELM模型，模型的輸入權(quán)用有限脈沖響應(yīng)濾波器方法確定，提高了ELM對(duì)噪聲數(shù)據(jù)魯棒性.在無(wú)監(jiān)督學(xué)習(xí)方面，Huang等[10]將ELM推廣到半監(jiān)督和無(wú)監(jiān)督學(xué)習(xí)的場(chǎng)景，提出了半監(jiān)督ELM和無(wú)監(jiān)督ELM，極大地?cái)U(kuò)展了ELM的適用性.Heeswijk等[11]提出了一種基于GPU加速的并行ELM集成方法，并用于解決大規(guī)模回歸問(wèn)題，取得了良好的效果.在ELM算法的表示學(xué)習(xí)方面，Kasun等[12]提出了一種基于ELM的表示學(xué)習(xí)的自編碼器，該自編碼器使用ELM學(xué)習(xí)的自編碼器進(jìn)行分層表示學(xué)習(xí)，形成了多層前饋網(wǎng)絡(luò).實(shí)驗(yàn)結(jié)果表明，該方法比深度信念網(wǎng)絡(luò)和深度玻爾茲曼機(jī)要快幾個(gè)數(shù)量級(jí)，所獲得的精度與深度學(xué)習(xí)算法相比具有很強(qiáng)的競(jìng)爭(zhēng)力.在應(yīng)用方面，An等[13]提出了一種基于ELM的高效圖像超分辨率方法，其目標(biāo)是對(duì)輸入的低分辨率圖像進(jìn)行處理，以生成高分辨率圖像.張和李[14]提出了深度極限學(xué)習(xí)機(jī)的立體圖像質(zhì)量評(píng)價(jià)方法，該方法將立體圖像數(shù)據(jù)經(jīng)過(guò)稀疏自編碼器預(yù)訓(xùn)練抽取圖像特征，再輸入ELM分類器進(jìn)行訓(xùn)練，分類器的輸出即為質(zhì)量評(píng)分，提升了該模型的準(zhǔn)確性和穩(wěn)定性.徐等[15]提出了一種融合加權(quán)ELM和Adaboost的交通標(biāo)志識(shí)別算法，該算法迭代更新訓(xùn)練樣本權(quán)重，將ELM分類器作為AdaBoost的弱分類器，最終構(gòu)造出最優(yōu)的強(qiáng)分類器.該方法的優(yōu)點(diǎn)是能夠?qū)崿F(xiàn)對(duì)訓(xùn)練樣本和弱分類器的雙重加權(quán)，提高了交通標(biāo)志的識(shí)別精度.黃和王[16]提出了結(jié)合超限學(xué)習(xí)機(jī)和融合卷積網(wǎng)絡(luò)的3D物體識(shí)別方法，該方法采用多層融合卷積網(wǎng)絡(luò)提取特征，用半隨機(jī)的ELM網(wǎng)絡(luò)進(jìn)行分類.與現(xiàn)有的卷積神經(jīng)網(wǎng)絡(luò)相比，有更好的效果和更短的訓(xùn)練時(shí)長(zhǎng).

針對(duì)大數(shù)據(jù)，傳統(tǒng)的ELM算法已不能適應(yīng)大數(shù)據(jù)環(huán)境的需要，針對(duì)這一問(wèn)題，He等[17]提出了基于MapReduce的ELM.針對(duì)大規(guī)模圖數(shù)據(jù)分類問(wèn)題，Sun等[18]提出了一種基于分布式ELM的分類方法，提出的方法具有好的擴(kuò)展性，而且易于實(shí)現(xiàn).Yao和Ge[19]提出了一種分布式并行ELM和一種層次ELM，解決了用大數(shù)據(jù)進(jìn)行多模式質(zhì)量預(yù)測(cè)問(wèn)題，取得了良好的效果.為了解決ELM在大數(shù)據(jù)環(huán)境中的可擴(kuò)展性問(wèn)題，Ming等[20]提出了兩種ELM并行化變體.一種是基于局部數(shù)據(jù)的模型并行化ELM，另一種是基于全局?jǐn)?shù)據(jù)的模型并行化ELM.基于開(kāi)源大數(shù)據(jù)平臺(tái)Flink，Chen等[21]提出了一種基于GPU加速的并行化層次ELM，并采用幾種優(yōu)化方法提高模型的并行性和可伸縮性.Duan等[22]提出了基于Spark的ELM.本文對(duì)基于MapReduce的ELM和Spark的ELM進(jìn)行全面的比較研究，得出了一些有價(jià)值的結(jié)論.

2 基礎(chǔ)知識(shí)

2.1 MapReduce

MapReduce是由谷歌最先提出，用于完成并行式計(jì)算的一種工具，其主要思想是“分而治之”，將要處理的數(shù)據(jù)隨機(jī)發(fā)送至集群上的各個(gè)節(jié)點(diǎn)上，這些數(shù)據(jù)存放于集群的分布式文件系統(tǒng)HDFS(Hadoop Distributed File System)上.各個(gè)節(jié)點(diǎn)并行地處理在該節(jié)點(diǎn)上的數(shù)據(jù)，然后對(duì)各個(gè)節(jié)點(diǎn)的中間結(jié)果加以處理，輸出處理結(jié)果.用戶主要是通過(guò)MapReduce中的兩個(gè)基本函數(shù)Map和Reduce來(lái)完成具體的大數(shù)據(jù)處理邏輯.在Map階段將數(shù)據(jù)根據(jù)具體要求逐條處理，并以鍵值對(duì)的形式傳送給Reduce階段.Reduce階段將鍵相同的值合并以文件的形式輸出結(jié)果.

2.2 Spark

Spark是一種用于內(nèi)存計(jì)算的大數(shù)據(jù)處理框架.它的設(shè)計(jì)理念中最重要的一點(diǎn)是改善大數(shù)據(jù)并行運(yùn)算時(shí)網(wǎng)絡(luò)數(shù)據(jù)流量承載過(guò)重和磁盤(pán)I/O開(kāi)銷過(guò)大的問(wèn)題.在Spark中，彈性分布式數(shù)據(jù)集RDD(Resilient Distributed Dataset)是最重要的組成成分之一.RDD是一個(gè)抽象的數(shù)據(jù)結(jié)構(gòu)，待處理的數(shù)據(jù)均被高度抽象至RDD中.從物理層面上分析，RDD將待處理的數(shù)據(jù)散布在集群的各個(gè)節(jié)點(diǎn)上，存儲(chǔ)于內(nèi)存或外存上，通過(guò)唯一的標(biāo)識(shí)符對(duì)其進(jìn)行操作；從邏輯層面上分析，待處理的數(shù)據(jù)塊根據(jù)實(shí)際操作劃分分區(qū)數(shù).RDD通過(guò)算子操作分區(qū)，完成轉(zhuǎn)換或行動(dòng)操作，形成新的RDD.在Spark平臺(tái)上的一切操作都是對(duì)RDD的操作.這些操作統(tǒng)分成兩大類，被稱為T(mén)ransformation(轉(zhuǎn)換)操作和Action(行動(dòng))操作.RDD中所有的轉(zhuǎn)換操作都不會(huì)直接計(jì)算結(jié)果，都是延遲加載的操作.它們只是記住這些應(yīng)用到基礎(chǔ)的數(shù)據(jù)集(例如一個(gè)文件)上的轉(zhuǎn)換操作.只有當(dāng)發(fā)生一個(gè)要求返回給Driver的動(dòng)作時(shí)，這些轉(zhuǎn)換操作才會(huì)真正運(yùn)行，這種設(shè)計(jì)使Spark更加有效率.MapReduce和Spark的差異性如表1所示.

表1 MapReduce和Spark平臺(tái)特性對(duì)比

Table 1 Comparison of features of MapReduce and Spark platform

平臺(tái)磁盤(pán)IO操作處理方式處理單元MapReduce生成中間文件,IO操作較頻繁逐條處理一條數(shù)據(jù)Spark基于內(nèi)存計(jì)算,IO操作較少分區(qū)處理RDD

3 ELM的并行化及其比較研究

本節(jié)重點(diǎn)介紹如何用MapReduce和Spark兩種平臺(tái)實(shí)現(xiàn)ELM的并行，并對(duì)這兩種實(shí)現(xiàn)進(jìn)行對(duì)比分析.

3.1 ELM算法

3.2 基于MapReduce的并行化ELM

用MapReduce實(shí)現(xiàn)ELM的并行化，關(guān)鍵是Map函數(shù)和Reduce函數(shù)的設(shè)計(jì).算法1和算法2是計(jì)算U，V兩個(gè)矩陣的Map函數(shù)和Reduce函數(shù).

算法1.Map函數(shù)

輸入:X={(xi,yi)|xi∈Rn,yi∈Rm,i=1,2,…,N},wj∈Rn,bj∈R,j=1,2,…,L.

輸出：輸出中間子矩陣U和V.

1.for(i=1;i<=L;i=i+1)do

2.H〗 = g(x×wi+bi)

3.end

4.for(i=1;i<=L;i=i+1)do

5. for(j=1;j<=L;j=j+1)do

7. context.write(triple(“U”,i,j),u,j〗)

8. end

9. for(j=1;j<=m;j=j+1)do

11. context.write((triple(“V”,i,j),v,j〗)

12. end

13.end

算法2.reduce函數(shù)

輸入:鍵值對(duì),.

輸出:矩陣U和矩陣V.

1.鍵值相同的子矩陣u求和,得到最終結(jié)果矩陣U;

2.鍵值相同的子矩陣v求和,得到最終結(jié)果矩陣V;

3.輸出U和V.

以MapReduce處理兩條數(shù)據(jù)為例，詳細(xì)的數(shù)據(jù)處理流程圖1所示.

圖1 基于MapReduce的ELM數(shù)據(jù)處理流程示意圖

其中，

H1=[w1x11+b1,…,wLx1L+bL]

(1)

H2=[w1x21+b1,…,wLx2L+bL]

(2)

(3)

(4)

(5)

(6)

基于MapReduce的ELM算法執(zhí)行流程如下：

1)將隱含層節(jié)點(diǎn)參數(shù)放置在集群緩存中；

2)在Map節(jié)點(diǎn)上執(zhí)行的操作：

將數(shù)據(jù)x逐條輸入至Map任務(wù)中，與緩存中的數(shù)據(jù)計(jì)算得出隱含層節(jié)點(diǎn)輸出向量H；

計(jì)算U的子矩陣；

計(jì)算V的子矩陣；

將U和V的子矩陣按照鍵值對(duì)的形式輸出至Reduce節(jié)點(diǎn)；

3)在Reduce節(jié)點(diǎn)上執(zhí)行的操作：

將接收到的所有的U的子矩陣u按照矩陣加法得出新矩陣U；

將接收到的所有的V的子矩陣v按照矩陣加法得出新矩陣V；

輸出U和V矩陣.

3.3 基于Spark的并行化ELM

用Spark實(shí)現(xiàn)ELM的并行化，關(guān)鍵是RDD的設(shè)計(jì)，用各種RDD處理數(shù)據(jù)的流程如圖2所示.

根據(jù)圖2，可以看出基于Spark的ELM執(zhí)行流程：

1)第一次遍歷：生成RDD并記錄依賴關(guān)系

讀取外部數(shù)據(jù)生成第一個(gè)RDD(TextFileRDD)；然后執(zhí)行Map轉(zhuǎn)換操作對(duì)數(shù)據(jù)進(jìn)行初步處理，將數(shù)據(jù)的類型轉(zhuǎn)換成數(shù)組，得到MappedRDD，再執(zhí)行Filter轉(zhuǎn)換操作，剔除格式錯(cuò)誤的數(shù)據(jù)(例如缺省值的情況)，生成FilteredRDD，再將數(shù)據(jù)格式轉(zhuǎn)換生成PairRDD，讀成分布式行矩陣的形式，執(zhí)行其內(nèi)部自定義函數(shù)computeGramianMatrix和multipy，具體算子如下：先由mapPartition操作計(jì)算分區(qū)中得到mapPartitionRDD，再由轉(zhuǎn)換操作ReduceByKey得到shuffledRDD，然后再次執(zhí)行mapPartition操作得到新的mapPartitionRDD.所有的轉(zhuǎn)換操作完畢，即在該次作業(yè)中所有RDD生成完畢，遍歷結(jié)束.

2)第二次遍歷：劃分階段

根據(jù)第一次遍歷中RDD記錄的依賴關(guān)系，從最后一次執(zhí)行轉(zhuǎn)換操作MapPartitionRDD向前執(zhí)行，遇到窄依賴就將其并入階段內(nèi)部，遇到寬依賴就形成一個(gè)新的階段繼續(xù)遍歷，直至向前遍歷至TextFileRDD為止.如圖2所示，劃分成了兩個(gè)階段.

3)第三次遍歷：按階段順序執(zhí)行任務(wù)

由第二次遍歷可知，劃分出了兩個(gè)階段，順序執(zhí)行即可.

圖2 基于Spark的ELM數(shù)據(jù)處理流程示意圖

算法3.計(jì)算H矩陣

輸入：訓(xùn)練集X={(xi,ti)|xi∈Rn,ti∈Rm,i=1,2,…,N},隱含層結(jié)點(diǎn)的權(quán)值和偏置wj∈Rn,bj∈R,j=1,2,…,L.

輸出：隱含層節(jié)點(diǎn)輸出矩陣H.

1.將訓(xùn)練集X按行劃分成L個(gè)分區(qū)，隱含層權(quán)重矩陣W按列劃分成L個(gè)分區(qū);

2.//矩陣初始化;

3.value=0;

4.for(i=1;i<=L;i=i+1)do

5. for(j=1;j<=L;j=j+1)

6. //計(jì)算x[i]×w[j];

8. end

9.end

隱含層節(jié)點(diǎn)權(quán)重矩陣w按列分成L個(gè)分區(qū)，每一個(gè)完整的隱含層節(jié)點(diǎn)參數(shù)獨(dú)立地放在一個(gè)分區(qū)中.也就是說(shuō)，w的每個(gè)分區(qū)緩存相對(duì)應(yīng)的隱含層節(jié)點(diǎn)的所有參數(shù)，為了有更多的本地計(jì)算，將待訓(xùn)練的數(shù)據(jù)集X按行分為L(zhǎng)個(gè)分區(qū)，對(duì)于X來(lái)說(shuō)，這將保證在每個(gè)分區(qū)中有1個(gè)或多個(gè)完整的訓(xùn)練數(shù)據(jù)；對(duì)于w來(lái)說(shuō)，可以保證每個(gè)分區(qū)有1個(gè)完整的隱含層節(jié)點(diǎn)參數(shù).計(jì)算矩陣H中元素的值時(shí)，只涉及到公式中訓(xùn)練樣例所在的分區(qū)和對(duì)應(yīng)隱含層節(jié)點(diǎn)參數(shù)所在的分區(qū)數(shù)，減少了網(wǎng)絡(luò)的傳輸.計(jì)算結(jié)果是隱含層節(jié)點(diǎn)輸出矩陣H，將其緩存在L個(gè)分區(qū)的內(nèi)存中.

輸入：矩陣H，主對(duì)角線均為γ的對(duì)角矩陣γL×L.

1.生成矩陣γL×L;

2.//矩陣初始化;

3.outValue=0;

4.//遍歷H的每一個(gè)分區(qū);

5.for(i=1;i<=L;i=i+1)do

6. //遍歷H的每一個(gè)分區(qū);

7. for(j=1;j<=L;j=j+1)do

10. end

11.end

12.//矩陣求和;

13.outValue=outValue+γL×L;

矩陣H分布在L個(gè)分區(qū)中，由U=HTH可知，矩陣U的計(jì)算可以解釋為：Uij的求解相當(dāng)于是矩陣H第i個(gè)分區(qū)與矩陣H第j個(gè)分區(qū)存放的數(shù)據(jù)做向量?jī)?nèi)積運(yùn)算，其中i=1,2,…,L；j=1,2,…,L，即可得出得到矩陣U，此時(shí)U是一個(gè)L×L的小規(guī)模矩陣，與γL×L做矩陣加法即可得出γL×L的值.

算法5.計(jì)算矩陣V

輸入：矩陣H，訓(xùn)練集類別矩陣YN×m.

輸出：矩陣V.

1.將YN×m按列劃分成m個(gè)分區(qū);

2.//矩陣初始化;

3.outValue = 0

4.//遍歷H的每一個(gè)分區(qū);

5.for(i= 1;i<=L;i=i+1)do

6. for(j=1;j<=m;j=j+1)do

9. end

10.end

11.輸出V.

矩陣H分布在L個(gè)分區(qū)中，由V=HTY可知，矩陣V的計(jì)算可以解釋為：Vij的求解相當(dāng)于是矩陣H第i個(gè)分區(qū)與矩陣Y第j個(gè)分區(qū)存放的數(shù)據(jù)做向量?jī)?nèi)積運(yùn)算，其中i=1,2,…,L；j=1,2,…,m，即可得出得到矩陣V的值.

3.4 基于MapReduce和Spark的并行ELM的比較

3.4.1 兩種算法實(shí)現(xiàn)的相同點(diǎn)

3.4.2 兩種算法實(shí)現(xiàn)的不同點(diǎn)

基于MapReduce機(jī)制計(jì)算矩陣UL×L時(shí)，是對(duì)于每一個(gè)樣例x經(jīng)過(guò)與隱含層節(jié)點(diǎn)矩陣H計(jì)算后得到一個(gè)L×L的子矩陣Ui，將所有樣例(即N個(gè)樣例)經(jīng)過(guò)計(jì)算后得到的N個(gè)L×L子矩陣U1,U2,…,UN進(jìn)行矩陣加法運(yùn)算，結(jié)果即為矩陣U.此時(shí)，存在中間結(jié)果的輸出，即存在內(nèi)存→硬盤(pán)→內(nèi)存的數(shù)據(jù)流動(dòng)，網(wǎng)絡(luò)開(kāi)銷不可避免，同時(shí)存在子矩陣的疊加過(guò)程,計(jì)算V矩陣同上；MapReduce并沒(méi)有生成完整的H矩陣，而是逐條處理數(shù)據(jù)，這是由自身機(jī)制造成的；一次MapReduce操作就算出了U和V矩陣，有較強(qiáng)的并行力度.

基于Spark機(jī)制計(jì)算矩陣UL×L時(shí)，這個(gè)矩陣中所有元素均是對(duì)應(yīng)位置分區(qū)里存放元素的向量?jī)?nèi)積運(yùn)算，在此過(guò)程中只涉及兩個(gè)分區(qū)內(nèi)部元素的相互作用，網(wǎng)絡(luò)開(kāi)銷較少，且求得即為最終結(jié)果，不存在子矩陣加和的情況，計(jì)算矩陣V同上；隱含層節(jié)點(diǎn)輸出矩陣H在Spark平臺(tái)上是并行完成的，從邏輯上講，生成了完整的矩陣H，從物理層面上講，矩陣H中的元素散落在各個(gè)分區(qū)中；矩陣U和V模塊內(nèi)部是并行執(zhí)行的，模塊間串行操作，并行度相對(duì)較弱.

4 實(shí)驗(yàn)結(jié)果及分析

4.1 實(shí)驗(yàn)結(jié)果對(duì)比分析

4.1.1 并行ELM算法在MapReduce和spark平臺(tái)上執(zhí)行時(shí)間對(duì)比

在2個(gè)UCI數(shù)據(jù)集和3個(gè)人工數(shù)據(jù)集上，對(duì)基于MapReduce的ELM和基于Spark的ELM進(jìn)行了對(duì)比分析研究.其中三個(gè)人工數(shù)據(jù)集均由高斯分布產(chǎn)生，第一個(gè)人工數(shù)據(jù)集是二類數(shù)據(jù)集，服從的概率分布是：

第二個(gè)人工數(shù)據(jù)集是三類數(shù)據(jù)集，服從的概率分布是：

第三個(gè)人工數(shù)據(jù)集是四類數(shù)據(jù)集，服從的概率分布是：

該實(shí)驗(yàn)是在擁有1個(gè)主節(jié)點(diǎn)和7個(gè)從節(jié)點(diǎn)的云計(jì)算平臺(tái)上進(jìn)行的，在云計(jì)算平臺(tái)上搭建了Hadoop和Spark兩個(gè)運(yùn)行環(huán)境，云計(jì)算平臺(tái)節(jié)點(diǎn)的基本配置信息和功能規(guī)劃如表2和表3所示，主機(jī)的基本配置如表4所示，實(shí)驗(yàn)所需數(shù)據(jù)集的基本信息如表5所示.實(shí)驗(yàn)將從訓(xùn)練數(shù)據(jù)維度、訓(xùn)練數(shù)據(jù)規(guī)模和隱層節(jié)點(diǎn)個(gè)數(shù)三個(gè)方面作為實(shí)驗(yàn)參數(shù)對(duì)含有10、20、30、50、100個(gè)隱含層節(jié)點(diǎn)的ELM網(wǎng)絡(luò)模型，比較了基于MapReduce和Spark的并行ELM算法的執(zhí)行時(shí)間，實(shí)驗(yàn)結(jié)果列于表6～表10中.對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行分析，得出了結(jié)論：基于Spark的ELM算法的效率遠(yuǎn)遠(yuǎn)高于基于MapReduce的效率，隨著隱含層節(jié)點(diǎn)個(gè)數(shù)逐漸增多，Spark平臺(tái)的優(yōu)勢(shì)愈加明顯.在下一節(jié)中，我們將從理論層面分析產(chǎn)生該現(xiàn)象的原因.

表2 云計(jì)算平臺(tái)節(jié)點(diǎn)的基本配置信息

Table 2 Basic configuration of the nodes of the cloud compution platform

配置項(xiàng)目配置情況處理(CPU)InterXeonE5-46032.0GHz(雙核)內(nèi)存8GBRDIMM硬盤(pán)1TB網(wǎng)卡Broadcom5720QP1Gb網(wǎng)絡(luò)子卡網(wǎng)絡(luò)設(shè)備華為S3700系列以太網(wǎng)交換機(jī)操作系統(tǒng)Ubuntukylin13.04云計(jì)算平臺(tái)Hadoop-2.7.3,Spark-2.1.0JDK版本Jdk-7u71-linux-i586Scala版本Scala-2.11.0

表3 云平臺(tái)的節(jié)點(diǎn)功能規(guī)劃

Table 3 Role assignment of the nodes of the cloud computing platform

主機(jī)名IP地址節(jié)點(diǎn)類型master10.187.86.242NameNode,Master,ResourceManagernode110.187.86.243DataNode,Worker,NodeManagernode210.187.86.244DataNode,Worker,NodeManagernode310.187.86.245DataNode,Worker,NodeManagernode410.187.86.246DataNode,Worker,NodeManagernode510.187.86.247DataNode,Worker,NodeManagernode610.187.86.248DataNode,Worker,NodeManagernode710.187.86.249DataNode,Worker,NodeManager

表4 主機(jī)基本配置信息

Table 4 Basic configuration of the host

配置項(xiàng)目配置情況處理器(CPU)IntelXeonCPUE5-16503.5GHz內(nèi)存16GB硬盤(pán)500G操作系統(tǒng)Win10JDK版本jdk-8u144-windows-x64MapReduce程序環(huán)境Eclipse-Phtotn-Releae-4.8.Scala版本Scala-2.11.0Spark程序環(huán)境Eclipse-4.7.0

表5 實(shí)驗(yàn)數(shù)據(jù)集

Table 5 Basic information of data sets

數(shù)據(jù)集類別數(shù)屬性數(shù)節(jié)點(diǎn)類型Gauss1221000000Gauss2321200000Gauss3431000000Covtype754581012Skin23245057

表6 兩種算法在Gauss1數(shù)據(jù)集上實(shí)驗(yàn)結(jié)果的對(duì)比(單位：s)

Table 6 Comparison of experimental results of two algorithms on data set Gauss1(s)

隱結(jié)點(diǎn)個(gè)數(shù)SparkELMMapReduceELM1018442320346845305011923509696076100185673696

表7 兩種算法在Gauss2數(shù)據(jù)集上實(shí)驗(yàn)結(jié)果的對(duì)比(單位：s)

Table 7 Comparison of experimental results of two algorithms on data set Gauss2(s)

隱結(jié)點(diǎn)個(gè)數(shù)SparkELMMapReduceELM102262302041919933060747945010656025100223571458

表8 兩種算法在Gauss3數(shù)據(jù)集上實(shí)驗(yàn)結(jié)果的對(duì)比(單位：s)

Table 8 Comparison of experimental results of two algorithms on data set Gauss3(s)

隱含層個(gè)數(shù)SparkELMMapReduceELM1019520520353690305181478508844205100190032442

4.1.2 并行ELM算法在MapReduce和Spark平臺(tái)上speedUp指標(biāo)和sizeUp指標(biāo)對(duì)比

以gauss3數(shù)據(jù)集的0.1倍作為本實(shí)驗(yàn)的原始數(shù)據(jù)集，我們將對(duì)基于MapReduce和Spark平臺(tái)的ELM算法進(jìn)行并行性能的評(píng)估.實(shí)驗(yàn)中采取的訓(xùn)練數(shù)據(jù)集分別是原始數(shù)據(jù)集的5倍、8倍和10倍，同時(shí)在并行度為7、14、28的平臺(tái)上運(yùn)行隱層節(jié)點(diǎn)個(gè)數(shù)為10、20、30的ELM并行算法，根據(jù)speedUp指標(biāo)和sizeUp指標(biāo)對(duì)兩種大數(shù)據(jù)平臺(tái)進(jìn)行比較說(shuō)明，實(shí)驗(yàn)結(jié)果如圖3和圖4所示.

speedUp(m)=程序運(yùn)行在1臺(tái)設(shè)備上的執(zhí)行時(shí)間/程序運(yùn)行在m臺(tái)設(shè)備上的執(zhí)行時(shí)間

sizeUp(m)=程序處理m倍的數(shù)據(jù)集執(zhí)行時(shí)間/程序處理原始數(shù)據(jù)集執(zhí)行時(shí)間

表9 兩種算法在Skin數(shù)據(jù)集上實(shí)驗(yàn)結(jié)果的對(duì)比(單位：s)

Table 9 Comparison of experimental results of two algorithms on data set Skin(s)

隱結(jié)點(diǎn)個(gè)數(shù)SparkELMMapReduceELM10562802089116730133279750215863810043543432

表10 兩種算法在covertype數(shù)據(jù)集上實(shí)驗(yàn)結(jié)果的對(duì)比(單位：s)

Table 10 Comparison of experimental results of two algorithms on data set covertype(s)

隱結(jié)點(diǎn)個(gè)數(shù)SparkELMMapReduceELM107685202312483032054450508167110010649704

圖3是隱層節(jié)點(diǎn)分別是10、20、30，并行度分別是7、14、28的ELM算法在大數(shù)據(jù)平臺(tái)MapReduce和Spark平臺(tái)上的對(duì)比情況，結(jié)果顯示：基于Spark平臺(tái)的ELM算法的speedUp值總體高于基于MapReduce平臺(tái)的ELM算法的speedUp值，隨著隱層節(jié)點(diǎn)數(shù)的增多，這種差異更加突出.speedUp折線圖近似于一條直線，且斜率有減小的趨勢(shì)這是因?yàn)椴⑿杏?jì)算將不可避免的增加在不同機(jī)器上的數(shù)據(jù)交換，造成時(shí)間的浪費(fèi).圖4是隱層節(jié)點(diǎn)分別是10、20、30，訓(xùn)練數(shù)據(jù)集分別是原始數(shù)據(jù)集的5倍、8倍、10倍.由圖4可知，基于Spark平臺(tái)的ELM算法的sizeUp值總體低于基于MapReduce平臺(tái)的ELM算法sizeUp值，也就是說(shuō)，訓(xùn)練的數(shù)據(jù)集規(guī)模越大時(shí)，Spark平臺(tái)上數(shù)據(jù)處理效率越突出.這是因?yàn)镾park是一種基于內(nèi)存計(jì)算的大數(shù)據(jù)平臺(tái)，中間結(jié)果可以緩存至內(nèi)存中，且只有RDD的行動(dòng)算子才會(huì)觸發(fā)計(jì)算，相較于MapReduce平臺(tái)，不存在中間數(shù)據(jù)流動(dòng)至HDFS的情況，數(shù)據(jù)IO操作較少，但在MapReduce平臺(tái)上隨著隱層節(jié)點(diǎn)增多時(shí)，在算法執(zhí)行過(guò)程中會(huì)存在更大規(guī)模的矩陣運(yùn)算，這將導(dǎo)致更大規(guī)模的數(shù)據(jù)IO操作，造成嚴(yán)重耗時(shí).

圖3 大數(shù)據(jù)平臺(tái)的SpeedUp性能對(duì)比

圖4 大數(shù)據(jù)平臺(tái)的sizeUp性能對(duì)比

4.2 理論分析

在本節(jié)中，針對(duì)MapReduce和Spark這兩種大數(shù)據(jù)框架，受文獻(xiàn)[23]的啟發(fā)，我們從算法執(zhí)行時(shí)間、同步次數(shù)、讀寫(xiě)文件數(shù)目和分類器的泛化性能4個(gè)方面進(jìn)行比較和分析.

4.2.1 算法執(zhí)行時(shí)間對(duì)比分析

基于大數(shù)據(jù)平臺(tái)的ELM算法執(zhí)行時(shí)間T為：T=Tr+Ts+Tt+Tw(其中Tr表示文件讀取時(shí)間，Ts表示中間數(shù)據(jù)排序時(shí)間，Tt表示中間數(shù)據(jù)傳輸時(shí)間，Tw表示文件寫(xiě)出時(shí)間).其中，Tr=文件讀速度×輸入文件大??；Tw=文件寫(xiě)速度×輸出文件大小.

基于不同大數(shù)據(jù)框架下的并行ELM運(yùn)行機(jī)制，導(dǎo)致程序執(zhí)行時(shí)間的差異.不同的只是大數(shù)據(jù)處理平臺(tái)，而程序的輸入數(shù)據(jù)和輸出數(shù)據(jù)、網(wǎng)絡(luò)傳輸速度以及文件讀寫(xiě)速度在實(shí)驗(yàn)中作為常量存在，其差異造成的影響忽略不計(jì).此時(shí)Tr和Tw在這兩種大數(shù)據(jù)平臺(tái)下的ELM算法中的值近似相同，其差異并不是本文中要研究的重點(diǎn)，在此不進(jìn)行詳細(xì)分析.主要對(duì)Ts和Tt在兩個(gè)大數(shù)據(jù)平臺(tái)下的差異進(jìn)行精要闡述說(shuō)明.

a)基于大數(shù)據(jù)平臺(tái)的ELM算法Ts中間數(shù)據(jù)排序時(shí)間的比較

對(duì)于Spark平臺(tái)來(lái)說(shuō)，不存在中間數(shù)據(jù)排序這一過(guò)程，故而:

Ts-spark=0

而對(duì)于MapReduce平臺(tái)來(lái)說(shuō)，每次執(zhí)行shuffle操作時(shí)，對(duì)中間數(shù)據(jù)的排序過(guò)程是必不可少的，目的是通過(guò)對(duì)中間數(shù)據(jù)的排序，實(shí)現(xiàn)初步的歸并操作這一步驟，確保一個(gè)Map任務(wù)最終只有一個(gè)有序的中間數(shù)據(jù)文件輸出，緩解網(wǎng)絡(luò)傳輸壓力，具體過(guò)程如下：在Map階段，對(duì)每一分區(qū)的數(shù)據(jù)分別進(jìn)行排序，若共有P個(gè)Map任務(wù)，每個(gè)Map任務(wù)負(fù)責(zé)處理p條數(shù)據(jù)，采用快速排序的機(jī)制進(jìn)行排序，則：

Ts-mr=Plogp

此時(shí)：

Ts-mr>Ts-spark

b)基于大數(shù)據(jù)平臺(tái)的ELM算法Tt中間數(shù)據(jù)傳輸時(shí)間的比較

在中間數(shù)據(jù)傳輸時(shí)間的比較中，我們主要從數(shù)據(jù)傳輸數(shù)量和數(shù)據(jù)存放位置兩方面進(jìn)行比較說(shuō)明.基于MapReduce的shuffle機(jī)制，在Map任務(wù)結(jié)束后傳至Reduce端之前，會(huì)存在文件合并的情況，這是MapReduce獨(dú)有的特色，因此當(dāng)MapReduce和Spark平臺(tái)處理相同的數(shù)據(jù)時(shí)，MapReduce平臺(tái)的中間數(shù)據(jù)傳輸量會(huì)小于Spark的中間數(shù)據(jù)傳輸量.當(dāng)傳輸速率相同時(shí)，則存在:

Tt-mr-Files

Spark是一種基于內(nèi)存計(jì)算的大數(shù)據(jù)平臺(tái)，即所有的操作都是基于RDD的操作，中間數(shù)據(jù)也是以RDD的形式在內(nèi)存中運(yùn)算并存儲(chǔ)，這是由Spark自身的機(jī)制決定的.MapReduce從硬盤(pán)上讀取數(shù)據(jù)，經(jīng)過(guò)Map計(jì)算后產(chǎn)生的中間數(shù)據(jù)以文件的形式存儲(chǔ)于分布式文件系統(tǒng)HDFS上，然后再?gòu)腍DFS上讀取并進(jìn)行Reduce計(jì)算.顯而易見(jiàn)，這比Spark的中間數(shù)據(jù)傳輸時(shí)間要長(zhǎng)得多.所以：

Tt-mr-io>Tt-spark-memory

HDFS讀取操作的時(shí)長(zhǎng)遠(yuǎn)遠(yuǎn)大于內(nèi)存操作，因此：

Tt-mr-Files+Tt-mr-io>Tt-spark-Files+Tt-spark-memory

綜上所述，可得：

Tt-mr>Tt-spark

根據(jù)以上兩方面的分析，可得出結(jié)論ELM算法在MapReduce平臺(tái)上的運(yùn)行時(shí)間大于在Spark平臺(tái)上的運(yùn)行時(shí)間.

4.2.2 同步次數(shù)對(duì)比分析

同步操作要求當(dāng)前階段中的所有節(jié)點(diǎn)都執(zhí)行完畢才開(kāi)始下一階段.在MapReduce框架下，所有的Map節(jié)點(diǎn)都完成之后，Reduce階段才開(kāi)始執(zhí)行，這是典型的同步操作.一次MapReduce操作，記一次同步.根據(jù)前面的分析可知，在基于MapReduce框架下的ELM算法，并行操作主要是進(jìn)行矩陣H、矩陣U和矩陣V的運(yùn)算，它主要是通過(guò)一次MapReduce操作實(shí)現(xiàn)了這三個(gè)矩陣的計(jì)算，因此，同步次數(shù)是1.

由前面基于Spark框架下的ELM算法流程可知，首先并行計(jì)算出矩陣H，矩陣H計(jì)算完畢后，執(zhí)行矩陣U和矩陣V的計(jì)算，這二者的計(jì)算可同時(shí)執(zhí)行，因此算法實(shí)現(xiàn)過(guò)程中的同步次數(shù)是2.

4.2.3 讀寫(xiě)文件數(shù)目對(duì)比分析

在MapReduce框架下，由于存在分區(qū)內(nèi)部排序操作，分區(qū)間的數(shù)據(jù)用偏移量標(biāo)記，可以將每一個(gè)Map中不同分區(qū)間的數(shù)據(jù)匯總成一個(gè)大的中間數(shù)據(jù)文件，即一個(gè)Map對(duì)應(yīng)一個(gè)中間文件.所以在MapReduce中，讀寫(xiě)文件數(shù)目是Map任務(wù)的數(shù)量.但在Spark平臺(tái)上，RDD是以分區(qū)為單位并行執(zhí)行的，所以在Spark中，讀寫(xiě)文件數(shù)目取決于RDD的分區(qū)數(shù).盡管并行ELM算法在這兩個(gè)大數(shù)據(jù)平臺(tái)上的具體實(shí)現(xiàn)有所差異，但這并不是導(dǎo)致讀寫(xiě)文件數(shù)目不同的原因，這是由大數(shù)據(jù)平臺(tái)自身的機(jī)制造成的.在MapReduce中，待處理的數(shù)據(jù)集逐條輸入至Map任務(wù)中，在每個(gè)Map任務(wù)中，根據(jù)實(shí)際需求生成一個(gè)大的數(shù)據(jù)文件，寫(xiě)入HDFS中；Reduce節(jié)點(diǎn)再?gòu)腍DFS中讀取這些文件，根據(jù)不同的需求執(zhí)行不同的操作.在基于MapReduce框架下的ELM算法中，并行操作主要是進(jìn)行矩陣H、U和V的運(yùn)算，它通過(guò)一次MapReduce操作實(shí)現(xiàn)了這三個(gè)矩陣的計(jì)算，讀寫(xiě)文件數(shù)目等于Map任務(wù)數(shù)目，讀寫(xiě)文件數(shù)目只與該算法執(zhí)行過(guò)程中Map任務(wù)數(shù)目有關(guān)；在Spark平臺(tái)上的一切操作都是對(duì)RDD的操作，以圖2為例，數(shù)據(jù)劃分為3個(gè)分區(qū)進(jìn)行并行處理，每個(gè)分區(qū)對(duì)應(yīng)一份數(shù)據(jù)文件，數(shù)據(jù)經(jīng)過(guò)TextFileRDD后，將數(shù)據(jù)分成3份，讀入3個(gè)文件中進(jìn)行并行操作，當(dāng)數(shù)據(jù)經(jīng)過(guò)mapPartitionRDD后，同一個(gè)文件中的數(shù)據(jù)會(huì)進(jìn)入shuffleRDD中不同的分區(qū)，這就會(huì)導(dǎo)致mapPartitionRDD每個(gè)分區(qū)中的一個(gè)數(shù)據(jù)文件拆分3個(gè)子數(shù)據(jù)文件，分別對(duì)應(yīng)shuffleRDD中不同的分區(qū)，實(shí)現(xiàn)文件的reduceByKey操作，此時(shí)讀寫(xiě)文件數(shù)目為3+3+3+3+3×3+3=24.其中，分區(qū)數(shù)3是可手動(dòng)控制的超參數(shù)，如當(dāng)分區(qū)數(shù)重置為4時(shí)，文件讀寫(xiě)數(shù)目=4+4+4+4+4×4+4=36.Spark平臺(tái)讀寫(xiě)文件數(shù)目只與RDD中的分區(qū)數(shù)有關(guān).

4.2.4 分類器的泛化性能對(duì)比分析

基于MapReduce和Spark平臺(tái)的并行ELM，使用了相同的方法計(jì)算從隱含層到輸出層之間的參數(shù)矩陣β，即在這兩個(gè)大數(shù)據(jù)平臺(tái)下，計(jì)算兩個(gè)中間結(jié)果矩陣U(即HTH)和矩陣V(即HTY)，當(dāng)所有的相關(guān)參數(shù)均相等時(shí)，用該算法對(duì)相同的訓(xùn)練數(shù)據(jù)訓(xùn)練分類器，顯而易見(jiàn)，訓(xùn)練出的分類器也是相同的，它們的泛化性能一致.因此在這兩個(gè)平臺(tái)下，相同的測(cè)試數(shù)據(jù)會(huì)得到相同的精度.

5 結(jié)束語(yǔ)

本文通過(guò)對(duì)基于MapReduce和Spark平臺(tái)的兩種并行ELM進(jìn)行比較研究，得出如下結(jié)論：1)從算法實(shí)現(xiàn)層面上看，這兩個(gè)大數(shù)據(jù)平臺(tái)均并行計(jì)算了矩陣H、U和V，計(jì)算過(guò)程大致相同；2)基于Spark的ELM的執(zhí)行效率遠(yuǎn)遠(yuǎn)高于基于MapReduce的ELM的執(zhí)行效率，而且從大數(shù)據(jù)平臺(tái)理論層面和并行指標(biāo)speedUp，sizeUp證明了這一結(jié)果的必然性；3)基于MapReduce的ELM在同步次數(shù)方面優(yōu)于Spark平臺(tái)的ELM；4)從讀寫(xiě)文件數(shù)目來(lái)看，基于MapReduce的ELM需要讀寫(xiě)文件數(shù)目與Map任務(wù)個(gè)數(shù)有關(guān)，而基于Spark的ELM讀寫(xiě)文件數(shù)目與分區(qū)數(shù)有關(guān)；5)從分類器泛化能力來(lái)看，兩種并行ELM并無(wú)差別.