基于Spark的OS-ELM并行化算法

鄧萬(wàn)宇，楊麗霞

(西安郵電大學(xué) 計(jì)算機(jī)學(xué)院，陜西 西安 710121)

基于Spark的OS-ELM并行化算法

鄧萬(wàn)宇，楊麗霞

(西安郵電大學(xué) 計(jì)算機(jī)學(xué)院，陜西 西安 710121)

摘要:針對(duì)Spark平臺(tái)的彈性分布式數(shù)據(jù)集并行計(jì)算框架機(jī)制，提出一種在線連續(xù)極限學(xué)習(xí)機(jī)并行處理的改進(jìn)算法。利用分離在線連續(xù)極限學(xué)習(xí)機(jī)矩陣之間的依賴關(guān)系，將大規(guī)模數(shù)據(jù)中的高度復(fù)雜的矩陣分布到Spark集群中并行化計(jì)算, 并行計(jì)算多個(gè)增量數(shù)據(jù)塊的隱藏層輸出矩陣，實(shí)現(xiàn)OS-ELM對(duì)矩陣的加速求解。實(shí)驗(yàn)結(jié)果表明，該算法在保持精度的同時(shí)可有效縮短學(xué)習(xí)時(shí)間，改善了大數(shù)據(jù)的擴(kuò)展能力。

關(guān)鍵詞:在線連續(xù)極限學(xué)習(xí)機(jī)；大數(shù)據(jù)；Spark；并行計(jì)算

在線連續(xù)極限學(xué)習(xí)機(jī)[1](onlinesequentialextremelearningmachine，OS-ELM)是極限學(xué)習(xí)機(jī)(extremelearningmachine，ELM)有效支持在線連續(xù)學(xué)習(xí)的改進(jìn)算法之一，已廣泛應(yīng)用在數(shù)據(jù)擬合、分類預(yù)測(cè)、動(dòng)態(tài)噪聲控制等領(lǐng)域[2]。

OS-ELM算法受制于龐大的數(shù)據(jù)量、機(jī)器配置(如CPU、內(nèi)存、磁盤)等資源，為提高集成在線順序極限學(xué)習(xí)機(jī)的分類準(zhǔn)確率提出一種集成方法[3]；通過(guò)調(diào)整網(wǎng)絡(luò)結(jié)構(gòu)給出了一種改進(jìn)的在線序列ELM算法[4]。這些方法都是在單機(jī)串行環(huán)境下運(yùn)行，不僅耗時(shí)而且也不能很好地執(zhí)行分類和回歸分析任務(wù)。在并行環(huán)境下，OS-ELM只少量在MapReduce分布式框架[5]運(yùn)行，但MapReduce中的大量磁盤I/O操作導(dǎo)致其響應(yīng)延遲加劇，尤其在面對(duì)OS-ELM運(yùn)算密集的機(jī)器學(xué)習(xí)算法時(shí)更需要用戶具備非常專業(yè)的程序優(yōu)化能力和深度優(yōu)化并行調(diào)度策略。

本文擬通過(guò)Spa-rk平臺(tái)的彈性分布式數(shù)據(jù)集(ResilientDistributedDatasets,RDD)并行計(jì)算框架[6-7]，對(duì)OS-ELM進(jìn)行并行化設(shè)計(jì)，以期改善OS-ELM算法對(duì)數(shù)據(jù)規(guī)模增大的適應(yīng)性。

1OS-ELM算法描述

OS-ELM是針對(duì)動(dòng)態(tài)數(shù)據(jù)應(yīng)用研制的在線增量式快速學(xué)習(xí)算法[2]。假設(shè)輸入樣本N個(gè)，第j個(gè)樣本設(shè)定的訓(xùn)練集

Ω={(xj,tj)|xj=(xj1,…,xjn)T∈Rn,

tj=(tj1,…,tjm)∈Rm,j=1,2,…,N}

其中xj=(xj1,…,xjn)T為輸入數(shù)據(jù)，tj=(tj1,…,tjm)T為期望輸出數(shù)據(jù)，n為輸入樣本數(shù)，m為樣本類別。

神經(jīng)網(wǎng)絡(luò)模型為

(j=1,2,…,N)。

(1)

