基于Spark大數據計算模型的遺傳算法深度前饋神經網絡訓練算法

任 剛,李 鑫,劉小杰,張 陽,郜廣蘭,4,肖東栩

(1.河南工學院 計算機科學與技術學院,河南 新鄉 453003;2.中國礦業大學 計算機科學與技術學院,江蘇 徐州 221116;3. 河南省生產制造物聯大數據工程技術研究中心,河南 新鄉 453003;4.新鄉市虛擬現實與系統重點實驗室,河南 新鄉 453003;5.河南大學 歐亞國際學院,河南 開封 475000)

0 引言

人工神經網絡(Artificial Neural Network, ANN)是一種模擬人腦神經節點信號傳遞的計算模型,該模型可通過大量數據學習找出潛在規律,在很多領域得到了廣泛應用。深度前饋神經神經網絡(Deep Feedforward Neural Network, DFNN)是一種應用較為廣泛的人工神經網絡[1],該模型采用信號向前傳遞的多層網絡結構,可通過訓練方式優化神經網絡節點間權值和閥值,并利用訓練過的模型進行預測,其模型訓練算法是重點研究內容之一[2]。

遺傳算法(Genetic Algorithm, GA)是一種借鑒生物界自然選擇和遺傳機制的全局隨機搜索算法,該算法把問題可能解看作種群個體, 多個個體組成1個種群,通過對種群個體使用選擇、交叉和變異3個遺傳算子,使種群不斷進化,直至產生近似最優解。該算法在全局尋優上表現出魯棒性和高效性,被廣泛應用于各類組合優化問題求解[3]。

遺傳算法深度前饋神經網絡(Genetic Algorithm Deep Feedforward Neural Network, GADFNN)是一種利用遺傳算法對深度前饋神經網絡模型進行訓練的算法。由于綜合了遺傳算法在全局尋優的優勢和深度前饋神經網絡在非線性逼近問題上的優勢,因此,該算法具有較好的計算效率和預測精度,在分類和回歸問題上應用廣泛[4-6]。但是,該類模型傳統訓練算法屬于單機版串行算法,在樣本規模較大時,訓練時間往往較長,難以滿足實際應用對計算時間的要求。

近年來,隨著數據采集技術的不斷提高,遺傳算法深度前饋神經網絡模型訓練樣本呈現出明顯的大數據特點[7],傳統的單機版訓練算法受到很大挑戰,迫切需要一個支持數據并行的訓練算法來滿足大數據樣本訓練的需要[8]。

Spark[9]是一種基于內存的大數據并行計算開源模型,該模型將大數據集分割成多個小數據塊,分配到多個計算節點,各計算節點通過并行計算提高計算效率。該模型通過數據轉換完成業務邏輯計算,具有編程模型簡單、計算高效的特點,被廣泛應用于大數據分析。Spark的高效性為實現數據并行訓練算法提供了一個可能的選擇。但是,由于該模型具有其特有數據編碼和轉換規則,據了解,目前尚無較成熟方法在Spark模型上實現遺傳算法深度前饋神經網絡訓練。

為此,本文將首先研究Spark模型數據編碼和轉換規則與遺傳算法深度前饋神經網絡模型訓練計算過程的內在對應關系,提出一個基于Spark模型的遺傳算法深度前饋神經網絡訓練算法——Spark-GADFNN。

1 遺傳算法深度前饋神經網絡模型

1.1 深度前饋神經網絡模型

深度前饋神經網絡[10]是一種單向多層網絡模型,每層包含多個神經元節點,各層神經元接前一層神經網元信號,并將結果輸送到下一層節點。圖1是一個具有L層的網絡模型,0層是輸入層(Input Layer),L層是輸出層(Output Layer),其余層是隱含層(Hidden Layers)。

l層神經節點j的輸出分兩步計算,首先使用公式(1)計算l-1層輸入集:

(1)

深度前饋神經網絡需要一個激活函數來觸發神經元輸出,本文使用在實際中應用較為廣泛的S型函數,如式(2)所示:

