鄧萬宇，楊麗霞

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

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

鄧萬宇，楊麗霞

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

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

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

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

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

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

1OS-ELM算法描述

OS-ELM是針對動態(tài)數(shù)據(jù)應(yīng)用研制的在線增量式快速學(xué)習(xí)算法[2]。假設(shè)輸入樣本N個，第j個樣本設(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é)點數(shù)為L，隨機生成輸入層與隱藏層的連接權(quán)值ai和隱含層閾值bi，βi為第i個隱藏層節(jié)點到輸出節(jié)點的輸出權(quán)值。當運用增加型隱藏層節(jié)點時對第j個樣本，第i個隱藏層結(jié)點來說，隱藏層輸出為G(ai,bi,xj)=g(ai·xj+bi)。OS-ELM算法包括初始化階段和在線連續(xù)學(xué)習(xí)階段兩個階段[8-9]。

計算初始隱藏層輸出矩陣

(2)

已知目標輸出

(3)

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

HB=T[10],

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

(4)

其中

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

(5)

(6)

其中I為單位矩陣。

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

2.1基本原理

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

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

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

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

為了實現(xiàn)對增量訓(xùn)練數(shù)據(jù)塊隱藏層輸出矩陣并行化設(shè)計，對OS-ELM算法進行改進。該改進算法命名為基于Spark在線連續(xù)極限學(xué)習(xí)機并行算法(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é)點個數(shù)L，訓(xùn)練數(shù)據(jù)塊k+1。

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

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

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

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

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

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

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

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

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

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

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

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

輸出：隱藏層輸出矩陣Hi,目標輸出Ti。

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

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

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

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

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

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

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

3實驗結(jié)果與分析

3.1實驗設(shè)置

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

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

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

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

3.2評估結(jié)果

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

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

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

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

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

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

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

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

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

3.2.3擴展性測試

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

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

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

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

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

4結(jié)束語

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

參考文獻

[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]付倩, 韓飛, 葉松林. 一種改進的集成在線順序極限學(xué)習(xí)機[J]. 無線通信技術(shù), 2013, 22(3):39-44.

[4]楊樂, 張瑞. 在線序列ELM算法及其發(fā)展[J]. 西北大學(xué)學(xué)報：自然科學(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的頻繁項集挖掘方法[J]. 西安郵電大學(xué)學(xué)報, 2011,16(4):37-39.

[7]王家林.大數(shù)據(jù)Spark企業(yè)級實戰(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]劉瑜. 基于云平臺的OLAP系統(tǒng)研究與實現(xiàn)[D]. 沈陽：東北大學(xué), 2013:48-52.

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

[11]梁彥. 基于分布式平臺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.

[責任編輯：祝劍]

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

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

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

中圖分類號：TP389.1

文獻標識碼：A

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