隱含層節(jié)點(diǎn)數(shù)為L(zhǎng)，隨機(jī)生成輸入層與隱藏層的連接權(quán)值ai和隱含層閾值bi，βi為第i個(gè)隱藏層節(jié)點(diǎn)到輸出節(jié)點(diǎn)的輸出權(quán)值。當(dāng)運(yùn)用增加型隱藏層節(jié)點(diǎn)時(shí)對(duì)第j個(gè)樣本，第i個(gè)隱藏層結(jié)點(diǎn)來(lái)說(shuō)，隱藏層輸出為G(ai,bi,xj)=g(ai·xj+bi)。OS-ELM算法包括初始化階段和在線連續(xù)學(xué)習(xí)階段兩個(gè)階段[8-9]。

計(jì)算初始隱藏層輸出矩陣

(2)

已知目標(biāo)輸出

(3)

計(jì)算初始輸出權(quán)值β0也就是計(jì)算‖H0β-T0‖最小值問(wèn)題[10]。由式(1)可以轉(zhuǎn)寫為矩陣形式

HB=T[10],

又由β=H?T,H?=(HTH)-1HT得出

(4)

其中

(2)在線連續(xù)學(xué)習(xí)階段：Mk+1，βk+1的運(yùn)算都需要計(jì)算中間變量Hk+1。當(dāng)輸入第k+1個(gè)樣本數(shù)據(jù)，計(jì)算隱含層的輸出矩陣Hk+1，則輸出權(quán)值βk+1可表示為

(5)

(6)

其中I為單位矩陣。

2OS-ELM并行化設(shè)計(jì)及實(shí)現(xiàn)

2.1基本原理

根據(jù)OS-ELM算法矩陣之間的依賴關(guān)系，在線階段每次新到來(lái)的增量訓(xùn)練數(shù)據(jù)集的輸出向量都要依賴于前一個(gè)數(shù)據(jù)集的輸出進(jìn)行更新。對(duì)計(jì)算每個(gè)增量訓(xùn)練數(shù)據(jù)集的隱藏層輸出矩陣之間互不影響，對(duì)其可進(jìn)行并行化處理。

OS-ELM算法利用增量塊來(lái)選取訓(xùn)練樣本，即從分布式文件系統(tǒng)(HighDensityFixedServices，HDFS)接收k個(gè)數(shù)據(jù)樣本，每個(gè)數(shù)據(jù)塊按Hadoop平臺(tái)所設(shè)塊的大小進(jìn)行分塊，對(duì)數(shù)據(jù)進(jìn)行RDD封裝，形成多個(gè)RDD。每個(gè)RDD都分成不同分片，每個(gè)分片中的每條記錄都需要進(jìn)行一次Map操作，當(dāng)數(shù)據(jù)的記錄量過(guò)多時(shí)會(huì)加消耗，使用MapPartition來(lái)代替Map對(duì)每個(gè)分片進(jìn)行計(jì)算 。計(jì)算該數(shù)據(jù)集的隱含層輸出矩陣Hk，然后將每一組增量數(shù)據(jù)傳遞給Reduce函數(shù)。Reduce函數(shù)通過(guò)讀取Hk+1,不斷更新Mk+1和輸出向量βk+1，最終計(jì)算出整個(gè)訓(xùn)練集的輸出向量β。基于Spark的OS-ELM算法框架如圖1所示。

圖1　基于Spark的OS-ELM算法框架

2.2基于Spark的OS-ELM算法設(shè)計(jì)

為了實(shí)現(xiàn)對(duì)增量訓(xùn)練數(shù)據(jù)塊隱藏層輸出矩陣并行化設(shè)計(jì)，對(duì)OS-ELM算法進(jìn)行改進(jìn)。該改進(jìn)算法命名為基于Spark在線連續(xù)極限學(xué)習(xí)機(jī)并行算法(SPOS-ELM)。

SPOS-ELM算法如下。

輸入：訓(xùn)練數(shù)據(jù)集

Ω={(xj,tj)|xj=(xj1,…,xjn)T∈Rn,

tj=(tj1,…,tjm)T∈Rm,j=1,2,…,N}

隱藏層節(jié)點(diǎn)個(gè)數(shù)L，訓(xùn)練數(shù)據(jù)塊k+1。

輸出：k+1塊訓(xùn)練數(shù)據(jù)集的輸出向量βk+1。

步驟1初始化階段，隨機(jī)生成的隱藏層輸入權(quán)值ai，隱藏層閾值bi。

步驟2根據(jù)式(2)計(jì)算初始隱藏層輸出矩陣H0。

步驟3根據(jù)式(4)計(jì)算初始輸出權(quán)值β0。