(2)

這樣,第l層節點j輸出為:

(3)

1.2 遺傳算法深度前饋神經網絡訓練算法

經典深度前饋神經網絡訓練算法包括輸入樣本數據(Input sample data)、確定神經網絡結構(Determination of NN structure)、初始化權值和閥值(Initialization of weight and threshold)、權值和閥值訓練((Training of weight and threshold)和收斂判斷(Determination convergence)等5個基本計算過程,該模型通過收斂判斷控制訓練迭代過程,一次訓練過程往往需要多次迭代來完成,整個訓練過程如圖2左側子圖所示。

遺傳算法包括種群初始化(Initialization of population)、評估(Evaluation)、選擇(Selection)、交叉(Crossover)、變異(Mutation)和收斂判斷(Determination of convergence)等6個基本計算過程,其中,收斂判斷通過設定條件負責決定迭代終止,整個過程如圖2中間子圖所示。

遺傳算法深度前饋神經網絡模型訓練算法基本實現方法是將神經網絡訓練過程映射到遺傳算法計算過程中,通過遺傳算法迭代來實現深度前饋神經網絡模型訓練過程。具體來說,輸入樣本數據、確定神經網絡結構、初始化權重和閥值在種群初始化過程中實現,權值和閥值訓練由遺傳算法評估、選擇、交叉和變異過程完成,神經網絡收斂判斷直接映射為遺傳算法收斂判斷等,通過收斂判斷決定是否迭代。具體映射關系如圖2左側映射關系所示。

圖2 Spark-GADFNN訓練算法映射關系

1.3 基于Spark模型的遺傳算法深度前饋神經網絡訓練算法

Spark是一種基于Hadoop分布式文件系統(Hadoop Distributed File System, HDFS)的大數據并行計算模型,以彈性分布式數據集(Resilient Distributed Dataset, RDD)為核心的并行計算模型,RDD是基于內存的只讀數據集合,通過轉換(Transformation)操作完成RDD的處理,轉換操作主要包括map和reduceByKey等操作,map轉換屬于窄依賴轉換,reduceByKey屬于寬依賴轉換,會觸發shuffle過程。

Spark模型采用分布式并行計算架構,首先從HDFS中讀取數據,形成RDD,此RDD一般分布存儲在各集群計算節點內存中。然后,針對RDD,通過一系列轉換操作,形成新的RDD,最終結果重新寫回HDFS,各RDD數據轉換操作采用并行計算模型,以此提高數據處理效率,Spark并行架構如圖3所示。

在利用RDD進行遺傳算法迭代操作時,通常采用鍵值對RDD這種數據集合形式,該數據集合每個元素都是(key,value)鍵值對類型,主要通過map和reduceByKey操作完成業務邏輯。

map輸入為(key1,value1),通過map操作根據具體業務邏輯輸出新的鍵值對(key2,value2),map操作鍵值對轉換形式定義如下:

map:: (key1,value1)→(key2,value2)

(4)

reduceByKey會接收來自map的輸出(key2,value2),此時,Spark模型會啟動shuffle操作,該操作通過全局通信,將分布于不同RDD的鍵值對,按照key2值進行連接,發送給reduceByKey操作,shuffle操作鍵值對轉換形式定義如下:

shuffle:: (key2,value2)→(key2, list(value2))

(5)

reduceByKey操作收到(key2, list(value2))后,根據業務規則聚合成value3,并形成新鍵值(key3,value3),reduceByKey鍵值對轉換形式定義如下:

reduceByKey:: (key2, list(value2))→(key3,value3)

(6)

圖3 Spark分布式并行計算架構

1.4 Spark-GADFNN算法實現

提出的Spark-GADFNN算法實現的關鍵,首先在于確定遺傳算法計算過程到Spark計算過程的映射關系。如圖2右側映射關系所示,提出的Spark-GADFNN算法在Main函數中實現種群初始化,遺傳算法迭代過程由map、reduceByKey和收斂判定(Determination of convergence)操作完成,map負責遺傳算法的評估、選擇、交叉和變異過程,以完成種群進化。

reduceByKey操作負責收集來自map輸出的種群信息,搜索全局最優解,并產生下一代種群。遺傳算法收斂判斷直接映射為Spark-GADFNN的收斂判斷過程。在具體實現上,為了進一步提高效率,該過程與reduceByKey過程合并為一個計算過程。

提出的Spark-GADFNN算法中,遺傳個體編碼形式化定義為:

ind=

(7)

式中,code為個體編碼,fitness為個體適應度。這樣,具有n個個體種群可形式化表示為:

(8)

popValueij=

(9)

populationij表示第j代種群i,popKeyi表示種群i關鍵字,迭代過程中該值保持恒定。Pcij和Pmij分別表示該子種群的交叉和變異概率,bestInd記錄該種群局部最優解,indkij表示該種群第k個體。

提出的Spark-GADFNN實現的另一個關鍵問題是確定map和reduceByKey的鍵值對轉化過程,轉化過程如圖4所示。種群以文件形式在HDFS,map每次讀取1個種群信息,形成鍵值對(key1,value1),如下所示:

key1=popKeyi

(10)

value1=popValueij

(11)

圖4 Spark-GADFNN訓練算法數據轉換過程

為了后繼shuffle過程中不同種群個體都能被送到同一個reducebyKey過程,以便找出全局最優解,并共享該值,將key2設置為0。同時,為了在下1次迭代中,保持種群穩定性,popKeyi作為普通數據元素,暫存在value2中,(key2,value2)形式定義如下所示:

key2=0

(12)

value2=popKeyi∪popValuei(j+1)

(13)

map實現主要代碼如下:map首先使用Evaluation函數計算value1中每個個體ind個體適應度,并更新當前種群最優解。然后,從value1中取出交叉概率和變異概率,并依次進行選擇、交叉和變異操作,并更新種群,此時,產生新一代種群值popValuei(j+1)。最后,輸出(key2,value2)鍵值對。

Algorithm 1: mapInput: (key1,value1);Output: (key2, value2)01for each ind in value1 do02 if ind.fitness==Null do03 Evaluation(ind);04 end if05 if ind.fitness> bestInd.fitness do06 value1.bestInd=ind;07 end if08end for09Pm=value1.getPm();10Pc=value1.getPc();11for (i=0; i++; i

Algorithm 1: map 14 {I″1, I″2}=Mutation({I'1, I'2}, Pm);15 value1=value1-{I1, I2}+{I″1, I″2};16end for17key2=0;18value2={key1}+value1;19EMIT(key2, value2);

生成(key2,value2)后,Spark模型啟動shuffle過程,具有相同key2的value2被連接為新的鍵值對(key2,list(value2))。由于算法1將key2設置為0,所以,所有value2被鏈接在一起,形成list(value2)。這意味著,所有種群被聚合在一起,以便尋找全局最優解。這一步是算法實現的關鍵步驟,即利用Spark系統提供shuffle機制完成種群聚合。

reduceByKey接收到來自Spark系統傳來的(key2,list(value2)),負責將其轉換為(key3,value3),作為下次的迭代輸入。為了保持種群穩定性,將暫存在list(value2)中的popKeyi取出,賦于key3。同時,用全局最優解替換value2中的局部最優解,輸出鍵值對(key3,value3)如下所示:

key3=popKeyi

(14)

value3=value2+{globalInd}-{bestInd}

(15)

reduceByKey操作首先查找全局最優解globalInd,然后通過Convergence函數判斷收斂條件。收斂有兩個條件,一個是現有全局最優解滿足預定條件,一個是達到最大迭代次。若滿足收斂,則直接結束;否則,用當前全局最優解替換各種群,最后生成鍵值對(key3,value3)。具體實現如算法2所示。

Algorithm 2: reduceByKey Input: (key2, list(value2))Output: (key3,value3)01for each value2 in list(value2) do02 if bestInd.fitness> globalInd.fitness do03 globalInd=bestInd;04 end if05end for06if convergence(key2, value2)==TRUE do07 return globalInd;08end if09for each value2 in list(value2)do10 value3=value2+{globalInd}-{bestInd};11 key3=value2.getPopKey();12 value3=value2-{key3};13 EMIT(key3, value3);14end for

2 性能驗證

通過三組實驗比較傳統GADFNN訓練算法[5]與提出的Spark-GADFNN訓練算法在預測精度和訓練效率上的表現。采用UCI實驗室提供的Lung Cancer (LC)[11]、Beijing PM2.5 Data (BPM2.5D)[12]和Heterogeneity Activity Recognition (HAR)[13]三個數據集,其基本信息如表1所示,取樣本數90%作為測試數據集,10%作為驗證數據集。

表1 實驗數據集

2.1 實驗1:計算節點擴展性

計算節點從1遞增至8,算法迭代80次自動結束,記錄運行時間,單位為秒,實驗主要參數設置如表2所示,計算結果如表3所示。由表3可以看出,在小規模數據集LC上,隨著計算節點個數增加,計算時間沒有減少,反而增加,計算節點擴展性不佳,其原因在于該數據集規模過小,系統通信成本和數據存儲時間在整個計算時間上占了大部分。對于中等規模數據集和大規模數據集算法,隨著計算節點的增加,訓練時間逐步減少,表現出良好的擴展性。同時確定,在小規模數據集LC上,算法最佳計算節點為1,在中等規模數據集BPM2.5D和大規模數據集HAR上,最佳計算節點數都為8。

表2 實驗參數

表3 計算節點擴展性分析

2.2 實驗2:預測精度分析

迭代次數從10逐步擴展到80,記錄不同迭代次數下模型預測精度,GADFNN采用單機版算法,Spark-GADFNN計算節點數在小規模數據集LC上設置為1,在中規模和小規模數據集上皆設置為8,該數據是實驗1給出的最佳并行計算節點數,實驗結果展示在表4,由表4可以看出,對于三種規模數據集,兩算法在迭代過程中,誤差率始終不大;還可以看出,兩算法的計算誤差都在40次迭代后達到穩定,誤差均相同。這說明數據集規模對于算法收斂速度和預測精度無顯著影響,其原因在于提出的算法和原算法僅在計算方式上有區別,并沒有改變原算法的計算原理。該實驗表明本文提出的算法保留了原算法在收斂速度和預測精度誤差上的優勢。

2.3 實驗3:訓練時間分析

兩算法迭代次數都取40,實驗2證明該數值下兩算法均收斂。Spark-GADFNN算法在LC、BPM2.5D和HAR數據集上,計算節點數分別設置為1、8、8,這是實驗1給出最佳計算節點數,時間單位為秒,計算結果如表5所示。由表5可以看出,在小規模數據集LC上,本文算法耗時較多,在時間上無優勢,其原因在于Spark計算模型在單節點計算模式下,數據存儲和模塊通信都消耗一部分時間,其性能不如普通單機版串行算法。

在中等規模數據集BPM2.5D和大規模數據集HAR上,本文算法訓練時間分別縮短為原算法的18.18%和16.67%,計算時間明顯縮短,其原因在于數據集被平均分配到8個計算節點上,Spark計算模型的優勢得以發揮。實驗表明,本文算法在中、大規模數據集上訓練時間具有明顯優勢。

表4 預測精度分析

表5 訓練時間分析

3 總結

提出了一個基于Spark大數據計算模型的遺傳算法深度前饋神經網絡模型訓練算法Spark-GADFNN,該算法實現了經典遺傳算法深度前饋神經網絡模型訓練算法數據并行。實驗表明,在中、大規模數據集上,該算法訓練時間分別縮短到原算法18.18%和16.67%。下一步可研究利用Spark模型實現其他網絡模型訓練算法的并行化。