步驟4在線學(xué)習(xí)階段,并行計(jì)算增量k+1個(gè)數(shù)據(jù)塊的隱藏層輸出矩陣(H1,…,Hk+1)。將中間變量隱藏層輸出矩陣的分布式求解得出的Hk+1進(jìn)行緩存，并用Spark RDD形式對(duì)訓(xùn)練完成的中間變量Hk+1進(jìn)行封裝。

步驟5根據(jù)式(5)和式(6)循環(huán)迭代訓(xùn)練計(jì)算出(M1,M2,…,Mk+1)

步驟6根據(jù)式(5)依次計(jì)算(β1,β2,…,βk+1),輸出最后β值。

2.3基于Spark的OS-ELM算法實(shí)現(xiàn)

OS-ELM算法在Spark上的并行實(shí)現(xiàn)主要分為隱藏層輸出矩陣的分布式求解過(guò)程和隱藏層輸出矩陣的Reduce過(guò)程。

(1)隱藏層輸出矩陣的分布式求解過(guò)程

當(dāng)數(shù)據(jù)集合Ω的RDD分成若干分片，為了避免大量不必要的通信開銷，選擇將主節(jié)點(diǎn)參數(shù)復(fù)制到各從節(jié)點(diǎn)上，而不是傳遞給各分片。廣播變量[10]是一種緩存于所有從節(jié)點(diǎn)的只讀型變量，應(yīng)用于所有從節(jié)點(diǎn)的數(shù)據(jù)分片。

輸入：Spark集群主節(jié)點(diǎn)構(gòu)造隱藏層權(quán)值ai，隱藏層閾值bi，i=1,…,k,隱藏層節(jié)點(diǎn)L個(gè)，激勵(lì)函數(shù)g(xi)，并將ai,bi,g(xi),以廣播變量的形式分發(fā)到各個(gè)從節(jié)點(diǎn)。

輸出：隱藏層輸出矩陣Hi,目標(biāo)輸出Ti。

各個(gè)從節(jié)點(diǎn)計(jì)算每個(gè)增量樣本的隱藏層輸出矩陣Hi,并匯總各個(gè)從節(jié)點(diǎn)的結(jié)果給主節(jié)點(diǎn)。

(2)隱藏層輸出矩陣的Reduce過(guò)程

輸入：(key,value)key是每個(gè)增量塊的序號(hào)，value是每個(gè)增量塊序號(hào)所對(duì)應(yīng)的隱藏層輸出矩陣和目標(biāo)輸出向量Hi和Ti。

輸出：k+1塊數(shù)據(jù)集輸出權(quán)值βk+1。

步驟1通過(guò)各從節(jié)點(diǎn)給主節(jié)點(diǎn)的結(jié)果進(jìn)行迭代計(jì)算輸出向量βk+1。

步驟2根據(jù)式(5)和式(6)循環(huán)計(jì)算出(M1,M1,…,Mk+1)。

步驟3根據(jù)式(5)依次計(jì)算(β1,β2,…,βk+1)，輸出最后β值。

3實(shí)驗(yàn)結(jié)果與分析

3.1實(shí)驗(yàn)設(shè)置

實(shí)驗(yàn)采用一臺(tái)PC作為主節(jié)點(diǎn)和服務(wù)器，5臺(tái)PC作為計(jì)算節(jié)點(diǎn)即從節(jié)點(diǎn)。軟硬件配置為4核XeonE5440(2.83G)CPU； 16GBytes內(nèi)存;Ubuntu14.04操作系統(tǒng);IDEA開發(fā)工具;scala開發(fā)語(yǔ)言[12]；Hadoop2.5.0；Java1.7.0_74；Spark1.3.1。

對(duì)基于Spark平臺(tái)的OS-ELM并行算法分別在精度、訓(xùn)練時(shí)間和加速比等3個(gè)方面進(jìn)行測(cè)試比較。所使用數(shù)據(jù)集均為L(zhǎng)IBSVM數(shù)據(jù)[13-14]。從LIVSVM數(shù)據(jù)中選定Shuttle、Ijcnn、Covtype3種真實(shí)的分類數(shù)據(jù)集以及CaliforniaHousing、Servo、Bank、Delta-Ailerons4種回歸數(shù)據(jù)集對(duì)該并行算法性能進(jìn)行驗(yàn)證。數(shù)據(jù)信息分別如表1和表2所示。

表1　回歸數(shù)據(jù)集信息

表2　分類數(shù)據(jù)集信息

3.2評(píng)估結(jié)果

3.2.1真實(shí)數(shù)據(jù)的精確度測(cè)試

利用表1和表2的數(shù)據(jù)集在Spark集群通過(guò)并行OS-ELM算法程序?qū)Ω鱾€(gè)數(shù)據(jù)集進(jìn)行測(cè)試。表3和表4的結(jié)果分別為回歸和分類數(shù)據(jù)集在程序中的測(cè)試結(jié)果。

表3　回歸數(shù)據(jù)的評(píng)估結(jié)果

表4　分類數(shù)據(jù)的評(píng)估結(jié)果

可以看出SPOS-ELM的訓(xùn)練精度與原始OS-ELM沒(méi)有多大區(qū)別，證明該改進(jìn)算法的精度準(zhǔn)確性和算法改進(jìn)的正確性。

3.2.2檢查訓(xùn)練速度與節(jié)點(diǎn)之間的關(guān)系

通過(guò)控制Spark集群節(jié)點(diǎn)數(shù)量從 1、2、3、4、5、6 來(lái)檢查各個(gè)數(shù)據(jù)集在不同節(jié)點(diǎn)的訓(xùn)練速度。通過(guò)圖2顯示了不同數(shù)據(jù)集在各個(gè)節(jié)點(diǎn)6上的訓(xùn)練時(shí)間。

圖2　各個(gè)數(shù)據(jù)集在不同節(jié)點(diǎn)的訓(xùn)練時(shí)間

由圖2可以看出，隨著節(jié)點(diǎn)數(shù)的增多，所有的數(shù)據(jù)集的訓(xùn)練速度加快，訓(xùn)練的時(shí)間縮短。如果數(shù)據(jù)集較小，隨著節(jié)點(diǎn)數(shù)增多時(shí)間上并沒(méi)有很明顯的改變。然而，對(duì)于數(shù)據(jù)集越大的數(shù)據(jù)，數(shù)據(jù)集的訓(xùn)練速度進(jìn)一步加快，說(shuō)明SPOS-ELM算法并不適合數(shù)據(jù)集較小的數(shù)據(jù)。

3.2.3擴(kuò)展性測(cè)試

對(duì)數(shù)據(jù)做可伸縮性測(cè)試，用于可伸縮性測(cè)試的參數(shù)如表5所示。訓(xùn)練樣本的數(shù)量和屬性擴(kuò)展基于CaliforniaHousing以循環(huán)的方式復(fù)制原始數(shù)據(jù)。

表5　規(guī)范合成可伸縮性測(cè)試的數(shù)據(jù)

圖3為可伸縮性數(shù)據(jù)CaliforniaHousing加速比與節(jié)點(diǎn)的數(shù)量的關(guān)系。訓(xùn)練數(shù)據(jù)對(duì)取值范圍內(nèi)大小為40k,320k和1 280k的加速比進(jìn)行比較。

圖3　可擴(kuò)展性數(shù)據(jù)加速比與節(jié)點(diǎn)的關(guān)系

由圖3可見(jiàn)，隨訓(xùn)練數(shù)據(jù)增大，對(duì)于SPOS-ELM加速比更大。但是，隨著節(jié)點(diǎn)數(shù)增多，多個(gè)節(jié)點(diǎn)和PC之間的協(xié)同操作的開銷成本增加。越小的訓(xùn)練數(shù)據(jù)隨著節(jié)點(diǎn)增多加速比反而變得較低，從而進(jìn)一步證實(shí)SPOS-ELM適合大規(guī)模學(xué)習(xí)。

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

基于Spark平臺(tái)對(duì)OS-ELM算法進(jìn)行并行化處理。通過(guò)利用分離在線連續(xù)極限學(xué)習(xí)機(jī)矩陣之間的依賴關(guān)系，進(jìn)行矩陣分解。以在精度準(zhǔn)確性、加速比、擴(kuò)展性等指標(biāo)從理論和實(shí)驗(yàn)結(jié)果兩個(gè)方面對(duì)并行算法進(jìn)行了評(píng)價(jià)。實(shí)驗(yàn)結(jié)果表明，該算法在保持精度的同時(shí)也成功實(shí)現(xiàn)算法效率的提升，比原始串行OS-ELM具有更好的可擴(kuò)展能力，提高了算法的準(zhǔn)確性。

參考文獻(xiàn)

[1]HUANGGB,ZHUQY,SIEWCK.ExtremeLearni-ngMachine:TheoryandApplications[J].Neuroco-mputing,2006,70(1):489-501.

[2]LIANGNY,HUANGGB,SARATCHANDRANP,etal.Afastandaccurateonlinesequentiallearningalgorith-mforfeedforwardnetworks[J].IEEETransactiononNeuralNetworks, 2006, 17(6):1411-1423.

[3]付倩, 韓飛, 葉松林. 一種改進(jìn)的集成在線順序極限學(xué)習(xí)機(jī)[J]. 無(wú)線通信技術(shù), 2013, 22(3):39-44.

[4]楊樂(lè), 張瑞. 在線序列ELM算法及其發(fā)展[J]. 西北大學(xué)學(xué)報(bào)：自然科學(xué)版, 2012, 42(6):885-889.

[5]VERMAA,LLORAX,GOLDERGDE,etal.ScalingG-eneticAlgorithmsUsingMapReduce[C]//2009NinthInternationalConferenceonIntelligentSystemsDe-signandApplications.Washington,DC,USA:IEEEComputerSociety, 2010 16(45):13-18.DOI:10.1109/ISDA.2009.181

[6]戎翔, 李玲娟. 基于MapReduce的頻繁項(xiàng)集挖掘方法[J]. 西安郵電大學(xué)學(xué)報(bào), 2011,16(4):37-39.

[7]王家林.大數(shù)據(jù)Spark企業(yè)級(jí)實(shí)戰(zhàn)[M].北京:電子工業(yè)出版社, 2014:20-24;431-458.

[8]WANGB,HUANGS,QIUJ,etal.ParallelonlinesequentialextremelearningmachinebasedonMapReduce[J/OL].Neurocomputing, 2015, 149:224[2015-9-30].http://www.sciencedirect.com/science/article/pii/S092523121401145X.DOI:10.1016/j.neucom.2014.03.076.

[9]劉瑜. 基于云平臺(tái)的OLAP系統(tǒng)研究與實(shí)現(xiàn)[D]. 沈陽(yáng)：東北大學(xué), 2013:48-52.

[10]HUANGGB,ZHUQY,SIEWCK.Extremelearningmachine:Theoryandapplications[J].Neurocomputing, 2006, 70(s1/3):489-501.

[11]梁彥. 基于分布式平臺(tái)Spark和YARN的數(shù)據(jù)挖掘算法的并行化研究[D].廣州：中山大學(xué), 2014:14-27.

[12]ODERSKYM,SPOONL,VENNERSB.ProgramminginScala[M].ArtimaInc, 2011:5-40;51-150.

[13]FANRE,CHANGKW,HSIENCJ,etal.LIBLIN-EAR:alibraryforlargelinearclassification[J].JournalofMachineLearningResearch, 2008, 9(12):1871-1874.

[14]CHANGCC,LINCJ.LIBSVM:alibraryforsupportvectormachines.ACMTransactionsonIntelligentSystemsandTechnology[EB/OL]. [2015-09-20].http://www.csie.ntu.edu.tw/～cjlin/libsvm.

[責(zé)任編輯：祝劍]

ParallelizationofOS-ELMbasedonSpark

DENGWanyu，YANGLixia

(SchoolofComputerScienceandTechnology,Xi’anUniversityofPostsandTelecommunications,Xi’an710121,China)

Abstract:A parallel processing algorithm of online sequential extreme learning machine is proposed for elastic distributed data set parallel computing framework based on Spark platform. By separating the dependence relationship among the matrix of online sequential extreme learning machine, the highly complex matrix of large scale data is distributed to the Spark cluster for parallel processing to figure out the hidden layer output matrix of the multiple incremental data block, and thus, the accelerated solution of the matrix by OS-ELM is implemented. Experimental results show that the algorithm can effectively shorten the learning time while maintaining the accuracy, and therefore improved the ability to expand massive data.

Keywords:online sequential extreme learning machine(OS-ELM), big data, Spark, parallel computing

doi:10.13682/j.issn.2095-6533.2016.02.020

收稿日期：2015-10-27

基金項(xiàng)目：國(guó)家自然科學(xué)基金資助項(xiàng)目(61572399)；陜西省科技新星資助項(xiàng)目(2013KJXX-29)

作者簡(jiǎn)介：鄧萬(wàn)宇(1979-)，男，博士，副教授，從事數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí)與知識(shí)服務(wù)研究。E-mail: 58028654@qq.com 楊麗霞(1988-)，女，碩士研究生，研究方向?yàn)閿?shù)據(jù)挖掘和機(jī)器學(xué)習(xí)。E-mail:498538730@qq.com

中圖分類號(hào)：TP389.1

文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：2095-6533(2016)02-0101-05